[Cryptography] The hypothetical random number generator backdoor

[Phillip Hallam-Baker]

On Tue, Sep 24, 2013 at 10:59 AM, Jerry Leichter <leichter at lrw.com> wrote:

> On Sep 22, 2013, at 8:09 PM, Phillip Hallam-Baker <hallam at gmail.com>
> wrote:
> > I was thinking about this and it occurred to me that it is fairly easy
> to get a public SSL server to provide a client with a session key - just
> ask to start a session.
> >
> > Which suggests that maybe the backdoor [for an NSA-spiked random number
> generator] is of the form that ... you get a lot of nonces [maybe just one]
> from the random number generator ... and that allows the [next one to be
> predicted more easily or even the] seed to be unearthed.  One simple way
> [to stop this] would be to encrypt the nonces from the RNG under a secret
> key generated in some other fashion.
> >
> > nonce = E (R, k)
> >
> > Or hashing the RNG output and XORing with it
> >
> > nonce = R  XOR H(R)
> You shifted from "random value" to "nonce".  Given the severe effects on
> security that using a "nonce" - a value that is simply never repeated in a
> given cryptographic context; it may be predictable, even fixed - to a
> "random value", one needs to be careful about the language.  (There's
> another layer as well, partly captured by "unpredictable value" but not
> really:  Is it a value that we must plan on the adversary learning at some
> point, even though he couldn't predict it up front, or must it remain
> secret?  The random values in PFS are only effective in providing forward
> security if they remain secret forever.)
>
> Anyway, everything you are talking about here is *supposed* to be a random
> value.  Using E(R,k) is a slightly complicated way of using a standard
> PRNG:  The output of a block cipher in counter mode.  Given (a) the
> security of the encryption under standard assumptions; (b) the secrecy and
> randomness of k; the result is a good PRNG.  (In fact, this is pretty much
> exactly one of the Indistinguishability assumptions.  There are subtly
> different forms of those around, but typically the randomness of input is
> irrelevant - these are semantic security assumptions so knowing something
> about the input can't help you.)  Putting R in there can't hurt, and if the
> way you got R really is random then even if k leaks or E turns out to be
> weak, you're still safe.  However ... where does k come from?  To be able
> to use any of the properties of E, k itself must be chosen at random.  If
> you use the same generator as way use to find R, it's not clear that this
> is much stronger than R itself.  If you have some assured way of getting a
> random k - why not use it for R itself?  (This might be worth it if you can
> generate a k you believe in but only at a much lower rate than you can
> generate an R directly.  Then you can "stretch" k over a number of R
> values.  But I'd really think long and hard about what you're assuming
> about the various components.)
>
> BTW, one thing you *must not* do is have k and the session key relate to
> each other in any simple way.
>
> For hash and XOR ... no standard property of any hash function tells you
> anything about the properties of R XOR H(R).  Granted, for the hash
> functions we generally use, it probably has about the same properties; but
> it won't have any more than that.  (If you look at the structure of classic
> iterated hashes, the last thing H did was compute S = S + R(S), where S was
> the internal state and R was the round function.  Since R is usually
> invertible, this is the only step that actually makes the whole thing
> non-invertible.  Your more-or-less repetition of the same operation
> probably neither helps more hinders.)
>
> At least if we assume the standard properties, it's hard to get R from
> H(R) - but an attacker in a position to try a large but (to him) tractable
> number of guesses for R can readily check them all.  Using R XOR H(R) makes
> it no harder for him to try that brute force search.  I much prefer the
> encryption approach.
>


There are three ways a RNG can fail

1) Insufficient randomness in the input
2) Losing randomness as a result of the random transformation
3) Leaking bits through an intentional or unintentional side channel

What I was concerned about in the above was (3).

I prefer the hashing approaches. While it is possible that there is a
matched set of weaknesses, I find that implausible.

-- 
Website: http://hallambaker.com/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20130924/f339bd6b/attachment.html>