randomness // how important is it 'really', if it's not *absolutely* random ?

Robert J. Hansen rjh at sixdemonbag.org
Wed Jan 28 21:50:38 CET 2009


vedaal at hush.com wrote:
> if the randomness collected for generation of a gnupg session key, 
> isn't *absolutely* random, then it may introduce a bias whereby the 
> session key space can be theoretically be able to be attacked by a 
> 'better-than-brute-force' method, by selectively concentrating on 
> the possibilities the bias in in favor of

Sure.  John von Neumann, one of the Grand Old Men of computer science,
once said something to the effect of "anyone producing random numbers by
algorithmic means is, of course, living in sin."  (Which is also why I
used the "living in sin" wording a couple of posts ago; it was an homage
to von Neumann.)

The interesting questions are then, (a) how do we do it, (b) what
constraints are put on it, (c) how many resources it will take, and (d)
if there's anyone smart enough to figure out (a) through (c).

> how much of a threat is this really,

Somewhere between "not at all" and "run for the hills."  Wish I could
give a more precise answer than that.

The pace of mathematical and technological development is not linear.
It's a series of plateaus and enormous jumps.  E.g., for a long time
SHA-1 was one of the strongest hashes out there, up until some
researchers from Shengdong University blew us all away.  Plateau, and jump.

It is possible that tomorrow someone will discover an attack against the
Merkle-Damgard construction and all the hashes in GnuPG will become
vulnerable.  And it's just as possible that we'll be in a plateau for
the next ten years.  It's impossible to say with any certainty.

> is there any practical way of exploiting this 'less-than-absolute' 
> randomness

Not that we know of.  Yet.  Maybe tomorrow, maybe in ten years.





More information about the Gnupg-users mailing list