Cryptography and Security: From Theory to Applications

If you are reading this text it is probably because you know Jean-Jacques, my Dad. While you know him professionally or more personally, I though it was a good idea to present him to you from the prism of his son. I will restrict myself to the scientifical part of our relationship, the rest being kept private.

My scientifical education started very early. Indeed, when I didn’t want to eat something as a child, he cut the food in the shape of rocket and other devices. He used this stratagem because he knew I was interested in technical stuffs and DIY’s. I was eager to leave school as soon as possible because his office was full of computer drawings and therefore working in real life appeared to me as very entertaining. Those drawings were actually Hoffman-Singleton graphs and Ulam spiral, which I didn’t know at that time.

Smart card technologies have had a huge impact on the development of cryptographic techniques for commercial applications. The first cryptographic smart card was introduced in 1979. It implemented the

Telepass 1

one-way function using 200 bytes! Next came smart cards with secret-key and public-key capabilities, respectively in 1985 and 1988. Implementing an RSA computation on a smart card was (and still is) a very challenging task. Numerous tips and tricks were used in the design of the resulting smart-card chip P83C852 from Philips using the

CORSAIR

crypto-coprocessor [1,12]. Among them was a new algorithm for the modular multiplication of two integers, the

Quisquater’s multiplication algorithm

[10,11]. This algorithm is also present in the subsequent crypto-coprocessors, namely the

FAME

crypto-coprocessor [4] and its various extensions.

This paper surveys research jointly with Jean-Jacques Quisquater, primarily the joint work on DES, on exhaustive key search machines, and on information hiding.

We revisit the problem of finding key collisions for the DES block cipher, twenty two years after Quisquater and Delescaille demonstrated the first DES collisions. We use the same distinguished points method, but in contrast to their work, our aim is to find a large number of collisions. A simple theoretical model to predict the number of collisions found with a given computational effort is developed, and experimental results are given to validate this model.

In this article we generalize the concept of line digraphs to line dihypergraphs. We give some general properties in particular concerning connectivity parameters of dihypergraphs and their line dihypergraphs, like the fact that the arc connectivity of a line dihypergraph is greater than or equal to that of the original dihypergraph. Then we show that the De Bruijn and Kautz dihypergraphs (which are among the best known bus networks) are iterated line digraphs. Finally we give short proofs that they are highly connected.

KeeLoq is a lightweight block cipher which is extensively used in the automotive industry [7,8,14,15]. Its periodic structure, and overall simplicity makes it vulnerable to many different attacks. Only certain attacks are considered as really “practical” attacks on KeeLoq: the brute force, and several other attacks which require up to 2

16

known plaintexts and are then much faster than brute force, developed by Courtois

et al.

, [10] and (faster attack) by Dunkelman

et al.

[1].

On the other hand, due to the unusually small block size, there are yet many other attacks on KeeLoq, which require the knowledge of as much as about 2

32

known plaintexts but are much faster still. There are many scenarios in which such attacks are of practical interest, for example if a master key can be recovered, see Section 2 in [11] for a detailed discussion. The fastest of these attacks is an attack by Courtois, Bard and Wagner from [10] that has a very low complexity of about 2

28

KeeLoq encryptions on average. In this paper we will propose an improved and refined attack which is faster both on average and in the best case.

We also present an exact mathematical analysis of probabilities that arise in these attacks using the methods of modern analytic combinatorics.

KeeLoq is a lightweight cipher that is widely used in car locks. The fastest known attack on KeeLoq is a Slide-Determine attack by Bard, Courtois and Wagner with a complexity of 2

28

KeeLoq computations [11]. However this attack requires the knowledge of the whole code-book of 2

32

known plaintexts, which is totally unrealistic. The first attack on KeeLoq with a far more realistic requirement of 2

16

known plaintexts was proposed by Courtois, Bard and Wagner [10,11] and can be used to clone KeeLoq devices in practice. Later, Dunkelman

et al.

proposed another faster attack in this setting [2].

From the practitioner point of view, the question remains however what is the best attack in the weakest possible setting, when the attacker is given only two (or a bit more) known plaintexts (one does not suffice due to the key size being larger than block size). In this case, the fastest known attack on KeeLoq remains brute force, which is actually feasible and reportedly criminals implement this attack in FPGA to steal cars, see [7]. In this paper we show that there is a better attack. More precisely, we show that due to a self-similarity property of KeeLoq the exhaustive key search process can be substantially accelerated and the security of KeeLoq is strictly lower as soon as the adversary disposes of two

