# Seminar 2011

A Special Set of Additive Differences with Application to the Differential Analysis of ARX

2pm Wednesday December 14th, Campus Kirchberg E212, LACS seminar held by Vesselin Velichkov from ESAT/SCD/COSIC, K.U.Leuven

In this talk we investigate the differential properties of cryptographic algorithms based on the operations modular addition, bit rotation and XOR (ARX). More specifically, we focus on estimating the probabilities of differentials, based on additive differences, over sequences of ARX operations.

Previous results provide methods for the exact computation of the probability with which differences propagate through separate ARX components. However, those methods do not scale very well when applied to multiple ARX operations. We address this problem by taking a different approach. We do not calculate the exact differential probability, but instead we multiply the differential probabilities of several ARX operations in order to estimate the total probability. To avoid that this estimation differs significantly from the actual probability, we introduce a new type of difference, called UNAF (unsigned non-adjacent form).

A UNAF is a set of specially chosen additive differences. We analyze the propagation of UNAF differences through the ARX operations. We define the corresponding probabilities and propose methods for their computation using S-functions. The practical application of UNAF differences is demonstrated on stream cipher Salsa20. We first show that using UNAF differences we are able to make more accurate estimations of the probabilities of differentials over multiple rounds of Salsa20. Then we describe a key-recovery attack on Salsa20 reduced to five rounds.

This talk is based on results obtained in collaboration with Nicky Mouha, Christophe De Canni\'{e}re and Bart Preneel.

On the Differential Analysis of ARX

11:00am Wednesday December 14th, Campus Kirchberg E212, LACS seminar held by Vesselin Velichkov from ESAT/SCD/COSIC, K.U.Leuven

Many cryptographic primitives are built using the operations modular addition, bit rotation and XOR (ARX). The advantage of using these operations is that they are very fast when implemented in software. At the same time, when they are combined they provide desirable cryptographic properties such as diffusion and non-linearity.

Although ARX algorithms are widely used in practice, general methods for the analysis of their cryptographic properties are lacking. In particular, there does not exist a general methodology for assessing the security of ARX algorithms against one of the most powerful cryptanalytic techniques - differential cryptanalysis. In this talk we present the first general framework for the differential analysis of ARX. It is based on the concept of S-functions and allows for the exact computation of the probabilities with which differences propagate through the ARX operations. We demonstrate that the S-function framework is flexible, extensible and easy to apply in an automatic way.

In the first part of the talk we apply the S-function framework to confirm two known results: the XOR differential probability of modular addition and the additive differential probability of XOR. The difference with previous approaches is that we are able to obtain the results in a fully automatic way. In the second part of our talk we extend the S-function framework to handle the case in which differences propagate through a sequence of modular addition, bit rotation and XOR seen as a single operation - ARX. We define the additive differential probability of ARX and propose a method for its exact computation using S-functions. We conclude by briefly outlining a few more applications of S-functions.

This talk is based on results obtained in collaboration with Nicky Mouha, Christophe De Canni\'{e}re and Bart Preneel.

PhD Defense - Analysis of Resynchronization Mechanisms of Stream Ciphers

11:30pm Friday November 25th, Campus Kirchberg Salle des Conseils, LACS PhD defense of Deike Priemuth-Schmid

Jury

A.-Prof.  Dr. Volker Müller, UL, chairman

Dr. Ralf-Philipp Weinmann, UL, vice-chairman

A.-Prof. Dr. Alex Biryukov, UL, supervisor

Prof. Dr. Stefan Lucks, University Weimar, Germany, member

A.-Prof. Dr. Frederik Armknecht, University Mannheim, Germany, member

Stream ciphers are cryptographic primitives belonging to symmetric key cryptography to ensure data confidentiality of messages sent through an insecure communication channel. This thesis presents attacks on several stream ciphers, especially against their initialization methods.

The first targets are the stream ciphers Salsa20 and Trivium. For both ciphers slid pairs are described. Salsa20 can be distinguished from a random function using only the slid pair relation. When a slid pair is given for Salsa20 then both secret keys can be recovered immediately if the nonces and counters are known. Also an efficient search for a hidden slid pair in a large list of ciphertexts is shown. The efficiency of the birthday attack can be increased twice using slid pairs. For the cipher Trivium a large related-key class which produces identical keystreams up to a shift is presented.

Then the resynchronization mechanism of the stream ciphers SNOW~3G and SNOW~2.0 is analyzed. Both ciphers are simplified by replacing all additions modulo $2^{32}$ with XORs. A known IV key-recovery attack is presented for SNOW~3G$^{\oplus}$ and SNOW~2.0$^{\oplus}$ where both ciphers have no feedback from the FSM. This attack works for any amount of initialization clocks. Then in both ciphers the feedback from the FSM is restored and the number of 33 initialization clocks is reduced. Chosen IV key-recovery attacks on SNOW~3G$^{\oplus}$ with 12 to 16 initialization clocks and SNOW~2.0$^{\oplus}$ with 12 to 18 initialization clocks are shown.

In a similar way versions of the stream cipher K2 are attacked. This cipher is simplified by replacing all additions modulo $2^{32}$ with XORs as well. Chosen IV key-recovery attacks on versions with reduced initialization clocks from five to seven out of 24 are presented. For the version with seven initialization clocks also a chosen IV distinguishing attack is shown.

The last part deals with a linear key-IV setup and known feedback polynomials of the shrinking generator. It is shown that this linear initialization results in a very weak cipher as only a few known IVs are required to recover the secret key. The original design of the shrinking generator does not include any initialization method so the initial state was assumed to be the secret key.

On Constructing Homomorphic Encryption Schemes from Coding Theory

10:00am Friday November 25th, Campus Kirchberg E212, LACS seminar held by Frederik Armknecht  from Univ. Mannheim

In this talk, we investigate the construction of homomorphic encryption schemes where the security can be reduced to the hardness of decoding problem. We show that such schemes are indeed possible by presenting a natural construction principle. Interestingly, these possess several non-standard positive features. First, they are not restricted to linear homomorphism but  allow for evaluating multivariate polynomials up to a fixed (but arbitrary) degree d on encrypted field elements. Second, they can be instantiated with various error correcting codes, even for codes with poor correcting capabilities. Third, depending on the deployed code, one can achieve very efficient schemes. As a concrete example, we present an instantiation based on Reed-Muller codes where for d=2 and 3 and security levels between 80 and 128 bits, all operations take less than a second
(after some pre-computation).

However, our analysis reveals also limitations on this approach. For structural reasons, such schemes cannot be public-key, allow for a limited number of encryptions only, and cannot be combined with the bootstrapping technique. We argue why such schemes are nonetheless useful in certain application scenarios and discuss future directions on how to overcome these issues.

10:30am Thursday October 20th, Campus Kirchberg E212, LACS seminar held by Jean-Camille Birget from Rutgers University, USA

In a graphical password, the user is presented with an image; the password consists of a sequence of points in the image, that the user clicks on. In order to make it possible to hash graphical passwords, a "robust" discretization is needed (i.e., a discretization that produces the same output when the click points vary within some tolerance). Graphical passwords seek to exploit humans' spatial and visual memory. Another type of graphical passwords will be presented, that offers some resistance to shoulder-surfing.

References for the talk:  Graphical passwords project web page --   http://clam.rutgers.edu/~birget/grPssw/index.html

Computing Cryptographic Pairings at the 128-Bit Security Level

2:30pm Tuesday October 18th, Campus Kirchberg E212, LACS seminar held by Jean-Luc Beuchat from Tsukuba University, Japan

Originally introduced in cryptography by Menezes, Okamoto & Vanstone (1993) then Frey & RÃƒÂ¼ck (1994) to attack the discrete logarithm problem over a particular class of elliptic curves, pairings have since then been put to a constructive use in various useful cryptographic protocols such as short digital signature or identity-based encryption. However, evaluating these pairings relies heavily on finite field arithmetic, and their computation is still expensive. Developing optimized software libraries and hardware accelerators is therefore crucial.
In this talk, we will present hardware and software architectures designed to accelerate the computation of the Tate pairing on
supersingular (hyper)elliptic curves. Our implementations satisfy the  recommended security level of 128 bits.

