TY - JOUR
T1 - Satisfiability-based framework for enabling side-channel attacks on cryptographic software
AU - Potlapally, Nachiketh R.
AU - Raghunathan, Anand
AU - Ravi, Srivaths
AU - Jha, Niraj K.
AU - Lee, Ruby B.
PY - 2006/12/1
Y1 - 2006/12/1
N2 - Many electronic systems contain implementations of cryptographic algorithms in order to provide security. It is well known that cryptographic algorithms, irrespective of their theoretical strength, can be broken through weaknesses in their implementation. In particular, side-channel attacks, which exploit unintended information leakage from the implementation, have been established as a powerful way of attacking cryptographic systems. All side-channel attacks can be viewed as consisting of two phases - an observation phase, wherein information is gathered from the target system, and an analysis or deduction phase in which the collected information is used to infer the cryptographic key. Thus far, most side-channel attacks have focused on extracting information that directly reveals the key, or variables from which the key can be easily deduced. We propose a new framework for performing side-channel attacks by formulating the analysis phase as a search problem that can be solved using modern Boolean analysis techniques such as satisfiability solvers. This approach can substantially enhance the scope of side-channel attacks by allowing a potentially wide range of internal variables to be exploited (not just those that are "simply" related to the key). For example, software implementations take great care in protecting secret keys through the use of onchip key generation and storage. However, they may inadvertently expose the values of intermediate variables in their computations. We demonstrate how to perform side-channel attacks on software implementations of cryptographic algorithms based on the use of a satisfiability solver for reasoning about the secret keys from the values of the exposed variables. Our attack technique is automated, and does not require mathematical expertise on the part of the attacker. We demonstrate the merit of the proposed technique by successfully applying it to two popular cryptographic algorithms, DES and 3DES.
AB - Many electronic systems contain implementations of cryptographic algorithms in order to provide security. It is well known that cryptographic algorithms, irrespective of their theoretical strength, can be broken through weaknesses in their implementation. In particular, side-channel attacks, which exploit unintended information leakage from the implementation, have been established as a powerful way of attacking cryptographic systems. All side-channel attacks can be viewed as consisting of two phases - an observation phase, wherein information is gathered from the target system, and an analysis or deduction phase in which the collected information is used to infer the cryptographic key. Thus far, most side-channel attacks have focused on extracting information that directly reveals the key, or variables from which the key can be easily deduced. We propose a new framework for performing side-channel attacks by formulating the analysis phase as a search problem that can be solved using modern Boolean analysis techniques such as satisfiability solvers. This approach can substantially enhance the scope of side-channel attacks by allowing a potentially wide range of internal variables to be exploited (not just those that are "simply" related to the key). For example, software implementations take great care in protecting secret keys through the use of onchip key generation and storage. However, they may inadvertently expose the values of intermediate variables in their computations. We demonstrate how to perform side-channel attacks on software implementations of cryptographic algorithms based on the use of a satisfiability solver for reasoning about the secret keys from the values of the exposed variables. Our attack technique is automated, and does not require mathematical expertise on the part of the attacker. We demonstrate the merit of the proposed technique by successfully applying it to two popular cryptographic algorithms, DES and 3DES.
UR - http://www.scopus.com/inward/record.url?scp=34047141132&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=34047141132&partnerID=8YFLogxK
M3 - Conference article
AN - SCOPUS:34047141132
VL - 2
JO - Proceedings -Design, Automation and Test in Europe, DATE
JF - Proceedings -Design, Automation and Test in Europe, DATE
SN - 1530-1591
M1 - 1657108
T2 - Design, Automation and Test in Europe, DATE'06
Y2 - 6 March 2006 through 10 March 2006
ER -