Paper 2019/618

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

Fukang Liu and Takanori Isobe

Abstract

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.