Fully Automated Differential Fault Analysis on Software Implementations of Block Ciphers
Differential Fault Analysis (DFA) is considered as the most popular fault analysis method. While there are techniques that provide a fault analysis automation on the cipher level to some degree, it can be shown that when it comes to software implementations, there are new vulnerabilities, which cann...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Ruhr-Universität Bochum
2019-05-01
|
| Series: | Transactions on Cryptographic Hardware and Embedded Systems |
| Subjects: | |
| Online Access: | https://tches.iacr.org/index.php/TCHES/article/view/8286 |
| _version_ | 1818474409031106560 |
|---|---|
| author | Xiaolu Hou Jakub Breier Fuyuan Zhang Yang Liu |
| author_facet | Xiaolu Hou Jakub Breier Fuyuan Zhang Yang Liu |
| author_sort | Xiaolu Hou |
| collection | DOAJ |
| description | Differential Fault Analysis (DFA) is considered as the most popular fault analysis method. While there are techniques that provide a fault analysis automation on the cipher level to some degree, it can be shown that when it comes to software implementations, there are new vulnerabilities, which cannot be found by observing the cipher design specification.
This work bridges the gap by providing a fully automated way to carry out DFA on assembly implementations of symmetric block ciphers. We use a customized data flow graph to represent the program and develop a novel fault analysis methodology to capture the program behavior under faults. We establish an effective description of DFA as constraints that are passed to an SMT solver. We create a tool that takes assembly code as input, analyzes the dependencies among instructions, automatically attacks vulnerable instructions using SMT solver and outputs the attack details that recover the last round key (and possibly the earlier keys). We support our design with evaluations on lightweight ciphers SIMON, SPECK, and PRIDE, and a current NIST standard, AES. By automated assembly analysis, we were able to find new efficient DFA attacks on SPECK and PRIDE, exploiting implementation specific vulnerabilities, and previously published DFA on SIMON and AES. Moreover, we present a novel DFA on multiplication operation that has never been shown for symmetric block ciphers before. Our experimental evaluation also shows reasonable execution times that are scalable to current cipher designs and can easily outclass the manual analysis. Moreover, we present a method to check the countermeasure-protected implementations in a way that helps implementers to decide how many rounds should be protected.
We note that this is the first work that automatically carries out DFA on cipher implementations without any plaintext or ciphertext information and therefore, can be generally applied to any input data to the cipher. |
| first_indexed | 2024-04-14T04:37:28Z |
| format | Article |
| id | doaj.art-d8a01b6d33844b64ac8b58e5ec72ce3e |
| institution | Directory Open Access Journal |
| issn | 2569-2925 |
| language | English |
| last_indexed | 2024-04-14T04:37:28Z |
| publishDate | 2019-05-01 |
| publisher | Ruhr-Universität Bochum |
| record_format | Article |
| series | Transactions on Cryptographic Hardware and Embedded Systems |
| spelling | doaj.art-d8a01b6d33844b64ac8b58e5ec72ce3e2022-12-22T02:11:49ZengRuhr-Universität BochumTransactions on Cryptographic Hardware and Embedded Systems2569-29252019-05-012019310.13154/tches.v2019.i3.1-29Fully Automated Differential Fault Analysis on Software Implementations of Block CiphersXiaolu Hou0Jakub Breier1Fuyuan Zhang2Yang Liu3AcronisSchool of Computer Science and Engineeering, Nanyang Technological UniversitySchool of Computer Science and Engineeering, Nanyang Technological UniversitySchool of Computer Science and Engineeering, Nanyang Technological UniversityDifferential Fault Analysis (DFA) is considered as the most popular fault analysis method. While there are techniques that provide a fault analysis automation on the cipher level to some degree, it can be shown that when it comes to software implementations, there are new vulnerabilities, which cannot be found by observing the cipher design specification. This work bridges the gap by providing a fully automated way to carry out DFA on assembly implementations of symmetric block ciphers. We use a customized data flow graph to represent the program and develop a novel fault analysis methodology to capture the program behavior under faults. We establish an effective description of DFA as constraints that are passed to an SMT solver. We create a tool that takes assembly code as input, analyzes the dependencies among instructions, automatically attacks vulnerable instructions using SMT solver and outputs the attack details that recover the last round key (and possibly the earlier keys). We support our design with evaluations on lightweight ciphers SIMON, SPECK, and PRIDE, and a current NIST standard, AES. By automated assembly analysis, we were able to find new efficient DFA attacks on SPECK and PRIDE, exploiting implementation specific vulnerabilities, and previously published DFA on SIMON and AES. Moreover, we present a novel DFA on multiplication operation that has never been shown for symmetric block ciphers before. Our experimental evaluation also shows reasonable execution times that are scalable to current cipher designs and can easily outclass the manual analysis. Moreover, we present a method to check the countermeasure-protected implementations in a way that helps implementers to decide how many rounds should be protected. We note that this is the first work that automatically carries out DFA on cipher implementations without any plaintext or ciphertext information and therefore, can be generally applied to any input data to the cipher.https://tches.iacr.org/index.php/TCHES/article/view/8286differential fault analysisfault attacksautomationassembly |
| spellingShingle | Xiaolu Hou Jakub Breier Fuyuan Zhang Yang Liu Fully Automated Differential Fault Analysis on Software Implementations of Block Ciphers Transactions on Cryptographic Hardware and Embedded Systems differential fault analysis fault attacks automation assembly |
| title | Fully Automated Differential Fault Analysis on Software Implementations of Block Ciphers |
| title_full | Fully Automated Differential Fault Analysis on Software Implementations of Block Ciphers |
| title_fullStr | Fully Automated Differential Fault Analysis on Software Implementations of Block Ciphers |
| title_full_unstemmed | Fully Automated Differential Fault Analysis on Software Implementations of Block Ciphers |
| title_short | Fully Automated Differential Fault Analysis on Software Implementations of Block Ciphers |
| title_sort | fully automated differential fault analysis on software implementations of block ciphers |
| topic | differential fault analysis fault attacks automation assembly |
| url | https://tches.iacr.org/index.php/TCHES/article/view/8286 |
| work_keys_str_mv | AT xiaoluhou fullyautomateddifferentialfaultanalysisonsoftwareimplementationsofblockciphers AT jakubbreier fullyautomateddifferentialfaultanalysisonsoftwareimplementationsofblockciphers AT fuyuanzhang fullyautomateddifferentialfaultanalysisonsoftwareimplementationsofblockciphers AT yangliu fullyautomateddifferentialfaultanalysisonsoftwareimplementationsofblockciphers |