Skip to content

Workshop Programme

for period 31 January - 2 February 2012

Is Cryptographic Theory Practically Relevant?

31 January - 2 February 2012


Tuesday 31 January
09:00-09:40 Registration
  Welcome: Is Cryptographic Theory Practically Relevant?
09:45-10:30 Vaudenay, S (EPFL)
  Privacy in Deniable Anonymous Concurrent Authentication with Setup is Impossible: Do we Care? Sem 1

In this talk we review four stories about theoretical cryptography and their impact in practice. This includes a recent analysis of RC4, the notion of deniable interactive proof, the impossibility of strong privacy in RFID protocols, and the impossibility to UC-realize commitment.

10:30-11:00 Morning Coffee
11:00-11:45 Cachin, C (IBM Research, Zurich)
  Storage encryption and key management Sem 1

Data encryption has become a key requirement for enterprise storage systems. As a consequence of this I have looked into storage encryption methods and contributed to several storage security products at IBM. Research has formulated the notion of tweakable encryption modes, which specifically address a requirement of storage encryption. On the other hand, practitioners have used specific key-wrapping modes for a long time before researchers came up with a formal notion. We highlight where and how they are used. The biggest concern in storage encryption are cryptographic keys, which must be maintained securely and reliably. Users struggle with the key-management problem because operating procedures and formats differ across systems. When multiple users access a key server, its interface must be designed with special consideration for cryptographic relations among keys. Cryptographic hardware-security modules (HSMs) face the same problem. Some logical attacks through the key-management operations of HSMs have been reported in the past, which allowed to expose keys merely by exploiting their interfaces in unexpected ways. We show how to model the security of key-management systems formally and protect them from interface attacks. This work originates in the context of creating the OASIS Key Management Interoperability Protocol (KMIP), a new open standard for enterprise-level key management.

11:45-12:30 Naccache, D (ENS Paris)
  Mathematical and practical security problems not directly related to cryptography Sem 1

Bored by random oracles, lattices, security reductions and games? This talk is for you! We will describe a number of practical security problems (some of which very mathematical) met while designing security systems. Subjet to available time, we will address the efficient spatial scattering of secrets, the geometrical properties of protective chip wire-meshes, a new breed of system fault protections requiring combinatorial tools, the optimal placement of scramblers, quick pre-identification and the use of secure devices to... attack other secure devices

12:30-13:30 Lunch at Wolfson Court
14:00-14:45 Groth, J (UCL)
  Efficient Verification of ElGamal Ciphertext Shuffles Sem 1

A shuffle is a permutation and rerandomization of a set of ciphertexts. This means that the input ciphertexts and the output ciphertexts contain the same set of plaintexts but in permuted order. Furthermore, due to rerandomization of the ciphertexts the permutation is hidden. Mix-nets often use a sequence of random shuffles performed by different mix-servers to hide the link between senders and plaintexts. A common use is found in voting schemes, where a mix-net uses random shuffles to anonymize a set of encrypted votes. To protect against malicious mix-servers it is necessary to verify that the shuffles are correct. Otherwise, a bad mix-server could for instance substitute encrypted votes cast by honest voters with encrypted votes for another candidate. Zero-knowledge proofs can be used to guarantee the correctness of a shuffle without revealing the underlying permutation or anything else. By providing such a zero-knowledge proof the mix-server can prove that it has not substituted any ciphertexts or in any other way deviated from the protocol; but at the same time the link between input ciphertexts and output ciphertexts remains secret. Zero-knowledge proofs for correctness of a shuffle are complicated beasts but we will present a construction that is both efficient and where the required communication is much smaller than the size of the shuffle itself. We have implemented the zero-knowledge proof and will provide concrete performance measurements for verifying shuffles of ElGamal ciphertexts.

14:45-15:30 Shrimpton, T (Portland State)
  A long answer to the simple question, "Is TLS provably secure?" Sem 1

TLS is perhaps the Internet's most widely used security protocol, and at its heart is a subprotocol for providing data privacy and integrity, called the TLS Record Protocol. Is the TLS Record Protocol provably secure? A series of papers starting in 2000 delivered the answers (roughly): no, not for all possible underlying encryption schemes; yes, for some of the specific encryption schemes that TLS uses, but only under some impractical assumptions; yes, under less restrictive assumptions, but for a definition of "secure" that is hard to understand; yes, as long as your integrity-providing "tag" isn't too short. We'll explore this line of papers, as well as some interesting attacks that helped to guide the provable-security results. In the end, we'll argue that the answer is still "it depends on how you use it" by discussing new results on using secure authenticated encryption (e.g. TLS) as a tunnel between a user and a proxy, through which webpages are requested and downloaded. We'll see that it is surprisingly easy to determine which webpage was visited, even in the presence of some sophisticated efforts to fragment and pad the webpage data prior to entering the provably-secure encryption tunnel.

