## 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[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);
}

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

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

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
.elseif (_i < 40)
xor	 t1, _d
xor	 t1, _b
.elseif (_i < 60)
mov  t2, _c
or   t1, _d
and  t1, _b
and  t2, _d
or   t1, t2
.else
xor	 t1, _d
xor	 t1, _b
.endif
; t += ROL32(a, 5) + e
mov   t2, _a
rol   t2, 5
mov   t2, _i
shl   t2, 2

; 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

mov    esi, _e
mov    edi, [esp+32+4]

; ctx->state.v32[0] += a;
scasd
; ctx->state.v32[1] += b;
scasd
; ctx->state.v32[2] += c;
scasd
; ctx->state.v32[3] += d;
scasd
; ctx->state.v32[4] += e;
; restore registers
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