Security of Cryptographic Functions and Efficient Implementations

Status

This project started in October 2004 and ended in August 2007.

Researchers

• Prof. Dr. Ueli Maurer
• Johan Sjödin

Motivation

The goal of this project is to base the security of practical cryptographic schemes on weakened assumptions (which are hence more likely to hold). This is a general research goal in cryptography. We plan to study known and define new security properties of cryptographic functions like one-way functions, hash functions, pseudo-random generators, pseudo-random functions (PRF), pseudo-random permutations, and message authentication codes (MACs).

Objectives

The detailed objectives are listed below:

• Base the security of practical cryptographic schemes on weaker assumptions, thereby also improving the efficiency.
• State meaningful security definitions.
• Characterize the relations between the definitions.
• Propose constructions of functions with stronger properties than those involved in the construction.
• Ideally: provide a complete framework of security definitions and reductions between them.
• Propose concrete new cryptographic functions with higher security and new features.
• Progress on cryptographic functions targeted for on-chip hardware implementations.

Progress

Domain Extension of MACs

A fundamental security requirement for data transmission is integrity of data. Message authentication codes (MACs) are a well-known technique for assuring this. A main focus of our research has been on the question of transforming a fixed-input-length (FIL) MAC to the more practical relevant arbitrary-input-length (AIL) MAC. The assumption that the FIL-primitive is a MAC is much weaker than the commonly used assumption that the FIL-primitive is a pseudo-random function (PRF). In [1] we systematically study and propose a natural and general paradigm for constructing AIL-MACs from any FIL-MAC. The constructions which are considered are basicly the ones of iterating nature (which uses the FIL-MAC in a black-box manner). Our results are the following:

• A substantially simplified proof of the previous only known construction, the NI-construction (by An and Bellare).
• Several improvements of the NI-construction (less key material, better throughput, improved security, and AIL message space).
• New AIL-MAC constructions, Chain-Shift (CS) and Chain-Rotate (CR), which are essentially optimal in terms of efficiency and security. They also have the nice property that the messages can be processed on-line and in parallel.

In the same line of research we generalize the paradigm further in [2], by using a compressed output version of the FIL-MAC as building block (rather than the FIL-MAC itself). This introduces an interesting security/efficiency tradeoff. Taking this tradeoff into account, we present a new construction, called Double-Iterated (DI), which is superior to all previous constructions in the literature. It appears obvious that this construction is essentially optimal.

Luby-Rackoff Ciphers with Weak Round Functions

The Feistel-network is a popular structure underlying many block-ciphers -- like DES -- where the cipher is constructed from many simpler rounds, each defined by some function which is derived from the secret key.

Luby and Rackoff showed that the three round Feistel-network -- each round instantiated with a pseudorandom function secure against adaptive chosen plaintext attacks (CPA) -- is a CPA secure pseudorandom permutation, thus giving some confidence in the soundness of using a Feistel-network to design block-ciphers.

But the round functions used in actual block-ciphers are -- for efficiency reasons -- far from being pseudorandom. We investigate in [3] the security of the Feistel-network against CPA distinguishers when the only security guarantee we have for the round functions is that they are secure against non-adaptive chosen plaintext attacks (nCPA), thus the round functions have a strictly weaker security guarantee than what we would like to achieve for the whole construction.

We show that in the information theoretic setting, four rounds with nCPA secure round functions are enough (and necessary) to get a CPA secure permutation.

Unfortunately this result does not translate into the more interesting pseudorandom setting. In fact, we can show that -- under the decisional Diffie-Hellman assumption -- the Feistel-network with four rounds, each instantiated with a nCPA secure pseudorandom function, is not necessarily a CPA secure pseudorandom permutation.

A Fast and Key-Efficient Reduction of Chosen-Ciphertext to Known-Plaintext Security

