BCrypt does not play nice with null bytes

bcrypt_null_test.go

package main

import (
	"bytes"
	"crypto/sha256"
	"fmt"

	"golang.org/x/crypto/bcrypt"
)

/*
	$ go build && ./bcrypt-null
	Comparing hash([0]) == hash([0]) 1
		SHA256: Equal!
		BCrypt: Equal!
	Comparing hash([65 66 67]) == hash([65 66 67]) 3
		SHA256: Equal!
		BCrypt: Equal!
	Comparing hash([0]) == hash([0 0 0]) 1
		SHA256: Not equal
		BCrypt: Equal!
	Comparing hash([0 1 1]) == hash([0 1 1 0 0 1 1]) 3
		SHA256: Not equal
		BCrypt: Equal!
	Comparing hash([0 1 1]) == hash([0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1]) 3
		SHA256: Not equal
		BCrypt: Equal!
	Comparing hash([1 2 3]) == hash([1 2 3 0 1 2 3 0 1 2 3]) 3
		SHA256: Not equal
		BCrypt: Equal!
	Comparing hash([65 66 67]) == hash([65 66 67 0 65 66 67 0 65 66 67]) 3
		SHA256: Not equal
		BCrypt: Equal!
	Comparing hash([116 101 115 116 0 116 101 115 116 0 116 101 115 116 0 116 101 115 116 0 116 101 115 116 0 116 101 115 116 0 116 101 115 116 0 116 101 115 116 0 116 101 115 116 0 116 101 115 116 0 116 101 115 116 0 116 101 115 116 0 116 101 115 116 0 116 101 115 116 0 116 101]) == hash([116 101 115 116]) 72
		SHA256: Not equal
		BCrypt: Equal!
	Comparing hash([116 101 115 116 0 116 101 115 116 0 116 101 115 116 0 116 101 115 116 0 116 101 115 116 0 116 101 115 116 0 116 101 115 116 0 116 101 115 116 0 116 101 115 116 0 116 101 115 116 0 116 101 115 116 0 116 101 115 116 0 116 101 115 116 0 116 101 115 116 0 116]) == hash([116 101 115 116]) 71
		SHA256: Not equal
		BCrypt: Not equal
	Comparing hash([116 101 115 116 0 116 101 115 116 0 116 101 115 116 0 116 101 115 116 0 116 101 115 116 0 116 101 115 116 0 116 101 115 116 0 116 101 115 116 0 116 101 115 116 0 116 101 115 116 0 116 101 115 116 0 116 101 115 116 0 116 101 115 116 0 116 101 115 116 0 116 101 120 120 120 120 120]) == hash([116 101 115 116]) 77
		SHA256: Not equal
		BCrypt: Equal!
	Comparing hash([97 0 98 99]) == hash([97 0 99 100]) 4
		SHA256: Not equal
		BCrypt: Not equal
	Found it! (bcrypt) [0 0] == [0]
	Found it! (bcrypt) [0 0 0] == [0]
	Found it! (bcrypt) [0 0 0] == [0 0]
	Found it! (bcrypt) [1 0 1] == [1]
	Found it! (bcrypt) [2 0 2] == [2]
*/

var verbose = false //true
var cost = bcrypt.MinCost

func compareHashOfPasswordsBcrypt(pass1, pass2 []byte) bool {
	if verbose {
		fmt.Printf("Comparing Bcrypt(%v, %d)==Bcrypt(%v, %d)\n",
			pass1, bcrypt.DefaultCost, pass2, bcrypt.DefaultCost)
	}

	hash, err := bcrypt.GenerateFromPassword(pass1, cost)
	if err != nil {
		panic(err)
	}

	err = bcrypt.CompareHashAndPassword(hash, pass2)
	hashesEqual := err == nil

	if verbose {
		if hashesEqual {
			fmt.Println("Equal")
		} else {
			fmt.Println("Not equal")
		}
	}

	return hashesEqual
}

func compareHashOfPasswordsSha256(pass1, pass2 []byte) bool {
	if verbose {
		fmt.Printf("Comparing sha256(%v)==sha256(%v)\n", pass1, pass2)
	}

	h1 := sha256.New()
	h1.Write(pass1)
	hash1 := h1.Sum(nil)

	h2 := sha256.New()
	h2.Write(pass2)
	hash2 := h2.Sum(nil)

	hashesEqual := bytes.Compare(hash1, hash2) == 0

	if verbose {
		if hashesEqual {
			fmt.Println("Equal")
		} else {
			fmt.Println("Not equal")
		}
	}

	return hashesEqual
}

