IOTA vs DCI, or how an innocent hash collision became a huge ego collision

#cryptoanalyst

This article describes my view on the IOTA vs DCI situation and explores why I would happily use Curl to secure IOTA.

Having read the leaked emails between IOTA and DCI entirely it seems very clear to me that DCI crossed the line of objectivity so far that it isn’t even funny any more. Conflict of interest is dripping from a lot of the emails and responses. Yes, I am an IOTA aficionado, but even more so I am a developer. And a developer wants to see the truth and proof of claims that are being made. I have a track record of allowing people to point out my mistakes and learn from them so that I can grow and come up with even better mistakes, errmmmm… I mean solutions.

Never roll your own ego…

Now imagine the following scenario. You are -or think you are- a famous cryptographer. And then you are asked to do an analysis of a new hash function designed to be used in a completely new crypto currency. You haven’t heard of them before, so you assume they are rank amateurs. You quickly cobble together a hash collision by analyzing their hash function, and triumphantly tell them you found a serious vulnerability!. Wow! Are you great, or what? That took hardly any time.

Now this guy who you haven’t ever heard of starts explaining to you that you found a copy protection measure in the function that was designed to create collisions, and furthermore, you also did not use the function correctly. He patiently explains to you (You! The person who literally wrote the book) the errors in your thinking, and asks you to check again and provide further proof of some unsubstantiated claims, which you made because it was ‘obvious’ to you that it was only a matter of time for you to break this thing completely.

Turns out this hash function was never meant to be a cryptographic hash function, but a light weight hash function that can be adapted to certain purposes (tuned, as it were), by simply increasing the number of rounds of hashing. The intended use cases range from hashing (obviously), to pseudo-random number generation, key generation, and include one-wayness and yes, even collision resistance. It was meant to be used in combination with other, more important measures to guarantee the safety of the crypto currency.

Now instead of becoming excited, as every open-minded researcher would be, that someone came up with some cool new ideas that could further the field of hashing/cryptography, you instead start nitpicking and stalling. Because obviously, they did not follow the book (which you wrote!). So obviously they cannot know what they are talking about. In addition, this new crypto currency now threatens to become a major competitor of the currency that you yourself are involved in.

So you ignore their requests for further proof that you can break it completely instead of only being able to create hash collisions by tweaking two input messages of your choice, and instead you publish a damaging report against established academic responsibility conventions, just so you can show everyone how smart you (think) you are. Ignoring the facts that you cannot prove collisions with random given inputs, that this function was only one part of their security measures, and that you are seriously hurting innocent people invested in the currency by torpedoing their investment value.

In fact, you enlist your buddy cryptographers to start tweeting even more bullshit, because obviously these guys are dangerous. Instead of doing 100% theoretical mental exercises, they actually use their knowledge for practical purposes, and it seems to work well in practice, proving you wrong even more. These guys even had the gall to -on the off chance that you were right- replace their hash function with an established one for now, just to be on the safe side, but they proclaim they are still intending to use their own hash function once it’s properly vetted by real cryptographers that have not encrypted their minds shut yet.

Funny how hypothetical scenarios often play out almost identically in real life. The moral of the story: never roll your own ego, egos are notoriously difficult to control, and if you must then it should be submitted for peer review before using it in a critical thinker environment.

Why I would use Curl as it is without hesitation

Like I said, I am a developer. I read code like other people read a book. So I dove into the code to inspect the security of IOTA for myself, and what I discovered left me in awe. The combination of ideas in there is so well thought out, and so practical when executed, that it puts itself light years ahead of other distributed ledger technology. Not only did it solve a number of the really big problems of block chain technology, but it enables entirely new applications without bogging everyone down with things they don’t need.

Anyway, after looking at the code I came to the conclusion that if you follow the rules it is practically impossible, and definitely impractical to break IOTA’s signing mechanism. The simple rule that makes it impossible to break a signature is: never re-use an address after spending from it.

That’s it. That’s all there is to it. Because IOTA’s addresses are created by hashing together the private key parts into a much smaller 81 tryte value, it is impossible to find your way back to the original private key. So as long as you don’t sign off on a transfer out of your address it is impossible for anyone to create a private key in their lifetime that would enable them to steal the funds in the address. Impossible, because finding a combination of private key parts that together hash into that same address is, due to the staggering amount of combinations that an 81 tryte value can assume not doable in the life time of our universe, even if you had whole galaxies full of quantum computers working on the problem.

For the cryptographers among you here is a video that explains it in very simple terms: https://www.youtube.com/watch?v=p8YIdmwcubc

I know you will probably want to start nitpicking on Twitter that this video is not about addresses but about seeds, but trust me, seeds are of identical length, so the same calculations apply here. The chance of me being right here is definitely non-negligible (no need to discuss that word on Twitter, I believe that was done sufficiently already).

