A Secure One-Way Hash Function Built from DES

Applying a one-way hash function is a useful preliminary to digitally signing a message, both for security and efficiency. Several proposals for building such a function out of DES have been shown to be insecure. This talk studies a proposal due to Davies, and provides some evidence for its security. We prove security under a black box model. That is, we consider algorithms which call the encryption function via an oracle, and calculate the expected running time for a randomly chosen block cipher. This mirrors attacks on the system which do not rely on special properties of the encryption function. Under this model, we show that, given Y, finding a message hashing to y requires 0(264) encryptions. However, if the opponent is also given some legitimately signed messages, a speedup is possible, proportional to the total length of such material. This can be foiled by adding a running count to each block. The resulting system provably requires O(264) steps to break, even given large amounts of signed material. By modifying the model, these results can be strengthened to show that tbe existence of weak keys and the complementation property of DES do not help the forger. Any successful attack would have to use more subtle properties of DES.