Re: randomdev entropy gathering is really weak

2000-08-02 Thread Peter Jeremy

On Sun, Jul 30, 2000 at 01:25:18AM -0400, Jeroen C. van Gelderen wrote:
Hmm, maybe the complainers should provide proof that they do 
need more than 2^256 complexity. Makes it easier for us,
proponents ;-/

How about creating one-time pads?

That said, in Applied Cryptography, Schneier makes the comment (end of
section 7.1) that, based on thermodynamic limitations, "brute force
attacks against 256-bit keys will be infeasible until computers are
build from something other than matter and occupy something other than
space".  (Though it's possible that a quantum computer would meet
those criteria - since it doesn't need to iterate through all possible
keys, it can bypass that part of the second law of thermodynamics).

This implies that if brute force is the best attack against Yarrow-256
(Blowfish), it is unbreakable.  (Of course, that's a big if).

Peter


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-31 Thread Mark Murray

 On Sun, 30 Jul 2000, Mark Murray wrote:
 
  This is a reversion to the count-entropy-and-block model which I have
  been fiercely resisting (and which argument I thought I had sucessfully
  defended).
 
 Actually, I was waiting for your reply to Jeroen's question about changing
 the semantics of the random devices.

Oops; I thought I got that one.

ISTR something about looking for different algorithms that may do it,
and you pointed me at 2 sites; one had no write-up, and I'm looking at
the other.

M
--
Mark Murray
Join the anti-SPAM movement: http://www.cauce.org


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-30 Thread Mark Murray

 Content-Disposition: attachment; filename="yarrow_blocking.patch"

Brian:

I want to take a different approach to this one.

Do not commit anything to the /dev/random device, please, without running
it by me.

M
--
Mark Murray
Join the anti-SPAM movement: http://www.cauce.org


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-30 Thread Brian Fundakowski Feldman

On Sun, 30 Jul 2000, Mark Murray wrote:

  Content-Disposition: attachment; filename="yarrow_blocking.patch"
 
 Brian:
 
 I want to take a different approach to this one.
 
 Do not commit anything to the /dev/random device, please, without running
 it by me.

I was not planning on it.  You really should take a look at the bugfixes,
though; reading buffer sizes of 8 bytes but not-8-byte-multiple should
do it.  There's also the ioctl handler which you need stubs for and then
checking for open devices when you attempt to unload the module.

 M
 --
 Mark Murray
 Join the anti-SPAM movement: http://www.cauce.org

--
 Brian Fundakowski Feldman   \  FreeBSD: The Power to Serve!  /
 [EMAIL PROTECTED]`--'



To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-30 Thread Brian Fundakowski Feldman

On Sun, 30 Jul 2000, Mark Murray wrote:

 This is a reversion to the count-entropy-and-block model which I have
 been fiercely resisting (and which argument I thought I had sucessfully
 defended).
 
 My solution is to get the entropy gathering at a high enough rate that
 this is not necessary.

How does entropy gathering at a high enough rate solve this
particularly?  Unless you wait for reseeds while reading, it simply
doesn't matter how much entropy is being gathered at the time since
reading any amount just doesn't give you a new key.  Indeed, if you
can get enough entropy that the blocking in read would be very short,
you would still need to block in read to give it time to use the
entropy.

The only alternative I can see that you might be thinking of would be
that the user would be encouraged to only read a small amount at a
time and reading more soon later in the assumption that Yarrow will be
rekeyed.  Then this would be just forcing the user to do the blocking
manually, and non-deterministically.

So how exactly _would_ just having a high entropy gathering rate help
the case that you need a large amount of data from /dev/random with
true entropic value, not only 256 bits worth?  It's not like reseeds
would be occurring while reads were in progress; reads are too fast
for that and are splsofttq() protected, anyway.

 I also agreed to _maybe_ look at a re-engineer of the "old" code in a
 secure way if a decent algorithm could be found (I am reading some
 papers about this ATM).
 
 M
 --
 Mark Murray
 Join the anti-SPAM movement: http://www.cauce.org

--
 Brian Fundakowski Feldman   \  FreeBSD: The Power to Serve!  /
 [EMAIL PROTECTED]`--'



To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-30 Thread Mark Murray

  Do not commit anything to the /dev/random device, please, without running
  it by me.
 
 I was not planning on it.  You really should take a look at the bugfixes,
 though; reading buffer sizes of 8 bytes but not-8-byte-multiple should
 do it.  There's also the ioctl handler which you need stubs for and then
 checking for open devices when you attempt to unload the module.

Will do, thanks!

M
--
Mark Murray
Join the anti-SPAM movement: http://www.cauce.org


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-30 Thread Mark Murray

 How does entropy gathering at a high enough rate solve this
 particularly?

EG, by having it such that Yarrow state perturbations happen often
enough that each read is "guaranteed" to be associated with at least
one and preferably more.

M
--
Mark Murray
Join the anti-SPAM movement: http://www.cauce.org


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-30 Thread Brian Fundakowski Feldman

On Sun, 30 Jul 2000, Mark Murray wrote:

  How does entropy gathering at a high enough rate solve this
  particularly?
 
 EG, by having it such that Yarrow state perturbations happen often
 enough that each read is "guaranteed" to be associated with at least
 one and preferably more.

Can you give me an idea how this would work, at least with e.g.
pseudocode annotation of the current code?  I'm curious what you're
going to change that will allow reseeeding while a read is in
progress.

 M
 --
 Mark Murray
 Join the anti-SPAM movement: http://www.cauce.org

--
 Brian Fundakowski Feldman   \  FreeBSD: The Power to Serve!  /
 [EMAIL PROTECTED]`--'



To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-30 Thread Mark Murray

  EG, by having it such that Yarrow state perturbations happen often
  enough that each read is "guaranteed" to be associated with at least
  one and preferably more.
 
 Can you give me an idea how this would work, at least with e.g.
 pseudocode annotation of the current code?  I'm curious what you're
 going to change that will allow reseeeding while a read is in
 progress.

I didn't say "reseed", I said "perturb". Same code, (improved reseed
control), more harvesting calls.

M
--
Mark Murray
Join the anti-SPAM movement: http://www.cauce.org


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-30 Thread Kris Kennaway

On Sun, 30 Jul 2000, Mark Murray wrote:

 This is a reversion to the count-entropy-and-block model which I have
 been fiercely resisting (and which argument I thought I had sucessfully
 defended).

Actually, I was waiting for your reply to Jeroen's question about changing
the semantics of the random devices.

I still maintain that as OS developers we can't predict the uses of this
tool and that some users may require new entropy in every 256-bit output.
I don't think that "near enough is good enough" is a valid excuse :-)

Kris

--
In God we Trust -- all others must submit an X.509 certificate.
-- Charles Forsythe [EMAIL PROTECTED]



To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-29 Thread Brian Fundakowski Feldman

On Mon, 24 Jul 2000, Jeroen C. van Gelderen wrote:

   What I meant with that point is that the user may get, say an extra few
   hundred bits out of it with no new entropy before the scheduled reseed
   task kicks in.
  
  How does he know which bits are which? His analysis task just got a whole
  lot more difficult.
 
 Again, not entirely correct but not relevant either...
 
 Kris is simply right in that the /dev/random semantics change 
 and that more bits can be output by Yarrow than there is entropy 
 gathered. *In theory* the complexity of an attack on our Yarrow 
 has an upper bound of 2^256 and *in theory* this is less than 
 the complexity of an attack on our current /dev/random. This is 
 a hard fact, no way around that.

Even if the attack on a single non-blocking read from Yarrow is only
of 2^256 complexity, it is designed to be much more expensive than
just cracking a single block cipher.  Blowfish has a very large keying
step, and Yarrow is designed to exploit having large keying steps and
then adding more complexity in its setup in addition.  This makes it
infeasible to mount attacks on Yarrow, and the security is really not
as weak as just cracking 20-round Blowfish-256.

However, none of this makes Yarrow useless for getting many bits of
high-quality random data for, e.g., generation of an RSA key.

 However, the big question here is not about theory but about
 *practicality*. Is Yarrow less secure than /dev/random in 
 practice? How does our /dev/random hold up under attack? How 
 does Yarrow compare? I think we need to evaluate these practical
 questions instead of deep theoretical issues as Yarrow is all 
 about practicality.
 
 At a more fundamental level we will need to answer the question:
 "Do we need to preserve the current /dev/random semantics or 
 can we decide to change 'em? [1]". And how will this affect our
 applications *in practice*.

Mark already stated that in *practicality*, Yarrow-BF-cbc-256 1.0
(I guess that's the proper name for this :-) is complex enough and
generates good enough ouput.  If you /really/ want to make the attack
on it much harder, how about this: if you're going to read 1024 bits
of entropy from Yarrow on /dev/random, you will request it all at once
and block just as the old random(4) used to block; the blocking can
occur at 256 bit intervals and sleep until there is a reseed.  Waiting
to reseed for each read will ensure a much larger amount of "real"
entropy than it "maybe" happening at random times.

Can you really find anything wrong with doing what I propose *in
practice*?  I'm certain that it would make it about as hard to
brute-force the key while knowing certain parameters of its generation
as it would be to just factor the damned 1024-bit number.  I've
already implemented this as well as some other bugfixes, so see the
attached diff.

 So let's concentrate this discussion on the practical issues
 and explain why you think backing /dev/random with Yarrow and
 changing the semantics is justifyable or even a good thing.
 
 Cheers,
 Jeroen
 
 [1] And, should we decide not to change /dev/random semantics,
 can we still back /dev/random with a modified Yarrow? 

I think it makes sense :)

 -- 
 Jeroen C. van Gelderen  o  _ _ _
 [EMAIL PROTECTED]  _o /\_   _ \\o  (_)\__/o  (_)
   _ \_   _(_) (_)/_\_| \   _|/' \/
  (_)(_) (_)(_)   (_)(_)'  _\o_

--
 Brian Fundakowski Feldman   \  FreeBSD: The Power to Serve!  /
 [EMAIL PROTECTED]`--'


Index: sys/sys/random.h
===
RCS file: /usr2/ncvs/src/sys/sys/random.h,v
retrieving revision 1.25
diff -u -r1.25 random.h
--- sys/sys/random.h2000/07/25 21:18:45 1.25
+++ sys/sys/random.h2000/07/29 23:19:20
@@ -36,6 +36,8 @@
 enum esource { RANDOM_WRITE, RANDOM_KEYBOARD, RANDOM_MOUSE, RANDOM_NET, \
ENTROPYSOURCE };
 void random_harvest(void *, u_int, u_int, u_int, enum esource);
+void set_wakeup(int *, int);
+void set_wakeup_exit(int *, int, int);
 
 #endif
 
Index: sys/dev/randomdev/harvest.c
===
RCS file: /usr2/ncvs/src/sys/dev/randomdev/harvest.c,v
retrieving revision 1.4
diff -u -r1.4 harvest.c
--- sys/dev/randomdev/harvest.c 2000/07/25 21:18:46 1.4
+++ sys/dev/randomdev/harvest.c 2000/07/29 23:18:50
@@ -30,6 +30,7 @@
 #include sys/systm.h
 #include sys/types.h
 #include sys/queue.h
+#include sys/kthread.h
 #include sys/linker.h
 #include sys/libkern.h
 #include sys/mbuf.h
@@ -72,4 +73,23 @@
nanotime(timebuf);
(*reap)(timebuf, entropy, count, bits, frac, origin);
}
+}
+
+/*
+ * Helper routines to let kthread_exit() do its stuff properly (i.e. no crash).
+ */
+void
+set_wakeup(int *var, int value)
+{
+
+   *var = value;
+   

Re: randomdev entropy gathering is really weak

2000-07-29 Thread Jeroen C. van Gelderen

Brian Fundakowski Feldman wrote:
 
 On Mon, 24 Jul 2000, Jeroen C. van Gelderen wrote:
 
What I meant with that point is that the user may get, say an extra few
hundred bits out of it with no new entropy before the scheduled reseed
task kicks in.
  
   How does he know which bits are which? His analysis task just got a whole
   lot more difficult.
 
  Again, not entirely correct but not relevant either...
 
  Kris is simply right in that the /dev/random semantics change
  and that more bits can be output by Yarrow than there is entropy
  gathered. *In theory* the complexity of an attack on our Yarrow
  has an upper bound of 2^256 and *in theory* this is less than
  the complexity of an attack on our current /dev/random. This is
  a hard fact, no way around that.
 
 Even if the attack on a single non-blocking read from Yarrow is only
 of 2^256 complexity, it is designed to be much more expensive than
 just cracking a single block cipher.  Blowfish has a very large keying
 
 step, and Yarrow is designed to exploit having large keying steps and
 then adding more complexity in its setup in addition.  This makes it
 infeasible to mount attacks on Yarrow, and the security is really not
 as weak as just cracking 20-round Blowfish-256.

Actually, it is. The low key agility doesn't add anything in
terms of practical security because it only affects brute
force attacks and can be optimized out in a pipelined 
implementation. Expensive, yes, but can be done. There is
some more details on this in the Yarrow paper I think...

Anyway, not that is matters, Yarrow was designed to be as 
secure as the underlying blockcipher and Blowfish is 
generally considered to be reasonably secure.

So, the security still is 2^256 maximum, no way around that.

 However, none of this makes Yarrow useless for getting many bits of
 high-quality random data for, e.g., generation of an RSA key.

Well, you will need to back that up with arguments if you want
to convince the more sceptical (not me). A mere statement will 
not do it, you need proof or at least arguments :-)

The question that Kris posed basically boiled down to: "Does 2^256 
complexity equal 2^x (x  256) complexity in practice?" . I can't
think of a practical system where it wouldn't be sufficient in 
practice but that's just me. Well, you seem to agree and MarkM
seems to too.

