Backdoor van a véletlenszám generátorban is

Az NSA 10 millió dollárt fizetett az RSA cégnek, hogy backdoort helyezzen el az egyik titkosítási eljárásuk véletlenszám generátorában, itt a lavinát kirobbantó Reuters cikk. Ebből:

RSA received $10 million in a deal that set the NSA formula as the preferred, or default, method for number generation in the BSafe software, according to two sources familiar with the contract.

Hogyan lehetséges ez technikailag? Nick Sullivan ex-Apple titkosítási szakértő elmagyarázza. Hogy ez miért érdekes? A véletlenszám generátor ismeretében hozzá lehet férni végeredményben a titkosított dokumentum tartalmához a kulcsok ismerete nélkül. Néhány példa a közelmúltból:

– A flaw in a random number generator allowed people to hijack Hacker News accounts.
– A broken random number generator in Android allowed attackers to hijack thousands of dollars worth of bitcoins.
– The version of OpenSSL on the Debian distribution of the Linux operating system had a random number generator problem that could allow attackers to guess private keys created on these systems.

És a lényeg:

One algorithm, a pseudo-random bit generator, Dual_EC_DRBG, was ratified by the National Institute of Standards and Technology (NIST) in 2007 and is attracting a lot of attention for having a potential backdoor. This is the algorithm that the NSA reportedly paid RSA $10 million in exchange for making it the default way for its BSAFE crypto toolkit to generated random numbers.


The amazing fact is that our toy random number generator described above is Dual EC_DRBG, almost exactly. It was published by the NSA with two “random” looking points P1 and P2. There is no indication of how these values were generated.

The values for the points P1 and P2 could have been chosen randomly or they could have been chosen with a deliberate relationship. If they were chosen deliberately, there is a backdoor. If they truly were chosen randomly, then finding the internal state is as difficult as breaking elliptic curve cryptography. Unfortunately, there is no way to identify if the two points were chosen together or randomly without either solving the elliptic curve discrete logarithm function, or catching the algorithm’s author with the secret backdoor value. This is the nature of a one-way trapdoor function.

The authors did not provide any proof of randomness for the two points P1 and P2. This could have easily been done by choosing P1 and P2 as outputs of a hash function, but they did not. This is just one of many flaws in the design of this algorithm.