Seminar 2010

Dismantling SecureMemory, CryptoMemory and CryptoRF

11:00am Friday November 19th, Campus Kirchberg E212, LACS seminar held by Flavio D. Garcia from Radboud University Nijmegen, The Netherlands

The Atmel chip families SecureMemory, CryptoMemory, and Cryptorf use a proprietary stream cipher to guarantee authenticity, confidentiality, and integrity. This paper describes the cipher in detail and points out several weaknesses.

One is the fact that the three components of the cipher operate largely independently; another is that the intermediate output generated by two of those components is strongly correlated with the generated keystream. For SecureMemory, a single eavesdropped trace is enough to recover the secret key with probability $0.57$ in $2^{39}$ cipher ticks. This is a factor of $2^{31.5}$ faster than a brute force attack. On a 2 GHz laptop, this takes around 10 minutes.

With more traces, the secret key can be recovered with virtual certainty without significant additional cost in time. For CryptoMemory and Cryptorf, if one has 2640 traces it is possible to recover the key in $2^{52}$ cipher ticks, which is $2^{19}$ times faster than brute force. On a 50 machine cluster of 2 GHz quad-core machines this would take less than 2 days.

Constant Query Locally Decodable Codes against Computationally Bounded Adversary

10:30am Thursday August 12th, Campus Kirchberg E212, LACS seminar held by Rishiraj Bhattacharya, from Indian Statistical Institute, Kolkata

Locally Decodable Codes (LDCs) are error correcting codes with sublinear time decoding algorithm. A q-query LDC consists of a randomized decoder, which can decode a message bit i with high probability by looking at only q  bits of the received corrupted message. Constructing constant query LDCs (i.e. q is a constant) with polynomial rate is a major open problem in Theoretical Computer Science.
 
In TCC 2005, Micali et. al. showed that, in case of general error correcting codes, if the adversarial channel is modeled as a Probabilistic Polynomial Time Turing Machine (PPTM),  one can construct, assuming existence of one way functions,  uniquely decodable error correcting codes which can achieve efficiency of list decoding. Hence constraining  the power  of the channel can improve the efficiency of general error correcting codes.
 
We consider the problem of constructing Constant Query Locally Decodable Codes with polynomial rate modelling the channel as  a PPTM.  In this work we prove ( under standard cryptographic assumptions) that unless both the sender and receiver share a secret key, a constant query LDC against PPTM adversary can not achieve significantly higher rate than information theoretic LDCs . On the other hand if the sender and receiver shares a secret key then there exists Constant Query LDC with polynomial rate.
 
(joint work with Sourav Chakraborty, CWI, Amsterdam)

Implementation Attacks in Practice

16:00pm Wednesday June 30th, Campus Kirchberg E212, LACS seminar held by Jörn-Marc Schmidt from Graz University of Technology, Austria

Implementation attacks are among the most powerful attacksagainst cryptographic devices nowadays. Instead of considering sucha device as a black box, these attacks try to benefit from thecharacteristics of the device (passive) or even influence its behavior(active). This talk discusses passive attacks as well as active attacksin practice. Furthermore, the vulnerability of RFID devices to activeattacks is highlighted.

Key distribution and oblivious transfer à la Merkle

11:00am Thursday July 1st, Campus Kirchberg E212, LACS seminar held by Gilles Brassard, Université de Montréal, Canada

Ralph Merkle's seminal 1974 protocol for public key distribution is extended in two directions: In the quantum setting and for achieving oblivious transfer. First we show that Merkle's original protocol is totally insecure against a quantum adversary; but then we prove that it can be repaired by allowing the legitimate parties to use quantum computation as well. Second, we give a novel classical protocol for oblivious transfer, based on Merkle's original construction for key distribution, and we prove its polynomial security against all classical attacks in the black-box model. However, we also show that our classical oblivious transfer protocol melts down against a quantum attack: it's easier to cheat it than to use it legitimately! Finally, we propose a fully quantum protocol for oblivious transfer and we conjecture that it is polynomially secure against quantum attacks. No previous knowledge in quantum information will be expected from the audience.

Cayley graph expanders and their applications

10:30am Monday June 21th, Campus Kirchberg E212, joint LACS/RMATH seminar held by Alina Vdovina, University of Newcastle

We present new infinite families of expanders graphs of degree 4, which is the minimal possible degree of vertices for Cayley graph expanders.

We will discuss possible applications to the coding theory and hash functions construction.

Duplexing the sponge: single-pass authenticated encryption and other applications