Anyway, I digress. So brute forcing the private key for a random address is definitely out. Which leaves you with analyzing the Curl hash function and find a way to come up with a method that, given a certain address, can reverse-engineer a corresponding valid signing key, of which there should be huge amounts, given the fact that any hash function essentially hashes a large input value into a smaller output value. I believe you call it a collision when 2 different input values end up with the same output value, right?

Cryptographic attack types

1. Collision attack. In this scenario the attacker is free to choose two different inputs m1 and m2 that will both generate the same hash value. This is what DCI did. They used an obvious flaw in the algorithm to demonstrate that -as long as they exploit that flaw- they are able to construct 2 different messages that will hash to the same value. Very nice. They did not use the Curl function correctly, did not even use the collision-resistant version of the Curl function, and ignored the fact that the obvious flaw they found was a copy protection measure, but hey! Who cares! They broke it, right?
2. Second Pre-image attack. This one is trickier to pull off, because you cannot construct input m1 yourself. You now need to be able to do the same for a random message, with non-negligible chance. So you need to be able to demonstrate that with several random m1’s to show it wasn’t a fluke. Now we’re getting into the problem area of the size of the hash output, which is 81 trytes. So brute forcing is out. Which means you definitely need to find a flaw in the hashing algorithm to pull it off. It also means you will need to prove that you can pull it off. Just saying you can is not enough. People need to be able to verify that you can do what you claim you can do. Hey, DCI! Still waiting for that proof after many months!
3. First pre-image attack. This one is even trickier. You now are only provided with the hash value. All you need to do is to show that you can construct a message m1 that hashes into that hash value. So you don’t have a sample of the input message that you can inspect for flaws. You just reverse the hash function that is supposed to by one-way only. This one is equivalent to being able to generate a private key to an address from the address itself.

Note that if you can do 3, you are probably able to generate two different messages that hash to the hash value, which means you can do 2. And in that case you have created a hash collision, so you are able to do 1. The other way around is not so easy. The successive types of attacks get more and more difficult to do.

Well, let’s do some calculations, shall we? Let’s use the lowest security setting for signatures to avoid complexity and give you the best chance to crack IOTA. And we’ll also ignore the fact that Curl itself does a predefined number of hash rounds that depends on its intended purpose and can easily be made collision resistant by increasing the amount of hash rounds. Instead we call an invocation of Curl a single hash. We are trying to improve the odds of breaking it by explicitly weakening our security here.

Generating an IOTA address

Addresses in IOTA are generated from an 81 tryte subseed, which is derived from a secure random seed by hashing once. This random subseed can have 27⁸¹ or over 8.7 x 10¹¹⁵ different values. To create a private key this subseed is hashed into 27 81-tryte key fragments. That means that we now have a private key of 27 x 81 or 2187 trytes long.

Next step: creating the address from the private key. An address is also 81 trytes. This should be easy to break for any cryptographer, right? I mean, we have 27²¹⁸⁷ possible private key input values that map onto 27⁸¹ possible address output values. Which means that every possible address on average should have about 27²¹⁰⁶ private keys. Take your pick! Lol. Yeah, right.

So here’s how you create the address: Take each of the 27 81-tryte key fragments and hash each of them 26 times. Then take the resulting 27 81-tryte hash values and hash them together into a single 81-tryte output value. This is your address. Note that you only have to do 27 x 26 + 27 or 729 hashes. Should be easy to break, right?

The signing process

Now here’s the (simplified) signing process. The whole idea is that you need to generate a signature that signs off on transferring funds from the address, and that signature proves conclusively that it was generated by the owner. In which case the Tangle will allow the transfer of the funds to another address.

Remember the address generation algorithm described above? Signing works exactly like that. Essentially the signer hashes each of the private key fragments anywhere from 0–26 times (on average about half-way) towards the address and uses the resulting 27 intermediary 81 tryte values as the 2187 tryte signature. Now to verify the signature, we determine how many times each fragment was hashed towards the address, perform the remaining number of hashes on each of the 27 hashed key fragments to reach 26 hashes, then hash the results together into a single 81 tryte hash value, and compare that result to the address that is being signed. Only the original owner of the private key should have been able to create that half-way hash signature.

The exact number of times to hash each key fragment is determined by the first 27 trytes of the bundle hash of the transaction bundle. For simplicity’s sake let’s not look at the fact that these are in reality first converted into a normalized bundle hash, and also disregard the fact that a bundle hash can need recalculating whenever those trytes contain a certain tryte value. I just want to show here how difficult breaking the signature still would be.

The bundle hash

The bundle hash is calculated from a number of fields in the transaction bundle. Assuming the simplest composition the transaction bundle will contain a single input transaction with the input address and value to transfer from that address, and a single output transaction, with the output address and the value to transfer into that address. Again, let’s simplify. Let’s assume the bundle hash is calculated only by hashing the address and value fields from each transaction. This will still be a random 81 tryte value because both the input and output addresses are completely random values.

By the way, if you’re interested, the security levels 2 and 3 will create a 2 or 3 times longer private key, and use the first 54 or 81 trytes of the hash value, respectively, to make breaking the signature exponentially more difficult.

