WEAKNESSES revealed last month in a key security technique are forcing cryptographers to look for new ways to keep online transactions secure. Though the flaws are unlikely to pose an immediate threat, they have given security experts a nasty jolt.
“It shows we don’t understand the theory as well as we thought,” says David Wagner, a cryptographer at the University of California at Berkeley. Unless new ideas can be harnessed to protect electronic transactions, e-commerce could be seriously undermined.
Many cryptographic routines are eventually broken. What has dashed experts’ confidence this time is the simultaneous discovery of similar flaws in two examples of the same type of system, says Wagner.
Advertisement
The algorithms that took the beating are of a type called a cryptographic hash function. These functions take a file, say a 20-page text document, and apply a mathematical operation that generates a fixed-length string of 0s and 1s that uniquely represents that file. So if you want to check that a document you have received is authentic, you “hash” it and check that the resulting string – the hash – created is the same as that created by the sender. No other document should generate the same hash; what’s more, it is impossible to work backwards and regenerate the original document from the hash (see “Making a hash of it”).
Hashing has become central to authentication because it is quick and convenient: a simple browser plug-in can handle the operation. If you buy an airline ticket online, a padlock icon appears in the browser showing that it has received a message from the website stamped with a digital signature. This signature includes the message, its hash and a cryptographic key. The browser’s hashing software verifies the message by checking that the hash is indeed generated by that particular message and that the key comes from a known, trusted sender.
To make sure that hashing algorithms are secure, cryptographers try to “break” them by looking for two files that produce the same hash. This is known as a collision, and finding one means that it would be at least theoretically possible to snip a digital signature from one file and append it to another.
Finding a collision in a tried-and-tested algorithm is rare, but at the Crypto 2004 Conference in Santa Barbara, California, last month, two announcements stunned the assembled cryptographers. First, Xiaoyun Wang of Shandong University of Technology in China demonstrated a collision in a hash function called MD5, used in e-commerce. Then Eli Biham and Rafi Chen from the Technion Israel Institute of Technology in Haifa revealed multiple collisions in a cut-down version of SHA-1, the hash function recommended by the US National Security Agency for authenticating business documents.
Although the collisions were found for a shortened version of SHA-1, many experts now believe that an attack on the full version is only a matter of time.
There are many ways hackers can exploit these collisions. They could create bogus websites that appeared secure, or falsify transaction records.
To do this, they would have to create software capable of exhaustively searching for a file that collides with the hash of a target file. And the collision file has to be more than digital gobbledegook: it has to pass for a paper describing an invention, say, or read like an authentication message from a secure website. “This is really hard,” says cryptographer Stuart Haber at Hewlett-Packard in Princeton, New Jersey.
But last month’s revelations show it could be done, and when a hash function has been broken it has to be replaced with a new, harder-to-break alternative. If that ever becomes impossible, e-commerce could one day be scuppered. “The hacker community, or worse organised crime, will do this if they can make it pay,” says Greg Rose of Qualcomm Australia in New South Wales.
Cryptographers agree that MD5 ought to be ditched immediately from all encryption and authentication systems, and most believe it is time to start phasing out SHA-1 and use information from the recent break-ins to make a new “gold-standard” hash function. How to proceed is an open question because hash functions have been made in a pretty ad-hoc manner. “In some way everything we are doing is guesswork,” says Wagner.
“With every break, we learn more,” says cryptographer Bruce Schneier of Counterpane Internet Security of Mountain View, California. “It’s really, really cool – the most fun you can have as cryptographer is breaking stuff. It’s how you create knowledge.”
Making a hash of it
A hash function is supposed to generate a unique fixed-length string of data – a hash – from a source file of arbitrary length. The SHA-1 function does this by first checking whether the total number of bits in the source file is a multiple of 512. In most cases it won’t be, so it pads out the file by adding a sequence of 0s and 1s. This allows the file to be split into 512-bit chunks.
The first 512 bits are then mathematically combined with a 160-bit constant, called the initialisation vector, to produce a 160-bit string. This string is then combined with the next 512-bit chunk, and so on until all the chunks have been processed, producing a final 160-bit string: the hash. MD5 operates in a similar way but creates a 128-bit hash.
As every bit in the original file contributed to the production of the hash, it should be unique to that file. But cryptographers are now discovering that this is not necessarily the case.
