Schneier on Security

Clive Robinson • March 7, 2015 6:19 AM

@ MarkH,

All Determanistic Random Bit Generators can be used as a back door one way or another, that much is the logical conclusion of “determanistic”. That is if a second party knows the key, the state, or one of the primes etc then it’s game over they can fully determine your next bit out of the generator.

For it to become a workable backdoor it must somehow leak sufficient information to the second party.

The problem with you saying,

I must challenge the quote from The Economist: “a flaw that can be exploited by Western governments is vulnerable to anyone who finds it.”

And then talking about the Dual_EC_DRBG is that you are confusing knowing that something can exist and showing it does exist.

We know it is possible to backdoor ALL determanistic generators, which the Economist referes to as “flaws”, what we don’t know is if it has actualy happened, thus it has not yet been found publicaly.

But even if it was found, is it actually a serious issue? No because any sensible crypto designer would know such a possability exists for any determanistic generator. Thus they would take steps to mitigate either the leaking of information or either the predictability or determanistic nature of the generator.

What raised red flags over dual EC was the very ham fisted behaviour of the NSA representative to NIST, and that RSA would have known that the generator would have needed mitigating, but chose not to. The third strike that tipped opinion was the large cash payment to RSA to make it not just the default generator, but also not particularly easy to change…

But the fact remains we know the generator has flaws, but importantly nobody has publicaly gone looking for them. Importantly they don’t need to there are better generators and mittigation is easy.

And that’s the important point as a back door hamstringing a random generator is not very effective or reliable because it is way to obvious and way to easy to get around.

The place to put backdoors is in the actual encryption chain, preferably where it’s next to impossible to mitigate.

Clive Robinson • March 8, 2015 12:04 PM

@ MikeA,

Or, of course, choice three: drop all methods of comunication and social connection, and go live in a cave until we have eaten the entire bat and bug population.

But will there be enough energy within walking distance of the cave to ensure they are all safely cooked, otherwise it might be a risky option 😉

Clive Robinson • March 8, 2015 2:52 PM

@ MarkH,

… deterministic RBGs are not inherently a vector for back- door compromise

Yes they are they are fully determanistic, go back and read the first two paragraphs of my post.

Also there is a lot of difference between an inherant weakness that has not yet been exploited and one that has been exploited, which is what paragraph two makes clear.

Further,

But that is not the same as a backdoor! If I can discover somebody’s symmetric encryption key (the internal state of their symmetric encryption process), I can read their traffic; that reality does not constitute a backdoor

It does if there is a processes or flaw by which the key or plain text is leaked.

Arguably using any block cipher in a simple code book mode is a backdoor, not because it leaks the key but because it leaks information on the plaintext, that can then be used to find the key –if practical– or the original plaintext identifing the source etc.

It’s why cipher system designers mitigate the issue by various methods such as cipher chaining, where either the plain text or ciphertext from previous blocks are mixed into either the current plaintext or ciphertext. These mitigations are now so generic we don’t think about why they are needed we just see them as standard modes to use a cipher in.

Importantly this mixing if done correctly adds a truely random element from the plain text which helps reduce the exploitable elements of the determanistic block cipher by adding uncertainty to the cipher output. A determanistic RNG does not have this simple but important mitigation.

So onto your second point,

Well, that’s an opinion. Some respected cryptographers, including Bruce, have opined more than once that the RBG is the preferred point of attack…

So have I, however the fact that it has in the past been prefered does not mean that doing it is “effective or reliable” or that it will remain prefered or even possible in the near future. Arguably with the hamfisted behaviour and the following debacle over Dual EC it’s probably nolonger prefered as a spotlight has been very vividly shone on that class of attack vectors.

The real reason it was prefered is down to the failings of people who design many commercial crypto systems, and either don’t mitigate for some reason a known weakness, or as RSA did chose to deliberately ignore it.

In part this is due to the failings of academia, in that although the problem with determanistic RNGs has been long known and certainly identified as a security issue back in the last century it’s not been given the prominance it deserves. Which means that software developers who have not undergone basic crypto specific training by practical cryptographers are often unaware of the issue.

Another issue is NIST standards, some are “descriptive” others “what must be done” whilst others are “what should be done as a minimum”. The AES standard is actually “descriptive” that is it accurately describes all the logical steps of how the block cipher should function. Thus any deviation, addition or subtraction will result in it not functioning. However the modes of AES are “what must be done” to be compatable with other implementations but they are effectivly generic and thus work with different block ciphers. Determanistic RNGs do not need to be compatible with other systems –unless they are inadvisably going to be used as stream ciphers etc– thus the standards fall in the “what should be done as a minimum” category. That is designers are free to make additions including mitigating obvious and known risks.

Which brings us back to,

For example, Dual_EC_DRBG could easily be modified in several ways to “close” the potential backdoor. For example, if the iteration output used the least significant half of the coordinate bits (instead of all but 16), it would apparently be infeasible to predict future outputs even with the presumed non-random Q value. There are other simple changes that would make a secure variant.

Any of your mitigations would close not just the suspected backdoor in this determanistic RNG but several others, without effecting the security or compatability with other systems. However if it was being used as a stream cipher none of the mitigations would be possible because it would break compatability. As for the number of bits v theoretical security issue and determanistic RNGs this is not new the idea was discussed in depth last century with the BBS generator and what went before it.

That said as you originaly pointed out, even without the mitigations currently it is in all probability secure against others other than it’s designers, however this can change at any point in time either by luck or considered and considerable effort, and we are unlikely to know when or where this first happens, if it has not happened already.

Which brings us back to why people should mitigate any determanistic RNG, it’s relativly trivial to do, it does not break compatability and with a little care it is very unlikely to weaken security whilst breaking any standards based backdoor.

Now the idea of a standards based backdoor in determanistic RNGs is well and truely out in the open, there is realy no excuse for designers not to add mitigation, and anybody not doing so should find people looking at them with incredulous stares as their design choices would be regarded as unprofessional.

That said those writing closed source software will no doubt carry on doing favours for the NSA or others in the darkness of their cubicals. It does not matter if it is done through ignorance or either accidently or deliberatly the result is the same security is lost and people will get hurt. Whilst this might appear as a recomendation for open source it’s not, it’s a recomendation for transparancy and sufficient verification. It just happens that both of these tend to be more easily accomplished with open source, and for most users impossible with closed source.

And when mitigation becomes general practice, backdooring determanistic RNGs will probably cease to be a prefered practice. A new prefered practice will no doubt arise, to join the legion of other attacks based on standards and protocols of which FREAK is just one. Whilst Bruce calls it a “security rollback” attack I’ve refered to such attacks frequently as “Fall back” attacks, which if you google this site you will find I have warned about on several occasions over a considerable period of time.

As in many things a common nomenclature would provide a common base line of agrement on the meaning of terms and thus make the lives of others easier and more harmonious.