chosen

plaintexts. Then we get an attack faster then brute force.

Independently, these attacks can be improved by a factor of 2 with some storage. Due to the protocol used, our attacks are realistic and allow to clone a KeeLoq entry devices more easily than previously thought.

In this paper we introduce a new general and powerful attack on block ciphers, a self-similarity attack. It is strictly more general than sliding attacks. For KeeLoq, but also for DES, self-similarity allows to speed up the brute force attack on the cipher. Both in case of DES and KeeLoq brute force is the most realistic attack known, and it can be improved by a self similarity attack, at the price of a chosen plaintext attack. Only 2 chosen plaintexts are needed in all these attacks.

In this paper we study how to generate new secret key block ciphers based on the AES and Feistel constructions, that allow arbitrary large input/output lengths while maintaining the ability to select -a priori- arbitrary security levels. We start from the generation of block ciphers that are simple balanced Feistel constructions that exploit the pseudorandomness of functions, namely the AES, as round function. This results in block ciphers with inputs and outputs of size 256 bits,

i.e.

, that are doubled compared to the AES. We then extend this principle following the “Russian Doll” design principle to build block ciphers with (arbitrarily) larger inputs and outputs. As an example, we build block ciphers with an expected security in about 2

512

, or 2

1024

, instead of 2

128

for the classical AES with 128 key-bits. The expected security is not proven, but our constructions are based on the best known attacks against Feistel networks with internal random permutations, as well as some natural security assumptions. We study two configurations of assumptions, leading to two families of simple and efficient new block ciphers, which can thus be seen as candidate schemes for higher security.

Vaudenay’s padding oracle attacks are a powerful type of side-channel attack against systems using CBC mode encryption. They have been shown to work in practice against certain implementations of important secure network protocols, including IPsec and SSL/TLS. A formal security analysis of CBC mode in the context of padding oracle attacks in the

chosen-plaintext setting

was previously performed by the authors. In this paper, we consider the

chosen-ciphertext setting

, examining the question of how CBC mode encryption, padding, and an integrity protection mechanism should be combined in order to provably defeat padding oracle attacks. We introduce new security models for the chosen-ciphertext setting which we then use to formally analyse certain authenticated-encryption schemes, namely the three compositions: Pad-then-Encrypt-then-Authenticate (as used in particular configurations of IPsec), Pad-then-Authenticate-then-Encrypt, and Authenticate-then-Pad-then-Encrypt (as used in SSL/TLS).

Traceable signatures schemes were introduced by Kiayias, Tsiounis and Yung in order to solve traceability issues in group signature schemes. They wanted to enable authorities to delegate some of their detection capabilities to tracing sub-authorities. Instead of opening every single signatures and then threatening privacy, tracing sub-authorities are able to know if a signature was emitted by specific users only.

In 2008, Libert and Yung proposed the first traceable signature schemes proven secure in the standard model. We design another scheme in the standard model, with two instantiations based either on the

$\textsf{SXDH}$

or the

$\textsf{DLin}$

assumptions. Our construction is far more efficient, both in term of group elements for the signature, and pairing computation for the verification. Besides the “step-in” (confirmation) feature that allows a user to prove he was indeed the signer, our construction provides the “step-out” (disavowal) procedure that allows a user to prove he was not the signer.

Since list signature schemes are closely related to this primitive, we consider them, and answer an open problem: list signature schemes are possible without random oracles.

The 40 thieves realize that the fortune in their cave is vanishing. A rumor says that Ali Baba has been granted access (in the form of a certificate) to the cave but they need evidence to get justice from the Caliph. On the other hand, Ali Baba wants to be able to securely access to the cave without leaking any evidence. A similar scenario holds in the biometric passport application: Ali Baba wants to be able to prove his identity securely but do not want to leak any transferable evidence of, say, his date of birth.

In this paper we discuss the notion of offline non-transferable authentication protocol (ONTAP). We review a construction based on the GQ protocol which could accommodate authentication based on any standard RSA certificate. We also discuss on the fragility of this deniability property with respect to set up assumptions. Namely, if tamper resistance exist, any ONTAP protocol in the standard model collapses.

