Find hash collision for limited data/hash size.

main.go

// Result, using input string from 0 to 999999.
// It finds some conflict if the hash size is 4 bytes,
// no conflict found if hash size is 6 bytes.
package main

import (
	"crypto/hmac"
	"crypto/sha256"
	"encoding/hex"
	"fmt"

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

func main() {
	collision := make(map[string]int, 1000000)

	input := make(chan int)
	output := make(chan struct {
		dk string
		i  int
	})
	done := make(chan bool)

	for r := 0; r < 3; r++ {
		go func() {
			mac := hmac.New(sha256.New, []byte("hello"))

			for i := range input {
				var dk []byte
				if false {
					mac.Reset()
					mac.Write([]byte(fmt.Sprintf("%06d", i)))
					for j := 1; j < 100; j++ {
						state := mac.Sum(nil)
						mac.Reset()
						mac.Write(state)
					}
					dk = mac.Sum(nil)[:6]
				}

				if true {
					dk_, err := scrypt.Key([]byte(fmt.Sprintf("%06d", i)), []byte("hello"), 16, 8, 1, 6)
					if err != nil {
						panic(err)
					}
					dk = dk_
				}

				output <- struct {
					dk string
					i  int
				}{hex.EncodeToString(dk), i}
			}

			done <- true
		}()
	}

	done2 := make(chan bool)
	go func() {
		for dk := range output {
			//fmt.Println(dk.dk, dk.i)
			if ii, ok := collision[dk.dk]; ok {
				fmt.Printf("Collision found for %06d and %06d\n", dk.i, ii)
			} else {
				collision[dk.dk] = dk.i
			}
		}
		done2 <- true
	}()

	for i := 0; i <= 999999; i++ {
		input <- i
		if i%1000 == 0 {
			fmt.Println(i)
		}
	}
	close(input)

	<-done
	<-done
	<-done

	close(output)

	<-done2
}