Paper 2019/618

Preimage Attacks on Reduced Troika with Divide-and-Conquer Methods

Fukang Liu and Takanori Isobe


Troika is a recently proposed sponge-based hash function for IOTA's ternary architecture and platform, which is developed by CYBERCRYPT. In this paper, we introduce the preimage attack on 2 and 3 rounds of Troika with a divide-and-conquer approach. Instead of directly matching a given hash value, we propose equivalent conditions to determine whether a message is the preimage before computing the complete hash value. As a result, for the two-round hash value that can be generated with one block, we can search the preimage only in a valid space and efficiently enumerate the messages which can satisfy most of the equivalent conditions with a guess-and-determine technique. For the three-round preimage attack, an MILP-based method is applied to separate the one-block message space into two parts in order to obtain the best advantage over brute force. Our experiments show that the time complexity of the preimage attack on 2 (out of 24) rounds of Troika can be improved to $3^{79}$, which is $3^{164}$ times faster than the brute force. For the preimage attack on 3 (out of 24) rounds of Troika, we can obtain an advantage of $3^{25.7}$ over brute force. In addition, how to construct the second preimage for two-round Troika in seconds is presented as well. Our attacks do not threaten the security of Troika.

Note: In previous paper, we partially solve the two-round preimage challenge with 25 different trits. In this new version, we slightly adjust the parameter and can partially solve this challenge with only 18 different trits, which was finished in minutes. However, when we search for longer time, there was still not a better result. If there is any update in the future, we will report it accrodingly. Moreover, we observed that the different trits are all located at the last two slices (slice 7 and slice 8) of the hash value and has a good difference pattern, which may be exploited to find a real preimage in the future.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. Minor revision. IWSEC 2019
hash functionTroikapreimageguess-and-determinedivide-and-conquerMILP
Contact author(s)
liufukangs @ 163 com
takanori isobe @ ai u-hyogo ac jp
2019-06-14: last of 3 revisions
2019-06-03: received
See all versions
Short URL
Creative Commons Attribution


      author = {Fukang Liu and Takanori Isobe},
      title = {Preimage Attacks on Reduced Troika with Divide-and-Conquer Methods},
      howpublished = {Cryptology ePrint Archive, Paper 2019/618},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.