Digital signature security is classically defined as an interaction between a signer

, a verifier

and an attacker

$\mathcal{A}$

.

$\mathcal{A}$

submits adaptively to

a sequence of messages

m

1

,…,

m

q

to which

replies with the signatures

U

 = {

σ

1

,…,

σ

q

}. Given

U

,

$\mathcal{A}$

attempts to produce a forgery,

i.e.

a pair (

m

′,

σ

′) such that

and

$\sigma'\not\in U$

.

The traditional approach consists in hardening

against a large query bound

q

. Interestingly, this is

one specific way

to prevent

$\mathcal{A}$

from winning the forgery game. This work explores an alternative option.

Rather than hardening

, we weaken

$\mathcal{A}$

by preventing him from influencing

’s input: upon receiving

m

i

,

will generate a fresh ephemeral signature key-pair

, use

to sign

m

i

, erase

, and output the signature and a certificate on

computed using the long-term key

. In other words,

will only use his permanent secret

to sign inputs which are

beyond

$\mathcal{A}$

’s control

(namely, freshly generated public-keys). As the

are ephemeral,

q

 = 1 by construction.

We show that this paradigm, called

autotomic signatures

, transforms weakly secure signature schemes (secure against generic attacks only) into strongly secure ones (secure against adaptively chosen-message attacks).

As a by-product of our analysis, we show that blending public key information with the signed message can significantly increase security.

When embedding cryptographic tools in actual computing systems, it is important to ensure physical layer protection to cryptographic keys. A simple risk analysis shows that taking advantage of system (

i.e.

, hardware, software, network) vulnerabilities is usually much easier than cryptanalyzing the cryptographic primitives themselves. For-ward-secure cryptosystems, in turn, are one of the suggested protective measures, where private keys periodically evolve in such a way that, if a break-in occurs, past uses of those keys in earlier periods are protected.

Group signatures are primary privacy-preserving credentials that enable both, non-repudiation and abuser-tracing. In 2001, Song argued why key exposures may cause even greater concerns in the context of group signatures (namely, under the mask of anonymity within a group of other key holders). She then gave two examples of forward-secure group signatures, and argued their ad hoc properties based on the state of understanding of group signature security properties at that time (proper security models had not been formalized yet). These implementations are fruitful initial efforts, but still suffer from certain imperfections. In the first scheme for instance, forward security is only guaranteed to signers as long as the group manager’s private key is safe. Another scheme recently described by Nakanishi

et al.

for static groups also fails to maintain security when the group manager is compromised.

In this paper, we reconsider the subject and first formalize the notion of “fully forward-secure group signature” (FS-GS) in dynamic groups. We carefully define the correctness and security properties that such a scheme ought to have. We then give a realization of the primitive with quite attractive features: constant-size signatures, constant cost of signing/verifying, and at most polylog complexity of other metrics. The scheme is further proven secure in the standard model (no random oracle idealization is assumed).

We investigate public key encryption that allows the originator of a ciphertext to retrieve a “forgotten” plaintext from the ciphertext. This type of public key encryption with “backward recovery” contrasts more widely analyzed public key encryption with “forward secrecy”. We advocate that together they form the two sides of a whole coin, whereby offering complementary roles in data security, especially in cloud computing, 3G/4G communications and other emerging computing and communication platforms. We formalize the notion of public key encryption with backward recovery, and present two construction methods together with formal analyses of their security. The first method embodies a generic public key encryption scheme with backward recovery using the “encrypt then sign” paradigm, whereas the second method provides a more efficient scheme that is built on Hofheinz and Kiltz’s public key encryption in conjunction with target collision resistant hashing. Security of the first method is proved in a two-user setting, whereas the second is in a more general multi-user setting.

We describe and analyze the password-based key establishment protocol PACE v2 Integrated Mapping (IM), an evolution of PACE v1 jointly proposed by Gemalto and Sagem Sécurité. PACE v2 IM enjoys the following properties:

patent-freeness (to the best of current knowledge in the field);

full resistance to dictionary attacks, secrecy and forward secrecy in the security model agreed upon by the CEN TC224 WG16 group;

optimal performances.

