Prev: Public/Public
Next: unique pemutation using 3DES
From: Michael on 22 Apr 2010 13:53
Hi,

I'm currently reading the paper about Yarrow (a secure PRNG from
Schneier and others, see http://www.schneier.com/paper-yarrow.html), and
I'm trying to understand the importance of the amount of entropy that
the PRNG provides for its quality as generator for bulk data encryption
keys. Although Yarrow may appear outdated (it was designed in 1999, and
its successor 'Fortuna' has already been published), it is still
important, as it is still used for /dev/random (the common Unix PRNG
device) in current versions of Mac OS X.

The authors state several times in the paper that Yarrow (with
Triple-DES/SHA1, as of 1999), only produces a secure output of some 160
bit. For bigger bulk data encryption keys, they consider (this version
of) Yarrow unsuitable, or even insecure (e.g. on page 6):

"Like any other cryptographic primitive, a Yarrow generator has a
limited strength which we express in the size of the key. Yarrow-160
relies on the strength of three-key triple-DES and SHA-1. Systems that
have switched to the new cryptographic mechanisms (such as the new AES
cipher, when it is selected) in the interests of getting higher security
should also use a different version of Yarrow to rely on those new
mechanisms. If a longer key is necessary, then a future "larger" version
of Yarrow should be used; it makes no sense to use a 160-bit PRNG to
generate a 256-bit key for a block cipher, if 256 bits of security are
actually required."

What does 160/256 "bits of security" actually mean when Yarrow is used
for the generation of a 256 bit key for bulk data encryption? Does it
mean (put overly simply) that it can only produce 160 bits of truly
random AND unguessable key stream, and that an attacker can calculate
the remaining 94 bits from the initial 160 bit? In my understanding of
PRNGs, this would only work if the attacker knew the seed of the PRNG
(which is not necessarily a common scenario for an attack on a PRNG in
an operating system)? If an attacker didn't know the seed, in my eyes he
would not be in any better position than an attacker who didn't know
anything about the key generation history. But maybe I'm missing some
specifics of Yarrow here. Also, what does this mean for the consecutive
generation of 256 bit keys? Would an attacker (without knowing the seed)
be able to benefit from cracking/knowing a preceding key when trying to
crack a subsequent key?

I'm grateful for any commments that can shed some light on this!

Thanks, Michael

From: Peter Pearson on 22 Apr 2010 15:13
On Thu, 22 Apr 2010 19:53:15 +0200, Michael <qawsedrftg(a)gmx-topmail.de> wrote:
>
> What does 160/256 "bits of security" actually mean when Yarrow is used
> for the generation of a 256 bit key for bulk data encryption?

Yarrow is built from components believed to be able to resist
an adversary whose strength is (in some sense) less than 2^160.
It uses entropy pools of 160 bits, relying on the assumption that
your adversary cannot test 2^160 guesses about the contents of an
entropy pool. It uses SHA-1, relying on the assumption that
your adversary cannot find the preimage of its output. It uses
triple DES, relying on the assumption that your adversary cannot
find the 168-bit key that connects a given plaintext to a given
ciphertext.

If you're planning to use a 256-bit key, you'd like to be able
to argue that your system will resist an adversary whose strength
(again, in some sense) is less than 2^256, but the design
assumptions of Yarrow are incompatible with this goal.

--
To email me, substitute nowhere->spamcop, invalid->net.
From: unruh on 22 Apr 2010 16:56
On 2010-04-22, Michael <qawsedrftg(a)gmx-topmail.de> wrote:
> Hi,
>
> I'm currently reading the paper about Yarrow (a secure PRNG from
> Schneier and others, see http://www.schneier.com/paper-yarrow.html), and
> I'm trying to understand the importance of the amount of entropy that
> the PRNG provides for its quality as generator for bulk data encryption
> keys. Although Yarrow may appear outdated (it was designed in 1999, and
> its successor 'Fortuna' has already been published), it is still
> important, as it is still used for /dev/random (the common Unix PRNG
> device) in current versions of Mac OS X.
>
> The authors state several times in the paper that Yarrow (with
> Triple-DES/SHA1, as of 1999), only produces a secure output of some 160
> bit. For bigger bulk data encryption keys, they consider (this version
> of) Yarrow unsuitable, or even insecure (e.g. on page 6):
>
> "Like any other cryptographic primitive, a Yarrow generator has a
> limited strength which we express in the size of the key. Yarrow-160
> relies on the strength of three-key triple-DES and SHA-1. Systems that
> have switched to the new cryptographic mechanisms (such as the new AES
> cipher, when it is selected) in the interests of getting higher security
> should also use a different version of Yarrow to rely on those new
> mechanisms. If a longer key is necessary, then a future "larger" version
> of Yarrow should be used; it makes no sense to use a 160-bit PRNG to
> generate a 256-bit key for a block cipher, if 256 bits of security are
> actually required."

This is a largely idiotic statement. What they mean is that one could do
an exhaustive search of 160 bit and find which key was used to generate
the stream. If you did AES you would need an exhaustive search of 256
bits. Since a 160 exhaustive search is totally and utterly unfeasible
now and for many years in the future, this statement is stupid. The
real question is whether or not given part of the output, one could reconstruct
the future values of the stream (or at least features of the future
valus of the stream). How much of the output would be needed to do so.
However, noone knows how to estimate that so they use silly replacements
for that.

You can certainly use it for far longer lengths than 160 bits. It is
"random" in that it is unpredictable against all known current attacks.
It might not be against future attacks, but if it falls it will
probably not be because computers are then able to launch a 160 bit
exhanustive search.
>
> What does 160/256 "bits of security" actually mean when Yarrow is used
> for the generation of a 256 bit key for bulk data encryption? Does it
> mean (put overly simply) that it can only produce 160 bits of truly
> random AND unguessable key stream, and that an attacker can calculate
> the remaining 94 bits from the initial 160 bit? In my understanding of

The attacker can do an exhaustive search through all 2^160 bits of key,
and once he has found the key which generates the current 160 bits of
output, and then predict the rest of the output, is I think what they
mean.

> PRNGs, this would only work if the attacker knew the seed of the PRNG
> (which is not necessarily a common scenario for an attack on a PRNG in
> an operating system)? If an attacker didn't know the seed, in my eyes he
> would not be in any better position than an attacker who didn't know
> anything about the key generation history. But maybe I'm missing some
> specifics of Yarrow here. Also, what does this mean for the consecutive
> generation of 256 bit keys? Would an attacker (without knowing the seed)
> be able to benefit from cracking/knowing a preceding key when trying to
> crack a subsequent key?

Sure. The above exhaustive search.

>
> I'm grateful for any commments that can shed some light on this!
>
> Thanks, Michael
>
 | 
Pages: 1
Prev: Public/Public
Next: unique pemutation using 3DES