[Resource Topic] 2019/618: Preimage Attacks on Reduced Troika with Divide-and-Conquer Methods

Welcome to the resource topic for 2019/618

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

Authors: Fukang Liu, 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.

ePrint: https://eprint.iacr.org/2019/618

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .