John Kennedy wrote:
>
<snip>
> Right now, we're operating under the assumption that the serpent cipher
> is secure and that I could encrypt gigabytes of zeros securely and it
> wouldn't do any good to a brute-force attacker, at least directly.
> The easiest way in is still through attacking the key.
>
Yes. Provided you don't use ECB encryption. Sorry yet another term for
you... But this one is easy:
ECB (Electronic CodeBook) is just the simplest form of encryption using
block ciphers: Let P[0],...,P[n] be the plaintext blocks (each of size
equal blocksize of the cipher). Then the resulting ciphertext
C[0],...,C[n] will be
C[i] = Serpent(K,P[i]) for i = 1,...,n (K = key).
Ie. you encrpyt each block individually. Thus, if you encrpyt an
all-zreros plaintext, all P[i] will be equal (zero) and hence all C[i]
will be equal. Not good.
Therefore, the linux loop_gen driver uses CBC encryption (Cipher Block
Chaining):
With the notation above, the ciphertext will be calculated as follows:
C[0] = Serpent( K, IV+P[0] ),
C[i] = Serpent( K, C[i-1]+P[i] ),
where '+' is XOR and IV is an Initialization Vector that can be choosen
randomly. Strictly speaking, the ciphertext now becomes
(IV,C[0],...,C[n]), because you must remember the IV to be able to
decrypt. Thus, if you encrypt all zeros, the ciphertext blocks will
still be different.
> The key is just a bitstream, X bits long. I could try all 2^X possible
> values to try and brute-force it, knowing I got it right when I see the
> gigabyte of zeros. That should be made computationally infeasible for
> a reasonable period of time, so the trick is to really cut back and find
> the smallest possible subset of 2^X to try.
>
Exactly.
> [tradeoff between security and the time it takes to decrypt
> the data. typically you want it to decrypt as fast as possible
> and still keep it as painful as possible for the brute-forcers,
> trusting that the cpu-expensive key generation will stop people
> from generating and trying to use a lot of keys very quickly.]
>
Not really. It helps if you have an expensive key-setup procedure. But
that can be pipelined, so that the actual throughput will not be
decreased (speaking of hardware decryption, of course).
Usually, you obtain the desired security margin by making the possible
number of keys so vast, that trying all of them in turn would require
thousands of times the age of the universe if you had one million
computers that can test one million keys per second each (the normal
example of the order of complexity brute-force should have).
> The hash that makes the key is there to make that difficult.
No. It's there to make it convenient for the user. Instead of trying to
remember
key = 580687838abb0ae8ad77a8192c6fc6be,
he only has to remember some nice passphrase.
> It takes
> a small amount of human-friendly bits and converts it into a much longer
> bitstream with a wide output-value range. It won't be any more random,
> but it hopefully guarantees you that brute-forcers can't eliminate any
> of the 2^X possibilities for the cipher key.
>
Or make it harder to do, yes.
> The brute-forcers then have to attack the key itself. It is a one-way
> hash and should be computationally expensive to generate, which cuts down
> on the number of attempts you can make in a time interval. Once again,
> you're trying to figure out ways to cut down on the possible input.
>
Exactly.
> [this can be very painful to generate, since it is a one-time cost
> if you know the correct password and it is good to make it as
> painful as you can if you don't.]
>
Yes, but it would be more effective to increase the cipher's key length
instead.
> Here is where the entropy comes into play and where I start to
> tie knots with my brain, tongue and fingers.
>
> You want N bits of entropy (good, random numbers). If those N bits
> are from a keyboard, you only get ~1.3 bits per key (byte). If they're
> a nice secure number from /dev/random (presuming it has good entropy)
> you should be able to get all 8 bits/byte. The only trick is that you
> have to remember those bits or you won't be able to decrypt your data.
>
Yep. Though entropy is not about random numbers. It's more about
information that is contained in the data. Suppose you want to compess
some data. And you want to know how well you can do that. If that data
is english text then the famous 1.3 bits/char tell you that you cannot
do better than to appox. 1.3/8=16.25%. If you have C source code, then
you might do better, simply because it has more structure, the text is
more predictable (you know that if you have a word 'for' then the next
few character will most probably be whitespace, followed by '(' and most
probably "i=0;i<somethung;i++" ), it has less entropy. Any if you have a
sequence of real random numbers, then you cannot compress them at all.
> Is the cipher-encrypted data any more secure with less entropy than
> with more entropy?
You mean the other way round, no? It's more secure iff the key contains
more entropy, ie. there are simply more possibilities.
> I think the bit that I have to bend my brain around
> is that the answer is *NO*. Less entropy just means that the attacker
> has to try fewer hashes, and in the end fewer cipher keys.
>
Yes. If you take your question as you asked it, and not as I answered
it.
> As an example, if I got *really* unlucky and my high-entropy bitstream
> happened to be all zeros, the data isn't encrypted any more securely than
> if I had a really bad hash generator that only let me pick a single digit
> between 0 and 9 as the bitstream. It makes a great deal of difference to
> an attacker that is thinking about trying to brute-force me. 2^X vs. 10.
>
No. If you have an key with entropy 128 bits and it happens to be all
zeros (this has then probability 2^{-128}), this will be nothing the
attacker can take advantage of. An all-zeros sequence will be just as
likely to occur as the sequence I gave you above in the line with "key
=". Yet, brute-force key search may of course start at an all-zeros key,
yet it could as well start with 580687838abb0ae8ad77a8192c6fc6be.
Entropy is not about a given key. It is about the size of the set of
possibilities this key has been chosen from.
> It seems like it really doesn't matter what I use as the hash input, so
> long as it has sufficient entropy to provide a good range of output.
>
Yes. You can enter 100 chars of english text, or 32 chars of hexadecimal
digits, representing output from /dev/random.
> In my original email, above, I'm protecting a key (key2, with a
> good range of input) with encryption, that is decoded by another key
> (key1, with a smaller range of input). If I knew I had decrypted key2
> correctly with key1 then I would have a weakest-link situation. If I
> don't know, then an incorrect key2 complicates the hell out of finding
> the correct cipher key. It may not magnify it, but I doubt if it helps
> to eliminates anything.
>
Yes, is does not help, but it is still moot. That is because you can be
in the following two cases:
a.) Your encrypted second key is accessible by the attacker.
b.) It is not.
ad a) You increase the complexity of the attack by 2. That is because
the attacker can attack your passphrase, decrypt the second key (he may
not know whether that decryption yields the real key, but he can check
so by) decrypting the first ciphertext block and check for all-zeros. So
instead of one decryption using the direct method, he has to do two.
ad b) Then you need not encrypt the second key at all (at least not in
theory).
> It may not contribute a whole lot to the security, but if key2 is
> disposed of the pulling-fingernails approach won't work for decryption. (:
>
How can you? If you throw away key2, then you are no longer able to
decrypt the data yourself. And an attacker, not believing you, may still
pull your fingernails while slowly asking the question "Where do you
have it?" again and again (repeat 10 times).
Bottomline: Choose a passphrase that has at least 64 bits of entropy and
you should be as secure as you need to be.
Marc
--
Marc Mutz <Marc@xxxxxxxx> http://EncryptionHOWTO.sourceforge.net/
University of Bielefeld, Dep. of Mathematics / Dep. of Physics
PGP-keyID's: 0xd46ce9ab (RSA), 0x7ae55b9e (DSS/DH)
Linux-crypto: cryptography in and on the Linux system
Archive: http://mail.nl.linux.org/linux-crypto/
