## CryptoDB

### Jean-Pierre Seifert

#### Publications

**Year**

**Venue**

**Title**

2020

TCHES

Splitting the Interpose PUF: A Novel Modeling Attack Strategy
📺
Abstract

We demonstrate that the Interpose PUF proposed at CHES 2019, an Arbiter PUF-based design for so-called Strong Physical Unclonable Functions (PUFs), can be modeled by novel machine learning strategies up to very substantial sizes and complexities. Our attacks require in the most difficult cases considerable, but realistic, numbers of CRPs, while consuming only moderate computation times, ranging from few seconds to few days. The attacks build on a new divide-and-conquer approach that allows us to model the two building blocks of the Interpose PUF separately. For non-reliability based Machine Learning (ML) attacks, this eventually leads to attack times on (kup, kdown)-Interpose PUFs that are comparable to the ones against max{kup, kdown}-XOR Arbiter PUFs, refuting the original claim that Interpose PUFs could provide security similar to (kdown + kup/2)-XOR Arbiter PUFs (CHES 2019). On the technical side, our novel divide-and-conquer technique might also be useful in analyzing other designs, where XOR Arbiter PUF challenge bits are unknown to the attacker.

2018

TCHES

Key Extraction Using Thermal Laser Stimulation A Case Study on Xilinx Ultrascale FPGAs
Abstract

Thermal laser stimulation (TLS) is a failure analysis technique, which can be deployed by an adversary to localize and read out stored secrets in the SRAM of a chip. To this date, a few proof-of-concept experiments based on TLS or similar approaches have been reported in the literature, which do not reflect a real attack scenario. Therefore, it is still questionable whether this attack technique is applicable to modern ICs equipped with side-channel countermeasures. The primary aim of this work is to assess the feasibility of launching a TLS attack against a device with robust security features. To this end, we select a modern FPGA, and more specifically, its key memory, the so-called battery-backed SRAM (BBRAM), as a target. We demonstrate that an attacker is able to extract the stored 256-bit AES key used for the decryption of the FPGA’s bitstream, by conducting just a single non-invasive measurement. Moreover, it becomes evident that conventional countermeasures are incapable of preventing our attack since the FPGA is turned off during key recovery. Based on our time measurements, the required effort to develop the attack is shown to be less than 7 hours. To avert this powerful attack, we propose a low-cost and CMOS compatible countermeasure circuit, which is capable of protecting the BBRAM from TLS attempts even when the FPGA is powered off. Using a proof-of-concept prototype of our countermeasure, we demonstrate its effectiveness against TLS key extraction attempts.

2012

CHES

2007

EPRINT

New Branch Prediction Vulnerabilities in OpenSSL and Necessary Software Countermeasures
Abstract

Software based side-channel attacks allow an unprivileged spy
process to extract secret information from a victim
(cryptosystem) process by exploiting some indirect leakage of
``side-channel'' information. It has been realized that some
components of modern computer microarchitectures leak certain
side-channel information and can create unforeseen security
risks. An example of such MicroArchitectural Side-Channel
Analysis is the Cache Attack --- a group of attacks that exploit
information leaks from cache latencies.
Public awareness of Cache Attack vulnerabilities lead software
writers of OpenSSL (version 0.9.8a and subsequent versions) to
incorporate countermeasures for preventing these attacks.
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.

2006

EPRINT

Software mitigations to hedge AES against cache-based software side channel vulnerabilities
Abstract

Hardware side channel vulnerabilities have been studied for many
years in embedded silicon-security arena including SmartCards,
SetTop-boxes, etc. However, because various recent security
activities
have goals of improving the software isolation properties of PC
platforms, software side channels have become a subject of
interest. Recent publications
discussed cache-based software side channel vulnerabilities of AES
and RSA. Thus, following the classical approach --- a new side
channel vulnerability opens a new mitigation research path
--- this paper starts to investigate efficient mitigations to
protect AES-software against side channel vulnerabilities. First,
we will present several mitigation strategies to harden existing
AES software against cache-based software side channel attacks and
analyze their theoretical protection. Then, we will present a
%thorough
performance and security evaluation of our mitigation strategies.
For ease of evaluation we measured the performance of our code
against the performance of the openSSL AES implementation. In
addition, we also analyzed our code under various existing
attacks.
Depending on the level of the
required side channel protection, the measured performance loss of
our mitigations strategies versus openSSL (respectively best assembler) varies
between factors of 1.35 (2.66) and 2.85 (5.83).

