Asmcodes: SHA-1 cryptographic hash

Introduction

The Secure Hash Algorithm 1 (SHA-1) is a cryptographic hash function designed by the United States National Security Agency (NSA) and is a Federal Information Processing Standard (FIPS) published by United States National Institute of Standards and Technology (NIST) in 1995.

It produces a 160-bit or 20-byte hash value known as a message digest which is converted to 40 hexadecimal digits and used for a variety of purposes including verifying the integrity of files or simple blocks of data using unique key (HMAC), verification of digital signatures and has been used for the construction of some password algorithms and block ciphers (although the latter 2 are not what it was intended for)

It was found to be vulnerable in 2005 but was already superceded by SHA-2 released in 2002.

Close inspection of this algorithm shows that its design was influenced by MD4 which was written and published by Ron Rivest in 1992.

This algorithm has been a very popular replacement for MD5 but with the availability of SHA-2 for some time now, it too like MD5 is being phased out. We will of course continue to encounter this algorithm for many years into the future.

Initialization

Exactly the same as MD4 and MD5 except there are 5 initial values

void SHA1_Init (SHA1_CTX *c) {
  c->len    = 0;
  c->s.w[0] = 0x67452301;
  c->s.w[1] = 0xefcdab89;
  c->s.w[2] = 0x98badcfe;
  c->s.w[3] = 0x10325476;
  c->s.w[4] = 0xc3d2e1f0;
}

Updating context

Again, this is exactly the same as MD4 and MD5.

Compression

The main difference between this and MD4 is the key expansion procedure and increased number of rounds.

void SHA1_Transform (SHA1_CTX *ctx) 
{
  uint32_t a, b, c, d, e, t, i;
  uint32_t w[80], s[SHA1_LBLOCK];

  // copy buffer to local
  for (i=0; i<16; i++) {
    w[i] = SWAP32(ctx->buf.w[i]);
  }
  
  // expand it
  for (i=16; i<80; i++) {
    w[i] = ROTL32(w[i -  3] ^ 
                  w[i -  8] ^ 
                  w[i - 14] ^ 
                  w[i - 16], 1);
  }
  
  // load state
  memcpy (s, ctx->s.b, SHA1_DIGEST_LENGTH);
  
  // for 80 rounds
  for (i=0; i<80; i++) {
    if (i<20) {
      t = (s[3] ^ (s[1] & (s[2] ^ s[3]))) + 0x5A827999L;
    } else if (i<40) {
      t = (s[1] ^ s[2] ^ s[3]) + 0x6ED9EBA1L;
    } else if (i<60) {
      t = ((s[1] & s[2]) | (s[3] & (s[1] | s[2]))) + 0x8F1BBCDCL;
    } else {
      t = (s[1] ^ s[2] ^ s[3]) + 0xCA62C1D6L;
    }
    t += ROTL32(s[0], 5) + s[4] + w[i];
    s[4] = s[3];
    s[3] = s[2];
    s[2] = ROTL32(s[1], 30);
    s[1] = s[0];
    s[0] = t;
  }
  
  // update state
  for (i=0; i<SHA1_LBLOCK; i++) {
    ctx->s.w[i] += s[i];
  }
}

In x86 assembly, this gets messy. The problem is we only have 8 general purpose registers and since we need to use ESP for stack operations, that leaves us with 7. In the H function (rounds 40-60) we need 2 temporary registers to calculate result. With a 160-bit hash, that’s 5 32-bit integers. So it’s doable but cutting it close. So is SHA-1 a good design for x86? Just about.

; workspace for transform
SHA1_WS struct
  w dword 80 dup (?)
  i dword ?
SHA1_WS ends

_a equ <eax>  ; don't change
_b equ <ebx>
_c equ <ebp>
_d equ <edx>
_e equ <edi>

_i textequ <[esp][SHA1_WS.i]>
_w textequ <[esp][SHA1_WS.w]>

t1 equ <esi>
t2 equ <ecx>

; update context with input
  public SHA1_Transform
SHA1_Transform proc
    pushad
    
    mov    ebx, [esp+32+4]
    lea    esi, [ebx][SHA_CTX.buffer]
    
    ; allocate space for work
    sub    esp, sizeof SHA1_WS
    mov    edi, esp
    
    ; convert 16 words to big endian
    push   16
    pop    ecx
swap_bytes:
    lodsd
    bswap  eax
    stosd
    loop   swap_bytes
    
    mov    _i, ecx
    
    ; expand 16 words to 80
    mov    cl, 64
expand:
    mov    eax, [edi -  3*4]
    xor    eax, [edi -  8*4]
    xor    eax, [edi - 14*4]
    xor    eax, [edi - 16*4]
    rol    eax, 1
    stosd
    loop   expand
    
    ; load context
    mov    esi, ebx
    ; a = ctx->state.v32[0]
    lodsd
    xchg   _e, 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
    ; e = ctx->state.v32[4]
    lodsd
    xchg   _e, eax
    
    ; update context
    .repeat
        mov	 t1, _c
      .if (_i < 20)
        xor	 t1, _d
        and	 t1, _b
        xor	 t1, _d
        add  t1, 05a827999h
      .elseif (_i < 40)
        xor	 t1, _d
        xor	 t1, _b
        add  t1, 06ed9eba1h
      .elseif (_i < 60)
        mov  t2, _c
        or   t1, _d
        and  t1, _b
        and  t2, _d
        or   t1, t2
        add  t1, 08f1bbcdch
      .else
        xor	 t1, _d
        xor	 t1, _b
        add  t1, 0ca62c1d6h
      .endif
      ; t += ROL32(a, 5) + e
      mov   t2, _a
      rol   t2, 5
      add   t2, _e
      add   t1, t2
      mov   t2, _i
      shl   t2, 2
      add   t1, [esp][SHA1_WS.w+t2]
      
      ; e = d
      mov   _e, _d
      ; d = c
      mov   _d, _c
      ; c = ROL32(b, 30)
      mov   _c, _b
      rol   _c, 30
      ; b = a
      mov   _b, _a
      ; a = t
      mov   _a, t1
      ; i++
      inc   _i
    .until  _i == 80
    
    add    esp, sizeof SHA1_WS
    
    mov    esi, _e
    mov    edi, [esp+32+4]
    
    ; 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
    scasd
    ; ctx->state.v32[4] += e;
    add    [edi], esi
    ; restore registers
    popad
    retn   4
SHA1_Transform endp

Summary

It’s not recommended you use this hash algorithm for anything that requires a high level of security. It’s only presented here for historical reasons.

See sources here

architecture size
x86 447
x64 456
Advertisements
This entry was posted in assembly, cryptography, encryption, programming, security 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