Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.programming > #5683 > unrolled thread
| Started by | Mok-Kong Shen <mok-kong.shen@t-online.de> |
|---|---|
| First post | 2015-09-01 13:09 +0200 |
| Last post | 2015-09-02 02:22 -0500 |
| Articles | 20 on this page of 85 — 6 participants |
Back to article view | Back to comp.programming
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
Page 3 of 5 — ← Prev page 1 2 [3] 4 5 Next page →
| From | Mok-Kong Shen <mok-kong.shen@t-online.de> |
|---|---|
| Date | 2015-09-04 19:47 +0200 |
| Message-ID | <msclg4$1uo$1@news.albasani.net> |
| In reply to | #5792 |
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.) M. K. Shen
[toc] | [prev] | [next] | [standalone]
| From | Robert Wessel <robertwessel2@yahoo.com> |
|---|---|
| Date | 2015-09-04 13:42 -0500 |
| Message-ID | <9unjuap4cjrt83f7pc6sqh3kf4ut3niv2k@4ax.com> |
| In reply to | #5803 |
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).
[toc] | [prev] | [next] | [standalone]
| From | Mok-Kong Shen <mok-kong.shen@t-online.de> |
|---|---|
| Date | 2015-09-04 21:50 +0200 |
| Message-ID | <mscsmk$f59$1@news.albasani.net> |
| In reply to | #5806 |
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 question is how the thus generated bit
sequence could nontheless be secure when considered in terms of entropy
(i.e. relative to "perfect security", which according to Shannon
requires 1 bit of entropy per bit of keystream).
M. K. Shen
[toc] | [prev] | [next] | [standalone]
| From | Kaz Kylheku <kaz@kylheku.com> |
|---|---|
| Date | 2015-09-04 20:33 +0000 |
| Message-ID | <20150904132412.636@kylheku.com> |
| In reply to | #5808 |
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.
[toc] | [prev] | [next] | [standalone]
| From | Mok-Kong Shen <mok-kong.shen@t-online.de> |
|---|---|
| Date | 2015-09-04 23:45 +0200 |
| Message-ID | <msd3cq$qp8$1@news.albasani.net> |
| In reply to | #5811 |
Am 04.09.2015 um 22:33 schrieb Kaz Kylheku:
> 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.
I don't yet see how your arguments above really refute my paradox.
Allow me thus to reformulate my issue as follows:
If I use, say, dice throws to obtain a sequence of 128 bits, then,
assuming the dice are perfect, each bit of the sequence has 1.0 of
entropy, right? I use that as key of AES-128 in CTR mode to generate
10000 bits. How much is the estimated entropy of each bit? I would
say that's anyway not larger than 128/10000. Am I right? If not, why?
If yes, how could one use bits of such low entropy value as keystream
to do good stream encryption (in comparison to Shannon's perfect
security case, which requires an entropy of 1.0 per bit)?
M. K. Shen
[toc] | [prev] | [next] | [standalone]
| From | bartekltg <bartek@gmail.com> |
|---|---|
| Date | 2015-09-05 01:24 +0200 |
| Message-ID | <msd97n$8dd$1@speranza.aioe.org> |
| In reply to | #5812 |
On 04.09.2015 23:45, Mok-Kong Shen wrote: > > I don't yet see how your arguments above really refute my paradox. > Allow me thus to reformulate my issue as follows: > > If I use, say, dice throws to obtain a sequence of 128 bits, then, > assuming the dice are perfect, each bit of the sequence has 1.0 of > entropy, right? I use that as key of AES-128 in CTR mode to generate > 10000 bits. How much is the estimated entropy of each bit? I would > say that's anyway not larger than 128/10000. Am I right? If not, why? > If yes, how could one use bits of such low entropy value as keystream > to do good stream encryption (in comparison to Shannon's perfect > security case, which requires an entropy of 1.0 per bit)? I have a coin. I also have a long sequence of bits. "In Search of Lost Time", in French, encoded in utf8, then Harry Potter (all books, English, ASCII) and gcc source code (gibberish, gzip compressed). This sequence is known, I put it on webpage. While I'm waiting for lawsouit, I can toss a coin. If the coin lands on head, I will post the sequence on usenet. If it land on tail, I will post (NOT sequence), binary complement of the sequence. Every 1 as 0 and every 0 as 1. You are waiting for this sequence to see, if bit #546737536 of posted sequence is 1 or 0 to decided if you want a cake or an icecream. How much entropy is in bit #546737536? Is there any difference betwen bit #546737536 and tossing a coin? Tossing a coin has 1 bit of entropy. If you know the answer, second question. You decided, before the sequence was posted, that 546737536 a is ugly number and decided to look at bit #9999999 to decide whether or not buy a soda. How much entropy is in this bit? Less than a coin? And now, you remember that you still have to eat a dessert, so you look at bit #546737536. Is there more entropy? Or these two bits are _corelated_ and if you know #9999999, you known #546737536 without looking. There never be drinking a soda and eating a cake;-) bartekltg
[toc] | [prev] | [next] | [standalone]
| From | Robert Wessel <robertwessel2@yahoo.com> |
|---|---|
| Date | 2015-09-07 00:50 -0500 |
| Message-ID | <279qua9otkos9f14b3en1q58536hk6n7hb@4ax.com> |
| In reply to | #5808 |
On Fri, 4 Sep 2015 21:50:52 +0200, 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 question is how the thus generated bit
>sequence could nontheless be secure when considered in terms of entropy
>(i.e. relative to "perfect security", which according to Shannon
>requires 1 bit of entropy per bit of keystream).
Why do you think that good security requires anything close to 1.0
bits of entropy per bit of keystream? *Perfect* security does require
1.0 bits, but that gives no hint at all to what amount of entropy
pre-keystream-bit would be necessary for "good enough" security. And
as it turns out, we're pretty sure there's no actual minimum, at least
on a per bit basis.
[toc] | [prev] | [next] | [standalone]
| From | Mok-Kong Shen <mok-kong.shen@t-online.de> |
|---|---|
| Date | 2015-09-07 14:14 +0200 |
| Message-ID | <msjv2h$u33$1@news.albasani.net> |
| In reply to | #5825 |
Am 07.09.2015 um 07:50 schrieb Robert Wessel:
> On Fri, 4 Sep 2015 21:50:52 +0200, 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 question is how the thus generated bit
>> sequence could nontheless be secure when considered in terms of entropy
>> (i.e. relative to "perfect security", which according to Shannon
>> requires 1 bit of entropy per bit of keystream).
>
>
> Why do you think that good security requires anything close to 1.0
> bits of entropy per bit of keystream? *Perfect* security does require
> 1.0 bits, but that gives no hint at all to what amount of entropy
> pre-keystream-bit would be necessary for "good enough" security. And
> as it turns out, we're pretty sure there's no actual minimum, at least
> on a per bit basis.
Oh, this is certainly a so-called common sense reasoning of mine.
If for perfect security one needs 1 bit of entropy, then one could
IMHO think of for some not too bad security a requirement of r bit of
entropy, where r might be, say, 0.9, 0.5, but one would not think
of values like 0.001 in this connection. For otherwise entropy would
have a very very strange unit of measurement for it to be a suitable
concept in practice at all. (As an an analogy, even one knows that
diehard doesn't give a measure of true entopy, diehard would totally
lose its value as a measure of (pseudo-)randomness, if a score of 0.9
from it doesn't mean at least something not too bad, though not the
best, relative to 1.0.)
M. K. Shen
[toc] | [prev] | [next] | [standalone]
| From | bartekltg <bartek@gmail.com> |
|---|---|
| Date | 2015-09-07 15:57 +0200 |
| Message-ID | <msk54j$ak4$1@speranza.aioe.org> |
| In reply to | #5826 |
On 07.09.2015 14:14, Mok-Kong Shen wrote:
> Am 07.09.2015 um 07:50 schrieb Robert Wessel:
>> On Fri, 4 Sep 2015 21:50:52 +0200, 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 question is how the thus generated bit
>>> sequence could nontheless be secure when considered in terms of entropy
>>> (i.e. relative to "perfect security", which according to Shannon
>>> requires 1 bit of entropy per bit of keystream).
>>
>>
>> Why do you think that good security requires anything close to 1.0
>> bits of entropy per bit of keystream? *Perfect* security does require
>> 1.0 bits, but that gives no hint at all to what amount of entropy
>> pre-keystream-bit would be necessary for "good enough" security. And
>> as it turns out, we're pretty sure there's no actual minimum, at least
>> on a per bit basis.
Be carefully with '1.0 bits of entropy per bit'.
Someone may understand that this is equivalent to "every bit
of keystream has 1.0 bit of entropy".
Like results of this function
long long unsigned int not_so_much_entropy()
{
unsigned long long int r = 0; //or =73495634398ll
if (rand()%2) r=~r;
return r;
}
;-)
> Oh, this is certainly a so-called common sense reasoning of mine.
> If for perfect security one needs 1 bit of entropy, then one could
> IMHO think of for some not too bad security a requirement of r bit of
> entropy, where r might be, say, 0.9, 0.5, but one would not think
> of values like 0.001 in this connection. For otherwise entropy would
> have a very very strange unit of measurement for it to be a suitable
> concept in practice at all. (As an an analogy, even one knows that
> diehard doesn't give a measure of true entopy, diehard would totally
> lose its value as a measure of (pseudo-)randomness, if a score of 0.9
> from it doesn't mean at least something not too bad, though not the
> best, relative to 1.0.)
Does diehard return any results named 'entropy'?
How do you define entropy for a sequence?
Entropy is about a set of possible messages (or just ouptputs
from a function). A probability distribution of messages and
how probable message is (if I get a rare message, it contain
more information).
We can take a long sequence, divide it into k-bit segments
and compute entropy as the segments were independent messages,
this approach is useful for example in compression (it is very
close to Huffman coding), but this have nothing to do with entropy
in this sequence. It just measure if the segments are evenly
distributed.
It looks like you know that, but it is no harm to repeat:
Of course, this is all about 'conditional probability'
and knowledge. If you give me just a long sequence of
pseudorandom numbers, for me it can even have more entropy
than you have used in seed. But I _may_ know more.
bartekltg
[toc] | [prev] | [next] | [standalone]
| From | Robert Wessel <robertwessel2@yahoo.com> |
|---|---|
| Date | 2015-09-07 12:19 -0500 |
| Message-ID | <tnhruadf8shvuoptuecgapqoob0347s0k8@4ax.com> |
| In reply to | #5826 |
On Mon, 7 Sep 2015 14:14:08 +0200, Mok-Kong Shen
<mok-kong.shen@t-online.de> wrote:
>Am 07.09.2015 um 07:50 schrieb Robert Wessel:
>> On Fri, 4 Sep 2015 21:50:52 +0200, 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 question is how the thus generated bit
>>> sequence could nontheless be secure when considered in terms of entropy
>>> (i.e. relative to "perfect security", which according to Shannon
>>> requires 1 bit of entropy per bit of keystream).
>>
>>
>> Why do you think that good security requires anything close to 1.0
>> bits of entropy per bit of keystream? *Perfect* security does require
>> 1.0 bits, but that gives no hint at all to what amount of entropy
>> pre-keystream-bit would be necessary for "good enough" security. And
>> as it turns out, we're pretty sure there's no actual minimum, at least
>> on a per bit basis.
>
>Oh, this is certainly a so-called common sense reasoning of mine.
>If for perfect security one needs 1 bit of entropy, then one could
>IMHO think of for some not too bad security a requirement of r bit of
>entropy, where r might be, say, 0.9, 0.5, but one would not think
>of values like 0.001 in this connection. For otherwise entropy would
>have a very very strange unit of measurement for it to be a suitable
>concept in practice at all. (As an an analogy, even one knows that
>diehard doesn't give a measure of true entopy, diehard would totally
>lose its value as a measure of (pseudo-)randomness, if a score of 0.9
>from it doesn't mean at least something not too bad, though not the
>best, relative to 1.0.)
Whether or not such an idea appeals to you intuitively, it's wrong.
[toc] | [prev] | [next] | [standalone]
| From | Mok-Kong Shen <mok-kong.shen@t-online.de> |
|---|---|
| Date | 2015-09-08 23:47 +0200 |
| Message-ID | <msnl1s$uuh$1@news.albasani.net> |
| In reply to | #5828 |
Am 07.09.2015 um 19:19 schrieb Robert Wessel:
> On Mon, 7 Sep 2015 14:14:08 +0200, Mok-Kong Shen
> <mok-kong.shen@t-online.de> wrote:
>
>> Am 07.09.2015 um 07:50 schrieb Robert Wessel:
>>> On Fri, 4 Sep 2015 21:50:52 +0200, 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 question is how the thus generated bit
>>>> sequence could nontheless be secure when considered in terms of entropy
>>>> (i.e. relative to "perfect security", which according to Shannon
>>>> requires 1 bit of entropy per bit of keystream).
>>>
>>>
>>> Why do you think that good security requires anything close to 1.0
>>> bits of entropy per bit of keystream? *Perfect* security does require
>>> 1.0 bits, but that gives no hint at all to what amount of entropy
>>> pre-keystream-bit would be necessary for "good enough" security. And
>>> as it turns out, we're pretty sure there's no actual minimum, at least
>>> on a per bit basis.
>>
>> Oh, this is certainly a so-called common sense reasoning of mine.
>> If for perfect security one needs 1 bit of entropy, then one could
>> IMHO think of for some not too bad security a requirement of r bit of
>> entropy, where r might be, say, 0.9, 0.5, but one would not think
>> of values like 0.001 in this connection. For otherwise entropy would
>> have a very very strange unit of measurement for it to be a suitable
>> concept in practice at all. (As an an analogy, even one knows that
>> diehard doesn't give a measure of true entopy, diehard would totally
>> lose its value as a measure of (pseudo-)randomness, if a score of 0.9
>>from it doesn't mean at least something not too bad, though not the
>> best, relative to 1.0.)
>
>
> Whether or not such an idea appeals to you intuitively, it's wrong.
>
Does diehard's scores 1.0, 0.9 etc. have sense for "apparent entropy"?
If yes, then 1.0, 0.9 etc. must have certain corresponding sense for
"true entropy". What would you then ascribe to the meaning of 0.9?
It isn't full entropy, but what (in relation to e.g. 0.01)? Isn't
it much greater than 0.01?
M. K. Shen
[toc] | [prev] | [next] | [standalone]
| From | bartekltg <bartek@gmail.com> |
|---|---|
| Date | 2015-09-09 02:28 +0200 |
| Message-ID | <msnufh$ts8$1@speranza.aioe.org> |
| In reply to | #5831 |
On 08.09.2015 23:47, Mok-Kong Shen wrote:
>>
>>
> Does diehard's scores 1.0, 0.9 etc. have sense for "apparent entropy"?
What did you name "apparent entropy" is weaker than diehard tests.
It would only check uniformity of the distribution, but
nothing about order in the sequence.
What is aparent entropy of all 32bit numbers in ascending order? ;-)
Diehard does not measure 'apparent entropy' nor entropy.
> If yes, then 1.0, 0.9 etc. must have certain corresponding sense for
> "true entropy".
No.
Please read the definition of entropy.
> What would you then ascribe to the meaning of 0.9?
> It isn't full entropy, but what (in relation to e.g. 0.01)? Isn't
> it much greater than 0.01?
I looked one more time into diehard and deiharder.
All test are done in a similar way. We compute
a some test, witch give us a number. Mean value of tries needed
to get number greater than 1 for example. Then we know
a distribution of such results, if the input is
a series of true random numbers.
Then as a displayed result, we get place, where on the
distribution (on the cumulative distribution function, to be precise)
the number is. If the most results is very close to 0.0 or/and 1.0,
then our data have _different_ distribution than random numbers.
From diehard:
"Most of the tests in DIEHARD return a p-value, which
should be uniform on [0,1) if the input file contains truly
independent random bits. Those p-values are obtained by
p=1-F(X), where F is the assumed distribution of the sample
random variable X---often normal. But that assumed F is often just
an asymptotic approximation, for which the fit will be worst
in the tails. Thus you should not be surprised with occasion-
al p-values near 0 or 1, such as .0012 or .9983. When a bit
stream really FAILS BIG, you will get p`s of 0 or 1 to six or more
places. By all means, do not, as a Statistician might, think that a p <
.025 or p> .975 means that the RNG
has "failed the test at the .05 level". Such p`s happen
among the hundreds that DIEHARD produces, even with good RNGs.
So keep in mind that "p happens"
"
Dieharder also use this king of output:
rng_name | filename |rands/second|
mt19937| bits.01| 1.05e+08 |
#=============================================================================#
test_name |ntup| tsamples |psamples| p-value |Assessment
#=============================================================================#
diehard_birthdays| 0| 100| 100|0.53531311| PASSED
diehard_operm5| 0| 1000000| 100|0.37500924| PASSED
diehard_rank_32x32| 0| 40000| 100|0.44750256| PASSED
diehard_rank_6x8| 0| 100000| 100|0.23010032| PASSED
diehard_bitstream| 0| 2097152| 100|0.91865978| PASSED
diehard_opso| 0| 2097152| 100|0.25262861| PASSED
diehard_oqso| 0| 2097152| 100|0.37117112| PASSED
diehard_dna| 0| 2097152| 100|0.27866865| PASSED
...
Maybe you are speaking about other version of diehard, but if you
do not, then results 1.0 are bad.
Bonus from dieharder source
"I know that this hypothesis is technically false for all software
generators as they are periodic and do not have the correct entropy
content for this statement to ever be true."
bartekltg
[toc] | [prev] | [next] | [standalone]
| From | Kaz Kylheku <kaz@kylheku.com> |
|---|---|
| Date | 2015-09-04 20:23 +0000 |
| Message-ID | <20150904130751.461@kylheku.com> |
| In reply to | #5803 |
On 2015-09-04, 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? 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.
[toc] | [prev] | [next] | [standalone]
| From | bartekltg <bartek@gmail.com> |
|---|---|
| Date | 2015-09-05 00:55 +0200 |
| Message-ID | <msd7gj$5hh$1@speranza.aioe.org> |
| In reply to | #5803 |
On 04.09.2015 19:47, 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?
I have build a cryptographic system based on 65536bit RSA (because
it's the only way to be sure). I generate two random 32768bit primes.
How? I put a 32768 bit pseudorandom sequence in the 'nextprime(x)'
function, it return smallest prime greater than x.
How I get 32768 bit pseudorandom sequences? I run simple PRNG
and generate 1024 unsigned 32bit integers.
I known randomnet od this numbers is very important so I used
RANLUX, PRNG with 'the paper', the only, I think, generator
with a proof or randomness. Used by hardcore mathematicians and
physicist to run simulation in conformal field theory.
In one word, serious stuff;-)
Diehard of course is quite sure sequence generated by this
PRNG is a random sequence.
But I also insert s seed every time the programs starts,
that means every time I generate random numbers and primes.
As a seed I use a number. From 1 to 100.
;-)
.
.
.
.
.
.
I tested, my sequence is one of the best in the word.
As a sequence of numbers.
But sequences given to the second part of the program ('nextprime')
have less than 7 bits of entropy.
There is only 100 possible sequences.
There is only 100 possible pair of random numbers.
It isn't much more secure than plain text, even though
I have used great PRNG with maxed score in diehard.
> 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.)
No. Conditional entropy H(sequence|AES(sequence)) = 0
((H(AES(sequence)|sequence))=0 too.)
If one read one sequense, second one have no entropy for you.
You can see how much entropy is in a k bit sqeuence generated
by looking at first k bits of output from a mixing
function applied on m-bit random variable.
The mixing function is Robert Jenkins' 32 bit integer hash modulo
2^k.
Entropy is computed exactly, by iterating over all possible inputs.
http://pastebin.com/Cd4Tfx0D
results. k goes vertical.
The theoretical maximum entropy is min(k,m) bits. It looks like,
for bigger k and m, this function looses ~0.8 bit of entropy
for k=m and ~0,4-0.5 for |k-m|=1.
http://pastebin.com/fU7fsGwD
code (c++)
bartekltg
[toc] | [prev] | [next] | [standalone]
| From | "Chris M. Thomasson" <nospam@nospam.nospam> |
|---|---|
| Date | 2015-09-04 17:11 -0700 |
| Message-ID | <msdc0k$dpr$1@speranza.aioe.org> |
| In reply to | #5813 |
> "bartekltg" wrote in message news:msd7gj$5hh$1@speranza.aioe.org... [...] > How I get 32768 bit pseudorandom sequences? You spend a long time on: https://www.random.org ? ;^)
[toc] | [prev] | [next] | [standalone]
| From | bartekltg <bartek@gmail.com> |
|---|---|
| Date | 2015-09-05 02:31 +0200 |
| Message-ID | <msdd5n$ftb$1@speranza.aioe.org> |
| In reply to | #5815 |
On 05.09.2015 02:11, Chris M. Thomasson wrote: >> "bartekltg" wrote in message news:msd7gj$5hh$1@speranza.aioe.org... > > [...] >> How I get 32768 bit pseudorandom sequences? > > You spend a long time on: > > https://www.random.org They claim this are random numbers, not pseudorandom. If it is on the Internet it must be true. > ? > ;^) ;-) Not long ago I have used quite big computer do to some computations. 20% of computing time was random number generation. It ran two weeks. I have no idea how many random bits it generated, but I think computer mice used to click on the page would cost more than this computer;-) bartekltg
[toc] | [prev] | [next] | [standalone]
| From | "Chris M. Thomasson" <nospam@nospam.nospam> |
|---|---|
| Date | 2015-09-04 20:15 -0700 |
| Message-ID | <msdmqp$vio$1@speranza.aioe.org> |
| In reply to | #5816 |
> "bartekltg" wrote in message news:msdd5n$ftb$1@speranza.aioe.org... > > On 05.09.2015 02:11, Chris M. Thomasson wrote: > >> "bartekltg" wrote in message news:msd7gj$5hh$1@speranza.aioe.org... > > > > [...] > >> How I get 32768 bit pseudorandom sequences? > > > > You spend a long time on: > > > > https://www.random.org > They claim this are random numbers, not pseudorandom. > If it is on the Internet it must be true. I am hoping they can shuffle the deck better than the average bear. There has to be pseudorandom qualities, however if they are gaining entropy from dynamical chaotic real-world sources, well, it just might be thought of pseudo-random with a little spice? ;^D
[toc] | [prev] | [next] | [standalone]
| From | bartekltg <bartek@gmail.com> |
|---|---|
| Date | 2015-09-03 00:35 +0200 |
| Message-ID | <ms7tk8$is0$1@speranza.aioe.org> |
| In reply to | #5739 |
On 03.09.2015 00:03, Mok-Kong Shen wrote: > Am 02.09.2015 um 23:52 schrieb Robert Wessel: >> On Wed, 2 Sep 2015 22:50:52 +0200, Mok-Kong Shen >> <mok-kong.shen@t-online.de> wrote: >> >>> Am 02.09.2015 um 15:00 schrieb Kaz Kylheku: >>>> On 2015-09-02, Mok-Kong Shen <mok-kong.shen@t-online.de> wrote: >>>>> In my code PROVABLEPRIME >>>>> (http://s13.zetaboards.com/Crypto/topic/7234475/1/) there is no seed >>>>> to be input by the user at all. When the Python session starts, the >>>>> system employs the current time to seed its built-in PRNG. So each >>>>> time one uses the code to e.g. generate RSA keys, one gets a different >>>>> pair by chance. Certainly one could question the security of that from >>>>> an "exact" standpoint (I mean in the sense of proofs of pure math), >>>> >>>> The "exact standpoint" here is quite obvious and it is that a sample >>>> of the >>>> current time (even if it includes micro or nanoseconds from a high >>>> resolution timer, >>>> and not only the "seconds sine epoch" or whatever) simply has too >>>> few bits of >>>> entropy to generate good RSA keys. >>> >>> I must admit that I yet have doubt on such application of the entropy >>> argument (i.e. without regard to how an amount of entropy is actually >>> being employed in the processing) due to a paradox that I put up >>> and described in a recent another thread: AES-128 in counter mode has >>> an input of max 128 bits of entropy but its ouput is commonly used to >>> e.g. xor n plaintext bits with n >> 128. The average entropy that is >>> contained in one ciphertext bit thus can't be greater than 128/n, >>> which is negligible for even moderately large n. Does that imply that >>> AES in CTR mode is totally broken? >> >> >> No, it simply means that you don't need to do more than about 2**128 >> work to break it with a known plaintext attack of sufficient size >> (where "sufficient" may be as little as 16 bytes). But that's not >> broken, since that's what we were assuming anyway. Sure, it's not a >> OTP, but it was never meant to be. > > I don't yet understand. One expands a sequence of 128 bits somehow > to a sequence of n bits with n >> 128. If the input 128 bits have > a total "entropy" of 128, then it can certainly also be asked how > much entropy the output n bits have in total and hence the average > value of entropy of each output bit. OK, this will be far from formal math... Do you assume the text is known? If the entropy is only entropy of the coding sequence, you do. In the first 128 bits there is 128bit of enthropy. In the second 128 bits there is 128bit of enthropy. In the first 256 bits - 128 bits of enthropy. The entropy of whole sequence (X,Y) H(X,Y) = H(X) + H(Y|X) (=H(y) + H(X|Y)) is equal to entropy of the first part plus _conditional_ entropy od Y under the assumption X is known. And because you use the same sequence to code the second half, there is no new information. H(X|Y) = 0. bartekltg
[toc] | [prev] | [next] | [standalone]
| From | bartekltg <bartek@gmail.com> |
|---|---|
| Date | 2015-09-03 00:42 +0200 |
| Message-ID | <ms7u0f$jem$1@speranza.aioe.org> |
| In reply to | #5744 |
On 03.09.2015 00:35, bartekltg wrote: > On 03.09.2015 00:03, Mok-Kong Shen wrote: >> Am 02.09.2015 um 23:52 schrieb Robert Wessel: >>> On Wed, 2 Sep 2015 22:50:52 +0200, Mok-Kong Shen >>> <mok-kong.shen@t-online.de> wrote: >>> >>>> Am 02.09.2015 um 15:00 schrieb Kaz Kylheku: >>>>> On 2015-09-02, Mok-Kong Shen <mok-kong.shen@t-online.de> wrote: >>>>>> In my code PROVABLEPRIME >>>>>> (http://s13.zetaboards.com/Crypto/topic/7234475/1/) there is no seed >>>>>> to be input by the user at all. When the Python session starts, the >>>>>> system employs the current time to seed its built-in PRNG. So each >>>>>> time one uses the code to e.g. generate RSA keys, one gets a >>>>>> different >>>>>> pair by chance. Certainly one could question the security of that >>>>>> from >>>>>> an "exact" standpoint (I mean in the sense of proofs of pure math), >>>>> >>>>> The "exact standpoint" here is quite obvious and it is that a sample >>>>> of the >>>>> current time (even if it includes micro or nanoseconds from a high >>>>> resolution timer, >>>>> and not only the "seconds sine epoch" or whatever) simply has too >>>>> few bits of >>>>> entropy to generate good RSA keys. >>>> >>>> I must admit that I yet have doubt on such application of the entropy >>>> argument (i.e. without regard to how an amount of entropy is actually >>>> being employed in the processing) due to a paradox that I put up >>>> and described in a recent another thread: AES-128 in counter mode has >>>> an input of max 128 bits of entropy but its ouput is commonly used to >>>> e.g. xor n plaintext bits with n >> 128. The average entropy that is >>>> contained in one ciphertext bit thus can't be greater than 128/n, >>>> which is negligible for even moderately large n. Does that imply that >>>> AES in CTR mode is totally broken? >>> >>> >>> No, it simply means that you don't need to do more than about 2**128 >>> work to break it with a known plaintext attack of sufficient size >>> (where "sufficient" may be as little as 16 bytes). But that's not >>> broken, since that's what we were assuming anyway. Sure, it's not a >>> OTP, but it was never meant to be. >> >> I don't yet understand. One expands a sequence of 128 bits somehow >> to a sequence of n bits with n >> 128. If the input 128 bits have >> a total "entropy" of 128, then it can certainly also be asked how >> much entropy the output n bits have in total and hence the average >> value of entropy of each output bit. > > OK, this will be far from formal math... > > Do you assume the text is known? If the entropy is only entropy > of the coding sequence, you do. > In the first 128 bits there is 128bit of enthropy. > In the second 128 bits there is 128bit of enthropy. > In the first 256 bits - 128 bits of enthropy. > > The entropy of whole sequence (X,Y) > H(X,Y) = H(X) + H(Y|X) (=H(y) + H(X|Y)) > is equal to entropy of the first part plus > _conditional_ entropy od Y under the assumption X is known. > And because you use the same sequence to code the second half, > there is no new information. H(X|Y) = 0. I have one candy. I hide it in one of my hands and present both hand to you. Information, where is the candy is one bit. It is either i left or in right hand. Information about my candy-state is write as 01 (no candy in right hand, a candy in left hand) or 10. Do you think that i I open one of my hands, you get a 1/2 bit of information? And when I open the second one - net 1/2 bit of information? Bo, the whole bit is in my left hand in the same way it is in my right hand. When I open the first hand you will get whole bit of information, and when I open the second hand, you gen no new information, 0 bits. bartekltg
[toc] | [prev] | [next] | [standalone]
| From | Mok-Kong Shen <mok-kong.shen@t-online.de> |
|---|---|
| Date | 2015-09-03 00:46 +0200 |
| Message-ID | <ms7u7i$u75$1@news.albasani.net> |
| In reply to | #5744 |
Am 03.09.2015 um 00:35 schrieb bartekltg: > On 03.09.2015 00:03, Mok-Kong Shen wrote: >> Am 02.09.2015 um 23:52 schrieb Robert Wessel: >>> On Wed, 2 Sep 2015 22:50:52 +0200, Mok-Kong Shen >>> <mok-kong.shen@t-online.de> wrote: >>> >>>> Am 02.09.2015 um 15:00 schrieb Kaz Kylheku: >>>>> On 2015-09-02, Mok-Kong Shen <mok-kong.shen@t-online.de> wrote: >>>>>> In my code PROVABLEPRIME >>>>>> (http://s13.zetaboards.com/Crypto/topic/7234475/1/) there is no seed >>>>>> to be input by the user at all. When the Python session starts, the >>>>>> system employs the current time to seed its built-in PRNG. So each >>>>>> time one uses the code to e.g. generate RSA keys, one gets a >>>>>> different >>>>>> pair by chance. Certainly one could question the security of that >>>>>> from >>>>>> an "exact" standpoint (I mean in the sense of proofs of pure math), >>>>> >>>>> The "exact standpoint" here is quite obvious and it is that a sample >>>>> of the >>>>> current time (even if it includes micro or nanoseconds from a high >>>>> resolution timer, >>>>> and not only the "seconds sine epoch" or whatever) simply has too >>>>> few bits of >>>>> entropy to generate good RSA keys. >>>> >>>> I must admit that I yet have doubt on such application of the entropy >>>> argument (i.e. without regard to how an amount of entropy is actually >>>> being employed in the processing) due to a paradox that I put up >>>> and described in a recent another thread: AES-128 in counter mode has >>>> an input of max 128 bits of entropy but its ouput is commonly used to >>>> e.g. xor n plaintext bits with n >> 128. The average entropy that is >>>> contained in one ciphertext bit thus can't be greater than 128/n, >>>> which is negligible for even moderately large n. Does that imply that >>>> AES in CTR mode is totally broken? >>> >>> >>> No, it simply means that you don't need to do more than about 2**128 >>> work to break it with a known plaintext attack of sufficient size >>> (where "sufficient" may be as little as 16 bytes). But that's not >>> broken, since that's what we were assuming anyway. Sure, it's not a >>> OTP, but it was never meant to be. >> >> I don't yet understand. One expands a sequence of 128 bits somehow >> to a sequence of n bits with n >> 128. If the input 128 bits have >> a total "entropy" of 128, then it can certainly also be asked how >> much entropy the output n bits have in total and hence the average >> value of entropy of each output bit. > > OK, this will be far from formal math... > > Do you assume the text is known? If the entropy is only entropy > of the coding sequence, you do. > In the first 128 bits there is 128bit of enthropy. > In the second 128 bits there is 128bit of enthropy. > In the first 256 bits - 128 bits of enthropy. > > The entropy of whole sequence (X,Y) > H(X,Y) = H(X) + H(Y|X) (=H(y) + H(X|Y)) > is equal to entropy of the first part plus > _conditional_ entropy od Y under the assumption X is known. > And because you use the same sequence to code the second half, > there is no new information. H(X|Y) = 0. Sorry, I can't follow your contional entropy argument. You wrote "... assumption X is known". But one can simply consider that one has got n output bits from AES before doing anything else. What is "known" at that time? If none, what's the average entropy per bit? M. K. Shen
[toc] | [prev] | [next] | [standalone]
Page 3 of 5 — ← Prev page 1 2 [3] 4 5 Next page →
Back to top | Article view | comp.programming
csiph-web