func boolToEqual(b bool) string {
	if b {
		return "Equal!"
	}
	return "Not equal"
}

func testStrings() {
	// Pairs of interesting combinations
	pass := [][][]byte{
		{{0}, {0}},
		{{65, 66, 67}, {65, 66, 67}},
		{{0}, {0, 0, 0}},
		{{0, 1, 1}, {0, 1, 1, 0, 0, 1, 1}},
		{{0, 1, 1}, {0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1}},
		{{1, 2, 3}, {1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3}},
		{{65, 66, 67}, {65, 66, 67, 0, 65, 66, 67, 0, 65, 66, 67}},
		{[]byte("test\x00test\x00test\x00test\x00test\x00test\x00test\x00test\x00test\x00test\x00test\x00test\x00test\x00test\x00te"), []byte("test")},      // 72 bytes long
		{[]byte("test\x00test\x00test\x00test\x00test\x00test\x00test\x00test\x00test\x00test\x00test\x00test\x00test\x00test\x00t"), []byte("test")},       // 71 bytes long, not equal
		{[]byte("test\x00test\x00test\x00test\x00test\x00test\x00test\x00test\x00test\x00test\x00test\x00test\x00test\x00test\x00texxxxx"), []byte("test")}, // >72 bytes is truncated
		{[]byte("a\x00bc"), []byte("a\x00cd")},                                                                                                              // Not equal in golang!
	}

	for _, p := range pass {
		fmt.Printf("Comparing hash(%v) == hash(%v) %d\n", p[0], p[1], len(p[0]))
		fmt.Printf("\tSHA256: %s\n", boolToEqual(compareHashOfPasswordsSha256(p[0], p[1])))
		fmt.Printf("\tBCrypt: %s\n", boolToEqual(compareHashOfPasswordsBcrypt(p[0], p[1])))
	}
}

func nextPerm(val []byte, min, max byte) bool {
	for ii := 0; ii < len(val); ii++ {
		//fmt.Println(ii, val[ii])
		if val[ii] < max {
			val[ii]++
			return true
		}
		if val[ii] == max {
			val[ii] = min
			if ii == len(val)-1 {
				return false
			}
		}
	}
	return false
}

func bruteforce() {
	// Ideally we want to test [0..255] but that will consume a lot of cpu cycles
	maxx := byte(2)
	// Infinite loop, find all combinations
	for k := 0; k >= 0; k++ {
		pass1 := make([]byte, k+1)
		for pass1ok := true; pass1ok; {
			// pass2 is an array of length kk, that is then permutated
			for kk := 0; kk <= k; kk++ {
				pass2 := make([]byte, kk+1)
				for pass2ok := true; pass2ok; {
					// fmt.Println(pass1, pass2)
					if bytes.Compare(pass1, pass2) == 0 {
						// Boring! Passwords are actually equal
						goto skip
					}
					if compareHashOfPasswordsBcrypt(pass1, pass2) {
						fmt.Println("Found it! (bcrypt)", pass1, "==", pass2)
					}
					if compareHashOfPasswordsSha256(pass1, pass2) {
						fmt.Println("Found it! (sha256)", pass1, "==", pass2)
					}
				skip:
					if !nextPerm(pass2, 0, maxx) {
						break
					}
				}
			}
			if !nextPerm(pass1, 0, maxx) {
				break
			}
		}
		pass1 = append(pass1, byte(0))
	}
}

func main() {
	testStrings()
	bruteforce()
}

A clear pattern is visible.
bcrypt("ABC") == bcrypt("ABC\x00" * n + "ABC")
bcrypt(data) == bcrypt((data + "\x00") * n + data)

The last null byte should be omitted because the golang implementation adds it: https://github.com/golang/crypto/blob/master/bcrypt/bcrypt.go#L214

The behavior is not identical with the PHP implementation as seen here: http://blog.ircmaxell.com/2015/03/security-issue-combining-bcrypt-with.html

The PHP implementation seems to ignore everything after a null byte, e.g. bcrypt("a\x00bc") == bcrypt("a\x00cd"), which is not the case in the golang implementation.

See how PHP handles null bytes here: https://3v4l.org/hNZ7D