Replace the sha1 implementation w/ a working one (#9242)

As #9239 points out the old implementation had some serious flaws.
The new implementation is a port of the MIT-licensed one used by
Chromium OS and has been tested against the FIPS-provided vectors and by
generating huge files like the ones mentioned in the issue above.

While I tried my best to take into account the existence of BE machines
the code has only been tested on a LE one.

1 files changed, 167 insertions, 160 deletions

diff --git a/lib/std/sha1.nim b/lib/std/sha1.nim
index c0b1bffcf..e7e6697cf 100644
--- a/lib/std/sha1.nim
+++ b/lib/std/sha1.nim
@@ -10,6 +10,7 @@
 ## Note: Import ``std/sha1`` to use this module
 
 import strutils
+from endians import bigEndian32, bigEndian64
 
 const Sha1DigestSize = 20
 
@@ -17,166 +18,165 @@ type
   Sha1Digest = array[0 .. Sha1DigestSize-1, uint8]
   SecureHash* = distinct Sha1Digest
 
-# Copyright (c) 2011, Micael Hildenborg
-# All rights reserved.
-#
-# Redistribution and use in source and binary forms, with or without
-# modification, are permitted provided that the following conditions are met:
-# * Redistributions of source code must retain the above copyright
-#   notice, this list of conditions and the following disclaimer.
-# * Redistributions in binary form must reproduce the above copyright
-#   notice, this list of conditions and the following disclaimer in the
-#   documentation and/or other materials provided with the distribution.
-# * Neither the name of Micael Hildenborg nor the
-#   names of its contributors may be used to endorse or promote products
-#   derived from this software without specific prior written permission.
-#
-# THIS SOFTWARE IS PROVIDED BY Micael Hildenborg ''AS IS'' AND ANY
-# EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
-# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
-# DISCLAIMED. IN NO EVENT SHALL Micael Hildenborg BE LIABLE FOR ANY
-# DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
-# (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
-# LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
-# ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
-# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
-# SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
-#
-# Ported to Nim by Erik O'Leary
-
 type
-  Sha1State* = array[0 .. 5-1, uint32]
-  Sha1Buffer = array[0 .. 80-1, uint32]
-
-template clearBuffer(w: Sha1Buffer, len = 16) =
-  zeroMem(addr(w), len * sizeof(uint32))
-
-proc init*(result: var Sha1State) =
-  result[0] = 0x67452301'u32
-  result[1] = 0xefcdab89'u32
-  result[2] = 0x98badcfe'u32
-  result[3] = 0x10325476'u32
-  result[4] = 0xc3d2e1f0'u32
-
-proc innerHash(state: var Sha1State, w: var Sha1Buffer) =
-  var
-    a = state[0]
-    b = state[1]
-    c = state[2]
-    d = state[3]
-    e = state[4]
-
-  var round = 0
-
-  template rot(value, bits: uint32): uint32 =
-    (value shl bits) or (value shr (32u32 - bits))
-
-  template sha1(fun, val: uint32) =
-    let t = rot(a, 5) + fun + e + val + w[round]
-    e = d
-    d = c
-    c = rot(b, 30)
-    b = a
-    a = t
-
-  template process(body: untyped) =
-    w[round] = rot(w[round - 3] xor w[round - 8] xor w[round - 14] xor w[round - 16], 1)
-    body
-    inc(round)
-
-  template wrap(dest, value: untyped) =
-    let v = dest + value
-    dest = v
-
-  while round < 16:
-    sha1((b and c) or (not b and d), 0x5a827999'u32)
-    inc(round)
-
-  while round < 20:
-    process:
-      sha1((b and c) or (not b and d), 0x5a827999'u32)
-
-  while round < 40:
-    process:
-      sha1(b xor c xor d, 0x6ed9eba1'u32)
-
-  while round < 60:
-    process:
-      sha1((b and c) or (b and d) or (c and d), 0x8f1bbcdc'u32)
-
-  while round < 80:
-    process:
-      sha1(b xor c xor d, 0xca62c1d6'u32)
-
-  wrap state[0], a
-  wrap state[1], b
-  wrap state[2], c
-  wrap state[3], d
-  wrap state[4], e
-
-proc sha1(src: cstring; len: int): Sha1Digest =
-  #Initialize state
-  var state: Sha1State
-  init(state)
-
-  #Create w buffer
-  var w: Sha1Buffer
-
-  #Loop through all complete 64byte blocks.
-  let byteLen = len
-  let endOfFullBlocks = byteLen - 64
-  var endCurrentBlock = 0
-  var currentBlock = 0
-
-  while currentBlock <= endOfFullBlocks:
-    endCurrentBlock = currentBlock + 64
-
-    var i = 0
-    while currentBlock < endCurrentBlock:
-      w[i] = uint32(src[currentBlock+3]) or
-             uint32(src[currentBlock+2]) shl 8'u32 or
-             uint32(src[currentBlock+1]) shl 16'u32 or
-             uint32(src[currentBlock])   shl 24'u32
-      currentBlock += 4
-      inc(i)
-
-    innerHash(state, w)
-
-  #Handle last and not full 64 byte block if existing
-  endCurrentBlock = byteLen - currentBlock
-  clearBuffer(w)
-  var lastBlockBytes = 0
-
-  while lastBlockBytes < endCurrentBlock:
-
-    var value = uint32(src[lastBlockBytes + currentBlock]) shl
-                ((3'u32 - uint32(lastBlockBytes and 3)) shl 3)
-
-    w[lastBlockBytes shr 2] = w[lastBlockBytes shr 2] or value
-    inc(lastBlockBytes)
-
-  w[lastBlockBytes shr 2] = w[lastBlockBytes shr 2] or (
-    0x80'u32 shl ((3'u32 - uint32(lastBlockBytes and 3)) shl 3)
-  )
-
-  if endCurrentBlock >= 56:
-    innerHash(state, w)
-    clearBuffer(w)
-
-  w[15] = uint32(byteLen) shl 3
-  innerHash(state, w)
-
-  # Store hash in result pointer, and make sure we get in in the correct order
-  # on both endian models.
-  for i in 0 .. Sha1DigestSize-1:
-    result[i] = uint8((int(state[i shr 2]) shr ((3-(i and 3)) * 8)) and 255)
-
-proc sha1(src: string): Sha1Digest =
-  ## Calculate SHA1 from input string
-  sha1(src, src.len)
-
-proc secureHash*(str: string): SecureHash = SecureHash(sha1(str))
-proc secureHashFile*(filename: string): SecureHash = secureHash(readFile(filename))
+  Sha1State = object
+    count: int
+    state: array[5, uint32]
+    buf:   array[64, byte]
+
+# This implementation of the SHA1 algorithm was ported from the Chromium OS one
+# with minor modifications that should not affect its functionality.
+
+proc newSha1State(): Sha1State =
+  result.count = 0
+  result.state[0] = 0x67452301'u32
+  result.state[1] = 0xEFCDAB89'u32
+  result.state[2] = 0x98BADCFE'u32
+  result.state[3] = 0x10325476'u32
+  result.state[4] = 0xC3D2E1F0'u32
+
+template ror27(val: uint32): uint32 = (val shr 27) or (val shl  5)
+template ror2 (val: uint32): uint32 = (val shr  2) or (val shl 30)
+template ror31(val: uint32): uint32 = (val shr 31) or (val shl  1)
+
+proc transform(ctx: var Sha1State) =
+  var W: array[80, uint32]
+  var A, B, C, D, E: uint32
+  var t = 0
+
+  A = ctx.state[0]
+  B = ctx.state[1]
+  C = ctx.state[2]
+  D = ctx.state[3]
+  E = ctx.state[4]
+
+  template SHA_F1(A, B, C, D, E, t: untyped) =
+    bigEndian32(addr W[t], addr ctx.buf[t * 4])
+    E += ror27(A) + W[t] + (D xor (B and (C xor D))) + 0x5A827999'u32
+    B = ror2(B)
+
+  while t < 15:
+    SHA_F1(A, B, C, D, E, t + 0)
+    SHA_F1(E, A, B, C, D, t + 1)
+    SHA_F1(D, E, A, B, C, t + 2)
+    SHA_F1(C, D, E, A, B, t + 3)
+    SHA_F1(B, C, D, E, A, t + 4)
+    t += 5
+  SHA_F1(A, B, C, D, E, t + 0) # 16th one, t == 15
+
+  template SHA_F11(A, B, C, D, E, t: untyped) =
+    W[t] = ror31(W[t-3] xor W[t-8] xor W[t-14] xor W[t-16])
+    E += ror27(A) + W[t] + (D xor (B and (C xor D))) + 0x5A827999'u32
+    B = ror2(B)
+
+  SHA_F11(E, A, B, C, D, t + 1)
+  SHA_F11(D, E, A, B, C, t + 2)
+  SHA_F11(C, D, E, A, B, t + 3)
+  SHA_F11(B, C, D, E, A, t + 4)
+
+  template SHA_F2(A, B, C, D, E, t: untyped) =
+    W[t] = ror31(W[t-3] xor W[t-8] xor W[t-14] xor W[t-16])
+    E += ror27(A) + W[t] + (B xor C xor D) + 0x6ED9EBA1'u32
+    B = ror2(B)
+
+  t = 20
+  while t < 40:
+    SHA_F2(A, B, C, D, E, t + 0)
+    SHA_F2(E, A, B, C, D, t + 1)
+    SHA_F2(D, E, A, B, C, t + 2)
+    SHA_F2(C, D, E, A, B, t + 3)
+    SHA_F2(B, C, D, E, A, t + 4)
+    t += 5
+
+  template SHA_F3(A, B, C, D, E, t: untyped) =
+    W[t] = ror31(W[t-3] xor W[t-8] xor W[t-14] xor W[t-16])
+    E += ror27(A) + W[t] + ((B and C) or (D and (B or C))) + 0x8F1BBCDC'u32
+    B = ror2(B)
+
+  while t < 60:
+    SHA_F3(A, B, C, D, E, t + 0)
+    SHA_F3(E, A, B, C, D, t + 1)
+    SHA_F3(D, E, A, B, C, t + 2)
+    SHA_F3(C, D, E, A, B, t + 3)
+    SHA_F3(B, C, D, E, A, t + 4)
+    t += 5
+
+  template SHA_F4(A, B, C, D, E, t: untyped) =
+    W[t] = ror31(W[t-3] xor W[t-8] xor W[t-14] xor W[t-16])
+    E += ror27(A) + W[t] + (B xor C xor D) + 0xCA62C1D6'u32
+    B = ror2(B)
+
+  while t < 80:
+    SHA_F4(A, B, C, D, E, t + 0)
+    SHA_F4(E, A, B, C, D, t + 1)
+    SHA_F4(D, E, A, B, C, t + 2)
+    SHA_F4(C, D, E, A, B, t + 3)
+    SHA_F4(B, C, D, E, A, t + 4)
+    t += 5
+
+  ctx.state[0] += A
+  ctx.state[1] += B
+  ctx.state[2] += C
+  ctx.state[3] += D
+  ctx.state[4] += E
+
+proc update(ctx: var Sha1State, data: openArray[char]) =
+  var i = ctx.count mod 64
+  var j = 0
+  var len = data.len
+  # Gather 64-bytes worth of data in order to perform a round with the leftover
+  # data we had stored (but not processed yet)
+  if len > 64 - i:
+    copyMem(addr ctx.buf[i], unsafeAddr data[j], 64 - i)
+    len -= 64 - i
+    j += 64 - i
+    transform(ctx)
+    # Update the index since it's used in the while loop below _and_ we want to
+    # keep its value if this code path isn't executed
+    i = 0
+  # Process the bulk of the payload
+  while len >= 64:
+    copyMem(addr ctx.buf[0], unsafeAddr data[j], 64)
+    len -= 64
+    j += 64
+    transform(ctx)
+  # Process the tail of the payload (len is < 64)
+  while len > 0:
+    dec len
+    ctx.buf[i] = byte(data[j])
+    inc i
+    inc j
+    if i == 64:
+      transform(ctx)
+      i = 0
+  ctx.count += data.len
+
+proc finalize(ctx: var Sha1State): Sha1Digest =
+  var cnt = uint64(ctx.count * 8)
+  # A 1 bit
+  update(ctx, "\x80")
+  # Add padding until we reach a complexive size of 64 - 8 bytes
+  while (ctx.count mod 64) != (64 - 8):
+    update(ctx, "\x00")
+  # The message length as a 64bit BE number completes the block
+  var tmp: array[8, char]
+  bigEndian64(addr tmp[0], addr cnt)
+  update(ctx, tmp)
+  # Turn the result into a single 160-bit number
+  for i in 0 ..< 5:
+    bigEndian32(addr ctx.state[i], addr ctx.state[i])
+  copyMem(addr result[0], addr ctx.state[0], Sha1DigestSize)
+
+# Public API
+
+proc secureHash*(str: string): SecureHash =
+  var state = newSha1State()
+  state.update(str)
+  SecureHash(state.finalize())
+
+proc secureHashFile*(filename: string): SecureHash =
+  secureHash(readFile(filename))
+
 proc `$`*(self: SecureHash): string =
   result = ""
   for v in Sha1Digest(self):
@@ -190,8 +190,15 @@ proc `==`*(a, b: SecureHash): bool =
   # Not a constant-time comparison, but that's acceptable in this context
   Sha1Digest(a) == Sha1Digest(b)
 
-
 when isMainModule:
   let hash1 = secureHash("a93tgj0p34jagp9[agjp98ajrhp9aej]")
   doAssert hash1 == hash1
   doAssert parseSecureHash($hash1) == hash1
+
+  template checkVector(s, exp: string) =
+    doAssert secureHash(s) == parseSecureHash(exp)
+
+  checkVector("", "da39a3ee5e6b4b0d3255bfef95601890afd80709")
+  checkVector("abc", "a9993e364706816aba3e25717850c26c9cd0d89d")
+  checkVector("abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq",
+              "84983e441c3bd26ebaae4aa1f95129e5e54670f1")