How government created a new secure hash
With its selection as the winner of the National Institute of Standards and Technology’s five-year SHA-3 competition, the Keccak algorithm is set to become the sixth Secure Hash Algorithm recognized under Federal Information Processing Standards. Expected to be designated as SHA-3 within the next year, Keccak will provide an additional cryptographic tool deemed secure enough that agencies can rely on it to authenticate and digitally sign documents.
Hash algorithms are important cryptographic tools, but their operation is transparent to most people who use the applications that apply them. So, here is a brief description of what they are and what they do.
Currently approved Secure Hash Algorithms are specified in FIPS 180-3, published in 2008. They are proposed, after analysis and testing, by NIST and approved by the secretary of Commerce. They are SHA-1; and SHA-224, SHA-256, SHA-384 and SHA-512, collectively known as SHA-2.
When the contents of a digital document are fed into the algorithm, it produces a hash — or message digest — of a fixed length that should be unique to the contents of the document. That means no other message will produce the same digest. And because a hash algorithm is a one-way function, it should not be possible to use the hash to recreate the message.
If a document is "hashed" and the resulting digest is made available, a second person using the same algorithm should be able to produce the same digest, which proves that the document has not been altered. Any change in the document would produce a completely different digest. The algorithms also can be used to create digital signatures, which then can be used, like ink-on-paper signatures, for non-repudiation.
The security of the scheme depends on whether the expectations for uniqueness are met by an algorithm.
"The five hash algorithms specified in this standard are called secure because, for a given algorithm, it is computationally infeasible 1) to find a message that corresponds to a given message digest, or 2) to find two different messages that produce the same message digest," says FIPS 180-3. "Any change to a message will, with a very high probability, result in a different message digest. This will result in a verification failure when the secure hash algorithm is used with a digital signature algorithm or a keyed-hash message authentication algorithm."
Generally, the security of the algorithm increases with the size of the message digest, which ranges in size from 160 bits for SHA-1 to 512 bits for SHA-512.
The computations are performed on fixed-size blocks of message content, so before the function is executed the message is prepared for hashing by padding it to produce the needed number of bits to produce only full blocks, and then parsing it into blocks.
For SHA-1, SHA-224 and SHA-256 each message block is 512 bits, represented as a sequence of 16 32-bit words. For SHA-384 and SHA-512 each message block has 1,024 bits represented by 16 64-bit words.