* Added SHA-1 support. `nix-hash' now has an option `--type sha1' to

  select SHA-1 hashing.

5 files changed, 471 insertions, 21 deletions

diff --git a/src/libutil/Makefile.am b/src/libutil/Makefile.am
index a7ff1b6e03..12459b1db5 100644
--- a/src/libutil/Makefile.am
+++ b/src/libutil/Makefile.am
@@ -1,6 +1,7 @@
 noinst_LIBRARIES = libutil.a
 
 libutil_a_SOURCES = util.cc util.hh hash.cc hash.hh \
- archive.cc archive.hh md5.c md5.h aterm.cc aterm.hh
+ archive.cc archive.hh md5.c md5.h sha1.c sha1.h \
+ aterm.cc aterm.hh 
 
 AM_CXXFLAGS = -Wall -I.. ${aterm_include}
diff --git a/src/libutil/hash.cc b/src/libutil/hash.cc
index 1a44c85341..46334ad820 100644
--- a/src/libutil/hash.cc
+++ b/src/libutil/hash.cc
@@ -2,17 +2,24 @@
 
 extern "C" {
 #include "md5.h"
+#include "sha1.h"
 }
 
 #include "hash.hh"
 #include "archive.hh"
 
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <fcntl.h>
+
+
 
 Hash::Hash(HashType type)
 {
     this->type = type;
     if (type == htMD5) hashSize = md5HashSize;
     else if (type == htSHA1) hashSize = sha1HashSize;
+    else throw Error("unknown hash type");
     memset(hash, 0, hashSize);
 }
 
@@ -85,44 +92,90 @@ bool isHash(const string & s)
 }
 
 
-Hash hashString(const string & s)
+struct Ctx
 {
-    Hash hash(htMD5);
-    md5_buffer(s.c_str(), s.length(), hash.hash);
+    md5_ctx md5;
+    sha_ctx sha1;
+};
+
+
+static void start(HashType ht, Ctx & ctx)
+{
+    if (ht == htMD5) md5_init_ctx(&ctx.md5);
+    else if (ht == htSHA1) sha_init(&ctx.sha1);
+}
+
+
+static void update(HashType ht, Ctx & ctx,
+    const unsigned char * bytes, unsigned int len)
+{
+    if (ht == htMD5) md5_process_bytes(bytes, len, &ctx.md5);
+    else if (ht == htSHA1) sha_update(&ctx.sha1, bytes, len);
+}
+
+
+static void finish(HashType ht, Ctx & ctx, unsigned char * hash)
+{
+    if (ht == htMD5) md5_finish_ctx(&ctx.md5, hash);
+    else if (ht == htSHA1) {
+        sha_final(&ctx.sha1);
+        sha_digest(&ctx.sha1, hash);
+    }
+}
+
+
+Hash hashString(const string & s, HashType ht)
+{
+    Ctx ctx;
+    Hash hash(ht);
+    start(ht, ctx);
+    update(ht, ctx, (const unsigned char *) s.c_str(), s.length());
+    finish(ht, ctx, hash.hash);
     return hash;
 }
 
 
-Hash hashFile(const Path & path)
+Hash hashFile(const Path & path, HashType ht)
 {
-    Hash hash(htMD5);
-    FILE * file = fopen(path.c_str(), "rb");
-    if (!file)
-        throw SysError(format("file `%1%' does not exist") % path);
-    int err = md5_stream(file, hash.hash);
-    fclose(file);
-    if (err) throw SysError(format("cannot hash file `%1%'") % path);
+    Ctx ctx;
+    Hash hash(ht);
+    start(ht, ctx);
+
+    AutoCloseFD fd = open(path.c_str(), O_RDONLY);
+    if (fd == -1) throw SysError(format("opening file `%1%'") % path);
+
+    unsigned char buf[8192];
+    ssize_t n;
+    while ((n = read(fd, buf, sizeof(buf)))) {
+        checkInterrupt();
+        if (n == -1) throw SysError(format("reading file `%1%'") % path);
+        update(ht, ctx, buf, n);
+    }
+    
+    finish(ht, ctx, hash.hash);
     return hash;
 }
 
 
 struct HashSink : DumpSink
 {
-    struct md5_ctx ctx;
+    HashType ht;
+    Ctx ctx;
     virtual void operator ()
         (const unsigned char * data, unsigned int len)
     {
-        md5_process_bytes(data, len, &ctx);
+        update(ht, ctx, data, len);
     }
 };
 
 
-Hash hashPath(const Path & path)
+Hash hashPath(const Path & path, HashType ht)
 {
-    Hash hash(htMD5);
     HashSink sink;
-    md5_init_ctx(&sink.ctx);
+    sink.ht = ht;
+    Hash hash(ht);
+    start(ht, sink.ctx);
     dumpPath(path, sink);
-    md5_finish_ctx(&sink.ctx, hash.hash);
+    finish(ht, sink.ctx, hash.hash);
     return hash;
 }
diff --git a/src/libutil/hash.hh b/src/libutil/hash.hh
index 0b5e46cc6b..1d2fce6455 100644
--- a/src/libutil/hash.hh
+++ b/src/libutil/hash.hh
@@ -47,15 +47,15 @@ Hash parseHash(const string & s);
 bool isHash(const string & s);
 
 /* Compute the hash of the given string. */
-Hash hashString(const string & s);
+Hash hashString(const string & s, HashType ht);
 
 /* Compute the hash of the given file. */
-Hash hashFile(const Path & path);
+Hash hashFile(const Path & path, HashType ht);
 
 /* Compute the hash of the given path.  The hash is defined as
    md5(dump(path)).
 */
-Hash hashPath(const Path & path);
+Hash hashPath(const Path & path, HashType ht);
 
 
 #endif /* !__HASH_H */
