On April 1, I announced the Eighth Movie-Plot Threat Contest:
I want a movie-plot threat that shows the evils of encryption. (For those who don't know, a movie-plot threat is a scary-threat story that would make a great movie, but is much too specific to build security policies around. Contest history here.) We've long heard about the evils of the Four Horsemen of the Internet Apocalypse -- terrorists, drug dealers, kidnappers, and child pornographers. (Or maybe they're terrorists, pedophiles, drug dealers, and money launderers; I can never remember.) Try to be more original than that. And nothing too science fictional; today's technology or presumed technology only.
On May 14, I announced the five semifinalists. The votes are in, and the winner is TonyK:
November 6 2020, the morning of the presidential election. This will be the first election where votes can be cast from smart phones and laptops. A record turnout is expected.
There is much excitement as live results are being displayed all over the place. Twitter, television, apps and websites are all displaying the vote counts. It is a close race between the leading candidates until about 9 am when a third candidate starts to rapidly close the gap. He was an unknown independent that had suspected ties to multiple terrorist organizations. There was outrage when he got on to the ballot, but it had quickly died down when he put forth no campaign effort.
By 11 am the independent was predicted to win, and the software called it for him at 3:22 pm.
At 4 the CEO of the software maker was being interviewed on CNN. There were accusations of everything from bribery to bugs to hackers being responsible for the results. Demands were made for audits and recounts. Some were even asking for the data to be made publicly available. The CEO calmly explained that there could be no audit or recount. The system was encrypted end to end and all the votes were cryptographically anonymized.
The interviewer was stunned and sat there in silence. When he eventually spoke, he said "We just elected a terrorist as the President of the United States."
Logjam is a new attack against the Diffie-Hellman key-exchange protocol used in TLS. Basically:
The Logjam attack allows a man-in-the-middle attacker to downgrade vulnerable TLS connections to 512-bit export-grade cryptography. This allows the attacker to read and modify any data passed over the connection. The attack is reminiscent of the FREAK attack, but is due to a flaw in the TLS protocol rather than an implementation vulnerability, and attacks a Diffie-Hellman key exchange rather than an RSA key exchange. The attack affects any server that supports DHE_EXPORT ciphers, and affects all modern web browsers. 8.4% of the Top 1 Million domains were initially vulnerable.
One of the problems with patching the vulnerability is that it breaks things:
On the plus side, the vulnerability has largely been patched thanks to consultation with tech companies like Google, and updates are available now or coming soon for Chrome, Firefox and other browsers. The bad news is that the fix rendered many sites unreachable, including the main website at the University of Michigan, which is home to many of the researchers that found the security hole.
This is a common problem with version downgrade attacks; patching them makes you incompatible with anyone who hasn't patched. And it's the vulnerability the media isfocusingon.
Much more interesting is the other vulnerability that the researchers found:
Millions of HTTPS, SSH, and VPN servers all use the same prime numbers for Diffie-Hellman key exchange. Practitioners believed this was safe as long as new key exchange messages were generated for every connection. However, the first step in the number field sieve -- the most efficient algorithm for breaking a Diffie-Hellman connection -- is dependent only on this prime. After this first step, an attacker can quickly break individual connections.
We carried out this computation against the most common 512-bit prime used for TLS and demonstrate that the Logjam attack can be used to downgrade connections to 80% of TLS servers supporting DHE_EXPORT. We further estimate that an academic team can break a 768-bit prime and that a nation-state can break a 1024-bit prime. Breaking the single, most common 1024-bit prime used by web servers would allow passive eavesdropping on connections to 18% of the Top 1 Million HTTPS domains. A second prime would allow passive decryption of connections to 66% of VPN servers and 26% of SSH servers. A close reading of published NSA leaks shows that the agency's attacks on VPNs are consistent with having achieved such a break.
Remember James Bamford's 2012 comment about the NSA's cryptanalytic capabilities:
According to another top official also involved with the program, the NSA made an enormous breakthrough several years ago in its ability to cryptanalyze, or break, unfathomably complex encryption systems employed by not only governments around the world but also many average computer users in the US. The upshot, according to this official: "Everybody's a target; everybody with communication is a target."
The breakthrough was enormous, says the former official, and soon afterward the agency pulled the shade down tight on the project, even within the intelligence community and Congress. "Only the chairman and vice chairman and the two staff directors of each intelligence committee were told about it," he says. The reason? "They were thinking that this computing breakthrough was going to give them the ability to crack current public encryption."
And remember Director of National Intelligence James Clapper's introduction to the 2013 "Black Budget":
Also, we are investing in groundbreaking cryptanalytic capabilities to defeat adversarial cryptography and exploit internet traffic.
It's a reasonable guess that this is what both Bamford's source and Clapper are talking about. It's an attack that requires a lot of precomputation -- just the sort of thing a national intelligence agency would go for.
But that requirement also speaks to its limitations. The NSA isn't going to put this capability at collection points like Room 641A at AT&T's San Francisco office: the precomputation table is too big, and the sensitivity of the capability is too high. More likely, an analyst identifies a target through some other means, and then looks for data by that target in databases like XKEYSCORE. Then he sends whatever ciphertext he finds to the Cryptanalysis and Exploitation Services (CES) group, which decrypts it if it can using this and other techniques.
Ross Anderson wrote about this earlier this month, almost certainly quoting Snowden:
As for crypto capabilities, a lot of stuff is decrypted automatically on ingest (e.g. using a "stolen cert", presumably a private key obtained through hacking). Else the analyst sends the ciphertext to CES and they either decrypt it or say they can't.
The analysts are instructed not to think about how this all works. This quote also applied to NSA employees:
Strict guidelines were laid down at the GCHQ complex in Cheltenham, Gloucestershire, on how to discuss projects relating to decryption. Analysts were instructed: "Do not ask about or speculate on sources or methods underpinning Bullrun."
I remember the same instructions in documents I saw about the NSA's CES.
Again, the NSA has put surveillance ahead of security. It never bothered to tell us that many of the "secure" encryption systems we were using were not secure. And we don't know what other national intelligence agencies independently discovered and used this attack.
The good news is now that we know reusing prime numbers is a bad idea, we can stop doing it.
EDITED TO ADD: The DH precomputation easily lends itself to custom ASIC design, and is something that pipelines easily. Using BitCoin mining hardware as a rough comparison, this means a couple orders of magnitude speedup.
EDITED TO ADD (5/23): Good analysis of the cryptography.
EDITED TO ADD (5/24): Good explanation by Matthew Green.
On April 1, I announced the Eighth Movie Plot Threat Contest: demonstrate the evils of encryption.
Not a whole lot of good submissions this year. Possibly this contest has run its course, and there's not a whole lot of interest left. On the other hand, it's heartening to know that there aren't a lot of encryption movie-plot threats out there.
Anyone can design a cipher that he himself cannot break. This is why you should uniformly distrust amateur cryptography, and why you should only use published algorithms that have withstood broad cryptanalysis. All cryptographers know this, but non-cryptographers do not. And this is why we repeatedly see bad amateur cryptography in fielded systems.
The latest is the cryptography in the Open Smart Grid Protocol, which is so bad as to be laughable. From the paper:
Dumb Crypto in Smart Grids: Practical Cryptanalysis of the Open Smart Grid Protocol
Philipp Jovanovic and Samuel Neves
Abstract: This paper analyses the cryptography used in the Open Smart Grid Protocol (OSGP). The authenticated encryption (AE) scheme deployed by OSGP is a non-standard composition of RC4 and a home-brewed MAC, the "OMA digest'."
We present several practical key-recovery attacks against the OMA digest. The first and basic variant can achieve this with a mere 13 queries to an OMA digest oracle and negligible time complexity. A more sophisticated version breaks the OMA digest with only 4 queries and a time complexity of about 2^25 simple operations. A different approach only requires one arbitrary valid plaintext-tag pair, and recovers the key in an average of 144 message verification queries, or one ciphertext-tag pair and 168 ciphertext verification queries.
Since the encryption key is derived from the key used by the OMA digest, our attacks break both confidentiality and authenticity of OSGP.
Ross Anderson summarizes a meeting in Princeton where Edward Snowden was "present."
Third, the leaks give us a clear view of an intelligence analyst's workflow. She will mainly look in Xkeyscore which is the Google of 5eyes comint; it's a federated system hoovering up masses of stuff not just from 5eyes own assets but from other countries where the NSA cooperates or pays for access. Data are "ingested" into a vast rolling buffer; an analyst can run a federated search, using a selector (such as an IP address) or fingerprint (something that can be matched against the traffic). There are other such systems: "Dancing oasis" is the middle eastern version. Some xkeyscore assets are actually compromised third-party systems; there are multiple cases of rooted SMS servers that are queried in place and the results exfiltrated. Others involve vast infrastructure, like Tempora. If data in Xkeyscore are marked as of interest, they're moved to Pinwale to be memorialised for 5+ years. This is one function of the MDRs (massive data repositories, now more tactfully renamed mission data repositories) like Utah. At present storage is behind ingestion. Xkeyscore buffer times just depend on volumes and what storage they managed to install, plus what they manage to filter out.
As for crypto capabilities, a lot of stuff is decrypted automatically on ingest (e.g. using a "stolen cert," presumably a private key obtained through hacking). Else the analyst sends the ciphertext to CES and they either decrypt it or say they can't. There's no evidence of a "wow" cryptanalysis; it was key theft, or an implant, or a predicted RNG or supply-chain interference. Cryptanalysis has been seen of RC4, but not of elliptic curve crypto, and there's no sign of exploits against other commonly used algorithms. Of course, the vendors of some products have been coopted, notably skype. Homegrown crypto is routinely problematic, but properly implemented crypto keeps the agency out; gpg ciphertexts with RSA 1024 were returned as fails.
What else might we learn from the disclosures when designing and implementing crypto? Well, read the disclosures and use your brain. Why did GCHQ bother stealing all the SIM card keys for Iceland from Gemalto, unless they have access to the local GSM radio links? Just look at the roof panels on US or UK embassies, that look like concrete but are actually transparent to RF. So when designing a protocol ask yourself whether a local listener is a serious consideration.
On the policy front, one of the eye-openers was the scale of intelligence sharing -- it's not just 5 eyes, but 15 or 35 or even 65 once you count all the countries sharing stuff with the NSA. So how does governance work? Quite simply, the NSA doesn't care about policy. Their OGC has 100 lawyers whose job is to "enable the mission"; to figure out loopholes or new interpretations of the law that let stuff get done. How do you restrain this? Could you use courts in other countries, that have stronger human-rights law? The precedents are not encouraging. New Zealand's GCSB was sharing intel with Bangladesh agencies while the NZ government was investigating them for human-rights abuses. Ramstein in Germany is involved in all the drone killings, as fibre is needed to keep latency down low enough for remote vehicle pilots. The problem is that the intelligence agencies figure out ways to shield the authorities from culpability, and this should not happen.
The spooks' lawyers play games saying for example that they dumped content, but if you know IP address and file size you often have it; and IP address is a good enough pseudonym for most intel / LE use. They deny that they outsource to do legal arbitrage (e.g. NSA spies on Brits and GCHQ returns the favour by spying on Americans). Are they telling the truth? In theory there will be an MOU between NSA and the partner agency stipulating respect for each others' laws, but there can be caveats, such as a classified version which says "this is not a binding legal document." The sad fact is that law and legislators are losing the capability to hold people in the intelligence world to account, and also losing the appetite for it.
It's April 1, and time for another Movie-Plot Threat Contest. This year, the theme is Crypto Wars II. Strong encryption is evil, because it prevents the police from solving crimes. (No, really -- that's the argument.) FBI Director James Comey is going to be hard to beat with his heartfelt litany of movie-plot threats:
"We're drifting toward a place where a whole lot of people are going to be looking at us with tears in their eyes," Comey argued, "and say 'What do you mean you can't? My daughter is missing. You have her phone. What do you mean you can't tell me who she was texting with before she disappeared?"
"I've heard tech executives say privacy should be the paramount virtue," Comey said. "When I hear that, I close my eyes and say, 'Try to imagine what that world looks like where pedophiles can't be seen, kidnappers can't be seen, drug dealers can't be seen.'"
Come on, Comey. You might be able to scare noobs like Rep. John Carter with that talk, but you're going to have to do better if you want to win this contest. We heard this same sort of stuff out of then-FBI director Louis Freeh in 1996 and 1997.
This is the contest: I want a movie-plot threat that shows the evils of encryption. (For those who don't know, a movie-plot threat is a scary-threat story that would make a great movie, but is much too specific to build security policies around. Contest history here.) We've long heard about the evils of the Four Horsemen of the Internet Apocalypse -- terrorists, drug dealers, kidnappers, and child pornographers. (Or maybe they're terrorists, pedophiles, drug dealers, and money launderers; I can never remember.) Try to be more original than that. And nothing too science fictional; today's technology or presumed technology only.
Entries are limited to 500 words -- I check -- and should be posted in the comments. At the end of the month, I'll choose five or so semifinalists, and we can all vote and pick the winner.
Every year, the Director of National Intelligence publishes an unclassified "Worldwide Threat Assessment." This year's report was published two weeks ago. "Cyber" is the first threat listed, and includes most of what you'd expect from a report like this.
More interesting is this comment about information integrity:
Most of the public discussion regarding cyber threats has focused on the confidentiality and availability of information; cyber espionage undermines confidentiality, whereas denial-of-service operations and data-deletion attacks undermine availability. In the future, however, we might also see more cyber operations that will change or manipulate electronic information in order to compromise its integrity (i.e. accuracy and reliability) instead of deleting it or disrupting access to it. Decisionmaking by senior government officials (civilian and military), corporate executives, investors, or others will be impaired if they cannot trust the information they are receiving.
This speaks directly to the need for strong cryptography to protect the integrity of information.
This week, welearnedaboutan attack called "FREAK" -- "Factoring Attack on RSA-EXPORT Keys" -- that can break the encryption of many websites. Basically, some sites' implementations of secure sockets layer technology, or SSL, contain both strong encryption algorithms and weak encryption algorithms. Connections are supposed to use the strong algorithms, but in many cases an attacker can force the website to use the weaker encryption algorithms and then decrypt the traffic. From Ars Technica:
In recent days, a scan of more than 14 million websites that support the secure sockets layer or transport layer security protocols found that more than 36 percent of them were vulnerable to the decryption attacks. The exploit takes about seven hours to carry out and costs as little as $100 per site.
This is a general class of attack I call "security rollback" attacks. Basically, the attacker forces the system users to revert to a less secure version of their protocol. Think about the last time you used your credit card. The verification procedure involved the retailer's computer connecting with the credit card company. What if you snuck around to the back of the building and severed the retailer's phone lines? Most likely, the retailer would have still accepted your card, but defaulted to making a manual impression of it and maybe looking at your signature. The result: you'll have a much easier time using a stolen card.
In this case, the security flaw was designed in deliberately. Matthew Green writes:
Back in the early 1990s when SSL was first invented at Netscape Corporation, the United States maintained a rigorous regime of export controls for encryption systems. In order to distribute crypto outside of the U.S., companies were required to deliberately "weaken" the strength of encryption keys. For RSA encryption, this implied a maximum allowed key length of 512 bits.
The 512-bit export grade encryption was a compromise between dumb and dumber. In theory it was designed to ensure that the NSA would have the ability to "access" communications, while allegedly providing crypto that was still "good enough" for commercial use. Or if you prefer modern terms, think of it as the original "golden master key."
The need to support export-grade ciphers led to some technical challenges. Since U.S. servers needed to support both strong and weak crypto, the SSL designers used a "cipher suite" negotiation mechanism to identify the best cipher both parties could support. In theory this would allow "strong" clients to negotiate "strong" ciphersuites with servers that supported them, while still providing compatibility to the broken foreign clients.
And that's the problem. The weak algorithms are still there, and can be exploited by attackers.
Fixes are coming. Companies like Apple are quickly rolling out patches. But the vulnerability has been around for over a decade, and almost has certainly used by national intelligence agencies and criminals alike.
This is the generic problem with government-mandated backdoors, key escrow, "golden keys," or whatever you want to call them. We don't know how to design a third-party access system that checks for morality; once we build in such access, we then have to ensure that only the good guys can do it. And we can't. Or, to quote the Economist: "...mathematics applies to just and unjust alike; a flaw that can be exploited by Western governments is vulnerable to anyone who finds it."
Abstract: Revelations over the past couple of years highlight the importance of understanding malicious and surreptitious weakening of cryptographic systems. We provide an overview of this domain, using a number of historical examples to drive development of a weaknesses taxonomy. This allows comparing different approaches to sabotage. We categorize a broader set of potential avenues for weakening systems using this taxonomy, and discuss what future research is needed to provide sabotage-resilient cryptography.