## 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 was 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. It can be used for a variety of purposes, including verifying the integrity of files or simple blocks of data using a unique key (HMAC), verification of digital signatures and has been used for the construction of some password algorithms (PBKDF) and block ciphers (SHACAL-1). It was superceded by SHA-2 in 2002 and is no longer considered secure. Close inspection of this algorithm shows that its design was influenced by MD4 that was written and published by Ron Rivest in 1992. Despite SHA-1 being obsolete and insecure since 2005, due to legacy reasons, we are likely to see this algorithm well into the future.

### Macros and data types

```#define R(v,n)(((v)<<(n))|((v)>>(32-(n))))
#define F(n)for(i=0;i<n;i++)

#define rev32(x) __builtin_bswap32(x)
#define rev64(x) __builtin_bswap64(x)

typedef unsigned long long Q;
typedef unsigned int W;
typedef unsigned char B;

typedef struct _sha1_ctx {
W s[5];
union {
B b[64];
W w[16];
Q q[8];
}x;
Q len;
}sha1_ctx;
```

### Initialization

It’s exactly the same as MD4 and MD5 except there are five initial values instead of four.

```void sha1_init(sha1_ctx*c) {
c->s[0] = 0x67452301;
c->s[1] = 0xefcdab89;
c->s[2] = 0x98badcfe;
c->s[3] = 0x10325476;
c->s[4] = 0xc3d2e1f0;
c->len  = 0;
}
```

### Adding data

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

```void sha1_update(sha1_ctx*c,const void*in,W len) {
B *p=(B*)in;
W i, idx;

idx = c->len & 63;
c->len += len;

for (i=0;i<len;i++) {
c->x.b[idx]=p[i]; idx++;
if(idx==64) {
sha1_compress(c);
idx=0;
}
}
}
```

### Finalization

```void sha1_final(void*h,sha1_ctx*c) {
W i,len,*p=h;

i = len = c->len & 63;
while(i<64) c->x.b[i++]=0;
c->x.b[len]=0x80;
if(len>=56) {
sha1_compress(c);
F(16)c->x.w[i]=0;
}
c->x.q[7]=rev64(c->len*8);
sha1_compress(c);
F(5)p[i]=rev32(c->s[i]);
}
```

### Compression

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

```#define FF(x,y,z)((z)^((x)&((y)^(z))))
#define GG(x,y,z)(((x)& (y))|((z)&((x)|(y))))
#define HH(x,y,z)((x)^(y)^(z))

void sha1_compress(sha1_ctx*c) {
W t,i,w[80],x[5];

// load 64-bytes in big endian byte order
F(16)w[i]=rev32(c->x.w[i]);

// expand buffer
for(i=16;i<80;i++)
w[i]=R(w[i-3]^w[i-8]^w[i-14]^w[i-16],1);

// load 160-bit state
F(5)x[i]=c->s[i];

// permute
F(80) {
if(i<20){
t = FF(x[1],x[2],x[3])+0x5A827999L;
} else if(i<40) {
t = HH(x[1],x[2],x[3])+0x6ED9EBA1L;
} else if(i<60) {
t = GG(x[1],x[2],x[3])+0x8F1BBCDCL;
} else {
t = HH(x[1],x[2],x[3])+0xCA62C1D6L;
}
t+=R(x[0],5)+x[4]+w[i];
x[4]=x[3];x[3]=x[2];x[2]=R(x[1],30);x[1]=x[0];x[0]=t;
}
// update state with result
F(5)c->s[i]+=x[i];
}
```

### x86 assembly

Only the sha1_compress function is provided.

```; -----------------------------------------------
; SHA-1 permutation function in x86 assembly
;
; size: 191 bytes
;
; global calls use cdecl convention
;
; -----------------------------------------------

bits 32

%ifndef BIN
global sha1_compress
global _sha1_compress
%endif

%define _a [edi   ]
%define _b [edi+ 4]
%define _c [edi+ 8]
%define _d [edi+12]
%define _e [edi+16]

sha1_compress:
_sha1_compress:
pushad
mov    esi, [esp+32+4] ; sha1_ctx

; allocate 512 bytes of local memory for state and expanded buffer
sub    esp, 80*4+20
mov    edi, esp

; load the 160-bit state
; F(5)x[i]=c->s[i];
push   esi
push   5
pop    ecx
rep    movsd

; load buffer in big endian order
; F(16)w[i]=rev32(c->x.w[i]);
mov    cl, 16
sha1_L0:
lodsd
bswap  eax
stosd
loop   sha1_L0

; expand buffer
; for(i=16;i<80;i++)
;   w[i]=R(w[i-3]^w[i-8]^w[i-14]^w[i-16],1);
mov    cl, 64
sha1_L2:
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   sha1_L2

pop    esi

mov    edi, esp
xchg   eax, ecx     ; i = 0
; permute
sha1_L3:
mov    edx, _c
cmp    al, 20
jae    sha1_L4
; t = FF(x[1],x[2],x[3])+0x5A827999L;
xor    edx, _d
and    edx, _b
xor    edx, _d
add    edx, 0x5A827999
jmp    sha1_L7
sha1_L4:
cmp    al, 40
jae    sha1_L5
; t = HH(x[1],x[2],x[3])+0x6ED9EBA1L;
xor    edx, _d
xor    edx, _b
add    edx, 0x6ED9EBA1
jmp    sha1_L7
sha1_L5:
cmp    al, 60
jae    sha1_L6
; t = GG(x[1],x[2],x[3])+0x8F1BBCDCL;
mov    ebp, edx
or     edx, _d
and    edx, _b
and    ebp, _d
or     edx, ebp
add    edx, 0x8F1BBCDC
jmp    sha1_L7
sha1_L6
; t = HH(x[1],x[2],x[3])+0xCA62C1D6L;
xor    edx, _d
xor    edx, _b
add    edx, 0xCA62C1D6
sha1_L7:
; t+=R(x[0],5)+x[4]+w[i];
mov    ebp, _a
rol    ebp, 5
add    ebp, _e
add    edx, ebp
add    edx, [edi+4*eax+20]

; x[4]=x[3];x[3]=x[2];x[2]=R(x[1],30);x[1]=x[0];x[0]=t;
mov    ebp, _d
mov    _e, ebp
mov    ebp, _c
mov    _d, ebp
mov    ebp, _b
rol    ebp, 30
mov    _c, ebp
mov    ebp, _a
mov    _b, ebp
mov    _a, edx

inc    eax             ; i++
cmp    al, 80          ; i<80
jne    sha1_L3

; update state and return
; F(5)c->s[i]+=x[i];
push   5
pop    ecx
sha1_L8:
mov    edx, [edi]      ; eax=x[i]
add    [esi], edx      ; c->s[i] += edx
cmpsd                  ; advance esi + edi
loop   sha1_L8

lea    esp, [edi+4*eax]
popad
ret
```

### 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.Sources here

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