Hmm, maybe the complainers should provide proof that they do 
need more than 2^256 complexity. Makes it easier for us,
proponents ;-/

Also, since a 1024 RSA-key only has ~2^77 complexity it isn't a 
very good example. A more interesting question is, what if you 
generate a couple of 256-bit symmetric keys in a row. Their
total complexity is 2^256 which is less than they could have.
Does that matter in practice?

 Mark already stated that in *practicality*, Yarrow-BF-cbc-256 1.0
 (I guess that's the proper name for this :-) 

According to Bruce S. one would call it 
  Yarrow-256 (implementation details go here)
You would definately spell out Blowfish completely.

Btw, how exactly is the hash actually constructed in our Yarrow?
I wonder how one constructs a 256-bit hash out of Blowfish with
a 64-bit block size. A quick explanation would be appreciated.

 is complex enough and
 generates good enough ouput.  If you /really/ want to make the attack
 on it much harder, how about this: if you're going to read 1024 bits
 of entropy from Yarrow on /dev/random, you will request it all at once
 and block just as the old random(4) used to block; the blocking can
 occur at 256 bit intervals and sleep until there is a reseed.  Waiting
 to reseed for each read will ensure a much larger amount of "real"
 entropy than it "maybe" happening at random times.

Sounds like a good idea. It looks like it would be reasonably
easy to then add an extra entropy counter to the pool from which
you subtract the number of bits that are output and to which you
add the number of entropy bits that are mixed in.

You can then extract bytes until that counter hits 0 and then block 
until it goes positive again which would ensure that the entropy
output trough /dev/random is not re-used for output trough
/dev/urandom. This would not affect the security of Yarrow at all
but preserve the semantics of /dev/random almost completely.

 Can you really find anything wrong with doing what I propose *in
 practice*?  

No. Although I think you can make it nearly perfect by 
incorporating the above suggestion. You would then *never* 
return more bits than you have gathered entropy and you 
would never use those entropy bits twice. 

 I've
 already implemented this as well as some other bugfixes, so see the
 attached diff.

Cool.

  [1] And, should we decide not to change /dev/random semantics,
  can we still back /dev/random with a modified Yarrow?
 
 I think it makes sense :)

Me too, especially with your changes (or modification thereof)
to preserve current /dev/random semantics.

Cheers,
Jeroen
-- 
Jeroen C. van Gelderen  

Re: randomdev entropy gathering is really weak

2000-07-26 Thread void

How does OpenBSD handle this issue?  Anyone know?
-- 
 Ben

220 go.ahead.make.my.day ESMTP Postfix


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-26 Thread Kris Kennaway

On Wed, 26 Jul 2000, void wrote:

 How does OpenBSD handle this issue?  Anyone know?

It looks like they have four different kernel-exported random-number
generators:

#define RND_RND 0   /* real randomness like nuclear chips */
#define RND_SRND1   /* strong random source */
#define RND_URND2   /* less strong random source */
#define RND_PRND3   /* pseudo random source */
#define RND_ARND4   /* aRC4 based random number generator */

RND_RND is not implemented.

/dev/random (RND_SRND) and /dev/urandom (RND_URND) are very similar to our
old system (based on the same code, in fact, and also used in Linux)
although OpenBSD use more entropy sources than us.

/dev/prandom (RND_PRND): This just returns the output of random() (Why
bother?)

/dev/arandom (RND_ARND): This uses the arc4 stream cipher to output a
stream of bytes based on an internal key, which is periodically (but I
don't know how often) reseeded using entropy samples. Much like
arc4random(), except it's periodically reseeded (which arc4random()
doesn't do, by default).

All of these systems have weaknesses (some serious), even if entropy is
estimated accurately (there were indications it was not, for our old
PRNG). That was the main motivation for moving to a cryptographically
well-designed system (Yarrow).

Kris

--
In God we Trust -- all others must submit an X.509 certificate.
-- Charles Forsythe [EMAIL PROTECTED]



To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-24 Thread Mark Murray

 http://www.counterpane.com/pseudorandom_number.html
 
 Cryptlib is described here:
 
 http://www.cs.auckland.ac.nz/~pgut001/cryptlib/

Thanks!

  Asynchonous reseeding _improves_ the situation; the attacker cannot force
  it to any degree of accuracy, and if he has the odds stacked heavily against
  him that each 256-bits of output will have an associated reseed, it makes
  his job pretty damn difficult.
 
 What I meant with that point is that the user may get, say an extra few
 hundred bits out of it with no new entropy before the scheduled reseed
 task kicks in.

How does he know which bits are which? His analysis task just got a whole
lot more difficult.

M
--
Mark Murray
Join the anti-SPAM movement: http://www.cauce.org


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-24 Thread Stefan `Sec` Zehl

On Sun, Jul 23, 2000 at 03:06:34PM +0200, Poul-Henning Kamp wrote:
 In message [EMAIL PROTECTED], Stefan `Sec` Zehl writes:
 With the current approach it has a 256bits key. This is, in my eyes, not
 good. Although yarrow is nice, It's suited for any kind of key
 generation.
 
 The first law of crypto clearly states: "Know what you're doing".
 
 There is no way around that law.
 
 We cannot load down FreeBSD with impossibly heavy computations to
 cater for any and all conceiveable application of random numbers.

But FreeBSD should provide a way to get truely random numbers when it
asks for them. /dev/random was invented so the applications don't have
to bother with entropy-gathering. I agree that yarrow is good, but we
need some way to get really random numbers. Maybe call it /dev/rrandom.
The way Kris describes it, it won't really use cpu time until it is
read. 

CU,
Sec
-- 
 I even remember having a private exchange of messages with you about other
 possible approaches to that problem. :-)
Hopefully, these approaches involved slowly crushing of tender body parts.
-- Liviu  Wietse about broken Mailers
~


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-24 Thread Kris Kennaway

On Mon, 24 Jul 2000, Jeroen C. van Gelderen wrote:

 1. The overhead will probably be insignificant. One doesn't
use such vast amounts of random numbers.

True, but the effect on slow CPUs for a single read may be signfificant.
We'll have to see.

 2. At least the generator gate can be optimized out if it 
turns out to be a problem.

Yes.

 3. We could use a cipher with better key agility (CAST)
to make each operation less computationally intensive.

Yes.

  ITYM Pg = k 2^(-k/3)
  though - you want a maximum k bits of output, not 1. 
 
 Pg is the number of blocks IIRC.

Pg is the number of (n=64)-bit blocks between generator gates, but
min(2^n,2^(k/3)Pg) is the maximum number of output bits you'll get before
the thing shuts up and waits for a reseed. So Pg  1 means we'll take a
generator gate after every output block, but will still output our
2^(k/3)Pg = k bits (i.e. 4 blocks worth)

In practice we'd probably have to just special-case this since the
required Pg is approximately 10^-24 :-)

Kris

--
In God we Trust -- all others must submit an X.509 certificate.
-- Charles Forsythe [EMAIL PROTECTED]



To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-24 Thread Jeroen C. van Gelderen

Mark Murray wrote:
[...]
   Asynchonous reseeding _improves_ the situation; the attacker cannot force
   it to any degree of accuracy, and if he has the odds stacked heavily against
   him that each 256-bits of output will have an associated reseed, it makes
   his job pretty damn difficult.

This is not correct for a variety of reasons. But that's all 
fairly theoretical and ... not relevant for the discussion at 
hand.

  What I meant with that point is that the user may get, say an extra few
  hundred bits out of it with no new entropy before the scheduled reseed
  task kicks in.
 
 How does he know which bits are which? His analysis task just got a whole
 lot more difficult.

Again, not entirely correct but not relevant either...

Kris is simply right in that the /dev/random semantics change 
and that more bits can be output by Yarrow than there is entropy 
gathered. *In theory* the complexity of an attack on our Yarrow 
has an upper bound of 2^256 and *in theory* this is less than 
the complexity of an attack on our current /dev/random. This is 
a hard fact, no way around that.

However, the big question here is not about theory but about
*practicality*. Is Yarrow less secure than /dev/random in 
practice? How does our /dev/random hold up under attack? How 
does Yarrow compare? I think we need to evaluate these practical
questions instead of deep theoretical issues as Yarrow is all 
about practicality.

At a more fundamental level we will need to answer the question:
"Do we need to preserve the current /dev/random semantics or 
can we decide to change 'em? [1]". And how will this affect our
applications *in practice*.

So let's concentrate this discussion on the practical issues
and explain why you think backing /dev/random with Yarrow and
changing the semantics is justifyable or even a good thing.

Cheers,
Jeroen

[1] And, should we decide not to change /dev/random semantics,
can we still back /dev/random with a modified Yarrow? 
-- 
Jeroen C. van Gelderen  o  _ _ _
[EMAIL PROTECTED]  _o /\_   _ \\o  (_)\__/o  (_)
  _ \_   _(_) (_)/_\_| \   _|/' \/
 (_)(_) (_)(_)   (_)(_)'  _\o_


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



RE: randomdev entropy gathering is really weak

2000-07-23 Thread David Schwartz


  /dev/random should block if the system does not contain as much
 real entropy
  as the reader desires. Otherwise, the PRNG implementation will be the
  weakest link for people who have deliberately selected higher levels of
  protection from cryptographic attack.

 I don't want to rehash this thread from the beginning. Please go
 back, read the Yarrow paper, and recognise that Yarrow is not an
 entropy-counter, it is a cryptographically secure PRNG. The "count
 random bits and block" model does not apply.

Then the current implementation cannot provide the usual semantics for
/dev/random, while it can provide the semantics for /dev/urandom. As I
understand it, /dev/random is supposed to provide true randomness suitable
for generating keys of unlimited length, whereas /dev/urandom is supposed to
provide cryptographically-strong randomness for general applications.

If people want /dev/random to seed 1024-bit keys, /dev/random must be
stronger than a 1024-bit key.

DS



To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-23 Thread Mark Murray

 On Sat, 22 Jul 2000, Mark Murray wrote:
 
   So what it if I want/need 257 bits? :-)
  
  Read them. You'll get them. If you want higher quality randomness than
  Yarrow gives, read more than once. Do other stuff; play. Don't get stuck
  in the "I have exhausted the randomness pool" loop; Yarrow does not play
  that game.
 
 I think you're missing the point. The only way I can get a random number
 with more than n bits of entropy out of Yarrow-n is if I sample either
 side of a reseed operation, which in general comes down to timing
 guesswork and having to make assumptions about the PRNG implementation.

I understand that. :-)

Your are missing the point that it is not possible to get more than
the ${number-of-bits-ofrandomness} from any accumulator or PRNG. You
have to draw the line somewhere; The current implementation has it
at 256.

 If you want to generate a cryptographic key of length n bits then you
 really want n bits of entropy in the random source you're deriving it
 from, otherwise your key is actually much weaker than advertised because
 it's easier for the attacker to attack the state of the PRNG that derived
 it than to attack the key itself.

Aha! That is where Yarrow wins. The paper argues it much better than
me: Section 4.1, the paragraph that begins "Yarrow takes a different
approach...".

  We currently have Yarrow-256(Blowfish); wanna make it Yarrow-1024? I could
  make it so.
 
 Well, if we did that then how about generating 2048-bit keys? :-)

Where do you draw the line? I could make it Yarrow-N, only to have
someone insist on $((N+1)) in the very next breath.

With what we have, I am staking my career on the "uncrackability"
of Blowfish-256. If that holds then Yarrow is safe. (The old one
was MD5, with all its weaknesses such as birthday attacks, and
blocking added to compensate for folk raping it for internal state;
this blocking was compromised by the non-blocking /dev/urandom. The
design was too simple. The current design has multiple accumulators,
dual pools, and cryptographically overseen reseed mechanism; on top
of that, the output is encrypted in its own right, so there is added
protection against folk guessing the internal state.).

M
--
Mark Murray
Join the anti-SPAM movement: http://www.cauce.org


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-23 Thread Mark Murray

 The core of my complaint is that even though our old PRNG did crappy
 entropy handling, we used to have such a method, which is now gone. I'd
 like to see yarrow hang off /dev/urandom and have /dev/random tap directly
 into the entropy pool (perhaps a third pool separate from Yarrow's
 fast/slow) so I can generate my large keys safely.

By your own admission, the old system was bad; yet you still want
${it}? You'd like to see a programmer with less experience than
Schneier come up with a more secure algorithm than him?

M
--
Mark Murray
Join the anti-SPAM movement: http://www.cauce.org


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-23 Thread Mark Murray

 The core of my complaint is that even though our old PRNG did crappy
 entropy handling, we used to have such a method, which is now gone. I'd
 like to see yarrow hang off /dev/urandom and have /dev/random tap directly
 into the entropy pool (perhaps a third pool separate from Yarrow's
 fast/slow) so I can generate my large keys safely.

By your own admission, the old system was bad; yet you still want
${it}? You'd like to see a programmer with less experience than
Schneier come up with a more secure algorithm than him?

M
--
Mark Murray
Join the anti-SPAM movement: http://www.cauce.org


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-23 Thread Mark Murray

 Okay, using RSA keys wasn't the best example to pick, but Yarrow also
 seems easy to misuse in other cases: for example if you want to generate
 multiple 256-bit symmetric keys (or other random data) at the same time,
 each additional key after the first won't contain any additional entropy,
 so if you break the state of the PRNG at the time the first one was
 generated you get the others for free (until the thing reseeds).
 
 This design tradeoff is discussed in section 4.1 of the paper.

