Path: csiph.com!news.mixmin.net!aioe.org!.POSTED!not-for-mail From: Kaz Kylheku Newsgroups: comp.programming Subject: Re: Researches in quantum computing seem to progress only extremely slowly Date: Fri, 4 Sep 2015 20:23:22 +0000 (UTC) Organization: Aioe.org NNTP Server Lines: 73 Message-ID: <20150904130751.461@kylheku.com> References: <34teuahtcltdi1mrq4gj95bu8gacjv112i@4ax.com> <0a1fua58g3o3sbe715rv0ugvvkkdd06lvr@4ax.com> <3vefualelae74fhsmcs0elv5us837istlh@4ax.com> NNTP-Posting-Host: OGJi3KNpFOhM58UHZwXj0w.user.speranza.aioe.org X-Complaints-To: abuse@aioe.org User-Agent: slrn/pre1.0.0-18 (Linux) X-Notice: Filtered by postfilter v. 0.8.2 Xref: csiph.com comp.programming:5810 On 2015-09-04, Mok-Kong Shen wrote: > Am 03.09.2015 um 17:49 schrieb Robert Wessel: >> On Thu, 3 Sep 2015 16:51:00 +0200, Mok-Kong Shen > [snip] >>> Thank you for your kind efforts to help me understand the paradoxical >>> phenomenon. Excuse me however for my slow learning capability and allow >>> me to ask a question so that I could be sure of having correctly >>> captured what you wrote. Is a good "apparent randomness" (e.g. one with >>> a score near 1.00 from diehard) sufficient for a bit sequence of n >>> bits to securely encrypt a plaintext bit sequence of n bits with xor? >>> (A simple yes/no is sufficient for the question. I might under >>> circumstances have a 2nd question depending on that.) >> >> >> No. Diehard will return a 1.00 (or near that) for the output from a >> good (non-CS) PRNG (like Mersenne Twister). Using MT will not be >> secure. >> >> OTOH, diehard should show (near) 1.00 on any CSPRNG (say AES in CTR >> mode). So a (near) 1.00 entropy rating from diehard is a necessary >> condition, but not a sufficient one. IOW, if your (hoped for) >> CSPRNG's output does not get a ~1.00 from diehard, it's probably not >> CS (or a very good PRNG, either). > > I understand that a score of diehard of 1.0 shows only that each > bit has 1 bit of "apparent entropy". But isn't it that for a very > secure keystream for stream encryption each bit should have (nearly) > 1 bit of "true" entropy? No, that is not a requirement. A fixed amount of key entropy can protect a much larger message. Ideally, the difficulty of breaking that encryption would be equivalent to a brute force search of the key space. A key's entropy is not "diluted" by the length of a message. If you have a 128 bit key and a 128 megabyte message, there is no naive relationship there such that one bit of the key corresponds to a megabyte of the message. (So that, for instance, we can attack individual megabytes to obtain specific bits of the key.) Each small block of the message (say 8 or 16 characters wide or whatever) is encrypted with all bits of the key. To search the key space, the attacker requires only a example of a known plaintext/ciphertext pair: i.e. one small block. Additional known plain/cipher pairs do not help; trying them also only slows down the search. Keys which are proportional to the message size (one time pads) are not usually practical. For example, when two entities wish to continously communicate, they continously must exchange new bits of key material also. The important thing is that a key that is understood by the users of crypto software as having a cetain size actually is generated using that much entropy. If the user is assured that a program uses AES-128, but some silly PRNG is used that generates a key using 40 bits of entropy, that user has been terribly deceived. > In fact, you wrote earlier "The entire > output of a AES-128 stream (assuming a good key), will contain > 2**128 bits of entropy." This might be unimaginable fo ryou, but the above is likely a simple typo. A 128 key has a 2**128 search space; he wrote the search space size in place of the entropy size. > I mean AES would then be a > very wonderful magic device of creation of true entropy. (I haven't > yet seen any literature that contains claims in that direction.) If you consider this newsgroup to be "literature", then just keep reading.