MD5, SHA-1, RIPEMD, etc.
Actually, MD5 is still holding up, but Dobbertin has indeed dented it.
Frankly, it would take a *hell* of a determined attacker to manage
to turn it into a successful securitty exploit if it's used for
file checksums.
All of RIPEMD-160, SHA-1 and MD5 are variants on MD4.
Frankly, I find the design of SHA-1 a lot clearer than that of
RIPEMD-160. Maybe that's just me. I like parsimony in design; Ron
Rivest's ciphers are always fascinatingly elegant. There's not much
*need* to make the decisions public; the algorithm is clear enough.
Although, yes, the fact it's the NSA creeps me out a bit, it's unlikely
they'd knowingly embarass themselves by releasing something weak.
(The whole Lucifer/DES thing is a classic case of broken telephone.
Lucifer was a weak cipher with a big key. Differential Cryptanalysis
goes through it easily. The same bunch of people designed DES, based
on what they learned from their mistakes with Lucifer. They learned
differential cryptanalysis, and the NSA asked them not to talk about
it, leading to secrecy. In truth, DES has shown itself to be a very
good cipher, for its design parameters. A 56-bit key size is too small
these days, but it balances nicely with the difficulty of DC attacks,
so if you want to increase it, you have to add rounds. This tends
to make be believe that the NSA is not into putting in back doors.)
In all cases, there is a main "cipher", which is actually reversible, and
then the standard Davies-Meyer hash construction is applied, adding
the input back to the output to produce an irreversible transform
step. But it is "almost reversible", which limits the loss of information
about past history.
In MD4-like ciphers,the processing is divided into "phases", which use
essentially the same round function repeatedly. MD4 has three phases
of 16 rounds each. MD5 has 4 phases of 16 rounds each. RIPEMD-160
has 5 phased of 16 rounds each. SHA-1 has 4 phases of 20 rounds
each. Note how having one round per inout word per output word
seems standard.
Both SHA-1 and RIPEMD add a rotate of another round variable to a round
to avoid some of the MD5 attacks that play with the most significant bit.
Compared with MD5, SHA-1 got rid of a number of features in MD5 that
were never well defended, anyway:
- The per-round constants. SHA-1 uses one constant for each of its
four "phases", and the constants are just the square roots of some
numbers, hardly mysterious.
- The per-round rotations. SHa-1 uses a fixed rotation, which does fine.
SHA-1, however, added the unique key-scheduling XOR pass, which I haven't
seen anywhere else, but which is the real revolutionary improvement in it.
Dobbertin's techniques involve limiting the hamming distance between
messages that collide so the differences are limited to a few rounds of
the hash, since MD5, like MD4, uses the input words as-is in each phase,
just permuted.
SHA's GFSR implementation means that any two inputs will have a large
Hamming distance in the scheduled key, i.e. lots of rounds will have
their keys altered. The "bug fix" in SHA-1 further increases this
tendency.
If you look at the history of /dev/random's implementation, you'll see
that I used the same techniques until I found a slight variant that's
even better (Matsumono's twisted GFSR).
This gives enormous resistance to Dobbertin's attacks.
As for RIPEMD-160, the changes are very different. The phases still
use permutations of the input data, which allows Dobbertin-style
attacks, although the permutations have been optimized to make them
difficult. The big "guaranteed prevention" technique is is that there
are *two* "cipher" blocks in it, which are summed along with the input
to produce the output of the round function. This is *not* a standard
hash construction, although I can't think of a reason why it's bad. Of
course, it certainly slows things down.
It also has the per-round variable rotates, although the constants
stay the same for each phase. Like SHA-1, it uses square (and cube)
roots for the phase constants.
It also rotates the outputs of the ciphers and the feedforward before
adding them together. I'm not sure why; the paper never explains it.
I have no fear of RIPEMD-160; it's certainly strong, but it's also
slower than necessary and has more unproven techniques, and I don't
quite see the reason to put up with that.
Oh, for a RIPEMD-160 program, look at http://www.nic.com/~cheah/ripmd160.html.
--
-Colin
--
TO UNSUBSCRIBE FROM THIS MAILING LIST: e-mail the word "unsubscribe" to
debian-devel-request@lists.debian.org .
Trouble? e-mail to templin@bucknell.edu .
Reply to: