Chameleon hash
[Hashing Home][Home]
The chameleon is an amazing creature that can adapt to its environment. So what’s that got to do with cybersecurity? Well, we can generate a Chameleon hash, and where we have a normal hash value which is resistant to collisions, but with a known secret we can easily create a collision. The concept was first defined by Krawcyk and Rabin in [2].
|
Outline
With a chameleon hash, we might have an image which generates a given hash value, and where it would be extremely difficult to generate the same hash for a different image. This is known as collision resistance, and is a highly desirable attribute of a hashing method. But, let’s say that we have an update to the image, but where we have already defined the hash of the image. For this, we can create a chameleon hash and where we apply a secret key to the hash process and then create the same hash. These keys can be defined as trapdoor keys. Unforunately, in 2004, Ateniese and De Medeiros found a weakness in these hashes which could expose the secret key [5], but newer papers have created methods which overcome the key exposure risk [3].
A core application of chameleon hashes relates to redactable blockchains, and where it is possible to delete transactions in a block, or even remove a whole block [1]. The approach could allow a blockchain infrastructure to comply with GDPR, especially in the implementation of the right-to-be-forgotten.
Chameleon methods
Overall, we have a pair of hashing/trapdoor keys, and the owner of the keys can easily find a collision within a given domain, but without the keys, the hash will be collision resistant. One of the best-defined methods was created by Ateniese and Medeiros [3]. The paper outlines two methods. One method is more traditional and based on Groth–Sahai proofs and Cramer–Shoup, and the second uses Groth and Maller SNARKs (zk-Snarks). These methods guarantee that no information about the secret key is ever leaked from the hashes. The zk-Snarks derived method uses bilinear pairings.
Coding
We can use the code [here][4]:
package main import ( "crypto/rand" "crypto/sha256" "fmt" "math/big" "os" ) func main() { var p, q, g, hk, tk, hash1, hash2, r1, s1, r2, s2, msg1, msg2 []byte keygen(128, &p, &q, &g, &hk, &tk) argCount := len(os.Args[1:]) m1 := "Test" m2 := "Not" if argCount > 0 { m1 = os.Args[1] } if argCount > 1 { m2 = os.Args[2] } msg1 = []byte(m1) msg2 = []byte(m2) r1 = randgen(&q) s1 = randgen(&q) fmt.Printf("Hash Parameters:"+ "\np: %s1"+ "\nq: %s1"+ "\ng: %s1"+ "\nhk: %s1"+ "\ntk: %s1"+ "\nDONE!", p, q, g, hk, tk) chameleonHash(&hk, &p, &q, &g, &msg1, &r1, &s1, &hash1) fmt.Printf("\n\nROUND 1:"+ "\nmsg1: %s"+ "\nr1: %s1"+ "\ns1: %s1"+ "\nhash1: %x\n", msg1, r1, s1, hash1) fmt.Printf("\n\nGenerating a collision...\n\n") // Generating a collision generateCollision(&hk, &tk, &p, &q, &g, &msg1, &msg2, &r1, &s1, &r2, &s2) chameleonHash(&hk, &p, &q, &g, &msg2, &r2, &s2, &hash2) fmt.Printf("\nROUND 2:"+ "\nmsg2: %s"+ "\nr2: %s"+ "\ns2: %s"+ "\nhash2: %x\n", msg2, r2, s2, hash2) } // Returns a random hex number within the bounds of 0 and upperBoundHex. func randgen(upperBoundHex *[]byte) []byte { upperBoundBig := new(big.Int) upperBoundBig, success := upperBoundBig.SetString(string(*upperBoundHex), 16) if success != true { fmt.Printf("Conversion from hex: %s to bigInt failed.", upperBoundHex) } randomBig, err := rand.Int(rand.Reader, upperBoundBig) if err != nil { fmt.Printf("Generation of random bigInt in bounds [0...%v] failed.", upperBoundBig) } return []byte(fmt.Sprintf("%x", randomBig)) } func keygen(bits int, p *[]byte, q *[]byte, g *[]byte, hk *[]byte, tk *[]byte) { gBig := new(big.Int) qBig := new(big.Int) hkBig := new(big.Int) tkBig := new(big.Int) oneBig := new(big.Int) twoBig := new(big.Int) oneBig.SetInt64(1) // oneBig = 1 twoBig.SetInt64(2) // twoBig = 2 pBig, err := rand.Prime(rand.Reader, bits) // pBig is a random prime of length bits if err != nil { fmt.Printf("Generation of random prime number failed.") } qBig.Sub(pBig, oneBig) // qBig = pBig - 1 qBig.Div(qBig, twoBig) // qBig = (pBig - 1) / 2 gBig, err = rand.Int(rand.Reader, pBig) if err != nil { fmt.Printf("Generation of random bigInt in bounds [0...%v] failed.", pBig) } gBig.Exp(gBig, twoBig, pBig) // gBig = gBig ^ 2 % pBig // Choosing hk and tk tkBig, err = rand.Int(rand.Reader, qBig) if err != nil { fmt.Printf("Generation of random bigInt in bounds [0...%v] failed.", qBig) } hkBig.Exp(gBig, tkBig, pBig) // hkBig = gBig ^ tkBig % pBig *p = []byte(fmt.Sprintf("%x", pBig)) *q = []byte(fmt.Sprintf("%x", qBig)) *g = []byte(fmt.Sprintf("%x", gBig)) *hk = []byte(fmt.Sprintf("%x", hkBig)) *tk = []byte(fmt.Sprintf("%x", tkBig)) } func chameleonHash( hk *[]byte, p *[]byte, q *[]byte, g *[]byte, message *[]byte, r *[]byte, s *[]byte, hashOut *[]byte, ) { hkeBig := new(big.Int) gsBig := new(big.Int) tmpBig := new(big.Int) eBig := new(big.Int) pBig := new(big.Int) qBig := new(big.Int) gBig := new(big.Int) rBig := new(big.Int) sBig := new(big.Int) hkBig := new(big.Int) hBig := new(big.Int) // Converting from hex to bigInt pBig.SetString(string(*p), 16) qBig.SetString(string(*q), 16) gBig.SetString(string(*g), 16) hkBig.SetString(string(*hk), 16) rBig.SetString(string(*r), 16) sBig.SetString(string(*s), 16) // Generate the hashOut with message || rBig hash := sha256.New() hash.Write([]byte(*message)) hash.Write([]byte(fmt.Sprintf("%x", rBig))) eBig.SetBytes(hash.Sum(nil)) hkeBig.Exp(hkBig, eBig, pBig) gsBig.Exp(gBig, sBig, pBig) tmpBig.Mul(hkeBig, gsBig) tmpBig.Mod(tmpBig, pBig) hBig.Sub(rBig, tmpBig) hBig.Mod(hBig, qBig) *hashOut = hBig.Bytes() // Return hBig in big endian encoding as string } func generateCollision( hk *[]byte, tk *[]byte, p *[]byte, q *[]byte, g *[]byte, msg1 *[]byte, msg2 *[]byte, r1 *[]byte, s1 *[]byte, r2 *[]byte, s2 *[]byte, ) { hkBig := new(big.Int) tkBig := new(big.Int) pBig := new(big.Int) qBig := new(big.Int) gBig := new(big.Int) r1Big := new(big.Int) s1Big := new(big.Int) kBig := new(big.Int) hBig := new(big.Int) eBig := new(big.Int) tmpBig := new(big.Int) r2Big := new(big.Int) s2Big := new(big.Int) pBig.SetString(string(*p), 16) qBig.SetString(string(*q), 16) gBig.SetString(string(*g), 16) r1Big.SetString(string(*r1), 16) s1Big.SetString(string(*s1), 16) hkBig.SetString(string(*hk), 16) tkBig.SetString(string(*tk), 16) // Generate random k kBig, err := rand.Int(rand.Reader, qBig) if err != nil { fmt.Printf("Generation of random bigInt in bounds [0...%v] failed.", qBig) } // Get chameleon hash of (msg1, r1, s1) var hash []byte chameleonHash(hk, p, q, g, msg1, r1, s1, &hash) hBig.SetBytes(hash) // Convert the big endian encoded hash into bigInt. // Compute the new r1 tmpBig.Exp(gBig, kBig, pBig) r2Big.Add(hBig, tmpBig) r2Big.Mod(r2Big, qBig) // Compute e' newHash := sha256.New() newHash.Write([]byte(*msg2)) newHash.Write([]byte(fmt.Sprintf("%x", r2Big))) eBig.SetBytes(newHash.Sum(nil)) // Compute s2 tmpBig.Mul(eBig, tkBig) tmpBig.Mod(tmpBig, qBig) s2Big.Sub(kBig, tmpBig) s2Big.Mod(s2Big, qBig) *r2 = []byte(fmt.Sprintf("%x", r2Big)) *s2 = []byte(fmt.Sprintf("%x", s2Big)) }
We can see that we initially create a keypair, and which gives us the parameters of p, q, g, hk, and tk:
keygen(128, &p, &q, &g, &hk, &tk)
From these and with two values random values of r1 (generated from between 0 and p-1) and s1 (generated from between 0 and q-1), we can create the hash with:
chameleonHash(&hk, &p, &q, &g, &msg1, &r1, &s1, &hash1)
We can generate a collision using our secrets, and then the same hash:
generateCollision(&hk, &tk, &p, &q, &g, &msg1, &msg2, &r1, &s1, &r2, &s2) chameleonHash(&hk, &p, &q, &g, &msg2, &r2, &s2, &hash2)
And a sample run:
CHAMELEON HASH PARAMETERS: p: ecbc698905de96022c1bc254191681d31 q: 765e34c482ef4b01160de12a0c8b40e91 g: 9092a7ee21c34cb57e398739fcf8d2371 hk: 75e7fde180498d167b5349341a3bb01b1 tk: 1911c632c333b481fe6f74c48bd3256d1 DONE! ROUND 1: msg1: Hello r1: 24ab7e5e3a98a102669e58fd03f6909b1 s1: 2b2db81b4b5ae09b6a6a28d8cb93ea2d1 hash1: 72c80e54c3fcbd3530e251c5887f6e21 Generating a collision... ROUND 2: msg2: Goodbye r2: 576e7f0d06127328ab872eaf3efe4c42 s2: 3c1d5ba4249387824937adc0048013d6 hash2: 72c80e54c3fcbd3530e251c5887f6e21
We can see here that our message of “Hello” creates a hash of “72c80e54c3fcbd3530e251c5887f6e21”, and where we can also create the same hash for “Goodbye”. This uses a key pair that has been created so that the collision can occur.
Conclusions
With hashing methods, a collision is often a bad thing and leads us to match different content to the same hash. This is the case for the MD5 hash, where it is often fairly easy to produce a collision, even for things like documents and executable programs. SHA-256, though, is much more robust, and it is almost impossible at the current time to produce a collision. But, sometimes we might have a trusted transaction that we want to delete. For this, the chameleon hash could allow us to produce the same hash for it, and where we can cancel the transaction.
References
[1] Ateniese, G., Magri, B., Venturi, D., & Andrade, E. (2017, April). Redactable blockchain–or–rewriting history in bitcoin and friends. In 2017 IEEE European symposium on security and privacy (EuroS&P) (pp. 111–126). IEEE.
[2] Krawczyk, H., & Rabin, T. (1997). Chameleon hashing and signatures.
[3] Khalili, M., Dakhilalian, M., & Susilo, W. (2020). Efficient chameleon hash functions in the enhanced collision resistant model. Information Sciences, 510, 155–164.
[4] Julius Willems, Chameleon hash, https://github.com/julwil/chameleon_hash.
[5] Ateniese, G., & Medeiros, B. D. (2004, September). On the key exposure problem in chameleon hashes. In International Conference on Security in Communication Networks (pp. 165–179). Springer, Berlin, Heidelberg.