NIST looks to cook up a new hash
Connecting state and local government leaders
Current algorithms are still secure, but cracks are beginning to show.
THE NATIONAL INSTITUTE OF Standards and Technology has opened a competition for a new crypto algorithm for digital signatures and message authentication, inviting nominations for what will become the Secure Hashing Algorithm-3.
SHA-1 and -2, the current widely used algorithms specified in Federal Information Processing Standard 180-2, are not broken ' yet. But weaknesses are beginning to appear, said William Burr, manager of the NIST security technology group, which creates cryptographic standards.
'The structure is crumbling, but it hasn't fallen down,' Burr said.
The two standards probably have years of life left in them. 'It is prudent to move on, but it's not a screaming emergency.'
In the details
The new algorithm, which will be chosen in a public evaluation process similar to that used for the Advanced Encryption Standard seven years ago, is expected to be secure enough to remain in use for decades. There is no firm schedule for the selection process, but the tentative timetable includes a year for the submissions process and two rounds of public and in-house review expected to last at least a year each.
A hashing algorithm is a cryptographic tool that produces a fixed-size digest or fingerprint of a message that can be used for digital signatures or message authentication.
Although most people do not digitally sign documents outside security-minded environments such as the military and intelligence communities, 'digital signatures are generally pervasive in the environment,' Burr said. They are used in authenticating Web sites, to verify the source of software patches and in many electronic transactions. But most hash function calls, possibly as many as 95 percent, are for message authentication codes rather than digital signatures, he said.
The need for new algorithms arises because weaknesses in existing ones become visible with use and research, and increases in computing power can make some attacks against them more practical.
SHA-0 was specified in FIPS 180 in 1993 and was quickly replaced with SHA-1. The SHA-2 family, which produces digests of 224, 256, 384 and 512 bits in length, was added to the standard with FIPS 180-2. It is SHA-1 that is showing its age and would be replaced by a new algorithm. SHA-2 would remain the standard for now.
'Although there is no specific reason to believe that a practical attack on any of the SHA-2 family of hash functions is imminent, a successful collision attack on an algorithm in the SHA-2 family could have catastrophic effects for digital signatures,' NIST wrote in announcing the competition.
A collision attack is a process to identify two messages that would produce the same digest. Such a digest could apply equally to a signature on either message.
'Once I've got two collisions, it's easier to find the third,' and so on, Burr said. Finding collisions, even on the weaker SHA-1 algorithm, is not simple. 'It's supposed to take 218 hash functions to find the collision.
Now it takes about 216.'
That still is a huge number, but it could be whittled down further as techniques are developed and computing power increases. 'It has cryptographers alarmed,' Burr said.
Weaknesses in SHA-1 make cryptographers uneasy about SHA-2 because they are based on a scheme called the Merkle- Damgard construct. 'They all are fairly similar in their internal structure and design to SHA-0, which is badly broken,' Burr said.
Developing a new algorithm that meets the requirements will be a challenge. It is expected to be at least as secure as the ones in use but more efficient in terms of speed and computational resources needed to run it. It must be similar enough to SHA-2 to directly substitute for it in all applications but different enough that a successful attack against SHA-2 will not work against it.
New selection process
The selection process will differ greatly from that for past hashing algorithms, which were developed behind closed doors. While NIST examines and tests the algorithms, submissions also will be made public, and outside evaluators will be encouraged to hammer away at them in search of weaknesses.
Candidate algorithms and accompanying information must be submitted by Oct. 31. Because signed statements are required ensuring that algorithms are freely available, submissions must be mailed rather than e-mailed.
They should be sent to Shu-Jen Chang, Information Technology Laboratory, Attention: Hash Algorithm Submission, 100 Bureau Dr. ' stop 8930, NIST, Gaithersburg, MD 20899-8930.
For more information about the competition, visit the NIST Web site at http://www.nist.gov/hashcompetition, contact Chang at (301) 975-2940, or e-mail her at shu-jen.chang@nist.gov.
NEXT STORY: The fourth dimension