From owner-freebsd-current Sat Aug 26 13:35:36 2000 Delivered-To: freebsd-current@freebsd.org Received: from smtp02.iafrica.com (smtp02.iafrica.com [196.7.0.140]) by hub.freebsd.org (Postfix) with ESMTP id 3365E37B422; Sat, 26 Aug 2000 13:35:23 -0700 (PDT) Received: from [196.7.18.138] (helo=grimreaper.grondar.za ident=root) by smtp02.iafrica.com with esmtp (Exim 1.92 #1) id 13SmfW-000MeD-00; Sat, 26 Aug 2000 22:35:10 +0200 Received: from grimreaper.grondar.za (mark@localhost [127.0.0.1]) by grimreaper.grondar.za (8.11.0/8.11.0) with ESMTP id e7QKZsp26706; Sat, 26 Aug 2000 22:35:54 +0200 (SAST) (envelope-from mark@grimreaper.grondar.za) Message-Id: <200008262035.e7QKZsp26706@grimreaper.grondar.za> To: Adam Back Cc: current@freebsd.org, kris@freebsd.org, jeroen@vangelderen.org Subject: Re: yarrow & /dev/random References: <200008262032.PAA05849@cypherspace.org> In-Reply-To: <200008262032.PAA05849@cypherspace.org> ; from Adam Back "Sat, 26 Aug 2000 15:32:38 EST." Date: Sat, 26 Aug 2000 22:35:54 +0200 From: Mark Murray Sender: owner-freebsd-current@FreeBSD.ORG Precedence: bulk X-Loop: FreeBSD.ORG > > OK; what then? The existing MD5 based system is very attackable, and > > protects itself very poorly. > > My argument for linux is leave it as it is, and see if we can persuade > the yarrow authors to change yarrow so it does export a /dev/random > compatible API. If that happened, I'd follow suit. > Isn't freeBSD using the same Ted T'so code? It's "good enough" IMO > that there is no rush to change it until we can preserve it's API > semantics. The linux version has been switched to SHA1, though IMO > Dobbertin's pseudo collision attack on MD5 isn't broken in any > practical way for this purpose. People are just moving away from MD5 > in case someone manages to extend this attacks as conservative design. FreeBSD is using an earlier version of T'so's code; I beiieve he improved it later, but it has no (or little) backtracking protection, and can be too easily attacked "from both sides". > > My approach to this (and this is the first time I am stating this in > > such a wide forum) is to provide another device (say /dev/srandom) for > > folk who want to do their own randomness processing. This would provide > > a structure of data including the entropy, the system nanotime and the > > source, so the user can do his own hard work when he needs to, and the > > folk simply needing a stream of "good" random numbers can do do from > > /dev/random. > > You don't want people to have work hard -- they just want to retain > the /dev/random API which works and has understood semantics. Reading random events from the kernel to stir into a pot is not too far off what I am asking folk to do; it would be better to ask them to read N bits out of /dev/random, but N bits aren't always available; we have to compromise. Raw data is a pretty "pure" compromaise. > > Sooner or later someone is going to come up with a requirement for > > M-bit randoness on Yarrow-N, where M > N. What then? > > You could use the /dev/random API if your entropy requirements are > greater than the output size of /dev/urandom (implemented with yarrow > or otherwise). With the API we could add a call to ask the device > what it's output block size is. And/or we could define a value > exported from random.h for the bit strength of /dev/urandom, though > that risks missing changes over time. Hmm. sounds like we need a way of forcing some entropy back into /dev/random, or doing things with reseeds. Lets say we have a zener noise generator and a geiger counter, but these are connected to a device that the kernel (and thus /dev/random) cannot "harvest" (like say an async line or at the end of an SSH connection), I have make the current FreeBSD accept that input (in 8-byte chunks) followed by an explicit reseed. This is not a perfect solution to anything, but a user with high entropy needs has a simple method of "pumping" the driver, and as long as he reads at the same spead as he writes, he gets his deskewing. > > I can't help broken applications, but if we provide a better API, and > > get folk to use it, that everyone wins. > > The applications aren't broken. They are using the advertised > /dev/random API, and some people are proposing to pull the rug out of > under them and effectively symlink /dev/random to /dev/urandom. I'm trying to improve, not pull the rug :-). > As they may have relied on better than /dev/urandom for security, you > may break the security of their application. This is what I'm counting on a) yarrow and b) better harvesting for. > > I fixed that and made it Davies-Meyer. > > http://people.freebsd.org/~markm/randomdev.patch > > Looks good. API comment: you might want a hash_final implemented as a > memcpy because some hashes you swap in have this phase (MD5, SHA1 mix > in the length as a last step). Also other hash APIs often don't have > an hash_init which takes the magic constants as an argument. As > you're not using any constants (and relying on 0 as the magic constant > / Davies-Meyer IV) you could remove that. Then you'd have the classic > MD5 API which would make plugging other hashes in easy. Sounds sensible. Will do. > Crypto construct-wise I don't think you can treat BF-CBC of a 256 bit > plaintext with a 256 bit key as a virtual 256 bit block cipher > operation. I suspect the result will be weaker than 256 bits because > of the internal structure of BF-CBC. I'm not sure I understand this? > If you want 256 bit hash (and it is desirable for AES) you could use > what Joeren suggested: abrest Davies-Meyer, and a 128 bit block > cipher. Or we could wait for the AES hash mode. That is doable; at the moment I only have SHA1, MD5, DES and Blowfish available in FreeBSD's kernel crypto API; I'd need a lot more evidence before I feen I can pull in any more :-) > Twofish in abrest Davies-Meyer mode is going to blow away BF-CBC-256 > pseudo 256 bit block cipher Davies-Meyer performance wise, because of > the key agility. Understood :-). See above. > > ...unless we can somehow get /dev/random to be "secure enough". > > I think we have an obligation to attempt to make it no less secure > than the current /dev/random; and of course we should try to make it > as secure as we can in general. See below for my ideas of how you > might do that. :-) I am of the opinion that a well-implemented Yarrow with lots of entropy-harvesting to back it up can be as good as a simple hash-based single-pool bit distiller. My argument is weakening, though. > The quality of the de-skewing function, conservative assumptions about > distribution of entropy across samples and conservativeness of the > entropy estimates don't help. It's the yarrow output function which > blows it. Yeah; that monotonically-increasing counter bothers me slightly. > The solution as I see it is to modify yarrow to bypass the yarrow > output function and grab raw de-skewing function output for > /dev/random output. You'd also want to do what John Kelsey was > suggesting and XOR the bypassed de-skewing function output with > /dev/urandom output as an additional safety measure. I'll look that up; It sounds like quite a departure from yarrow to me though; that makes me nervous. > But let's get this put in yarrow-160-a, rather than making our own > variant -- then we can say we are using stock yarrow, and other yarrow > users benefit. Ok - as long as "classic" yarrow has it. > > Folk who are generating OTP's for anything other than personal use > > would be insane to use anything other than custom hardware such as > > the ubiquitous geiger-counter or zener noise generator. > > Even those hardware devices have biases and rely on software > de-skewing functions. Provided we can do a good job of de-skewing, That stuff can be harvested into yarrow, sure, but... > entropy estimation and make good assumptions about entropy > distribution I see no inherent reason why we can't generate OTP > quality randomness from generic PC hardware. There is real entropy in > that mouse swirl and keyboard input. ...there may not be a suitable monkey at the keyboard. What about a server in an unattended colo? MHO - hardware RNG. M -- Mark Murray Join the anti-SPAM movement: http://www.cauce.org To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-current" in the body of the message