Automated Side-Channel Vulnerability Discovery and Hardening

In traditional cryptography, an attacker tries to infer a mathematical relationship between the inputs and outputs of a cryptosystem to recover secret information. With the advances in the theoretical basis of the cryptographic algorithms, this task became harder and attackers started to seek different approaches. A family of attacks known as side-channel attacks have focused on using information leaked through the underlying device when the cryptographic algorithm is running. For instance, a power analysis attack can exploit the relationship between the inputs of a cryptosystem and the underlying device’s power consumption while performing cryptographic operations on these inputs. Such attacks have shown to be so successful and efficient in practice that prudent designers now insert countermeasures against these attacks to their hardware and software systems. However, the insertion process is challenging to a non-expert in cryptography due to several factors including unnatural structure of the countermeasures (e.g., obfuscating the implementation), use of non-standard elements in the design (e.g., using non-CMOS logic styles), conflict with standard design parameters and the optimization processes of design tools (e.g., adding dummy operations, which are normally eliminated by the design tools to increase performance), etc. To facilitate a reliably-secure design process, this thesis proposes automated methodologies which analyze a given hardware or software cryptosystem and insert appropriate side-channel countermeasures. We first propose one type of hardware countermeasure and show how it can easily be integrated into the standard electronic design automation flow to protect high-level hardware implementations. The countermeasure is based on adding random jitter to the clocks of sequential circuit elements, and incurs a modest area and energy overhead. Next, we propose a hardware extension unit, an instruction shuffler, to existing processors. The unit is very lightweight and does not require any architectural changes, and hence can be used with any processor, increasing the side-channel resistance of the overall system. We then present a compiler, which can easily be combined with the off-the-shelf compilers, to automatically apply countermeasures on given software implementations. We show that the compiler can produce protected implementations that are as efficient as their manually optimized counterparts, eliminating the need for designer expertise and time. Finally, we present an automated security verification methodology, which checks certain properties to detect potential vulnerabilities in a (manually or automatically) protected implementation. Our experiments show that we can successfully detect common security problems in a flawed implementation of a countermeasure within a reasonable amount of time.