Re: Hardening MD5 with multiplications

From: Gregory G Rose (ggr_at_qualcomm.com)
Date: 08/19/05


Date: 19 Aug 2005 11:55:04 -0700

In article <1124444048.789155.27810@f14g2000cwb.googlegroups.com>,
dullien@gmx.de <dullien@gmx.de> wrote:
>seeing MD5's structure and the attacks used on it so far,
>why has nobody proposed foiling the differential attacks
>by replacing operations that have easily controllable differential
>trails (addition, specifically when only the msbit is changed)
>with something that is arguably a lot harder to control
>(modular multiplication) ?

There are two problems with using modmult in
applications like this. The first is, as you've
noted further down, that performance. People often
forget that this has to be implemented in
toasters, where you can't afford the hardware of a
multiplier, and on low-end embedded
microprocessors that don't have multipliers
either.

The other problem creeps in when you more closely
examine the word "modular". You have two choices,
really:
1. mod 2^32
2. mod something else, hopefully prime.

Now in case 1, the problem is that even numbers
in either operand guarantee an even output, and
differentials like that would almost certainly
cause a real problem.

In case 2, you actually have to do division (or
something like it), with extreme performance
penalty. And then, the little biases that build up
because the result can't occupy the entire 32-bit
word might also cause trouble.

Anyway, that's my take.

Greg.

-- 
Greg Rose
232B EC8F 44C6 C853 D68F  E107 E6BF CD2F 1081 A37C
Qualcomm Australia: http://www.qualcomm.com.au