ACNS 2012 - Day 3

Today's the last day of ACNS 2012. As we'll be immediately heading off to the conference VIP dinner after the last session and I'll probably don't want to whip out my laptop afterwards ;-) I'll give a short day's summary before the last session (dedicated to web security) takes place.

Today was dedicated mainly to security and privacy issues in current and emerging application fields like social networks, cloud systems and smart grids. Personally I found the talks regarding smart grids interesting as this field is very important to help us to reduce overall power consumption (through an increase of awareness in consumers) as well as to increase the efficiency of energy use (through the interplay of a smart grid with smart household appliances and devices). While it is clear that there is a communication need for individual smart meters to the grid operator and/or electricity provider, the different solutions presented in this session vary in the requirement of communication amongst smart meters themselves. The first system presented by Hsiao-Ying Lin does not require such communication but in turn has a few shortcomings which the authors hope to address in their future work. The second system presented by Zekeriya Erking requires communication amongst smart meters and employs an additive homomorphic encryption (Paillier) in a modified variant so that individual power readings cannot be decrypted, but a sum of such readings can. While this is certainly an interesting approach, it also requires all smart meters to be "honest" (as a single "dishonest" smart meter contributing malformated ciphertexts will prevent correct decryption of the sum of the readings).

ACNS 2012 - Day 2

The second day was mainly devoted to theoretical works on various new or improved cryptographic primitives or cryptanalytic methods. Unfortunately I missed the invited talk of the industry track for "A New Masking Scheme for Side-Channel Protection of the AES" as it clashed with the session where I presented our work. Apart from that, the last session featured three talks on side channel attacks with some first results on zero-value point attacks on computations on Kummer surfaces (which can be used to speed up ECC/HECC), a new block cipher (Picardo), whose S-box is specifically designed to make higher-order masking more efficient, and practical results on power-analysis attacks on AES using wide collisions. Wide collisions mean that a number of intermediate values of two encryptions end up having the same value (instead of e.g. just a single S-box output byte). The price to pay for this is the requirement for the attacker to be in control of the plaintext fed to the cryptographic device. Of the three side-channel talks, the wide-collision one has probably the most immediate practical relevance, as these results need to be taken into account when implementing AES in a side-channel resistant way.

ACNS 2012 - Day 1

We've just concluded the first "working" day of ACNS 2012 (this year in its 10th installment and taking place in Singapore). There have been quite a few interesting talks regarding practical security applications.

Hao and Clarke have analyzed a multi-factor authenticated key exchange protocol (using passwords, tokens, and biometric data) and have shown it to be insecure once only one of the authentication factors (in this case the password) is learned by an attacker. As similar multi-factor authentication protocols have been shown to be insecure in the past, it seems that the design of such protocols is trickier as one would expect.

Another work by Nguyen et al. analyzed the security of an animated CAPTCHA scheme and showed with successful attacks that the introduction of animation does not improve the security of such systems.

Apart from giving the first keynote talk on 10 years of ACNS (and an outlook to the next 10 years), Moti Yung (currently Research Scientist with Google) presented joint work with Ben-David et al. on extending current one-time password (OTP) systems to counter more powerful man-in-the-middle (MITM) attacks (current OTP systems are susceptible to active MITM attacks). Their proposed extended OTP (XOTP) systems takes some additional contextual information about the communication channel into account, which must be recognized by the communicating parties and which must differ for each communication session. They also propose to use smartphones as OTP generators (and use their wireless communication capabilities as a means to convey the OTP) in order to relieve users from carrying around a number of custom-build OTP generators from a number of different companies.

Zhang et al. propose to merge public-key encryption and identity-based encryption to add a feature of key escrow (which would usually conflict with non-repudiation). Their basic idea is to employ the user's PKI certificate as an identity in IBE to generate a second (escrowed) key pair. All traditional PKI mechanisms (like certificate validation and revocation) can still be applied as usual and the new system (called RIKE for Revocable Identities to Support Key Escrow) can be used with little changes from a traditional PKI.

Mueller et al. presented the implementation of platform independent full disk-encryption (called TreVisor) which utilizes many features of advanced 64-bit CPUs (like VT-x/VT-d and AES-NI) and which is resistant to both DMA-attacks and cold-boot attacks.

Study Group: Side-channels and PUFs

