Provides implementation of MD4 hashing algorithm.

See IETF RFC 1320, http://tools.ietf.org/html/rfc1320.
Fixes issue 279.

R=rsc
http://codereview.appspot.com/159051

Committer: Russ Cox <rsc@golang.org>

5 files changed, 279 insertions, 0 deletions

diff --git a/src/pkg/Makefile b/src/pkg/Makefile
index c9e070e62..549377db2 100644
--- a/src/pkg/Makefile
+++ b/src/pkg/Makefile
@@ -28,6 +28,7 @@ DIRS=\
 	crypto/aes\
 	crypto/block\
 	crypto/hmac\
+	crypto/md4\
 	crypto/md5\
 	crypto/rc4\
 	crypto/rsa\
diff --git a/src/pkg/crypto/md4/Makefile b/src/pkg/crypto/md4/Makefile
new file mode 100644
index 000000000..087d89866
--- /dev/null
+++ b/src/pkg/crypto/md4/Makefile
@@ -0,0 +1,12 @@
+# Copyright 2009 The Go Authors. All rights reserved.
+# Use of this source code is governed by a BSD-style
+# license that can be found in the LICENSE file.
+
+include $(GOROOT)/src/Make.$(GOARCH)
+
+TARG=crypto/md4
+GOFILES=\
+	md4.go\
+	md4block.go\
+
+include $(GOROOT)/src/Make.pkg
diff --git a/src/pkg/crypto/md4/md4.go b/src/pkg/crypto/md4/md4.go
new file mode 100644
index 000000000..8efb74e47
--- /dev/null
+++ b/src/pkg/crypto/md4/md4.go
@@ -0,0 +1,115 @@
+// Copyright 2009 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// This package implements the MD4 hash algorithm as defined in RFC 1320.
+package md4
+
+import (
+	"hash";
+	"os";
+)
+
+// The size of an MD4 checksum in bytes.
+const Size = 16
+
+const (
+	_Chunk	= 64;
+	_Init0	= 0x67452301;
+	_Init1	= 0xEFCDAB89;
+	_Init2	= 0x98BADCFE;
+	_Init3	= 0x10325476;
+)
+
+// digest represents the partial evaluation of a checksum.
+type digest struct {
+	s	[4]uint32;
+	x	[_Chunk]byte;
+	nx	int;
+	len	uint64;
+}
+
+func (d *digest) Reset() {
+	d.s[0] = _Init0;
+	d.s[1] = _Init1;
+	d.s[2] = _Init2;
+	d.s[3] = _Init3;
+	d.nx = 0;
+	d.len = 0;
+}
+
+// New returns a new hash.Hash computing the MD4 checksum.
+func New() hash.Hash {
+	d := new(digest);
+	d.Reset();
+	return d;
+}
+
+func (d *digest) Size() int	{ return Size }
+
+func (d *digest) Write(p []byte) (nn int, err os.Error) {
+	nn = len(p);
+	d.len += uint64(nn);
+	if d.nx > 0 {
+		n := len(p);
+		if n > _Chunk-d.nx {
+			n = _Chunk - d.nx
+		}
+		for i := 0; i < n; i++ {
+			d.x[d.nx+i] = p[i]
+		}
+		d.nx += n;
+		if d.nx == _Chunk {
+			_Block(d, &d.x);
+			d.nx = 0;
+		}
+		p = p[n:];
+	}
+	n := _Block(d, p);
+	p = p[n:];
+	if len(p) > 0 {
+		for i := 0; i < len(p); i++ {
+			d.x[i] = p[i]
+		}
+		d.nx = len(p);
+	}
+	return;
+}
+
+func (d *digest) Sum() []byte {
+	// Padding.  Add a 1 bit and 0 bits until 56 bytes mod 64.
+	len := d.len;
+	var tmp [64]byte;
+	tmp[0] = 0x80;
+	if len%64 < 56 {
+		d.Write(tmp[0 : 56-len%64])
+	} else {
+		d.Write(tmp[0 : 64+56-len%64])
+	}
+
+	// Length in bits.
+	len <<= 3;
+	for i := uint(0); i < 8; i++ {
+		tmp[i] = byte(len >> (8 * i))
+	}
+	d.Write(tmp[0:8]);
+
+	if d.nx != 0 {
+		panicln("oops")
+	}
+
+	p := make([]byte, 16);
+	j := 0;
+	for i := 0; i < 4; i++ {
+		s := d.s[i];
+		p[j] = byte(s);
+		j++;
+		p[j] = byte(s >> 8);
+		j++;
+		p[j] = byte(s >> 16);
+		j++;
+		p[j] = byte(s >> 24);
+		j++;
+	}
+	return p;
+}
diff --git a/src/pkg/crypto/md4/md4_test.go b/src/pkg/crypto/md4/md4_test.go
new file mode 100644
index 000000000..31aa67527
--- /dev/null
+++ b/src/pkg/crypto/md4/md4_test.go
@@ -0,0 +1,66 @@
+// Copyright 2009 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package md4
+
+import (
+	"fmt";
+	"io";
+	"testing";
+)
+
+type md4Test struct {
+	out	string;
+	in	string;
+}
+
+var golden = []md4Test{
+	md4Test{"31d6cfe0d16ae931b73c59d7e0c089c0", ""},
+	md4Test{"bde52cb31de33e46245e05fbdbd6fb24", "a"},
+	md4Test{"ec388dd78999dfc7cf4632465693b6bf", "ab"},
+	md4Test{"a448017aaf21d8525fc10ae87aa6729d", "abc"},
+	md4Test{"41decd8f579255c5200f86a4bb3ba740", "abcd"},
+	md4Test{"9803f4a34e8eb14f96adba49064a0c41", "abcde"},
+	md4Test{"804e7f1c2586e50b49ac65db5b645131", "abcdef"},
+	md4Test{"752f4adfe53d1da0241b5bc216d098fc", "abcdefg"},
+	md4Test{"ad9daf8d49d81988590a6f0e745d15dd", "abcdefgh"},
+	md4Test{"1e4e28b05464316b56402b3815ed2dfd", "abcdefghi"},
+	md4Test{"dc959c6f5d6f9e04e4380777cc964b3d", "abcdefghij"},
+	md4Test{"1b5701e265778898ef7de5623bbe7cc0", "Discard medicine more than two years old."},
+	md4Test{"d7f087e090fe7ad4a01cb59dacc9a572", "He who has a shady past knows that nice guys finish last."},
+	md4Test{"a6f8fd6df617c72837592fc3570595c9", "I wouldn't marry him with a ten foot pole."},
+	md4Test{"c92a84a9526da8abc240c05d6b1a1ce0", "Free! Free!/A trip/to Mars/for 900/empty jars/Burma Shave"},
+	md4Test{"f6013160c4dcb00847069fee3bb09803", "The days of the digital watch are numbered.  -Tom Stoppard"},
+	md4Test{"2c3bb64f50b9107ed57640fe94bec09f", "Nepal premier won't resign."},
+	md4Test{"45b7d8a32c7806f2f7f897332774d6e4", "For every action there is an equal and opposite government program."},
+	md4Test{"b5b4f9026b175c62d7654bdc3a1cd438", "His money is twice tainted: 'taint yours and 'taint mine."},
+	md4Test{"caf44e80f2c20ce19b5ba1cab766e7bd", "There is no reason for any individual to have a computer in their home. -Ken Olsen, 1977"},
+	md4Test{"191fae6707f496aa54a6bce9f2ecf74d", "It's a tiny change to the code and not completely disgusting. - Bob Manchek"},
+	md4Test{"9ddc753e7a4ccee6081cd1b45b23a834", "size:  a.out:  bad magic"},
+	md4Test{"8d050f55b1cadb9323474564be08a521", "The major problem is with sendmail.  -Mark Horton"},
+	md4Test{"ad6e2587f74c3e3cc19146f6127fa2e3", "Give me a rock, paper and scissors and I will move the world.  CCFestoon"},
+	md4Test{"1d616d60a5fabe85589c3f1566ca7fca", "If the enemy is within range, then so are you."},
+	md4Test{"aec3326a4f496a2ced65a1963f84577f", "It's well we cannot hear the screams/That we create in others' dreams."},
+	md4Test{"77b4fd762d6b9245e61c50bf6ebf118b", "You remind me of a TV show, but that's all right: I watch it anyway."},
+	md4Test{"e8f48c726bae5e516f6ddb1a4fe62438", "C is as portable as Stonehedge!!"},
+	md4Test{"a3a84366e7219e887423b01f9be7166e", "Even if I could be Shakespeare, I think I should still choose to be Faraday. - A. Huxley"},
+	md4Test{"a6b7aa35157e984ef5d9b7f32e5fbb52", "The fugacity of a constituent in a mixture of gases at a given temperature is proportional to its mole fraction.  Lewis-Randall Rule"},
+	md4Test{"75661f0545955f8f9abeeb17845f3fd6", "How can you write a big system without C++?  -Paul Glick"},
+}
+
+func TestGolden(t *testing.T) {
+	for i := 0; i < len(golden); i++ {
+		g := golden[i];
+		c := New();
+		for j := 0; j < 2; j++ {
+			io.WriteString(c, g.in);
+			s := fmt.Sprintf("%x", c.Sum());
+			if s != g.out {
+				t.Errorf("md4[%d](%s) = %s want %s", j, g.in, s, g.out);
+				t.FailNow();
+			}
+			c.Reset();
+		}
+	}
+}
diff --git a/src/pkg/crypto/md4/md4block.go b/src/pkg/crypto/md4/md4block.go
new file mode 100644
index 000000000..6f2c2d5a2
--- /dev/null
+++ b/src/pkg/crypto/md4/md4block.go
@@ -0,0 +1,85 @@
+// Copyright 2009 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// MD4 block step.
+// In its own file so that a faster assembly or C version
+// can be substituted easily.
+
+package md4
+
+var shift1 = []uint{3, 7, 11, 19}
+var shift2 = []uint{3, 5, 9, 13}
+var shift3 = []uint{3, 9, 11, 15}
+
+var xIndex2 = []uint{0, 4, 8, 12, 1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15}
+var xIndex3 = []uint{0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}
+
+func _Block(dig *digest, p []byte) int {
+	a := dig.s[0];
+	b := dig.s[1];
+	c := dig.s[2];
+	d := dig.s[3];
+	n := 0;
+	var X [16]uint32;
+	for len(p) >= _Chunk {
+		aa, bb, cc, dd := a, b, c, d;
+
+		for i := 0; i < 16; i++ {
+			j := i * 4;
+			X[i] = uint32(p[j]) | uint32(p[j+1])<<8 | uint32(p[j+2])<<16 | uint32(p[j+3])<<24;
+		}
+
+		// If this needs to be made faster in the future,
+		// the usual trick is to unroll each of these
+		// loops by a factor of 4; that lets you replace
+		// the shift[] lookups with constants and,
+		// with suitable variable renaming in each
+		// unrolled body, delete the a, b, c, d = d, a, b, c
+		// (or you can let the optimizer do the renaming).
+
+		// Round 1.
+		for i := 0; i < 16; i++ {
+			x := i;
+			s := shift1[i%4];
+			f := ((c ^ d) & b) ^ d;
+			a += f + X[x];
+			a = a<<s | a>>(32-s);
+			a, b, c, d = d, a, b, c;
+		}
+
+		// Round 2.
+		for i := 0; i < 16; i++ {
+			x := xIndex2[i];
+			s := shift2[i%4];
+			g := (b & c) | (b & d) | (c & d);
+			a += g + X[x] + 0x5a827999;
+			a = a<<s | a>>(32-s);
+			a, b, c, d = d, a, b, c;
+		}
+
+		// Round 3.
+		for i := 0; i < 16; i++ {
+			x := xIndex3[i];
+			s := shift3[i%4];
+			h := b ^ c ^ d;
+			a += h + X[x] + 0x6ed9eba1;
+			a = a<<s | a>>(32-s);
+			a, b, c, d = d, a, b, c;
+		}
+
+		a += aa;
+		b += bb;
+		c += cc;
+		d += dd;
+
+		p = p[_Chunk:];
+		n += _Chunk;
+	}
+
+	dig.s[0] = a;
+	dig.s[1] = b;
+	dig.s[2] = c;
+	dig.s[3] = d;
+	return n;
+}