tech-kern archive

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]

Re: Patch: new random pseudodevice

> [...] I'm pretty sure the assertion you seem to keep making that if
> you use 128 bits of information to key a CSPRNG, or a cryptographic
> hash, or pretty much any other cryptographic device, then taking 128
> bits of output from the device is fine but the 129th bit is somehow
> suspect,

I don't think that's quite what I've been saying.

I've been saying that the output contains at most 128 bits of
information, no matter how many bits it's spread among.  This
information is not necessarily all present in the first 128 bits of
output, and, as you point out, if it is then it is a weakness in the CS
part of the PRNG.

> The argument that the 128 bits are indistinguishable from random
> instead relies on a computational expense argument:

Right.  That's why I consider it a weak argument - attacks just get
better.  Once upon a time, a Vigenère cipher was computationally
secure, in that nobody knew how to break it.

> knowing that codes are missing does an attacker no good unless he
> knows which codes are missing, and if the only way to determine which
> codes are missing is by trying all 2^N possible inputs to see what is
> *not* missing then, for sufficiently large N, the computation may be
> infeasible.

I see no reason to believe the first part.  Cryptography is littered
with cases where something general was known to be true but specifics
were unknown and it was used as a point of attack nevertheless.

*If* the only way to determine which codes are missing is exhaustive
search, yes, it's infeasible.  I see no particular reason to think
that's so.  Indeed, it is almost certainly not so; we just don't know
of any significantly better way at present.

>> The security of bits drawn from an properly-designed entropy pool
>> depends on much weaker assumptions than the security of bits
>> produced by a PRNG (when the PRNG seed is smaller than the number of
>> bits produced).
> You keep saying the bit in parentheses, but I'm pretty sure that's
> wrong.

Assuming, in both cases, that the input contains as much information as
its bit count allows:

I'm saying that a PRNG - or any other determinstic computation - that
generates more bits of output than it's fed as input cannot output more
information than it was given; the output cannot contain as much
information as its bit count seems to imply.

I am not saying that a PRNG, even a CSPRNG, that _isn't_ drawn on for
more bits than it's keyed with _will_ contain as much information in
its output as the bit count allows.

I think the latter is what you are saying is wrong.  (If so, I agree.)

> A cryptographic function where an 'N' bit output was as random as the
> 'N' bit input would not be a cryptographic function,

What is a "cryptographic function", here?  It's not a phrase I
recognize as a technical term.

/~\ The ASCII                             Mouse
\ / Ribbon Campaign
 X  Against HTML      
/ \ Email!           7D C8 61 52 5D E7 2D 39  4E F1 31 3E E8 B3 27 4B

Home | Main Index | Thread Index | Old Index