International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Christof Paar

Affiliation: Ruhr-Universitaet Bochum

Publications

Year
Venue
Title
2018
TCHES
Stealthy Opaque Predicates in Hardware - Obfuscating Constant Expressions at Negligible Overhead 📺
Max Hoffmann Christof Paar
Opaque predicates are a well-established fundamental building block for software obfuscation. Simplified, an opaque predicate implements an expression that provides constant Boolean output, but appears to have dynamic behavior for static analysis. Even though there has been extensive research regarding opaque predicates in software, techniques for opaque predicates in hardware are barely explored. In this work, we propose a novel technique to instantiate opaque predicates in hardware, such that they (1) are resource-efficient, and (2) are challenging to reverse engineer even with dynamic analysis capabilities. We demonstrate the applicability of opaque predicates in hardware for both, protection of intellectual property and obfuscation of cryptographic hardware Trojans. Our results show that we are able to implement stealthy opaque predicates in hardware with minimal overhead in area and no impact on latency.
2018
TCHES
On the Difficulty of FSM-based Hardware Obfuscation
In today’s Integrated Circuit (IC) production chains, a designer’s valuable Intellectual Property (IP) is transparent to diverse stakeholders and thus inevitably prone to piracy. To protect against this threat, numerous defenses based on the obfuscation of a circuit’s control path, i.e. Finite State Machine (FSM), have been proposed and are commonly believed to be secure. However, the security of these sequential obfuscation schemes is doubtful since realistic capabilities of reverse engineering and subsequent manipulation are commonly neglected in the security analysis. The contribution of our work is threefold: First, we demonstrate how high-level control path information can be automatically extracted from third-party, gate-level netlists. To this end, we extend state-of-the-art reverse engineering algorithms to deal with Field Programmable Gate Array (FPGA) gate-level netlists equipped with FSM obfuscation. Second, on the basis of realistic reverse engineering capabilities we carefully review the security of state-of-the-art FSM obfuscation schemes. We reveal several generic strategies that bypass allegedly secure FSM obfuscation schemes and we practically demonstrate our attacks for a several of hardware designs, including cryptographic IP cores. Third, we present the design and implementation of Hardware Nanomites, a novel obfuscation scheme based on partial dynamic reconfiguration that generically mitigates existing algorithmic reverse engineering.
2017
ASIACRYPT
2016
CHES
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
CHES
2014
CRYPTO
2014
EPRINT
2013
CRYPTO
2013
CHES
2012
ASIACRYPT
2012
FSE
2011
EUROCRYPT
2011
CHES
2011
CHES
2011
ASIACRYPT
2011
JOFC
2009
CHES
2009
CHES
2009
CHES
2008
CHES
2008
CHES
2008
CRYPTO
2008
EPRINT
Physical Cryptanalysis of KeeLoq Code Hopping Applications
KeeLoq remote keyless entry systems are widely used for access control purposes such as garage door openers for car anti-theft systems. We present the first successful differential power analysis attacks on numerous commercially available products employing KeeLoq code hopping. Our new techniques combine side-channel cryptanalysis with specific properties of the KeeLoq algorithm. They allow for efficiently revealing both the secret key of a remote transmitter and the manufacturer key stored in a receiver. As a result, a remote control can be cloned from only ten power traces, allowing for a practical key recovery in few minutes. Once knowing the manufacturer key, we demonstrate how to disclose the secret key of a remote control and replicate it from a distance, just by eavesdropping at most two messages. This key-cloning without physical access to the device has serious real-world security implications. Finally, we mount a denial-of-service attack on a KeeLoq access control system. All the proposed attacks have been verified on several commercial KeeLoq products.
2008
EPRINT
Information Leakage of Flip-Flops in DPA-Resistant Logic Styles
This contribution discusses the information leakage of flip-flops for different DPA-resistant logic styles. We show that many of the proposed side-channel resistant logic styles still employ flip-flops that leak data-dependent information. Furthermore, we apply simple models for the leakage of masked flip-flops to design a new attack on circuits implemented using masked logic styles. Contrary to previous attacks on masked logic styles, our attack does not predict the mask bit and does not need detailed knowledge about the attacked device, e.g., the circuit layout. Moreover, our attack works even if all the load capacitances of the complementary logic signals are perfectly balanced and even if the PRNG is ideally unbiased. Finally, after performing the attack on DRSL, MDPL, and iMDPL circuits we show that single-bit masks do not influence the exploitability of the revealed leakage of the masked flip-flops.
2007
CHES
2007
CHES
2007
FSE
2006
CHES
2006
CHES
2006
EPRINT
Generalizations of the Karatsuba Algorithm for Efficient Implementations
André Weimerskirch Christof Paar
In this work we generalize the classical Karatsuba Algorithm (KA) for polynomial multiplication to (i) polynomials of arbitrary degree and (ii) recursive use. We determine exact complexity expressions for the KA and focus on how to use it with the least number of operations. We develop a rule for the optimum order of steps if the KA is used recursively. We show how the usage of dummy coefficients may improve performance. Finally we provide detailed information on how to use the KA with least cost, and also provide tables that describe the best possible usage of the KA for polynomials up to a degree of 127. Our results are especially useful for efficient implementations of cryptographic and coding schemes over fixed-size fields like $GF(p^m)$.
2005
CHES
2005
CHES
2004
CHES
2004
CHES
2004
EPRINT
Finding Optimum Parallel Coprocessor Design for Genus 2 Hyperelliptic Curve Cryptosystems
Hardware accelerators are often used in cryptographic applications for speeding up the highly arithmetic-intensive public-key primitives, e.g. in high-end smart cards. One of these emerging and very promising public-key scheme is based on HyperElliptic Curve Cryptosystems (HECC). In the open literature only a few considerations deal with hardware implementation issues of HECC. Our contribution appears to be the first one to propose architectures for the latest findings in efficient group arithmetic on HEC. The group operation of HECC allows parallelization at different levels: bit-level parallelization (via different digit-sizes in multipliers) and arithmetic operation-level parallelization (via replicated multipliers). We investigate the trade-offs between both parallelization options and identify speed and time-area optimized configurations. We found that a coprocessor using a single multiplier (D = 8) instead of two or more is best suited. This coprocessor is able to compute group addition and doubling in 479 and 334 clock cycles, respectively. Providing more resources it is possible to achieve 288 and 248 clock cycles, respectively.
2003
CHES
2003
FSE
2003
EPRINT
Hyperelliptic Curve Cryptosystems: Closing the Performance Gap to Elliptic Curves (Update)
For most of the time since they were proposed, it was widely believed that hyperelliptic curve cryptosystems (HECC) carry a substantial performance penalty compared to elliptic curve cryptosystems (ECC) and are, thus, not too attractive for practical applications. Only quite recently improvements have been made, mainly restricted to curves of genus 2. The work at hand advances the state-of-the-art considerably in several aspects. First, we generalize and improve the closed formulae for the group operation of genus 3 for HEC defined over fields of characteristic two. For certain curves we achieve over 50% complexity improvement compared to the best previously published results. Second, we introduce a new complexity metric for ECC and HECC defined over characteristic two fields which allow performance comparisons of practical relevance. It can be shown that the HECC performance is in the range of the performance of an ECC; for specific parameters HECC can even possess a lower complexity than an ECC at the same security level. Third, we describe the first implementation of a HEC cryptosystem on an embedded (ARM7) processor. Since HEC are particularly attractive for constrained environments, such a case study should be of relevance.
2003
EPRINT
Low Cost Security: Explicit Formulae for Genus 4 Hyperelliptic Curves
Jan Pelzl Thomas Wollinger Christof Paar
It is widely believed that genus four hyperelliptic curve cryptosystems (HECC) are not attractive for practical applications because of their complexity compared to systems based on lower genera, especially elliptic curves. Our contribution shows that for low cost security applications genus-4 hyperelliptic curves (HEC) can outperform genus-2 HEC and that we can achieve a performance similar to genus-3 HEC. Furthermore our implementation results show that a genus-4 HECC is an alternative cryptosystem to systems based on elliptic curves. In the work at hand we present for the first time explicit formulae for genus-4 HEC, resulting in a 60% speed-up compared to the best published results. In addition we implemented genus-4 HECC on a Pentium4 and an ARM microprocessor. Our implementations on the ARM show that for genus four HECC are only a factor of 1.66 slower than genus-2 curves considering group order ~2^{190}. For the same group order ECC and genus-3 HECC are about a factor of 2 faster than genus-4 curves on the ARM. The two most surprising results are: 1) for low cost security application, namely considering an underlying group of order 2^{128}, HECC with genus 4 outperform genus-2 curves by a factor of 1.46 and has similar performance to genus-3 curves on the ARM and 2) when compared to genus-2 and genus-3, genus-4 HECC are better suited to embedded microprocessors than to general purpose processors.
2003
EPRINT
How Secure Are FPGAs in Cryptographic Applications?
Thomas Wollinger Christof Paar
The use of FPGAs for cryptographic applications is highly attractive for a variety of reasons but at the same time there are many open issues related to the general security of FPGAs. This contribution attempts to provide a state-of-the-art description of this topic. First, the advantages of reconfigurable hardware for cryptographic applications are discussed from a systems perspective. Second, potential security problems of FPGAs are described in detail, followed by a proposal of a some countermeasure. Third, a list of open research problems is provided. Even though there have been many contributions dealing with the algorithmic aspects of cryptographic schemes implemented on FPGAs, this contribution appears to be the first comprehensive treatment of system and security aspects.
2003
EPRINT
High Performance Arithmetic for Hyperelliptic Curve Cryptosystems of Genus Two
Jan Pelzl Thomas Wollinger Christof Paar
Nowadays, there exists a manifold variety of cryptographic applications: from low level embedded crypto implementations up to high end cryptographic engines for servers. The latter require a flexible implementation of a variety of cryptographic primitives in order to be capable of communicating with several clients. On the other hand, on the client it only requires an implementation of one specific algorithm with fixed parameters such as a fixed field size or fixed curve parameters if using ECC/ HECC. In particular for embedded environments like PDAs or mobile communication devices, fixing these parameters can be crucial regarding speed and power consumption. In this contribution, we propose a highly efficient algorithm for a hyperelliptic curve cryptosystem of genus two, well suited for these constraint devices. In recent years, a lot of effort was made to speed up arithmetic on genus-2 HEC. This work is based on the work of Lange and presents a major improvement of HECC arithmetic for curves defined over fields of characteristic two. We optimized the group doubling operation for certain types of genus-2 curves and we were able to reduce the number of required multiplications to a total of 9 multiplications. The saving in multiplications is 47% for the cost of one additional squaring. Thus, the efficiency of the whole cryptosystem was drastically increased.
2001
CHES
2001
PKC
2001
JOFC
2000
CHES
1998
CRYPTO
1997
CRYPTO
1997
EUROCRYPT

