Date: Tue, 25 Jul 2000 23:57:53 -0700 (PDT) From: Kris Kennaway <kris@FreeBSD.org> To: "Jeroen C. van Gelderen" <jeroen@vangelderen.org>, markm@freebsd.org Cc: arch@freebsd.org Subject: Estimating entropy Message-ID: <Pine.BSF.4.21.0007252346200.58758-100000@freefall.freebsd.org> In-Reply-To: <Pine.BSF.4.21.0007252338370.58758-100000@freefall.freebsd.org>
next in thread | previous in thread | raw e-mail | index | archive | help
I've been looking for some good entropy estimation algorithms which are suitable for running "online", i.e. at runtime to estimate the content of a set of samples. I haven't had much success so far - the only two things I can think of are to keep a pool of the last n samples from a source, and then either: 1) gzip them and use the resulting compressed size * a multiplier (e.g. 0.5) to estimate the entropy. 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) 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 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. Any thoughts? Kris -- In God we Trust -- all others must submit an X.509 certificate. -- Charles Forsythe <forsythe@alum.mit.edu> 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?Pine.BSF.4.21.0007252346200.58758-100000>