The PACE v2 IM protocol is intended to provide an alternative to the German PACE v1 protocol, which is also the German PACE v2 Generic Mapping (GM) protocol, proposed by the German Federal Office for Information Security (BSI). In this document, we provide

a description of PACE v2 IM,

a description of the security requirements one expects from a password-based key establishment protocol in order to support secure applications,

a security proof of PACE v2 IM in the so-called Bellare-Pointcheval-Rogaway (BPR) security model.

Finding efficient countermeasures for cryptosystems against fault attacks is challenged by a constant discovery of flaws in designs. Even elements, such as public keys, that do not seem critical must be protected. From the attacks against RSA [5,4], we develop a new attack of DLP-based cryptosystems, built in addition on a lattice analysis [26] to recover DSA public keys from partially known nonces. Based on a realistic fault model, our attack only requires 16 faulty signatures to recover a 160-bit DSA secret key within a few minutes on a standard PC. These results significantly improves the previous public element fault attack in the context of DLP-based cryptosystems [22].

Along with the vast use of cryptography in security devices came the emergence of attacks like Electro-Magnetic analysis (EMA) where the measurement of the Electro-Magnetic (EM) waves radiated from an integrated circuit are used to extract sensitive information. Several research papers have covered EMA but very few have focused on the probes used. In this paper we detail an approach for analysing different probes for EMA. We perform the characterisation of several EM probes on elementary circuits like an isolated copper wire and silicon lines. We then illustrate how EM probes can be characterised based on data dependant information leakage of integrated circuits by doing measurements on a smart card like chip. We show that the latter results are in line with those obtained from the measurements on the elementary circuits, onto which detailed and more precise analyses can be carried.

Unprotected implementations of cryptographic primitives are vulnerable to physical attacks. While the adversary only needs to succeed in one out of many attack methods, the designers have to consider all the known attacks, whenever applicable to their system, simultaneously. Thus, keeping an organized, complete and up-to-date table of physical attacks and countermeasures is of paramount importance to system designers. This paper summarises known physical attacks and countermeasures on Elliptic Curve Cryptosystems. For implementers of elliptic curve cryptography, this paper can be used as a road map for countermeasure selection in the early design stages.

We propose a new countermeasure to protect block ciphers implemented in leaking devices, at the intersection between One-Time Programs and Boolean masking schemes. First, we show that this countermeasure prevents side-channel attacks of all orders during the execution of a protected block cipher implementation, given that some secure precomputations can be performed. Second, we show that taking advantage of the linear diffusion layer in modern block ciphers allows deriving clear arguments for the security of their implementations, that can be easily interpreted by hardware designers. Masking with randomized look up tables allows fast execution times but its memory requirements are high and, depending on the block cipher to protect, can be prohibitive. We believe this proposal brings an interesting connection between former countermeasures against side-channel attacks and recent formal solutions to cope with physical leakage. It illustrates the security vs. performance tradeoff between these complementary approaches and, as a result, highlights simple design guidelines for leakage resilient ciphers.

An important building block for many cryptographic systems is a random number generator. Random numbers are required in these systems, because they are unpredictable for potential attackers. These random numbers can either be generated by a truly random physical source (that is non-deterministic) or using a deterministic algorithm. In practical applications where relatively large amounts of random bits are needed, it is also possible to combine both of these generator types. A non-deterministic random number generator is used to provide a truly random seed, which is used as input for a deterministic algorithm that generates a larger amount of (pseudo-)random bits. In cryptographic systems where Physical Unclonable Functions (PUFs) are used for authentication or secure key storage, an interesting source of randomness is readily available. Therefore, we propose the construction of a FIPS 140-3 compliant random bit generator based on an SRAM PUF in this paper. These PUFs are a source of instant randomness, which is available when powering an IC. Based on large sets of measurements, we derive the min-entropy of noise on the start-up patterns of SRAM memories. The min-entropy determines the compression factor of a conditioning algorithm, which is used to extract a truly random (256 bits) seed from the memory. Using several randomness tests we prove that the conditioned seed has all the properties of a truly random string with full entropy. This truly random seed can be derived in a low cost and area efficient manner from the standard IC component SRAM. Furthermore, an efficient implementation of a deterministic algorithm for generating (pseudo-)random output bits will be proposed. Combining these two functions leads to an ideal way to generate large amounts of random data based on non-deterministic randomness.

