The science of guessing in collision-optimized divide-and-conquer attacks
Recovering keys ranked in very deep candidate space efficiently is a very important but challenging issue in side-channel attacks (SCAs). State-of-the-art collision-optimized divide-and-conquer attacks (CODCAs) extract collision information from a collision attack to optimize the key recovery of a d...
Saved in:
Main Authors: | , , |
---|---|
Other Authors: | |
Format: | Article |
Language: | English |
Published: |
2022
|
Subjects: | |
Online Access: | https://hdl.handle.net/10356/160239 |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Nanyang Technological University |
Language: | English |
id |
sg-ntu-dr.10356-160239 |
---|---|
record_format |
dspace |
spelling |
sg-ntu-dr.10356-1602392022-07-18T03:00:40Z The science of guessing in collision-optimized divide-and-conquer attacks Ou, Changhai Lam, Siew-Kei Jiang, Guiyuan School of Computer Science and Engineering Hardware & Embedded Systems Lab (HESL) Engineering::Computer science and engineering Collision Attack Divide and Conquer Recovering keys ranked in very deep candidate space efficiently is a very important but challenging issue in side-channel attacks (SCAs). State-of-the-art collision-optimized divide-and-conquer attacks (CODCAs) extract collision information from a collision attack to optimize the key recovery of a divide-and-conquer attack, and transform the very huge guessing space to a much smaller collision space. However, the inefficient collision detection makes them time consuming. The very limited collisions exploited and large performance difference between the collision attack and the divide-and-conquer attack in CODCAs also prevent their application in much larger spaces. In this article, we propose a Minkowski distance enhanced collision attack (MDCA) with performance closer to template attack (TA) compared to traditional correlation-enhanced collision attack (CECA), thus making the optimization more practical and meaningful. Next, we build a more advanced CODCA named full-collision chain (FCC) from TA and MDCA to exploit all collisions. Moreover, to minimize the thresholds while guaranteeing a high success probability of key recovery, we propose a fault-tolerant scheme to optimize FCC. The full key is divided into several big 'blocks,' on which a fault-tolerant vector (FTV) is exploited to flexibly adjust its chain space. Finally, guessing theory is exploited to optimize thresholds determination and search order of subkeys. Experimental results show that FCC notably outperforms the existing CODCAs. National Research Foundation (NRF) This work was supported in part by the National Research Foundation Singapore Under Its Campus for Research Excellence and Technological Enterprise Programme with the Technical University of Munich at TUMCREATE. 2022-07-18T03:00:40Z 2022-07-18T03:00:40Z 2020 Journal Article Ou, C., Lam, S. & Jiang, G. (2020). The science of guessing in collision-optimized divide-and-conquer attacks. IEEE Transactions On Computer-Aided Design of Integrated Circuits and Systems, 40(6), 1039-1051. https://dx.doi.org/10.1109/TCAD.2020.3031243 0278-0070 https://hdl.handle.net/10356/160239 10.1109/TCAD.2020.3031243 2-s2.0-85106626822 6 40 1039 1051 en IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems © 2020 IEEE. All rights reserved. |
institution |
Nanyang Technological University |
building |
NTU Library |
continent |
Asia |
country |
Singapore Singapore |
content_provider |
NTU Library |
collection |
DR-NTU |
language |
English |
topic |
Engineering::Computer science and engineering Collision Attack Divide and Conquer |
spellingShingle |
Engineering::Computer science and engineering Collision Attack Divide and Conquer Ou, Changhai Lam, Siew-Kei Jiang, Guiyuan The science of guessing in collision-optimized divide-and-conquer attacks |
description |
Recovering keys ranked in very deep candidate space efficiently is a very important but challenging issue in side-channel attacks (SCAs). State-of-the-art collision-optimized divide-and-conquer attacks (CODCAs) extract collision information from a collision attack to optimize the key recovery of a divide-and-conquer attack, and transform the very huge guessing space to a much smaller collision space. However, the inefficient collision detection makes them time consuming. The very limited collisions exploited and large performance difference between the collision attack and the divide-and-conquer attack in CODCAs also prevent their application in much larger spaces. In this article, we propose a Minkowski distance enhanced collision attack (MDCA) with performance closer to template attack (TA) compared to traditional correlation-enhanced collision attack (CECA), thus making the optimization more practical and meaningful. Next, we build a more advanced CODCA named full-collision chain (FCC) from TA and MDCA to exploit all collisions. Moreover, to minimize the thresholds while guaranteeing a high success probability of key recovery, we propose a fault-tolerant scheme to optimize FCC. The full key is divided into several big 'blocks,' on which a fault-tolerant vector (FTV) is exploited to flexibly adjust its chain space. Finally, guessing theory is exploited to optimize thresholds determination and search order of subkeys. Experimental results show that FCC notably outperforms the existing CODCAs. |
author2 |
School of Computer Science and Engineering |
author_facet |
School of Computer Science and Engineering Ou, Changhai Lam, Siew-Kei Jiang, Guiyuan |
format |
Article |
author |
Ou, Changhai Lam, Siew-Kei Jiang, Guiyuan |
author_sort |
Ou, Changhai |
title |
The science of guessing in collision-optimized divide-and-conquer attacks |
title_short |
The science of guessing in collision-optimized divide-and-conquer attacks |
title_full |
The science of guessing in collision-optimized divide-and-conquer attacks |
title_fullStr |
The science of guessing in collision-optimized divide-and-conquer attacks |
title_full_unstemmed |
The science of guessing in collision-optimized divide-and-conquer attacks |
title_sort |
science of guessing in collision-optimized divide-and-conquer attacks |
publishDate |
2022 |
url |
https://hdl.handle.net/10356/160239 |
_version_ |
1738844855452303360 |