15:30-16:00 Afternoon Tea
16:00-16:30 Horne, R; French, G (Barclays and UK Cabinet Office/Barclays)
  Scaling Cryptographic Deployments Sem 1

As use of cryptography has exploded in recent years, so has the vulnerability to exploitation of the multitude of implementations. Organisations such as banks who critically depend on cryptography on a massive scale (both in terms of volume of keys under management and number of different implementations) need: 1. Solutions that enable standardised, central service provision of cryptography, and 2. Implementations of cryptographic standards and protocols that are demonstrably secure. This talk will discuss the requirements and illustrate how research is required to meet them. It will illustrate the real-world applicability of current research to identify weaknesses in implementations of cryptographic protocols.

16:30-17:15 Steel, G (ENS Cachan)
  Analysis of Cryptographic Security APIs Sem 1

In practice, many developers use cryptography via an application program interface (API) either to a software library or a hardware device where keys are stored and all cryptographic operations take place. Designing such interfaces so that they offer flexible functionality but cannot be abused to reveal keys or secrets has proved to be extremely difficult, with a number of published vulnerabilities in widely-used APIs appearing over the last decade. This talk will discuss recent research on the use of formal methods to specify and verify such interfaces in order to either detect flaws or prove security properties. We will focus on the example of RSA PKCS#11, the most widely used interface for cryptographic devices. We will demonstrate a tool, Tookan, which can reverse engineer the particular configuration of PKCS#11 in use on some device under test, construct a model of the device's functionality, and call a model checker to search for attacks. If an attack is found, it can be executed automatically on the device. We will comment on design principles for the next generation of APIs.

17:30-18:00 Drinks Reception
Wednesday 1 February
09:00-09:45 Krawczyk, H (IBM Research, USA)
  Cryptographic Extraction Sem 1

Randomness extractors are algorithms that map sources of sufficient min-entropy to outputs that are statistically close to uniform. Randomness extraction has become a central and ubiquitous notion in complexity theory and theoretical computer science with innumerable applications and surprising and unifying connections to other notions. Cryptography, too, has greatly benefited from this notion. Cryptographic applications of randomness extractors range from the construction of pseudorandom generators from one-way functions to the design of cryptographic functionality from noisy and weak sources (including applications to quantum cryptography) to the more recent advances in areas such as leakage- and exposure-resilient cryptography, circular encryption, fully homomorphic encryption, etc. Randomness extractors have also found important cryptographic uses in practical applications, particularly for the construction of key derivation functions. In many of these applications, the defining property of randomness extractors, namely, statistical closeness of their output to a uniform distribution, can be relaxed and replaced with computational indistinguishability. Extractors that provide this form of relaxed guarantee are called 'computational extractors'. In this talk I will cover some recent advances in the understanding and applicability of computational extractors with particular focus on their role in building key derivation functions. As a connection between this talk and the question 'Is Cryptographic Theory Practically Relevant?' see

09:45-10:30 Beric, J; Ward, M (Mastercard International)
  The practical application of cryptography to international card payments Sem 1

The presentation will explore chip card payment systems based on the EMV specifications and their use of and reliance on cryptography. The presentation will begin by reviewing some earlier forms of card payments and then move on to a more detailed analysis of the cryptographic methods used in today's systems and those that may be deployed in the future.

10:30-11:00 Morning Coffee
11:00-11:45 Kiayias, A (Athens)
  Cryptography with Work-based Corruptions and the Combinatorics of Anonymity Sem 1

