Defend encryption systems against side-channel attacks
From its ancient origin as a tool for protecting sensitive wartime or espionage-related messages, cryptography has become a foundational building-block for securing the systems, protocols, and infrastructure that underpin our modern interconnected world. But the physical mechanisms used in performing encryption and decryption can leak information, making it possible to bypass this security. Protecting designs against such side-channel attacks starts with understanding how such attacks operate.
At its very essence, cryptography is a branch of mathematics dealing with efficiently computable transforms that convert inputs to outputs using additional data known as a cryptographic key. These transforms have the property that, despite observing many input/output pairs, it remains infeasible to compute or invert the transform without the knowledge of the key.
An example of a cryptographic transformation is the symmetric-key based Advanced Encryption Standard (AES-256). An AES-256 encryption device that has access to a 256-bit secret cryptographic key, can transform any sensitive message - known as plaintext - into an unintelligible form known as the ciphertext. Anyone observing the ciphertext, without knowing the plaintext or the key, cannot recover the plaintext or the key. Further, even an observer who knows or can choose the plaintext and can observe the corresponding ciphertext can still not recover the secret key being using within the encryption device. However, any AES decryption device that has access to the same 256-bit secret key as the encrypting device, can readily recover the plaintext from the ciphertext.
Another example of a cryptographic transformation is a public-key based RSA (Rivest-Shamir-Adelman) digital signature algorithm. This algorithm uses pairs of cryptographic keys consisting of a non-secret public key and a secret private key. A signing device that has access to a secret private key can attach a "tag" or digital signature to any message. This RSA signature has the property that without knowledge of the private key, it is infeasible to calculate the digital signature to a message. Anyone who receives a message with a digital signature on that message can use the corresponding public key to establish the authenticity of the message by verifying that the digital signature corresponds to that message.
Strong mathematical guarantees make cryptographic primitives (established, low-level cryptographic algorithms) highly popular as building blocks for securing systems and infrastructure. Encryption is widely deployed to protect confidential data during storage or transmission over insecure networks. Digital signatures are widely used for validating the authenticity and integrity of software, software updates and the data that systems rely upon. Other cryptographic primitives such as message authentication codes, key agreement protocols, and hash functions are also widely deployed for protecting information and systems from attacks.
However, successful attacks on fielded cryptographic systems have also highlighted the pitfalls of relying on purely mathematical guarantees for securing physical systems. It may be infeasible to extract keys mathematically from message traffic, but monitoring message traffic is only one of many possible approaches to breaking encryption.
One common attack vector is exploiting deficiencies in protecting secret cryptographic keying material. Real world systems need to be carefully designed so that secret keys cannot be easily recovered by malicious software or via a simple hardware attack. Unfortunately, incidents where systems get compromised due to poorly protected secret keys are still common.
Another source of problems has been poor communication between the cryptographers, who are mostly mathematicians, and the engineering community that actually develops these systems. If cryptographers do not properly convey all the requirements needed for the mathematical proofs of security - such as the non-reuse of certain parameters or the quality of certain random inputs to the system designers, the resulting implementations may be vulnerable to a mathematical attack. For example, hackers were able to recover the digital signature key used for signing code for the Sony PlayStation 3 because designers reused a once-per-signature parameter across multiple signatures.
Even if a system protects keying material and meets all the mathematical requirements of the security proofs, there is a class of attacks on all cryptographic implementations that can easily and non-invasively recover secret keys from a system. These attacks, known as side-channel attacks, rely on the fact that any physical realization of cryptography in hardware or software cannot be an atomic black-box transform as assumed by the mathematical proofs of security. A physical system must necessarily leak information about the process of computing the transform into the environment.
Examples of this "side-channel" information include the time taken by the cryptographic operation, the power consumption, EM and heat emissions of the cryptographic device while computing the transform, and the like, all of which depend on the physical details of the implementation. Depending on proximity, an attacker could gather some of this side-channel information and use it to recover the secret cryptographic key. While remote attackers may only be able to get low-bandwidth information such as the approximate time taken by the cryptographic calculations, attackers in closer proximity may be able to collect much higher bandwidth channels, such as the power consumption profile or the EM emissions profile of the device.
Once an attacker has collected side-channel data for a cryptographic computation, there are two classes of attacks that can be mounted using the collected data to recover the key. The first class of attacks, known as simple side-channel analysis, recovers the secret key from the side-channel data collected during a single cryptographic transaction. Simple side-channel attacks are more commonly applicable to public-key cryptography-based systems such as RSA.
In this case, the cryptographic calculation consists of a key-dependent sequence of operations. Because each type of operation is likely to have a unique power or EM profile, examining a device's power consumption or EM emission profile while it is performing the RSA operation typically reveals the sequence of operations the device performed. The secret key can then be easily reconstructed from this operation sequence.
Attacks of the second class, known as differential side-channel analysis, are typically applicable to symmetric key based algorithms such as AES as well as in situations where the collected side-channel data is very noisy or of otherwise poor quality. This style of attack uses statistical hypothesis testing on side-channel data across multiple cryptographic transactions to recover the secret key, piece-by-piece.
The basic concept behind differential side-channel analysis is that side-channel leakage from power, EM, or timing correlates to the cryptographic activity occurring within the device. It even correlates to individual subactivities occurring in the device that depend only on small portions of the key and known data such as inputs or outputs. But other subactivities occurring within the device as well as the noise from the measurement process are all uncorrelated to the targeted subactivity.
This correlation means that an attacker can guess the value for a portion of the key and predict the resulting target subactivity for each transaction. The attacker can then use a correlation calculation between predicted subactivity and side-channel data to verify whether the key guess is correct. Incorrect key portion guesses will show no correlation between predicted subactivity and the side-channel traces, whereas the correct key guess will show a statistically significant correlation. These statistical techniques are so powerful that, with sufficient data, subactivity corresponding to a single transistor switching could be utilized for an attack.
Continue reading the next page of this article on Embedded's sister site, EDN: "Defend encryption systems against side-channel attacks."
Join over 2,000 technical professionals and embedded systems hardware, software, and firmware developers at ESC Boston May 6-7, 2015, and learn about the latest techniques and tips for reducing time, cost, and complexity in the development process.
Passes for the ESC Boston 2015 Technical Conference are available at the conference's official site, with discounted advance pricing until May 1, 2015. Make sure to follow updates about ESC Boston's other talks, programs, and announcements via the Destination ESC blog on Embedded.com and social media accounts Twitter, Facebook, LinkedIn, and Google+.
The Embedded Systems Conference, EE Times, and Embedded.com are owned by UBM Canon.