Cracking the signature

To generate a valid signature without having the private key of the address you will now have to do the following:

Create a bundle that transfers the amount from the (random) input address to your (random) output address. Note that both addresses are so random because they were generated from a random seed by hashing 729 times. You will need to be able to get to the funds after stealing them, so you must be able to sign your own address. Therefore there is no way to cheat and use just any predefined output address. Now you use the transaction fields to calculate the bundle hash.

Now you have to come up with a signature that, for each of the key fragments, will be hashed the remaining number of times to get to 26 hashes as defined by the corresponding tryte in the bundle hash. So on average that would amount to about 13 or so hashes per fragment. Then you need to hash the fragments together and end up with the input address. Sounds complex? That’s because it is!

Note that an attacker does not need the original private key at all. He only needs to come up with a valid intermediate set of key fragments. Any signature that, when hashed further according to the bundle hash trytes, results in the input address will be accepted by the Tangle as valid. The Tangle has no clue about the exact private key for an address, nor does it need to know. All it needs to know is the verification process.

The problem in constructing such a signature is the dependency on the bundle hash, and the sheer amount of hashes involved. Even if you analyze the hash function for weaknesses, you cannot easily choose the input values for the bundle hash, nor come up easily with signature fragments that end up as the address when finalizing the address generation process. Tracing this backward from the address to the signature fragments is pretty much impossible. Plus it depends on the exact values of the first 27 trytes of the bundle hash. Which makes it extra difficult. You cannot simply generate a bundle hash that makes the amount of remaining hashes minimal, either.

Straight brute forcing is definitely out. The only way to do it is to limit the amount of brute forcing using a weakness in the hashing algorithm. Well, isn’t that where the whole discussion began? There is no proof of being able to do a First Pre-image Attack. And, to be blunt, without proof you better shut your trap. There’s no way this proof exists, because it would have been the simplest way of proving you are right and they are wrong. In fact, there now is a whole legion of cryptographers that have been manipulated into taking sides and therefore are anxious to prove there actually is a flaw. And still no proof. After many months. Guess I will take my chances here….

But what about addresses that were signed already?

Oh, so you want to do a Second Pre-image Attack instead?

Well, if you can trick someone into signing a transaction from an address and against the clear rules receive funds again on that same address you just considerably increased your chances. Personally, knowing what I know, I tell people all the time to ignore payments made to previously spent addresses until they have succeeded in moving the funds safely to an unused address. I will assume malicious intent if you send funds anywhere else than an address I previously reserved for you.

But okay. Let’s see. You tricked me nonetheless, and now you have a valid signature, so all you need now is to generate a bundle hash that collides only in the same first 27 trytes as the bundle that was signed before.

Except that original bundle transferred to an address of my choosing. Now if you want to create a bundle that sends to your address you will need to create a very specific bundle, containing your random address, that hashes into the same bundle hash. Usually an attacker would try to brute force such a bundle by using one of the fields (like the tag field) in the bundle as a nonce field, and then incrementing the nonce until the bundle ends up having the required 27 trytes prefix. On average that would mean you need to try 27²⁷ / 2 possible nonce combinations. I hope you have the time and/or processing power to do that.

To be frank, there is a simpler way, because having the signature means you also can calculate the signatures for higher tryte values than those in each of the first 27 trytes of the bundle hash. You know how many hashes were done already from the original bundle, and so you also can generate all signature fragments that are hashed more than that amount. Of course that means a whole different permutation game, because now you only need to check if the first 27 separate trytes are greater or equal to the corresponding separate trytes in the original bundle hash. It will still require considerable hashing power to achieve this, however. Depending on the exact values of the bundle hash, of course, but statistically on average you will have to check 13.5²⁷ / 2 possible nonce combinations.

This last trick, by the way, is how thieves can in certain optimal cases steal your funds while you are spending/signing a second time from the same address. They now have even more key fragments than before to check against, and statistically they only need to check 6.75²⁷ / 2 possible nonce combinations. In practice, their odds could even be better than this due to the nature of randomness.

Moral of the story: never re-use an address and you should be safe. Also: always verify that, when someone sends you funds, they use the specified receive address, and they don’t try to send to one of your previously spent addresses. They or some other hacker may try to siphon the funds to their own account in that case. I will personally refuse any funds that get sent to the wrong address as a valid payment until I had the chance to safely transfer them to a previously unused address. If they get stolen during this process the payment is null and void, and I make that very clear on any invoices I send.

Conclusion

A hash function forms only a small part of the overall system security. Being able to create a hash collision in certain chosen cases is not a recipe for being able to crack the entire system, just like me being able to duplicate a chosen key to the bank from the bank director will still not allow me to rob the bank.

Misinformation is a very powerful tool in today’s internet world, because not many people take the time to verify a claim, especially when it comes from an ‘authority’ figure. Abusing the power thus given to you is reprehensible to say the least. Academics in particular should always be impartial and dedicated to the truth instead of to their egos, and definitely clearly mark any conflict of interest.