Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.programming > #5811
| From | Kaz Kylheku <kaz@kylheku.com> |
|---|---|
| Newsgroups | comp.programming |
| Subject | Re: Researches in quantum computing seem to progress only extremely slowly |
| Date | 2015-09-04 20:33 +0000 |
| Organization | Aioe.org NNTP Server |
| Message-ID | <20150904132412.636@kylheku.com> (permalink) |
| References | (9 earlier) <ms9mod$hei$1@news.albasani.net> <fjqgua5aqj4v41bgr73ou57kftm5scnp7v@4ax.com> <msclg4$1uo$1@news.albasani.net> <9unjuap4cjrt83f7pc6sqh3kf4ut3niv2k@4ax.com> <mscsmk$f59$1@news.albasani.net> |
On 2015-09-04, Mok-Kong Shen <mok-kong.shen@t-online.de> wrote:
> Am 04.09.2015 um 20:42 schrieb Robert Wessel:
>> On Fri, 4 Sep 2015 19:47:57 +0200, Mok-Kong Shen
>> <mok-kong.shen@t-online.de> 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? In fact, you wrote earlier "The entire
>>> output of a AES-128 stream (assuming a good key), will contain
>>> 2**128 bits of entropy." However this means that one feeds AES
>>> with 128 bits of "true" entropy and out comes from it 2**128 bits
>>> of "true" entropy. Could that be true? 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.)
>>
>>
>>
>> Sorry, I added a "2**" to that inappropriately. "The entire output of
>> a AES-128 stream (assuming a good key), will contain _128_ bits of
>> entropy." Probably lost it editing the rest of that paragraph ("that
>> means the "key" stream will only be one of 2**128 possible streams,").
>>
>> "Very secure" is an interesting term. In the case of OTP, yes, you
>> need 1.0 bits of "real" entropy per key bit. And that's certainly
>> "very secure".
>>
>> OTOH, AES-128 is such that it appears* that you cannot recover the
>> key, or other parts of a message, if you know some of the plaintext,
>> with less than 2**128 work, and since that's an implausible amount of
>> work, that also seems "very secure", despite the entire keystream
>> having been seeded with only 128 bits of entropy.
>>
>> But not any generated sequence seeded with 128 bits of entropy is
>> secure. A 128 bit LFSR seeded with 128 bit of entropy is decidedly
>> *not* secure, since it's actually fairly easy** to run in reverse to
>> generate what the internal state is.
>>
>> Given 16 bytes of plaintext, I *know* an algorithm to recover the
>> key*** and the remainder of a message that's been encrypted with a 128
>> bit key (any cipher), it just won't finish in a useful amount of time.
>> What's special about AES (and other good ciphers), is that they appear
>> to *require* that amount of work, and don't allow any shortcuts (as
>> does, for example, an LFSR).
>>
>>
>> *The lack of an actual proof of security is disheartening, of course.
>>
>> **FSVO "easy", but there are plenty of easy to find descriptions of
>> the process if you're interested.
>>
>> ***Actually simple brute force will generate on average about two
>> possible keys if you only know 128 bits of plaintext (with 128 bit
>> keys). So in practice you'd want a few extra bits of plaintext.
>> Almost always all of the "wrong" keys will decrypt to gibberish (which
>> is just another way of saying we have a few extra bits of plaintext).
>
> I suppose that, according to what you wrote in the last posts about
> "apparent entropy", we could in future drop any issues involving it,
> since we are concerned here with security or more exactly secure
> encryption. That is, entropy will henceforth mean "true" entropy.
>
> Now, assuming we can agree that AES-128 can't generate any
> "additional" entropy, the situation is: If the output CTR-mode bit
> sequence is of length n, the estimated entropy of each bit is <= 128/n,
> from which it follows that for sufficiently large n the entropy per
> bit would be neligible.
The fact remains that no matter how large is the message (how large n),
the large message is still perturbed by the encryption in (hopefully) one
of 2**128 possible ways, just like a smaller one.
Your thinking is analogous to the suspicion that we can break into
a larger building more easily than into a small one, because the same
kind of lock is used (the same number of tumblers) which are diluted
over a larger building.
The security of the key resets in the absolute number of combinations, not its
relative size to the message.
A larger message just means that there is more confidential information
*at risk* with regard to a given key.
But that is not related to the cryptographic strength of the key.
This is why, for instance, secure communication mechanisms over the network
negotiate new session keys for new connections, rather than reusing the
same key. It's not because of entropy but because it's easy to generate
new keys: why put all the eggs into one basket?
Another reason is time. If you keep using the same key for a continuous
communication stream (an indefinitely long message), you're increasing the
likelihood that the key will be cracked and that the entire communication, all
the way back to the beginning, will be revealed to the attacker in one
instant. You have to assume that the attacker is gathering all your
communication and retaining it, and that the attacker has, somehow, at least
one known plaintext/ciphertext pair with which to do a brute force search (and
possibly has methods of attacking the cipher better than a brute force search).
Assume that everything you encrypt will be cracked eventually. You have to then
choose the system accordingly, so that by the *time* something is cracked, it
is of no value. If you use old keys, they have less "time remaining", so
to speak.
Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-01 13:09 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Kaz Kylheku <kaz@kylheku.com> - 2015-09-01 14:23 +0000
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-01 20:00 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Kaz Kylheku <kaz@kylheku.com> - 2015-09-01 18:43 +0000
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-02 10:48 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Kaz Kylheku <kaz@kylheku.com> - 2015-09-02 13:00 +0000
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-02 22:50 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Kaz Kylheku <kaz@kylheku.com> - 2015-09-02 21:31 +0000
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-02 23:46 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Kaz Kylheku <kaz@kylheku.com> - 2015-09-02 21:58 +0000
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 00:13 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Kaz Kylheku <kaz@kylheku.com> - 2015-09-03 00:32 +0000
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 02:47 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Robert Wessel <robertwessel2@yahoo.com> - 2015-09-02 16:52 -0500
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 00:03 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Robert Wessel <robertwessel2@yahoo.com> - 2015-09-02 17:18 -0500
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 00:28 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Robert Wessel <robertwessel2@yahoo.com> - 2015-09-02 17:52 -0500
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-03 01:04 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Robert Wessel <robertwessel2@yahoo.com> - 2015-09-02 18:29 -0500
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 01:04 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Robert Wessel <robertwessel2@yahoo.com> - 2015-09-02 18:25 -0500
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 01:33 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Robert Wessel <robertwessel2@yahoo.com> - 2015-09-02 18:53 -0500
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 02:16 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 02:18 +0200
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-03 02:33 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 02:42 +0200
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-03 02:55 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 03:03 +0200
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-03 03:14 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 03:17 +0200
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-03 03:30 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 03:36 +0200
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-03 04:13 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 04:19 +0200
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-03 04:32 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Robert Wessel <robertwessel2@yahoo.com> - 2015-09-02 22:51 -0500
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 16:51 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Robert Wessel <robertwessel2@yahoo.com> - 2015-09-03 10:49 -0500
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-04 19:47 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Robert Wessel <robertwessel2@yahoo.com> - 2015-09-04 13:42 -0500
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-04 21:50 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Kaz Kylheku <kaz@kylheku.com> - 2015-09-04 20:33 +0000
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-04 23:45 +0200
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-05 01:24 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Robert Wessel <robertwessel2@yahoo.com> - 2015-09-07 00:50 -0500
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-07 14:14 +0200
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-07 15:57 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Robert Wessel <robertwessel2@yahoo.com> - 2015-09-07 12:19 -0500
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-08 23:47 +0200
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-09 02:28 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Kaz Kylheku <kaz@kylheku.com> - 2015-09-04 20:23 +0000
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-05 00:55 +0200
Re: Researches in quantum computing seem to progress only extremely slowly "Chris M. Thomasson" <nospam@nospam.nospam> - 2015-09-04 17:11 -0700
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-05 02:31 +0200
Re: Researches in quantum computing seem to progress only extremely slowly "Chris M. Thomasson" <nospam@nospam.nospam> - 2015-09-04 20:15 -0700
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-03 00:35 +0200
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-03 00:42 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 00:46 +0200
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-03 00:54 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 01:11 +0200
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-03 01:21 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 01:28 +0200
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-03 02:01 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 02:22 +0200
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-03 02:51 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 02:57 +0200
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-03 03:08 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 03:31 +0200
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-03 03:45 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 03:54 +0200
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-03 04:18 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 04:24 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Johannes Bauer <dfnsonfsduifb@gmx.de> - 2015-09-03 07:23 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Robert Wessel <robertwessel2@yahoo.com> - 2015-09-02 16:14 -0500
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-02 23:23 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Kaz Kylheku <kaz@kylheku.com> - 2015-09-02 21:33 +0000
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-02 23:54 +0200
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-02 23:22 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-02 23:32 +0200
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-03 00:22 +0200
Re: Researches in quantum computing seem to progress only extremely slowly "Chris M. Thomasson" <nospam@nospam.nospam> - 2015-09-01 13:23 -0700
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-02 11:04 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Robert Wessel <robertwessel2@yahoo.com> - 2015-09-02 02:22 -0500
csiph-web