#### PhD Defense - Security of RFID protocols

14:00pm Tuesday September 27th, Campus Kirchberg room C02, LACS PhD defense of Ton van Deursen

Jury

Prof. Dr. Peter Ryan, chairman

Prof. Dr. Sjouke Mauw, supervisor

Prof. Dr. Gildas Avoine, Université Catholique de Louvain, member

Prof. Dr. Mark Ryan, University of Birmingham, member

Radio-frequency identification (RFID) is a technology that uses radio waves to exchange data between RFID readers and tags. The low manufacturing costs and small size as well as the lack of need of a power source make RFID tags useful in many applications, but also impose a strong need for secure RFID protocols.

The first part of this thesis considers the analysis of untraceability of RFID protocols. Informally, untraceability ensures that an attacker cannot recognize RFID tags with which he has communicated in the past. We start by designing a formal syntax and semantics for security protocols. Within our formalization, one can precisely describe RFID protocols and systematically explore their execution traces. We define untraceability as a property on the traces of a protocol. Our definition requires that each trace in which the adversary could possibly deduce that a tag occurs twice, can also be understood as a trace in which two different tags occur.

The academic literature provides an abundance of RFID protocols designed to satisfy untraceability. We find untraceability flaws in a number of published RFID protocols. We introduce a categorization of these flaws comprising attribute acquisition attacks, man-in-the-middle attacks, insider attacks, compositionality attacks, and pseudonym-based attacks.

We then turn our attention to computational proof models for untraceability. We investigate the relation between two categories of computational proof models. The first category of computational proof models describes untraceability as the inability of the adversary to distinguish different tags. The second category defines untraceability as the attacker's inability to predict the messages sent by the tag. We show that the two classes of definitions are incomparable. Furthermore, we show that a category of public-key based RFID protocols is susceptible to insider attacks.  As a result, we extend an existing computational proof model with insider attackers. Finally, we propose a provably untraceable and authenticating RFID protocol based solely on elliptic-curve operations.

The second part of this thesis is concerned with authentication of RFID protocols. Authentication ensures that agents cannot be impersonated. We categorize authentication attacks into algebraic replay attacks, man-in-the-middle attacks, compositionality attacks, and cryptanalytic attacks. For each of these categories we give specific attacks on protocols from the academic literature.

The third part of this thesis deals with formalizing ownership in RFID systems as well as related security properties. In dynamic environments where RFID tags are exchanged, sold, or traded, the owner of a tag may change. Secure ownership transfer ensures that ownership of the tag can be securely handed over to the new owner. Within our security protocol framework, we define secure ownership, exclusive ownership, secure ownership transfer, and desynchronization resistance.

For all of these definitions, we show how they can be applied by exhibiting an attack on a published protocol.

The fourth part of this thesis describes the generic problem of recovering memory structures of systems. RFID tags often have a small portion of memory that can be used by the RFID application. One could repeatedly dump this memory and annotate each dump with the data suspected to be encoded on the tag. We define the carving problem as recovering the structure of the memory, based on this attributed dump set. We design and implement algorithms to find commonalities and dissimilarities and apply them to an RFID system deployed in Luxembourg.

New Constructions of (Time-Selective) Convertible Undeniable Signatures

10:30am Thursday September 15th, Campus Kirchberg E212, LACS seminar held by Duncan S. Wong from City University of Hong Kong

A convertible undeniable signature scheme allows a signer to confirm or disavow a non-self-authenticating signature and also convert a valid one to a conventional publicly verifiable signature. Existing schemes either require the signer to be stateful, or have their security based on the random oracle assumption, or result in getting a large converter. In this work we propose a new construction, which supports both selective and universal conversion, and is provably secure in the standard model. The scheme has the shortest signature and the smallest converters even when compared with existing schemes secure in the random oracle model. We also show that the scheme can be further extended to an efficient designated confirmer signature. A time-selective convertible undeniable signature scheme has an additional time-selective converter which converts all undeniable signatures corresponding to a specific time period to publicly verifiable ones. The security of existing schemes relies on a strong and interactive assumption called xyz-DCAA in random oracle model or several hash function assumptions in the generic group model. For some of them, the converter size for each time period grows linearly or logarithmically with the number of previous time periods. In the second part of this talk, we propose a new construction in which all the converters (i.e. time-selective, selective and universal) are of constant size. In particular, the time-selective converter for each time period has only one group element, no matter how many previous time periods there are already. The security of this new construction is proved in the random oracle model based on non-interactive assumptions.

