Date: Sat, 26 Aug 2000 18:49:56 -0500 From: Adam Back <adam@cypherspace.org> To: mark@grondar.za Cc: current@freebsd.org, kris@freebsd.org, jeroen@vangelderen.org Subject: Re: yarrow & /dev/random Message-ID: <200008262349.SAA06044@cypherspace.org> In-Reply-To: <200008262035.e7QKZsp26706@grimreaper.grondar.za> (message from Mark Murray on Sat, 26 Aug 2000 22:35:54 %2B0200)
next in thread | previous in thread | raw e-mail | index | archive | help
Mark writes: > [...] > 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". OK, I agree that that's an area where yarrow offers better protection. But it's not like Ted's code is broken or anything. We would break things using /dev/random by switching as is to yarrow, so this is why I don't like it: we're trying to improve things (Yarrows protection aginst the attacks you describe), but in order to do this we're doing some other damage. We should at least do no damage: we're improving one thing and breaking something else. > > 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? Well consider the behavior of the BF-CBC-256 construct as a block cipher. If we encrypt: X1 = (x1 || x2 || x3 || x4) where |x| is blowfish block size (64 bits) and |X1| is BF-CBC-256 pseudo-blocksize (256 bits). The encryption of X1 and X1' = (x1 || x2 || x3 || x4') are going to be the same in all blocks except the last: Y1 = (y1||y2||y3||y4) = E( X1 ) Y1' = (y1||y2||y3||y4') = E( X1' ) a block cipher would be considered broken if it exhibited that behavior. I don't immediately see how to transfer that to weakening the Davies-Meyer hash built using it -- but it certainly violates the stated requirements for the strength of the underlying block cipher. Probably you can do some kind of 2^64 work factor precomputation attack something. Bear in mind anything significantly short of 2^256 operations allowing you to compute hash collisions is going to be considered a break, and that gives quite a lot of scope for precomputation against CBC on a smaller block cipher given the hash output size. > > > ...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 distiller needs looking at -- it seems to be a bit hazy due to the unknown spread of correlations between input samples, but even if you presume god's distiller, getting outputs via the yarrow output function is going to destroy any hopes of getting information theoretic security. > > 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. Well you leave most of yarrow alone, you just add the ability to reserve de-skewing function outputs for /dev/random. /dev/urandom still goes through the normal yarrow output function. > > 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. I agree, we need the peer review. > > 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. Unattended servers are a problem alright. One thing you can do is if your server has any private keys -- and it generally will have if it's doing crypto -- is mix the private key into the random pool along with the curren time. As the attacker doesn't know your private key (if he does it's game over anyway), you get a /dev/urandom which is secure. (If you don't like the `feel' of putting your private key into /dev/urandom as a sample, run it through a one-way hash function first). The other thing you can do is mix in encrypted IVs people connecting to your server send you -- for example SSL, SSH, and PGP and so on tend to do this. It can't hurt because you're only mixing, and you can't destroy entropy with a good mixing function; and if you presume the collection of people who connect to you aren't colluding it helps. (If there is only one person communicating with you, it doesn't matter anyway, because they have their own plaintext.) We should encourage people to do these two things. Adam 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?200008262349.SAA06044>