This paper describes a new accumulate-and-add multiplication algorithm. The method partitions one of the operands and re-combines the results of computations done with each of the partitions. The resulting design turns-out to be both compact and fast.

When the operands’ bit-length

m

is 1024, the new algorithm requires only 0.194

m

 + 56 additions (on average), this is about half the number of additions required by the classical accumulate-and-add multiplication algorithm (

$\frac{m}2$

).

We discuss a recent cryptographic primitive termed

SIMPL system

, where the acronym stands for

SIM

ulation

P

ossible, but

L

aborious. Like Physical Unclonable Functions (PUFs), SIMPL systems are disordered, unclonable physical systems with many possible inputs and a complex input-output behavior. Contrary to PUFs, however, each SIMPL system comes with a publicly known, individual numeric description that allows its slow simulation and output prediction. While everyone can determine a SIMPL system’s output slowly by simulation, only its actual holder can determine the output fast by physical measurement. This added functionality allows new public key like protocols and applications.

But SIMPLs have a second, perhaps more striking advantage: No secret information is, or needs to be, contained in SIMPL systems in order to enable cryptographic security. Neither in the form of a standard digital key, nor as secret information hidden in the random, analog features of some hardware, as it is the case for PUFs. The security of SIMPL systems instead rests on (i) an assumption regarding their physical unclonability, and (ii) a computational assumption on the complexity of simulating their output. This provides SIMPL systems with a natural immunity against any key extraction attacks, including malware, side channel, invasive, and modeling attempts.

In this manuscript, we give a comprehensive discussion of SIMPLs as a cryptographic and security primitive. Special emphasis is placed on the different cryptographic protocols that are enabled by this new tool.

We introduce the use of asynchronous logic automata (ALA) for cryptography. ALA aligns the descriptions of hardware and software for portability, programmability, and scalability. An implementation of the A5/1 stream cipher is provided as a design example in a concise hardware description language, Snap, and we discuss a power- and timing-balanced cell design.

3-D integration presents many new opportunities for architects and embedded systems designers. However, 3-D integration has not yet been explored by the cryptographic hardware community. Traditionally, crypto co-processors have been implemented as a separate die or by utilizing one or more cores in a chip multiprocessor. These methods have their drawbacks and limitations in terms of tamper-resistance, side-channel immunity and performance. In this work we propose a new class of co-processors that are “snapped-on” to the main processor using 3-D integration, and we investigate their security ramifications. These 3-D co-processors hold many advantages over previous implementations. This paper begins with an overview of 3-D integration and its prior applications. We then outline security threat models relevant to crypto co-processors and discuss the advantages and disadvantages of using a dedicated 3-D crypto co-processor compared to traditional, commodity, off-chip crypto co-processors. We also discuss the performance improvements that can be gained from using a 3-D approach.

A privacy-preserving identity card is a personal device device that allows its owner to prove some binary statements about himself (such as his right of access to some resources or a property linked to his identity) while minimizing personal information leakage. After introducing the desirable properties that a privacy-preserving identity card should fulfill and describing two proposals of implementations, we discuss a taxonomy of threats against the card. Finally, we also propose for security and cryptography experts some novel challenges and research directions raised by the privacy-preserving identity card.

Java Card is a kind of smart card that implements one of the two editions, “

Classic Edition

” or “

Connected Edition

”, of the standard Java Card 3.0 [7]. Such a smart card embeds a virtual machine which interprets codes already romized with the operating system or downloaded after issuance. Due to security reasons, the ability to download code into the card is controlled by a protocol defined by Global Platform [3]. This protocol ensures that the owner of the code has the necessary authorization to perform the action. Java Card is an open platform for smart cards,

i.e.

able of loading and executing new applications after issuance. Thus, different applications from different providers run in the same smart card. Thanks to type verification, byte codes delivered by the Java compiler and the converter (in charge of giving a compact representation of class files) are safe,

i.e.

the loaded application is not hostile to other applications in the Java Card. Furthermore, the Java Card firewall checks permissions between applications in the card, enforcing isolation between them.