A Hardware Processor Supporting Elliptic Curve Cryptography on RFID Tags for Less Than 9kGEs

11:00am Friday September 9th, Campus Kirchberg E212, LACS seminar held by Erich Wenger from Graz University of Technology

Differential power analysis is a powerful cryptanalytic technique that exploits information leaking from physical implementations of cryptographic algorithms to mount efficient key recovery attacks. During the two last decades numerous variations of the original principle have been published. In particular, the univariate case, where a single instantaneous leakage is exploited, has attracted much research effort. A previous work from Mangard et al. analysed the asymptotic equivalence of several univariate differential power analysis attacks. It is shown that the statistical tools involved in these attacks only differ in terms that become key-independent once properly estimated. In this paper, we first extend this observation and show that several univariate side channel attacks are not only asymptotically equivalent, but can also be rewritten one in function of the other, only by changing the leakage model used by the adversary. In particular, we show that most univariate differential power analysis attacks proposed in the literature can be expressed as correlation power analyses with different leakage models. This result emphasizes the importance of choosing a good model, namely a model as close as possible to the actual leakage function. As such a model is not always available to the adversary, we also discuss and evaluate side channel attacks that involve no leakage model but rely on some general assumptions about the leakage function. Our experiments show that such attacks, named robust, are a valuable alternative to the univariate differential power analyses. They only loose bit of efficiency in case a perfect model is available to the adversary, and gain a lot in case such information is not available.

Univariate Side Channel Attacks and Leakage Modeling

11:20am Wednesday June 29th, Campus Kirchberg E212, LACS seminar held by Emmanuel Prouff from Oberthur Technologies

Differential power analysis is a powerful cryptanalytic technique that exploits information leaking from physical implementations of cryptographic algorithms to mount efficient key recovery attacks. During the two last decades numerous variations of the original principle have been published. In particular, the univariate case, where a single instantaneous leakage is exploited, has attracted much research effort. A previous work from Mangard et al. analysed the asymptotic equivalence of several univariate differential power analysis attacks. It is shown that the statistical tools involved in these attacks only differ in terms that become key-independent once properly estimated. In this paper, we first extend this observation and show that several univariate side channel attacks are not only asymptotically equivalent, but can also be rewritten one in function of the other, only by changing the leakage model used by the adversary. In particular, we show that most univariate differential power analysis attacks proposed in the literature can be expressed as correlation power analyses with different leakage models. This result emphasizes the importance of choosing a good model, namely a model as close as possible to the actual leakage function. As such a model is not always available to the adversary, we also discuss and evaluate side channel attacks that involve no leakage model but rely on some general assumptions about the leakage function. Our experiments show that such attacks, named robust, are a valuable alternative to the univariate differential power analyses. They only loose bit of efficiency in case a perfect model is available to the adversary, and gain a lot in case such information is not available.

#### Physical Security of Cryptographic Algorithm Implementations

14:00pm Wednesday June 29th, Campus Kirchberg room A02, LACS PhD defense of Ilya Kizhvatov

This thesis deals with physical attacks on implementations of cryptographic algorithms and countermeasures against these attacks. Physical attacks exploit properties of an implementation such as leakage through physically observable parameters (side-channel analysis) or susceptibility to errors (fault analysis) to recover secret cryptographic keys. In the absence of adequate countermeasures such attacks are often much more efficient than classical cryptanalytic attacks. Particularly vulnerable to physical attacks are embedded devices that implement cryptography in a variety of security-demanding applications.

