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

【Author】 Liu, Fukang; Isobe, Takanori

【Source】IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES

【影响因子】0.423

【Abstract】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 3(79) from 3(243). For the preimage attack on 3-round Troika, the MILP-based method is applied to achieve the optimal time complexity, which is 3(27) times faster than brute force.

【Keywords】hash function; Troika; (second) preimage; guess-and-determine; divide-and-conquer; MILP

【发表时间】2020 NOV

【收录时间】2022-01-02

【文献类型】

【主题类别】

--