Tweakable.

  That said, there is nothing to prevent the system admin 
  from tweaking the Yarrow security parameters so that 
  Yarrow will only spit out as many bits or pseudo-randomness 
  as it gathers bits of entropy.[4]
 
 Well, I don't see a way to tune this without modifying the Yarrow design,
 since the entropy pool is intentionally decoupled from the output
 mechanism, and it seems like it would add additional (unnecessary)
 overhead anyway to use it in that fashion.

Look at the sysctls (some improvements and documentation coming).

 Indications are we can probably get quite a lot of usable entropy from a
 standard system (on the order of many kilobytes per second - but I need to
 read more of the literature about processing of entropy samples) - in this
 case I think maintaining a third pool which is directly tapped by
 /dev/random, and leaving Yarrow sitting behind /dev/urandom is the way to
 go.

I suspect you are missing the whole point of yarrow. Yarrow protects
you from the compromises inherent in attackers injecting their own
junk into the "third pool".

M
--
Mark Murray
Join the anti-SPAM movement: http://www.cauce.org


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-23 Thread Kris Kennaway

On Sun, 23 Jul 2000, Mark Murray wrote:

 Your are missing the point that it is not possible to get more than
 the ${number-of-bits-ofrandomness} from any accumulator or PRNG. You
 have to draw the line somewhere; The current implementation has it
 at 256.

Uhh..a PRNG which hashes entropy samples with e.g. SHA1 and outputs the
digest once the bucket is "full" will have 1-epsilon bit of entropy per
1 bit of output. It may not be very fast depending on the rate of entropy
accumulation, but you can get as much entropy out of it as you want.

This is basically the model I am advocating for /dev/random. It's also the
alternative "basic design philosophy" described in the yarrow paper.

  If you want to generate a cryptographic key of length n bits then you
  really want n bits of entropy in the random source you're deriving it
  from, otherwise your key is actually much weaker than advertised because
  it's easier for the attacker to attack the state of the PRNG that derived
  it than to attack the key itself.
 
 Aha! That is where Yarrow wins. The paper argues it much better than
 me: Section 4.1, the paragraph that begins "Yarrow takes a different
 approach...".

See "important issue" number 2 on p6. Yarrow-derived numbers are only
"good for" 256 bits of strength. Modulo reseeds, Yarrow never accumulates
more than 256 bits of entropy. Therefore you are silly to use it for
applications which require more than 256 bits of randomness.

 Where do you draw the line? I could make it Yarrow-N, only to have
 someone insist on $((N+1)) in the very next breath.

Precisely, which is why /dev/random shouldn't use Yarrow, or any other
seeded-cipher PRNG.

 With what we have, I am staking my career on the "uncrackability"
 of Blowfish-256. If that holds then Yarrow is safe. (The old one

I'm not bothered about this. My point is that, by design, Yarrow is not
suitable as a replacement for /dev/random (/dev/urandom, yes).

Kris

--
In God we Trust -- all others must submit an X.509 certificate.
-- Charles Forsythe [EMAIL PROTECTED]



To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-23 Thread Kris Kennaway

On Sun, 23 Jul 2000, Mark Murray wrote:

 By your own admission, the old system was bad; yet you still want
 ${it}? You'd like to see a programmer with less experience than
 Schneier come up with a more secure algorithm than him?

The old implementation was bad. The class of algorithm is not, as long as
you are conservative about your entropy estimates.

Kris

--
In God we Trust -- all others must submit an X.509 certificate.
-- Charles Forsythe [EMAIL PROTECTED]



To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-23 Thread Kris Kennaway

On Sun, 23 Jul 2000, Mark Murray wrote:

  Okay, using RSA keys wasn't the best example to pick, but Yarrow also
  seems easy to misuse in other cases: for example if you want to generate
  multiple 256-bit symmetric keys (or other random data) at the same time,
  each additional key after the first won't contain any additional entropy,
  so if you break the state of the PRNG at the time the first one was
  generated you get the others for free (until the thing reseeds).
  
  This design tradeoff is discussed in section 4.1 of the paper.
 
 Tweakable.

Doing a reseed operation with every output is going to be *very*
computationally expensive.

   That said, there is nothing to prevent the system admin 
   from tweaking the Yarrow security parameters so that 
   Yarrow will only spit out as many bits or pseudo-randomness 
   as it gathers bits of entropy.[4]
  
  Well, I don't see a way to tune this without modifying the Yarrow design,
  since the entropy pool is intentionally decoupled from the output
  mechanism, and it seems like it would add additional (unnecessary)
  overhead anyway to use it in that fashion.
 
 Look at the sysctls (some improvements and documentation coming).

Please tell me which of the following sysctls will cause Yarrow to
deactivate the keyed cipher feature that spits out a constant data stream
independent of the state of the entropy pools:

kern.random.yarrow.gengateinterval: 10
kern.random.yarrow.bins: 10
kern.random.yarrow.fastthresh: 100
kern.random.yarrow.slowthresh: 160
kern.random.yarrow.slowoverthresh: 2

  Indications are we can probably get quite a lot of usable entropy from a
  standard system (on the order of many kilobytes per second - but I need to
  read more of the literature about processing of entropy samples) - in this
  case I think maintaining a third pool which is directly tapped by
  /dev/random, and leaving Yarrow sitting behind /dev/urandom is the way to
  go.
 
 I suspect you are missing the whole point of yarrow. Yarrow protects
 you from the compromises inherent in attackers injecting their own
 junk into the "third pool".

Mark, I understand this stuff quite well - I'm not "missing the whole
point of Yarrow" at all. Yarrow is a good system as far as it goes, but
the authors themselves admit this limitation - you just can't use this
tool in contexts it was not designed for.

Kris

--
In God we Trust -- all others must submit an X.509 certificate.
-- Charles Forsythe [EMAIL PROTECTED]



To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-23 Thread Poul-Henning Kamp

In message [EMAIL PROTECTED], Kri
s Kennaway writes:
On Sat, 22 Jul 2000, Jeroen C. van Gelderen wrote:

 I agree that you need long RSA keys ... but the real 
 discussion isn't really about key length but rather about 
 the overall complexity of attacking the key:

Okay, using RSA keys wasn't the best example to pick, but Yarrow also
seems easy to misuse in other cases: for example if you want to generate
multiple 256-bit symmetric keys (or other random data) at the same time,

Kris,

Obviously, if you need more randomness than a stock FreeBSD system
can provide you with, you add hardware to give you more randomness.

In other words, and more bluntly:  Please shut up now, will you ?

--
Poul-Henning Kamp   | UNIX since Zilog Zeus 3.20
[EMAIL PROTECTED] | TCP/IP since RFC 956
FreeBSD coreteam member | BSD since 4.3-tahoe
Never attribute to malice what can adequately be explained by incompetence.


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-23 Thread Mark Murray

 This is basically the model I am advocating for /dev/random. It's also the
 alternative "basic design philosophy" described in the yarrow paper.

Erm, read 4.1 again :-). The paragraph that begins "One approach..." is
the old approach. It is also the approach that you are advocating.

The next paragraph "Yarrow takes..." is Yarrow, and the current
implementation.

 See "important issue" number 2 on p6. Yarrow-derived numbers are only
 "good for" 256 bits of strength. Modulo reseeds, Yarrow never accumulates
 more than 256 bits of entropy. Therefore you are silly to use it for
 applications which require more than 256 bits of randomness.
 
  Where do you draw the line? I could make it Yarrow-N, only to have
  someone insist on $((N+1)) in the very next breath.
 
 Precisely, which is why /dev/random shouldn't use Yarrow, or any other
 seeded-cipher PRNG.

It should not use the old method, which is attackable for many
reasons that Schneier makes clear. (Effectively a 128 bit hash with
a reseed ("stir") every read. Can you spell "Iterative attack"? :-) ).

Where does that leave us?

How good were our old numbers? How many users have I screwed by implementing
that system?

How do we fix it? What accumulation algorithm do we use that does not
clue the reader into what the internal state is?

  With what we have, I am staking my career on the "uncrackability"
  of Blowfish-256. If that holds then Yarrow is safe. (The old one
 
 I'm not bothered about this. My point is that, by design, Yarrow is not
 suitable as a replacement for /dev/random (/dev/urandom, yes).

_My_ point is that the old system is broken, and that IMO Yarrow is a
good replacement. (I support my point by noting that Schneier is a far
better cryptographer than I, and he designed the algorithm that I
implemented).

M
--
Mark Murray
Join the anti-SPAM movement: http://www.cauce.org


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-23 Thread Kris Kennaway

On Sun, 23 Jul 2000, Poul-Henning Kamp wrote:

 Obviously, if you need more randomness than a stock FreeBSD system
 can provide you with, you add hardware to give you more randomness.

This won't help if it's fed through Yarrow.

 In other words, and more bluntly:  Please shut up now, will you ?

No. There are legitimate technical issues to be resolved here. If you
don't want to participate, press 'D' and move on with your life.

Kris

--
In God we Trust -- all others must submit an X.509 certificate.
-- Charles Forsythe [EMAIL PROTECTED]



To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-23 Thread Kris Kennaway

On Sun, 23 Jul 2000, Mark Murray wrote:

 Erm, read 4.1 again :-). The paragraph that begins "One approach..." is
 the old approach. It is also the approach that you are advocating.
 
 The next paragraph "Yarrow takes..." is Yarrow, and the current
 implementation.

"The strength of the first approach is that, if properly designed, it is
possible to get unconditional security from the PRNG."

This is a good thing :-)

 It should not use the old method, which is attackable for many
 reasons that Schneier makes clear. (Effectively a 128 bit hash with
 a reseed ("stir") every read. Can you spell "Iterative attack"? :-) ).
 
 Where does that leave us?
 
 How good were our old numbers? How many users have I screwed by
 implementing that system?

Please understand that this is not a personal attack - I appreciate your
work, and welcome it in FreeBSD. My concern is with what Yarrow does not
do, but which FreeBSD needs: a PRNG which is capable of generating
arbitrarily large keys.

 How do we fix it? What accumulation algorithm do we use that does not
 clue the reader into what the internal state is?

I suggest we ask Bruce Schneier instead of bantering back and forth about
the issue. I claim (supported by the quote above) that it's possible to
implement such a system securely and have it co-exist with Yarrow.

 _My_ point is that the old system is broken, and that IMO Yarrow is a
 good replacement. (I support my point by noting that Schneier is a far
 better cryptographer than I, and he designed the algorithm that I
 implemented).

Yarrow is a good replacement for /dev/urandom. However it doesn't provide
features which I believe are necessary, namely the ability to generate
high-entropy keys of arbitrary size, without severely impacting on PRNG
performance by constantly reseeding.

Kris

--
In God we Trust -- all others must submit an X.509 certificate.
-- Charles Forsythe [EMAIL PROTECTED]



To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-23 Thread Poul-Henning Kamp

In message [EMAIL PROTECTED], Kri
s Kennaway writes:
On Sun, 23 Jul 2000, Poul-Henning Kamp wrote:

 Obviously, if you need more randomness than a stock FreeBSD system
 can provide you with, you add hardware to give you more randomness.

This won't help if it's fed through Yarrow.

Nobody has said anything about forcing you to use Yarrow, have they ?

 In other words, and more bluntly:  Please shut up now, will you ?

No. There are legitimate technical issues to be resolved here. If you
don't want to participate, press 'D' and move on with your life.

I think the general concensus is that all legitimate technical
issues has been resolved and that we are stuck with a small band
of merry men wasting bandwidth by repeatedly rehashing the obvious:
"Any source of random bits has a finite capacity and you should
not exceed that capacity."


I have not seen any new information in the last N emails from you.

--
Poul-Henning Kamp   | UNIX since Zilog Zeus 3.20
[EMAIL PROTECTED] | TCP/IP since RFC 956
FreeBSD coreteam member | BSD since 4.3-tahoe
Never attribute to malice what can adequately be explained by incompetence.


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-23 Thread Mark Murray

   Obviously, if you need more randomness than a stock FreeBSD system
   can provide you with, you add hardware to give you more randomness.
  
  This won't help if it's fed through Yarrow.
 
 *BTTT!* Wrong. A good hardware RNG when fed at a high-enough rate
 through Yarrow can easily produce a continuous stream of what you need.
 (If we take that route, the current implementation may need to be tweaked
 a bit to stop reseeding after a period of unuse to avoid hammering the
 kernel too much; this needs careful thought).

Been thinking about this; the current implemnetation runs continuously
(thanks to taskqueue(9)). There is no reason that it couldn't be made
(somewhat) use-driven, so that it works harder at harvesting when being
used heavily. This may make it slower, but it would hurt the kernel a
bit less when not in use.

M
--
Mark Murray
Join the anti-SPAM movement: http://www.cauce.org


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-23 Thread Mark Murray

 On Sun, 23 Jul 2000, Poul-Henning Kamp wrote:
 
  Obviously, if you need more randomness than a stock FreeBSD system
  can provide you with, you add hardware to give you more randomness.
 
 This won't help if it's fed through Yarrow.

*BTTT!* Wrong. A good hardware RNG when fed at a high-enough rate
through Yarrow can easily produce a continuous stream of what you need.
(If we take that route, the current implementation may need to be tweaked
a bit to stop reseeding after a period of unuse to avoid hammering the
kernel too much; this needs careful thought).

M
--
Mark Murray
Join the anti-SPAM movement: http://www.cauce.org


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-23 Thread Mark Murray

   This design tradeoff is discussed in section 4.1 of the paper.
 
  Tweakable.

 Doing a reseed operation with every output is going to be *very*
 computationally expensive.

