At 10:15 PM 2/12/2001 GMT, Nikita Borisov wrote:
>In article <3.0.3.32.20010208064718.00fd6870mail>,
>Alex Alten <Altenhome.com> wrote:
>>At 04:08 PM 2/7/2001 -0800, Wei Dai wrote:
>>>Instead of using /dev/random directly, grab 160 bits from it as a seed for
>>>your own PRNG, and then generate q using that.
>>
>>I feel uncomfortable with this suggestion. I doubt you can eliminate the
>>problem by transforming the bits via another PRNG.
>
>I think the attack becomes much harder if we use this construction with
>a cryptographically strong PRNG seeded with 160 bits. Intuitively, to
>succeed the Bliechenbacher attack would need to distinguish the output
>of the PRNG from random, which should be computationally infeasible.
>From what I can understand, the attacker needs to know which values of k
>are more likely than others. To a first approximation, P(k=k_0) >
>2^-160 if there exists a seed s such that PRNG(s) = x,k_0,... (breaking
>up the output into 160-bit chunks) and x >= q. In other words, given
>that the first output of the PRNG was outside the range [0..q-1], we
>need to find out what the likely values for the second output are. A
>cryptographically strong PRNG should make this infeasible.
>

No PRNG can increase entropy, for example from 160 to 168 bits. What
you are suggesting cannot possibly eliminate the bias problem. It's
kind of like claiming you've invented a perpetual motion machine, the
patent office will toss you out without bothering to examine it.

- Alex

--
Alex Alten
AltenHome.Com

• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]