Location-aware technology and its applications are fundamental to ubiquitous computing. Essential to this technology is object localization and identification. RFID (radio frequency identification) technology has been shown to be very effective for identification and tracking applications in industry, transport, agriculture and health-care. However it can also be used for accurate object localization. Indeed RFID technology is ideally suited for such applications, and more generally for context-aware computing, because of the low cost, low power, light weight and endurance of RFID tags. In this article we study the security of RFID localization.

One concern in using cloud storage is that the sensitive data should be confidential to the servers which are outside the trust domain of data owners. Another issue is that the user may want to preserve his/her anonymity in the sharing or accessing of the data (such as in Web 2.0 applications). To fully enjoy the benefits of cloud storage, we need a confidential data sharing mechanism which is fine-grained (one can specify

who

can access

which classes

of his/her encrypted files), dynamic (the total number of users is not fixed in the setup, and any new user can decrypt previously encrypted messages), scalable (space requirement does not depend on the number of decryptors), accountable (anonymity can be revoked if necessary) and secure (trust level is minimized).

This paper addresses the problem of building a secure cloud storage system which supports dynamic users and data provenance. Previous system is based on specific constructions and does not offer all of the aforementioned desirable properties. Most importantly, dynamic user is not supported. We study the various features offered by cryptographic anonymous authentication and encryption mechanisms; and instantiate our design with verifier-local revocable group signature and identity-based broadcast encryption with constant size ciphertexts and private keys. To realize our concept, we equip the broadcast encryption with the dynamic ciphertext update feature, and give formal security guarantee against adaptive chosen-ciphertext decryption and update attacks.

We present a result related to encryption, shared storage and similarity. The new protocol for secure storage of information solves a recent problem of how multiple independent and non-communicating individuals/processes can store and retrieve the same file in a shared storage facility without the use of a key escrow facility. That is, we present a method in which each individual

i

stores the ciphertext

C

M

,

i

for the same message

M

in shared storage at different time with a protocol requiring

O

(1) ciphertext memory size (i.e., a ciphertext whose size is independent of the number of individuals). Though the individuals can “store” / create the ciphertext for

M

at different times without communicating with one another or having pre-shared secret data, they must also be able to decrypt the same ciphertext at different times without communicating directly or indirectly with one another. As will be noted in the Introduction, this problem is motivated by approaches used by cloud storage providers. We further extend the result by enhancing the technique to allow an individual

i

to store

$C_{M_i,i}$

where each

M

i

is similar, but possibly different, yet use less memory than storing multiple ciphertext of each messages.

The result has practical implications in privacy and shared storage as has recently been demonstrated by a regulatory complaint to a cloud storage provider. The result uses multiple techniques from both cryptography and coding theory.

Any non-singular plane cubic with a rational point is an elliptic curve, and is therefore birationally equivalent to a curve in Weierstraß form. Such a birational equivalence can be found using generic techniques, but they are computationally quite inefficient.

As early as 1928, Nagell proposed a much simpler procedure to construct that birational equivalence in the particular case of plane cubics, which is implemented in computer algebra packages to this day. However, the procedure fails in even characteristic. We show how the algorithm can be modified to work in any characteristic.

In this note we describe a cryptographic curiosity: readable messages that carry their own digital signature.

Biometrics are increasingly being deployed as solutions to the security problems of authentication, identification and to some extent, non-repudiation. Biometrics are also publicized by proponents to be more secure than conventional mechanisms such as passwords and tokens, while also being more convenient too since there is no need to remember passwords nor carry anything around. Yet the security of biometrics lies on the assumption that biometric traits are unique to an individual and are unforgeable; once this assumption is invalidated, the security of biometrics collapses. Therefore, it is crucial to ensure that biometric traits are indeed unforgeable. In scientific literature, proponents have invented different ways for liveness detection, in order to differentiate forged traits from real ones, based on the premise that forged traits should not have liveness. In this paper, we show that a celebrated capacitive fingerprint scanner with liveness detection claims, can be fooled by fake fingers produced by amateurs from cheap commercially available materials. This brings into question that a gap may exist between what scientific literature has proposed for liveness detection and the actual robustness of liveness-detecting fingerprint scanners available in the market against fake fingers.

In this note we study the structure and the behavior of inarticulate robots. We introduce a robot that moves by successive revolvings. The robot’s structure is analyzed, simulated and discussed in detail.