RE: [sqlite] Encryption and fixed header values (was Re: [sqlite] Why can i open a textfile?)
On Fri, 2005-08-26 at 12:53 -0400, Griggs, Donald wrote: > Regarding Mrs. Brisby's ending comment: >"A better defense: use a different key each time. Encrypt the session key > separately." > > I may way off in asking this, but: > Since we're talking about the encyption of data at rest, and aren't in a > client-server situation, how could sqlite make session keys work? What > would constitute a session? The lifetime of the session is the time between encrypting the data and decrypting it. It doesn't have to be on line. PGP (for example) encrypts the message using symmetric ciphers (like RC4 or Blowfish) using a completely random key. It then encrypts the key using the public-key algorithms desired (RSA, DSA) and writes the encrypted key. This works because the receiver decrypts the encrypted random key and uses it to decode the rest of the message. It has some fantastic benefits: 1. assymetric ciphers are slow, this is certainly much faster 2. if any information is leaked about the "real key", it's very little. Often very few bits of the real key are needed. 3. Brute-force attacks on the message will yield the session key, but brute-force attacks on the encrypted session key won't yield enough information to reconstruct the key. This is similar to how SSL works as well, although the exchange is done "on line" - which is probably why you're confused about it. This is almost certainly what people are talking about when they refer to session keys. With some ciphers (like RC4), the session key can be obtained through other means. Because RC4's encryption/decryption routine permutes the keyspace, encrypting _anything_ causes permutations to occur. But because those permutations are wildly predictable (at first), many people discard the beginning of the RC4 keystream. I disagree with this. I suggest taking some random junk and encrypt it. Throw away the result. This permutes the keystream faster, and it means that no plaintext is encrypted twice accidentally. The random junk isn't secret. You can store it at the head of your ciphertext. This "random junk" is often called an initialization vector- and is a common way to reuse keys with more safety. This "IV" and "key" combination are often considered "the session key".
Re: [sqlite] Encryption and fixed header values (was Re: [sqlite]Why can i open a textfile?)
On Fri, 2005-08-26 at 16:21 +0200, F.W.A. van Leeuwen wrote: > > > > The usual defense against this attack is to mix some random information > > into the beginning of the plaintext. > > > > A better defense: use a different key each time. Encrypt the session key > > separately. > > > > And /or start encrypting after the fixed header. Agreed. Thanks for pointing this out.
RE: [sqlite] Encryption and fixed header values (was Re: [sqlite] Why can i open a textfile?)
Regarding Mrs. Brisby's ending comment: "A better defense: use a different key each time. Encrypt the session key separately." I may way off in asking this, but: Since we're talking about the encyption of data at rest, and aren't in a client-server situation, how could sqlite make session keys work? What would constitute a session? Donald Griggs Opinions are not necessarily those of Misys Healthcare Systems nor its board of directors.
Re: [sqlite] Encryption and fixed header values (was Re: [sqlite]Why can i open a textfile?)
> > The usual defense against this attack is to mix some random information > into the beginning of the plaintext. > > A better defense: use a different key each time. Encrypt the session key > separately. > And /or start encrypting after the fixed header. Best regards, Frank.
Re: [sqlite] Encryption and fixed header values (was Re: [sqlite] Why can i open a textfile?)
On Wed, 2005-08-24 at 22:55 -0400, D. Richard Hipp wrote: > Weaknesses in RC4 have been found where > the first few numbers coming out of the PRNG leak information about the > key. If an attacker can guess the first few bytes of plaintext, and > hence guess the first few numbers from the PRNG, and can do this many > many times (millions of times) then the attacker can eventually > reconstruct > the key. I noticed this. You understate how much it helps. The first few cycles of RC4 are so bad that key recovery is easy for modern general purpose computers. > The usual defense against this attack (and the one used by SQLite) > is to discard the first 1000 bytes or so of information coming out > of the PRNG. No key information leaks into later bytes of the > PRNG stream (at least as far as we know) so this secures the cypher > from attack. It doesn't need to leak information about the key. A combination known-plaintext and known-ciphertext attack works very well against RC4. http://groups.google.com/group/sci.crypt/browse_frm/thread/2716ac20a3fc9971/64eba041932a98ae?lnk=st&rnum=1&hl=en Since the header is well known, convincing the program to encrypt the database (by say, making a change to it) several times allows the user to collect some known-plaintext and lots of ciphertext very quickly. The usual defense against this attack is to mix some random information into the beginning of the plaintext. A better defense: use a different key each time. Encrypt the session key separately.
Re: [sqlite] Encryption and fixed header values (was Re: [sqlite] Why can i open a textfile?)
On Wed, 2005-08-24 at 22:32 -0400, Mrs. Brisby wrote: > > There are several attacks that can be used to derive the original key > > state, but they all require huge samples of data to analyze. > > No they don't. That's the problem. They only need a large number of > _uses_ of the key, not large amounts of data. Adding some random junk to > the beginning of the plaintext would help some, but I don't think SQLite > does this. > RC4 is a pseudorandom number generator (PRNG) against which the plaintext is XORed to yield cyphertext. Weaknesses in RC4 have been found where the first few numbers coming out of the PRNG leak information about the key. If an attacker can guess the first few bytes of plaintext, and hence guess the first few numbers from the PRNG, and can do this many many times (millions of times) then the attacker can eventually reconstruct the key. The usual defense against this attack (and the one used by SQLite) is to discard the first 1000 bytes or so of information coming out of the PRNG. No key information leaks into later bytes of the PRNG stream (at least as far as we know) so this secures the cypher from attack. -- D. Richard Hipp <[EMAIL PROTECTED]>
Re: [sqlite] Encryption and fixed header values (was Re: [sqlite] Why can i open a textfile?)
On Mon, 2005-08-22 at 16:39 -0500, Dennis Jenkins wrote: > RC4 is basically an XOR against a huge one-time pad. No it's not. The only thing like a one-time pad is a one-time pad. What makes an OTP secure isn't the protocol, but where the bits come from. If they come from ANYWHERE but a truly random source then it is not secure. RC4/ARCFOUR isn't a random source of bits, so it isn't a one-time pad. > That pad is creating using a "key scheduling algorithm". No it's not. The key scheduling system moves S-boxes around. There are exactly 256 S-boxes with RC4/ARCFOUR. If you really did perform an XOR operation on those SBOXes you would have no security unless: * your key was exactly 256 bytes * your data stream was exactly 256 bytes Nevertheless, it still wouldn't be much security because you probably didn't chose a strong key to begin with. > The key state for the random number generator is 256 bytes of data and two > 8-bit indicies. No it's not. The substitution array (S-boxes) is 256 bytes. It essentially translates one byte into another byte, then performs a permutation on the S-boxes. That permutation is fixed. The S-boxes are moved around each step, thus increasing the run-length. Unfortunately, its not enough- getting the initial key bytes of the stream makes it much easier to reconstruct the rest of the swapping routine. > There are several attacks that can be used to derive the original key > state, but they all require huge samples of data to analyze. No they don't. That's the problem. They only need a large number of _uses_ of the key, not large amounts of data. Adding some random junk to the beginning of the plaintext would help some, but I don't think SQLite does this. > RC4 is not the strongest encryption available, but for most of us, it is good > enough. ... and it wouldn't matter anyway because the key exists in the software that decrypts it. That's much easier to get to anyway. > The best way to attack any system using sqlite w/ the crypto extension > is to hook the call to "sqlite3_key()" and just steal the rc4 key > directly. Much easier than crunhcing numbers on a super computer. At least on this, I agree.
Re: [sqlite] Encryption and fixed header values (was Re: [sqlite] Why can i open a textfile?)
On Mon, 2005-08-22 at 17:19 -0400, Mike Shaver wrote: > On 8/22/05, Edwin Knoppert <[EMAIL PROTECTED]> wrote: > > Hmm, but every known file format has an header. > > Sqlite has a string, not really a header as it seems. > > Maybe for v4 to implement a real header (if not yet) > > A header doesn't need to be encrypted. > > (A bit for testing if it's encrypted might have it use as well) > > In fact, I was wondering about this very issue when I was working on > my own encryption layer for Mozilla's storage use. Does the reliable > format of the first page (known sqlite header string, various other > fields that are very likely to be zero or in some way related to the > size of the DB file) not make known-plaintext attacks on the encrypted > database much easier? The key schedule is perturbed by a randomly chosen nonce that is added to each page. The size of the nonce is selectable when the database is created and defaults to 4 bytes. This makes an encrypted database about 0.4% larger than an unencrypted database (since the nonce has to be stored, thus reducing the space available to store real data) but it also make known or chosen plaintext attacks considerably more difficult. -- D. Richard Hipp <[EMAIL PROTECTED]>
Re: [sqlite] Encryption and fixed header values (was Re: [sqlite] Why can i open a textfile?)
Mike Shaver wrote: On 8/22/05, Edwin Knoppert <[EMAIL PROTECTED]> wrote: Hmm, but every known file format has an header. Sqlite has a string, not really a header as it seems. Maybe for v4 to implement a real header (if not yet) A header doesn't need to be encrypted. (A bit for testing if it's encrypted might have it use as well) In fact, I was wondering about this very issue when I was working on my own encryption layer for Mozilla's storage use. Does the reliable format of the first page (known sqlite header string, various other fields that are very likely to be zero or in some way related to the size of the DB file) not make known-plaintext attacks on the encrypted database much easier? Given that the encryption is limited to a page at a time due to the pager implementation (and placement of the hooks in sqlite), it would seem that that would be fairly worrisome. I can mitigate it a bit by having the page number affect the key selection, but I'm still sort of nervous about it. Mike I hope that I don't spill too many beans here My company has licensed the RC4 encryption add-on for sqlite. RC4 is basically an XOR against a huge one-time pad. That pad is creating using a "key scheduling algorithm". The key state for the random number generator is 256 bytes of data and two 8-bit indicies. There are several attacks that can be used to derive the original key state, but they all require huge samples of data to analyze. RC4 is not the strongest encryption available, but for most of us, it is good enough. The best way to attack any system using sqlite w/ the crypto extension is to hook the call to "sqlite3_key()" and just steal the rc4 key directly. Much easier than crunhcing numbers on a super computer. http://en.wikipedia.org/wiki/Rc4