In this paper, we present a new and yet unforeseen side channel attack that is enabled by the recently published Simple Branch Prediction Analysis (SBPA) which is another type of MicroArchitectural Analysis. We show that modular inversion --- a critical primitive in public key cryptography --- is a natural target of SBPA attacks because it typically uses the Binary Extended Euclidean algorithm whose nature is an input-centric sequence of conditional branches. Our results show that SBPA can be used to extract secret parameters during the execution of the Binary Extended Euclidean algorithm. This poses a new potential risk to crypto-applications such as OpenSSL, which already employs Cache Attack countermeasures. Thus, it is necessary to develop new software mitigation techniques for BPA and incorporate them with cache analysis countermeasures in security applications.
To mitigate this new risk in full generality, we apply a security-aware algorithm design methodology and propose some changes to the CRT-RSA algorithm flow. These changes either avoid some of the steps that require modular inversion, or remove the critical information leak from this procedure.
In addition, we also show by example that, independently of the required changes in the algorithms, careful software analysis is also required in order to assure that the software implementation does not inadvertently introduce branches that may expose the application to SBPA attacks.
These offer several simple ways for modifying OpenSSL in order to mitigate Branch Prediction Attacks.Category / Keywords: implementation / Side channel attacks, branch prediction attacks, cache eviction attacks, Binary Extended Euclidean, Algorithm, modular inversion, software mitigation methods, OpenSSL, RSA, CRT. Date: received 6 Feb 2007 Contact author: jeanpierreseifert at yahoo com Available format(s): PDF | BibTeX Citation Version: 20070214:103630 (All versions of this report) Short URL: ia.cr/2007/039 Discussion forum: Show discussion | Start new discussion