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 2 of 5 — ← Prev page 1 [2] 3 4 5 Next page →
| From | Mok-Kong Shen <mok-kong.shen@t-online.de> |
|---|---|
| Date | 2015-09-03 01:04 +0200 |
| Message-ID | <ms7va6$vtj$1@news.albasani.net> |
| In reply to | #5747 |
Am 03.09.2015 um 00:52 schrieb Robert Wessel:
> On Thu, 3 Sep 2015 00:28:33 +0200, Mok-Kong Shen
> <mok-kong.shen@t-online.de> wrote:
>
>> Am 03.09.2015 um 00:18 schrieb Robert Wessel:
>>> On Thu, 3 Sep 2015 00:03:52 +0200, Mok-Kong Shen
>>> <mok-kong.shen@t-online.de> 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.
>>>
>>>
>>> If there's 128 bits of entropy going in, that's what's coming out.
>>> Spread over however many bits you output. IOW, if you encrypt
>>> something with AES-128 in whatever mode (ignoring any nonce or IV),
>>> there will be only 2**128 possible decryptions of the message, no
>>> matter how long it might be.
>>
>> But you are ignoring the "entropy" in your 2nd sentence. My paradox
>> is however centered on "entropy". Each input bit is assumed to have
>> 1 bit of entropy. After spreading, the average entropy can't be
>> larger than 128/n. What is wrong in that calculation logically?
>> That's what I like very much to know from you or Kylheku.
>
>
> I wouldn't use the word average, but there would be about 128/n bits
> of entropy per output bit.
>
> That's not really at question, or very interesting. If I take a
> gallon of milk, and divide it evenly between 1024 containers, I'll
> have an eighth of an ounce of milk in each container.
>
> I have perhaps missed some part of this discussion.
>
> If this has to do with CS vs. non-CS PRNGs, the difference is that
> non-CS PRNGs make it trivial(-ish) to extract the original data
> ("entropy") from the stream, or equivalently, allow the prediction of
> future outputs from existing ones without excessive work. For example
> you can seed and LFSR with some amount of entropy, but if you have
> some output from it, you can work it backwards to determine what that
> initial seed (or at least the initial state derived from that seed)
> was.
The paradox I had also posted previously elsewhere and is thus not
specifially constructed for the CSPRNG issue. If the paradox as such
can't be resolved, then I would say that employing entropy to treat
the security of crypto schemes seems to have some fundamental logical
problems in general.
M. K. Shen
[toc] | [prev] | [next] | [standalone]
| From | Robert Wessel <robertwessel2@yahoo.com> |
|---|---|
| Date | 2015-09-02 18:25 -0500 |
| Message-ID | <0a1fua58g3o3sbe715rv0ugvvkkdd06lvr@4ax.com> |
| In reply to | #5750 |
On Thu, 3 Sep 2015 01:04:43 +0200, Mok-Kong Shen
<mok-kong.shen@t-online.de> wrote:
>Am 03.09.2015 um 00:52 schrieb Robert Wessel:
>> On Thu, 3 Sep 2015 00:28:33 +0200, Mok-Kong Shen
>> <mok-kong.shen@t-online.de> wrote:
>>
>>> Am 03.09.2015 um 00:18 schrieb Robert Wessel:
>>>> On Thu, 3 Sep 2015 00:03:52 +0200, Mok-Kong Shen
>>>> <mok-kong.shen@t-online.de> 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.
>>>>
>>>>
>>>> If there's 128 bits of entropy going in, that's what's coming out.
>>>> Spread over however many bits you output. IOW, if you encrypt
>>>> something with AES-128 in whatever mode (ignoring any nonce or IV),
>>>> there will be only 2**128 possible decryptions of the message, no
>>>> matter how long it might be.
>>>
>>> But you are ignoring the "entropy" in your 2nd sentence. My paradox
>>> is however centered on "entropy". Each input bit is assumed to have
>>> 1 bit of entropy. After spreading, the average entropy can't be
>>> larger than 128/n. What is wrong in that calculation logically?
>>> That's what I like very much to know from you or Kylheku.
>>
>>
>> I wouldn't use the word average, but there would be about 128/n bits
>> of entropy per output bit.
>>
>> That's not really at question, or very interesting. If I take a
>> gallon of milk, and divide it evenly between 1024 containers, I'll
>> have an eighth of an ounce of milk in each container.
>>
>> I have perhaps missed some part of this discussion.
>>
>> If this has to do with CS vs. non-CS PRNGs, the difference is that
>> non-CS PRNGs make it trivial(-ish) to extract the original data
>> ("entropy") from the stream, or equivalently, allow the prediction of
>> future outputs from existing ones without excessive work. For example
>> you can seed and LFSR with some amount of entropy, but if you have
>> some output from it, you can work it backwards to determine what that
>> initial seed (or at least the initial state derived from that seed)
>> was.
>
>The paradox I had also posted previously elsewhere and is thus not
>specifially constructed for the CSPRNG issue. If the paradox as such
>can't be resolved, then I would say that employing entropy to treat
>the security of crypto schemes seems to have some fundamental logical
>problems in general.
Well, your paradox posted previous elsewhere is not immediately
visible to me, so I can't really comment on it.
[toc] | [prev] | [next] | [standalone]
| From | Mok-Kong Shen <mok-kong.shen@t-online.de> |
|---|---|
| Date | 2015-09-03 01:33 +0200 |
| Message-ID | <ms80vk$2ls$1@news.albasani.net> |
| In reply to | #5753 |
Am 03.09.2015 um 01:25 schrieb Robert Wessel:
> On Thu, 3 Sep 2015 01:04:43 +0200, Mok-Kong Shen
> <mok-kong.shen@t-online.de> wrote:
>
>> Am 03.09.2015 um 00:52 schrieb Robert Wessel:
>>> On Thu, 3 Sep 2015 00:28:33 +0200, Mok-Kong Shen
>>> <mok-kong.shen@t-online.de> wrote:
>>>
>>>> Am 03.09.2015 um 00:18 schrieb Robert Wessel:
>>>>> On Thu, 3 Sep 2015 00:03:52 +0200, Mok-Kong Shen
>>>>> <mok-kong.shen@t-online.de> 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.
>>>>>
>>>>>
>>>>> If there's 128 bits of entropy going in, that's what's coming out.
>>>>> Spread over however many bits you output. IOW, if you encrypt
>>>>> something with AES-128 in whatever mode (ignoring any nonce or IV),
>>>>> there will be only 2**128 possible decryptions of the message, no
>>>>> matter how long it might be.
>>>>
>>>> But you are ignoring the "entropy" in your 2nd sentence. My paradox
>>>> is however centered on "entropy". Each input bit is assumed to have
>>>> 1 bit of entropy. After spreading, the average entropy can't be
>>>> larger than 128/n. What is wrong in that calculation logically?
>>>> That's what I like very much to know from you or Kylheku.
>>>
>>>
>>> I wouldn't use the word average, but there would be about 128/n bits
>>> of entropy per output bit.
>>>
>>> That's not really at question, or very interesting. If I take a
>>> gallon of milk, and divide it evenly between 1024 containers, I'll
>>> have an eighth of an ounce of milk in each container.
>>>
>>> I have perhaps missed some part of this discussion.
>>>
>>> If this has to do with CS vs. non-CS PRNGs, the difference is that
>>> non-CS PRNGs make it trivial(-ish) to extract the original data
>>> ("entropy") from the stream, or equivalently, allow the prediction of
>>> future outputs from existing ones without excessive work. For example
>>> you can seed and LFSR with some amount of entropy, but if you have
>>> some output from it, you can work it backwards to determine what that
>>> initial seed (or at least the initial state derived from that seed)
>>> was.
>>
>> The paradox I had also posted previously elsewhere and is thus not
>> specifially constructed for the CSPRNG issue. If the paradox as such
>> can't be resolved, then I would say that employing entropy to treat
>> the security of crypto schemes seems to have some fundamental logical
>> problems in general.
>
>
> Well, your paradox posted previous elsewhere is not immediately
> visible to me, so I can't really comment on it.
That's the same in content as I described in this thread. (I only
mentioned its history, in order to explain that it is not specifically
thought of for this thread.) So you don't have to look at what I posted
elsewhere and need only to treat what I posted in this thread.
M. K. Shen
[toc] | [prev] | [next] | [standalone]
| From | Robert Wessel <robertwessel2@yahoo.com> |
|---|---|
| Date | 2015-09-02 18:53 -0500 |
| Message-ID | <sq2fuahnogne19tirojcpghp4vb1nb9k1k@4ax.com> |
| In reply to | #5756 |
On Thu, 3 Sep 2015 01:33:13 +0200, Mok-Kong Shen
<mok-kong.shen@t-online.de> wrote:
>Am 03.09.2015 um 01:25 schrieb Robert Wessel:
>> On Thu, 3 Sep 2015 01:04:43 +0200, Mok-Kong Shen
>> <mok-kong.shen@t-online.de> wrote:
>>
>>> Am 03.09.2015 um 00:52 schrieb Robert Wessel:
>>>> On Thu, 3 Sep 2015 00:28:33 +0200, Mok-Kong Shen
>>>> <mok-kong.shen@t-online.de> wrote:
>>>>
>>>>> Am 03.09.2015 um 00:18 schrieb Robert Wessel:
>>>>>> On Thu, 3 Sep 2015 00:03:52 +0200, Mok-Kong Shen
>>>>>> <mok-kong.shen@t-online.de> 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.
>>>>>>
>>>>>>
>>>>>> If there's 128 bits of entropy going in, that's what's coming out.
>>>>>> Spread over however many bits you output. IOW, if you encrypt
>>>>>> something with AES-128 in whatever mode (ignoring any nonce or IV),
>>>>>> there will be only 2**128 possible decryptions of the message, no
>>>>>> matter how long it might be.
>>>>>
>>>>> But you are ignoring the "entropy" in your 2nd sentence. My paradox
>>>>> is however centered on "entropy". Each input bit is assumed to have
>>>>> 1 bit of entropy. After spreading, the average entropy can't be
>>>>> larger than 128/n. What is wrong in that calculation logically?
>>>>> That's what I like very much to know from you or Kylheku.
>>>>
>>>>
>>>> I wouldn't use the word average, but there would be about 128/n bits
>>>> of entropy per output bit.
>>>>
>>>> That's not really at question, or very interesting. If I take a
>>>> gallon of milk, and divide it evenly between 1024 containers, I'll
>>>> have an eighth of an ounce of milk in each container.
>>>>
>>>> I have perhaps missed some part of this discussion.
>>>>
>>>> If this has to do with CS vs. non-CS PRNGs, the difference is that
>>>> non-CS PRNGs make it trivial(-ish) to extract the original data
>>>> ("entropy") from the stream, or equivalently, allow the prediction of
>>>> future outputs from existing ones without excessive work. For example
>>>> you can seed and LFSR with some amount of entropy, but if you have
>>>> some output from it, you can work it backwards to determine what that
>>>> initial seed (or at least the initial state derived from that seed)
>>>> was.
>>>
>>> The paradox I had also posted previously elsewhere and is thus not
>>> specifially constructed for the CSPRNG issue. If the paradox as such
>>> can't be resolved, then I would say that employing entropy to treat
>>> the security of crypto schemes seems to have some fundamental logical
>>> problems in general.
>>
>>
>> Well, your paradox posted previous elsewhere is not immediately
>> visible to me, so I can't really comment on it.
>
>That's the same in content as I described in this thread. (I only
>mentioned its history, in order to explain that it is not specifically
>thought of for this thread.) So you don't have to look at what I posted
>elsewhere and need only to treat what I posted in this thread.
Sorry, after rereading all of your posts in this thread, I can't see
what you're going on about.
What are you trying to do?
[toc] | [prev] | [next] | [standalone]
| From | Mok-Kong Shen <mok-kong.shen@t-online.de> |
|---|---|
| Date | 2015-09-03 02:16 +0200 |
| Message-ID | <ms83g0$2tp$1@news.albasani.net> |
| In reply to | #5757 |
Am 03.09.2015 um 01:53 schrieb Robert Wessel:
> On Thu, 3 Sep 2015 01:33:13 +0200, Mok-Kong Shen
> <mok-kong.shen@t-online.de> wrote:
>
>> Am 03.09.2015 um 01:25 schrieb Robert Wessel:
>>> On Thu, 3 Sep 2015 01:04:43 +0200, Mok-Kong Shen
>>> <mok-kong.shen@t-online.de> wrote:
>>>
>>>> Am 03.09.2015 um 00:52 schrieb Robert Wessel:
>>>>> On Thu, 3 Sep 2015 00:28:33 +0200, Mok-Kong Shen
>>>>> <mok-kong.shen@t-online.de> wrote:
>>>>>
>>>>>> Am 03.09.2015 um 00:18 schrieb Robert Wessel:
>>>>>>> On Thu, 3 Sep 2015 00:03:52 +0200, Mok-Kong Shen
>>>>>>> <mok-kong.shen@t-online.de> 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.
>>>>>>>
>>>>>>>
>>>>>>> If there's 128 bits of entropy going in, that's what's coming out.
>>>>>>> Spread over however many bits you output. IOW, if you encrypt
>>>>>>> something with AES-128 in whatever mode (ignoring any nonce or IV),
>>>>>>> there will be only 2**128 possible decryptions of the message, no
>>>>>>> matter how long it might be.
>>>>>>
>>>>>> But you are ignoring the "entropy" in your 2nd sentence. My paradox
>>>>>> is however centered on "entropy". Each input bit is assumed to have
>>>>>> 1 bit of entropy. After spreading, the average entropy can't be
>>>>>> larger than 128/n. What is wrong in that calculation logically?
>>>>>> That's what I like very much to know from you or Kylheku.
>>>>>
>>>>>
>>>>> I wouldn't use the word average, but there would be about 128/n bits
>>>>> of entropy per output bit.
>>>>>
>>>>> That's not really at question, or very interesting. If I take a
>>>>> gallon of milk, and divide it evenly between 1024 containers, I'll
>>>>> have an eighth of an ounce of milk in each container.
>>>>>
>>>>> I have perhaps missed some part of this discussion.
>>>>>
>>>>> If this has to do with CS vs. non-CS PRNGs, the difference is that
>>>>> non-CS PRNGs make it trivial(-ish) to extract the original data
>>>>> ("entropy") from the stream, or equivalently, allow the prediction of
>>>>> future outputs from existing ones without excessive work. For example
>>>>> you can seed and LFSR with some amount of entropy, but if you have
>>>>> some output from it, you can work it backwards to determine what that
>>>>> initial seed (or at least the initial state derived from that seed)
>>>>> was.
>>>>
>>>> The paradox I had also posted previously elsewhere and is thus not
>>>> specifially constructed for the CSPRNG issue. If the paradox as such
>>>> can't be resolved, then I would say that employing entropy to treat
>>>> the security of crypto schemes seems to have some fundamental logical
>>>> problems in general.
>>>
>>>
>>> Well, your paradox posted previous elsewhere is not immediately
>>> visible to me, so I can't really comment on it.
>>
>> That's the same in content as I described in this thread. (I only
>> mentioned its history, in order to explain that it is not specifically
>> thought of for this thread.) So you don't have to look at what I posted
>> elsewhere and need only to treat what I posted in this thread.
>
>
> Sorry, after rereading all of your posts in this thread, I can't see
> what you're going on about.
>
> What are you trying to do?
You have agreed on my argument that (assuming the quality of output from
AES is uniformly good) the entropy of each output bit is 128/n.
Now, for stream encryption with xor, one needs a good so-called
key-stream. The ideal case is a sequence of bits of full entropy,
i.e. 1.0, which is commonly termed an ideal OTP. The opposite bad
case is a sequence of bits having very low value of entropy. Now, if
n is even moderately large, say 10000, the output bits in CTR mode
will have entropy of 1/10000. Obviously no one would seriously
consider doing any stream encryption with a key-stream having such
a low value of entropy per bit. However, AES in CTR is generally
deemed to be secure in practice. Thus the paradox indicates in my
view that employing the concept entropy to discuss security has some
fundamental problems in general that anyway yet need clarifications.
Have I explained my thoughts clear enough now?
M. K. Shen
[toc] | [prev] | [next] | [standalone]
| From | Mok-Kong Shen <mok-kong.shen@t-online.de> |
|---|---|
| Date | 2015-09-03 02:18 +0200 |
| Message-ID | <ms83k5$2tp$2@news.albasani.net> |
| In reply to | #5759 |
Am 03.09.2015 um 02:16 schrieb Mok-Kong Shen:
> Am 03.09.2015 um 01:53 schrieb Robert Wessel:
>> On Thu, 3 Sep 2015 01:33:13 +0200, Mok-Kong Shen
>> <mok-kong.shen@t-online.de> wrote:
>>
>>> Am 03.09.2015 um 01:25 schrieb Robert Wessel:
>>>> On Thu, 3 Sep 2015 01:04:43 +0200, Mok-Kong Shen
>>>> <mok-kong.shen@t-online.de> wrote:
>>>>
>>>>> Am 03.09.2015 um 00:52 schrieb Robert Wessel:
>>>>>> On Thu, 3 Sep 2015 00:28:33 +0200, Mok-Kong Shen
>>>>>> <mok-kong.shen@t-online.de> wrote:
>>>>>>
>>>>>>> Am 03.09.2015 um 00:18 schrieb Robert Wessel:
>>>>>>>> On Thu, 3 Sep 2015 00:03:52 +0200, Mok-Kong Shen
>>>>>>>> <mok-kong.shen@t-online.de> 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.
>>>>>>>>
>>>>>>>>
>>>>>>>> If there's 128 bits of entropy going in, that's what's coming out.
>>>>>>>> Spread over however many bits you output. IOW, if you encrypt
>>>>>>>> something with AES-128 in whatever mode (ignoring any nonce or IV),
>>>>>>>> there will be only 2**128 possible decryptions of the message, no
>>>>>>>> matter how long it might be.
>>>>>>>
>>>>>>> But you are ignoring the "entropy" in your 2nd sentence. My paradox
>>>>>>> is however centered on "entropy". Each input bit is assumed to have
>>>>>>> 1 bit of entropy. After spreading, the average entropy can't be
>>>>>>> larger than 128/n. What is wrong in that calculation logically?
>>>>>>> That's what I like very much to know from you or Kylheku.
>>>>>>
>>>>>>
>>>>>> I wouldn't use the word average, but there would be about 128/n bits
>>>>>> of entropy per output bit.
>>>>>>
>>>>>> That's not really at question, or very interesting. If I take a
>>>>>> gallon of milk, and divide it evenly between 1024 containers, I'll
>>>>>> have an eighth of an ounce of milk in each container.
>>>>>>
>>>>>> I have perhaps missed some part of this discussion.
>>>>>>
>>>>>> If this has to do with CS vs. non-CS PRNGs, the difference is that
>>>>>> non-CS PRNGs make it trivial(-ish) to extract the original data
>>>>>> ("entropy") from the stream, or equivalently, allow the prediction of
>>>>>> future outputs from existing ones without excessive work. For
>>>>>> example
>>>>>> you can seed and LFSR with some amount of entropy, but if you have
>>>>>> some output from it, you can work it backwards to determine what that
>>>>>> initial seed (or at least the initial state derived from that seed)
>>>>>> was.
>>>>>
>>>>> The paradox I had also posted previously elsewhere and is thus not
>>>>> specifially constructed for the CSPRNG issue. If the paradox as such
>>>>> can't be resolved, then I would say that employing entropy to treat
>>>>> the security of crypto schemes seems to have some fundamental logical
>>>>> problems in general.
>>>>
>>>>
>>>> Well, your paradox posted previous elsewhere is not immediately
>>>> visible to me, so I can't really comment on it.
>>>
>>> That's the same in content as I described in this thread. (I only
>>> mentioned its history, in order to explain that it is not specifically
>>> thought of for this thread.) So you don't have to look at what I posted
>>> elsewhere and need only to treat what I posted in this thread.
>>
>>
>> Sorry, after rereading all of your posts in this thread, I can't see
>> what you're going on about.
>>
>> What are you trying to do?
>
> You have agreed on my argument that (assuming the quality of output from
> AES is uniformly good) the entropy of each output bit is 128/n.
> Now, for stream encryption with xor, one needs a good so-called
> key-stream. The ideal case is a sequence of bits of full entropy,
> i.e. 1.0, which is commonly termed an ideal OTP. The opposite bad
> case is a sequence of bits having very low value of entropy. Now, if
> n is even moderately large, say 10000, the output bits in CTR mode
> will have entropy of 1/10000. Obviously no one would seriously
> consider doing any stream encryption with a key-stream having such
> a low value of entropy per bit. However, AES in CTR is generally
> deemed to be secure in practice. Thus the paradox indicates in my
> view that employing the concept entropy to discuss security has some
> fundamental problems in general that anyway yet need clarifications.
> Have I explained my thoughts clear enough now?
Sorry, typo, read "will have entropy of 128/10000"
M. K. Shen
[toc] | [prev] | [next] | [standalone]
| From | bartekltg <bartek@gmail.com> |
|---|---|
| Date | 2015-09-03 02:33 +0200 |
| Message-ID | <ms84g3$urv$1@speranza.aioe.org> |
| In reply to | #5759 |
On 03.09.2015 02:16, Mok-Kong Shen wrote:
> Am 03.09.2015 um 01:53 schrieb Robert Wessel:
>> On Thu, 3 Sep 2015 01:33:13 +0200, Mok-Kong Shen
>> <mok-kong.shen@t-online.de> wrote:
>>
>>> Am 03.09.2015 um 01:25 schrieb Robert Wessel:
>>>> On Thu, 3 Sep 2015 01:04:43 +0200, Mok-Kong Shen
>>>> <mok-kong.shen@t-online.de> wrote:
>>>>
>>>>> Am 03.09.2015 um 00:52 schrieb Robert Wessel:
>>>>>> On Thu, 3 Sep 2015 00:28:33 +0200, Mok-Kong Shen
>>>>>> <mok-kong.shen@t-online.de> wrote:
>>>>>>
>>>>>>> Am 03.09.2015 um 00:18 schrieb Robert Wessel:
>>>>>>>> On Thu, 3 Sep 2015 00:03:52 +0200, Mok-Kong Shen
>>>>>>>> <mok-kong.shen@t-online.de> 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.
>>>>>>>>
>>>>>>>>
>>>>>>>> If there's 128 bits of entropy going in, that's what's coming out.
>>>>>>>> Spread over however many bits you output. IOW, if you encrypt
>>>>>>>> something with AES-128 in whatever mode (ignoring any nonce or IV),
>>>>>>>> there will be only 2**128 possible decryptions of the message, no
>>>>>>>> matter how long it might be.
>>>>>>>
>>>>>>> But you are ignoring the "entropy" in your 2nd sentence. My paradox
>>>>>>> is however centered on "entropy". Each input bit is assumed to have
>>>>>>> 1 bit of entropy. After spreading, the average entropy can't be
>>>>>>> larger than 128/n. What is wrong in that calculation logically?
>>>>>>> That's what I like very much to know from you or Kylheku.
>>>>>>
>>>>>>
>>>>>> I wouldn't use the word average, but there would be about 128/n bits
>>>>>> of entropy per output bit.
>>>>>>
>>>>>> That's not really at question, or very interesting. If I take a
>>>>>> gallon of milk, and divide it evenly between 1024 containers, I'll
>>>>>> have an eighth of an ounce of milk in each container.
>>>>>>
>>>>>> I have perhaps missed some part of this discussion.
>>>>>>
>>>>>> If this has to do with CS vs. non-CS PRNGs, the difference is that
>>>>>> non-CS PRNGs make it trivial(-ish) to extract the original data
>>>>>> ("entropy") from the stream, or equivalently, allow the prediction of
>>>>>> future outputs from existing ones without excessive work. For
>>>>>> example
>>>>>> you can seed and LFSR with some amount of entropy, but if you have
>>>>>> some output from it, you can work it backwards to determine what that
>>>>>> initial seed (or at least the initial state derived from that seed)
>>>>>> was.
>>>>>
>>>>> The paradox I had also posted previously elsewhere and is thus not
>>>>> specifially constructed for the CSPRNG issue. If the paradox as such
>>>>> can't be resolved, then I would say that employing entropy to treat
>>>>> the security of crypto schemes seems to have some fundamental logical
>>>>> problems in general.
>>>>
>>>>
>>>> Well, your paradox posted previous elsewhere is not immediately
>>>> visible to me, so I can't really comment on it.
>>>
>>> That's the same in content as I described in this thread. (I only
>>> mentioned its history, in order to explain that it is not specifically
>>> thought of for this thread.) So you don't have to look at what I posted
>>> elsewhere and need only to treat what I posted in this thread.
>>
>>
>> Sorry, after rereading all of your posts in this thread, I can't see
>> what you're going on about.
>>
>> What are you trying to do?
>
> You have agreed on my argument that (assuming the quality of output from
> AES is uniformly good) the entropy of each output bit is 128/n.
No, stop this and read mathbook and definition of entropy;-)
One bit is either x1=0 or x2=1. If AES is good, probability of both
are equal. So P(x1) = P(x2) = 0.5.
Entropy oh this one bit is H = \sum_i P(x_i)*log2(1/P(x_i)) =
0.5*log2(2)+0.5*log2(2) = 1
One bit.
It can't be more.
It can be less, if propability od that bit equal 1 is not 1/2,
but this is against the assumption about AES.
The entropy of one bit taken from sequence of n bits (n is arbitrary),
generated by decent hash function, from 128bit random sequence,
is 1bit.
Never more. Significantly less only if hash function is broken.
bartekltg
[toc] | [prev] | [next] | [standalone]
| From | Mok-Kong Shen <mok-kong.shen@t-online.de> |
|---|---|
| Date | 2015-09-03 02:42 +0200 |
| Message-ID | <ms850q$51n$1@news.albasani.net> |
| In reply to | #5763 |
Am 03.09.2015 um 02:33 schrieb bartekltg:
> On 03.09.2015 02:16, Mok-Kong Shen wrote:
>> Am 03.09.2015 um 01:53 schrieb Robert Wessel:
>>> On Thu, 3 Sep 2015 01:33:13 +0200, Mok-Kong Shen
>>> <mok-kong.shen@t-online.de> wrote:
>>>
>>>> Am 03.09.2015 um 01:25 schrieb Robert Wessel:
>>>>> On Thu, 3 Sep 2015 01:04:43 +0200, Mok-Kong Shen
>>>>> <mok-kong.shen@t-online.de> wrote:
>>>>>
>>>>>> Am 03.09.2015 um 00:52 schrieb Robert Wessel:
>>>>>>> On Thu, 3 Sep 2015 00:28:33 +0200, Mok-Kong Shen
>>>>>>> <mok-kong.shen@t-online.de> wrote:
>>>>>>>
>>>>>>>> Am 03.09.2015 um 00:18 schrieb Robert Wessel:
>>>>>>>>> On Thu, 3 Sep 2015 00:03:52 +0200, Mok-Kong Shen
>>>>>>>>> <mok-kong.shen@t-online.de> 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.
>>>>>>>>>
>>>>>>>>>
>>>>>>>>> If there's 128 bits of entropy going in, that's what's coming out.
>>>>>>>>> Spread over however many bits you output. IOW, if you encrypt
>>>>>>>>> something with AES-128 in whatever mode (ignoring any nonce or
>>>>>>>>> IV),
>>>>>>>>> there will be only 2**128 possible decryptions of the message, no
>>>>>>>>> matter how long it might be.
>>>>>>>>
>>>>>>>> But you are ignoring the "entropy" in your 2nd sentence. My paradox
>>>>>>>> is however centered on "entropy". Each input bit is assumed to have
>>>>>>>> 1 bit of entropy. After spreading, the average entropy can't be
>>>>>>>> larger than 128/n. What is wrong in that calculation logically?
>>>>>>>> That's what I like very much to know from you or Kylheku.
>>>>>>>
>>>>>>>
>>>>>>> I wouldn't use the word average, but there would be about 128/n bits
>>>>>>> of entropy per output bit.
>>>>>>>
>>>>>>> That's not really at question, or very interesting. If I take a
>>>>>>> gallon of milk, and divide it evenly between 1024 containers, I'll
>>>>>>> have an eighth of an ounce of milk in each container.
>>>>>>>
>>>>>>> I have perhaps missed some part of this discussion.
>>>>>>>
>>>>>>> If this has to do with CS vs. non-CS PRNGs, the difference is that
>>>>>>> non-CS PRNGs make it trivial(-ish) to extract the original data
>>>>>>> ("entropy") from the stream, or equivalently, allow the
>>>>>>> prediction of
>>>>>>> future outputs from existing ones without excessive work. For
>>>>>>> example
>>>>>>> you can seed and LFSR with some amount of entropy, but if you have
>>>>>>> some output from it, you can work it backwards to determine what
>>>>>>> that
>>>>>>> initial seed (or at least the initial state derived from that seed)
>>>>>>> was.
>>>>>>
>>>>>> The paradox I had also posted previously elsewhere and is thus not
>>>>>> specifially constructed for the CSPRNG issue. If the paradox as such
>>>>>> can't be resolved, then I would say that employing entropy to treat
>>>>>> the security of crypto schemes seems to have some fundamental logical
>>>>>> problems in general.
>>>>>
>>>>>
>>>>> Well, your paradox posted previous elsewhere is not immediately
>>>>> visible to me, so I can't really comment on it.
>>>>
>>>> That's the same in content as I described in this thread. (I only
>>>> mentioned its history, in order to explain that it is not specifically
>>>> thought of for this thread.) So you don't have to look at what I posted
>>>> elsewhere and need only to treat what I posted in this thread.
>>>
>>>
>>> Sorry, after rereading all of your posts in this thread, I can't see
>>> what you're going on about.
>>>
>>> What are you trying to do?
>>
>> You have agreed on my argument that (assuming the quality of output from
>> AES is uniformly good) the entropy of each output bit is 128/n.
>
> No, stop this and read mathbook and definition of entropy;-)
>
> One bit is either x1=0 or x2=1. If AES is good, probability of both
> are equal. So P(x1) = P(x2) = 0.5.
>
> Entropy oh this one bit is H = \sum_i P(x_i)*log2(1/P(x_i)) =
> 0.5*log2(2)+0.5*log2(2) = 1
> One bit.
>
> It can't be more.
>
> It can be less, if propability od that bit equal 1 is not 1/2,
> but this is against the assumption about AES.
>
> The entropy of one bit taken from sequence of n bits (n is arbitrary),
> generated by decent hash function, from 128bit random sequence,
> is 1bit.
>
> Never more. Significantly less only if hash function is broken.
Have I ever said of bits having entropy greater than 1.0 per bit?
That in practice, even with very good devices, one get's less
than 1.0 entropy per bit is understandable and well known. But that
doesn't affect my paradox logically which takes some idealizations
for discussion purposes. Is that ok?
M. K. Shen
[toc] | [prev] | [next] | [standalone]
| From | bartekltg <bartek@gmail.com> |
|---|---|
| Date | 2015-09-03 02:55 +0200 |
| Message-ID | <ms85qr$1eg$2@speranza.aioe.org> |
| In reply to | #5764 |
On 03.09.2015 02:42, Mok-Kong Shen wrote: > Am 03.09.2015 um 02:33 schrieb bartekltg: >> >> No, stop this and read mathbook and definition of entropy;-) >> >> One bit is either x1=0 or x2=1. If AES is good, probability of both >> are equal. So P(x1) = P(x2) = 0.5. >> >> Entropy oh this one bit is H = \sum_i P(x_i)*log2(1/P(x_i)) = >> 0.5*log2(2)+0.5*log2(2) = 1 >> One bit. >> >> It can't be more. >> >> It can be less, if propability od that bit equal 1 is not 1/2, >> but this is against the assumption about AES. >> >> The entropy of one bit taken from sequence of n bits (n is arbitrary), >> generated by decent hash function, from 128bit random sequence, >> is 1bit. >> >> Never more. Significantly less only if hash function is broken. > > Have I ever said of bits having entropy greater than 1.0 per bit? 128/n is greater than one for 127 different positive integers;-) > That in practice, even with very good devices, one get's less > than 1.0 entropy per bit is understandable and well known. But that > doesn't affect my paradox logically which takes some idealizations > for discussion purposes. Is that ok? OK. And now you can read this post one more time to get to the of it main point and understand, why it always is (almost) one bit of entropy, even if n = 495624357436265. bartekltg
[toc] | [prev] | [next] | [standalone]
| From | Mok-Kong Shen <mok-kong.shen@t-online.de> |
|---|---|
| Date | 2015-09-03 03:03 +0200 |
| Message-ID | <ms8697$6u7$1@news.albasani.net> |
| In reply to | #5767 |
Am 03.09.2015 um 02:55 schrieb bartekltg: > On 03.09.2015 02:42, Mok-Kong Shen wrote: >> Am 03.09.2015 um 02:33 schrieb bartekltg: > >>> >>> No, stop this and read mathbook and definition of entropy;-) >>> >>> One bit is either x1=0 or x2=1. If AES is good, probability of both >>> are equal. So P(x1) = P(x2) = 0.5. >>> >>> Entropy oh this one bit is H = \sum_i P(x_i)*log2(1/P(x_i)) = >>> 0.5*log2(2)+0.5*log2(2) = 1 >>> One bit. >>> >>> It can't be more. >>> >>> It can be less, if propability od that bit equal 1 is not 1/2, >>> but this is against the assumption about AES. >>> >>> The entropy of one bit taken from sequence of n bits (n is arbitrary), >>> generated by decent hash function, from 128bit random sequence, >>> is 1bit. >>> >>> Never more. Significantly less only if hash function is broken. >> >> Have I ever said of bits having entropy greater than 1.0 per bit? > > 128/n is greater than one for 127 different positive integers;-) What are you saying here? I stated that n >> 128! > >> That in practice, even with very good devices, one get's less >> than 1.0 entropy per bit is understandable and well known. But that >> doesn't affect my paradox logically which takes some idealizations >> for discussion purposes. Is that ok? > > OK. And now you can read this post one more time to get to > the of it main point and understand, why it always is (almost) > one bit of entropy, even if n = 495624357436265. What do you mean? If you consider that the input bits have an entropy value of t with t < 1.0, then the output bits will have entropy value of 128*t/n and the same paradoxical effect would follow. M. K. Shen
[toc] | [prev] | [next] | [standalone]
| From | bartekltg <bartek@gmail.com> |
|---|---|
| Date | 2015-09-03 03:14 +0200 |
| Message-ID | <ms86tl$3ah$1@speranza.aioe.org> |
| In reply to | #5769 |
On 03.09.2015 03:03, Mok-Kong Shen wrote: > > What do you mean? If you consider that the input bits have an > entropy value of t with t < 1.0, then the output bits will > have entropy value of 128*t/n and the same paradoxical > effect would follow. No. This is wrong. I explained it a couple of times, but you need to _read_ it. Carefully and slowly. This isn't a hard part of mathematics, but it can be confusing at first try. First try to understand the definition of entropy. Read wiki or book, then look at my post with "4 bit toy AES". bartekltg
[toc] | [prev] | [next] | [standalone]
| From | Mok-Kong Shen <mok-kong.shen@t-online.de> |
|---|---|
| Date | 2015-09-03 03:17 +0200 |
| Message-ID | <ms8735$6u7$2@news.albasani.net> |
| In reply to | #5771 |
Am 03.09.2015 um 03:14 schrieb bartekltg: > On 03.09.2015 03:03, Mok-Kong Shen wrote: > >> >> What do you mean? If you consider that the input bits have an >> entropy value of t with t < 1.0, then the output bits will >> have entropy value of 128*t/n and the same paradoxical >> effect would follow. > > No. This is wrong. I explained it a couple of times, > but you need to _read_ it. Carefully and slowly. > This isn't a hard part of mathematics, but it can > be confusing at first try. First try to understand > the definition of entropy. Read wiki or book, then > look at my post with "4 bit toy AES". I do think that I know what entropy is. Anyway, also Wessel ágreed on my calculation of 128/n. (Would you like to refute him?) M. K. Shen
[toc] | [prev] | [next] | [standalone]
| From | bartekltg <bartek@gmail.com> |
|---|---|
| Date | 2015-09-03 03:30 +0200 |
| Message-ID | <ms87rd$52p$1@speranza.aioe.org> |
| In reply to | #5772 |
On 03.09.2015 03:17, Mok-Kong Shen wrote: > Am 03.09.2015 um 03:14 schrieb bartekltg: >> On 03.09.2015 03:03, Mok-Kong Shen wrote: >> >>> >>> What do you mean? If you consider that the input bits have an >>> entropy value of t with t < 1.0, then the output bits will >>> have entropy value of 128*t/n and the same paradoxical >>> effect would follow. >> >> No. This is wrong. I explained it a couple of times, >> but you need to _read_ it. Carefully and slowly. >> This isn't a hard part of mathematics, but it can >> be confusing at first try. First try to understand >> the definition of entropy. Read wiki or book, then >> look at my post with "4 bit toy AES". > > I do think that I know what entropy is. No, sadly you have no idea:( Not if you still claim "128/n". I don't talk about intuition, but a real definition. The half-true intimation is that what has mislead you. > Anyway, also > Wessel ágreed on my calculation of 128/n. (Would you > like to refute him?) WTF? Mathematics is not a democracy, there is no voting. I give you a simple proof. It even ton't deserve to be called a proof. "Substitute to the definition", this is all. bartekltg
[toc] | [prev] | [next] | [standalone]
| From | Mok-Kong Shen <mok-kong.shen@t-online.de> |
|---|---|
| Date | 2015-09-03 03:36 +0200 |
| Message-ID | <ms886k$ab0$2@news.albasani.net> |
| In reply to | #5773 |
Am 03.09.2015 um 03:30 schrieb bartekltg: > On 03.09.2015 03:17, Mok-Kong Shen wrote: >> Am 03.09.2015 um 03:14 schrieb bartekltg: >>> On 03.09.2015 03:03, Mok-Kong Shen wrote: >>> >>>> >>>> What do you mean? If you consider that the input bits have an >>>> entropy value of t with t < 1.0, then the output bits will >>>> have entropy value of 128*t/n and the same paradoxical >>>> effect would follow. >>> >>> No. This is wrong. I explained it a couple of times, >>> but you need to _read_ it. Carefully and slowly. >>> This isn't a hard part of mathematics, but it can >>> be confusing at first try. First try to understand >>> the definition of entropy. Read wiki or book, then >>> look at my post with "4 bit toy AES". >> >> I do think that I know what entropy is. > > No, sadly you have no idea:( Not if you still claim "128/n". > > I don't talk about intuition, but a real definition. > The half-true intimation is that what has mislead you. > >> Anyway, also >> Wessel ágreed on my calculation of 128/n. (Would you >> like to refute him?) > > WTF? Mathematics is not a democracy, there is no voting. > I give you a simple proof. > It even ton't deserve to be called a proof. > "Substitute to the definition", this is all. Why don't you similarly tell Wessel that he is wrong? M. K. Shen
[toc] | [prev] | [next] | [standalone]
| From | bartekltg <bartek@gmail.com> |
|---|---|
| Date | 2015-09-03 04:13 +0200 |
| Message-ID | <ms8ac2$90e$1@speranza.aioe.org> |
| In reply to | #5775 |
On 03.09.2015 03:36, Mok-Kong Shen wrote: > Am 03.09.2015 um 03:30 schrieb bartekltg: >> On 03.09.2015 03:17, Mok-Kong Shen wrote: >>> Am 03.09.2015 um 03:14 schrieb bartekltg: >>>> On 03.09.2015 03:03, Mok-Kong Shen wrote: >>>> >>>>> >>>>> What do you mean? If you consider that the input bits have an >>>>> entropy value of t with t < 1.0, then the output bits will >>>>> have entropy value of 128*t/n and the same paradoxical >>>>> effect would follow. >>>> >>>> No. This is wrong. I explained it a couple of times, >>>> but you need to _read_ it. Carefully and slowly. >>>> This isn't a hard part of mathematics, but it can >>>> be confusing at first try. First try to understand >>>> the definition of entropy. Read wiki or book, then >>>> look at my post with "4 bit toy AES". >>> >>> I do think that I know what entropy is. >> >> No, sadly you have no idea:( Not if you still claim "128/n". >> >> I don't talk about intuition, but a real definition. >> The half-true intimation is that what has mislead you. >> >>> Anyway, also >>> Wessel ágreed on my calculation of 128/n. (Would you >>> like to refute him?) >> >> WTF? Mathematics is not a democracy, there is no voting. >> I give you a simple proof. >> It even ton't deserve to be called a proof. >> "Substitute to the definition", this is all. > > Why don't you similarly tell Wessel that he is wrong? Are you serious? Wessel! I summon you because you have written: >>> I wouldn't use the word average, but there would be about 128/n bits >>> of entropy per output bit. and this is so wrong that I have to tell you that so you kung-fu... I mean your math->probabilistic->information theory is weak. ;-) Hmm. But Wessel post one message where he agreed with you, and a couple of messages where he claim he do not understand what you are doing. He go to sleep/work/away form usenet and didn't read a dozen of our post about the problem, including post with proof or post with nice illustration how it works. In other hand, you have many chances to take a bit of paper and work it out. ;-) bartekltg
[toc] | [prev] | [next] | [standalone]
| From | Mok-Kong Shen <mok-kong.shen@t-online.de> |
|---|---|
| Date | 2015-09-03 04:19 +0200 |
| Message-ID | <ms8ao1$eju$1@news.albasani.net> |
| In reply to | #5778 |
Am 03.09.2015 um 04:13 schrieb bartekltg: > On 03.09.2015 03:36, Mok-Kong Shen wrote: >> Am 03.09.2015 um 03:30 schrieb bartekltg: >>> On 03.09.2015 03:17, Mok-Kong Shen wrote: >>>> Am 03.09.2015 um 03:14 schrieb bartekltg: >>>>> On 03.09.2015 03:03, Mok-Kong Shen wrote: >>>>> >>>>>> >>>>>> What do you mean? If you consider that the input bits have an >>>>>> entropy value of t with t < 1.0, then the output bits will >>>>>> have entropy value of 128*t/n and the same paradoxical >>>>>> effect would follow. >>>>> >>>>> No. This is wrong. I explained it a couple of times, >>>>> but you need to _read_ it. Carefully and slowly. >>>>> This isn't a hard part of mathematics, but it can >>>>> be confusing at first try. First try to understand >>>>> the definition of entropy. Read wiki or book, then >>>>> look at my post with "4 bit toy AES". >>>> >>>> I do think that I know what entropy is. >>> >>> No, sadly you have no idea:( Not if you still claim "128/n". >>> >>> I don't talk about intuition, but a real definition. >>> The half-true intimation is that what has mislead you. >>> >>>> Anyway, also >>>> Wessel ágreed on my calculation of 128/n. (Would you >>>> like to refute him?) >>> >>> WTF? Mathematics is not a democracy, there is no voting. >>> I give you a simple proof. >>> It even ton't deserve to be called a proof. >>> "Substitute to the definition", this is all. >> >> Why don't you similarly tell Wessel that he is wrong? > > Are you serious? > > > Wessel! I summon you because you have written: > > >>> I wouldn't use the word average, but there would be about 128/n bits > >>> of entropy per output bit. > > and this is so wrong that I have to tell you that so you > kung-fu... I mean your math->probabilistic->information theory > is weak. > > ;-) > > > Hmm. But Wessel post one message where he agreed with you, > and a couple of messages where he claim he do not understand > what you are doing. He go to sleep/work/away form usenet > and didn't read a dozen of our post about the problem, > including post with proof or post with nice illustration > how it works. > In other hand, you have many chances to take a bit of paper > and work it out. > ;-) No matter what you claim here, Wessel has written that the he agreed that the total entropy is evenly diluted. So please write first a post to him telling him of his error (in that post) in your opinion. Afterwards we could continue discuss here. ok? M. K. Shen
[toc] | [prev] | [next] | [standalone]
| From | bartekltg <bartek@gmail.com> |
|---|---|
| Date | 2015-09-03 04:32 +0200 |
| Message-ID | <ms8bfa$apm$1@speranza.aioe.org> |
| In reply to | #5780 |
On 03.09.2015 04:19, Mok-Kong Shen wrote: > No matter what you claim here, Wessel has written that the > he agreed that the total entropy is evenly diluted. So please > write first a post to him telling him of his error (in that > post) in your opinion. Afterwards we could continue discuss here. > ok? No. 1. Is everything OK? This obsession looks bad. 2. We going in circles. I think I have written everything what is needed to understand this problem. Sure, it can be said clearer and in better words, but it is enough. If you have a substantial question, that hasn't been answered three times, I will try to answer it. bartekltg
[toc] | [prev] | [next] | [standalone]
| From | Robert Wessel <robertwessel2@yahoo.com> |
|---|---|
| Date | 2015-09-02 22:51 -0500 |
| Message-ID | <3vefualelae74fhsmcs0elv5us837istlh@4ax.com> |
| In reply to | #5759 |
On Thu, 3 Sep 2015 02:16:03 +0200, Mok-Kong Shen
<mok-kong.shen@t-online.de> wrote:
>Am 03.09.2015 um 01:53 schrieb Robert Wessel:
>> On Thu, 3 Sep 2015 01:33:13 +0200, Mok-Kong Shen
>> <mok-kong.shen@t-online.de> wrote:
>>
>>> Am 03.09.2015 um 01:25 schrieb Robert Wessel:
>>>> On Thu, 3 Sep 2015 01:04:43 +0200, Mok-Kong Shen
>>>> <mok-kong.shen@t-online.de> wrote:
>>>>
>>>>> Am 03.09.2015 um 00:52 schrieb Robert Wessel:
>>>>>> On Thu, 3 Sep 2015 00:28:33 +0200, Mok-Kong Shen
>>>>>> <mok-kong.shen@t-online.de> wrote:
>>>>>>
>>>>>>> Am 03.09.2015 um 00:18 schrieb Robert Wessel:
>>>>>>>> On Thu, 3 Sep 2015 00:03:52 +0200, Mok-Kong Shen
>>>>>>>> <mok-kong.shen@t-online.de> 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.
>>>>>>>>
>>>>>>>>
>>>>>>>> If there's 128 bits of entropy going in, that's what's coming out.
>>>>>>>> Spread over however many bits you output. IOW, if you encrypt
>>>>>>>> something with AES-128 in whatever mode (ignoring any nonce or IV),
>>>>>>>> there will be only 2**128 possible decryptions of the message, no
>>>>>>>> matter how long it might be.
>>>>>>>
>>>>>>> But you are ignoring the "entropy" in your 2nd sentence. My paradox
>>>>>>> is however centered on "entropy". Each input bit is assumed to have
>>>>>>> 1 bit of entropy. After spreading, the average entropy can't be
>>>>>>> larger than 128/n. What is wrong in that calculation logically?
>>>>>>> That's what I like very much to know from you or Kylheku.
>>>>>>
>>>>>>
>>>>>> I wouldn't use the word average, but there would be about 128/n bits
>>>>>> of entropy per output bit.
>>>>>>
>>>>>> That's not really at question, or very interesting. If I take a
>>>>>> gallon of milk, and divide it evenly between 1024 containers, I'll
>>>>>> have an eighth of an ounce of milk in each container.
>>>>>>
>>>>>> I have perhaps missed some part of this discussion.
>>>>>>
>>>>>> If this has to do with CS vs. non-CS PRNGs, the difference is that
>>>>>> non-CS PRNGs make it trivial(-ish) to extract the original data
>>>>>> ("entropy") from the stream, or equivalently, allow the prediction of
>>>>>> future outputs from existing ones without excessive work. For example
>>>>>> you can seed and LFSR with some amount of entropy, but if you have
>>>>>> some output from it, you can work it backwards to determine what that
>>>>>> initial seed (or at least the initial state derived from that seed)
>>>>>> was.
>>>>>
>>>>> The paradox I had also posted previously elsewhere and is thus not
>>>>> specifially constructed for the CSPRNG issue. If the paradox as such
>>>>> can't be resolved, then I would say that employing entropy to treat
>>>>> the security of crypto schemes seems to have some fundamental logical
>>>>> problems in general.
>>>>
>>>>
>>>> Well, your paradox posted previous elsewhere is not immediately
>>>> visible to me, so I can't really comment on it.
>>>
>>> That's the same in content as I described in this thread. (I only
>>> mentioned its history, in order to explain that it is not specifically
>>> thought of for this thread.) So you don't have to look at what I posted
>>> elsewhere and need only to treat what I posted in this thread.
>>
>>
>> Sorry, after rereading all of your posts in this thread, I can't see
>> what you're going on about.
>>
>> What are you trying to do?
>
>You have agreed on my argument that (assuming the quality of output from
>AES is uniformly good) the entropy of each output bit is 128/n.
>Now, for stream encryption with xor, one needs a good so-called
>key-stream. The ideal case is a sequence of bits of full entropy,
>i.e. 1.0, which is commonly termed an ideal OTP. The opposite bad
>case is a sequence of bits having very low value of entropy. Now, if
>n is even moderately large, say 10000, the output bits in CTR mode
>will have entropy of 1/10000. Obviously no one would seriously
>consider doing any stream encryption with a key-stream having such
>a low value of entropy per bit. However, AES in CTR is generally
>deemed to be secure in practice. Thus the paradox indicates in my
>view that employing the concept entropy to discuss security has some
>fundamental problems in general that anyway yet need clarifications.
>Have I explained my thoughts clear enough now?
OK, I think I now understand what you're asking.
First things first, bartekltg is pretty much right on target. And as
I said, the spreading of the input entropy by a PRNG in that sense is
not actually an interesting question. You've spread (say) 128 bits of
"real" entropy over more bits, that's all. There are many sources of
random bits where we do need to consider that. For example when
generating randomness from a physical source, the actual bits from the
source will almost always have some, or (more commonly) a lot, of
bias, and you need to consider how many input bits you need to feed
into your whitening function in order to get output bits with ~1.00
bits of "real" entropy (aka "randomness"). If you spread 128 bits of
entropy over 1024 bits, a process that tries to create something with
some amount of real randomness, will need to collect eight input bits
for every output bit. This applies to prime generation for
Diffie-Hellman or RSA purposes, for example, where you actually need
(almost*) 1024 of real randomness in order to generate an actual 1024
bit random prime.
The entire output of a AES-128 stream (assuming a good key), will
contain 2**128 bits of entropy. Used in a stream cipher (as for CTR
mode), that means the "key" stream will only be one of 2**128 possible
streams, no matter how long the generated stream is.
The crucial thing is that this is an implausible amount of work, and
there's no way to easily dig the input entropy (or at least one of the
internal states) of the stream cipher out of the key stream.
We can for any stream cipher, knowing 128 bits (or more) of the key
stream (and this includes a block cipher in CTR mode), recover the
input key in about 2**128 units of work. That's basically the same as
a known plaintext attack.
We use ciphers, of all sorts, with that "low" an "entropy" for the
entire stream constantly. Where you're mixing things up is that this
is in a different measurement, namely that of the apparent
"randomness" of the keystream. That's commonly called "entropy", but
it's not. Or at least it's a different sort. That "appaerent
entropy", is what something like diehard will report when you feed it
the keystream. That "apparent entropy" is required in a stream cipher
(any keystream output from a stream cipher had darn well better score
near 1.00 in diehard - although that's *not* sufficient - any good
non-CS PRNG will do that), but is not related to "real" entropy, IOW,
entropy based on randomness. The fact that diehard reports 1.00 for
such a stream is a failure of diehard to adequately understand the
stream.
You're attempting to compare two different things that happen to both
be commonly called entropy: actual randomness, and the apparent
randomness of a psuedo-random stream. If you remember your first
semester of physics, you've failed to keep your units straight.
*I don't want to get off topic, but the theoretical requirement
depends on the density of rime numbers in the size range you're
generating, at 1024 bits, it's about 1-in-700, so you need
(1024-lg(700)) to randomly select one of the actual primes - in
practice we always generate 1022, then attempt to see if we actually
hit one.
[toc] | [prev] | [next] | [standalone]
| From | Mok-Kong Shen <mok-kong.shen@t-online.de> |
|---|---|
| Date | 2015-09-03 16:51 +0200 |
| Message-ID | <ms9mod$hei$1@news.albasani.net> |
| In reply to | #5783 |
Am 03.09.2015 um 05:51 schrieb Robert Wessel: > On Thu, 3 Sep 2015 02:16:03 +0200, Mok-Kong Shen > <mok-kong.shen@t-online.de> wrote: [snip] >> You have agreed on my argument that (assuming the quality of output from >> AES is uniformly good) the entropy of each output bit is 128/n. >> Now, for stream encryption with xor, one needs a good so-called >> key-stream. The ideal case is a sequence of bits of full entropy, >> i.e. 1.0, which is commonly termed an ideal OTP. The opposite bad >> case is a sequence of bits having very low value of entropy. Now, if >> n is even moderately large, say 10000, the output bits in CTR mode >> will have entropy of 1/10000. Obviously no one would seriously >> consider doing any stream encryption with a key-stream having such >> a low value of entropy per bit. However, AES in CTR is generally >> deemed to be secure in practice. Thus the paradox indicates in my >> view that employing the concept entropy to discuss security has some >> fundamental problems in general that anyway yet need clarifications. >> Have I explained my thoughts clear enough now? > > > OK, I think I now understand what you're asking. > > First things first, bartekltg is pretty much right on target. And as > I said, the spreading of the input entropy by a PRNG in that sense is > not actually an interesting question. You've spread (say) 128 bits of > "real" entropy over more bits, that's all. There are many sources of > random bits where we do need to consider that. For example when > generating randomness from a physical source, the actual bits from the > source will almost always have some, or (more commonly) a lot, of > bias, and you need to consider how many input bits you need to feed > into your whitening function in order to get output bits with ~1.00 > bits of "real" entropy (aka "randomness"). If you spread 128 bits of > entropy over 1024 bits, a process that tries to create something with > some amount of real randomness, will need to collect eight input bits > for every output bit. This applies to prime generation for > Diffie-Hellman or RSA purposes, for example, where you actually need > (almost*) 1024 of real randomness in order to generate an actual 1024 > bit random prime. > > The entire output of a AES-128 stream (assuming a good key), will > contain 2**128 bits of entropy. Used in a stream cipher (as for CTR > mode), that means the "key" stream will only be one of 2**128 possible > streams, no matter how long the generated stream is. > > The crucial thing is that this is an implausible amount of work, and > there's no way to easily dig the input entropy (or at least one of the > internal states) of the stream cipher out of the key stream. > > We can for any stream cipher, knowing 128 bits (or more) of the key > stream (and this includes a block cipher in CTR mode), recover the > input key in about 2**128 units of work. That's basically the same as > a known plaintext attack. > > We use ciphers, of all sorts, with that "low" an "entropy" for the > entire stream constantly. Where you're mixing things up is that this > is in a different measurement, namely that of the apparent > "randomness" of the keystream. That's commonly called "entropy", but > it's not. Or at least it's a different sort. That "appaerent > entropy", is what something like diehard will report when you feed it > the keystream. That "apparent entropy" is required in a stream cipher > (any keystream output from a stream cipher had darn well better score > near 1.00 in diehard - although that's *not* sufficient - any good > non-CS PRNG will do that), but is not related to "real" entropy, IOW, > entropy based on randomness. The fact that diehard reports 1.00 for > such a stream is a failure of diehard to adequately understand the > stream. > > You're attempting to compare two different things that happen to both > be commonly called entropy: actual randomness, and the apparent > randomness of a psuedo-random stream. If you remember your first > semester of physics, you've failed to keep your units straight. 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.) M. K. Shen
[toc] | [prev] | [next] | [standalone]
| From | Robert Wessel <robertwessel2@yahoo.com> |
|---|---|
| Date | 2015-09-03 10:49 -0500 |
| Message-ID | <fjqgua5aqj4v41bgr73ou57kftm5scnp7v@4ax.com> |
| In reply to | #5791 |
On Thu, 3 Sep 2015 16:51:00 +0200, Mok-Kong Shen <mok-kong.shen@t-online.de> wrote: >Am 03.09.2015 um 05:51 schrieb Robert Wessel: >> On Thu, 3 Sep 2015 02:16:03 +0200, Mok-Kong Shen >> <mok-kong.shen@t-online.de> wrote: >[snip] > >>> You have agreed on my argument that (assuming the quality of output from >>> AES is uniformly good) the entropy of each output bit is 128/n. >>> Now, for stream encryption with xor, one needs a good so-called >>> key-stream. The ideal case is a sequence of bits of full entropy, >>> i.e. 1.0, which is commonly termed an ideal OTP. The opposite bad >>> case is a sequence of bits having very low value of entropy. Now, if >>> n is even moderately large, say 10000, the output bits in CTR mode >>> will have entropy of 1/10000. Obviously no one would seriously >>> consider doing any stream encryption with a key-stream having such >>> a low value of entropy per bit. However, AES in CTR is generally >>> deemed to be secure in practice. Thus the paradox indicates in my >>> view that employing the concept entropy to discuss security has some >>> fundamental problems in general that anyway yet need clarifications. >>> Have I explained my thoughts clear enough now? >> >> >> OK, I think I now understand what you're asking. >> >> First things first, bartekltg is pretty much right on target. And as >> I said, the spreading of the input entropy by a PRNG in that sense is >> not actually an interesting question. You've spread (say) 128 bits of >> "real" entropy over more bits, that's all. There are many sources of >> random bits where we do need to consider that. For example when >> generating randomness from a physical source, the actual bits from the >> source will almost always have some, or (more commonly) a lot, of >> bias, and you need to consider how many input bits you need to feed >> into your whitening function in order to get output bits with ~1.00 >> bits of "real" entropy (aka "randomness"). If you spread 128 bits of >> entropy over 1024 bits, a process that tries to create something with >> some amount of real randomness, will need to collect eight input bits >> for every output bit. This applies to prime generation for >> Diffie-Hellman or RSA purposes, for example, where you actually need >> (almost*) 1024 of real randomness in order to generate an actual 1024 >> bit random prime. >> >> The entire output of a AES-128 stream (assuming a good key), will >> contain 2**128 bits of entropy. Used in a stream cipher (as for CTR >> mode), that means the "key" stream will only be one of 2**128 possible >> streams, no matter how long the generated stream is. >> >> The crucial thing is that this is an implausible amount of work, and >> there's no way to easily dig the input entropy (or at least one of the >> internal states) of the stream cipher out of the key stream. >> >> We can for any stream cipher, knowing 128 bits (or more) of the key >> stream (and this includes a block cipher in CTR mode), recover the >> input key in about 2**128 units of work. That's basically the same as >> a known plaintext attack. >> >> We use ciphers, of all sorts, with that "low" an "entropy" for the >> entire stream constantly. Where you're mixing things up is that this >> is in a different measurement, namely that of the apparent >> "randomness" of the keystream. That's commonly called "entropy", but >> it's not. Or at least it's a different sort. That "appaerent >> entropy", is what something like diehard will report when you feed it >> the keystream. That "apparent entropy" is required in a stream cipher >> (any keystream output from a stream cipher had darn well better score >> near 1.00 in diehard - although that's *not* sufficient - any good >> non-CS PRNG will do that), but is not related to "real" entropy, IOW, >> entropy based on randomness. The fact that diehard reports 1.00 for >> such a stream is a failure of diehard to adequately understand the >> stream. >> >> You're attempting to compare two different things that happen to both >> be commonly called entropy: actual randomness, and the apparent >> randomness of a psuedo-random stream. If you remember your first >> semester of physics, you've failed to keep your units straight. > >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).
[toc] | [prev] | [next] | [standalone]
Page 2 of 5 — ← Prev page 1 [2] 3 4 5 Next page →
Back to top | Article view | comp.programming
csiph-web