Date: Wed, 26 Jul 2000 12:19:39 +0200 From: Mark Murray <mark@grondar.za> To: Kris Kennaway <kris@FreeBSD.org> Cc: arch@FreeBSD.org Subject: Re: Estimating entropy Message-ID: <200007261019.MAA00605@grimreaper.grondar.za> In-Reply-To: <Pine.BSF.4.21.0007252346200.58758-100000@freefall.freebsd.org> ; from Kris Kennaway <kris@FreeBSD.org> "Tue, 25 Jul 2000 23:57:53 MST." References: <Pine.BSF.4.21.0007252346200.58758-100000@freefall.freebsd.org>
next in thread | previous in thread | raw e-mail | index | archive | help
> 1) gzip them and use the resulting compressed size * a multiplier (e.g. > 0.5) to estimate the entropy. Computationally expensive, but easy to do; the compressed data is also a half-decent way of getting the stuff into the pools, as it adds a layer of hashing/mixing. > 2) Keep a frequency table and calculate or estimate the shannon entropy > periodically. This may be feasible if we treat the samples as 8-bit > sources, as you only have to loop over 256 values and calculate a log_2 of > the probabilities (although lack of FP in the kernel would complicate > this) I have been looking for articles on Shannon entropy; all I can find is a theorem that covers ergodic systems. Do you have any online references? > However, the following paper looks interesting - I didnt read it in detail > yet, but it may also be suitable. > > http://www.geocities.com/SiliconValley/Code/4704/universal.pdf Thanks! > It seems that any online (low-cost) estimation function is going to be > easy to fool by feeding it low-entropy inputs designed to pass the tests. > This is likely only a problem for entropy samples obtained from userland, > if we were to allow untrusted processes to submit entropy which is given a > non-zero weight. On the other hand, if we only allow "trusted" root > processes to submit entropy with a non-zero weight then it should be okay. Sane. We need to "disconnect" as much of the entropy harvesting from the attacker as possible. The harvesting needs to use internal state where it can (that's why I want to hook namei()). Syscons is an exception; and I'd like to fix that (syscons can be "attacked" by (say) holding down a key). > > Any thoughts? > > Kris > > -- > In God we Trust -- all others must submit an X.509 certificate. > -- Charles Forsythe <forsythe@alum.mit.edu> > > -- Mark Murray Join the anti-SPAM movement: http://www.cauce.org To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-arch" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?200007261019.MAA00605>