In the area of side-channel analysis, this thesis addresses attacks that exploit observations of power consumption or electromagnetic leakage of the device and target symmetric cryptographic algorithms (at the notable example of the Advanced Encryption Standard (AES)). First, this work proposes a new combination of two well-known techniques of such attacks: differential side-channel analysis and side-channel collision attacks. The combination is more efficient than each of the attacks individually. As a further improvement, new dimension reduction techniques for side-channel acquisitions are introduced for side-channel collision detection and compared using an information-theoretic metric. Second, this work studies attacks exploiting leakage induced by microprocessor cache mechanism. We present an algorithm for cache-collision attacks that can recover the secret key in the presence of uncertainties in cache event detection from side-channel acquisitions, which may happen in a noisy measurement environment. Third, practical side-channel attacks are discovered against the AES engine of the AVR XMEGA, a recent versatile microcontroller for a variety of embedded applications.

In the area of fault analysis, this thesis extends existing attacks against the RSA digital signature algorithm implemented with the Chinese remainder theorem to a setting where parts of the signed message are unknown to the attacker. The new attacks are applicable in particular to the randomized ISO/IEC 9796-2 encoding variant used in the EMV standard, and to the PKCS\#1 v1.5 standard in the setting when the message is totally unknown. Both standards are widely used in modern smart card applications.

In the area of countermeasures, this work proposes a new algorithm for random delay generation in embedded software. Random delays can be inserted into the execution flow of a cryptographic algorithm to break synchronization in physical attacks and therefore increase their complexity. The new algorithm is based on the idea of generating individual random delays non-independently. It is more efficient than the previously suggested algorithms since it introduces more uncertainty for the attacker with less performance overhead.The results presented in this thesis are practically validated in experiments with general-purpose 8-bit AVR and 32-bit ARM microcontrollers that are used in many embedded devices.

Privacy-Oriented Cryptography for Social Clouds

14:30pm Thursday May 19th, Campus Kirchberg E212, LACS seminar held by Mark Manulis from Technische Universität Darmstadt/CASED

Users increasingly rely on the social cloud'' for storing and sharing personal information, for establishing new contacts, and for interacting with their friends and colleagues. Even though social media platforms may differ in the target audience, in the nature of collected and disseminated information, and in services offered to the users, there are several building blocks that enable user's social interactions and are deployed by the majority of these platforms. Designing these building blocks in a secure and privacy-preserving way is of utmost importance, should potential damage from the misuse of user-provided content in the existing social cloud'' be averted.

Due to the absence of appropriate models and security/privacy definitions it is, so far, impossible to judge, whether a proposed protection mechanism is suitable or not, whether it can be applied in general, or is tailored to a specific social media platform. Instead of using ad-hoc'' and best practice'' solutions with questionable guarantees, it is advisable to strive for a more formal treatment of the underlying building blocks by providing sophisticated  security/privacy definitions and designing solutions amenable to formal reasoning and security proofs.

In the first part of my talk I will focus on the management of personal user profiles. User profiles serve as a main building block for most social media platforms. I will introduce a formal cryptographic model forprivate user profiles, supporting generation of the digital content owned by the user and its controlled disclosure to other users of the social community. I will present formal definitions of security and privacy that reflect the natural expectations on private profiles. I will further describe two general solutions based on different encryption techniques and highlight their trade-offs from the security/privacy and complexity point of view. These solutions do not require any specific network infrastructure or any trusted third parties. The provided analysis takes into account statistics of several real-world social media platforms.

The second part of my talk will address the problem of discovery of common social contacts, for which I will introduce the first privacy-friendly practical solution that lets two users, on input their respective contact lists, learn their common contacts (if any), and nothing else. The proposed protocol prevents arbitrary list manipulation by means of contact certification, and guarantees user authentication and revocability. I will explain why current approaches such as private set intersection or anonymous credentials, although being related, do not provide an appropriate solution to this problem. I will discuss the modeling of contact-hiding security that private contact discovery should provide. I will also highlight efficiency considerations for the proposed protocol that does not require involvement of any trusted third parties and can be deployed in resource-constraint environments.

The content of this talk is based on the recent results from FC 2011/RLCSP, ASIACCS 2011, and ACNS 2011.

#### Adaptive Pseudo-Free Groups and Applications