Tradeoff. What do you want? Lightning fast? Excessive security? Balance
it out.

   Well, I don't see a way to tune this without modifying the Yarrow
   design, since the entropy pool is intentionally decoupled from
   the output mechanism, and it seems like it would add additional
   (unnecessary) overhead anyway to use it in that fashion.
 
  Look at the sysctls (some improvements and documentation coming).

 Please tell me which of the following sysctls will cause Yarrow to
 deactivate the keyed cipher feature that spits out a constant data
 stream independent of the state of the entropy pools:

 kern.random.yarrow.gengateinterval: 10 kern.random.yarrow.bins: 10
 kern.random.yarrow.fastthresh: 100 kern.random.yarrow.slowthresh: 160
 kern.random.yarrow.slowoverthresh: 2

None, but very paranoid reseed intervals can be set if
required. (Requires more entropy-harvesting, but doable).

  I suspect you are missing the whole point of yarrow. Yarrow protects
  you from the compromises inherent in attackers injecting their own
  junk into the "third pool".

 Mark, I understand this stuff quite well - I'm not "missing the whole
 point of Yarrow" at all.

The acknowlegment that I am looking for is that the old, simple "gather
entropy, stir with hash, serve" model is inadequate IMO, and I have not
seen any alternatives.

  Yarrow is a good system as far as it goes,
 but the authors themselves admit this limitation - you just can't use
 this tool in contexts it was not designed for.

Goes for any tool; a universal truth. I'm trying to come up with a
better tool that what was, and I believe that I have, and I am perhaps
misunderstanding folks' motives in shouting for the blocking model. In
quite a few cases, it has been a very obvious non-understanding of what
Yarrow is (I apologise for lumping you in this category).

I'll relent somewhat if a secure entropy distilling algorithm could be
found; one which stands up to crypanalysis.

Will you relent a step or two if I can get the entropy harvesting _rate_
high enough? :-)

M
--
Mark Murray
Join the anti-SPAM movement: http://www.cauce.org


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-23 Thread Kris Kennaway

On Sun, 23 Jul 2000, Mark Murray wrote:

This design tradeoff is discussed in section 4.1 of the paper.
  
   Tweakable.
 
  Doing a reseed operation with every output is going to be *very*
  computationally expensive.
 
 Tradeoff. What do you want? Lightning fast? Excessive security? Balance
 it out.

Thinking about it further, I dont think Yarrow can even do this (introduce
entropy into every output value) without bypassing the block cipher. And
if you reseed with every 256 bits of output then you're vulnerable to an
iterative guessing attack because the fast pool won't have much in it. So
if we want to use the Yarrow "backend" we'd have to basically reduce it to
the system I describe below.

 The acknowlegment that I am looking for is that the old, simple "gather
 entropy, stir with hash, serve" model is inadequate IMO, and I have not
 seen any alternatives.

There are two other models which rate "pretty well-designed" in the Yarrow
paper: the cryptlib and PGP PRNGs. I don't know what their properties are
right now (the cryptlib one is described in the paper on PRNG
cryptanalysis).

 I'll relent somewhat if a secure entropy distilling algorithm could be
 found; one which stands up to crypanalysis.

Well, a simple scheme which doesn't seem to suffer from any of the
vulnerabilities discussed in the schneier papers is to accumulate entropy
in a pool, and only return output when the pool is full. i.e. the PRNG
would either block or return 0 bytes of data, or a full pool's worth.

 Will you relent a step or two if I can get the entropy harvesting _rate_
 high enough? :-)

If we get the entropy pools filling fast enough that the reseed is
triggering close to every 256 bits of output then it becomes much less of
a concern (but it's still there, because reseeding happens asynchronously
with respect to PRNG output). However I think that in practice this will
be too heavy on the CPU (unless we weaken the reseed operation) and make
dd if=/dev/urandom of=/dev/null a very effective local user DoS :-(

Kris

--
In God we Trust -- all others must submit an X.509 certificate.
-- Charles Forsythe [EMAIL PROTECTED]






To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-23 Thread Mark Murray

  The acknowlegment that I am looking for is that the old, simple "gather
  entropy, stir with hash, serve" model is inadequate IMO, and I have not
  seen any alternatives.
 
 There are two other models which rate "pretty well-designed" in the Yarrow
 paper: the cryptlib and PGP PRNGs. I don't know what their properties are
 right now (the cryptlib one is described in the paper on PRNG
 cryptanalysis).

Do you have copies of the articles concerned? I'd surely appreciate
a photocopy of the relevant pages if you don't mind! :-)

  I'll relent somewhat if a secure entropy distilling algorithm could be
  found; one which stands up to crypanalysis.
 
 Well, a simple scheme which doesn't seem to suffer from any of the
 vulnerabilities discussed in the schneier papers is to accumulate entropy
 in a pool, and only return output when the pool is full. i.e. the PRNG
 would either block or return 0 bytes of data, or a full pool's worth.

Hmm. Timing attacks? Known-input attacks?

  Will you relent a step or two if I can get the entropy harvesting _rate_
  high enough? :-)
 
 If we get the entropy pools filling fast enough that the reseed is
 triggering close to every 256 bits of output then it becomes much less of
 a concern (but it's still there, because reseeding happens asynchronously
 with respect to PRNG output). However I think that in practice this will
 be too heavy on the CPU (unless we weaken the reseed operation) and make
 dd if=/dev/urandom of=/dev/null a very effective local user DoS :-(

The dd if=/dev/urandom of=/dev/null is _already_ a doozy of a dos. Likewise
a fork-bomb, a /tmp-filler, likewise a whole bunch of things much worse.
Heck, you can hurt your system with cat /dev/zero  /dev/null.

Asynchonous reseeding _improves_ the situation; the attacker cannot force
it to any degree of accuracy, and if he has the odds stacked heavily against
him that each 256-bits of output will have an associated reseed, it makes
his job pretty damn difficult.

M
--
Mark Murray
Join the anti-SPAM movement: http://www.cauce.org


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-23 Thread Poul-Henning Kamp

In message [EMAIL PROTECTED], Stefan `Sec` Zehl writes:

Assume I want to encrypt a message by XOR'ing with randomness.

If I then exchange my keys securely, the message is uncrackable.

With the current approach it has a 256bits key. This is, in my eyes, not
good. Although yarrow is nice, It's suited for any kind of key
generation.

The first law of crypto clearly states: "Know what you're doing".

There is no way around that law.

We cannot load down FreeBSD with impossibly heavy computations to
cater for any and all conceiveable application of random numbers.

In particular I fear that the current implementation already has
killed battery lifetimes on laptops :-(

--
Poul-Henning Kamp   | UNIX since Zilog Zeus 3.20
[EMAIL PROTECTED] | TCP/IP since RFC 956
FreeBSD coreteam member | BSD since 4.3-tahoe
Never attribute to malice what can adequately be explained by incompetence.


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-23 Thread Jeroen C. van Gelderen

David Schwartz wrote:
 
   /dev/random should block if the system does not contain as much
  real entropy
   as the reader desires. Otherwise, the PRNG implementation will be the
   weakest link for people who have deliberately selected higher levels of
   protection from cryptographic attack.
 
  I don't want to rehash this thread from the beginning. Please go
  back, read the Yarrow paper, and recognise that Yarrow is not an
  entropy-counter, it is a cryptographically secure PRNG. The "count
  random bits and block" model does not apply.
 
 Then the current implementation cannot provide the usual semantics for
 /dev/random, while it can provide the semantics for /dev/urandom. As I
 understand it, /dev/random is supposed to provide true randomness suitable
 for generating keys of unlimited length, whereas /dev/urandom is supposed to
 provide cryptographically-strong randomness for general applications.
 
 If people want /dev/random to seed 1024-bit keys, /dev/random must be
 stronger than a 1024-bit key.

1. The current /dev/random cannot do it, it's less secure 
   than Yarrow for a variety of reasons. So we have a net
   improvement anyway. Thanks Mark.

2. Most people do not want to seed 1024-bit keys as outlined
   in another mail in this thread. If they *understand* the 
   issues involved they will realize that 2^256 complexity
   is plenty uncrackable for all practical purposes. FreeBSD 
   is about practical purposes IMHO.

3. Yarrow can be modified to just do this, should someone
   think this is neccessary. Read the paper and think of
   what happens when you set Pg to 1/(2^(k/3)). (Note that
   the paper restricts this value to 1 = Pg but that's of
   no importance here.) 
** This is overly conservative for most applications  I can
   think of; Even a multi-million dollar financial 
   transactioning system will be practically secure when Pg 
   is set to 1.

4. Nothing prevents you from adapting Yarrow so that current
   /dev/random semantics are preserved, making Yarrow even
   better. It can be done with the current design it's just
   not very beneficial to do it.

5. Yarrow was designed as a better replacement for most any
   PRNG by a couple of bright cryptographers. Can you do
   better than that?

Cheers,
Jeroen
-- 
Jeroen C. van Gelderen  o  _ _ _
[EMAIL PROTECTED]  _o /\_   _ \\o  (_)\__/o  (_)
  _ \_   _(_) (_)/_\_| \   _|/' \/
 (_)(_) (_)(_)   (_)(_)'  _\o_


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-23 Thread Jeroen C. van Gelderen

Kris Kennaway wrote:
 
 On Sun, 23 Jul 2000, Mark Murray wrote:
 
 This design tradeoff is discussed in section 4.1 of the paper.
   
Tweakable.
  
   Doing a reseed operation with every output is going to be *very*
   computationally expensive.
 
  Tradeoff. What do you want? Lightning fast? Excessive security? Balance
  it out.
 
 Thinking about it further, I dont think Yarrow can even do this (introduce
 entropy into every output value) without bypassing the block cipher. 

Why not?

 And
 if you reseed with every 256 bits of output then you're vulnerable to an
 iterative guessing attack because the fast pool won't have much in it. 

You would block until the pool is filled with entropy.

[...]
 There are two other models which rate "pretty well-designed" in the Yarrow
 paper: the cryptlib and PGP PRNGs. I don't know what their properties are
 right now (the cryptlib one is described in the paper on PRNG
 cryptanalysis).

Fortunately you don't need them :-)

  I'll relent somewhat if a secure entropy distilling algorithm could be
  found; one which stands up to crypanalysis.
 
 Well, a simple scheme which doesn't seem to suffer from any of the
 vulnerabilities discussed in the schneier papers is to accumulate entropy
 in a pool, and only return output when the pool is full. i.e. the PRNG
 would either block or return 0 bytes of data, or a full pool's worth.

And you can make Yarrow do just that. Not very practical but
you can do it. You effectively set Pg to 1/(2^(k/3)).

  Will you relent a step or two if I can get the entropy harvesting _rate_
  high enough? :-)
 
 If we get the entropy pools filling fast enough that the reseed is
 triggering close to every 256 bits of output then it becomes much less of
 a concern (but it's still there, because reseeding happens asynchronously
 with respect to PRNG output). 

Reseeds do not *have* to happen asynchronously as pointed out
above. What is of importance is that you *cannot* forcibly 
trigger a reseed without there being enough entropy in the 
pools. There is nothing against having /dev/random block
until the pools have accumulated enough entropy.

Cheers,
Jeroen
-- 
Jeroen C. van Gelderen  o  _ _ _
[EMAIL PROTECTED]  _o /\_   _ \\o  (_)\__/o  (_)
  _ \_   _(_) (_)/_\_| \   _|/' \/
 (_)(_) (_)(_)   (_)(_)'  _\o_


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



RE: randomdev entropy gathering is really weak

2000-07-23 Thread David Schwartz


 5. Yarrow was designed as a better replacement for most any
PRNG by a couple of bright cryptographers. Can you do
better than that?

Nope, I agree. Ignore my previous objections.

DS



To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-23 Thread Kris Kennaway

On Sun, 23 Jul 2000, Mark Murray wrote:

  There are two other models which rate "pretty well-designed" in the Yarrow
  paper: the cryptlib and PGP PRNGs. I don't know what their properties are
  right now (the cryptlib one is described in the paper on PRNG
  cryptanalysis).
 
 Do you have copies of the articles concerned? I'd surely appreciate
 a photocopy of the relevant pages if you don't mind! :-)

The paper I was referring to was:

http://www.counterpane.com/pseudorandom_number.html

Cryptlib is described here:

http://www.cs.auckland.ac.nz/~pgut001/cryptlib/

  Well, a simple scheme which doesn't seem to suffer from any of the
  vulnerabilities discussed in the schneier papers is to accumulate entropy
  in a pool, and only return output when the pool is full. i.e. the PRNG
  would either block or return 0 bytes of data, or a full pool's worth.
 
 Hmm. Timing attacks? Known-input attacks?

Inasmuch as the hash function has no timing attacks (data-dependent code
paths, etc) I don't see a weakness there. Chosen input attacks can be
mitigated by using a hash function which provides strong mixing (e.g.
SHA1), so there is no correlation between partially-known input and
output. Yarrow of course takes it a step further by using a very heavy
mixing function to regenerate the key, although it seems to me from the
design rationale that this is to remove correlations between the Yarrow
key before and after reseeding, which doesn't affect an unkeyed PRNG which
doesnt maintain state.

   Will you relent a step or two if I can get the entropy harvesting _rate_
   high enough? :-)
  
  If we get the entropy pools filling fast enough that the reseed is
  triggering close to every 256 bits of output then it becomes much less of
  a concern (but it's still there, because reseeding happens asynchronously
  with respect to PRNG output). However I think that in practice this will
  be too heavy on the CPU (unless we weaken the reseed operation) and make
  dd if=/dev/urandom of=/dev/null a very effective local user DoS :-(
 
 The dd if=/dev/urandom of=/dev/null is _already_ a doozy of a dos. Likewise
 a fork-bomb, a /tmp-filler, likewise a whole bunch of things much worse.
 Heck, you can hurt your system with cat /dev/zero  /dev/null.

Well, all of the others can be mitigated by resource limits. It's
something which needs to be revisited.

 Asynchonous reseeding _improves_ the situation; the attacker cannot force
 it to any degree of accuracy, and if he has the odds stacked heavily against
 him that each 256-bits of output will have an associated reseed, it makes
 his job pretty damn difficult.

What I meant with that point is that the user may get, say an extra few
hundred bits out of it with no new entropy before the scheduled reseed
task kicks in.

Kris

--
In God we Trust -- all others must submit an X.509 certificate.
-- Charles Forsythe [EMAIL PROTECTED]



To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-23 Thread Kris Kennaway

On Sun, 23 Jul 2000, Jeroen C. van Gelderen wrote:

  Well, a simple scheme which doesn't seem to suffer from any of the
  vulnerabilities discussed in the schneier papers is to accumulate entropy
  in a pool, and only return output when the pool is full. i.e. the PRNG
  would either block or return 0 bytes of data, or a full pool's worth.
 
 And you can make Yarrow do just that. Not very practical but
 you can do it. You effectively set Pg to 1/(2^(k/3)).

Oh, I missed this - thanks. It does introduce an extra overhead, namely
applying a generator gate with every output (since n  k and Pg  1) and
then the full reseed with every k bits of output. ITYM Pg = k 2^(-k/3)
though - you want a maximum k bits of output, not 1. I'm not sure if the
current implementation will let you do this (since Pg  1 here).

 Reseeds do not *have* to happen asynchronously as pointed out
 above.

Yeah, but they do in the current implementation (AFAICT).

Kris

--
In God we Trust -- all others must submit an X.509 certificate.
-- Charles Forsythe [EMAIL PROTECTED]



To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-22 Thread Mark Murray

 I'm all for storing a sample at shutdown and using it to help seed the
 PRNG at startup, but it shouldn't be the only seed used (for example, the
 case where the system has never been shut down (cleanly) before and so has
 no pre-existing seed file is a BIG corner case to consider since thats how
 the system is at the time it first generates SSH keys after a fresh
 install).

