Historical Context of Iota’s Hash Functions
Once upon a time, researchers discovered that the hash function used within the Iota cryptocurrency (Curl-P), was vulnerable to practical collisions. When pressed about this, the Iota Foundation said the following:
https://twitter.com/durumcrustulum/status/1083859956841889792
In response to this research, the Iota developers threatened to sue the researchers.
https://twitter.com/matthew_d_green/status/965731647579664385?lang=en
Iota replaced Curl-P-27 with a hash function based on Keccak-384 they call Kerl. Keccak, you may recall, is a sponge function that went on to become SHA-3.
At its face, this sounds like a conservative choice in cryptography protocol design: Migrate from a backdoored hash function to one trusted and respected by cryptographers around the world.
https://twitter.com/cybergibbons/status/1283065819300331520
Iota even offered a bug bounty for attacks against reduced round variants:
https://twitter.com/durumcrustulum/status/1083860482866343936
Kerl isn’t Keccak-384 though. It’s Keccak-384 with a bit of an odd twist: They encode the input bytes into ternary ({0, 1} -> {-1, 0, 1}) before hashing. Apparently this weird obsession with ternary encoding is part of Iota’s schtick?
Practical Kerl Collisions
As a consequence of their weird ternary obsession, the following inputs all produce the same Kerl hash:
- GYOMKVTSNHVJNCNFBBAH9AAMXLPLLLROQY99QN9DLSJUHDPBLCFFAIQXZA9BKMBJCYSFHFPXAHDWZFEIZ
- GYOMKVTSNHVJNCNFBBAH9AAMXLPLLLROQY99QN9DLSJUHDPBLCFFAIQXZA9BKMBJCYSFHFPXAHDWZFEIH
- GYOMKVTSNHVJNCNFBBAH9AAMXLPLLLROQY99QN9DLSJUHDPBLCFFAIQXZA9BKMBJCYSFHFPXAHDWZFEIQ
This is a consequence of always zeroing out the last “trit” before passing the input to Keccak-384.
Since this zeroing was an explicit design choice of Iota’s, I decided to helpfully submit a pull request adding these inputs as test vectors to their JavaScript implementation.
Why It Matters
These are the facts:
- Kerl is intended to replace Curl-P-27 within the Iota cryptocurrency.
- The Iota Foundation previously admitted that Curl-P-27 was a “copy-protection backdoor”.
- The ternary encoding in Kerl allows three different inputs to produce the same hash output (which is not true of Keccak-384).
Given the past behavior of the Iota developers, there are three possible explanations for this:
- It’s a bugdoor (a backdoor enabled by a bug) intended to be exploited by the Coordinator–possibly as another copy-protection backdoor in the spirit of Curl-P-27.
- They made a critical design mistake in Kerl, which may or may not be exploitable in one or more of the places they use Kerl.
- Their alleged justification for zeroing out the last trit is sound, and there’s no way to exploit this collision vulnerability within Iota.
The last explanation is the one that Iota fanboys will probably cling to, but let me be clear: Even if this isn’t exploitable within Iota, it’s still a huge fuck-up in the design of Kerl.
I’ve lost count of the number of projects I’ve encountered that used secp256k1 as their elliptic curve choice simply because it was also the curve Bitcoin used. These are protocols doing ECDSA for JSON Web Tokens, or ECDH for use in ECIES schemes.
The probability of someone eventually using Kerl outside of Iota is 1, and they will be vulnerable to collisions because of that choice.
Takeaways
Iota is a cryptocurrency project that threatens security researchers, intentionally backdoored the cryptographic hash function in their original design (for “copy-protection”) and admitted to it, and designed a replacement cryptographic hash function (Kerl) that is vulnerable to trivial collision attacks (but the underlying hash function, Keccak-384, is not).
I don’t need to connect the lines on this one, do I?
Since this attack also works on “reduced round” variants of Kerl, I guess I win their bug bounty too!
If the Iota developers are reading this, please remit payment for your promised bounty to the following ZEC address: zs1lwghzjazt4h53gwnl7f24tdq99kw7eh9hgh3qumdvcndszl7ml4xmsudcmm60dut2cfesxmlcec
That being said, I never got an answer to my question, “Should I report the security reduction in bits or trits?” I’m feeling generous though. Given the cost of a collision is basically 1 trit, this is a 242-trit security reduction against collision attacks in Kerl.
https://soatok.blog/2020/07/15/kerlissions-trivial-collisions-in-iotas-hash-function-kerl/
#collision #cryptanalysis #Cryptocurrency #cryptographicHashFunction #hashFunction #iota #kerl #kerlission
Historical Context of Iota’s Hash Functions
Once upon a time, researchers discovered that the hash function used within the Iota cryptocurrency (Curl-P), was vulnerable to practical collisions. When pressed about this, the Iota Foundation said the following:https://twitter.com/durumcrustulum/status/1083859956841889792
In response to this research, the Iota developers threatened to sue the researchers.
https://twitter.com/matthew_d_green/status/965731647579664385?lang=en
Iota replaced Curl-P-27 with a hash function based on Keccak-384 they call Kerl. Keccak, you may recall, is a sponge function that went on to become SHA-3.
At its face, this sounds like a conservative choice in cryptography protocol design: Migrate from a backdoored hash function to one trusted and respected by cryptographers around the world.
https://twitter.com/cybergibbons/status/1283065819300331520
Iota even offered a bug bounty for attacks against reduced round variants:
https://twitter.com/durumcrustulum/status/1083860482866343936
Kerl isn’t Keccak-384 though. It’s Keccak-384 with a bit of an odd twist: They encode the input bytes into ternary ({0, 1} -> {-1, 0, 1}) before hashing. Apparently this weird obsession with ternary encoding is part of Iota’s schtick?
Practical Kerl Collisions
As a consequence of their weird ternary obsession, the following inputs all produce the same Kerl hash:
- GYOMKVTSNHVJNCNFBBAH9AAMXLPLLLROQY99QN9DLSJUHDPBLCFFAIQXZA9BKMBJCYSFHFPXAHDWZFEIZ
- GYOMKVTSNHVJNCNFBBAH9AAMXLPLLLROQY99QN9DLSJUHDPBLCFFAIQXZA9BKMBJCYSFHFPXAHDWZFEIH
- GYOMKVTSNHVJNCNFBBAH9AAMXLPLLLROQY99QN9DLSJUHDPBLCFFAIQXZA9BKMBJCYSFHFPXAHDWZFEIQ
This is a consequence of always zeroing out the last “trit” before passing the input to Keccak-384.
Since this zeroing was an explicit design choice of Iota’s, I decided to helpfully submit a pull request adding these inputs as test vectors to their JavaScript implementation.
Why It Matters
These are the facts:
- Kerl is intended to replace Curl-P-27 within the Iota cryptocurrency.
- The Iota Foundation previously admitted that Curl-P-27 was a “copy-protection backdoor”.
- The ternary encoding in Kerl allows three different inputs to produce the same hash output (which is not true of Keccak-384).
Given the past behavior of the Iota developers, there are three possible explanations for this:
- It’s a bugdoor (a backdoor enabled by a bug) intended to be exploited by the Coordinator–possibly as another copy-protection backdoor in the spirit of Curl-P-27.
- They made a critical design mistake in Kerl, which may or may not be exploitable in one or more of the places they use Kerl.
- Their alleged justification for zeroing out the last trit is sound, and there’s no way to exploit this collision vulnerability within Iota.
The last explanation is the one that Iota fanboys will probably cling to, but let me be clear: Even if this isn’t exploitable within Iota, it’s still a huge fuck-up in the design of Kerl.
I’ve lost count of the number of projects I’ve encountered that used secp256k1 as their elliptic curve choice simply because it was also the curve Bitcoin used. These are protocols doing ECDSA for JSON Web Tokens, or ECDH for use in ECIES schemes.
The probability of someone eventually using Kerl outside of Iota is 1, and they will be vulnerable to collisions because of that choice.
Takeaways
Iota is a cryptocurrency project that threatens security researchers, intentionally backdoored the cryptographic hash function in their original design (for “copy-protection”) and admitted to it, and designed a replacement cryptographic hash function (Kerl) that is vulnerable to trivial collision attacks (but the underlying hash function, Keccak-384, is not).I don’t need to connect the lines on this one, do I?
Since this attack also works on “reduced round” variants of Kerl, I guess I win their bug bounty too!
If the Iota developers are reading this, please remit payment for your promised bounty to the following ZEC address: zs1lwghzjazt4h53gwnl7f24tdq99kw7eh9hgh3qumdvcndszl7ml4xmsudcmm60dut2cfesxmlcec
That being said, I never got an answer to my question, “Should I report the security reduction in bits or trits?” I’m feeling generous though. Given the cost of a collision is basically 1 trit, this is a 242-trit security reduction against collision attacks in Kerl.
https://soatok.blog/2020/07/15/kerlissions-trivial-collisions-in-iotas-hash-function-kerl/
#collision #cryptanalysis #Cryptocurrency #cryptographicHashFunction #hashFunction #iota #kerl #kerlission
