The BiBa One Time Signature is used to sign messages, and where we search for hash collisions in signing a message [article][paper]:
BiBa One Time Signature |
BiBa
One area where we can use this collision is within a one-time signature (OTS) and with the method defined as "BiBa" ("Bins and Balls").
Basically with BiBa, Bob creates a number of random values for his private key:
\(Priv = x_1, x_2, … x_n\)
Next he creates his public key from the hashed versions of his private key:
\(Pub = SHA1(x_1), SHA1(x_2) … SHA1(x_n)\)
To create the signature for a message (\(M\)), he finds two values which will create a collision (as we have seen it should be fairly easy to find a collision within a reasonable amount of guesses):
\(H(M || x_i) == H(M || x_j)\)
He would then publish (\(x_i, x_j\)) as the signature of the message.
It would then be too difficult for Eve to find the values of \(x_i\) and \(x_j\) to create a collision, as Bob does not reveal them (they are only defined with their hash signature).
Code
The coding to determine a collision and generate the signature is:
// https://asecuritysite.com/encryption/go_biba package main import ( "hash/fnv" "fmt" "strconv" "math/rand" "os" "time" ) func randInt(min int, max int) int { rand.Seed(time.Now().UTC().UnixNano()) return min + rand.Intn(max-min) } func hash(s string) string { h:=fnv.New32a() h.Write([]byte(s)) return strconv.FormatInt((int64(h.Sum32())),10)[:5] } func main() { M:="abcd" argCount := len(os.Args[1:]) if (argCount>0) {M= string(os.Args[1])} priv:=randInt(1000,10000) tofind:=fmt.Sprintf("%s%s",M, strconv.Itoa(priv)) fmt.Printf("Message is %s. Private key is %d. Finding for [%s] \n",M,priv,tofind) result :=hash(tofind) fmt.Printf("Looking for a collision for %s. Hash: %s\n",fmt.Sprintf("%s%d",M, priv),result) fmt.Printf("\nSearching ....\n\n") for j:=1;j<1000000000;j++ { rtn:=fmt.Sprintf("%s%d",M, j) test := hash(rtn) if (result==test && j!=priv) { fmt.Printf("Found it at %d. String is %s. Hash: %s\n" , j,rtn,test) fmt.Printf("BiBa Signature [%d,%d]\n" ,priv,j) break } } }
A sample run for a message of "abcde" is:
Message is abcde. Private key is 3227. Finding for [abcde3227] Looking for a collision for abcde3227. Hash: 35690 Searching .... Found it at 44304. String is abcde44304. Hash: 35690 BiBa Signature [3227, 44304]
Presentation
The presentation is here [slides]: