Africacrypt

One of the more interesting talks at Africacrypt this year was a talk given by Daniel Loebenberger on a paper with Michael Nusken (Univeristy of Bonn) on "Analyzing Standards for RSA Integers". The premise of this paper is that algorithms used in standards to generate RSA moduli might lead to "insecure" generation. The analysis is carried out by setting up a theoretical framework for calculating the entropy of the output distribution of algorithms for RSA modulus generation such as those found in IEEE 1363, FIPS 186-3, ISO 18033-2 etc.

It is perhaps unsurprising that many of these standards do indeed produce 'secure' RSA moduli however a closer inspection of some of the algorithms gives some surprising results. For example if we consider RSA integers generated from the GNU Crypto library it turns out the second prime q is only chosen after p, and the product must be of fixed length. Hence, if p is large there are far less choices for q. One might expect the loss in entropy to be large but in fact this is not the case and the output modulus pq is still suitably random.

This rather unusual and interesting work provides a theoretical framework for analysing practical cryptography and it would be good if other algorithms that have been standardised came under similar scrutiny. This could both prove the quality of some standards and expose weaknesses in others.

VAM2 workshop - day 2

Similar to the first day, the second day of ECRYPT II VAM2 Workshop on Practical Implementation Attacks was mostly dedicated to industry talks. The morning session started with a very interesting talk given by Steven Murdoch from Cambridge University who presented man-in-the middle attacks for chip and PIN payments. It was his second talk on this workshop and the second one being as interesting as the first one on the day before. He described possibilities how to use a fake terminal to perform an on-line attack and charge the user more for a transaction then he would expect.

Next, Benoit Feix from Inside Secure gave a talk about the Daily Life for a Secure Product in the Industry, where he introduced threats and countermeasures against physical attacks and a more general overview of how companies have to deal with it in their product and design life cycle. Afterwards, Lex Schoonen gave a talk about the Practical Aspects of Security Evaluation where he described the use and pitfalls of Common Criteria standards. He also presented a couple of practical evaluation examples which shown out-of-the-box thinking, e.g. use an UZI gun to shoot away a chip from the PCB board which was responsible for raising an alarm and erasing the key storage. The trick was to be quicker than the signal propagation time, chip setup time etc. So it seems that that the UZI has a new application.

The workshop ended with two talks given by Sergei Skorobogatov from Cambridge University in which he presented Fault Attacks on Secure Chips and Side-channel Attacks: New Directions and Horizons. Both talks were very interested, specially the second one where we could hear about new measurement setups with lower noise. This allows to perform power attacks quicker and with less traces. Unfortunately, to achieve lower noise, lots of design details have to be know in advance. The whole idea also suffers from randomization issues but nevertheless the overall performance improvement was significant.

Day 2 of WISTP'11

Today I'm going to write about two interesting talks from the WISTP 2011 conference which deserve some attention. The first was Pim Tuyls talk on intrinsic PUFs. It was an invited talk like yesterday's talk by David Naccache but unlike yesterdays talk it didn't focus on research to come but on a topic that has mostly moved from the world of research to the world of product development: Intrinsic PUFs. Pim Tuyls described the security advantages of PUFs very convincingly but even more outstanding in his talk was another advantage of intrinsic PUFs: They can be implemented as soon as a new semiconductor technology step (for example 28nm technology) is available and doesn't have to wait for non-volatile memory such as flash to be available in that technology. Considering that it usually takes considerable amount of time between the availability of a technology step and the availability of non-volatile memory in the same technology, this is quite an important advantage.

