[Cryptography] The hypothetical random number generator backdoor

Nico Williams nico at cryptonector.com
Wed Sep 25 16:31:15 EDT 2013


On Sep 25, 2013 8:06 AM, "John Kelsey" <crypto.jmk at gmail.com> wrote:
> On Sep 22, 2013, at 8:09 PM, Phillip Hallam-Baker <hallam at gmail.com> wrote:
> > Either way, the question is how to stop this side channel attack.
> > One simple way would be to encrypt the nonces from the RNG under a
> > secret key generated in some other fashion.
> >
> > nonce = E (R, k)
>
> This would work if you had a secure key I couldn't guess for k.  If
> the entropy is really low, though, I would still see duplicate outputs
> from time to time.  If the RNG has short cycles, this would also show
> up.

Note that Kerberos "confounds": it encrypts it's nonces for AES in CTS
mode (similar to CBC).  Confounding makes it harder to exploit a
backdoored RNG if the exploit is made easier by the ability to see RNG
outputs as nonces.  I'm not sure how much harder though: presumably in
the worst case the attacker has the victim's device's seed somehow
(e.g., from a MAC address, purchase records, ...), and can search its
output via boot and iteration counter searches (the details depend on
the PRNG construction, obviously).  Seeing an RNG output in the clear
probably helps, but the attacker could design the PRNG such that they
don't need to.

Now, there's a proposal to drop confounding for new cipher suites in
Kerberos.  Among other things doing so would improve performance.  It
would also make analysis of the new cipher suites easier, as they'd
match what other standard protocols do.

Of course, I'd rather implementations have a strong enough RNG and SRNG
-- I'd rather not have to care if some RNG outputs are trivially
available to attackers.  But if confounding is a net security
improvement for PRNG-only use cases (is it? it might depend on the PRNG
construction and boot-time seed handling), maybe we should keep it.

Thoughts?

Nico
-- 


More information about the cryptography mailing list