True Random Number Generator
in [Cryptography]
|
From: bmearns on 9 Feb 2010 16:03 On Feb 9, 3:13 pm, Mok-Kong Shen <mok-kong.s...(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? > > Thanks, > > M. K. Shen 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. -Brian
From: Mok-Kong Shen on 9 Feb 2010 16:11 Am 09.02.2010 21:42, schrieb bmearns: > On Feb 9, 3:20 pm, Mok-Kong Shen<mok-kong.s...(a)t-online.de> wrote: >> Spinner wrote: >>> Silly statement. The fact that a totally provably random OTP has never >>> been created is going to be a helluva suprise to a lot of people who >>> have been using them for many manyt years. Not to mentioni there are >>> websites where you can go get a list of quantum-generated (radioactive >>> decay) random numbers. >> >> The problem is "proving" that what one has at hand "is" a OTP. I can't >> conceive how one could deliver a proof in the sense of proofs in math. >> This is analogous to the case of a point in elementary geometry. >> One simply can't have in the real world a point that has no "size", >> though one could have arbitrarily good approximation of that. In matter >> of OTP in "practice", see also the story about Venona. > This in particular is far from my realm of expertise, but as I > understand it, it is the generator itself which can be proven to be > random. It's true, you can't look at the OTP itself and prove that it > is truly random, but if the values come from a truly random process, > like a quantum effect, then the generator can be proven random, and > therefore the data it produces is as well. I am afraid that there is in reality a logical problem here, i.e. a circularity in argumentation. How does one "know" that employing quantum effect gives "perfect" randomness? Certainly one could "define" it that way, but that I would consider to be problematic. Or consider a "fair coin". As a "theoretical" concept it is excellent and very useful. But can one really make such a coin "practically", depite all the advances e.g. in nano-technology today and in future? M. K. Shen
From: Mok-Kong Shen on 9 Feb 2010 16:25 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
From: unruh on 9 Feb 2010 17:24 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. > > M. K. Shen >
From: unruh on 9 Feb 2010 17:26
On 2010-02-09, Mok-Kong Shen <mok-kong.shen(a)t-online.de> wrote: > WTShaw wrote: > >> Remember that with higher bases, entropy may not be easily described >> in bits, and might have more useful bang for the buck. Too difficult >> subjects are avoided because they are that, not that they are not >> worth knowing, or are even superior to the usual gruel. > > 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. > > M. K. Shen |