Re: OpenBSD-2.9 random devices (fwd)

[Andreas Gunnarsson <andreas_(_at_)_crt_(_dot_)_se>]

On Sat, 29 Sep 2001, June Carey wrote:

> >- If one bit of entropy is weak that weakness is concentrated to one bit
> >   of output instead of spread out as when using a cryptographically secure
> >   hash.
>
> One-time-pad is a cryptographically secure hash.

No. A one-time-pad is an encyption method that is secure in an information
theoretic sense. If a message is encrypted with an OTP, an attacker will
not be able to find out anything except the fact that a message was sent
and the length of that message no matter how much time and computational
power is spent.

A cryptographically secure hash on the other hand has the following
qualities:
1) Flipping one bit of the input flips on an average half of the output
   bits.
2) To know which output bits are affected by 1), all input bits must be
   known.
3) It is computationally hard to find an input with a given output.
4) Given one input, it is computationally hard to find any other input
   that gives the same output.
(I hope I didn't forget anything)

A hash function takes one input parameter. An encryption function (e.g.
OTP) requires two; data and key. If you try to make a hash funtion out of
XOR by splitting the input in half and XOR it with itself, none of the
requirements for a cryptographically secure hash function will be
fulfilled.

OTP is provably secure in an informational theoretic sense because:
A) The key is as long as the message
B) All keys are equally probable
This means that all decrypted messages are equally probable from the OTP
point of view. Even if an attacker guesses a key, the encryption algorithm
does not give any hint whether the key is correct or not.

Note that any bias in the key generation forces the system to be non-OTP.
Even a simple condition like
'if (key == 0x0000000...) then generate_new_key();'
which gets rid of the trivial key that encrypts any input to itself, makes
the system non-OTP. If you can not prove that all keys are equally
probable, the system is not an OTP. Since it is not known today whether it
is actually possible to generate true randomness (through e.g. quantum
mechanical processes like particle decay etc), it is not known whether it
is actually possible to create an OTP system at all. OTP systems are
therefore only theoretic constructions, and anyone who claims to have
obtained OTP security in practice must therefore either be a fraud or have
misunderstood the concept, unless they have made some major break through
in physics.

> >- An attacker who can affect the input entropy has deterministic control
> >   over the output without knowing the entire internal state.
>
> Well, thats always going to be a problem.

No. If you use a cryptographically secure hash function, you can not
predict any output bit with a higher probability than any other bit
without knowing the entire internal state of the PRNG. No matter how much
'known entropy' you feed the PRNG, it won't lower the quality of the
output.

> The reason being one-time-pad is a "perfect" one-way hash and is very fast.
> MD5 is not a "perfect" or "guaranteed" one-way hash.

Well, OTP is a (theroretcal) system for encryption and not a one-way hash
at all. It does not possess any of the qualities of a cryptographically
secure hash. Granted, MD5 is not proven to be a cryptographically secure
hash either, but it is at least not trivially broken for that purpose in
contrary to XOR which I assume you mean when you say OTP.

In order to obtain OTP security you need a perfect entropy source that can
generate as much output data as needed. If you had one of those, why not
just use that as your RNG?

>From reading your comments though, I think I first misunderstood what you
wanted to do. I now think you want to do the following:
* Maintain two arc4 PRNG:s, each with its own internal state.
* When one bit of output is requested, get one bit of output from each
  arc4 PRNG and output the XOR of those bits.
* Each new bit of entropy is used to stir the internal state of oe of the
  arc4 PRNGs in a round-robin fashion.

Is this correct?

If this is what you mean, you will need to operate two arc4 PRNGs instead
of one MD5 one, and each one will have access to only half the entropy. I
do not find it obvious that two arc4 based PRNGs would give better
security or performance than one MD5 based PRNG fed with twice the
entropy. Do you have any reference to any research paper that makes this
claim?

   Andreas

--