Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id ; Sun, 18 Aug 2002 13:27:48 -0400 Received: (majordomo@vger.kernel.org) by vger.kernel.org id ; Sun, 18 Aug 2002 13:27:48 -0400 Received: from waste.org ([209.173.204.2]:3232 "EHLO waste.org") by vger.kernel.org with ESMTP id ; Sun, 18 Aug 2002 13:27:46 -0400 Date: Sun, 18 Aug 2002 12:31:40 -0500 From: Oliver Xymoron To: Linus Torvalds Cc: linux-kernel Subject: Re: [PATCH] (0/4) Entropy accounting fixes Message-ID: <20020818173140.GU21643@waste.org> References: <20020818052417.GL21643@waste.org> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.3.28i Sender: linux-kernel-owner@vger.kernel.org X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 4658 Lines: 125 On Sun, Aug 18, 2002 at 09:59:41AM -0700, Linus Torvalds wrote: > > On Sun, 18 Aug 2002, Oliver Xymoron wrote: > > > > The key word is actually conservative, as in conservative estimate. > > Conservative here means less than or equal to. > > Your argument is that even with a gigahz logic analyzer on the network > line, you should certainly see randomness that is worth considering. > > I dare you to actually show perfect correlation from it: the interrupt may > be synchronized to the PCI clock, but the code executed there-after > certainly will not. And even if the machine is 100% idle, and the whole > working set fits in the L1 cache, the DMA generated by the packet itself > will result in cache invalidations. > > In other words, in order for you to actually be able to predict the TSC > from the outside, you'd have to not just have the gigahz logic analyzer on > the network line, you' dalso have to be able to correlate the ethernet > heartbeat to the PCI clock (which you probably could do by looking at the > timing of the reply packets from a ping flood, although it would be > "interestng" to say the least and probably depends on how the network card > generates the ethernet clock), _and_ you'd have to be able to do a cache > eviction analysis (which in turn requires knowing the initial memory > layout for the kernel data structures for networking). Yes, obviously 'nontrivial'. But then so are sideband attacks on smart cards. > And your argument that there is zero randomness in the TSC _depends_ on > your ability to perfectly estimate what the TSC is. If you cannot do it, > there is obviously at least one bit of randomness there. So I don't think > your "zero" is a good conservative estimate. Have you seen my compromise patch yet? I think this (or something like it) should make us both happy. diff -ur a/drivers/char/random.c b/drivers/char/random.c --- a/drivers/char/random.c 2002-08-17 20:54:02.000000000 -0500 +++ b/drivers/char/random.c 2002-08-18 01:38:58.000000000 -0500 @@ -724,6 +724,7 @@ */ static int benford[16]={0,0,0,1,2,3,4,5,5,6,7,7,8,9,9,10}; static int last_ctxt=0; +static int trust_break=50, trust_pct=0, trust_min=0, trust_max=100; void add_timing_entropy(void *src, unsigned datum) { @@ -764,6 +765,18 @@ delta>>=es->shift; bits=benford[int_log2_16bits(delta & 0xffff)]; } + + /* Throw in an untrusted bit as entropy trust_pct% of the time */ + if(trust_pct && !bits) + { + trust_break+=trust_pct; + if(trust_break>=100) + { + bits=1; + trust_break-=100; + } + } + batch_entropy_store(datum^time, bits); } @@ -1779,6 +1792,10 @@ {RANDOM_UUID, "uuid", NULL, 16, 0444, NULL, &proc_do_uuid, &uuid_strategy}, + {RANDOM_TRUST_PCT, "trust_pct", + &trust_pct, sizeof(int), 0644, NULL, + &proc_dointvec_minmax, &sysctl_intvec, 0, + &trust_min, &trust_max}, {0} }; diff -ur a/include/linux/sysctl.h b/include/linux/sysctl.h --- a/include/linux/sysctl.h 2002-08-17 00:30:00.000000000 -0500 +++ b/include/linux/sysctl.h 2002-08-18 01:37:54.000000000 -0500 @@ -182,7 +182,8 @@ RANDOM_READ_THRESH=3, RANDOM_WRITE_THRESH=4, RANDOM_BOOT_ID=5, - RANDOM_UUID=6 + RANDOM_UUID=6, + RANDOM_TRUST_PCT=7 }; /* /proc/sys/bus/isa */ > > [ Side note: the most common source of pseudo-random numbers is the old > linear congruental generator, which really is a sampling of a "beat" > between two frequencies that are supposed to be "close", but prime. > > That's a fairly simple and accepted pseudo-random generator _despite_ > the fact that the two frequencies are totally known, and there is zero > noise inserted. I'll bet you'll see a _very_ hard-to-predict stream from > something like the PCI clock / CPU clock thing, with noise inserted > thanks to things like cache misses and shared bus interactions. Never > mind the _real_ noise of having a work-load. ] In practically all modern machines, the CPU clock is driven off the same source as the PCI clock, the northbus clock, and every other clock used in the core. > > No, it says /dev/random is primarily useful for generating large > > (>>160 bit) keys. > > Which is exactly what something like sshd would want to use for generating > keys for the machine, right? That is _the_ primary reason to use > /dev/random. Sshd doesn't generate large keys, ssh-keygen does. -- "Love the dolphins," she advised him. "Write by W.A.S.T.E.." - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/