What tests could you write to verify that the MD5 implementation is correct?

Question

Suppose you have access to an oracle implementation that you think is the correct output.

The most obvious way to do this seems to be to run a set of known plaintext / hash combinations through an implementation and see if they come out as expected. An arbitrary number of these cases can be constructed by generating random plaintexts (using static seed to keep it deterministic) and using the oracle to find their hashes.

The main problem that I see in this is that it does not guarantee the entry of possible angular cases. Creating more cases will reduce the likelihood of no corner cases, but how many cases are enough?

There is also the problem of specifying the lengths of these random plaintexts, since MD5 accepts a string of arbitrary length as input. For my purposes, I don’t need long inputs (let's say something longer than 16 bytes), so you can use the fact that this is an implementation of the “special purpose” MD5 in your answer, if it simplifies or you can just answer the general case, if he cares.

Answer 1

If you have an algorithmic error, it is very likely that every hash will be incorrect. Hashes are inexorable by nature.

Since most of the possible errors will be exposed quickly, you really will not need many tests. The main items to cover are cross-event cases:

• Length = 0 (input is empty)
• Length = 1
• length = 16
• The input contains at least one byte with a value of 0
• Repeated input byte patterns (will this be a significant edge case for MD5?)

If all this passes, perhaps, along with tests for one or two more typical inputs, you can be sure of your algorithm. There are not many edge cases (if someone more familiar with the details of the algorithm cannot think of any other).