2006

EPRINT

Predicting Secret Keys via Branch Prediction
Abstract

This paper presents a new software side-channel attack - enabled by the branch prediction capability common to all modern high-performance CPUs. The penalty payed (extra clock cycles) for a mispredicted branch can be used for cryptanalysis of cryptographic primitives that employ a data-dependent program flow. Analogous to the recently described cache-based side-channel attacks our attacks also allow an unprivileged process to attack other processes
running in parallel on the same processor, despite sophisticated partitioning methods such as memory protection, sandboxing or even virtualization. We will discuss in detail several such attacks for the example of RSA, and experimentally show their applicability to real systems, such as OpenSSL and Linux. More specifically, we will present four different types of attacks, which are all derived from the basic idea underlying our novel side-channel attack. Moreover,
we also demonstrate the strength of the branch prediction side-channel attack by rendering the obvious countermeasure in this context (Montgomery Multiplication with dummy-reduction) as useless. Although the deeper consequences of the latter result make the task of writing an efficient and secure modular expeonentiation (or scalar multiplication on an elliptic curve) a challenging task, we will eventually suggest some countermeasures to mitigate branch prediction
side-channel attacks.

2006

EPRINT

On the Power of Simple Branch Prediction Analysis
Abstract

Very recently, a new software side-channel attack, called Branch Prediction Analysis (BPA) attack, has been discovered and also demonstrated to be practically feasible on popular commodity PC platforms. While the above recent attack still had the flavor of a classical timing attack against RSA, where one uses many execution-time measurements under the same key in order to statistically amplify some small but key-dependent timing differences, we dramatically improve upon the former result. We prove that a carefully written spy-process running simultaneously with an RSA-process, is able to collect during one \emph{single} RSA signing execution almost all of the secret key bits. We call such an attack, analyzing the CPU's Branch Predictor states through spying on a single quasi-parallel computation process, a \emph{Simple Branch Prediction Analysis (SBPA)} attack --- sharply differentiating it from those one relying on statistical methods and requiring many
computation measurements under the same key. The successful extraction of almost all secret key bits by our SBPA attack against an openSSL RSA implementation proves that the often recommended blinding or so called randomization techniques to protect RSA
against side-channel attacks are, in the context of SBPA attacks, totally useless. Additional to that very crucial security implication, targeted at such implementations which are assumed to be
at least statistically secure, our successful SBPA attack also bears another equally critical security implication. Namely, in the context of simple side-channel attacks, it is widely believed that equally balancing the operations after branches is a secure countermeasure against such simple attacks. Unfortunately, this is not true, as even such ``balanced branch'' implementations can be completely broken by our SBPA attacks. Moreover, despite sophisticated hardware-assisted partitioning methods such as memory
protection, sandboxing or even virtualization, SBPA attacks empower an unprivileged process to successfully attack other processes running in parallel on the same processor. Thus, we conclude that SBPA attacks are much more dangerous than previously anticipated,
as they obviously do not belong to the same category as pure timing attacks.

2005

EPRINT

Duality between Multiplication and Modular Reduction
Abstract

