Inspector Deep Learning breaks protected RSA and ECC implementations
Already, the deep learning approach shows strong results against block ciphers, bypassing such countermeasures as trace misalignment and first-order masking. Even when public-key crypto implementations incorporate strong countermeasures, deep learning proves to be a promising attack method to recover sensitive information from a target. One of the major updates of the upcoming Inspector version will be an enhanced Deep Learning module with the ability to test the resilience of public-key cryptography algorithms.
Inspector 2018.2 is planned for early May, and will provide numerous additions to the Deep Learning module. Support for public-key crypto algorithms is one of the most eye-catching features. This Deep Learning attack works in a supervised setting, where the training set is a trace set labelled according to the private key. This requires knowledge of the type of modular exponentiation (RSA) or scalar multiplication (ECC) implementation as well as some security parameters adopted for the countermeasures. The test phase, which is applied to another and identical target, does not require knowledge about these security parameters.
Tests conducted by Riscure show that with the Inspector Deep Learning the protected RSA and ECC implementations can be broken even when the processed traces are not aligned, which in most cases is considered to be a sufficient countermeasure to prevent template attacks or horizontal attacks. The keys were recovered with 100% accuracy in scenarios without misalignment and with 99.5% in scenarios where misalignment was present. But even with a few error bits in the recovered private key, a brute-force attack using special key enumeration algorithms can complete full key recovery in a reasonable time.
This testing technology is especially recommended for developers who want to verify the occurrence of leakages in their designs, even when several countermeasures are implemented. Watch out for more news on our research progress and the upcoming features of the second Inspector release of 2018!
Background: Public key characteristics
Public-key cryptography makes use of specific protocols for key generation, digital signature and key exchange. The main operations within these protocols are binary algorithms where a private key defines the sequence of mathematical operations using long integers. For RSA and ECC-based protocols, modular exponentiation and scalar multiplication, respectively, perform this loop operation. For every bit of the exponent or the scalar, the algorithm performs a mathematical operation (modular multiplication/modular squaring for RSA or point addition/point doubling for ECC). If an attacker, by analyzing side-channel traces, can differentiate which operation is performed for every bit, he/she can also recover the private key.
Different countermeasures at an algorithmic level have been implemented on RSA and ECC designs. Regular, branchless and constant-time modular exponentiation and scalar multiplication algorithms prevent the application SPA attacks. Private key randomization is used to defeat DPA attacks. Finally, message masking increases the resilience of the implementation against chosen-message attacks. Horizontal and template attacks are still applicable even when those countermeasures are implemented. However, these two side-channel methods are very sensitive to misalignment and clock jittering effects. The developing Deep Learning approach to side channel analysis improves the efficiency of an attack in these complex situations, which ultimately allows our customers to achieve more robust cryptography implementations.