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.

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s