diff --git a/src/libutil/sha1.c b/src/libutil/sha1.c
new file mode 100644
index 0000000000..799e8bd7e6
--- /dev/null
+++ b/src/libutil/sha1.c
@@ -0,0 +1,368 @@
+/* $Id$ */
+
+/* sha.c - Implementation of the Secure Hash Algorithm
+ *
+ * Copyright (C) 1995, A.M. Kuchling
+ *
+ * Distribute and use freely; there are no restrictions on further 
+ * dissemination and usage except those imposed by the laws of your 
+ * country of residence.
+ *
+ * Adapted to pike and some cleanup by Niels Möller.
+ */
+
+/* $Id$ */
+
+/* SHA: NIST's Secure Hash Algorithm */
+
+/* Based on SHA code originally posted to sci.crypt by Peter Gutmann
+   in message <30ajo5$oe8@ccu2.auckland.ac.nz>.
+   Modified to test for endianness on creation of SHA objects by AMK.
+   Also, the original specification of SHA was found to have a weakness
+   by NSA/NIST.  This code implements the fixed version of SHA.
+*/
+
+/* Here's the first paragraph of Peter Gutmann's posting:
+   
+The following is my SHA (FIPS 180) code updated to allow use of the "fixed"
+SHA, thanks to Jim Gillogly and an anonymous contributor for the information on
+what's changed in the new version.  The fix is a simple change which involves
+adding a single rotate in the initial expansion function.  It is unknown
+whether this is an optimal solution to the problem which was discovered in the
+SHA or whether it's simply a bandaid which fixes the problem with a minimum of
+effort (for example the reengineering of a great many Capstone chips).
+*/
+
+#include "sha1.h"
+
+#include <string.h>
+
+void sha_copy(struct sha_ctx *dest, struct sha_ctx *src)
+{
+  unsigned int i;
+
+  dest->count_l=src->count_l;
+  dest->count_h=src->count_h;
+  for(i=0; i<SHA_DIGESTLEN; i++)
+    dest->digest[i]=src->digest[i];
+  for(i=0; i < src->index; i++)
+    dest->block[i] = src->block[i];
+  dest->index = src->index;
+}
+
+
+/* The SHA f()-functions.  The f1 and f3 functions can be optimized to
+   save one boolean operation each - thanks to Rich Schroeppel,
+   rcs@cs.arizona.edu for discovering this */
+
+/*#define f1(x,y,z) ( ( x & y ) | ( ~x & z ) )          // Rounds  0-19 */
+#define f1(x,y,z)   ( z ^ ( x & ( y ^ z ) ) )           /* Rounds  0-19 */
+#define f2(x,y,z)   ( x ^ y ^ z )                       /* Rounds 20-39 */
+/*#define f3(x,y,z) ( ( x & y ) | ( x & z ) | ( y & z ) )   // Rounds 40-59 */
+#define f3(x,y,z)   ( ( x & y ) | ( z & ( x | y ) ) )   /* Rounds 40-59 */
+#define f4(x,y,z)   ( x ^ y ^ z )                       /* Rounds 60-79 */
+
+/* The SHA Mysterious Constants */
+
+#define K1  0x5A827999L                                 /* Rounds  0-19 */
+#define K2  0x6ED9EBA1L                                 /* Rounds 20-39 */
+#define K3  0x8F1BBCDCL                                 /* Rounds 40-59 */
+#define K4  0xCA62C1D6L                                 /* Rounds 60-79 */
+
+/* SHA initial values */
+
+#define h0init  0x67452301L
+#define h1init  0xEFCDAB89L
+#define h2init  0x98BADCFEL
+#define h3init  0x10325476L
+#define h4init  0xC3D2E1F0L
+
+/* 32-bit rotate left - kludged with shifts */
+
+#define ROTL(n,X)  ( ( (X) << (n) ) | ( (X) >> ( 32 - (n) ) ) )
+
+/* The initial expanding function.  The hash function is defined over an
+   80-word expanded input array W, where the first 16 are copies of the input
+   data, and the remaining 64 are defined by
+
+        W[ i ] = W[ i - 16 ] ^ W[ i - 14 ] ^ W[ i - 8 ] ^ W[ i - 3 ]
+
+   This implementation generates these values on the fly in a circular
+   buffer - thanks to Colin Plumb, colin@nyx10.cs.du.edu for this
+   optimization.
+
+   The updated SHA changes the expanding function by adding a rotate of 1
+   bit.  Thanks to Jim Gillogly, jim@rand.org, and an anonymous contributor
+   for this information */
+
+#define expand(W,i) ( W[ i & 15 ] = \
+		      ROTL( 1, ( W[ i & 15 ] ^ W[ (i - 14) & 15 ] ^ \
+				 W[ (i - 8) & 15 ] ^ W[ (i - 3) & 15 ] ) ) )
+
+
+/* The prototype SHA sub-round.  The fundamental sub-round is:
+
+        a' = e + ROTL( 5, a ) + f( b, c, d ) + k + data;
+        b' = a;
+        c' = ROTL( 30, b );
+        d' = c;
+        e' = d;
+
+   but this is implemented by unrolling the loop 5 times and renaming the
+   variables ( e, a, b, c, d ) = ( a', b', c', d', e' ) each iteration.
+   This code is then replicated 20 times for each of the 4 functions, using
+   the next 20 values from the W[] array each time */
+
+#define subRound(a, b, c, d, e, f, k, data) \
+    ( e += ROTL( 5, a ) + f( b, c, d ) + k + data, b = ROTL( 30, b ) )
+
+/* Initialize the SHA values */
+
+void sha_init(struct sha_ctx *ctx)
+{
+  /* Set the h-vars to their initial values */
+  ctx->digest[ 0 ] = h0init;
+  ctx->digest[ 1 ] = h1init;
+  ctx->digest[ 2 ] = h2init;
+  ctx->digest[ 3 ] = h3init;
+  ctx->digest[ 4 ] = h4init;
+
+  /* Initialize bit count */
+  ctx->count_l = ctx->count_h = 0;
+  
+  /* Initialize buffer */
+  ctx->index = 0;
+}
+
+/* Perform the SHA transformation.  Note that this code, like MD5, seems to
+   break some optimizing compilers due to the complexity of the expressions
+   and the size of the basic block.  It may be necessary to split it into
+   sections, e.g. based on the four subrounds
+
+   Note that this function destroys the data area */
+
+static void sha_transform(struct sha_ctx *ctx, uint32_t *data )
+{
+  uint32_t A, B, C, D, E;     /* Local vars */
+
+  /* Set up first buffer and local data buffer */
+  A = ctx->digest[0];
+  B = ctx->digest[1];
+  C = ctx->digest[2];
+  D = ctx->digest[3];
+  E = ctx->digest[4];
+
+  /* Heavy mangling, in 4 sub-rounds of 20 interations each. */
+  subRound( A, B, C, D, E, f1, K1, data[ 0] );
+  subRound( E, A, B, C, D, f1, K1, data[ 1] );
+  subRound( D, E, A, B, C, f1, K1, data[ 2] );
+  subRound( C, D, E, A, B, f1, K1, data[ 3] );
+  subRound( B, C, D, E, A, f1, K1, data[ 4] );
+  subRound( A, B, C, D, E, f1, K1, data[ 5] );
+  subRound( E, A, B, C, D, f1, K1, data[ 6] );
+  subRound( D, E, A, B, C, f1, K1, data[ 7] );
+  subRound( C, D, E, A, B, f1, K1, data[ 8] );
+  subRound( B, C, D, E, A, f1, K1, data[ 9] );
+  subRound( A, B, C, D, E, f1, K1, data[10] );
+  subRound( E, A, B, C, D, f1, K1, data[11] );
+  subRound( D, E, A, B, C, f1, K1, data[12] );
+  subRound( C, D, E, A, B, f1, K1, data[13] );
+  subRound( B, C, D, E, A, f1, K1, data[14] );
+  subRound( A, B, C, D, E, f1, K1, data[15] );
+  subRound( E, A, B, C, D, f1, K1, expand( data, 16 ) );
+  subRound( D, E, A, B, C, f1, K1, expand( data, 17 ) );
+  subRound( C, D, E, A, B, f1, K1, expand( data, 18 ) );
+  subRound( B, C, D, E, A, f1, K1, expand( data, 19 ) );
+
+  subRound( A, B, C, D, E, f2, K2, expand( data, 20 ) );
+  subRound( E, A, B, C, D, f2, K2, expand( data, 21 ) );
+  subRound( D, E, A, B, C, f2, K2, expand( data, 22 ) );
+  subRound( C, D, E, A, B, f2, K2, expand( data, 23 ) );
+  subRound( B, C, D, E, A, f2, K2, expand( data, 24 ) );
+  subRound( A, B, C, D, E, f2, K2, expand( data, 25 ) );
+  subRound( E, A, B, C, D, f2, K2, expand( data, 26 ) );
+  subRound( D, E, A, B, C, f2, K2, expand( data, 27 ) );
+  subRound( C, D, E, A, B, f2, K2, expand( data, 28 ) );
+  subRound( B, C, D, E, A, f2, K2, expand( data, 29 ) );
+  subRound( A, B, C, D, E, f2, K2, expand( data, 30 ) );
+  subRound( E, A, B, C, D, f2, K2, expand( data, 31 ) );
+  subRound( D, E, A, B, C, f2, K2, expand( data, 32 ) );
+  subRound( C, D, E, A, B, f2, K2, expand( data, 33 ) );
+  subRound( B, C, D, E, A, f2, K2, expand( data, 34 ) );
+  subRound( A, B, C, D, E, f2, K2, expand( data, 35 ) );
+  subRound( E, A, B, C, D, f2, K2, expand( data, 36 ) );
+  subRound( D, E, A, B, C, f2, K2, expand( data, 37 ) );
+  subRound( C, D, E, A, B, f2, K2, expand( data, 38 ) );
+  subRound( B, C, D, E, A, f2, K2, expand( data, 39 ) );
+
+  subRound( A, B, C, D, E, f3, K3, expand( data, 40 ) );
+  subRound( E, A, B, C, D, f3, K3, expand( data, 41 ) );
+  subRound( D, E, A, B, C, f3, K3, expand( data, 42 ) );
+  subRound( C, D, E, A, B, f3, K3, expand( data, 43 ) );
+  subRound( B, C, D, E, A, f3, K3, expand( data, 44 ) );
+  subRound( A, B, C, D, E, f3, K3, expand( data, 45 ) );
+  subRound( E, A, B, C, D, f3, K3, expand( data, 46 ) );
+  subRound( D, E, A, B, C, f3, K3, expand( data, 47 ) );
+  subRound( C, D, E, A, B, f3, K3, expand( data, 48 ) );
+  subRound( B, C, D, E, A, f3, K3, expand( data, 49 ) );
+  subRound( A, B, C, D, E, f3, K3, expand( data, 50 ) );
+  subRound( E, A, B, C, D, f3, K3, expand( data, 51 ) );
+  subRound( D, E, A, B, C, f3, K3, expand( data, 52 ) );
+  subRound( C, D, E, A, B, f3, K3, expand( data, 53 ) );
+  subRound( B, C, D, E, A, f3, K3, expand( data, 54 ) );
+  subRound( A, B, C, D, E, f3, K3, expand( data, 55 ) );
+  subRound( E, A, B, C, D, f3, K3, expand( data, 56 ) );
+  subRound( D, E, A, B, C, f3, K3, expand( data, 57 ) );
+  subRound( C, D, E, A, B, f3, K3, expand( data, 58 ) );
+  subRound( B, C, D, E, A, f3, K3, expand( data, 59 ) );
+
+  subRound( A, B, C, D, E, f4, K4, expand( data, 60 ) );
+  subRound( E, A, B, C, D, f4, K4, expand( data, 61 ) );
+  subRound( D, E, A, B, C, f4, K4, expand( data, 62 ) );
+  subRound( C, D, E, A, B, f4, K4, expand( data, 63 ) );
+  subRound( B, C, D, E, A, f4, K4, expand( data, 64 ) );
+  subRound( A, B, C, D, E, f4, K4, expand( data, 65 ) );
+  subRound( E, A, B, C, D, f4, K4, expand( data, 66 ) );
+  subRound( D, E, A, B, C, f4, K4, expand( data, 67 ) );
+  subRound( C, D, E, A, B, f4, K4, expand( data, 68 ) );
+  subRound( B, C, D, E, A, f4, K4, expand( data, 69 ) );
+  subRound( A, B, C, D, E, f4, K4, expand( data, 70 ) );
+  subRound( E, A, B, C, D, f4, K4, expand( data, 71 ) );
+  subRound( D, E, A, B, C, f4, K4, expand( data, 72 ) );
+  subRound( C, D, E, A, B, f4, K4, expand( data, 73 ) );
+  subRound( B, C, D, E, A, f4, K4, expand( data, 74 ) );
+  subRound( A, B, C, D, E, f4, K4, expand( data, 75 ) );
+  subRound( E, A, B, C, D, f4, K4, expand( data, 76 ) );
+  subRound( D, E, A, B, C, f4, K4, expand( data, 77 ) );
+  subRound( C, D, E, A, B, f4, K4, expand( data, 78 ) );
+  subRound( B, C, D, E, A, f4, K4, expand( data, 79 ) );
+
+  /* Build message digest */
+  ctx->digest[0] += A;
+  ctx->digest[1] += B;
+  ctx->digest[2] += C;
+  ctx->digest[3] += D;
+  ctx->digest[4] += E;
+}
+
+#if 1
+
+#ifndef EXTRACT_UCHAR
+#define EXTRACT_UCHAR(p)  (*(unsigned char *)(p))
+#endif
+
+#define STRING2INT(s) ((((((EXTRACT_UCHAR(s) << 8)    \
+			 | EXTRACT_UCHAR(s+1)) << 8)  \
+			 | EXTRACT_UCHAR(s+2)) << 8)  \
+			 | EXTRACT_UCHAR(s+3))
+#else
+uint32_t STRING2INT(unsigned char *s)
+{
+  uint32_t r;
+  unsigned int i;
+  
+  for (i = 0, r = 0; i < 4; i++, s++)
+    r = (r << 8) | *s;
+  return r;
+}
+#endif
+
+static void sha_block(struct sha_ctx *ctx, const unsigned char *block)
+{
+  uint32_t data[SHA_DATALEN];
+  unsigned int i;
+  
+  /* Update block count */
+  if (!++ctx->count_l)
+    ++ctx->count_h;
+
+  /* Endian independent conversion */
+  for (i = 0; i<SHA_DATALEN; i++, block += 4)
+    data[i] = STRING2INT(block);
+
+  sha_transform(ctx, data);
+}
+
+void sha_update(struct sha_ctx *ctx, const unsigned char *buffer, uint32_t len)
+{
+  if (ctx->index)
+    { /* Try to fill partial block */
+      unsigned left = SHA_DATASIZE - ctx->index;
+      if (len < left)
+	{
+	  memcpy(ctx->block + ctx->index, buffer, len);
+	  ctx->index += len;
+	  return; /* Finished */
+	}
+      else
+	{
+	  memcpy(ctx->block + ctx->index, buffer, left);
+	  sha_block(ctx, ctx->block);
+	  buffer += left;
+	  len -= left;
+	}
+    }
+  while (len >= SHA_DATASIZE)
+    {
+      sha_block(ctx, buffer);
+      buffer += SHA_DATASIZE;
+      len -= SHA_DATASIZE;
+    }
+  if ((ctx->index = len))     /* This assignment is intended */
+    /* Buffer leftovers */
+    memcpy(ctx->block, buffer, len);
+}
+	  
+/* Final wrapup - pad to SHA_DATASIZE-byte boundary with the bit pattern
+   1 0* (64-bit count of bits processed, MSB-first) */
+
+void sha_final(struct sha_ctx *ctx)
+{
+  uint32_t data[SHA_DATALEN];
+  unsigned int i;
+  unsigned int words;
+  
+  i = ctx->index;
+  /* Set the first char of padding to 0x80.  This is safe since there is
+     always at least one byte free */
+  ctx->block[i++] = 0x80;
+
+  /* Fill rest of word */
+  for( ; i & 3; i++)
+    ctx->block[i] = 0;
+
+  /* i is now a multiple of the word size 4 */
+  words = i >> 2;
+  for (i = 0; i < words; i++)
+    data[i] = STRING2INT(ctx->block + 4*i);
+  
+  if (words > (SHA_DATALEN-2))
+    { /* No room for length in this block. Process it and
+       * pad with another one */
+      for (i = words ; i < SHA_DATALEN; i++)
+	data[i] = 0;
+      sha_transform(ctx, data);
+      for (i = 0; i < (SHA_DATALEN-2); i++)
+	data[i] = 0;
+    }
+  else
+    for (i = words ; i < SHA_DATALEN - 2; i++)
+      data[i] = 0;
+  /* Theres 512 = 2^9 bits in one block */
+  data[SHA_DATALEN-2] = (ctx->count_h << 9) | (ctx->count_l >> 23);
+  data[SHA_DATALEN-1] = (ctx->count_l << 9) | (ctx->index << 3);
+  sha_transform(ctx, data);
+}
+
+void sha_digest(struct sha_ctx *ctx, unsigned char *s)
+{
+  unsigned int i;
+
+  for (i = 0; i < SHA_DIGESTLEN; i++)
+    {
+      *s++ =         ctx->digest[i] >> 24;
+      *s++ = 0xff & (ctx->digest[i] >> 16);
+      *s++ = 0xff & (ctx->digest[i] >> 8);
+      *s++ = 0xff &  ctx->digest[i];
+    }
+}
diff --git a/src/libutil/sha1.h b/src/libutil/sha1.h
new file mode 100644
index 0000000000..012893bd3b
--- /dev/null
+++ b/src/libutil/sha1.h
@@ -0,0 +1,28 @@
+#ifndef _SHA_H
+#define _SHA_H
+
+#include <stdint.h>
+
+/* The SHA block size and message digest sizes, in bytes */
+
+#define SHA_DATASIZE    64
+#define SHA_DATALEN     16
+#define SHA_DIGESTSIZE  20
+#define SHA_DIGESTLEN    5
+/* The structure for storing SHA info */
+
+struct sha_ctx {
+  uint32_t digest[SHA_DIGESTLEN];  /* Message digest */
+  uint32_t count_l, count_h;       /* 64-bit block count */
+  uint8_t block[SHA_DATASIZE];     /* SHA data buffer */
+  unsigned int index;            /* index into buffer */
+};
+
+void sha_init(struct sha_ctx *ctx);
+void sha_update(struct sha_ctx *ctx, const unsigned char *buffer, uint32_t len);
+void sha_final(struct sha_ctx *ctx);
+void sha_digest(struct sha_ctx *ctx, unsigned char *s);
+void sha_copy(struct sha_ctx *dest, struct sha_ctx *src);
+
+
+#endif /* !_SHA_H */