I wanted to title this “CBC mode in the AES implementation on the iPhone isn’t as effective as it could be” but that was a bit too long. Bob Rudis forwarded this post, “AES on the iPhone is broken by Default” to me via twitter this morning and I wanted to write up something quick on it because I responded “premise is faulty in that write up” and this ain’t gonna fit in 140 characters. Here is the premise I’m talking about:
In order for CBC mode to perform securely, the IV must remain impossible for the attacker to derive or predict.
This isn’t correct. In order for CBC mode to be effective the initialization vector (IV) should be unique (i.e. random), preferably per individual use. To correct the statement: In order for AES to perform securely, the key must remain impossible for the attacker to derive or predict. There is nothing in the post that makes the claim that the key is exposed or somehow able to be derived or predicted.
Here’s the thing about IV’s: they are not secret. If there is a requirement to keep an IV secret, the cryptosystem is either designed wrong or has some funky restrictions and I’ll be honest, I’ve seen both. In fact, the IV is so not secret, the IV can be passed in the clear (unprotected) along with the encrypted message and it does not weaken the implementation. Along those lines, there are critical cryptosystems in use that don’t use IV’s. For example, some financial systems leverage ECB mode which doesn’t use an IV (and has it’s own problems). Even a bad implementation of CBC is better than ECB. Keep that in mind because apparently ECB is good enough for much of the worlds lifeblood.
So what’s the real damage here? As I said in order for CBC to be effective, the IV should not be reused. If it is reused (as it appears to be on the implementation in the iPhone Nadim wrote about), we get a case where an attacker may start to pull out patterns from the first block. Which means if the first block contains repeatable patterns across multiple messages, it may be possible to detect that repetition and infer some type of meaning. For example, if the message started out with the name of the sender, a pattern could emerge (across multiple encrypted messages using the same key and IV) in the first block that may enable some inference as to the sender on that particular message.
Overall, I think the claim of “AES is broken on the iPhone” is a bit overblown, but it’s up to the interpretation of “broken”. If I were to rate this finding on a risk scale from “meh” to “sky is falling”, off the cuff I’d say it was more towards “meh”. I’d appreciate this fixed from apple at some point… that is, if they get around to it and can squeeze it in so it doesn’t affect when I can get an iPhone 5… I’d totally apply that patch. But I certainly wouldn’t chuck my phone in the river over this.
I have two geek-loves, information risk analysis and cryptography. In many ways the two are polar opposite because cryptography is at its core, binary math functions. Data is either enciphered and deciphered correctly or it’s not. Signatures either pass or fail verification. Cryptography never makes use of Monte Carlo simulations and certainly never has “medium” outcomes.
But let’s be honest, that is theoretical cryptography. In the real world cryptography is drenched in uncertainties because the problem isn’t the math. The problem is that we are implementing this this math on the same foundation as the rest of our fallible security controls. Because of this shaky foundation, there is no binary pass/fail cryptography in the real world… it’s all about understanding the risks within the cryptosystems.
But let me back up and talk about the (false) perceptions of the math. Cryptography deals with some really big stinking numbers, and we as human processors fail to correctly understand these large values. One purpose I have here is to frame some of these big numbers into something we can begin to fathom. Without the key itself, it is so unlikely to break modern ciphers that it should be considered impossible in decision making and we should focus elsewhere.
Not Just Numbers, Big F’n Numbers
When talking about large numbers and improbable events, it’s natural to refer to the lottery. The “game” that has been politely referred to as the “tax on the mathematically challenged”. At first I was thinking that people may not know the odds, because surely if people knew the chances of winning the jackpot in the Powerball is 1 in 195,249,054 they wouldn’t donate to the cause. But that’s not the case, because those odds are clearly posted. I think it’s more that people can’t understand what 195 million looks like. People are incapable of wrapping their head around what that number signifies and how unlikely pulling 1 out 195 million truly is. I think most people just here “it’s possible” and fail to comprehend the (lack of) probability.
There is a better chance of getting struck by lightening… twice, and there are plenty of other relative comparisons. What if people knew that they would have a better chance of finding a four-leaf clover on their first attempt then winning the lottery? What if I said they’d have a better chance of finding two four-leaf clovers on the first two attempts? I wonder if people would shell out a dollar for two chances at finding two four-leaf clovers in a field for an early-retirement reward.
Now what if I start talking about cryptography and change those odds to something like 1 in 21,267,647,932,558,653,966,460,912,964,485,513,216? Because those are the odds of picking the winning AES 128 bit lottery ticket. If we can’t fathom 195 million, how can we possibly think of that number in context? That number is 38 digits long!
In an attempt to put this into perspective, let’s assume we had access to the Ohio Supercomputer Center and their massive supercomputer there. It’s capable of 75 teraflops (that’s 75 trillion instructions per second). Now let’s pretend that we were able to start it counting (1, 2, 3 etc) at the birth of the universe (estimated at 13.7 billion years ago). So that exactly 1 second after the big bang, it has already counted to 75,000,000,000,000. Where would we be today?
86,400 seconds in a day * 366 days a year * 13.7 billion years * 75 teraflops =
That number is 32 digits long, not even close. Keep in mind also this process would just count through the possible key values, it would take quite a bit more time to test for a correct key. I don’t want to even compute the probability in lightning strikes. Is it enough to say it’s ah, um… really stinking improbable to guess, or even attempt to brute force with the processing power we have today?
There is always a secret
This one of the main reasons that managing keys as well as the other security controls are much more important than all that math stuff. It’s much more likely that an adversary will simply try to get a copy of a key, or otherwise work around the cryptography, rather than gain access to the Ohio supercomputer. As Cryptologist Whitfield Diffie said:
“If breaking into Web sites, stealing identities or subverting critical infrastructure required breaking AES or elliptic-curve cryptosystems, we would not be complaining about cybersecurity.”
The line between the various data protection controls eventually blur together only differentiated by their varying degrees of obfuscation and assumptions. We’ve got the math, and it’s so improbable to break it we can think of it as impossible. It’s the other parts of our systems that we have to focus on like the key management. But we have to realize that encryption is built on key management and key management faces the same problems as our other security controls since it is build on the same exact foundation. There is too much mystery and misperception around that relatively simple concept.
But it’s not just encryption that we have misperception on, other technologies that promise to do good, like tokenization also fall prey to this problem. All we’re doing is shifting around the secret within our existing framework of controls. With encryption we shift the secret to the key and subsequently shift it to the access control around the key. If there is a nervousness about exposing the key itself, we can supply some type of service to encrypt/decrypt, but then we’re just shifting the secret to the access control on the service. Just as with a technology like tokenization, we’re shifting the secret to the token server, and subsequently the secret gets shifted to the access control on the tokenization service. The only real difference between those is our perception of them.
May 5th of this year, I gave a presentation at the 2010 IEEE Key Management Summit in Lake Tahoe and the slides and videos are being posted online. My presentation can be viewed in High-Def (400M) or the usable (200M) version. This conference was all about key management and crypto stuff.
I talked about a flaw in cryptographic design principles.
Kirckhoffs wrote several principles in 1883 on designing cryptosystems for military applications, his second principle is the most enduring:
It must not be required to be secret, and it must be able to fall into the hands of the enemy without inconvenience.
Which basically says that secrets should be in the right place and not designed into the system because the enemy will eventually figure it out. This was greatly simplified by Claude Shannon when he said “The enemy knows the system” (around the 1940’s best I can tell). It really gets to the point that adversaries are motivated to dig in and uncover how things work. We don’t invent our own algorithm and we should assume everyone is smarter than us. This is great advice but we, as an industry, routinely fail to follow this simple design principle. I give some examples in my talk of projects I’ve worked on that don’t heed this guidance.
But I’ve also found products that met Shannon’s Maxim and yet still had security problems. They assumed everyone was smarter and not just adversaries. Which results in an incorrect assumption that administrators and users share the same passion and motivation towards the solution as adversaries.
I wanted to keep Shannon’s maxim because we still need to learn that lesson, we need to understand how to handle secrets and where to put our trust. But we also need to account for the motivation of administrators, operators and users, which generally is not security. To that end, I created an updated maxim:
The enemy knows the system, and the allies do not.
Repeat it to yourself. It’s short enough to memorize, it’s mobile enough to carry it around and whip it out on a moments notice. This acknowledges that the people configuring the system care a lot more about making it operational then they do about making it secure. They are tasked with delivering on some other primary task: enabling email, setting up a service for business clients. Security concerns are secondary and often aren’t discovered until much later, even then it was probably the security teams fault.
As we design our solutions, cryptographic or not, we need to account for this motivation, we need to build security options to align with the operational options. We need to understand that people aren’t motivated to evaluate all the options and pick the best, they are motivated to pick the first option that works and move on. That realization means that if we list rot13 as a viable encryption algorithm, someone, somewhere will select it and operate that way.
Sometimes this means taking away options. What would happen if every browser just failed for an invalid certificate? What if we didn’t assume the user could read x.509 and just simply failed… how quickly would providers figure out how to create and maintain valid certificates? How much would companies invest in maintaining certificates if the service itself depended on it? Now, I’m not suggesting this is a solution to the PKI/X.509/SSL problem, just that there are opportunities to align security goals with operational goals and we should seek those out, even create those instances.