The second talk I have to mention is Matt Henricksen's talk on AES variants secure against related-key attacks. I am not going to describe their paper in great detail as I am not convinced that the AES standard will be modified to support another key schedule anytime soon (not least of all because the practical relevance of related-key attacks is contestable) but I have another reason for selecting this talk: It was a good demonstration that something as "trivial" as a key schedule should not be neglected in research. Indeed, as far as AES is considered, the problem of designing a symmetric cipher seems to be better understood than the problem of designing a key schedule for this cipher. Matt's talk made it clear that they have made an important contribution to solving this problem and I look forward to read their paper (even though I'm not an expert for the design of symmetric ciphers).

VAM2 workshop - day 1

Today was the first day of the ECRYPT II VAM2 Workshop on Practical Implementation Attacks. We had four interesting lectures, mostly from people from industry. Guillaume Dabosville from Oberthur talked about the security challenges in the smart card industry. The biggest challenge today is still the issue of how to secure systems which center around an insecure user devcie (be it a conventional desktop PC or a modern smart phone). Even if secure components like a SIM card are present, this is still an unsolved problem. Then, Steven Murdoch from Cambridge University presented their attacks on payment terminals which allowed to spy out user PINs, clone cards, and make unauthorized payments. These attacks are especially interesting as they pertain to a large group of EMV users (which encompasses the holders of about a billion EMV cards). Lex Schoonen from Brightsight evaluation labs discussed certification and compliance for the security industry, which mainly relates to Common Criteria certification. Finally, Marc Joye from Telecolor (formerly Thomson) showed details on his work on efficient and secure generation of primes for cryptographic use on smart cards. His talk gave a good insight on the interplay between design for efficiency and design for security.

On subleq machines

One of the most interesting talks at WISTP so far was David Naccache's talk who, as an invited speaker, used the time to talk about some projects he's currently working on with students and fellow researchers and one of those topics was subleq machines. I've heard about RISC and CISC machines, Turing machines, single- and multicore processors, reconfigureable processors, general-purpose and dedicated co-processors and a lot of other architectures before but a subleq machine was completely new to me. It's not about Complex Instruction Set Computing nor Reduced ISC but about Single Instruction Computing. Now this might initially sound stupid if not impossible but quite to the contrary: Not only is it possible to compute any instruction using sequences of the subleq instruction (a bit like NAND-logic where you build arbitrary gates from NAND gates) but there's also some sense to limiting yourself to just one instruction. But let me explain the subleq machine a bit more, first.

A

   subleq a b c

instruction computes the same as the following C pseudo code:

   *b = *b - *a;

   if (*b <= 0) { goto c; }

With this,

   subleq a, a, $+1

is the same as

   clear a

just to give an example of the construction of other instructions and David Naccache showed some more. Also, subleq isn't the only instruction which could be used for a SI(S)C machine but among all the instructions investigated so far, subleq was their favourite.

So why would you want to build such a subleq machine? One thing is, that it is a very simple machine and thus easy to analyze on the hardware level if you need to prove resilience to power analysis attacks and fault injection. It also fills the gap between theoretical fault injection ("I have this equation and if there's a fault in this value then...") and practical fault injection ("I have this device and point my laser at that position and something happens...") as a subleq machine is simple enough to be used within formal frameworks of theoretic computer science. Using the tools of theoretic computer science one may thus hope to prove for a specific subleq program that it is resilient for up to n faulty instructions.

EUROCRYPT 11 - Day 2

Tuesday was a short day with only two sessions; one on signatures, on which I will focus, and one on information-theoretic cryptography. The afternoon was then reserved for the social event, which was a walking tour in the historic centre of Tallinn.

The first talk of the day was by Sven Schäge from Bochum who talked about tight proofs for signatures schemes without random oracles. For many standard-model signatures schemes, the proof of unforgeability splits into two cases depending on whether or not the adversary recycles parts of a signature it obtained in a signing query for its forgery. For the recycle case, the simulator in the proof typically guesses which of the queries the forgery will relate to, which introduces a polynomial loss in the reduction. Having tighter security proofs now allows us to use smaller parameters for practical instantiations.

The rest of the session were Bristol papers: the first one by Dario Catalano and Fiore, and Bogdan. Dario II introduced the concept of adaptive pseudo-free groups. This is an abstraction of objects typically used in cryptography where certain operations are "hard". A pseudo-free group is a group with efficient group operations which behaves like a free group for computationally bounded adversaries, such as an RSA group. For cryptographic applications this concept might be too weak, as e.g. for signature schemes, the adversary is allowed to see solutions to non-trivial equations by making signing queries. Adaptive pseudo-free groups extend thus pseudo-free groups to adaptive adversaries.

The last talk of the session was by myself on a new primitive called commuting signatures. They extend the functionality of verifiably encrypted signatures, which enable encryption of signatures and/or messages while giving a publicly verifiable proof that the content is valid. Commuting signatures allow a signer, given an encryption of a message, to produce a verifiably encrypted signature on the plaintext. As an application I gave the currently most efficient instantiation of delegatable anonymous credentials, which can be non-interactively delegated.

Eurocrypt '11 - Tallinn - Day One

We started off with the best paper at the conference - and a strong candidate for "best talk" too!
Efficient Authentication from Hard Learning Problems looked at how you could do authentication in a RFID tag. Forget Moore's Law, this is state-of the art technology and we're talking about a few thousand gates total. Even AES is not an option, so the authors developed an authentication protocol based on the "Learning Parity with Noise" problem (LPN), building on the HB scheme and adding security against active adversaries.
The basic idea is that prover and verifier share a secret vector, the verifier picks a random challenge vector and the prover replies with the inner product of the challenge and the secret XOR some biased random bit - this can fail for both honest and dishonest provers but the difference in failure probabilities allows you to construct a secure protocol through repetition.

Next up, a variant of NTRU which comes with a proof that it really is as hard as finding short vectors in lattices and a great introduction to the field of lattice-based cryptography by Phong Nguyen (invited talk).

The afternoon was devoted to side channels and (fully) homomorphic cryptography, where among others we saw fast(er) implementations of pairings, AES and Gentry's FHE scheme.
One highlight on side channels: A Formal Study of Power Variability Issues and Side-Channel Attacks for Nanoscale Devices.
As processsors get smaller, variability between different chips - even of the same series - starts to influence measurements like power traces, so you can't measure one chip to construct a hypothesis then test it on another as you'd like - the more exactly your hypothesis fits the first chip, the worse variation will make it on the second. The authors showed how you get better results by aiming for robustness rather than precision.
As an aside, chip manufacturers may be able to thwart side-channel attacks better by putting less effort into reducing variability.