Agreed; we need more entropy sources that are available early enough to
be useful.

 It might be only an academic vulnerability, but if someone can read your
 HD during the time the system is shut down then I'd prefer them not to
 know the precise state when the system next starts up again. Yes, if they
 can read they can probably also write, but it seems like a mistake when
 there's nothing really gained by saving the complete state, as opposed to
 an extract.

Academic argument noted; with more entropy sources, this situation will
improve.

M
--
Mark Murray
Join the anti-SPAM movement: http://www.cauce.org


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-22 Thread Mark Murray

 After rereading the paper in more detail, Step 7 of the reseed algorithm
 seems not entirely consistent with this: they explicitly refer to writing
 out "the next 2k bits of output from the generator to the seed file"
 (slightly different terminology, but I couldn't find any other references
 to the "seed file")

He doesn't talk about it too much :-(.

 Another important point is that Yarrow-160 is not useful for generating
 keys 160 bits, because of Shannon's theorem and the fact that it uses
 SHA-1. You seem to be using a blowfish-based hash function with 256-bit
 keysize (do you have a reference for using blowfish in that fashion?), but
 the point stands. It seems we would need to use an alternative interface
 which either synchronously reseeds with every output to generate stronger
 random data, or just taps into the (hashed) entropy pools directly.

Lots of references: Schneier's "Applied Cryptography" talks about
using Good Hashes for crypto and Good Crypto for hashes. Schneier's
site at www.counterpane.com will give you plenty.

It is also an extension and improvement on the way OpenBSD do their
bcrypt (passwd) hash.

 This was also a problem with our /dev/urandom (by design), but not with
 /dev/random since that tapped the entropy pool directly. Incidentally, it
 also looks like a problem with OpenBSD's /dev/arandom which is a stream
 cipher (arc4 with 256-bit key) periodically reseeded.

The differnce with the old system and Yarrow is yarrow's self-recovery
property; Yarrow screens its internal state from the ouside world
very heavily, and provides enough perturbation of it from its
copious :-) entropy harvesting to keep the state safe from compromise.

Yarrow also keeps multiple (fast/slow pools + key) states, and the
long, slow interactions between those give much better protection
that the old system which was pretty much a simple PRNG+simple
random perturbations.  (I know MD5 is not "simple", but it is
deterministic, and was only used once).

M
--
Mark Murray
Join the anti-SPAM movement: http://www.cauce.org


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-22 Thread Kris Kennaway

On Sat, 22 Jul 2000, Mark Murray wrote:

 Lots of references: Schneier's "Applied Cryptography" talks about
 using Good Hashes for crypto and Good Crypto for hashes. Schneier's
 site at www.counterpane.com will give you plenty.

I havent been able to get my hands on Applied Cryptography, but I don't
recall seeing anything like this on the website. I'll check again.

 The differnce with the old system and Yarrow is yarrow's self-recovery
 property; Yarrow screens its internal state from the ouside world
 very heavily, and provides enough perturbation of it from its
 copious :-) entropy harvesting to keep the state safe from compromise.

Yeah, I know all this and agree that Yarrow makes a better /dev/urandom,
but it doesn't change the fact that Yarrow-256 is only good for 256 bits
of entropy between reseeding operations. You can pull all you want out of
it but will never get more than 256 bits until it reseeds.

Kris

--
In God we Trust -- all others must submit an X.509 certificate.
-- Charles Forsythe [EMAIL PROTECTED]




To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-22 Thread Mark Murray

  The differnce with the old system and Yarrow is yarrow's self-recovery
  property; Yarrow screens its internal state from the ouside world
  very heavily, and provides enough perturbation of it from its
  copious :-) entropy harvesting to keep the state safe from compromise.
 
 Yeah, I know all this and agree that Yarrow makes a better /dev/urandom,
 but it doesn't change the fact that Yarrow-256 is only good for 256 bits
 of entropy between reseeding operations. You can pull all you want out of
 it but will never get more than 256 bits until it reseeds.

Aaah! I understand your question better; this is the "conservation of
entropy" argument which Yarrow "breaks".

Because of Yarrow's cryptographic protection of its internal state, its
frequent reseeds and its clever geneation mechanism, this paradigm is
less important - the output is 256-bit safe (Blowfish safe) for any size
of output[*]. When you read 1000 bits, I am not selling you 1000 bits
each guaranteed random, I am selling you 1000 bits that are predictable
within the constraints of needing to crack 256-bit Blowfish.

[*] Assuming no errors on the part of the implementor (me). :-)

M
--
Mark Murray
Join the anti-SPAM movement: http://www.cauce.org


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-22 Thread Kris Kennaway

On Sat, 22 Jul 2000, Mark Murray wrote:

 Because of Yarrow's cryptographic protection of its internal state, its
 frequent reseeds and its clever geneation mechanism, this paradigm is
 less important - the output is 256-bit safe (Blowfish safe) for any size
 of output[*]. When you read 1000 bits, I am not selling you 1000 bits
 each guaranteed random, I am selling you 1000 bits that are predictable
 within the constraints of needing to crack 256-bit Blowfish.

So what it if I want/need 257 bits? :-)

Kris

--
In God we Trust -- all others must submit an X.509 certificate.
-- Charles Forsythe [EMAIL PROTECTED]



To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-22 Thread Mark Murray

 On Sat, 22 Jul 2000, Mark Murray wrote:
 
  Because of Yarrow's cryptographic protection of its internal state, its
  frequent reseeds and its clever geneation mechanism, this paradigm is
  less important - the output is 256-bit safe (Blowfish safe) for any size
  of output[*]. When you read 1000 bits, I am not selling you 1000 bits
  each guaranteed random, I am selling you 1000 bits that are predictable
  within the constraints of needing to crack 256-bit Blowfish.
 
 So what it if I want/need 257 bits? :-)

Read them. You'll get them. If you want higher quality randomness than
Yarrow gives, read more than once. Do other stuff; play. Don't get stuck
in the "I have exhausted the randomness pool" loop; Yarrow does not play
that game.

From the Yarrow paper:
``Yarrow's outputs are cryptographically derived. Systems that use Yarrow's
outputs are no more secure than the generation mechanism used.''

We currently have Yarrow-256(Blowfish); wanna make it Yarrow-1024? I could
make it so.

M
--
Mark Murray
Join the anti-SPAM movement: http://www.cauce.org


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-22 Thread Jeroen C. van Gelderen

Kris Kennaway wrote:
 
 On Sat, 22 Jul 2000, Mark Murray wrote:
 
  Lots of references: Schneier's "Applied Cryptography" talks about
  using Good Hashes for crypto and Good Crypto for hashes. Schneier's
  site at www.counterpane.com will give you plenty.
 
 I havent been able to get my hands on Applied Cryptography, but I don't
 recall seeing anything like this on the website. I'll check again.
 
  The differnce with the old system and Yarrow is yarrow's self-recovery
  property; Yarrow screens its internal state from the ouside world
  very heavily, and provides enough perturbation of it from its
  copious :-) entropy harvesting to keep the state safe from compromise.
 
 Yeah, I know all this and agree that Yarrow makes a better /dev/urandom,
 but it doesn't change the fact that Yarrow-256 is only good for 256 bits
 of entropy between reseeding operations. You can pull all you want out of
 it but will never get more than 256 bits until it reseeds.

You don't care in practice, 256 bits are unguessable.
If you do care, you load a different random module :-)

Cheers,
Jeroen
-- 
Jeroen C. van Gelderen  o  _ _ _
[EMAIL PROTECTED]  _o /\_   _ \\o  (_)\__/o  (_)
  _ \_   _(_) (_)/_\_| \   _|/' \/
 (_)(_) (_)(_)   (_)(_)'  _\o_


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-22 Thread Jeroen C. van Gelderen

Kris Kennaway wrote:
 
 On Fri, 21 Jul 2000, Mark Murray wrote:
 
  Section 2.1, last paragraph:
  "If a system is shut down, and restarted, it is desirable to store some
  high-entropy data (such as the key) in non-volatile memory. This allows
  the PRNG to be restarted in an unguessable state at the next restart. We
  call this data the reseed file."
 
 I'm all for storing a sample at shutdown and using it to help seed the
 PRNG at startup, but it shouldn't be the only seed used (for example, the
 case where the system has never been shut down (cleanly) before and so has
 no pre-existing seed file is a BIG corner case to consider since thats how
 the system is at the time it first generates SSH keys after a fresh
 install).
 
 It might be only an academic vulnerability, but if someone can read your
 HD during the time the system is shut down then I'd prefer them not to
 know the precise state when the system next starts up again. Yes, if they
 can read they can probably also write, but it seems like a mistake when
 there's nothing really gained by saving the complete state, as opposed to
 an extract.

Well, academic or not (not when you run financial transactioning
systems on FreeBSD) you can edit rc.shutdown to not write out a
seed file. You don't have to use it but it's good that it's there.

Cheers,
Jeroen
-- 
Jeroen C. van Gelderen  o  _ _ _
[EMAIL PROTECTED]  _o /\_   _ \\o  (_)\__/o  (_)
  _ \_   _(_) (_)/_\_| \   _|/' \/
 (_)(_) (_)(_)   (_)(_)'  _\o_


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-22 Thread Rodney W. Grimes

 On Fri, 21 Jul 2000, Mark Murray wrote:
 
  Section 2.1, last paragraph:
  "If a system is shut down, and restarted, it is desirable to store some
  high-entropy data (such as the key) in non-volatile memory. This allows
  the PRNG to be restarted in an unguessable state at the next restart. We
  call this data the reseed file."
 
 I'm all for storing a sample at shutdown and using it to help seed the
 PRNG at startup, but it shouldn't be the only seed used (for example, the
 case where the system has never been shut down (cleanly) before and so has
 no pre-existing seed file is a BIG corner case to consider since thats how
 the system is at the time it first generates SSH keys after a fresh
 install).
 
 It might be only an academic vulnerability, but if someone can read your
 HD during the time the system is shut down then I'd prefer them not to
 know the precise state when the system next starts up again. Yes, if they
 can read they can probably also write, but it seems like a mistake when
 there's nothing really gained by saving the complete state, as opposed to
 an extract.

And for folks like us who do mass installs via dd if=/dev/da1 of=/dev/da2,
where da1 is a mastered image created via ``make installworld DESTDIR=/mnt'',
the corner case is very large.  I have been bitten by an event where the
master disk was booted once before replication, and thus all systems
had _IDENTICAL_ /etc/ssh contents.  Not a very good idea !!

We have amended the manufacturing process now, so that part of the
disk replication is the nuking and regeneration of /etc/ssh.


-- 
Rod Grimes - KD7CAX @ CN85sl - (RWG25)   [EMAIL PROTECTED]


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



RE: randomdev entropy gathering is really weak

2000-07-22 Thread David Schwartz


 From the Yarrow paper:
 ``Yarrow's outputs are cryptographically derived. Systems that
 use Yarrow's
 outputs are no more secure than the generation mechanism used.''

 We currently have Yarrow-256(Blowfish); wanna make it Yarrow-1024? I could
 make it so.

 M
 --
 Mark Murray

It doesn't matter if it's Yarrow-256, Yarrow-1024, or Yarrow-10.
/dev/random should block if the system does not contain as much real entropy
as the reader desires. Otherwise, the PRNG implementation will be the
weakest link for people who have deliberately selected higher levels of
protection from cryptographic attack.

DS



To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-22 Thread Mark Murray

 /dev/random should block if the system does not contain as much real entropy
 as the reader desires. Otherwise, the PRNG implementation will be the
 weakest link for people who have deliberately selected higher levels of
 protection from cryptographic attack.

