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

Fukang LIU  Takanori ISOBE  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E103-A   No.11   pp.1260-1273
Publication Date: 2020/11/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.2019EAP1166
Type of Manuscript: PAPER
Category: Cryptography and Information Security
Keyword: 
hash function,  Troika,  (second) preimage,  guess-and-determine,  divide-and-conquer,  MILP,  

Full Text: PDF(2.3MB)>>
Buy this Article




Summary: 
Troika is a recently proposed sponge-based hash function for IOTA's ternary architecture and platform, which is developed by CYBERCRYPT and is now used in IOTA's blockchain. In this paper, we introduce the preimage attack on 2/3 rounds of Troika with a divide-and-conquer approach. Firstly, we propose the equivalent conditions to determine whether a message is the preimage with an algebraic method. As a result, for the preimage attack on two-round Troika, we can search the preimage only in a valid smaller space and efficiently enumerate the messages which can satisfy most of the equivalent conditions with a guess-and-determine technique. Our experiments show that the time complexity of the preimage attack on 2-round Troika can be improved to 379 from 3243. For the preimage attack on 3-round Troika, the MILP-based method is applied to achieve the optimal time complexity, which is 327 times faster than brute force.