IEICE TRANSACTIONS on Fundamentals
Preimage Attacks on Reduced Troika with Divide-and-Conquer Methods
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E103-A No.11 pp.1260-1273
- Publication Date
- 2020/11/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.2019EAP1166
- Type of Manuscript
- PAPER
- Category
- Cryptography and Information Security
Authors
Fukang LIU
University of Hyogo,East China Normal University
Takanori ISOBE
University of Hyogo,National Institute of Information and Communications Technology
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Fukang LIU, Takanori ISOBE, "Preimage Attacks on Reduced Troika with Divide-and-Conquer Methods" in IEICE TRANSACTIONS on Fundamentals,
vol. E103-A, no. 11, pp. 1260-1273, November 2020, doi: 10.1587/transfun.2019EAP1166.
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 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2019EAP1166/_p
Copy
@ARTICLE{e103-a_11_1260,
author={Fukang LIU, Takanori ISOBE, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Preimage Attacks on Reduced Troika with Divide-and-Conquer Methods},
year={2020},
volume={E103-A},
number={11},
pages={1260-1273},
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 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.},
keywords={},
doi={10.1587/transfun.2019EAP1166},
ISSN={1745-1337},
month={November},}
Copy
TY - JOUR
TI - Preimage Attacks on Reduced Troika with Divide-and-Conquer Methods
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1260
EP - 1273
AU - Fukang LIU
AU - Takanori ISOBE
PY - 2020
DO - 10.1587/transfun.2019EAP1166
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E103-A
IS - 11
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - November 2020
AB - 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.
ER -
English
