crypto/blowfish: exposing the blowfish key schedule

Mostly useful for the coming crypto/bcrypt package

R=bradfitz, agl, rsc, agl
CC=golang-dev
https://golang.org/cl/5013043

3 files changed, 141 insertions, 8 deletions

diff --git a/src/pkg/crypto/blowfish/block.go b/src/pkg/crypto/blowfish/block.go
index 7fbe7eefb0..326292dfc3 100644
--- a/src/pkg/crypto/blowfish/block.go
+++ b/src/pkg/crypto/blowfish/block.go
@@ -4,13 +4,12 @@
 
 package blowfish
 
-func expandKey(key []byte, c *Cipher) {
-	copy(c.p[0:], p[0:])
-	copy(c.s0[0:], s0[0:])
-	copy(c.s1[0:], s1[0:])
-	copy(c.s2[0:], s2[0:])
-	copy(c.s3[0:], s3[0:])
-
+// ExpandKey performs a key expansion on the given *Cipher. Specifically, it
+// performs the Blowfish algorithm's key schedule which sets up the *Cipher's
+// pi and substitution tables for calls to Encrypt. This is used, primarily,
+// by the bcrypt package to reuse the Blowfish key schedule during its
+// set up. It's unlikely that you need to use this directly.
+func ExpandKey(key []byte, c *Cipher) {
 	j := 0
 	for i := 0; i < 18; i++ {
 		var d uint32
@@ -48,6 +47,98 @@ func expandKey(key []byte, c *Cipher) {
 	}
 }
 
+// This is similar to ExpandKey, but folds the salt during the key
+// schedule. While ExpandKey is essentially expandKeyWithSalt with an all-zero
+// salt passed in, reusing ExpandKey turns out to be a place of inefficiency
+// and specializing it here is useful.
+func expandKeyWithSalt(key []byte, salt []byte, c *Cipher) {
+	j := 0
+	expandedKey := make([]uint32, 18)
+	for i := 0; i < 18; i++ {
+		var d uint32
+		for k := 0; k < 4; k++ {
+			d = d<<8 | uint32(key[j])&0x000000FF
+			j++
+			if j >= len(key) {
+				j = 0
+			}
+		}
+		expandedKey[i] = d
+		c.p[i] ^= d
+	}
+
+	j = 0
+	expandedSalt := make([]uint32, 18)
+	for i := 0; i < 18; i++ {
+		var d uint32
+		for k := 0; k < 4; k++ {
+			d = d<<8 | uint32(salt[j])&0x000000FF
+			j++
+			if j >= len(salt) {
+				j = 0
+			}
+		}
+		expandedSalt[i] = d
+	}
+
+	var l, r uint32
+	for i := 0; i < 18; i += 2 {
+		l ^= expandedSalt[i&2]
+		r ^= expandedSalt[(i&2)+1]
+		l, r = encryptBlock(l, r, c)
+		c.p[i], c.p[i+1] = l, r
+	}
+
+	for i := 0; i < 256; i += 4 {
+		l ^= expandedSalt[2]
+		r ^= expandedSalt[3]
+		l, r = encryptBlock(l, r, c)
+		c.s0[i], c.s0[i+1] = l, r
+
+		l ^= expandedSalt[0]
+		r ^= expandedSalt[1]
+		l, r = encryptBlock(l, r, c)
+		c.s0[i+2], c.s0[i+3] = l, r
+
+	}
+
+	for i := 0; i < 256; i += 4 {
+		l ^= expandedSalt[2]
+		r ^= expandedSalt[3]
+		l, r = encryptBlock(l, r, c)
+		c.s1[i], c.s1[i+1] = l, r
+
+		l ^= expandedSalt[0]
+		r ^= expandedSalt[1]
+		l, r = encryptBlock(l, r, c)
+		c.s1[i+2], c.s1[i+3] = l, r
+	}
+
+	for i := 0; i < 256; i += 4 {
+		l ^= expandedSalt[2]
+		r ^= expandedSalt[3]
+		l, r = encryptBlock(l, r, c)
+		c.s2[i], c.s2[i+1] = l, r
+
+		l ^= expandedSalt[0]
+		r ^= expandedSalt[1]
+		l, r = encryptBlock(l, r, c)
+		c.s2[i+2], c.s2[i+3] = l, r
+	}
+
+	for i := 0; i < 256; i += 4 {
+		l ^= expandedSalt[2]
+		r ^= expandedSalt[3]
+		l, r = encryptBlock(l, r, c)
+		c.s3[i], c.s3[i+1] = l, r
+
+		l ^= expandedSalt[0]
+		r ^= expandedSalt[1]
+		l, r = encryptBlock(l, r, c)
+		c.s3[i+2], c.s3[i+3] = l, r
+	}
+}
+
 func encryptBlock(l, r uint32, c *Cipher) (uint32, uint32) {
 	xl, xr := l, r
 	xl ^= c.p[0]
diff --git a/src/pkg/crypto/blowfish/blowfish_test.go b/src/pkg/crypto/blowfish/blowfish_test.go
index 3a7ab6c2a8..1038d2e39e 100644
--- a/src/pkg/crypto/blowfish/blowfish_test.go
+++ b/src/pkg/crypto/blowfish/blowfish_test.go
@@ -190,3 +190,21 @@ func TestCipherDecrypt(t *testing.T) {
 		}
 	}
 }
+
+func TestSaltedCipherKeyLength(t *testing.T) {
+	var key []byte
+	for i := 0; i < 4; i++ {
+		_, err := NewSaltedCipher(key, []byte{'a'})
+		if err != KeySizeError(i) {
+			t.Errorf("NewSaltedCipher with short key, gave error %#v, expected %#v", err, KeySizeError(i))
+		}
+		key = append(key, 'a')
+	}
+
+	// A 57-byte key. One over the typical blowfish restriction.
+	key = []byte("012345678901234567890123456789012345678901234567890123456")
+	_, err := NewSaltedCipher(key, []byte{'a'})
+	if err != nil {
+		t.Errorf("NewSaltedCipher with long key, gave error %#v", err)
+	}
+}
diff --git a/src/pkg/crypto/blowfish/cipher.go b/src/pkg/crypto/blowfish/cipher.go
index 6c37dfe940..3439825e89 100644
--- a/src/pkg/crypto/blowfish/cipher.go
+++ b/src/pkg/crypto/blowfish/cipher.go
@@ -31,12 +31,28 @@ func (k KeySizeError) String() string {
 // NewCipher creates and returns a Cipher.
 // The key argument should be the Blowfish key, 4 to 56 bytes.
 func NewCipher(key []byte) (*Cipher, os.Error) {
+	var result Cipher
 	k := len(key)
 	if k < 4 || k > 56 {
 		return nil, KeySizeError(k)
 	}
+	initCipher(key, &result)
+	ExpandKey(key, &result)
+	return &result, nil
+}
+
+// NewSaltedCipher creates a returns a Cipher that folds a salt into its key
+// schedule. For most purposes, NewCipher, instead of NewSaltedCipher, is
+// sufficient and desirable. For bcrypt compatiblity, the key can be over 56
+// bytes.
+func NewSaltedCipher(key, salt []byte) (*Cipher, os.Error) {
 	var result Cipher
-	expandKey(key, &result)
+	k := len(key)
+	if k < 4 {
+		return nil, KeySizeError(k)
+	}
+	initCipher(key, &result)
+	expandKeyWithSalt(key, salt, &result)
 	return &result, nil
 }
 
@@ -77,3 +93,11 @@ func (c *Cipher) Reset() {
 	zero(c.s2[0:])
 	zero(c.s3[0:])
 }
+
+func initCipher(key []byte, c *Cipher) {
+	copy(c.p[0:], p[0:])
+	copy(c.s0[0:], s0[0:])
+	copy(c.s1[0:], s1[0:])
+	copy(c.s2[0:], s2[0:])
+	copy(c.s3[0:], s3[0:])
+}