Vulnerability in IOTA’s curl-P hashing algorithm: What the fuss was all about?

in #iota6 years ago

Not quite long ago (just about a year, to be a bit more precise), there were articles floating all around, describing the tussle between IOTA’s development team and MIT’s Digital Currency Initiative team regarding collisions produced by the curl-P hashing algorithm that was being used by IOTA to sign transactions. The claim was that, since the signature scheme in IOTA Reference Implementation was operating on hashes of the message portion (which consisted of the amount of transaction and sender and receiver addresses), the signing process depended on the collision resistance of curl-P. This could potentially be exploited by a hacker to obtain valid signatures for a forged transaction. In other words, since two different message portions could be hashed to the same value, the signatures valid for the first (intended transaction) and the second (forged) transaction would be the same, which could then be broadcasted on the network to create unwanted transactions and hence, steal funds. (Signatures for a transaction can be easily queried. I can say that from my experience of designing a [wallet](https://github.com/utkarsh009/heliota) for iota).
To get have a closer look at the claims, I’ll be using a formal paper published in this regard.

Formal Paper

Do note that the emails related to this issue were leaked and can be found here.
Leaked Emails

A look at the formal research paper depicting the vulnerabilities

The paper is quite simple for a layman to read and you can simply glide through the paper. I don’t really think that anybody would have trouble reading and thoroughly understanding it, unless you’re really bad at basic mathematical operations, like addition, subtraction, multiplication etc.
However, for those who are really weak at it, I’d like to provide a few corrections (that were probably printing mistakes) and explanations, after all, it isn’t really a good idea to rush out to your peers and end up looking like Ocasio-Cortez.

An important thing to notice here is that this:

Theorem 1_1
Theorem 1_2

This theorem seeks to show that the absorption phase merely reorders the constituents of individual states of a sponge. It does so by proving that transform is indeed bijective (since the cardinality of domain and range is the same, they simply need to prove that it is injective). I’d like to point out that the method used for finding cycles of a desired length is much better and intuitive than the regular method of DFS traversals that some of the low grade colleges ask the students to memorise and never forget to include it in the exam papers. The same exact question is also asked as in interviews of some giant tech companies. If the solution is already out there, why ask for it?

Lemma 2

This lemma is a bit fucked up and they’ve mixed the words together, often using wrong words. So I’ve decided to put it down once again.

Diagram

Congruence

Similarly, replace ‘j’ with ‘j+1’, in the final result, to get the other congruency. The point to be made here is that given two states of sponges, s(k) and s(k+1), the relation that determines the value at position ‘j’ in s(k+1) can be inverted to get the positions that were affected by a change in ‘j’. This ‘differential’ propagates through the states of the sponge.

Probability

The encircled 231 is actually 359 (because that’s what bijection implies). Also, you can calculate and see that the resulting decimal is obtained when you divide 359 by 729. Anyways, just in case you were suspicious, I simply verified it. The results are shown below.

Terminal 1
Terminal 2

Conclusion

I’d finally like to conclude that curl-P is not a safe cryptographic hash function, as stated in the paper. On the positive side, the IOTA development team doesn’t claim it to be one either (according to the leaked emails). It was designed to allow practical collisions. Since they have since switched to kerl from curl-P for the purpose of signing, it doesn’t pose any practical threats.
Source

Sort:  

Congratulations @valkyr! You received a personal award!

1 Year on Steemit

Click here to view your Board

Do not miss the last post from @steemitboard:

Christmas Challenge - The party continues
Christmas Challenge - Send a gift to to your friends

Support SteemitBoard's project! Vote for its witness and get one more award!

Congratulations @valkyr! You have completed the following achievement on the Steem blockchain and have been rewarded with new badge(s) :

You got your First payout

Click here to view your Board
If you no longer want to receive notifications, reply to this comment with the word STOP

Support SteemitBoard's project! Vote for its witness and get one more award!

Congratulations @valkyr! You have completed the following achievement on the Steem blockchain and have been rewarded with new badge(s) :

You got a First Reply

Click here to view your Board
If you no longer want to receive notifications, reply to this comment with the word STOP

Support SteemitBoard's project! Vote for its witness and get one more award!

Congratulations @valkyr! You have completed the following achievement on the Steem blockchain and have been rewarded with new badge(s) :

You got more than 10 replies. Your next target is to reach 50 replies.

Click here to view your Board
If you no longer want to receive notifications, reply to this comment with the word STOP

Support SteemitBoard's project! Vote for its witness and get one more award!

Congratulations @valkyr! You have completed the following achievement on the Steem blockchain and have been rewarded with new badge(s) :

You made more than 50 upvotes. Your next target is to reach 100 upvotes.

Click here to view your Board
If you no longer want to receive notifications, reply to this comment with the word STOP

Support SteemitBoard's project! Vote for its witness and get one more award!

Congratulations @valkyr! You have completed the following achievement on the Steem blockchain and have been rewarded with new badge(s) :

You made more than 10 comments. Your next target is to reach 50 comments.

Click here to view your Board
If you no longer want to receive notifications, reply to this comment with the word STOP

Support SteemitBoard's project! Vote for its witness and get one more award!

Dear @valkyr

I just decided to visit your profile and check out your latest content only to notice that you didn't blog in quite a while already.

Hope you didn't give up completely on Steemit?

Cheers, Piotr

You can clearly see that the first few of my posts were written long before the recent ones, thereby implying that I’m not at all a blogger. I write only a few blogs every few months, whenever I feel like. Think of it like the social media posts that people make. I don’t like sharing my personal life. Instead, I like sharing my opinions on topics every once in a while. Sometimes I blog on Steemit and other times, I simply comment on YouTube videos.

Posted using Partiko iOS

Absolutely @valkyr

Thank you for your comment. Cheers
Piotr

Thx for your reply @valkyr

Thank you so much for sharing this amazing post with us!

Have you heard about Partiko? It’s a really convenient mobile app for Steem! With Partiko, you can easily see what’s going on in the Steem community, make posts and comments (no beneficiary cut forever!), and always stayed connected with your followers via push notification!

Partiko also rewards you with Partiko Points (3000 Partiko Point bonus when you first use it!), and Partiko Points can be converted into Steem tokens. You can earn Partiko Points easily by making posts and comments using Partiko.

We also noticed that your Steem Power is low. We will be very happy to delegate 15 Steem Power to you once you have made a post using Partiko! With more Steem Power, you can make more posts and comments, and earn more rewards!

If that all sounds interesting, you can:

Thank you so much for reading this message!

“Have you heard about Partiko?”
Yes.

Posted using Partiko iOS

Coin Marketplace

STEEM 0.20
TRX 0.15
JST 0.029
BTC 64512.68
ETH 2615.54
USDT 1.00
SBD 2.82