From owner-freebsd-arch Tue Jul 25 23:57:56 2000 Delivered-To: freebsd-arch@freebsd.org Received: from freefall.freebsd.org (freefall.FreeBSD.ORG [204.216.27.21]) by hub.freebsd.org (Postfix) with ESMTP id 7EA6E37BDE6; Tue, 25 Jul 2000 23:57:54 -0700 (PDT) (envelope-from kris@FreeBSD.org) Received: from localhost (kris@localhost) by freefall.freebsd.org (8.9.3/8.9.2) with ESMTP id XAA61784; Tue, 25 Jul 2000 23:57:54 -0700 (PDT) (envelope-from kris@FreeBSD.org) X-Authentication-Warning: freefall.freebsd.org: kris owned process doing -bs Date: Tue, 25 Jul 2000 23:57:53 -0700 (PDT) From: Kris Kennaway To: "Jeroen C. van Gelderen" , markm@freebsd.org Cc: arch@freebsd.org Subject: Estimating entropy In-Reply-To: Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: owner-freebsd-arch@FreeBSD.ORG Precedence: bulk X-Loop: FreeBSD.ORG 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 To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-arch" in the body of the message