True Random Number Generator
in [Cryptography]
|
From: unruh on 9 Feb 2010 17:28 On 2010-02-09, Mok-Kong Shen <mok-kong.shen(a)t-online.de> wrote: > bmearns wrote: > [snip] >> More generally, the entropy per symbol is irrelevant in terms of brute >> force attacks, whether you're talking about the key, the plaintext, or >> the ciphertext. Even if all the entropy the ciphertext had was the 128 >> bits from the key, it wouldn't matter if that was spread out over 128 >> binary digits, or a million octets; there are still 2^128 different >> possible values. The entropy per symbol is only relevant to the >> efficiency of the encoding. >> >> So in summary: the entropy of the ciphertext is inconsequential in >> terms of security. If it has low entropy, that is necessarily because >> the plaintext has low entropy. > > Your arguments are understadable. However I have one layman's problem: > Isn't the single theoretical "perfect" security, provided by OTP, based > on the other hand on the concept of entropy? No. It is based on the concept that any output can be obtained by decryption with some key of the input, and if there is nothing to choose between the keys, there is nothing to choose between the possible outputs. > > Thanks, > > M. K. Shen
From: Mok-Kong Shen on 9 Feb 2010 17:33 Am 09.02.2010 23:28, schrieb unruh: > On 2010-02-09, Mok-Kong Shen<mok-kong.shen(a)t-online.de> wrote: >> bmearns wrote: >> [snip] >>> More generally, the entropy per symbol is irrelevant in terms of brute >>> force attacks, whether you're talking about the key, the plaintext, or >>> the ciphertext. Even if all the entropy the ciphertext had was the 128 >>> bits from the key, it wouldn't matter if that was spread out over 128 >>> binary digits, or a million octets; there are still 2^128 different >>> possible values. The entropy per symbol is only relevant to the >>> efficiency of the encoding. >>> >>> So in summary: the entropy of the ciphertext is inconsequential in >>> terms of security. If it has low entropy, that is necessarily because >>> the plaintext has low entropy. >> >> Your arguments are understadable. However I have one layman's problem: >> Isn't the single theoretical "perfect" security, provided by OTP, based >> on the other hand on the concept of entropy? > > No. It is based on the concept that any output can be obtained by > decryption with some key of the input, and if there is nothing to choose > between the keys, there is nothing to choose between the possible > outputs. But what characterizes an OTP (by definition)? Not via its entropy content? M. K. Shen
From: Mok-Kong Shen on 9 Feb 2010 17:36 Am 09.02.2010 23:24, schrieb unruh: > On 2010-02-09, Mok-Kong Shen<mok-kong.shen(a)t-online.de> wrote: >> unruh wrote: >> >>>> Just an observation: If one uses a good block cipher like AES to >>>> encrypt, it is common that a single key is used to process a fairly >>>> long plaintext stream. But the key has at most 128 bits of entropy. >>>> Isn't it a miracle that the resulting ciphertext stream (a result >>>> of combination) has very high entropy? Or is it rather the case that >>>> the ciphertext stream doesn't possess much higher entropy per bit >>>> "after all" in comparison with the plaintext stream (the enhancement >>>> of entropy per bit being at most 128 divided by the (commonly >>>> relatively large) total number of bits being processed) and thus the >>>> achieved security, on which one "believes", were actually an illusion >>>> (cf. optical illusions)? >>> >>> Of course it is. We know the attack. Try every one of the 2^128 keys and >>> see which one works. That is the 128 bits of entropy. the problem is >>> that "try all 2^128 keys" is really really tedious. Ie, this indicates >>> that if done properly, 128 bits of entropy is sufficient to hide any >>> text you wish, for all practical purposes. (at least for now). 128 bits >>> of entropy is really a lot of different states. >> >> My point is this: If one considers the input natural language text has, >> say, 1 bit of entropy per character (this is the lowest figure of >> estimate I have seen of all textbooks), then the ciphertext from >> encryption using AES has not much more than 1.0001 bit of entropy per >> character. I am not sure that people are commonly conscious of that. > > It depends on how long the text stream is. In the limit as the text > stream goes to infinity, the output entropy equals the input entropy. > For one character, the entropy is max (8 bits). > > You can see this easily. The way you break this cypher is that you do an > exhaustive search. But that means that you have to be able to recognize > a valid cleartext message. You do that by using the regularities in the > clear text ( that 1 bit of entropy per character). The more text you > have the more regularity you have to use. > This also illustrates that to a large extent these discussions of > entropy are irrelevant. Even if the entire message is 2*128 bits, what is added in can't be more than 0.5 bit per bit (of bits being processed), isn't it? That's my point, no more no less. See also my response to your other post. M. K. Shen
From: Mok-Kong Shen on 9 Feb 2010 17:42 unruh wrote: >> In textbook sources, English charaters (hence base 26) are said to have >> entropy somewhere between 1.0 and 1.5 bit pro chaaracter (See Stinson). >> As layman I don't know the details of how these figures got evaluated. >> Certainly that's not a trivial task, maybe indeed very very >> difficult, as you said. But that has nonetheless been done! > > Calculate the frequency distribution of the letters. Do Sum P_i ln(P_i) > where P_i is the noralised frequency of the ith letter. This is an upper > bound. You can also look for correlations to refine the estimate. Do > this for a bunch of sample texts. Not hard. I don't have that impression. I vaguely remember (hence I didn't mention in my previous post) to have seen Shannon's paper where he obtained an estimate. If I remembered right (I am not sure), experiments using test persons were done. M. K. Shen
From: bmearns on 9 Feb 2010 22:31
On Feb 9, 4:25 pm, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: > bmearns wrote: > > It depends on your meaning of perfect security. Even with an OTP, it > > is possible to guess the plaintext. It just so happens that the > > ciphertext does not give you any information about it (except its > > length). But yes, I suppose the security of an OTP is pretty closely > > tied to entropy. What an OTP really does is eliminate all limiting > > factors. In the general case, the key of a non-OTP cipher will be the > > limiting case: it will have less entropy than anything else (except > > for short messages), and is therefore the easiest to brute force. For > > an OTP this is no longer the case, the key will never have less > > entropy than the plaintext since they are the same length, and the key > > has maximum entropy (1 Shannon per bit). > > > To your original point, however, it is not the entropy per symbol of > > the ciphertext that provides security, even for an OTP. You could > > perform your OTP and then encode each bit of encrypted output as an > > ASCII description of the bit ("TRUE" or "FALSE). The entropy per bit > > is going to drop dramatically (2 Shannons per 9 octets, about 0.11 > > Shannons per bit), but it is not less secure than if you left it in > > binary. This is what you were missing when you were pointing out the > > low per-symbol entropy contribution AES makes. The fact that each > > octet of ciphertext only has (for instance) 0.00001 extra bits of > > entropy compared to the input doesn't change the fact that the message > > as a whole still has 128 more bits of entropy, and is therefore 2^128 > > times harder to guess. > > The OTP xor-ed plaintext bits, i.e. a sequence of ciphertext bits, have > full entropy and have perfect security in a certain accepted definition > of crypto. My problem is this: An AES encrypted plaintext bits (let's > forget that they come originally from symbols), doesn't have perfect > security. Can't one view this fact from the view point that this is > because this sequence of bits doesn't have full entropy? If not, why not? > > Thanks, > > M. K. Shen You're assuming causation where none is required. AES also generates binary ciphertext, that doesn't mean that this is the reason it doesn't have perfect security. Likewise, just because it doesn't have maximum entropy doesn't mean this is necessarily the reason it isn't perfectly secure. -Brian |