RE: key material

["Burton M. Strauss III" <BStrauss () acm org>]

Read the papers on the Lottery machines.

The output of the PRNGs passed all the standard tests for randomness.

The only problem was that when you looked at the TOTAL UNIVERSE of quick
pick tickets that COULD be generated, they didn't cover the universe of
possible numbers and tickets.  The constant resets of the machines made
things much worse...

I guess it depends upon your usage of the PRNG output.  It could be that for
some applications (many? most???) a number of seed bits < the key size is
ok.  But for sampling it's clearly not.

What happens if your PRNG doesn't generate all possible random #s for you to
test for primality?  Don't know.  That depends upon your application.

But I'm very leery of any system that assumes you can't enumerate a small
number of things (and the outputs of simple transformations against them) as
a cracking technology - we've seen CDs available with the hashes of all
possible passwords for a simple reverse lookup process.

Primes are sparse enough that if your PRNG only has 64 bits of seed, it
might be possible to generate the reverse lookup table.  Maybe not today,
but within the lifespan that the protected data still has value.

-----Burton


> -----Original Message-----
> From: Greg Kilford [mailto:greg_kilford () hotmail com]
> Sent: Friday, April 23, 2004 9:25 AM
> To: BStrauss () acm org; vuln-dev () securityfocus com
> Subject: RE: key material
>
>
> So u are suggesting 1024/2048 bits size/length for A to seed the PRNG and
> then after that the output stream O could be drawn to provide the
> bits for
> RSA 1024/2048 bits modulo key materials generation?
>
> A few of us are inclined towards this, but a few of my pals seem to think
> weirdly.  They feel that 64/128 or even 192 bits would have
> sufficed.  Their
> argument is that the symmetric and asymmetric crypto "strength"
> would means
> that such length/size of A would match up.  A few years back, Schneier
> commented in a paper on the comparison of crypto "strength" between
> symmetric and asymmetric key sizes (something like 80bits symm key is
> equivalent to 1024bits asymm RSA key).  But I really disagree that the
> crypto strength has anythin to do with RNG.  What does everyone think?
>
>
> > From: "Burton M. Strauss III" <BStrauss () acm org>
> > To: <vuln-dev () securityfocus com>
> > CC: "Greg Kilford" <greg_kilford () hotmail com>
> > Subject: RE: key material
> > Date: Fri, 23 Apr 2004 06:48:46 -0500
> >
> > Remember, while a PRNG may GENERATE more bits, the initial
> random pool caps
> > the total randomness.
> >
> > Suppose you generate 5 numbers using any PRNG you like.  If the seed is
> > only
> > 1 bit(0 or 1), there are only TWO patterns you will see.  Period.  If the
> > seed is two bits, there are 4 patterns, etc.
> >
> > This surfaced recently in some of the lottery machines - small seed space
> > and the machines were frequently reset - meaning that the 'quick pick'
> > tickets covered only a small % of the number space.
> >
> > -----Burton
> >
> > > -----Original Message-----
> > > From: Greg Kilford [mailto:greg_kilford () hotmail com]
> > > Sent: Thursday, April 22, 2004 12:29 PM
> > > To: vuln-dev () securityfocus com
> > > Subject: key material
> > >
> > >
> > > Hi everyone,
> > >
> > > I was juz discussing with my pals the other day on the
> > > appropriate initial
> > > input bit size to seed a PRNG of the structure below for it
> to be used
> > to
> > > generate the random bits for RSA key material of modulus 1024
> > > bits or 2048
> > > bits.  Anyone know what would be the ideal length/size of A so
> > > that there is
> > > sufficient entropy to generate the key material for RSA 1024/2048
> > > bits keys?
> > >
> > > A: Initial input seed of x bit size and fed into the 3DES x9.17
> > > PRNG in 64
> > > bit blocks.
> > > B: A constant key of 128 bits (112 bits effective).  Does not change
> > with
> > > each loop of output block O.
> > > C: Initialization vector - 64 bits size with initial fixed
> value and fed
> > > back with each loop.
> > > O: Output of 64 bit block with each loop for RSA 1024/2048
> key material.
> > > Initial total of x bits as seed
> > > (feeding in 64-bit block feed)
> > >             A
> > >             |
> > >            \|/
> > > x9.17 PRNG   V
> > > ----------------------
> > > |                    |
> > > |                    |<------ B (128bits with 112 bits effective)
> > > : Constant
> > > value for all loops
> > > |                    |
> > > |       3DES         |
> > > |                    |
> > > |                    |<-------
> > > |                    |       |
> > > ----------------------       |
> > >         |          |          | C (64 bit IV) : Initial fixed IV.
> > > Changed/feedback with every loop.
> > >         |          |          |
> > >         |          -----------|
> > >         |
> > >        \|/
> > >         V
> > >         O
> > > Output Random Stream
> > > (in 64 bit blocks)
> > >
> > > _________________________________________________________________
> > > MSN 8 helps eliminate e-mail viruses. Get 2 months FREE*.
> > > http://join.msn.com/?page=features/virus
>
> _________________________________________________________________
> The new MSN 8: advanced junk mail protection and 2 months FREE*
> http://join.msn.com/?page=features/junkmail