10:30am Friday May 6th, Campus Kirchberg E212, LACS seminar held by Dario Fiore from ENS Paris, France

A computational group is {\em pseudo-free} if an adversary cannot find solutions in this group for equations that are not trivially solvable in the free group. This notion was put forth by Rivest at TCC 2004 as a unifying abstraction of multiple group-related hardness assumptions commonly used in cryptography. Rivest's conjecture that the RSA group is pseudo-free had been settled by Micciancio for the case of RSA moduli that are the product of two safe primes. This result holds for a static setting where the adversary is only given the description of the group (together with a set of randomly chosen generators) and has to come up with the equation and the solution.

In this paper we explore a powerful extension of the notion of pseudo-freeness. We identify, motivate, and study pseudo-freeness in face of {\em adaptive} adversaries who may learn solutions to other non-trivial equations before having to solve a new non-trivial equation.

We present a novel, carefully crafted definition of {\em adaptive} pseudo-freeness that walks a fine line between being too weak and being unsatisfiable. We show that groups that satisfy our definition yield, via a generic construction, digital and network coding signature schemes.

Finally, we obtain concrete constructions of such schemes in the RSA group by showing this group to be adaptive pseudo-free.  In particular, we demonstrate the generality of our framework for signatures by showing that most existing schemes are instantiations of our generic construction.

This is a joint work with Dario Catalano and Bogdan Warinschi.

#### Uniqueness, Identity and Privacy

11:00 am Wednesday February 23rd, Salle Paul Feidert, Campus Kirchberg, LACS seminar held by Prof Bart Preneel from K.U.Leuven, Belgium

Prof Preneel is the president of the International Association for Cryptologic Research (IACR), project manager of NoE ECRYPT II and the head of COSIC, one of the largest research groups in cryptology/security in Europe.

Technological developments bring a shrinking scale of electronics but also lead to an increasing variance of hardware processes and an ever growing resolution to distinguish objects.  These trends make it easier to uniquely identify all objects and humans; in combination with the progress in information and communication technologies this opens the door to efficient and continuous tracking of all objects and people.  There is an increasing concern on the implications of these developments on our society and in particular on privacy.  Cryptographic techniques can act as a counterbalance by creating solutions such as anonymous communications, pseudonyms and unlinkeable credentials.  However, it is not clear that they will be effective: the intertwining of logical and physical security presents a substantial technological challenge; in addition, the adoption of these technologies is hampered by economic and socio-political factors (cost, risk of abuse).  This talk will try to explore these issues with an emphasis on a technological perspective.

#### Error-Tolerance in Trace-Driven Cache Collision Attacks

14:15pm Tuesday February 22nd, Campus Kirchberg E212, LACS seminar held by Jean-François Gallais from LACS, University of Luxembourg

We present enhancements of the trace-driven cache collision attack against embedded AES implementations presented at WISA 2010. First, we improve the attack to reduce the remaining exhaustive search complexity from 232 to at most 10 AES encryptions. Second, we extend the tolerance to errors in cache event detection to the full attack and show that the attack is efficient even for the significant error
probabilities. Finally, we show that previous univariate models for estimating attack complexity are not good, and present the multivariate model which is  easy to simulate. Our attack is comparable to DPA, while being of a different nature, and consequently defeats some DPA countermeasures. We also show by further explorations on an ARM platform that cache events are distinguishable in practice.

The paper with the same title (co-authored with Ilya Kizhvatov) will be presented at COSADE 2011.

#### Boomerang Attacks on BLAKE-32

11:30am Monday February 7th, Campus Kirchberg E212, LACS seminar held by Arnab Roy from LACS, University of Luxembourg

We present high probability differential trails on 2 and 3 rounds of BLAKE-32. Using the trails we are able to launch boomerang attacks on up to 8 round-reduced keyed permutation of BLAKE-32. Also, we show that boomerangs can be used as distinguishers for hash/compression functions and present such distinguishers for the compression function of BLAKE-32 reduced to 7 rounds. Since our distinguishers on up to 6 round-reduced keyed permutation of BLAKE-32 are practical (complexity of only $2^{12}$ encryptions), we are able to find boomerang quartets on a PC.