The Withdrawal of the A5/2 Encryption Algorithm
Interesting story of the withdrawal of the A5/2 encryption algorithm from GSM phones.
Entries Tagged "cryptanalysis"
Page 16 of 22
UAE Man-in-the-Middle Attack Against SSL
Who are these certificate authorities? At the beginning of Web history, there were only a handful of companies, like Verisign, Equifax, and Thawte, that made near-monopoly profits from being the only providers trusted by Internet Explorer or Netscape Navigator. But over time, browsers have trusted more and more organizations to verify Web sites. Safari and Firefox now trust more than 60 separate certificate authorities by default. Microsoft’s software trusts more than 100 private and government institutions.
Disturbingly, some of these trusted certificate authorities have decided to delegate their powers to yet more organizations, which aren’t tracked or audited by browser companies. By scouring the Net for certificates, security researchers have uncovered more than 600 groups who, through such delegation, are now also automatically trusted by most browsers, including the Department of Homeland Security, Google, and Ford Motorsand a UAE mobile phone company called Etisalat.
In 2005, a company called CyberTrust—which has since been purchased by Verizon—gave Etisalat, the government-connected mobile company in the UAE, the right to verify that a site is valid. Here’s why this is trouble: Since browsers now automatically trust Etisalat to confirm a site’s identity, the company has the potential ability to fake a secure connection to any site Etisalat subscribers might visit using a man-in-the-middle scheme.
EDITED TO ADD (9/14): EFF has gotten involved.
Successful Attack Against a Quantum Cryptography System
Quantum cryptography is often touted as being perfectly secure. It is based on the principle that you cannot make measurements of a quantum system without disturbing it. So, in theory, it is impossible for an eavesdropper to intercept a quantum encryption key without disrupting it in a noticeable way, triggering alarm bells.
Vadim Makarov at the Norwegian University of Science and Technology in Trondheim and his colleagues have now cracked it. “Our hack gave 100% knowledge of the key, with zero disturbance to the system,” he says.
[…]
The cunning part is that while blinded, Bob’s detector cannot function as a ‘quantum detector’ that distinguishes between different quantum states of incoming light. However, it does still work as a ‘classical detector’ recording a bit value of 1 if it is hit by an additional bright light pulse, regardless of the quantum properties of that pulse.
That means that every time Eve intercepts a bit value of 1 from Alice, she can send a bright pulse to Bob, so that he also receives the correct signal, and is entirely unaware that his detector has been sabotaged. There is no mismatch between Eve and Bob’s readings because Eve sends Bob a classical signal, not a quantum one. As quantum cryptographic rules no longer apply, no alarm bells are triggered, says Makarov.
“We have exploited a purely technological loophole that turns a quantum cryptographic system into a classical system, without anyone noticing,” says Makarov.
Makarov and his team have demonstrated that the hack works on two commercially available systems: one sold by ID Quantique (IDQ), based in Geneva, Switzerland, and one by MagiQ Technologies, based in Boston, Massachusetts. “Once I had the systems in the lab, it took only about two months to develop a working hack,” says Makarov.
Just because something is secure in theory doesn’t mean it’s secure in practice. Or, to put it more cleverly: in theory, theory and practice are the same; but in practice, they’re very different.
The paper is here.
More Skein News
Skein is my new hash function. Well, “my” is an overstatement; I’m one of the eight designers. It was submitted to NIST for their SHA-3 competition, and one of the 14 algorithms selected to advance to the second round. Here’s the Skein paper; source code is here. The Skein website is here.
Last week was the Second SHA-3 Candidate Conference. Lots of people presented papers on the candidates: cryptanalysis papers, implementation papers, performance comparisons, etc. There were two cryptanalysis papers on Skein. The first was by Kerry McKay and Poorvi L. Vora (presentation and paper). They tried to extend linear cryptanalysis to groups of bits to attack Threefish (the block cipher inside Skein). It was a nice analysis, but it didn’t get very far at all.
The second was a fantastic piece of cryptanalysis by Dmitry Khovratovich, Ivica Nikolié, and Christian Rechberger. They used a rotational rebound attack (presentation and paper) to mount a “known-key distinguisher attack” on 57 out of 72 Threefish rounds faster than brute force. It’s a new type of attack—some go so far as to call it an “observation”—and the community is still trying to figure out what it means. It only works if the attacker can manipulate both the plaintexts and the keys in a structured way. Against 57-round Threefish, it requires 2503 work—barely better than brute force. And it only distinguishes reduced-round Threefish from a random permutation; it doesn’t actually recover any key bits.
Even with the attack, Threefish has a good security margin. Also, the attack doesn’t affect Skein. But changing one constant in the algorithm’s key schedule makes the attack impossible. NIST has said they’re allowing second-round tweaks, so we’re going to make the change. It won’t affect any performance numbers or obviate any other cryptanalytic results—but the best attack would be 33 out of 72 rounds.
Our update on Skein, which we presented at the conference, is here. All the other papers and presentations are here. (My 2008 essay on SHA-3 is here, and my 2009 update is here.) The second-round algorithms are: BLAKE, Blue Midnight Wish, CubeHash, ECHO, Fugue, Grøstl, Hamsi, JH, Keccak, Luffa, Shabal, SHAvite-3, SIMD, and Skein. You can find details on all of them, as well as the current state of their cryptanalysis, here. NIST will select approximately five algorithms to go on to the third round by the end of the year.
In other news, we’re once again making Skein polo shirts available to the public. Those of you who attended either of the two SHA-3 conferences might have noticed the stylish black Skein polo shirts worn by the Skein team. Anyone who wants one is welcome to buy it, at cost. Details (with photos) are here. All orders must be received before October 1, and we’ll have all the shirts made in one batch.
Eavesdropping on Smart Homes with Distributed Wireless Sensors
“Protecting your daily in-home activity information from a wireless snooping attack,” by Vijay Srinivasan, John Stankovic, and Kamin Whitehouse:
Abstract: In this paper, we first present a new privacy leak in residential wireless ubiquitous computing systems, and then we propose guidelines for designing future systems to prevent this problem. We show that we can observe private activities in the home such as cooking, showering, toileting, and sleeping by eavesdropping on the wireless transmissions of sensors in a home, even when all of the transmissions are encrypted. We call this the Fingerprint and Timing-based Snooping (FATS) attack. This attack can already be carried out on millions of homes today, and may become more important as ubiquitous computing environments such as smart homes and assisted living facilities become more prevalent. In this paper, we demonstrate and evaluate the FATS attack on eight different homes containing wireless sensors. We also propose and evaluate a set of privacy preserving design guidelines for future wireless ubiquitous systems and show how these guidelines can be used in a hybrid fashion to prevent against the FATS attack with low implementation costs.
The group was able to infer surprisingly detailed activity information about the residents, including when they were home or away, when they were awake or sleeping, and when they were performing activities such as showering or cooking. They were able to infer all this without any knowledge of the location, semantics, or source identifier of the wireless sensors, while assuming perfect encryption of the data and source identifiers.
WPA Cracking in the Cloud
It’s a service:
The mechanism used involves captured network traffic, which is uploaded to the WPA Cracker service and subjected to an intensive brute force cracking effort. As advertised on the site, what would be a five-day task on a dual-core PC is reduced to a job of about twenty minutes on average. For the more “premium” price of $35, you can get the job done in about half the time. Because it is a dictionary attack using a predefined 135-million-word list, there is no guarantee that you will crack the WPA key, but such an extensive dictionary attack should be sufficient for any but the most specialized penetration testing purposes.
[…]
It gets even better. If you try the standard 135-million-word dictionary and do not crack the WPA encryption on your target network, there is an extended dictionary that contains an additional 284 million words. In short, serious brute force wireless network encryption cracking has become a retail commodity.
FAQ here.
In related news, there might be a man-in-the-middle attack possible against the WPA2 protocol. Man-in-the-middle attacks are potentially serious, but it depends on the details—and they’re not available yet.
EDITED TO ADD (8/8): Details about the MITM attack.
Cryptography Success Story
From Brazil: the moral, of course, is to choose a strong key and to encrypt the entire drive, not just key files.
Cryptanalysis of the DECT
New cryptanalysis of the proprietrary encryption algorithm used in the Digital Enhanced Cordless Telecommunications (DECT) standard for cordless phones.
Abstract. The DECT Standard Cipher (DSC) is a proprietary 64-bit stream cipher based on irregularly clocked LFSRs and a non-linear output combiner. The cipher is meant to provide confidentiality for cordless telephony. This paper illustrates how the DSC was reverse-engineered from a hardware implementation using custom firmware and information on the structure of the cipher gathered from a patent. Beyond disclosing the DSC, the paper proposes a practical attack against DSC that recovers the secret key from 215 keystreams on a standard PC with a success rate of 50% within hours; somewhat faster when a CUDA graphics adapter is available.
News.
Cryptography Broken on American Military Attack Video
Any ideas?
At a news conference at the National Press Club, WikiLeaks said it had acquired the video from whistle-blowers in the military and viewed it after breaking the encryption code. WikiLeaks released the full 38-minute video as well as a 17-minute edited version.
And this quote from the WikiLeaks Twitter feed on Feb 20th:
Finally cracked the encryption to US military video in which journalists, among others, are shot. Thanks to all who donated $/CPUs.
Surely this isn’t NSA-level encryption. But what is it?
Note that this is intended to be a discussion about the cryptanalysis, not about the geopolitics of the event.
EDITED TO ADD (4/13): It was a dictionary attack.
New Attack on Threefish
At FSE 2010 this week, Dmitry Khovratovich and Ivica Nikolic presented a paper where they cryptanalyze ARX algorithms (algorithms that use only addition, rotation, and exclusive-OR operations): “Rotational Cryptanalysis of ARX.” In the paper, they demonstrate their attack against Threefish. Their attack breaks 39 (out of 72) rounds of Threefish-256 with a complexity of 2252.4, 42 (out of 72) rounds of Threefish-512 with a complexity of 2507, and 43.5 (out of 80) rounds of Threefish-1024 with a complexity of 21014.5. (Yes, that’s over 21000. Don’t laugh; it really is a valid attack, even though it—or any of these others—will never be practical.)
This is excellent work, and represents the best attacks against Threefish to date. (I suspect that the attacks can be extended a few more rounds with some clever cryptanalytic tricks, but no further.) The security of full Threefish isn’t at risk, of course; there’s still plenty of security margin.
We have always stood by the security of Threefish with any set of non-obviously-bad constants. Still, a trivial modification—changing a single constant in the key schedule—dramatically reduces the number of rounds through which this attack can penetrate. If NIST allows another round of tweaks to the SHA-3 candidate algorithms, we will almost certainly take the opportunity to improve Skein’s security; we’ll change this constant to a value that removes the rotational symmetries that this technique exploits. If they don’t, we’re still confident of the security of Threefish and Skein.
And we’re always pleased to see more cryptanalysis against Threefish and Skein.
Sidebar photo of Bruce Schneier by Joe MacInnis.