The last study group was chaired by Simon Hoerder and Philipp Grabher where the focus was on selected topics of Physically Unclonable Functions (PUFs). So what is the big deal with these PUFs? A PUF is a physical structure, in which, a unique challenge-response pair depends on manufacturing variations. The challenge-response pair is unique for each chip and can not be controlled during the manufacturing process, i.e., when it is used in a clever way, it can be useful, for instance, for authentication purposes. In this case each chip has some kind of unique "fingerprint". That's the most common way of using PUFs, e.g., as lightweight authentication mechanism in RFID tags.

In the first part, Simon introduced the basic definition of PUFs and definitions of PUF categories, like Strong PUFs, Controlled PUFs and Weak PUFs. Following the paper "Modelling Attacks on Physical Unclonable Functions" by Ulrich Rührmair, Frank Sehnke, Jan Sölter and Gideon Dror, Simon presented attacks on selected delay-based PUFs. Considering different types of PUFs like Arbiter PUF, XOR Arbiter PUF, Lightweight Secure PUF, Feed-Forwared Arbiter PUFs and Ring Oscilator PUFs, it is possible to build a model, using machine learning algorithms like Support Vector Machine, Logistic Regression, Evolution Strategies. In other words, gathering enough challenge-response pairs from a PUF and apply certain machine learning algorithms it is possible to predict other challenge-response pairs without any further access to the physical structure.

The next paper "A Formal Foundation for the Security Features of Physical Functions" by Frederik Armknecht, Roel Maes, Ahmad-Reza Sadeghi, Francois-Xavier Standaert and Christian Wachsmann, introduced us to a formal approach of PUFs, e.g., we discussed topics like existential physical unclonability, selective physical unclonability and weak/strong unpredictability.

The second part covered by Philipp focused more on practical attacks on PUFs. The discussion was based on two papers: "Semi-invasive EM attack on FPGA RO PUFs and countermeasures" and "Side-Channel Analysis of PUFs and Fuzzy Extractor" both by Dominik Merli, Dieter Schuster, Frederic Stumpf and Georg Sigl. Although a good PUF design should remain resistant against invasive and semi-invasive attacks (any modification of the PUF structure should change its behaviour), the first paper shows that sometimes this case doesn't hold and, e.g., titled Ring Oscillator based PUF is vulnerable to semi-invasive electromagnetic (EM) analysis attacks. In the second paper, the threat of side-channel attacks is being discussed when mounted on various PUF implementations.

All in all, Physically Unclonable Functions is an active filed of research, and there is not doubt that we see in the future many more interesting results both in theoretical as well as in practical implementations.

Study Group: Proving Correctness of a Shuffle

Today David and Essam talked about shuffle proofs. These allow to prove that a shuffle and re-randomisation of a list of ciphertexts was done correctly. The main application is e-voting, where several hosts in a so-called mix net sequentially shuffle and re-randomise ciphertexts containing the votes. Shuffle proofs ensure that no host can tamper with the votes. As usual, the requirements for shuffle proofs are completeness, soundness, and zero-knowledge. Most proofs are based on (semi-)homomorphic cryptosystems such as ElGamal that allow to re-randomise a ciphertext without knowing the cleartext.

In the last millennium, Sako and Kilian presented a cut-and-choose implementation of shuffle proofs: The prover shuffles the input ciphertext list X once more to get Z, and the verifier ask to see either the randomness used, or the randomness that would be used to shuffle X to Z. The correct response to both queries allows to compute the randomness for shuffling X to Y, which reveals a cheating prover with probability 1/2. Zero-knowledge follows from the fact that both replies on their own are independent on randomness used to shuffle X to Y.

More recently, Wikström presented a more efficient solution using extended Pedersen commitments, Schnorr-like protocols, and batch proof techniques. Extended Pedersen commitments allow to commit to a vector in only one group element. The protocol works in two phases. In an offline phase, the prover commits to a random permutation as a matrix and proves it be correct. Later, the provers shuffles the input ciphertext list according to the committed permutation and proves having done so.

At Eurocrypt 2012, Bayer and Groth presented another solution combining similar techniques, Groth's earlier work on sublinear size arguments and algebraic techniques like FFT and the Schwartz-Zippel lemma. An implementation of their protocol can prove the correctness of a shuffle of 100'000 ciphertext in 2 minutes.