Kerlissions – Trivial Collisions in Iota’s Hash Function (Kerl)

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:

pic.twitter.com/0dm6r18rBE

— Deirdre Connolly¹ ² (@durumcrustulum) January 11, 2019

In response to this research, the Iota developers threatened to sue the researchers.

Oh good. Here’s an IOTA founder darkly threatening to sue a researcher who found out that the IOTA hash function was broken (something he later claimed was done on purpose.) pic.twitter.com/myRCv098uf

— Matthew Green (@matthew_d_green) February 19, 2018

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:

pic.twitter.com/wedOjaUxlI

— Deirdre Connolly¹ ² (@durumcrustulum) January 11, 2019

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:

1. 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.
2. 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.
3. 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.