This paper presents a duality between the classical optimally speeded up multiplication algorithm
and some "fast" reduction algorithm.
For this, the multiplier is represented by the unique signed digit representation with minimal Hamming
weight using Reitwiesner's multiplier recoding algorithm.
In fact, the present paper proves that this optimal multiplier recoding technique naturally translates
into a canonical modular reduction technique.
The other direction is shown as well.
Thus, the resulting reduction algorithm is optimal with respect to its average-time complexity as well.
Besides these two new results, our proof of the transfer-theorem serves another interesting purpose:
The reason that the considered reduction algorithm from \cite{Sedlak} is so unknown
might lie in the fact that it is rather un-intuitive and no proper understanding was available so far.
Therefore, our proper mathematical derivation/explanation solves this lack of understanding.

2004

EPRINT

Sign Change Fault Attacks On Elliptic Curve Cryptosystems
Abstract

We present a new type of fault attacks on elliptic curve scalar
multiplications: Sign Change Attacks. These attacks exploit different number representations as they are often employed in modern cryptographic applications. Previously, fault attacks on elliptic curves aimed to force a device to output points which are on a cryptographically weak curve. Such attacks can easily be defended against. Our attack produces points which do not leave the curve and are not easily detected. The paper also presents a revised scalar multiplication algorithm that provably protects against Sign Change Attacks.

2002

EPRINT

Parallel scalar multiplication on general elliptic curves over $\mathbb{F}_p$ hedged against Non-Differential Side-Channel Attacks
Abstract

For speeding up elliptic curve scalar multiplication and making it secure against side-channel attacks such as timing or power analysis, various
methods have been proposed using specifically chosen elliptic curves. We show that both goals can be achieved simultaneously even for conventional
elliptic curves over $\mathbb{F}_p$. This result is shown via two facts.
First, we recall the known fact that every elliptic curve over $\mathbb{F}_p$ admits a scalar
multiplication via a (Montgomery ladder) Lucas chain.
As such chains are known to be resistant against timing- and simple power/electromagnetic
radiation analysis attacks, the security of our scalar multiplication against timing and
simple power/electromagnetic radiation analysis follows.
Second, we show how to parallelize the 19 multiplications within the resulting
\lq\lq double" and \lq\lq add" formulas of the Lucas chain for the
scalar multiplication.
This parallelism together with the Lucas chain results in 10 parallel field multiplications per bit of the scalar.
Finally, we also report on a concrete successful implementation of the above mentioned scalar multiplication algorithm
on a very recently developed and commercially available coprocessor for smart cards.

2002

EPRINT

Fault attacks on RSA with CRT: Concrete Results and Practical Countermeasures
Abstract

This article describes concrete results and practically approved countermeasures concerning differential fault attacks
on RSA using the CRT. It especially investigates smartcards with a RSA coprocessor where any hardware countermeasure to
defeat such fault attacks have been switched off.
This scenario has been chosen in order to completely analyze the resulting effects
and errors occurring inside the hardware. Using the results of this kind of physical
stress attack enables the development of completely reliable software countermeasures.
Although {\em successful\/} RSA attacks on the investigated hardware have been only possible with an expensive enhanced
laboratory equipment, the effects on the unprotected hardware have been tremendously. This caused lots of analysis efforts to
investigate what really happened during the attack. Indeed, this will be addressed in this paper.
We first report on the nature of the resulting errors within the hardware due to the physical stress applied to the
smartcard. Hereafter, we describe the experiments and results with a very efficient and prominent software RSA-CRT DFA
countermeasure. This method could be shown to be insufficient, i.e., detected nearly no error, when we introduced
stress at the right position during the computation.
Naturally, a detailed error analysis model followed, specifying every failure point during the RSA-CRT operation.
This model finally allowed to develop and present here new very practically oriented software countermeasures hedging
the observed and characterized fault attacks.
Eventually, we present the security analysis of our new developed software RSA-CRT DFA countermeasures.
Thanks to their careful specification according to the observed and analyzed errors they resisted all kinds of physical
stress attacks and were able to detect any subtle computation error, thus avoiding to break the smartcard by fault attacks.
Nevertheless, we stress, that although our software countermeasures have been fully approved by practical experiments,
we are convinced that only sophisticated hardware countermeasures like sensors and filters in combination with
software countermeasures will be able to provide a secure and comfortable base to defeat in general any conceivable
fault attacks scenario on smartcards properly.