I don't want to rehash this thread from the beginning. Please go
back, read the Yarrow paper, and recognise that Yarrow is not an
entropy-counter, it is a cryptographically secure PRNG. The "count
random bits and block" model does not apply.

M
--
Mark Murray
Join the anti-SPAM movement: http://www.cauce.org


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-22 Thread Kris Kennaway

On Sat, 22 Jul 2000, Mark Murray wrote:

  So what it if I want/need 257 bits? :-)
 
 Read them. You'll get them. If you want higher quality randomness than
 Yarrow gives, read more than once. Do other stuff; play. Don't get stuck
 in the "I have exhausted the randomness pool" loop; Yarrow does not play
 that game.

I think you're missing the point. The only way I can get a random number
with more than n bits of entropy out of Yarrow-n is if I sample either
side of a reseed operation, which in general comes down to timing
guesswork and having to make assumptions about the PRNG implementation.

If you want to generate a cryptographic key of length n bits then you
really want n bits of entropy in the random source you're deriving it
from, otherwise your key is actually much weaker than advertised because
it's easier for the attacker to attack the state of the PRNG that derived
it than to attack the key itself.

 From the Yarrow paper:
 ``Yarrow's outputs are cryptographically derived. Systems that use Yarrow's
 outputs are no more secure than the generation mechanism used.''
 
 We currently have Yarrow-256(Blowfish); wanna make it Yarrow-1024? I could
 make it so.

Well, if we did that then how about generating 2048-bit keys? :-)

Kris

--
In God we Trust -- all others must submit an X.509 certificate.
-- Charles Forsythe [EMAIL PROTECTED]



To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-22 Thread Kris Kennaway

On Sat, 22 Jul 2000, Jeroen C. van Gelderen wrote:

 You don't care in practice, 256 bits are unguessable.

Actually, I do..that's the entire point of using long keys.

 If you do care, you load a different random module :-)

The core of my complaint is that even though our old PRNG did crappy
entropy handling, we used to have such a method, which is now gone. I'd
like to see yarrow hang off /dev/urandom and have /dev/random tap directly
into the entropy pool (perhaps a third pool separate from Yarrow's
fast/slow) so I can generate my large keys safely.

Kris

--
In God we Trust -- all others must submit an X.509 certificate.
-- Charles Forsythe [EMAIL PROTECTED]



To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-22 Thread Jeroen C. van Gelderen

Kris Kennaway wrote:
 
 On Sat, 22 Jul 2000, Jeroen C. van Gelderen wrote:
 
  You don't care in practice, 256 bits are unguessable.
 
 Actually, I do..that's the entire point of using long keys.

I agree that you need long RSA keys ... but the real 
discussion isn't really about key length but rather about 
the overall complexity of attacking the key:

The complexity of factoring a 1024-bit RSA keys is on the
order of 2^71 operations. For a 3214-bit key it is roughly 
equivalent to 2^101 complexity. (See [1][2] for gloriously 
arcane details.)

Now, assuming that you generate a 3214-bit RSA key from a 
256-bit entropy pool, the complexity of factoring it (2^101) 
is much lower than the complexity of guessing the entropy
pool from which it was generated (2^256); Actually, factoring 
is the most efficient attack up to the point where you are 
using something like a 13841-bit RSA key[3].

So, for practical key purposes Yarrow-256 is in excess of 
complexity requirements. (I can't say anything about other 
uses than crypto but seeing as the promise of /dev/random 
is cryptographically secure random numbers this should not 
pose a problem.)

That said, there is nothing to prevent the system admin 
from tweaking the Yarrow security parameters so that 
Yarrow will only spit out as many bits or pseudo-randomness 
as it gathers bits of entropy.[4]

Check out http://www.cryptosavvy.com/table.htm and preferrably
the full paper at http://www.cryptosavvy.com/cryptosizes.pdf
if you remain unconvinced :-)

Cheers,
Jeroen

[1] Numbers from http://www.cryptosavvy.com/table.htm .

[2] Yes, this sortof means that using = 128-bit keys is 
overkill for most applications that use assymmetric
algorithms for key-negotiation :-)

[3] http://www.cryptosavvy.com/suggestions.htm

[4] And if you really would like to restore the old semantics
of /dev/[u]random, you could code it into Yarrow. Just 
make /dev/random block based on the entropy estimation 
that Yarrow keeps anyway.

-- 
Jeroen C. van Gelderen  o  _ _ _
[EMAIL PROTECTED]  _o /\_   _ \\o  (_)\__/o  (_)
  _ \_   _(_) (_)/_\_| \   _|/' \/
 (_)(_) (_)(_)   (_)(_)'  _\o_


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-22 Thread Kris Kennaway

On Sat, 22 Jul 2000, Jeroen C. van Gelderen wrote:

 I agree that you need long RSA keys ... but the real 
 discussion isn't really about key length but rather about 
 the overall complexity of attacking the key:

Okay, using RSA keys wasn't the best example to pick, but Yarrow also
seems easy to misuse in other cases: for example if you want to generate
multiple 256-bit symmetric keys (or other random data) at the same time,
each additional key after the first won't contain any additional entropy,
so if you break the state of the PRNG at the time the first one was
generated you get the others for free (until the thing reseeds).

This design tradeoff is discussed in section 4.1 of the paper.

 That said, there is nothing to prevent the system admin 
 from tweaking the Yarrow security parameters so that 
 Yarrow will only spit out as many bits or pseudo-randomness 
 as it gathers bits of entropy.[4]

Well, I don't see a way to tune this without modifying the Yarrow design,
since the entropy pool is intentionally decoupled from the output
mechanism, and it seems like it would add additional (unnecessary)
overhead anyway to use it in that fashion.

Indications are we can probably get quite a lot of usable entropy from a
standard system (on the order of many kilobytes per second - but I need to
read more of the literature about processing of entropy samples) - in this
case I think maintaining a third pool which is directly tapped by
/dev/random, and leaving Yarrow sitting behind /dev/urandom is the way to
go.

Kris

--
In God we Trust -- all others must submit an X.509 certificate.
-- Charles Forsythe [EMAIL PROTECTED]



To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-21 Thread Kris Kennaway

On Tue, 18 Jul 2000, Dan Moschuk wrote:

 Well, how many other OSs out there allow /dev/random to be written to?

FreeBSD, OpenBSD, NetBSD, Linux...

Kris

--
In God we Trust -- all others must submit an X.509 certificate.
-- Charles Forsythe [EMAIL PROTECTED]




To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-21 Thread Mark Murray

  What about saving the state of the RNG and re-reading it on bootup?  That
  will allow Yarrow to continue right where it left off. :-)
 
 That's a bad thing. You don't want someone to be able to examine the exact
 PRNG state at next boot by looking at your hard disk after the machine has
 shut down.

It is a Yarrow-mandated procedure. Please read the Yarrow paper.

If they can do that, they have either the console (==root) or they have
root. Either way, who cares what they know about your machine, they have
the whole darn thing :-O.

M
--
Mark Murray
Join the anti-SPAM movement: http://www.cauce.org


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-21 Thread Dan Moschuk


|  | Gotcha - fix coming; I need to stash some randomness at shutdown time, and
|  | use that to reseed the RNG at reboot time.
|  
|  What about saving the state of the RNG and re-reading it on bootup?  That
|  will allow Yarrow to continue right where it left off. :-)
| 
| That's a bad thing. You don't want someone to be able to examine the exact
| PRNG state at next boot by looking at your hard disk after the machine has
| shut down.

I don't see how.  If the attacker has physical access to the machine, there
are plenty worse things to be done than just reading the state of a PRNG.

If the random device is initialized in single user mode, and the file is
then unlink()ed, I don't see any problems with that.

-Dan


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-21 Thread Jeroen C. van Gelderen

Mark Murray wrote:
 
   What about saving the state of the RNG and re-reading it on bootup?  That
   will allow Yarrow to continue right where it left off. :-)
 
  That's a bad thing. You don't want someone to be able to examine the exact
  PRNG state at next boot by looking at your hard disk after the machine has
  shut down.
 
 It is a Yarrow-mandated procedure. Please read the Yarrow paper.

Actually, it's not. You don not want to save the exact 
PRNG state to disk, ever. It's not Yarrow mandated 
procedure but a big security hole. 

That said, you do not write out the state of the PRNG,
you write out a couple of blocks of output from which 
the state cannot be derived. That *is* okay and that's
what you are doing. 

And just for completeness: it's not mandatory to do so.
I don't know where you read that in the paper.

 If they can do that, they have either the console (==root) or they have
 root. Either way, who cares what they know about your machine, they have
 the whole darn thing :-O.

Someone may well compromise your randomness source without 
you noticing. And read your PGP mail for the coming couple 
of years because your PGP key was compromised without you 
noticing. Perfect Trojan horse to write for the FBI, IRS,
anyone who doesn't like you. Oops.

Cheers,
Jeroen
-- 
Jeroen C. van Gelderen  o  _ _ _
[EMAIL PROTECTED]  _o /\_   _ \\o  (_)\__/o  (_)
  _ \_   _(_) (_)/_\_| \   _|/' \/
 (_)(_) (_)(_)   (_)(_)'  _\o_


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-21 Thread Jeroen C. van Gelderen

Dan Moschuk wrote:
 
 |  | Gotcha - fix coming; I need to stash some randomness at shutdown time, and
 |  | use that to reseed the RNG at reboot time.
 | 
 |  What about saving the state of the RNG and re-reading it on bootup?  That
 |  will allow Yarrow to continue right where it left off. :-)
 |
 | That's a bad thing. You don't want someone to be able to examine the exact
 | PRNG state at next boot by looking at your hard disk after the machine has
 | shut down.
 
 I don't see how.  If the attacker has physical access to the machine, there
 are plenty worse things to be done than just reading the state of a PRNG.
 
 If the random device is initialized in single user mode, and the file is
 then unlink()ed, I don't see any problems with that.

You generate a new PGP keypair and start using it. Your
co-worker reboots your machine afterwards and recovers 
the PRNG state that happens to be stashed on disk. He 
can then backtrack and potentially recover the exact same
random numbers that you used for your key.

Cheers,
Jeroen
-- 
Jeroen C. van Gelderen  o  _ _ _
[EMAIL PROTECTED]  _o /\_   _ \\o  (_)\__/o  (_)
  _ \_   _(_) (_)/_\_| \   _|/' \/
 (_)(_) (_)(_)   (_)(_)'  _\o_


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-21 Thread Steve Kargl

Jeroen C. van Gelderen wrote:
 Dan Moschuk wrote:
  
  I don't see how.  If the attacker has physical access to the machine, there
  are plenty worse things to be done than just reading the state of a PRNG.
  
  If the random device is initialized in single user mode, and the file is
  then unlink()ed, I don't see any problems with that.
 
 You generate a new PGP keypair and start using it. Your
 co-worker reboots your machine afterwards and recovers 
 the PRNG state that happens to be stashed on disk. He 
 can then backtrack and potentially recover the exact same
 random numbers that you used for your key.
 

I don't follow your logic.

A normal boot/shutdown sequence would be:
  (1) power on (or shutdown -r)
  (2) in single-user mode
  (a) read /dev/saved_entropy into buffer
  (b) unlink /dev/saved_entropy
  (c) create /dev/saved_entropy with all zeros
  (d) test contents in buffer against all zeros
  (I)  buffer contents is different from all zeros;
   initialize entropy pool
  (II) buffer contents matches all zeros; use
   a fall-back method.
  (3) go multi-user   
  (4) normal shutdown
  (a) kick everybody off system
  (b) kill off daemons
  (c) umount all partitions except the partition with /dev
  (c) save entropy to /dev/saved_entropy
  (d) umount partition with /dev

After a crash or panic, the system reboots.  Step 2(c) has
left a finger print to test for valid saved entropy.  If all
zeros are found use a suitable fallback method to stir the
entropy.

I don't see how co-worker can do what you suggest.  And, if
he can easily reboot your system, you have other problems to
worry about.

-- 
Steve


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-21 Thread Mark Murray

  It is a Yarrow-mandated procedure. Please read the Yarrow paper.
 
 Actually, it's not. You don not want to save the exact 
 PRNG state to disk, ever. It's not Yarrow mandated 
 procedure but a big security hole. 

Section 2.1, last paragraph:
"If a system is shut down, and restarted, it is desirable to store some
high-entropy data (such as the key) in non-volatile memory. This allows
the PRNG to be restarted in an unguessable state at the next restart. We
call this data the reseed file."

Perhaps "mandated" was a bit strong; "desired" might be better.

 That said, you do not write out the state of the PRNG,
 you write out a couple of blocks of output from which 
 the state cannot be derived. That *is* okay and that's
 what you are doing. 

Writing the 256-bit key would have been OK according to the paper.

 And just for completeness: it's not mandatory to do so.
 I don't know where you read that in the paper.

See above.

  If they can do that, they have either the console (==root) or they have
  root. Either way, who cares what they know about your machine, they have
  the whole darn thing :-O.
 
 Someone may well compromise your randomness source without 
 you noticing. And read your PGP mail for the coming couple 
 of years because your PGP key was compromised without you 
 noticing. Perfect Trojan horse to write for the FBI, IRS,
 anyone who doesn't like you. Oops.

Sure; we neet to be appropriately paranoid about that, but let's not
get ridiculous. The seed file could certainly use some decent protection,
but unfortunately, PC architectures don't come with SIMcards or the like.

M
--
Mark Murray
Join the anti-SPAM movement: http://www.cauce.org


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-21 Thread Mark Murray

 You generate a new PGP keypair and start using it. Your
 co-worker reboots your machine afterwards and recovers 
 the PRNG state that happens to be stashed on disk. He 
 can then backtrack and potentially recover the exact same
 random numbers that you used for your key.

