Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:18:27
John Kelsey (kelsey@plnet.net)
Thu, 11 Feb 1999 15:35:44 -0600
-----BEGIN PGP SIGNED MESSAGE-----
[ To: CodherPlunks ## Date: 02/11/99 ##
Subject: Re: CSPRNG stuff ]
>Date: Mon, 8 Feb 1999 23:06:24 -0800 (PST)
>From: bram <bram@gawth.com>
>To: "David R. Conrad" <drc@adni.net>
>cc: CodherPlunks@toad.com
>Subject: Re: CSPRNG stuff
[ Much deleted. Here, Bram's quoting David: ]
>>When they are asked to return random bits, they apply SHA-1
>>to the pool, do some mixing of the pool so that it'll never
>>return the same thing twice, and decrement the count of
>>bits in the pool as appropriate. Thus, you can't directly
>>control the bits in the pool by writing to it, and you
>>can't learn the state of the pool by reading from it.
>Ah, but there's a chance you can. There's an attack on
>hamsters where you can get them to repeat the same output
>over and over again by sending them messages with a specific
>pattern. RSAREF is similar to the above except it uses
>addition instead of polynomials, and a number of people have
>figured out a rather practical attack on it. There's
>probably a similar attack on using a polynomial mixing
>function.
I haven't looked at this mechanism real closely. Each time
an output is generated, the pool is updated somehow, so the
PRNG doesn't spew the same output forever. If we can find
an input sequence that will undo the effects of this update,
then we can mount the same attack that worked on RSAREF.
That is, without knowledge of the pool's internal state, we
force the PRNG to repeat the same outputs again and again by
a chosen-input attack.
For example, if the pool were updated by treating the output
as a new value to be mixed back into the pool via the
polynomial, then we'd be able to choose an input sequence
that would undo the previous output's effects. Has anyone
looked at whether this can be done to /dev/random's
generator?
[Stuff deleted.]
>Come to think of it, there's a bit of an implemention
>question here - the API for adding to the pool should really
>include information about how much entropy is in the data
>being added (it's very easy to have a string which contains
>many fewer bits of entropy than it's length.) Probably the
>easiest way to deal with this would be to have an assumed
>amount of entropy in data fed into /dev/random - half a bit
>per bit, say. Of course, this should be decided on and
>documented rather clearly.
In Yarrow, I believe there's a way of specifying how much
entropy the programmer believes some input sample has. This
is compared with an estimate based on a statistical test,
and the smaller of the two is used as the entropy estimate.
>Actually, the collection technique I mentioned above is
>designed for the extremely pessimistic scenario of, say,
>being handed a 1 megabyte file and being told it only
>contains 1 bit of entropy. A completely practical scheme
>might be to assume each intput bit has at least a certain
>amount of entropy, and allocate an array to put intput into
>it until there's enough, at which point you hash whatever's
>in the array and xor the pool with the result.
I prefer having the combination of programmer input and
statistical testing. I might reasonably feed all nonces
sent to me in some protocol into Yarrow as entropy samples
with entropy estimates of 0. This can't make Yarrow less
secure, and will help against attackers who missed any of
those nonces being sent. However, if Yarrow silently
assumes (say) one bit of entropy per 32 bits of input, then
an attacker may try to mount some protocol attack, in which
he carries out the protocol 100 times with the targeted
system, in order to force it to reseed before it's ready.
[ Stuff deleted. ]
>>I was fascinated to discover that there are a number of
>>configurable options. First, the POOLWORDS, which as I
>>said can be increased up to 2048 from the default of 128,
>>second, several unrolled versions of SHA-1 which make
>>size/speed tradeoffs (or you can even use MD5 rather than
>>SHA-1, not that you'd want to)
>If you're using SHA-1, there's no point in having a pool of
>more than 160 bits, since that's how much output SHA-1 gives
>anyway.
This isn't quite right. There's a difference in
design philosophy between these two approaches. Our
approach in Yarrow is to say ``all we can get from a PRNG
are pseudorandom numbers, so our goal is to design a
cryptographically-strong generation mechanism.'' The
dev/random approach is to say ``we hope to get enough
entropy to be able to provide 160 bits of entropy in each
160-bit output. If we get less entropy, then we need to get
cryptographic security.'' This approach isn't inherently
wrong, although the mechanism isn't quite right to
accomplish it.
I think most of the time when we need a CSPRNG (or hamster),
we have trouble being sure we've got very much entropy, and
we'll be happy to get numbers we can't distinguish from
random, even if they're not really random.
>It's very good that there are some size/speed tradeoffs for
>SHA-1. It is however a significant omission that RIPEMD-160
>isn't supported. (RIPEMD-160 and SHA-1 have the same block
>and output size, so either can be used, and some people
>prefer RIPEMD-160 for political and technological reasons.)
Maybe. There are an enormous number of cryptographic
mechanisms out there that *could* be included--SHA1,
RIPE-MD160, Tiger, Haval, Snefru-8/256, etc. I'd be
inclined to say that a user who didn't want to trust SHA1
was welcome to go into the source and replace those calls
with RIPE-MD160 calls. It's not like the PRNGs need to be
*compatible* or anything.
>-Bram
- --John Kelsey, kelsey@counterpane.com / kelsey@plnet.net
NEW PGP print = 5D91 6F57 2646 83F9 6D7F 9C87 886D 88AF
-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 5.5.3i for non-commercial use <http://www.pgpi.com>
iQCVAwUBNsNNHCZv+/Ry/LrBAQEUCAQAuWnkXOCQu9ONPoOSuPRlz8k+3sjC52eV
aMFf1XttJRUvWQqMwisvkqzHp6Nyldkr8Y6uHi0M7VrrqrXSZF9dINiZ5vMoL8lj
bRgUqkkNfdbzdJk61xl46+vaZ83Gi+0KGhbDMDfJJdekQlhRYpspt3/WS9pSBl2d
gLHTxVscEOs=
=cH7f
-----END PGP SIGNATURE-----
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:18:27