2002

EPRINT

Fault based cryptanalysis of the Advanced Encryption Standard
Abstract

In this paper we describe several fault attacks on the
Advanced Encryption Standard (AES).
First, using optical fault induction attacks as recently
publicly presented by Skorobogatov and Anderson \cite{SA}, we
present an implementation independent fault attack on AES.
This attack is able to determine the complete $128$-bit
secret key of a sealed tamper-proof smartcard by
generating $128$ faulty cipher texts.
Second, we present
several implementation-dependent fault attacks on AES.
These attacks
rely on the observation that due to the AES's known timing analysis
vulnerability (as pointed out by Koeune and Quisquater \cite{KQ}),
any implementation of the AES must ensure a data independent timing
behavior for the so called AES's {\tt xtime} operation. We present
fault attacks on AES based on various timing analysis resistant
implementations of the {\tt xtime}-operation.
Our strongest attack in this direction
uses a very liberal fault model and requires only $256$ faulty
encryptions to determine a $128$-bit key.

2000

EPRINT

Using fewer Qubits in Shor's Factorization Algorithm via Simultaneous Diophantine Approximation
Abstract

While quantum computers might speed up in principle
certain computations dramatically, in pratice, though
quantum computing technology is still in its infancy.
Even we cannot clearly envison at present what the
hardware of that machine will be like.
Nevertheless, we can be quite confident that it will be
much easier to build any practical quantum computer
operating on a few number of quantum bits rather than one operating
on a huge number of of quantum bits.
It is therefore of big practical impact to use the resource
of quantum bits very spare,
i.e., to find quantum algorithms which use as few as possible
quantum bits.
Here, we present a method to reduce the number of actually needed qubits
in Shor's algorithm to factor a composite number $N$.
Exploiting the inherent probabilism of quantum computation we are able to
substitute the continued fraction algorithm to find a certain unknown
fraction by a simultaneous Diophantine approximation.
While the continued fraction algorithm is able to find a Diophantine
approximation to a single known fraction with a denominator greater than
$N^2$, our simultaneous Diophantine approximation method computes in
polynomial time unusually good approximations to known fractions with a
denominator of size $N^{1+\varepsilon}$, where $\varepsilon$ is allowed to be
an arbitrarily small positive constant.
As these unusually good approximations are almost unique we are able to
recover an unknown denominator using fewer qubits in the quantum part of our
algorithm.

#### Program Committees

- CHES 2019
- CHES 2008
- CHES 2007
- CHES 2005
- CHES 2004
- CHES 2003

#### Coauthors

- Onur Aciiçmez (3)
- Christian Aumüller (2)
- Peter Bier (2)
- Johannes Blömer (3)
- Christian Boit (5)
- Ernest F. Brickell (1)
- Enrico Dietz (3)
- Helmar Dittrich (3)
- Fabian Fäßler (1)
- Wieland Fischer (5)
- Sven Frohmann (3)
- Fatemeh Ganji (2)
- Christophe Giraud (1)
- Gary Graunke (1)
- Shay Gueron (1)
- Peter Günther (1)
- Clemens Helfmeier (3)
- Peter Hofreiter (2)
- Heinz-Wilhelm Hübers (2)
- Erik Woodward Knudsen (1)
- Çetin Kaya Koç (2)
- Thilo Krachenfels (1)
- Juliane Krämer (2)
- Heiko Lohrke (2)
- Marian Margraf (1)
- Christopher Mühl (1)
- Dmitry Nedospasov (4)
- Michael Neve (1)
- Phuong Ha Nguyen (1)
- Susanna Orlic (1)
- Martin Otto (1)
- Niklas Pirnay (1)
- Ulrich Rührmair (1)
- Alexander Schlösser (1)
- Ricardo Gomes da Silva (1)
- Shahin Tajik (7)
- Marten van Dijk (1)
- Nils Wisiol (1)