Date: Thu, 26 Oct 2000 19:05:15 +0000 (GMT) From: Terry Lambert <tlambert@primenet.com> To: kris@citusc.usc.edu (Kris Kennaway) Cc: ache@nagual.pp.ru (Andrej Cernov), tlambert@primenet.com (Terry Lambert), imp@village.org (Warner Losh), current@FreeBSD.ORG, markm@FreeBSD.ORG Subject: Re: entropy reseeding is totally broken Message-ID: <200010261905.MAA03050@usr08.primenet.com> In-Reply-To: <20001026022122.C69282@citusc17.usc.edu> from "Kris Kennaway" at Oct 26, 2000 02:21:22 AM
next in thread | previous in thread | raw e-mail | index | archive | help
> > It is because /dev/random totally ignore _time_ and not reseed from it, > > but no other randomness source available at boot time. > > We should probably be using the time since boot as ONE thing we seed > with, but it only provides maybe 3-4 bits of randomness - meaning if > thats all you seed with then your attacker has to brute-force 3-4 bits > of state to break the PRNG state as it was at boot time, hardly a > difficult challenge :-) The actual time would probably be more useful than the time since boot. I still have a problem with what I see as a fundamental weakness in storing "randomness" across reboots. Logically, given a sufficiently large amount of time between a crash and the subsequent reboot, one could predict the random state, and attack immediately after a reboot... just like one could guess the fortune now, following a reboot. The state save in the shutdown -- besides not working unless you hopping on one leg, pat your head, and rub your tummy while singinging "Danny Boy" (or the moral equivalent of not being allowed to crash or use the "halt" or "reboot" commands) -- seems to me to be an inherent security flaw. Matt's points about compromise, number of random bits, as well as the amount of time it's OK to take, are also salient. Bottom line: any algorithm predicated only on saved state and based on predictable progression over a large period of time in which a compromise may be effected, is a problem. Jordan's points are good ones as well. I think that if /dev/random can be shown to be a solid foundation, it could be a keystone in an overall security strategy that can then be used to build large, sturdy, secure, edifices. But _unless_ it's shown to be a solid foundation, using it as a keystone is going to turn everything else into a house of cards, where if you compromise /dev/random, then you have a skeleton key to everything. I'm not too worried about people seeing fortunes before their time... they could always look at the fortunes.dat file anyway. But the implication in randomness used elsewhere in the system is nowhere so obvious when it is broken as when getting the same fortune each time you boot. Perhaps it's time to draft a "big gun"? Someone who knows enough about number theory to know that multiplying two random numbers together results in less randomness, not more? Or perhaps it's time to use a "tried but true" algorithm, like the 48 bit linear congruential algorithm, with a polynomial preterbation based on the current time at the time of reseeding, until the random ducks get (not) in a row? Pseudorandom seeding with a hidden key has got to be better than anything that opens a computation window for as long as your system is down after a crash... after all, we _are_ talking about security through obscurity (of the next number in a pseudorandom sequence), here. Nothing wrong with finding a handy giant, and standing on its shoulders... it's a time honored scientific tradition. I'm not really volunteering here, since I'm just an applied mathematician, and only ever got off on theory as it applied to real problems in physics and computer science and elsewhere. I just know enough to know that it'd be dangerous to trust me to do the job 100% correctly. 8-). But I also see this as getting more important as /dev/random gets more and more central to security and authentication policy and enforcement. Terry Lambert terry@lambert.org --- Any opinions in this posting are my own and not those of my present or previous employers. To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-current" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?200010261905.MAA03050>