Date: Sat, 15 Sep 2012 11:09:17 +0100 From: Ben Laurie <benl@freebsd.org> To: Mark Murray <mark@grondar.org>, Mark Murray <markm@freebsd.org> Cc: Arthur Mesh <arthurmesh@gmail.com>, Ian Lepore <freebsd@damnhippie.dyndns.org>, Doug Barton <dougb@freebsd.org>, freebsd-security@freebsd.org, RW <rwmaillists@googlemail.com>, "Bjoern A. Zeeb" <bz@freebsd.org> Subject: Re: svn commit: r239569 - head/etc/rc.d Message-ID: <CAG5KPzzFO1H5Wcx34oXi09=aJqg5w%2BXWSd8fnn0Byvpy_8%2B-rA@mail.gmail.com> In-Reply-To: <E1TCdlD-000C1N-4g@groundzero.grondar.org> References: <50453686.9090100@FreeBSD.org> <20120911082309.GD72584@dragon.NUXI.org> <504F0687.7020309@FreeBSD.org> <201209121628.18088.jhb@freebsd.org> <5050F477.8060409@FreeBSD.org> <20120912213141.GI14077@x96.org> <20120913052431.GA15052@dragon.NUXI.org> <alpine.BSF.2.00.1209131258210.13080@ai.fobar.qr> <alpine.BSF.2.00.1209141336170.13080@ai.fobar.qr> <E1TCXN0-000NFT-7I@groundzero.grondar.org> <CAG5KPzwOdCkybj3D5uic1KC-pwW-pewgsrqrXg60f5SJjtzYPw@mail.gmail.com> <E1TCbDG-0002Hz-9D@groundzero.grondar.org> <CAG5KPzzRxzVX-%2B9fYjRdqjY-wScbM6AA7GYtLmktgMG0Zg8iyQ@mail.gmail.com> <E1TCbSz-0007CJ-BI@groundzero.grondar.org> <CAG5KPzyJNmXRfxtPPrdc2zVCsxGtDfJT79YC3a1PNUfOOSzt8A@mail.gmail.com> <E1TCcIq-000Brr-Ex@groundzero.grondar.org> <CAG5KPzwEESg7iUb2%2B-kAN%2Bk55M95BZjh5VaSvxzSsSCVuZ9kMw@mail.gmail.com> <E1TCdlD-000C1N-4g@groundzero.grondar.org>
next in thread | previous in thread | raw e-mail | index | archive | help
On Fri, Sep 14, 2012 at 10:49 PM, Mark Murray <mark@grondar.org> wrote: > Ben Laurie writes: >> > My proposed solution is intended so address, if not solve that >> > problem, by preventing file writes from filling up the harvest >> > queue. Yarrow already has pretty good data hashing; there is no >> > point in duplicating that. >> >> Fine: then when the queue fills, run the Yarrow algorithm. > > I can certainly trigger a reseed at will, but allowing external writes > to overwhelm the system by doing a > > $ cat /dev/zero > /dev/random > > ... just ain't gonna happen. No, sir. Let's just quantify the risk here: essentially the problem is that if I feed something with no entropy into the pool and that is allowed to trigger a reseed, then you end up hashing what existing entropy you have with the no-entropy input, leading to a loss of entropy. The theoretical loss for a perfect hash function is log_2(N)log_2(1/e), where N is the number of iterations. log_2(1/e) is ~.66. So, to reduce the entropy from, say, 256 bits, if SHA-1 is used, to 128 bits, takes ~2^(128/.66) reseeds - that is, ~2^193. Around 10^58. So, you're right, it ain't gonna happen, even if you allow an attacker to reseed as often as he wants :-) Switching from SHA-256 to SHA-384 would get all that entropy back, too (if it exists in the first place, of course). We can do the sums for less extreme examples, of course. Let's say we think that the loss of even 32 bits is a problem, then that's still around 10^15 reseeds - and you have to get < 32 bits of entropy from other sources in the time taken to do those reseeds. At one reseed per clock (clearly impossible), that's over a day on a 3 GHz machine... >> If not, then whatever you run instead must also be sound. XOR isn't. > > You have a way to go before you convince me on this one. I'll buy this > argument if it is a routine/regular/risky ocurrence that the output > of (say) > > $ ( ps -gauxwww ; netstat -arn ; sysctl -ao ) | gzip | ... > > ... can be demonstrated to have insignificant entropy when harvested > using my proposed method. BTW - you may want to actually see the method. I do want to see the method :-) My point here is that you don't have full control of the inputs to /dev/random, so assuming that they take some particular form seems like a mistake to me - the aim, I would hope, would be to extract available entropy from whatever inputs you get, regardless of quality. So, the argument against xor is that it is possible for a careless/naive person to shoot themselves in the foot, and it would be nice to avoid that - it seems unkind to assume that everyone who wants to help the PRNG is going to be knowledgeable about its inner workings. >> > Note that I have already agreed that external preconditioning of >> > the data is a good idea; I like the idea of compression and some >> > external hashing (but not the speed of these duting boot). >> >> I don't, because you can't rely on it. That is, I'm not against it, >> but we can't rely on it. > > You have to rely on something; Yarrow needs some entropy to cold-start, > and on a freshly installed OS, this is rocking-horse shit. This is > where BIG problems start because it is at this time that (eg) SSH keys > are built. We make some effort to get the user to "kayboard bash", but > experience has shown that annoyed users screw up, and annoyed engineers > are often worse. > > On a properly shut-down box this is better-controlled as entropy can be > cached for restart. > > What we have works; but for reasons discussed is imperfect. Proposed > fixes make it better. Perfection will always be asyptotically > unattainable. > > M > -- > Mark R V Murray > Pi: 132511160 >
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?CAG5KPzzFO1H5Wcx34oXi09=aJqg5w%2BXWSd8fnn0Byvpy_8%2B-rA>