Modeling Soft Analytical Side-Channel Attacks from a Coding Theory Viewpoint
One important open question in side-channel analysis is to find out whether all the leakage samples in an implementation can be exploited by an adversary, as suggested by masking security proofs. For attacks exploiting a divide-and-conquer strategy, the answer is negative: only the leakages correspo...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Ruhr-Universität Bochum
2020-08-01
|
| Series: | Transactions on Cryptographic Hardware and Embedded Systems |
| Subjects: | |
| Online Access: | https://tches.iacr.org/index.php/TCHES/article/view/8682 |
| _version_ | 1818533153335148544 |
|---|---|
| author | Qian Guo Vincent Grosso François-Xavier Standaert Olivier Bronchain |
| author_facet | Qian Guo Vincent Grosso François-Xavier Standaert Olivier Bronchain |
| author_sort | Qian Guo |
| collection | DOAJ |
| description | One important open question in side-channel analysis is to find out whether all the leakage samples in an implementation can be exploited by an adversary, as suggested by masking security proofs. For attacks exploiting a divide-and-conquer strategy, the answer is negative: only the leakages corresponding to the first/last rounds of a block cipher can be exploited. Soft Analytical Side-Channel Attacks (SASCA) have been introduced as a powerful solution to mitigate this limitation. They represent the target implementation and its leakages as a code (similar to a Low Density Parity Check code) that is decoded thanks to belief propagation. Previous works have shown the low data complexities that SASCA can reach in practice. In this paper, we revisit these attacks by modeling them with a variation of the Random Probing Model used in masking security proofs, that we denote as the Local Random Probing Model (LRPM). Our study establishes interesting connections between this model and the erasure channel used in coding theory, leading to the following benefits. First, the LRPM allows bounding the security of concrete implementations against SASCA in a fast and intuitive manner. We use it in order to confirm that the leakage of any operation in a block cipher can be exploited, although the leakages of external operations dominate in known-plaintext/ciphertext attack scenarios. Second, we show that the LRPM is a tool of choice for the (nearly worst-case) analysis of masked implementations in the noisy leakage model, taking advantage of all the operations performed, and leading to new tradeoffs between their amount of randomness and physical noise level. Third, we show that it can considerably speed up the evaluation of other countermeasures such as shuffling. |
| first_indexed | 2024-12-11T17:54:55Z |
| format | Article |
| id | doaj.art-ec11eb76f0534bc9939d3d3004fed075 |
| institution | Directory Open Access Journal |
| issn | 2569-2925 |
| language | English |
| last_indexed | 2024-12-11T17:54:55Z |
| publishDate | 2020-08-01 |
| publisher | Ruhr-Universität Bochum |
| record_format | Article |
| series | Transactions on Cryptographic Hardware and Embedded Systems |
| spelling | doaj.art-ec11eb76f0534bc9939d3d3004fed0752022-12-22T00:56:06ZengRuhr-Universität BochumTransactions on Cryptographic Hardware and Embedded Systems2569-29252020-08-012020410.13154/tches.v2020.i4.209-238Modeling Soft Analytical Side-Channel Attacks from a Coding Theory ViewpointQian Guo0Vincent Grosso1François-Xavier Standaert2Olivier Bronchain3Department of Electrical and Information Technology, Lund University, Sweden; Department of Informatics, University of Bergen, Norway; Crypto Group, ICTEAM Institute, UCLouvain, Louvain-la-Neuve, BelgiumCNRS/Laboratoire Hubert Curien, Université de Lyon, FranceCrypto Group, ICTEAM Institute, UCLouvain, Louvain-la-Neuve, BelgiumCrypto Group, ICTEAM Institute, UCLouvain, Louvain-la-Neuve, BelgiumOne important open question in side-channel analysis is to find out whether all the leakage samples in an implementation can be exploited by an adversary, as suggested by masking security proofs. For attacks exploiting a divide-and-conquer strategy, the answer is negative: only the leakages corresponding to the first/last rounds of a block cipher can be exploited. Soft Analytical Side-Channel Attacks (SASCA) have been introduced as a powerful solution to mitigate this limitation. They represent the target implementation and its leakages as a code (similar to a Low Density Parity Check code) that is decoded thanks to belief propagation. Previous works have shown the low data complexities that SASCA can reach in practice. In this paper, we revisit these attacks by modeling them with a variation of the Random Probing Model used in masking security proofs, that we denote as the Local Random Probing Model (LRPM). Our study establishes interesting connections between this model and the erasure channel used in coding theory, leading to the following benefits. First, the LRPM allows bounding the security of concrete implementations against SASCA in a fast and intuitive manner. We use it in order to confirm that the leakage of any operation in a block cipher can be exploited, although the leakages of external operations dominate in known-plaintext/ciphertext attack scenarios. Second, we show that the LRPM is a tool of choice for the (nearly worst-case) analysis of masked implementations in the noisy leakage model, taking advantage of all the operations performed, and leading to new tradeoffs between their amount of randomness and physical noise level. Third, we show that it can considerably speed up the evaluation of other countermeasures such as shuffling.https://tches.iacr.org/index.php/TCHES/article/view/8682Side-Channel AnalysisWorst-Case Security EvaluationsHorizontal (aka Multi-Target) AttacksBelief PropagationMaskingShuffling |
| spellingShingle | Qian Guo Vincent Grosso François-Xavier Standaert Olivier Bronchain Modeling Soft Analytical Side-Channel Attacks from a Coding Theory Viewpoint Transactions on Cryptographic Hardware and Embedded Systems Side-Channel Analysis Worst-Case Security Evaluations Horizontal (aka Multi-Target) Attacks Belief Propagation Masking Shuffling |
| title | Modeling Soft Analytical Side-Channel Attacks from a Coding Theory Viewpoint |
| title_full | Modeling Soft Analytical Side-Channel Attacks from a Coding Theory Viewpoint |
| title_fullStr | Modeling Soft Analytical Side-Channel Attacks from a Coding Theory Viewpoint |
| title_full_unstemmed | Modeling Soft Analytical Side-Channel Attacks from a Coding Theory Viewpoint |
| title_short | Modeling Soft Analytical Side-Channel Attacks from a Coding Theory Viewpoint |
| title_sort | modeling soft analytical side channel attacks from a coding theory viewpoint |
| topic | Side-Channel Analysis Worst-Case Security Evaluations Horizontal (aka Multi-Target) Attacks Belief Propagation Masking Shuffling |
| url | https://tches.iacr.org/index.php/TCHES/article/view/8682 |
| work_keys_str_mv | AT qianguo modelingsoftanalyticalsidechannelattacksfromacodingtheoryviewpoint AT vincentgrosso modelingsoftanalyticalsidechannelattacksfromacodingtheoryviewpoint AT francoisxavierstandaert modelingsoftanalyticalsidechannelattacksfromacodingtheoryviewpoint AT olivierbronchain modelingsoftanalyticalsidechannelattacksfromacodingtheoryviewpoint |