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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s