Re: SHA1 as PRNG?

From: Anton Stiglic (stiglic_at_cs.mcgill.ca)
Date: 06/09/04 

Date: Wed, 9 Jun 2004 11:13:18 -0400

"Matt Mahoney" <matmahoney@yahoo.com> wrote in message
news:ggnxc.2932$Y3.1812@newsread2.news.atl.earthlink.net...
>
> "Tom St Denis" <tomstdenis@iahu.ca> wrote in message
> news:Bxaxc.1525$MH3.1363@news04.bloor.is.net.cable.rogers.com...
> > No need to X-POST this to comp.compression... fixed.
> >
> > Matt Mahoney wrote:
> > > Suppose I generate the pseudo random sequence x[1], x[2], x[3]...
where
> each
> > > x[i] is 160 bits, and
> > >
> > > x[i] = SHA1(x[i-1] || key)
> > >
> > > and x[0] = 0.
> > >
> > > Is this a secure pseudo-random sequence? Given all but one bit of an
> >
> > Not really. What if X[j] == X[k] for j != k?
>
> I'd expect that to happen on average after 2^80 blocks. I think given
> reasonable computing resources, say 2^40 blocks (20 TB memory), the odds
of
> a cycle are 2^-80.
>
> > A reasonable alternative would be
> >
> > x[i] = SHA1(i || key)
>
> Yes, at least I'll know exactly what the cycle length is, although I
wonder
> if having lots of similar inputs makes it any more likely to expose any
> weaknesses in SHA1, not that I am aware of any.

SHA1 was specifically disigned so that small differences create large random
looking differences in the output.

You could also do
x[i] = SHA1(key XOR PAD || encode(i))

where PAD is a 512 bit PAD (such as used in HMAC), and encode is a
prefix-free
encoding. In that case, you would be using SHA1 as a PRF, see
http://www.cs.ucsd.edu/users/mihir/papers/cascade.pdf

As long as the key is secret and random, the outputs will look like that of
a random
function, and thus would make for a good PRG. Note I use the term PRG and
not PRNG, see this discussion to why:
http://groups.google.ca/groups?hl=en&lr=&ie=UTF-8&threadm=fecc092d.0304010938.31ac5e21%40posting.google.com&rnum=3&prev=/groups%3Fq%3DPRNG%2BRamzan%26hl%3Den%26lr%3D%26ie%3DUTF-8%26selm%3Dfecc092d.0304010938.31ac5e21%2540posting.google.com%26rnum%3D3

This post is also related to the topic
http://groups.google.ca/groups?q=PRG+from+PRF&hl=en&lr=&ie=UTF-8&selm=slrnbil4tl.u6.mdw%40tux.nsict.org&rnum=6

--Anton

If the input differs by 1
> bit, could the probability of a collision be slightly greater than 2^-160?
>
> Also I wonder if either method really produces uncompressible data. That
> isn't a requirement for security. For example, if the output was 51% 0s
> and 49% 1s, SHA would still be secure (but not quite 2^160). As a quick
> statistical test I tried a few compressors and found no compression, but I
> can get the same results with rand().
>
> -- Matt Mahoney
>
>

Quantcast