10:30am Monday June 15th, Campus Kirchberg E212, LACS seminar held by Joan Daemen, STMicroelectronics Belgium

We present a novel construction closely related to the sponge construction, called Duplex. It accepts message blocks to be hashed and — at no extra cost — provides digests on the input blocks received so far. It can be proven equivalent to a cascade of sponge functions and hence inherits its security against generic attacks. As main application of the Duplex construction we present an authenticated encryption mode. This mode is readily usable in, e.g., key wrapping and is single-pass, namely, enciphering and authenticating requires only a single call to the underlying permutation per block. The Duplex construction can be used to efficiently realize other primitives as well, such as a reseedable pseudorandom sequence generators and a sponge variant that overwrites part of the state with the input block rather than to XOR it in.

Joint work with Guido Bertoni, Michaël Peeters and Gilles Van Assche.

Hierarchical Design and Security Proofs

10:30am Monday June 7th, Campus Kirchberg E212, LACS seminar held by Tatsuaki Okamoto, NTT Tokyo

If a cryptographic system is highly functional, it is not easy to design the system and analyze its security. It is a natural strategy to design and analyze such a complicated system in a modular way. In my talk, I will introduce a type of modular way of design and analysis, hierarchical design and security proof. In our approach, the underlying primitive is bilinear pairing groups, and a higher level of concept is constructed on the primitive, where a highly functional crypto system is directly designed over the higher level of concept. In addition, the security proof can be executed in a hierarchical manner, where the underlying assumption for the security proof is one of the simplest assumptions over the primitive, and higher level assumptions are reduced to the primitive assumption and the top level assumption over the higher level concept is directly employed to prove the security of the cryptosystem.

Automorphic signatures

14:15pm Wednesday April 28th, Campus Kirchberg E212, LACS seminar held by Georg Fuchsbauer, ENS Paris

We present a new class of digital signatures with the  following properties: the verification keys lie in the message space, messages and signatures consist of elements from a pairing-friendly group, and signatures are verified by evaluating a set of pairing-product equations.

These signatures were designed to be combined with a powerful non-interactive proof system by Groth and Sahai from Eurocrypt 2008. We show how this combination enables efficient instantiations of anonymous proxy signatures and round-efficient blind signatures.

Memory corruption in the 21st century

10:30am  Monday April 26th, Campus Kirchberg E212, LACS seminar held by Ralf-Philipp Weinmann, University of Luxembourg

Software bugs leading to memory corruption are powerful: In almost all cases, memory corruptions can be used to hijack the control flow of the program which usually leads to the ability to execute arbitrary code. Most of the problems leading to memory corruption taught to students in IT security courses however are close to extinct in well-audited code bases. Fortify, Coverity and related static analysis tools have significantly reduced the number of simple buffer and heap overflows. Moreover, mitigations such as stack/heap cookies and safe unlinking have make exploitation of these bugs increasingly more difficult. However, this does not mean that memory corruption problems are a problem of the past.

This talk will show a bug class that is still prevalent in modern software and how it can be exploited.

LACS Research Days, March 2 - 3, 2010 

On March 2-3, LACS hold the 2nd edition of its Research Days. This an event where all PhD students and postdocs of LACS present their recent research to other members of the lab. The presentations are open to everybody in CSC.

Recent Improvements in Onion Routing Circuit Construction

14:15pm  Monday February 1st, Campus Kirchberg E212, LACS seminar held by Aniket Kate, University of Waterloo

Identity-based cryptography significantly simplifies public-key and certificate management in a public-key infrastructure. In this talk, I will describe provably secure one-way and two-way anonymous key agreement schemes in an identity-based infrastructure setting and will employ those to define new onion routing circuit construction: pairing-based onion routing (PB-OR). PB-OR, based on a user's selection, offer immediate or eventual forward secrecy at each node in a circuit. Along with other benefits, they also require significantlyless computation and communication than the telescoping mechanism used by the Tor anonymizing network.

In the second half of the talk, I will present new message formats for onion routing circuit construction using the Sphinx methodology developed for mixes. These message formats significantly compress the circuit construction messages for three onion routing protocols that have emerged as enhancements to Tor; namely, Tor with predistributed Diffie-Hellman values, PB-OR, and certificateless onion routing. Further, the corresponding circuit constructions are secure in the universal composability framework, a property that was missing from the original constructions. Finally, I will compare the performance of the new schemes with their older counterparts as well as with each other.

This is a joint work with Ian Goldberg and Greg M. Zaverucha.