Don't Trust the Math (2013)

Counterpoint to Bruce Schneier: Don't "Trust the Math"

Bruce has told us a few times we can trust the math, if not the code in the cryptosystems. This slogan sounds really nice and all. It's only problem is that it's a BAD idea that creates a false sense of security for that aspect of things. It's also meaningless with some crypto constructs when they become code.

The simple truth is:

1. Computers don't run math. They run *code*. And it may or may not implement the math spec.

2. Math pro's make plenty of mistakes. And cryptographers keep giving us different advice over time, so I think they're not in the "infallible" category themselves. ;)

Potential Problems With The Math

1. Relies on unsound formalism. If the underlying logic/tool is unsound, then all proofs or constructions on top of it might be incorrect.

2. Math model doesn't reflect reality. Our models must reflect what's actually going to happen or their properties are kinda useless, yes? This might come from over-approximation, under-approximation, an error class I can't think of right now, or even outright deception.

3. Math looks good but is simply wrong. This has happened many times in the math field, including with crypto. They thought their theory, proof, construction, etc was correct/secure and it wasn't. It often takes a long time for the peer review process to catch the math errors even when many people see the theory/proof. More disconcerting, some problems might be subtle, require new analysis techniques, etc.

4. Poor problem catching. Building on 3, I originally learned this from Bruce's adage that almost anyone can design something they can't beat themselves. If experienced flaw finders haven't looked at the math, we have no way of knowing if it hides a flaw. Like with open source, the mere possibility of peer review doesn't mean a bunch of people were looking at the math for problems.

Making Math More Trustworthy

So, for those who don't find mathematicians infallible, here's some abstract solutions to manage the risk of math:

1. Use sound formalisms and theories.

2. Model all security critical aspects of operation when forming arguments of correctness and/or security.

3. Use only tried and true theories, tools, lemmas, etc. Although risk still exists, reducing the amount of unknowns and/or building on vetted work reduces the risk.

4. The math must be vetted by a diverse-thinking set of people who are experts in both math and the domain it applies to.

*Only then* can you trust the math. Then you have to implement it correctly as computers run code, not math. (evil grin) The code is essentially a concrete version of the math. Its properties must correspond to the properties of the math model or else the math may barely be relevant. Informal methods dominate this area for better or worse (often worse). Formal specification/verification of code is steadily growing in capability but still not the norm. So every implementation will have "hand waiving" arguments to get from the math to the 1's and 0's.

Lesson from the NSA?

Even Orange Book A1 security engineering didn't fully trust the math of a given algorithm: it combined math specs, English specs, math security policy, math proofs that specs met security policy, strong code correspondence to math spec, covert channel analysis, functional testing, hardware testing, pen testing, and strong lifecycle management. That's what the NSA required for a given system or software before they'd trust it. Over time, security requirements for a secure system or implementation have only increased. I see no reason to trade such rigorous vetting processes for blind faith in cryptographers' math constructions.

The Good News

Good news is that cryptographers aren't as overconfident as they seem. They're careful, thorough and their math has improved over time. There are tools available that seem pretty sound. Certain aspects of crypto have been very thoroughly vetted and analyzed. Bruce has contributed to such work, which I actually use. There have been more books over time on how to correctly implement crypto. There's plenty of academics worldwide looking into algorithms, hardware issues, etc. There's also quite a few constructions with formal proofs of security, also being vetted.

So, it's mostly good news for us at least for the basics like ciphers, hashes, & signing. The rest needs more work on the math and code sides. It's the strong design and vetting choices that result in math you can *trust.* It's strong and secure implementation choices that result in math you can *use.* And anyone wanting truly secure crypto needs to look at everything from the abstract theory itself all the way to how its internal components interact with a cache then down to analogue and RF components and environment/people that system operates in. Doing all this, you're not really trusting the math: you're trusting a total process & the product that results from it.

Note: Peter Gutmann, another math crypto guru, wrote the definitive paper (below) on problems that occur when math and software meet. Goes to show that these problems have been known for a long time although mathematicians don't like to talk about them so much.

http://www.cypherpunks.to/~peter/04_verif_techniques.pdf

Original posted on Schneier's blog October 2013. Revised for quality and clarity.

Nick P.
Security Engineer/Researcher
(High-assurance and anti-nation-state focus)