Entries Tagged "cryptanalysis"

Page 20 of 22

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.

Posted on February 8, 2007 at 9:07 AM • View Comments

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.

Posted on January 26, 2007 at 12:47 PM • View Comments

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.

Posted on December 29, 2006 at 6:02 AM • View Comments

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.

Posted on December 7, 2006 at 12:42 PM • View Comments

New Timing Attack Against RSA

A new paper describes a timing attack against RSA, one that bypasses existing security measures against these sorts of attacks. The attack described is optimized for the Pentium 4, and is particularly suited for applications like DRM.

Meta moral: If Alice controls the device, and Bob wants to control secrets inside the device, Bob has a very difficult security problem. These “side-channel” attacks—timing, power, radiation, etc.—allow Alice to mount some very devastating attacks against Bob’s secrets.

I’m going to write more about this for Wired next week, but for now you can read the paper, the Slashdot thread, and the essay I wrote in 1998 about side-channel attacks (also this academic paper).

Posted on November 21, 2006 at 7:24 AM • View Comments

Notes from the Hash Function Workshop

Last month, NIST hosted the Second Hash Workshop, primarily as a vehicle for discussing a replacement strategy for SHA-1. (I liveblogged NIST’s first Cryptographic Hash Workshop here, here, here, here, and here.)

As I’ve written about before, there are some impressive cryptanalytic results against SHA-1. These attacks are still not practical, and the hash function is still operationally secure, but it makes sense for NIST to start looking at replacement strategies—before these attacks get worse.

The conference covered a wide variety of topics (see the agenda for details) on hash function design, hash function attacks, hash function features, and so on.

Perhaps the most interesting part was a panel discussion called “SHA-256 Today and Maybe Something Else in a Few Years: Effects on Research and Design.” Moderated by Paul Hoffman (VPN Consortium) and Arjen Lenstra (Ecole Polytechnique Federale de Lausanne), the panel consisted of Niels Ferguson (Microsoft), Antoine Joux (Universite de Versailles-Saint-Quentin-en-Yvelines), Bart Preneel (Katholieke Universiteit Leuven), Ron Rivest (MIT), and Adi Shamir (Weismann Institute of Science).

Paul Hoffman has posted a composite set of notes from the panel discussion. If you’re interested in the current state of hash function research, it’s well worth reading.

My opinion is that we need a new hash function, and that a NIST-sponsored contest is a great way to stimulate research in the area. I think we need one function and one function only, because users won’t know how to choose between different functions. (It would be smart to design the function with a couple of parameters that can be easily changed to increase security—increase the number of rounds, for example—but it shouldn’t be a variable that users have to decide whether or not to change.) And I think it needs to be secure in the broadest definitions we can come up with: hash functions are the workhorse of cryptographic protocols, and they’re used in all sorts of places for all sorts of reasons in all sorts of applications. We can’t limit the use of hash functions, so we can’t put one out there that’s only secure if used in a certain way.

Posted on September 11, 2006 at 3:30 PM • View Comments

Galileo Satellite Code Cracked

Anyone know more?

Members of Cornell’s Global Positioning System (GPS) Laboratory have cracked the so-called pseudo random number (PRN) codes of Europe’s first global navigation satellite, despite efforts to keep the codes secret. That means free access for consumers who use navigation devices—including handheld receivers and systems installed in vehicles—that need PRNs to listen to satellites.

Security by obscurity: it doesn’t work, and it’s a royal pain to recover when it fails.

Posted on July 11, 2006 at 11:30 AM • View Comments

Da Vinci Code Ruling Code

There is a code embedded in the ruling in The Da Vinci Code plagiarism case.

You can find it by searching for the characters in italic and boldface scattered throughout the ruling. The first characters spell out “SMITHCODE”: that’s the name of the judge who wrote the ruling The rest remains unsolved.

According to The Times, the remaining letters are: J, a, e, i, e, x, t, o, s, t, p, s, a, c, g, r, e, a, m, q, w, f, k, a, d, p, m, q, z.

According to The Register, the remaining letters are: j a e i e x t o s t g p s a c g r e a m q w f k a d p m q z v.

According to one of my readers, who says he “may have missed some letters,” it’s: SMITHYCODEJAEIEXTOSTGPSACGREAMQWFKADPMQZV.

I think a bunch of us need to check for ourselves, and then compare notes.

And then we have to start working on solving the thing.

From the BBC:

Although he would not be drawn on his code and its meaning, Mr Justice Smith said he would probably confirm it if someone cracked it, which was “not a difficult thing to do”.

As an aside, I am mentioned in Da Vinci Code. No, really. Page 199 of the American hardcover edition. “Da Vinci had been a cryptography pioneer, Sophie knew, although he was seldom given credit. Sophie’s university instructors, while presenting computer encryption methods for securing data, praised modern cryptologists like Zimmermann and Schneier but failed to mention that it was Leonardo who had invented one of the first rudimentary forms of public key encryption centuries ago.”

That’s right. I am a realistic background detail.

EDITED TO ADD (4/28): The code is broken. Details are in The New York Times:

Among Justice Smith’s hints, he told decoders to look at page 255 in the British paperback edition of “The Da Vinci Code,” where the protagonists discuss the Fibonacci Sequence, a famous numerical series in which each number is the sum of the two preceding ones. Omitting the zero as Dan Brown, “The Da Vinci Code” author, does the series begins 1, 1, 2, 3, 5, 8, 13, 21.

Solving the judge’s code requires repeatedly applying the Fibonacci Sequence, through the number 21, to the apparently random coded letters that appear in boldfaced italics in the text of his ruling: JAEIEXTOSTGPSACGREAMQWFKADPMQZVZ.

For example, the fourth letter of the coded message is I. The fourth number of the Fibonacci Sequence, as used in “The Da Vinci Code,” is 3. Therefore, decoding the I requires an alphabet that starts at the third letter of the regular alphabet, C. I is the ninth letter regularly; the ninth letter of the alphabet starting with C is K; thus, the I in the coded message stands for the letter K.

The judge inserted two twists to confound codebreakers. One is a typographical error: a letter that should have been an H in both the coded message and its translation is instead a T. The other is drawn from “Holy Blood, Holy Grail,” the other book in the copy right case. It concerns the number 2 in the Fibonacci series, which becomes a requirement to count two letters back in the regular alphabet rather than a signal to use an alphabet that begins with B. For instance, the first E in the coded message, which corresponds to a 2 in the Fibonacci series, becomes a C in the answer.

The message reads: “Jackie Fisher who are you Dreadnought.”

I’m disappointed, actually. That was a whopper of a hint, and I would have preferred the judge to keep quiet.

EDITED TO ADD (5/8): Commentary on my name being in The Da Vinci Code.

Posted on April 27, 2006 at 6:47 PM • View Comments

1 … 18 19 20 21 22

Sidebar photo of Bruce Schneier by Joe MacInnis.