Entries Tagged "cryptanalysis"
Page 18 of 21
NASA Using 1960s Cryptanalysis Techniques
Well, sort of.
This paper from the Goddard Space Center, “NiCd Space Battery Test Data Analysis Project, Phase 2 Quarterly Report, 1 Jan. – 30 Apr. 1967,” uses “cryptanalytic techniques”—some sort of tri-gram frequency analysis, I think—to ferret out hidden clues about battery failures.
It’s hard to imagine non-NSA cryptography in the U.S. from the 1960s. Basically, it was all alphabetic stuff. Even rotor machines were highly classified, and absolutely nothing was being done in binary.
KeeLoq Broken
There’s been a lot of hype, but finally there’s a good article about the cryptanalysis of the KeeLoq electronic car-door entry system.
Presentation here.
Interview with WEP Attack Researchers
They explain how their attack on the 802.11 wireless security protocol works.
Breaking WEP in Under a Minute
WEP (Wired Equivalent Privacy) was the protocol used to secure wireless networks. It’s known to be insecure and has been replaced by Wi-Fi Protected Access, but it’s still in use.
This paper, “Breaking 104 bit WEP in less than 60 seconds,” is the best attack against WEP to date:
Abstract:
We demonstrate an active attack on the WEP protocol that is able to recover a 104-bit WEP key using less than 40.000 frames with a success probability of 50%. In order to succeed in 95% of all cases, 85.000 packets are needed. The IV of these packets can be randomly chosen. This is an improvement in the number of required frames by more than an order of magnitude over the best known key-recovery attacks for WEP. On a IEEE 802.11g network, the number of frames required can be obtained by re-injection in less than a minute. The required computational effort is approximately 2^20 RC4 key setups, which on current desktop and laptop CPUs in negligible.
More AACS Cracking
Slowly, AACS—the security in both Blu-ray and HD DVD—has been cracked. Now, it has been cracked even further:
Arnezami, a hacker on the Doom9 forum, has published a crack for extracting the “processing key” from a high-def DVD player. This key can be used to gain access to every single Blu-Ray and HD-DVD disc.
Previously, another Doom9 user called Muslix64 had broken both Blu-Ray and HD-DVD by extracting the “volume keys” for each disc, a cumbersome process. This break builds on Muslix64’s work but extends it—now you can break all AACS-locked discs.
As I have said before, what will be interesting to watch is how well HD DVD and Blu-ray recover. Both were built expecting these sorts of cracks, and both have mechanisms to recover security for future movies. It remains to be seen how well these recovery systems will work.
A New Secure Hash Standard
The U.S. National Institute of Standards and Technology is having a competition for a new cryptographic hash function.
This matters. The phrase “one-way hash function” might sound arcane and geeky, but hash functions are the workhorses of modern cryptography. They provide web security in SSL. They help with key management in e-mail and voice encryption: PGP, Skype, all the others. They help make it harder to guess passwords. They’re used in virtual private networks, help provide DNS security and ensure that your automatic software updates are legitimate. They provide all sorts of security functions in your operating system. Every time you do something with security on the internet, a hash function is involved somewhere.
Basically, a hash function is a fingerprint function. It takes a variable-length input—anywhere from a single byte to a file terabytes in length—and converts it to a fixed-length string: 20 bytes, for example.
One-way hash functions are supposed to have two properties. First, they’re one-way. This means that it is easy to take an input and compute the hash value, but it’s impossible to take a hash value and recreate the original input. By “impossible” I mean “can’t be done in any reasonable amount of time.”
Second, they’re collision-free. This means that even though there are an infinite number of inputs for every hash value, you’re never going to find two of them. Again, “never” is defined as above. The cryptographic reasoning behind these two properties is subtle, but any cryptographic text talks about them.
The hash function you’re most likely to use routinely is SHA-1. Invented by the National Security Agency, it’s been around since 1995. Recently, though, there have been some pretty impressive cryptanalytic attacks against the algorithm. The best attack is barely on the edge of feasibility, and not effective against all applications of SHA-1. But there’s an old saying inside the NSA: “Attacks always get better; they never get worse.” It’s past time to abandon SHA-1.
There are near-term alternatives—a related algorithm called SHA-256 is the most obvious—but they’re all based on the family of hash functions first developed in 1992. We’ve learned a lot more about the topic in the past 15 years, and can certainly do better.
Why the National Institute of Standards and Technology, or NIST, though? Because it has exactly the experience and reputation we want. We were in the same position with encryption functions in 1997. We needed to replace the Data Encryption Standard, but it wasn’t obvious what should replace it. NIST decided to orchestrate a worldwide competition for a new encryption algorithm. There were 15 submissions from 10 countries—I was part of the group that submitted Twofish—and after four years of analysis and cryptanalysis, NIST chose the algorithm Rijndael to become the Advanced Encryption Standard (.pdf), or AES.
The AES competition was the most fun I’ve ever had in cryptography. Think of it as a giant cryptographic demolition derby: A bunch of us put our best work into the ring, and then we beat on each other until there was only one standing. It was really more academic and structured than that, but the process stimulated a lot of research in block-cipher design and cryptanalysis. I personally learned an enormous amount about those topics from the AES competition, and we as a community benefited immeasurably.
NIST did a great job managing the AES process, so it’s the perfect choice to do the same thing with hash functions. And it’s doing just that (.pdf). Last year and the year before, NIST sponsored two workshops to discuss the requirements for a new hash function, and last month it announced a competition to choose a replacement for SHA-1. Submissions will be due in fall 2008, and a single standard is scheduled to be chosen by the end of 2011.
Yes, this is a reasonable schedule. Designing a secure hash function seems harder than designing a secure encryption algorithm, although we don’t know whether this is inherently true of the mathematics or simply a result of our imperfect knowledge. Producing a new secure hash standard is going to take a while. Luckily, we have an interim solution in SHA-256.
Now, if you’ll excuse me, the Twofish team needs to reconstitute and get to work on an Advanced Hash Standard submission.
This essay originally appeared on Wired.com.
EDITED TO ADD (2/8): Every time I write about one-way hash functions, I get responses from people claiming they can’t possibly be secure because an infinite number of texts hash to the same short (160-bit, in the case of SHA-1) hash value. Yes, of course an infinite number of texts hash to the same value; that’s the way the function works. But the odds of it happening naturally are less than the odds of all the air molecules bunching up in the corner of the room and suffocating you, and you can’t force it to happen either. Right now, several groups are trying to implement Xiaoyun Wang’s attack against SHA-1. I predict one of them will find two texts that hash to the same value this year—it will demonstrate that the hash function is broken and be really big news.
Blu-ray Cracked
The Blu-ray DRM system has been broken, although details are scant. It’s the same person who broke the HD DVD system last month. (Both use AACS.)
As I’ve written previously, both of these systems are supposed to be designed in such a way as to recover from hacks like this. We’re going to find out if the recovery feature works.
Blu-ray and HD DVD both allow for decryption keys to be updated in reaction to attacks, for example by making it impossible to play high-definition movies via playback software known to be weak or flawed. So muslix64 work has effectively sparked off a cat-and-mouse game between hackers and the entertainment industry, where consumers are likely to face compatibility problems while footing the bill for the entertainment industry’s insistence on pushing ultimately flawed DRM technology on an unwilling public.
EDITED TO ADD (1/29): You should read this seven part series on the topic.
AACS Cracked?
This is a big deal. AACS (Advanced Access Content System), the copy protection is used in both Blu Ray and HD DVD, might have been cracked—but it’s still a rumor.
If it’s true, what will be interesting is the system’s in-the-field recovery system. Will it work?
Hypothetical fallout could be something like this: if PowerDVD is the source of the keys, an AACS initiative will be launched to revoke the player’s keys to render it inoperable and in need of an update. There is some confusion regarding this process, however. It is not the case that you can protect a cracked player by hiding it offline (the idea being that the player will never “update” with new code that way). Instead, the player’s existing keys will be revoked at the disc level, meaning that new pressings of discs won’t play on the cracked player. In this way, hiding a player from updates will not result in having a cracked player that will work throughout the years. It could mean that all bets are off for discs that are currently playable on the cracked player, however (provided it is not updated). Again, this is all hypothetical at this time.
Copy protection is inherently futile. The best it can be is a neverending arms race, which is why Big Media is increasingly relying on legal and social barriers.
EDITED TO ADD (12/30): An update.
EDITED TO ADD (1/3): More info from the author of the tool.
EDITED TO ADD (1/12): Excellent multi-part analysis here.
EDITED TO ADD (1/16): Part five of the above series of essays. And keys for different movies are starting to appear.
Class Break of TiVoToGo DRM
Last week I wrote about the security problems of having a secret stored in a device given to your attacker, and how they are vulnerable to class breaks. I singled out DRM systems as being particularly vulnerable to this kind of security problem.
This week we have an example: The DRM in TiVoToGo has been cracked:
An open source command-line utility that converts TiVoToGo movies into an MPEG file and strips the DRM is now available online. Released under a BSD license, the utility—called TiVo File Decoder—builds on the extensive reverse engineering efforts of the TiVo hacking community. The goal of the project is to bring TiVo media viewing capabilities to unsupported platforms like OS X and the open source Linux operating system. TiVoToGo support is currently only available on Windows.
EDITED TO ADD (12/8): I have been told that TiVoTo Go has not been hacked: “The decryption engine has been reverse engineered in cross-platform code – replicating what TiVo already provides customers on the Windows platform (in the form of TiVo Desktop software). Each customer’s unique Media Access Key (MAK) is still needed as a *key* to decrypt content from their particular TiVo unit. I can’t decrypt shows from your TiVo, and you can’t decrypt shows from mine. Until someone figures out how to produce or bypass the required MAK, it hasn’t been cracked.”
And here’s a guide to installing TiVoToGo on your Mac.
EDITED TO ADD (12/17): Log of several hackers working on the problem. Interesting.
Sidebar photo of Bruce Schneier by Joe MacInnis.