Program Committees

CHES 2015
CHES 2014
Crypto 2013
CHES 2013
CHES 2011
Eurocrypt 2011
CHES 2010
Crypto 2009
CHES 2009
CHES 2008
CHES 2007
CHES 2006
CHES 2005
CHES 2003 (Program chair)
CHES 2002 (Program chair)
CHES 2001 (Program chair)
CHES 2000 (Program chair)
CHES 1999 (Program chair)

Coauthors

Nils Albartus (1)
Martin R. Albrecht (2)
Daniel V. Bailey (2)
Georg T. Becker (2)
Guido Bertoni (1)
Rainer Blümel (1)
Sinan Böcker (1)
Andrey Bogdanov (2)
Julia Borghoff (1)
Luca Breveglieri (1)
Wayne P. Burleson (1)
Wayne Burleson (1)
Anne Canteaut (1)
Jonathan Déchelotte (1)
Itai Dinur (1)
Benedikt Driessen (3)
Michael Düll (1)
Thomas Eisenbarth (4)
Maik Ender (1)
Patrick Felke (1)
Jens Franke (1)
Jürgen Frinken (1)
Marc Fyrbiak (2)
Samaneh Ghandali (2)
Benedikt Gierlichs (1)
Andreas Gornik (1)
Jorge Guajardo (4)
Tim Güneysu (5)
Björn Haase (1)
Stefan Heyse (2)
Gesine Hinterwälder (1)
Max Hoffmann (1)
Daniel E. Holcomb (1)
Michael Hutter (1)
Markus Kasper (1)
Timo Kasper (3)
Elif Bilge Kavun (3)
Eike Kiltz (1)
Christian Kison (1)
Thorsten Kleinjung (1)
Miroslav Knezevic (1)
Lars R. Knudsen (2)
Philipp Koppe (1)
Uwe Krieger (1)
Sandeep S. Kumar (1)
Gregor Leander (8)
Kerstin Lemke-Rust (4)
Yang Li (1)
Lang Lin (1)
San Ling (1)
Vadim Lyubashevsky (1)
Oliver Mischke (1)
Amir Moradi (8)
Ventzislav Nikov (1)
Jürgen Oehm (1)
Kazuo Ohta (1)
Gerardo Orlando (2)
David Oswald (2)
Jan Pelzl (6)
Gerd Pfeiffer (1)
Krzysztof Pietrzak (1)
Axel Poschmann (5)
Christine Priplata (1)
Jean-Jacques Quisquater (1)
Christian Rechberger (1)
Francesco Regazzoni (1)
Matthew J. B. Robshaw (2)
Carsten Rolfes (1)
Peter Rombouts (1)
Kazuo Sakiyama (1)
Mahmoud Salmasizadeh (3)
Ana Helena Sánchez (1)
Falk Schellenberg (1)
Manfred Schimmler (1)
Werner Schindler (1)
Kai Schramm (4)
Peter Schwabe (1)
Yannick Seurin (2)
Mohammad T. Manzuri Shalmani (3)
Adi Shamir (1)
Pedro Soria-Rodriguez (1)
Colin Stahlke (1)
Daehyun Strobel (1)
Berk Sunar (1)
Pawel Swierczynski (1)
Russell Tessier (1)
Søren S. Thomsen (1)
C. Vikkelsoe (1)
Sebastian Wallat (1)
Huaxiong Wang (1)
André Weimerskirch (1)
Thomas J. Wollinger (7)
Tolga Yalçin (3)
Ralf Zimmermann (1)