MD5 Cryptographic Hash

Introduction

The MD5 Message-Digest Algorithm published in 1992 by Ron Rivest was his successor to MD4 which I’ve discussed previously. Some security considerations for this algorithm are detailed in RFC 6151 published in 2011.

It is undoubtedly the most famous hashing algorithm around and still used in many applications although is being phased out in favour of SHA-256 and others.

I have already discussed the generation of T constants here. The initialization, update and finalization are exact same as MD4 discussed earlier.

The transform/compression function looks like

```void MD5_Transform (MD5_CTX* ctx)
{
uint32_t a, b, c, d, i, t, x, s;

a = ctx->state.v32[0];
b = ctx->state.v32[1];
c = ctx->state.v32[2];
d = ctx->state.v32[3];

for (i=0; i<64; i++) {
#ifdef DYNAMIC
t=tc(i+1);
#else
t=tc[i];
#endif
if (i < 16) {
s = rotf[i%4];
a += F (b, c, d);
} else if (i < 32) {
s = rotg[i%4];
a += G (b, c, d);
} else if (i < 48) {
s = roth[i%4];
a += H (b, c, d);
} else {
s = roti[i%4];
a += I (b, c, d);
}
a += ctx->data.v32[sigma[i]] + t;
a = ROL32(a, s);
a += b;
t=a;
a=d;
d=c;
c=b;
b=t;
}

ctx->state.v32[0] += a;
ctx->state.v32[1] += b;
ctx->state.v32[2] += c;
ctx->state.v32[3] += d;
}
```

The function in assembly is very similar to MD4 again but this time with the option of generating T constants dynamically.

```MD5_Transform proc
pushad
ifdef DYNAMIC
; set control word to round down numbers
call   init_fpu
endif
; load context
mov    esi, [esp+32+4]  ; ctx

; a = ctx->state.v32[0]
lodsd
xchg   _d, eax
; b = ctx->state.v32[1]
lodsd
xchg   _b, eax
; c = ctx->state.v32[2]
lodsd
xchg   _c, eax
; d = ctx->state.v32[3]
lodsd
xchg   _d, eax

push   esi         ; x

xor    _i, _i

.repeat
mov    t1, [esp]
movzx  t2, byte ptr idx[_i]     ; idx[i]
add    _a, [t1+4*t2]            ; a += x[i]
mov    t2, _i
and    t2, 3                    ; i %= 4
mov    t1, _c
.if     _i < 16
mov   cl, byte ptr rotf[t2]    ; rotf[i%4]
xor   t1, _d
and   t1, _b
xor   t1, _d
.elseif _i < 32
mov   cl, byte ptr rotg[t2]    ; rotg[i%4]
xor   t1, _b
and   t1, _d
xor   t1, _c
.elseif _i < 48
mov   cl, byte ptr roth[t2]    ; roth[i%4]
xor   t1, _d
xor   t1, _b
.else
mov   cl, byte ptr roti[t2]
mov   t1, _d
xor   t1, -1
or    t1, _b
xor   t1, _c
.endif

add    _a, t1
ifdef DYNAMIC
call   sin2int
else
mov    t1, dword ptr tc[_i*4]
endif
add    _a, t1
rol    _a, cl
add    _a, _b

mov    t1, _a
mov    _a, _d
mov    _d, _c
mov    _c, _b
mov    _b, t1

inc    _i
.until _i == MD5_CBLOCK

pop    esi

; restore registers
mov    edi, [esp+32+4]
; save context
; ctx->state.v32[0] += a;
add    [edi], _a
scasd
; ctx->state.v32[1] += b;
add    [edi], _b
scasd
; ctx->state.v32[2] += c;
add    [edi], _c
scasd
; ctx->state.v32[3] += d;
add    [edi], _d
; restore registers
popad
retn   4
MD5_Transform endp
```

Summary

architecture size
x86 479 (dynamic T values)
x86 685 (static T values)
x64 585 (dynamic T values)
x64 782 (static T values)

The main problem again with this algorithm is how to implement in device that has low resources.
The size of this code in x86 is 485 bytes and slightly larger when you include array of 64 constants.

See sources here

Advertisements
This entry was posted in assembly, cryptography, programming and tagged , , , . Bookmark the permalink.