Photo by Anand Rathod on Unsplash

Chameleon Hashes

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 [here][2]:

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 where we apply a secret key to the hash process and then create the same hash. These keys can be defined as trapdoor keys.

Unfortunately, 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 Khalili et al [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 [here].

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)
}

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 [here]:

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.