Paper 2019/690
Multiple-Differential Mechanism for Collision-Optimized Divide-and-Conquer Attacks
Changhai Ou, Siew-Kei Lam, and Guiyuan Jiang
Abstract
Several combined attacks have shown promising results in recovering cryptographic keys by introducing collision information into divide-and-conquer attacks to transform a part of the best key candidates within given thresholds into a much smaller collision space. However, these Collision-Optimized Divide-and-Conquer Attacks (CODCAs) uniformly demarcate the thresholds for all sub-keys, which is unreasonable. Moreover, the inadequate exploitation of collision information and backward fault tolerance mechanisms of CODCAs also lead to low attack efficiency. Finally, existing CODCAs mainly focus on improving collision detection algorithms but lack theoretical basis. We exploit Correlation-Enhanced Collision Attack (CECA) to optimize Template Attack (TA). To overcome the above-mentioned problems, we first introduce guessing theory into TA to enable the quick estimation of success probability and the corresponding complexity of key recovery. Next, a novel Multiple-Differential mechanism for CODCAs (MD-CODCA) is proposed. The first two differential mechanisms construct collision chains satisfying the given number of collisions from several sub-keys with the fewest candidates under a fixed probability provided by guessing theory, then exploit them to vote for the remaining sub-keys. This guarantees that the number of remaining chains is minimal, and makes MD-CODCA suitable for very high thresholds. Our third differential mechanism simply divides the key into several large non-overlapping ``blocks'' to further exploit intra-block collisions from the remaining candidates and properly ignore the inter-block collisions, thus facilitating the latter key enumeration. The experimental results show that MD-CODCA significantly reduces the candidate space and lowers the complexity of collision detection, without considerably reducing the success probability of attacks.
Metadata
- Available format(s)
-
PDF
- Category
- Implementation
- Publication info
- Preprint. MINOR revision.
- Keywords
- MD-CODCACODCAguessing theorycandidate spacekey enumerationcollision attackside-channel attack
- Contact author(s)
- chou @ ntu edu sg
- History
- 2020-06-08: last of 2 revisions
- 2019-06-12: received
- See all versions
- Short URL
- https://ia.cr/2019/690
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2019/690,
author = {Changhai Ou and Siew-Kei Lam and Guiyuan Jiang},
title = {Multiple-Differential Mechanism for Collision-Optimized Divide-and-Conquer Attacks},
howpublished = {Cryptology {ePrint} Archive, Paper 2019/690},
year = {2019},
url = {https://eprint.iacr.org/2019/690}
}