Said state is rm'med after use. If you didn't detect the breakin,
your fault for poor intrusion detection. lets put the paranoia
to practical use and detect the breakin, not nitpick the systems
that are supposed to be protected.

M
--
Mark Murray
Join the anti-SPAM movement: http://www.cauce.org


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-21 Thread David Scheidt

On Fri, 21 Jul 2000, Mark Murray wrote:

:
:Sure; we neet to be appropriately paranoid about that, but let's not
:get ridiculous. The seed file could certainly use some decent protection,
:but unfortunately, PC architectures don't come with SIMcards or the like.
:

Is it possible to combine the state of the disk based seed with some other
source of real entropy?  That would redudce the risk of having someone  read
your disks while the system is shutdown.


David



To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-21 Thread Mark Murray

 :Sure; we neet to be appropriately paranoid about that, but let's not
 :get ridiculous. The seed file could certainly use some decent protection,
 :but unfortunately, PC architectures don't come with SIMcards or the like.
 :
 
 Is it possible to combine the state of the disk based seed with some other
 source of real entropy?  That would redudce the risk of having someone  read
 your disks while the system is shutdown.

I'm working on haresting some more entropy; that should do what you want.
(Things like disk activity, network stack, process tables and so on).

If you are worried about someone reading the disk of a rebooting box,
then you need to be worried about console access; if your attacker has
console, you are screwed anyway.

M
--
Mark Murray
Join the anti-SPAM movement: http://www.cauce.org


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



RE: randomdev entropy gathering is really weak

2000-07-21 Thread David Schwartz



 You generate a new PGP keypair and start using it. Your
 co-worker reboots your machine afterwards and recovers
 the PRNG state that happens to be stashed on disk. He
 can then backtrack and potentially recover the exact same
 random numbers that you used for your key.

If that is possible, then Yarrow's algorithm is badly broken. It should not
be possible to run a PRNG backwards without knowing what it output. Once it
outputs something, the state information neccessary to produce that output
should be removed by the output process.

Imagine if I have a PRNG in state 0 (which I'll call "S(0)"). It then
outputs a particular 32-bit PRN, called 'A' and is now in a new state S(1).
Now, if one tries to backtrack from S(1) to S(0), one needs to know A. For
every possible 32-bit A that could have been output, there's a different
corresponding S'(0) (state that might have been S(0)). Since the attacker
does not know A, he does not know which S'(0) corresponds to S(0), and hence
cannot backtrack.

Since the people who developed this algorithm are pretty bright, I will
conculde that this is not the case.

DS



To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-21 Thread Kris Kennaway

On Fri, 21 Jul 2000, Mark Murray wrote:

 Section 2.1, last paragraph:
 "If a system is shut down, and restarted, it is desirable to store some
 high-entropy data (such as the key) in non-volatile memory. This allows
 the PRNG to be restarted in an unguessable state at the next restart. We
 call this data the reseed file."

I'm all for storing a sample at shutdown and using it to help seed the
PRNG at startup, but it shouldn't be the only seed used (for example, the
case where the system has never been shut down (cleanly) before and so has
no pre-existing seed file is a BIG corner case to consider since thats how
the system is at the time it first generates SSH keys after a fresh
install).

It might be only an academic vulnerability, but if someone can read your
HD during the time the system is shut down then I'd prefer them not to
know the precise state when the system next starts up again. Yes, if they
can read they can probably also write, but it seems like a mistake when
there's nothing really gained by saving the complete state, as opposed to
an extract.

Kris

--
In God we Trust -- all others must submit an X.509 certificate.
-- Charles Forsythe [EMAIL PROTECTED]



To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-21 Thread Kris Kennaway

On Fri, 21 Jul 2000, Mark Murray wrote:

 If you are worried about someone reading the disk of a rebooting box,
 then you need to be worried about console access; if your attacker has
 console, you are screwed anyway.

For most people, yes. But it's like all of the buffer overflows in
non-setuid utilities: they're not security risks for the vast majority of
users, but who's to say there won't be a situation somewhere when it is
one. Better not to take the risk, since it's not necessary here.

Kris

--
In God we Trust -- all others must submit an X.509 certificate.
-- Charles Forsythe [EMAIL PROTECTED]



To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



RE: randomdev entropy gathering is really weak

2000-07-21 Thread Kris Kennaway

On Fri, 21 Jul 2000, David Schwartz wrote:

  You generate a new PGP keypair and start using it. Your
  co-worker reboots your machine afterwards and recovers
  the PRNG state that happens to be stashed on disk. He
  can then backtrack and potentially recover the exact same
  random numbers that you used for your key.
 
   If that is possible, then Yarrow's algorithm is badly broken. It
 should not be possible to run a PRNG backwards without knowing what it
 output. Once it outputs something, the state information neccessary to
 produce that output should be removed by the output process.

Yarrow only reseeds every so often when it has enough entropy accumulated,
and changes its internal key using a "generator gate" every few inputs
(the paper suggests 10). So if you break the state of the algorithm (e.g.
if it were stored on disk after a reboot) you can learn up to 10 previous
PRNG outputs with that key, back to the previous generator gate or reseed.

This issue is common to all PRNGs that don't reseed with every output
value - it's discussed in the Yarrow paper, which you should read :-)

Kris

--
In God we Trust -- all others must submit an X.509 certificate.
-- Charles Forsythe [EMAIL PROTECTED]



To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-21 Thread Kris Kennaway

On Fri, 21 Jul 2000, Kris Kennaway wrote:

  Section 2.1, last paragraph:
  "If a system is shut down, and restarted, it is desirable to store some
  high-entropy data (such as the key) in non-volatile memory. This allows
  the PRNG to be restarted in an unguessable state at the next restart. We
  call this data the reseed file."

After rereading the paper in more detail, Step 7 of the reseed algorithm
seems not entirely consistent with this: they explicitly refer to writing
out "the next 2k bits of output from the generator to the seed file"
(slightly different terminology, but I couldn't find any other references
to the "seed file")

Another important point is that Yarrow-160 is not useful for generating
keys 160 bits, because of Shannon's theorem and the fact that it uses
SHA-1. You seem to be using a blowfish-based hash function with 256-bit
keysize (do you have a reference for using blowfish in that fashion?), but
the point stands. It seems we would need to use an alternative interface
which either synchronously reseeds with every output to generate stronger
random data, or just taps into the (hashed) entropy pools directly.

This was also a problem with our /dev/urandom (by design), but not with
/dev/random since that tapped the entropy pool directly. Incidentally, it
also looks like a problem with OpenBSD's /dev/arandom which is a stream
cipher (arc4 with 256-bit key) periodically reseeded.

Kris

--
In God we Trust -- all others must submit an X.509 certificate.
-- Charles Forsythe [EMAIL PROTECTED]



To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-19 Thread Peter Dufault

 The reason why ntp is interesting is that we compare the received data
 with our unpredictable local clock.  It is the result of this comparison
 which is good entropy bits.

Is the resolution of thermal sensors on many new motherboards and
CPU high enough to get thermal randomness?

Peter
--
Peter Dufault ([EMAIL PROTECTED])   Realtime development, Machine control,
HD Associates, Inc.   Fail-Safe systems, Agency approval


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-19 Thread Steve O'Hara-Smith


On 19-Jul-00 Peter Dufault wrote:
 Is the resolution of thermal sensors on many new motherboards and
 CPU high enough to get thermal randomness?

The voltage sensors have some noise too (maybe not enough).

-- 
Steve O'Hara-Smith [EMAIL PROTECTED]

http://sohara.webhop.net/ A Better Way To Focus The Sun


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-19 Thread Leif Neland



On Wed, 19 Jul 2000, Steve O'Hara-Smith wrote:

 
 On 19-Jul-00 Peter Dufault wrote:
  Is the resolution of thermal sensors on many new motherboards and
  CPU high enough to get thermal randomness?
 
 The voltage sensors have some noise too (maybe not enough).
 
Fan speed too.

Leif



To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-19 Thread Warner Losh

In message [EMAIL PROTECTED] Alexander Leidinger writes:
: systems which have a more or less precise clock attached (e.g. GPS or
: atomic clocks which sync the system clock via nptd)? And what are the
: numbers for this solution (for those people which are interested in
: numbers to be their own judge)?

I can tell you right now that the variation between GPS and a good
cesium clock is on the order of +- 25ns.  With nanosecond resolution,
this gives you about 5 bits.  The variation of the system clock when
synchronized to the GPS receiver is on the order of +-10us as measured
with a parallel port interrupt and a pps line from the gps receiver.
The pps interrupt is measured using a fast interrupt (we hacked ppc to
do fast interrupts for this), so the latency is fairly small and
fairly constant.

I don't have datasets that I can point people at, however.

Warner



To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-19 Thread Poul-Henning Kamp

In message [EMAIL PROTECTED], Warner Losh writes:

Another good source would be if you had a Cesium clock and a GPS
receiver.  The delay due to atmospherics is another good source of
random data.  This varies +- 25ns and is highly locale dependent.  One
can measure this variance down to the nanosecond easily (giving about
5 bits of randomness) and with a lot of effort down to the pico second 
level, which would give you about 15 bits of randomness.

A geiger counter and a smoke-detector would be *so much* cheaper
and give more bits per second :-)

It certainly would be better than nothing and would be a decent source 
of randomness.  It would be my expectation that if tests were run to
measure this randomness and the crypto random tests were applied,
we'd find a fairly good source.

The trick here is to actually measure the quality of our entropy.
I have asked Markm to provide us with some kernel option which can
be used to get a copy of the entropy so we can study the quality
off it.

BTW: You have *no* idea how much I envy your access to high quality
timing hardware :-)

--
Poul-Henning Kamp   | UNIX since Zilog Zeus 3.20
[EMAIL PROTECTED] | TCP/IP since RFC 956
FreeBSD coreteam member | BSD since 4.3-tahoe
Never attribute to malice what can adequately be explained by incompetence.


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-19 Thread Mark Murray

[ A whole bunch of sane stuff removed ]

 It certainly would be better than nothing and would be a decent source 
 of randomness.  It would be my expectation that if tests were run to
 measure this randomness and the crypto random tests were applied,
 we'd find a fairly good source.

The randomness is good, no doubt; I worry about how accessible that
randomness is to an attacker?

If the attacker is on your computer (he us a user, say), he might know
a lot about the current frequency of your xtal. He can also get the same
(remote) time offsets as you. What does that give him? Not much, but it
could reduce the bits that he needs to guess. By how much? I don't
know.

M
--
Mark Murray
Join the anti-SPAM movement: http://www.cauce.org


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-19 Thread Warner Losh

In message [EMAIL PROTECTED] Poul-Henning Kamp writes:
: A geiger counter and a smoke-detector would be *so much* cheaper
: and give more bits per second :-)

Agreed.  And a lot less hassle.  A *LOT* less hassle. :-)

: It certainly would be better than nothing and would be a decent source 
: of randomness.  It would be my expectation that if tests were run to
: measure this randomness and the crypto random tests were applied,
: we'd find a fairly good source.
: 
: The trick here is to actually measure the quality of our entropy.
: I have asked Markm to provide us with some kernel option which can
: be used to get a copy of the entropy so we can study the quality
: off it.

Yes.  That's the hard part.  that's one area where my knowledge is
somewhat weak.

: BTW: You have *no* idea how much I envy your access to high quality
: timing hardware :-)

Well, there are hidden benefits working here that I never knew :-)

Warner


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-19 Thread Warner Losh

In message [EMAIL PROTECTED] Mark Murray writes:
: The randomness is good, no doubt; I worry about how accessible that
: randomness is to an attacker?

That's a good thing to worry about.

: If the attacker is on your computer (he us a user, say), he might know
: a lot about the current frequency of your xtal. He can also get the same
: (remote) time offsets as you. What does that give him? Not much, but it
: could reduce the bits that he needs to guess. By how much? I don't
: know.

I don't know the answers to that either.

Of course, if the attaker has root access to your machine, then you
have bigtime problems with keeping the random bits secret anyway...

Warner


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-19 Thread Poul-Henning Kamp

In message [EMAIL PROTECTED], Mark Murray writes:
[ A whole bunch of sane stuff removed ]

 It certainly would be better than nothing and would be a decent source 
 of randomness.  It would be my expectation that if tests were run to
 measure this randomness and the crypto random tests were applied,
 we'd find a fairly good source.

The randomness is good, no doubt; I worry about how accessible that
randomness is to an attacker?

If the attacker is on your computer (he us a user, say), he might know
a lot about the current frequency of your xtal. He can also get the same
(remote) time offsets as you. What does that give him? Not much, but it
could reduce the bits that he needs to guess. By how much? I don't
know.

Mark, this is one of the reasons why we need a way to measure the
quality of our entropy, please

--
Poul-Henning Kamp   | UNIX since Zilog Zeus 3.20
[EMAIL PROTECTED] | TCP/IP since RFC 956
FreeBSD coreteam member | BSD since 4.3-tahoe
Never attribute to malice what can adequately be explained by incompetence.


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-19 Thread Peter Dufault

 In message [EMAIL PROTECTED] Peter Dufault writes:
 :  The reason why ntp is interesting is that we compare the received data
 :  with our unpredictable local clock.  It is the result of this comparison
 :  which is good entropy bits.
 : 
 : Is the resolution of thermal sensors on many new motherboards and
 : CPU high enough to get thermal randomness?
 
 Yes.  You'll also find that the voltage drifts as well.  However, I
 doubt you'd be able to get more than 1 bit out of the voltage
 readings.  The thermal readings, depending on their precision, would
 also yield several random bits.  But this several may be only 3 or 4.
 The temperature varies based on work load and on the climate controls
 in place at the site.

