hash collision

collide.go

package main

import (
	"crypto/sha256"
	"fmt"
	"math/rand"
	"os"
	"time"
)

var s = sha256.New().Size() - 7

func sha(m [8]byte) []byte {
	h := sha256.New()
	h.Write(m[:])
	return h.Sum(nil)
}

func shaTrunc(m int64) (ma [8]byte, r [7]byte) {
	ma[0] = byte(m >> 56)
	ma[1] = byte(m >> 48)
	ma[2] = byte(m >> 40)
	ma[3] = byte(m >> 32)
	ma[4] = byte(m >> 24)
	ma[5] = byte(m >> 16)
	ma[6] = byte(m >> 8)
	ma[7] = byte(m)
	h := sha256.New()
	h.Write(ma[:])
	copy(r[:], h.Sum(nil)[s:])
	r[0] &= 0x3
	return
}

func main() {
	rand.Seed(time.Now().Unix())
	for j := 0; j < 10; j++ {
		fmt.Printf("Run %d:\n", j)
		t := make(map[[7]byte][8]byte, 1<<25)
		for i := 0; i < 1<<25; i++ {
			m := rand.Int63()
			bm, s := shaTrunc(m)
			if i%(1<<20) == 0 {
				fmt.Printf(" %0x...\n", i)
			}
			if h, ok := t[s]; ok && h != bm {
				fmt.Printf("Found collision: %x == %x, %x != %x\n%x\n%x\n", s, s, h, bm, sha(h), sha(bm))
				os.Exit(0)
			} else {
				t[s] = bm
			}
		}
	}
	fmt.Println("Failed to find collision.")
}