lkml.org 
[lkml]   [2002]   [Aug]   [18]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
Patch in this message
/
Date
From
SubjectRe: [PATCH] (0/4) Entropy accounting fixes
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/
\
 
 \ /
  Last update: 2005-03-22 13:28    [W:0.107 / U:3.940 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site