2
$\begingroup$

I was watching Computerphile's "Magic 'Nothing Up My Sleeve' Numbers" video where Dr. Mike Pound reasons that the numbers used to create cryptographic functions should not arouse suspicion or contain hidden properties, because doing otherwise would introduce vulnerabilities into the algorithm.

I'm having difficulty conceptualizing how a nefarious agent, N, would exploit numbers that fail to satisfy the nothing-up-my-sleeve criteria.

The scenario I have in mind goes something like this: N proposes numbers for the basis of a cryptographic function, numbers that contain hidden properties that only N knows about. N goes away on vacation and when he returns to the lab, he finds his team has created a cipher in his absence; he wasn't there for the processes that followed, but what he does know is that his numbers laid the foundation. (I realize the case is probably naive, but hopefully it shows the bridge that I'm trying to build between non-nothing-up-my-sleeve numbers and exploitation.)

How would N's knowledge of what's hidden in these numbers allow him to attack the cipher? How would such an attack play out?

Improve this question
$\endgroup$

4 Answers 4

Reset to default
2
$\begingroup$

Here is an example that I like: Malicious SHA-1.

The researchers took standard SHA-1 and changed only the four 32-bit "nothing up my sleeve numbers".

They were crafted in such a way that collisions could be generated much more easily.

This qualifies as a backdoor because a collision is only easier if the attacker knows the particular differential to use, which they would need to already have knowledge of or discover themselves.

Improve this answer
$\endgroup$
2
$\begingroup$

It could be, for example, that this $N$ is a specially crafter prime number, that looks random and safe according to the NIST recommendations, yet discrete logarithms modulo $N$ can be solved considerably more efficiently due to its hidden structure. An attack of this type has been demonstrated last year at Eurocrypt in this paper; it uses a random-looking prime with a hidden structure that makes it especially sensitive to the SNFS algorithm. The team could solve discrete logarithms with respect to a $1024$-bit prime, while the current record for 'normal' primes is 768 bits.

Improve this answer
$\endgroup$
0
$\begingroup$

In your example, you have probably obfuscated the problem sufficiently far that nobody will be able to provide you an example of how an exploit could occur in that fashion.

For a more practical example, consider Dual_EC_DRBG, an algorithm based on elliptic curves. It was in NIST SP 800-90A for quite some time before being revoked. In the mean time, it was shown that that particular algorithm could be vulnerable in a way that nobody could detect except the creators of Dual_EC_DRBG.

You can read the article for the specifics. The way a number could be exploited is always quite specific to the algorithm, so you're not going to find one general purpose pattern which all number follow. Dual_EC_DRBG has a unique advantage of being a well documented example where mathematicians have shown how one could use a backdoor to weaken the encryption.

The real issue is also captured in Dual_EC_DRBG: it's almost impossible to prove that such a backdoor exists. It puts enormous onus on the crypto community to ferret out any possible issues. It is far simpler to choose a nothing-up-my-sleeve number and bypass the whole fiasco.

Improve this answer
$\endgroup$
3
  • $\begingroup$ How could the creators of DUAL_EC_DRBG be confident that no one would detect the backdoor sooner? $\endgroup$
    – user56586
    Mar 13, 2018 at 3:06
  • $\begingroup$ They couldn't be sure. And in the case of du_ec_dbrg, they failed (if they indeed did). But if you think about it, hiding important information in a pile of numbers is literally the heart of encryption, so these designers are rather good at it. $\endgroup$
    – Cort Ammon
    Mar 13, 2018 at 3:16
  • $\begingroup$ @orbuculum: actually, the existence of the backdoor was actually detected fairly early. What is unique about DUAL_EC_DRBG is that the backdoor cannot be exploited unless you were the one the pick the internal parameters that DUAL_EC_DRBG used. $\endgroup$
    – poncho
    Mar 13, 2018 at 13:16
0
$\begingroup$

With respect, you're suffering from a logical fallacy called "Absence of Evidence" which itself is evidenced within your first two paragraphs.

...should not arouse suspicion...

I'm having difficulty conceptualizing how...

The fallacy goes like this: you don't have to be able to work out how to attack a construct. Neither does anyone else. Just because a construct can't be attacked by you /others, doesn't mean that the developers can't. And if those developers are some of the best cryptographers on the planet with huge budgets, that might be likely. This is especially true in the ever increasingly complex algorithms like elliptical curves and post quantum lattices. No evidence does not constitute proof. We would constantly have to prove our innocence otherwise, and would be considered guilty if we couldn't.

But it can raise suspicions. And in cryptography as in banking, a suspicion alone can sink a product. The world was right in it's suspicions about Dual_EC_DRBG, but wrong about the NSA's refinement of DES but which was initially highly suspect.

Hence suspicion is eliminated by use of ever more flamboyant nothing up my sleeve numbers like lottery results for the Million Dollar Curve, deriving them from the US Declaration of Independence or the names of the planets. These (perhaps crazy) ideas for numbers serve to create the necessary disassociation between variable initialisation and the algorithm's core principles.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.