Motivated by the quest for reducing assumptions in security proofs in cryptography, this work is concerned with designing efficient symmetric encryption and authentication schemes based on any weak pseudorandom function (PRF) which can be more efficiently implemented than PRFs. Damgaard and Nielsen (CRYPTO '02) have shown how to construct an efficient symmetric encryption scheme based on any weak PRF that is provably secure against chosen-plaintext attacks. The main ingredient is a range-extension construction for weak PRFs. By using well-known techniques, they also showed how their scheme can be made secure against the stronger chosen- ciphertext attacks.

The results of our paper [4] are three-fold. First, we give a range-extension construction for weak PRFs that is optimal (within a large and natural class of constructions, especially all constructions that are known today). Second, we propose a strengthening of a weak PRF to a PRF. Third, these two results imply a (for long messages) much more efficient chosen-ciphertext secure encryption scheme than the one proposed by Damgaard and Nielsen. The results also solve open questions posed by Naor and Reingold (CRYPTO '98) and by Damgaard and Nielsen.

Range Extension for Weak PRFs; The Good, the Bad, and the Ugly

In [5], we investigate a general class of (black-box) constructions for range extension of weak pseudorandom functions: a construction based on m independent functions F_1,...,F_m is given by a set of strings over {1,...,m}*, where for example {<2>,<1,2>} corresponds to the function X --> [F_2(X),F_2(F_1(X))]. All efficient constructions for range expansion of weak pseudorandom functions that we are aware of are of this form.

We completely classify such constructions as good, bad or ugly, where the good constructions are those whose security can be proven via a black-box reduction, the bad constructions are those whose insecurity can be proven via a black-box reduction. The ugly constructions are those which are neither good nor bad.

Our classification shows that the range expansion from [6] is optimal, in the sense that it achieves the best possible expansion (2^m-1 when using m keys).

Along the way we show that for weak quasirandom functions (i.e., in the information theoretic setting), all constructions which are not bad -- in particular all the ugly ones -- are secure.

Weak Pseudorandom Functions in Minicrypt

A family of functions is weakly pseudorandom if its members are indistinguishable from uniformly random functions when queried on random inputs. In [6], we point out a subtle ambiguity in the definition of weak PRFs: there are natural weak PRFs whose security breaks down if the randomness used to sample the inputs is revealed. To capture this ambiguity we distinguish between public-coin and secret-coin weak PRFs.

We show that the existence of a secret-coin weak PRF which is not also a public-coin weak PRF implies the existence of two pass key-agreement (i.e. public-key encryption). So in Minicrypt, i.e. under the assumption that one-way functions exist but public-key cryptography does not, the notion of public- and secret-coin weak PRFs coincide.

Previous to this paper all positive cryptographic statements known to hold exclusively in Minicrypt concerned the adaptive security of constructions using non-adaptively secure components. Weak PRFs give rise to a new set of statements having this property. As another example we consider the problem of range expansion for weak PRFs, we show that in Minicrypt one can beat the best possible range expansion factor (using a fixed number of distinct keys) for a very general class of constructions (in particular, this class contains all constructions we are aware of).

Publications

[1] U. Maurer and J. Sjödin. Single-Key AIL-MACs from any FIL-MAC. In ICALP 2005, Lecture Notes in Computer Science, Springer-Verlag, volume 3580, pages 472-484, July 2005.

[2] U. Maurer and J. Sjödin. Domain expansion of MACs: Alternative uses of the FIL-MAC. In Cryptography and Coding 2005, Lecture Notes in Computer Science, Springer-Verlag, volume 3796, pages 168-185, December 2005.

[3] U. Maurer, Y. A. Oswald, K. Pietrzak and J. Sjödin. Luby-Rackoff ciphers with weak round functions. In Advances in Cryptology - EUROCRYPT 2006, Lecture Notes in Computer Science, Springer-Verlag, volume 4004, pages 391-408, May 2006.

[4] U. Maurer and J. Sjödin. A Fast and Key-Efficient Reduction of Chosen-Ciphertext to Known-Plaintext Security. In Advances in Cryptology --- EUROCRYPT 2007 , Lecture Notes in Computer Science, Springer-Verlag, volume 4515, pages 498-516, May 2007.

[5] K. Pietrzak and J. Sjödin. Range Extension for Weak PRFs; The Good, the Bad, and the Ugly. In Advances in Cryptology --- EUROCRYPT 2007, Lecture Notes in Computer Science, Springer-Verlag, volume 4515, pages 517-533, May 2007.

[6] K. Pietrzak and J. Sjödin. Weak Pseudorandom Functions in Minicrypt. In ICALP 2008, Lecture Notes in Computer Science, Springer-Verlag, volume 5126, pages 423-436, Jul 2008.