In the setting of cryptographic protocols, the corruption of a party has been viewed as a simple, uniform and atomic operation, where the adversary decides to get control over a party and this party immediately gets corrupted. In this talk, motivated by the fact that different players may require different resources to get corrupted, we introduce the notion of resource-based corruptions, where the adversary must invest some resources in order to perform corruptions. If the adversary has full information about the system configuration then resource-based corruptions would provide no fundamental difference from the standard corruption model. However, in the `anonymous' setting (where anonymity is in the sense that such configuration is hidden from the adversary), much is to be gained in terms of efficiency and security. We showcase the power of anonymity in the setting of secure multiparty computation with resource-based corruptions and prove that anonymity can effectively be used to circumvent impossibility results. Regarding efficiency gains, we show that anonymity can be used to force the corruption threshold to drop from 1/2 to 1/3, in turn allowing the use of more efficient cryptographic protocols in various settings. Joint work with Juan Garay, David Johnson (AT&T), Moti Yung (Google).

11:45-12:30 Bond, M (Cryptomathic)
  HSM Portal – Practical Tools built on Theory Sem 1

Cryptomathic has been working on a new approach to applications cryptography, inspired by the need to give useful and sound building blocks to applications developers, rather than flexible but dangerous tools. This is partly based on some ideas and work by George French, Senior Security Architect, Barclays. The talk describes novel features of our âM portalâ a cryptographic service which offers high-level primitives to applications, and abstracts away dirty detail of hardware security module and software cryptography and key management. Using a high-level approach allows the service to offer primitives closer to the theoretical models of black box cryptography than are ordinarily provided by a simple crypto library. Our talk will discuss why we believe the gap between applications developers requiring cryptography and security engineers/theorists is ever widening. We believe new tools are needed and proposed theoretical ideas need to be brought to life to bridge this gap, lest practice become totally disconnected from theory in the future.

12:30-13:30 Lunch at Wolfson Court
14:00-14:45 Preneel, B (KU Leuven)
  Theory and practice for hash functions Sem 1

In the last seven years we have witnessed a surge in the cryptanalysis of hash functions. The most visible result was the cryptanalysis of MD5 and SHA-1 by Wang et al., but there have been other results including multi-collision attacks, long message second preimage attacks, and rebound attacks. There has also been substantial progress in understanding security definitions and models (e.g. indifferentiability) and a large number of security reductions has been proven. In 2007, NIST has launched the call for the SHA-3 competition. In 2008 more than 60 submissions were received, which makes this the largest open cryptographic competition to date. In this talk we will discuss the impact of the research on hash functions on practice and the interaction between theory and practice in the SHA-3 competition.

14:45-15:30 Paar, C (Ruhr University Bochum)
  Lessons Learned from Four Years of Implementation Attacks against Real-World Targets Sem 1

Over the last few years we were able to break various real-world security systems using various flavours of physical attacks. About three years ago we were able to break KeeLoq, which is a 64 bit block cipher that is popular for remote keyless entry (RKE) systems. Even though the attack seems almost straightforward in hindsight, there where many practical and theoretical problems to overcome. More recently we were able to break certain types of the DESFire contactless smart card, which are widely used, e.g., for payment application. We also completely broke the bit stream encryption used in Xilinx FPGAs. In all both cases we were able to recover the keys for either 3DES or AES using power analysis attacks. In contrast to KeeLoq, both 3DES and AES are considered very secure from a classical cryptanalyitical point of view. Interesingly, the real-world implications of these key-extraction attacks are highly dependend on the system design (and not on the cipher used). In addition to summarizing the above mentioned work, I will try to draw some meaningful conclusions. This includes the often considerable practial hurdles an attacker has to overcome and the important role that system design plays.

15:30-16:00 Afternoon Tea
16:00-16:45 Danezis, G (Microsoft)
  Secure metrology: From theory to practice Sem 1

Over that past year our team has developed a portfolio of technologies to address privacy issues in smart metering. These were inspired by cryptographic techniques well established in research, but unheard of in the domain of embedded systems security. In this talk I chart our journey from the design of the techniques, to our experiences implementing them to be part of a real smart meter. Considerations such as memory footprint, stateless interfaces, and compatibility with communications protocols, not mere security properties, ended up being the deciding factor.

16:45-17:15 Discussion Time
19:30-22:00 Conference Dinner at Emmanuel College
Thursday 2 February
09:00-09:45 Ristenpart, T (Wisconsin, Madison)
  Practice-Driven Cryptographic Theory Sem 1

Cryptographic standards abound: TLS, SSH, IPSec, XML Encryption, PKCS, and so many more. In theory the cryptographic schemes used within these standards solve well understood problems, yet a parade of damaging attacks leave us with the question: What gives? Theoreticians often suggest (at least in private) that the problems are well-understood and attacks arise because standardizers misunderstand cryptographic theory. I'll use some of my recent work which uses provable-security techniques to analyze important standards (including TLS, HMAC, and PKCS#5) to argue that, just as often, it is the theoreticians who don't have all the answers: analyzing practically-useful cryptography requires pushing models and proof techniques in never-before-considered directions. We'll see how (what I'll call) practice-driven cryptographic theory can lead to new understanding and improved confidence in cryptographic practice. This talk will cover joint work with Mihir Bellare, Yevgeniy Dodis, Kenneth Paterson, Thomas Shrimpton, Neils Fergeson, John Steinberger, and Stefano Tessaro.

09:45-10:30 Shacham, H (UCSB)
  Cars and Voting Machines: Embedded Systems in the Field Sem 1

How well are the tools of modern cryptography employed in fielded embedded systems? How are the common tasks of communication and authentication, key storage and distribution, and firmware update and verification performed? In this talk, we describe evidence gathered from several studies of deployed embedded systems: a modern mass-market automobile and two electronic voting machines. These studies consisted of substantial reverse-engineering efforts by large teams of researchers. We find that in many cases the designers of the systems we studied are getting simple cryptographic tasks wrong. These failures suggest a lack of engagement with the cryptography and security research community. We consider some reasons for the status quo, and some ways that it might be improved. Joint work with Danny Anderson, Stephen Checkoway, Alexei Czeskis, Ariel Feldman, Edward Felten, J. Alex Halderman, Srinivas Inguva, Brian Kantor, Tadayoshi Kohno, Karl Koscher, Damon McCoy, Shwetak Patel, Eric Rescorla, Franziska Roesner, Stefan Savage, and Dan Wallach.

10:30-11:00 Morning Coffee
11:00-11:45 Chen, L (Hewlett-Packard Laboratories)
  From Cryptographer's Cryptography to Engineer's Crypto Sem 1

Cryptography has become an increasingly important subject, not only for cryptographers but also for computer engineers. Having been involved for many years in research and industrial consultation in cryptography and its practical applications, I have become very aware of the huge gap between the cryptographer's and the engineer's point of view regarding cryptography. In this talk, I would like to share my experiences with the workshop participants, and will take cryptographic functionalities of a TPM (trusted platform module), as an interesting example, to discuss how to create a healthy life circle in cryptography. This will include a smooth link between academic research, international standards, industrial products and real usages.

11:45-12:30 Wikström, D (KTH - Royal Institute of Technology)
  Verificatum -- An efficient and provably secure mix-net Sem 1

A common component in electronic election schemes is a so called 'mix-net'. This is a protocol executed by a group of servers that takes a list of ciphertexts and outputs the plaintexts in sorted order without revealing anything about the correspondence between input ciphertexts and output plaintexts. Thus, a mix-net can securely perform the tabulation in an electronic election where voters submit encrypted votes. Verificatum is an open source implementation of an efficient and provably secure mix-net (see In its simplest form it is a Java application that is easy to install and use, but it can also exploit optimized C code, it can be configured in many ways, and it is a perfect platform for implementing more advanced election schemes. It has already been used successfully in the Wombat voting project. We will present Verificatum and describe the work we have done so far and what lies ahead.

12:30-13:30 Lunch at Wolfson Court
14:00-14:45 Cremers, C (ETH Zurich)
  Key Exchange: Security Models and Automatic Analysis Sem 1

During the last 20 years many game-based security models have been proposed for the analysis of Key Exchange protocols. The intent of these models is to prove Key Exchange protocols secure in the presence of increasingly powerful adversaries. In this talk, we present the main ingredients of these models, and relate them to practical threat models. We highlight both benefits and drawbacks of the way in which these security models are currently defined. Additionally, we present to what extent we can currently provide automatic analysis for Key Exchange protocols. We show how we use automatic analysis for evaluating existing security models as well as for developing alternative security models.

14:45-15:30 McGrew, D (Cisco)
  Problems in Cryptographic Standards and Implementations Sem 1

In theory, we understand how to provide security through cryptography, yet too often practice does not live up to this promise. In standards, cryptographic imperatives compete with other pragmatic needs. This work seeks to understand those non-cryptographic needs and shed light on how they impact cryptographic security. We survey security failures in cryptographic standards and implementations, and analyze common problems. For standards, we consider the example of problems with authentication and the slow but steady adoption of authenticated encryption. For implementations, we review reported vulnerabilities and assess typical misuses and failure modes. Lastly, we suggest some ways that the research and standards communities can collaborate.

15:30-16:00 Afternoon Tea
16:00-16:30 Panel Session: New Directions in Practice Driven Cryptography

Back to top ∧