Lorentz Center - Provable Security against Physical Attacks from 15 Feb 2010 through 19 Feb 2010
  Current Workshop  |   Overview   Back  |   Home   |   Search   |     

    Provable Security against Physical Attacks
    from 15 Feb 2010 through 19 Feb 2010







Yevgeniy Dodis

"Survey: Leakage Resilience and the Bounded Retrieval Model".


This survey discusses recent advances in the field of Leakage-Resilient Cryptography. This booming area is concerned with the design of  cryptographic primitives resistant to arbitraryside-channel attacks, where an attacker can repeatedly and adaptively learn information about the secret key, subject *only* to the constraint that the *overall amount* of such information is bounded by some parameter L. We start by surveying recent results in the so called Relative Leakage Model, where all the parameters of the system are allowed to depend on L, and the goal is to make L large relative to the length of the secret key. We conclude by showing how to extend the relative leakage results to the Bounded Retrieval Model (aka "Absolute Leakage Model''), where only the secret key length is allowed to be slightly larger than L, but all other system parameters (e.g., public-key, communication, etc.) are independent of the absolute value of L.





Stefan Dziembowski

On the "only computation leaks information" paradigm


The "only computation leaks information paradigm" for designing leakage-resilient cryptographic schemes was first formulated by Micali and Reyzin (TCC 2004).  Essentially, it postulates that only these parts of the memory that take part in the computation can leak information.  This assumption was later used by Dziembowski and

Pietrzak (FOCS 2008) and Pietrzak (Eurocrypt 2009) to construct leakage-resilient stream-ciphers, and by Faust et al (EUROCRYPT 2009) to construct leakage-resilient signature schemes. We will give a short introduction to this area, focusing on the work

of Dziembowski and Pietrzak.





Christophe Giraud

Practical Difficulties of Physical Attacks”


In this talk we'll firstly discuss the practical problems we face when securing embedded cryptosystem implementations against side-channel analysis. Indeed, even on very simple hardware architecture in which leakages are well identified, securing a very simple piece of code against first order SCA can be much more complex than expected. Secondly, we will discuss the pertinence of high order attacks in practice depending on the characteristics of the attacker and of the device. We'll show that in some cases, second order SCA can't unfortunately be used to validate the security of a device during an evaluation. Finally, we'll present how to quantify the impact of a successful attack by using the so-called JIL quotation. We'll see that such an attack can be tolerated as long as high potential attackers are not able to put it into practice.







Helena Handshuh

“Practical aspects of physical security, implementation attacks and countermeasures”


In this presentation we review the main side-channel attacks and invasive attacks the embedded security industry has to deal with and which types of countermeasures are relevant and practical. We provide some estimate of acceptable performance and area impact of practical countermeasures and insights into development constraints for embedded security chips.  We also introduce a fairly new security primitive called Physically Unclonable Functions which allows to protect against a major category of implementation attacks, namely invasive attacks.

We explain the physical security advantages of this approach and analyze how PUFs help to provide essentially much higher security at a low cost.





Nadia Heninger

“Recovering cryptographic keys with the cold boot attack”


The "cold boot" attack is a side-channel attack that allows an attacker to extract encryption keys from data that is still left in a computer's RAM after the power has been cut.  I will discuss the kind of data an attacker can find in practice, some practical and theoretical aspects of finding keys hidden in gigabytes of data, experimental results on errors introduced during the attack, and techniques for efficiently correcting bit errors in encryption keys from both symmetric and public-key

encryption systems.





Yuval Ishai

 “Private Circuits”


"Private circuits" are circuits that can store a secret, perform computations involving the secret, and maintain its secrecy even in the presence of side-channel attacks. This talk will survey work on private circuits (including joint works with Manoj Prabhakaran, Amit Sahai, and David Wagner) and discuss some related open questions.

Yuval Ishai, Technion and UCLA





Stefan Mangard

“Advanced Topics in Side-Channel Attacks”


Advanced side-channel attacks typically become relevant in the context of attacks on devices that implement countermeasures. This talk discusses different ountermeasures and attacks on these countermeasures. The talk in particular discusses masking countermeasures and attacks like template attacks, higher-order attacks and mutual information analysis. Based on these attacks, the challenges of securely implementing cryptographic algorithms in practice are discussed.





David Naccache and Nigel Smart

“Hamster wheel keys”


In this talk we will present key evolution algorithms allowing to better resist side channel attacks. All the methods that will be presented are based on the following idea. We consider functions f, other than trees, such that f^i(x) can be computed from x in less than i successive applications of f, using a computational shortcut. Typical examples of such functions are f(x)=c x^e mod p, the concatenation of such functions for small p values or their ECC equivalents. In the considered scenario, a smart card contains a secret k_0 updated after each session by the operation k_{i+1}=f(k_i) thereby offering resistance to an attacker capable of reading some bits of k_i from a side channel leakage. The terminal uses the shortcut to derive directly k_{i+1} from k_0. We will present different known PRNGs featuring this property and evaluate their degree of resistance to leakage using a number of artithmetic techniques (LLL, Coppersmith etc) for different parameter combinations.





Elisabeth Oswald
"Introduction to Side-Channel Analysis"

In this tutorial I aim to introduce several core concepts in the area of side-channel analysis. This includes attack strategies, such as simple and differential power analysis,
the notion of leakage of a device (and the exploitation of this leakage), as well as countermeasures and their pros and cons. Finally, I will discuss the most popular research directions pursued by theoreticians and practitioners in the area.






Olivier Pereira

“Leakage Resilient Cryptography in Practice”


Using the design of a secure PRG as a motivating example, we discuss several models and constructions for leakage resilient cryptography, in the light of observations from the practice of side-channel attacks. This is a joint work with Francois-Xavier Standaert and Yu Yu and Jean-Jacques Quisquater and Moti Yung and Elisabeth Oswald.






Kerstin Lemke-Rust

"On Security Evaluation Testing"


For the security evaluation of products and systems penetration testing is  traditionally of fundamental importance. Penetration testing is done by  evaluation labs, mostly according to certification schemes. New research findings in practical physical analysis are thereby continuously taken into  account. This talk discusses two different certification schemes: the Common  Criteria and the FIPS 140. Both schemes are introduced with a focus on  vulnerability analysis for cryptographic modules with high needs for physical  security. As examples, we discuss the penetration testing approach for  smartcard ICs in the Common Criteria scheme and the test requirements for multiple chip cryptographic modules according to the FIPS 140 scheme.






Gil Segev

“Public-key Cryptosystems Resilient to Key Leakage”


Most of the work in the analysis of cryptographic schemes has traditionally focused on abstract adversarial models that do not capture "side-channel attacks". Such attacks exploit various forms of unintended leakage of sensitive information, which is inherent to almost all physical implementations. Inspired by extremely devastating real-life attacks, in this talk I will describe a recent approach for modeling and combating side-channel attacks. I will focus on a framework for modeling a wide range of attacks that rely on partial leakage of secret keys. In particular, I will present a rather simple and efficient construction of a public-key encryption scheme that is resilient to leakage of almost its whole secret key, as well as a generic method for constructing leakage-resilient encryption schemes that can be based on a variety of number-theoretic assumptions.

Based on joint work with Moni Naor.






Sergei Skorobogatov

“Hardware security of silicon chips: progress, pitfalls and challenges for physical attacks”


Tamper resistance of secure silicon devices like microcontrollers and smartcards is an important subject since the outbreak of attacks in the late nineties. Embedded memory in microcontrollers, smartcards, FPGAs and ASICs are among the security concerns as these areas usually store critical parts of algorithms, secret data and cryptographic keys. It seemed to be relatively easy and straightforward to attack silicon chips ten years ago. Many of those old and well known tools no longer work for modern chips. However, this did not mean a relief for hardware manufacturers and developers as new tools and techniques have emerged posing even greater threat. One of the greatest shake-ups happened in 2002 with introduction of optical fault injection attacks. This lead to separation of a new class of attacks called semi-invasive and which are very efficient and low-cost. This even forced the revision of certain security evaluation requirements. Despite to a long time since introduction, optical attacks still bring many surprises and their danger and effectiveness is sometimes dangerously underestimated. There are many examples to that including recent achievements which I will introduce in this talk. I will present an overview of tools and techniques used in the old days and nowadays. I will discuss challenges that still exist for modern chips including the ways it could be overcome. I will discuss hardware security awareness and its lead to countermeasures. At the end I will give some anecdotal examples how hardware security can be ruined by careless implementation and management.






Ingrid Verbauwhede

“Design methods and tools for side-channel secure circuits”


Designing secure embedded devices is a joint optimization problem of many parameters. The most important ones are area, e.g. transistor count or memory footprint, performance, e.g. real-time throughput or average response time, energy or power consumption, for battery operated devices or for cooling issues and flexibility, for updates, remote reconfigurations and so on. Security against passive and active attacks is yet another optimization goal.  In this presentation, systematic design methods and tools will be described to make devices resistant against side-channel attacks.

taking the other design parameters into account. The quality of the methods and tools depends on the engineering and mathematical models used during the design phase of the circuit. We will try to link the engineering models used in the design of circuits with the abstract models proposed by the computer science theory community for side-channel leakage.





Daniel Wichs

“Non-Malleable Codes and Applications to Tamper-Resilient Security”


Joint work with Stefan Dziembowski and Krzysztof Pietrzak.

We introduce the notion of “non-malleable codes” which relaxes the notion of error correction and error detection. Informally, a code is non-malleable if the message contained in a modified codeword is either the original message, or a completely unrelated value. In contrast to error-correction and error-detection,  non malleability can be achieved for very rich classes of modifications.  We construct an efficient code that is non-malleable with respect to modifications that effect each bit of the codeword arbitrarily (i.e. leave it untouched, flip it or set it to either 0 or 1), but independently of the value of the other bits of the codeword. Using the probabilistic method, we also show a very strong and general statement: there exists a non-malleable code for every “small enough” family F of functions via which codewords can be modified. Although this probabilistic method argument does not directly yield efficient constructions, it gives us efficient non-malleable codes in the random-oracle model for very general classes of tampering functions-e.g. functions where every bit in the tampered codeword can depend arbitrarily on any 99% of the bits in the original codeword. As an application of non-malleable codes, we show that they provide an elegant algorithmic solution to the task of protecting functionalities implemented in hardware (e.g. signature cards) against “tampering attacks”. In such attacks, the secret state of a physical system is tampered, in the hopes that future interaction with the modified system will reveal some secret information. This problem, was previously studied in the work of Gennaro et al. in 2004 under the name “algorithmic tamper proof security” (ATP). We show that non-malleable codes can be used to achieve important improvements over the prior work. In particular, we show that any functionality can be made secure against a large class of tampering attacks, simply by encoding the secret-state with a non-malleable code while it is stored

in memory.