[Next] [Up] [Previous] [Index]

One-way Hash Functions

For some purposes, including key generation, but especially for digital signatures, something that is like a checksum of a block of text, but which is secure in the sense that it is nearly impossible to generate text that will have a given hash function value when that value is determined in advance, is required. This way, if someone signs a document by using public-key methods to sign its hash value, an adversary is unable to generate a document saying something different, and claim that it was this document, having the same hash, that was signed instead.

Since some block ciphers, including DES, are very secure against someone determining the key even when the plaintext as well as the ciphertext is known, using a document somehow as the key to a block cipher like DES rather than as the plaintext input might allow the ciphertext output to function as a secure hash.

This kind of approach, but used with specially constructed block algorithms which operate on larger blocks, and with the text being hashed used as a source of subkeys rather than keys from which keys for multiple rounds are derived, is the common method of performing secure hash functions. Only one such method, the Secure Hash Algorithm, an NSA design which is similar to, and based upon, MD4 from RSA Laboratories (and also similar to MD5 from RSA Laboratories, also an MD4 descendant) will be described here.

In general terms, SHA-1 and MD5 look like a block cipher, operating on a fixed initial value, with the message being hashed providing the subkeys for the block cipher's operation. However, they do somewhat more than that, and they must do so, because it is trivial with DES, for example, to produce any desired value for the final output by varying the last two subkeys; thus, collisions could be produced essentially at will for a hash function which operated in that way.

SHA-1, which we will examine in full detail in the next section, expands 16 32-bit words of message text to 80 32-bit subkey words with a shift-register technique. And, after 80 rounds of the hash function are applied to the 160-bit value, the original value and the result value are combined together (using 32-bit addition with no carries between words) to make the hash operation noninvertible.

Thus, SHA-1 heeds the lessons of work done on using DES or similar block ciphers to hash messages. The following diagram illustrates the two basic methods of doing that involving a single encryption for a message block which are believed to be secure, plus a method using two encryptions per block:

The first method uses the same principle as found in SHA-1: the message block is used as the key for encrypting the previous hash value, and then both the previous hash value and the encrypted version are XORed together.

The second method, depicted as three different methods in Applied Cryptography, involves using the previous hash value as the key to encrypt the message block. But the previous hash value must also be XORed with the message block on input, or the enciphered version of the message block on output, or both, for security.

Seeing these methods had inspired me to think of the third structure shown in the diagram, where the results of encrypting the previous hash value with the message block as the key and of encrypting the message block with the previous hash value as the key are XORed together to produce the new hash value.

While that would be an unnecessary complication for a hash using actual block ciphers, with their complicated key schedules and large number of rounds, this might well be a useful structure on which to base the design of a new hash function.

But although this method has greater security in some ways, it has one flaw: one can produce a zero hash result with a message block that equals the preceding hash value, because it is symmetrical. There might be a way to exploit this to cause hash collisions.

[Next] [Up] [Previous] [Index]

Table of Contents
Main Page