Leaking state

From: Joe C (jkc8289_at_bellsouth.net)
Date: 08/16/04 

Date: Mon, 16 Aug 2004 13:49:54 -0400

Suppose I have a PRNG that returns 32-bit integers, has good stastical
properties, but it returns some of it's internal state as it's "random"
output. Exactly which bits of the internal state are being returned is
non-determinable by the PRNG user without him knowing the internal state,
and varies with the current state of the system. Also, the number of bits
returned per round is a small but variable fraction of the internal system
size.

First question: Do I have an automatic weakness in my generator since the
user can see actual bits of the system, even though they can't determine
which bits they are seeing?

Seconc question: Assuming the answer to the first question is "yes, it is a
weakness" can I overcome this weakness by making the trivial modification to
the generator so that it returns two of it's original output XOR'd together.
My reasoning is that since each generator output appears totally random and
independent of preceeding output, then by combining 2 successive outputs the
user will have zero knowledge about any actual generator state bits. Is my
logic flawed?

I am aware that the output is often hashed in order to avoid the leaking
state problem, but this seems like a fairly expensive operation to tack on
to the base generator, especially if another simpler solution exists.

With my current system on my machine, I can encrypt ~8MB/sec, but with the
modification that effectively doubles the amount of output required, the
throughput drops to ~ 5MB/sec. However, if using this scheme works, then I
could change the equation by returning a much greater percentage of the
system per round without comprimising internal state, which would allow me
to deliver random numbers at a *much* higher rate.

Relevant Pages

  • Re: Leaking state
    ... Exactly which bits of the internal state are being returned is ... >> the generator so that it returns two of it's original output XOR'd ... then isn't your PRNG now simply have one more operation in it? ... bad thing" because an attacker would then know a specific portion of the ...
    (sci.crypt)
  • Re: Leaking state
    ... Exactly which bits of the internal state are being returned is ... > non-determinable by the PRNG user without him knowing the internal state, ... > the generator so that it returns two of it's original output XOR'd together. ... I've gotten roughly those numbers wuth AES in CTR mode. ...
    (sci.crypt)
  • Re: threads do not get cpa
    ... > Also note that some implementations of drand48require a mutex to ... > protect the internal state of the random number generator. ...
    (comp.sys.sgi.misc)
  • Re: random_seed
    ... The seed is the internal state of a pseudo-random number generator that ... the seed to the size specified by the first call because the standard ... allows each implementation to have internal state of different size. ...
    (comp.lang.fortran)
  • Re: Use of Pseudo Random Generators for One Time Pad?
    ... it's pretty easy to make a PRNG with a period as long as you desire. ... internal state to the user, you can reveal virtually no information about ... repeat length, there is nothing stopping you from increasing tht system size ... > work out a way to predict the sequence. ...
    (sci.crypt)