From owner-freebsd-current  Sat Jul 22 17: 7: 7 2000
Delivered-To: freebsd-current@freebsd.org
Received: from cypherpunks.ai (cypherpunks.ai [209.88.68.47])
	by hub.freebsd.org (Postfix) with ESMTP
	id 8F67937C36E; Sat, 22 Jul 2000 17:06:53 -0700 (PDT)
	(envelope-from jeroen@vangelderen.org)
Received: from vangelderen.org (grolsch.ai [209.88.68.214])
	by cypherpunks.ai (Postfix) with ESMTP
	id 411404F; Sat, 22 Jul 2000 20:06:46 -0400 (AST)
Message-ID: <397A3716.A14DBF38@vangelderen.org>
Date: Sat, 22 Jul 2000 20:06:46 -0400
From: "Jeroen C. van Gelderen" <jeroen@vangelderen.org>
X-Mailer: Mozilla 4.73 [en] (X11; I; Linux 2.2.12 i386)
X-Accept-Language: en
MIME-Version: 1.0
To: Kris Kennaway <kris@FreeBSD.org>
Cc: Mark Murray <mark@grondar.za>, current@FreeBSD.ORG
Subject: Re: randomdev entropy gathering is really weak
References: <Pine.BSF.4.21.0007221515150.26717-100000@freefall.freebsd.org>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Sender: owner-freebsd-current@FreeBSD.ORG
Precedence: bulk
X-Loop: FreeBSD.ORG

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      _     _         _
jeroen@vangelderen.org  _o     /\_   _ \\o  (_)\__/o  (_)
                      _< \_   _>(_) (_)/<_    \_| \   _|/' \/
                     (_)>(_) (_)        (_)   (_)    (_)'  _\o_


To Unsubscribe: send mail to majordomo@FreeBSD.org
with "unsubscribe freebsd-current" in the body of the message