I actually meant can you get real randomness,
measuring the thermal noise in the on-chip temperature diode
should be a good source of randomness.  Except they are probably "kind"
enough to fully filter it out.

Peter

--

Peter Dufault ([EMAIL PROTECTED])   Realtime development, Machine control,
HD Associates, Inc.   Fail-Safe systems, Agency approval


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-19 Thread Mark Murray

 The trick here is to actually measure the quality of our entropy.
 I have asked Markm to provide us with some kernel option which can
 be used to get a copy of the entropy so we can study the quality
 off it.

I have something that is _very_ crude, and definitely not
commitworthy, but it is up to the doing the job above.
As soon as I've prettyfied it a bit, I'll give y'all
some patches.

M
--
Mark Murray
Join the anti-SPAM movement: http://www.cauce.org


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-19 Thread Mark Murray

 : If the attacker is on your computer (he us a user, say), he might know
 : a lot about the current frequency of your xtal. He can also get the same
 : (remote) time offsets as you. What does that give him? Not much, but it
 : could reduce the bits that he needs to guess. By how much? I don't
 : know.
 
 I don't know the answers to that either.
 
 Of course, if the attaker has root access to your machine, then you
 have bigtime problems with keeping the random bits secret anyway...

My scenario assumed that the attacker/user was not root. Of course if
he is root, he knows a bit more, but even a non-root attacker can make
a statistical study of the local clock and some hand-rolled ntp code.

(I'm not suggesting it is easy, just possible :-) )

M
--
Mark Murray
Join the anti-SPAM movement: http://www.cauce.org


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-19 Thread Mark Murray

 If the attacker is on your computer (he us a user, say), he might know
 a lot about the current frequency of your xtal. He can also get the same
 (remote) time offsets as you. What does that give him? Not much, but it
 could reduce the bits that he needs to guess. By how much? I don't
 know.
 
 Mark, this is one of the reasons why we need a way to measure the
 quality of our entropy, please

I understand 100%! That's why I'm doing it :-)

M
--
Mark Murray
Join the anti-SPAM movement: http://www.cauce.org


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-18 Thread Mark Murray

 Actually, you could really use this in ntpd(8), rather than just ntpdate.
 You could crank in the offset and delay samples for each packet
 received from an NTP peer; this will have the effect of adding into
 the entropy pool the "noise" in the latency of the path between you
 and each of your NTP peers.  This varies over time with each sample,
 and in fact, NTP goes to considerable effort in it's sample filtering
 to exclude the noisy samples.  We need to get that date before it's
 discarded and contribute it to the entropy cause.

You forget; a snooper watching your (ether)net has access to nearly
all of this information.

M
--
Mark Murray
Join the anti-SPAM movement: http://www.cauce.org


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-18 Thread Poul-Henning Kamp

In message [EMAIL PROTECTED], Mark Murray writes:
 Actually, you could really use this in ntpd(8), rather than just ntpdate.
 You could crank in the offset and delay samples for each packet
 received from an NTP peer; this will have the effect of adding into
 the entropy pool the "noise" in the latency of the path between you
 and each of your NTP peers.  This varies over time with each sample,
 and in fact, NTP goes to considerable effort in it's sample filtering
 to exclude the noisy samples.  We need to get that date before it's
 discarded and contribute it to the entropy cause.

You forget; a snooper watching your (ether)net has access to nearly
all of this information.

No, he doesn't have access to the offset from the machines local clock.

I ran a quick  dirty test here on some logfiles: that offset is
very close to white noise.

--
Poul-Henning Kamp   | UNIX since Zilog Zeus 3.20
[EMAIL PROTECTED] | TCP/IP since RFC 956
FreeBSD coreteam member | BSD since 4.3-tahoe
Never attribute to malice what can adequately be explained by incompetence.


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-18 Thread Mark Murray

 People have tried for 30+ years to predict what a quartz xtal
 will do next.  Nobody expects any chance of success.  Add to this
 the need to predict the difference between one or more NTP servers
 and your local qartz xtal and I think we can safely say "impossible".

You can't predict this, but you can _measure_ it with a degree of
accuracy. The attacker can use this accuracy to reduce the number
of tries in his attack.

 I think we first need to figure out the security implications.
 
 I think the security implications of having no entropy are much
 worse than having entropy which a truly superhuman *maybe* could
 guess *some* of the bits in, are far worse.

Yarrow addresses this problem; even if the attacker does manage to
get the internal state, Yarrow will revover.

M
--
Mark Murray
Join the anti-SPAM movement: http://www.cauce.org


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-18 Thread Poul-Henning Kamp

In message [EMAIL PROTECTED], Mark Murray writes:
 People have tried for 30+ years to predict what a quartz xtal
 will do next.  Nobody expects any chance of success.  Add to this
 the need to predict the difference between one or more NTP servers
 and your local qartz xtal and I think we can safely say "impossible".

You can't predict this, but you can _measure_ it with a degree of
accuracy. The attacker can use this accuracy to reduce the number
of tries in his attack.

No he cannot.  The NTP poll period is 64 seconds or longer and unless
you have done something special about your hardware, he cannot predict
all bits.


If he could, ntp would have a longer poll period :-)

--
Poul-Henning Kamp   | UNIX since Zilog Zeus 3.20
[EMAIL PROTECTED] | TCP/IP since RFC 956
FreeBSD coreteam member | BSD since 4.3-tahoe
Never attribute to malice what can adequately be explained by incompetence.


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-18 Thread Jeroen C. van Gelderen

Poul-Henning Kamp wrote:
 
 In message [EMAIL PROTECTED], "Jeroen C. van Gelderen" writes
 :
 
  Predicting the clock's offset from reality and the two way path to
  the server of choice is impossible, plus if people enable authentication
  later on the packets will be choke full of high-quality entropy.
 
 Please quantify 'impossible'.
 
 People have tried for 30+ years to predict what a quartz xtal
 will do next.  Nobody expects any chance of success.  Add to this
 the need to predict the difference between one or more NTP servers
 and your local qartz xtal and I think we can safely say "impossible".

See my reply to David Schwartz. What kind of numbers are we
talking about?

 I think we first need to figure out the security implications.
 
 I think the security implications of having no entropy are much
 worse than having entropy which a truly superhuman *maybe* could
 guess *some* of the bits in, are far worse.

I agree, but to paraphrase: that's policy decision.
Just quantify it so that people can be their own judge.

Cheers,
Jeroen
-- 
Jeroen C. van Gelderen  o  _ _ _
[EMAIL PROTECTED]  _o /\_   _ \\o  (_)\__/o  (_)
  _ \_   _(_) (_)/_\_| \   _|/' \/
 (_)(_) (_)(_)   (_)(_)'  _\o_


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-18 Thread Sheldon Hearn



On Mon, 17 Jul 2000 16:27:17 MST, "Kurt D. Zeilenga" wrote:

 Note that there should be no need to cron the job.

You're right.  My suggestion to use cron's @reboot was as stupid as they
come. :-)

Sorry,
Sheldon.


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-18 Thread Jeroen C. van Gelderen

Poul-Henning Kamp wrote:
 
 In message [EMAIL PROTECTED], "Jeroen C. van Gelderen" writes:
 
  People have tried for 30+ years to predict what a quartz xtal
  will do next.  Nobody expects any chance of success.  Add to this
  the need to predict the difference between one or more NTP servers
  and your local qartz xtal and I think we can safely say "impossible".
 
 See my reply to David Schwartz. What kind of numbers are we
 talking about?
 
 With microsecond timestamps, 64second ntp poll period we are talking
 about approx 10 bits of randomness in the received packet and about
 3 bits of randomness in the clock difference.
 
 FreeBSD uses nanosecond timestamping (Actually could do nanoseconds
 with 32 bitfractions), but that only adds about 4 bits to the clock
 difference due to the clock frequency end interrupt hardware.

Thanks! This is useful.

  I think we first need to figure out the security implications.
 
  I think the security implications of having no entropy are much
  worse than having entropy which a truly superhuman *maybe* could
  guess *some* of the bits in, are far worse.
 
 I agree, but to paraphrase: that's policy decision.
 Just quantify it so that people can be their own judge.
 
 No, it is not policy to try to get as many random bits as we can
 by default.  It would be policy to *not* do so for some obscure
 principle of scientific purity.

It's up to the user to decide what security level he needs.
Both ought to be possible but having an insecure box ought
to be an explicit decision.

I think you will agree that there needs to be a decent 
security level by default. I.e. newly generated SSH host 
keys are sufficiently secure.

Cheers,
Jeroen
-- 
Jeroen C. van Gelderen  o  _ _ _
[EMAIL PROTECTED]  _o /\_   _ \\o  (_)\__/o  (_)
  _ \_   _(_) (_)/_\_| \   _|/' \/
 (_)(_) (_)(_)   (_)(_)'  _\o_


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-18 Thread Mark Murray

 No, he doesn't have access to the offset from the machines local clock.
 
 I ran a quick  dirty test here on some logfiles: that offset is
 very close to white noise.

With what amplitude?

M
--
Mark Murray
Join the anti-SPAM movement: http://www.cauce.org


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-18 Thread Poul-Henning Kamp

In message [EMAIL PROTECTED], Mark Murray writes:
 No, he doesn't have access to the offset from the machines local clock.
 
 I ran a quick  dirty test here on some logfiles: that offset is
 very close to white noise.

With what amplitude?

Depends on the termal environment of your xtal obviously :-)

--
Poul-Henning Kamp   | UNIX since Zilog Zeus 3.20
[EMAIL PROTECTED] | TCP/IP since RFC 956
FreeBSD coreteam member | BSD since 4.3-tahoe
Never attribute to malice what can adequately be explained by incompetence.


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-18 Thread Poul-Henning Kamp

In message [EMAIL PROTECTED], "Jeroen C. van Gelderen" writes

It's up to the user to decide what security level he needs.
Both ought to be possible but having an insecure box ought
to be an explicit decision.

Principle of POLA:  The box doesn't come up in a stupid configuration
right after install.

Principle of "tools, not politics": You can configure it stupidly if
you want, you can also strengthen it beyond practical use if you want.

--
Poul-Henning Kamp   | UNIX since Zilog Zeus 3.20
[EMAIL PROTECTED] | TCP/IP since RFC 956
FreeBSD coreteam member | BSD since 4.3-tahoe
Never attribute to malice what can adequately be explained by incompetence.


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-18 Thread Alexander Langer

Thus spake Louis A. Mamakos ([EMAIL PROTECTED]):

 Actually, you could really use this in ntpd(8), rather than just ntpdate.

Hmm, as addition, I agree.

However, I think more people use ntpdate than ntpd, and thus ntpdate
is a good place :)

Alex
-- 
cat: /home/alex/.sig: No such file or directory


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-18 Thread Bruce Evans

On Sun, 16 Jul 2000, Kris Kennaway wrote:

 On the other hand, doing a dd if=/dev/random of=/dev/null gives me
 infinite "randomness" at 10MB/sec - have the semantics of /dev/random
 changed?

Yes.  /dev/random is now just an alias for /dev/urandom (or vice versa).

You must have a fast machine to get 10MB/sec.  I see the following speeds
(using a better reading program than dd; dd gives up on EOF on the old
/dev/random):

old /dev/random  on P5/1335K/sec
old /dev/urandom on P5/133  244K/sec
old /dev/random  on Celeron 366 overclocked to 5.5*9525K/sec
old /dev/urandom on Celeron 366 overclocked to 5.5*95   970K/sec
new /dev/*random on Celeron 400 overclocked to 6.0*75   270K/sec

Bruce



To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-18 Thread Mark Murray

 With microsecond timestamps, 64second ntp poll period we are talking
 about approx 10 bits of randomness in the received packet and about
 3 bits of randomness in the clock difference.
 
 FreeBSD uses nanosecond timestamping (Actually could do nanoseconds
 with 32 bitfractions), but that only adds about 4 bits to the clock
 difference due to the clock frequency end interrupt hardware.

So the attacker is down to 17 bits == 128k guesses. Now that is good
entropy, but we need to know what the attacker can see inside the
packet etc. How else can he reduce his keyspace?

 No, it is not policy to try to get as many random bits as we can
 by default.  It would be policy to *not* do so for some obscure
 principle of scientific purity.

Pray explain?

M
--
Mark Murray
Join the anti-SPAM movement: http://www.cauce.org


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-18 Thread Kris Kennaway

On Tue, 18 Jul 2000, Bruce Evans wrote:

 You must have a fast machine to get 10MB/sec.  I see the following speeds
 (using a better reading program than dd; dd gives up on EOF on the old
 /dev/random):

Oops, I misread the rate by 2 orders of magnitude. I get about 100K/sec on
my PPro/233 :-)

 old /dev/random  on P5/1335K/sec
 old /dev/urandom on P5/133  244K/sec
 old /dev/random  on Celeron 366 overclocked to 5.5*9525K/sec
 old /dev/urandom on Celeron 366 overclocked to 5.5*95   970K/sec
 new /dev/*random on Celeron 400 overclocked to 6.0*75   270K/sec

Kris

--
In God we Trust -- all others must submit an X.509 certificate.
-- Charles Forsythe [EMAIL PROTECTED]



To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



Re: randomdev entropy gathering is really weak

2000-07-18 Thread Mark Murray

  I ran a quick  dirty test here on some logfiles: that offset is
  very close to white noise.
 
 With what amplitude?
 
 Depends on the termal environment of your xtal obviously :-)

Help me here! :-)

In your observed sample, what was the white noise amplitude?

M
--
Mark Murray
Join the anti-SPAM movement: http://www.cauce.org


To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message



  1   2   >