• 検索結果がありません。

A Study of Block Cipher Modes for Encryption and Authentication

N/A
N/A
Protected

Academic year: 2022

シェア "A Study of Block Cipher Modes for Encryption and Authentication"

Copied!
85
0
0

読み込み中.... (全文を見る)

全文

(1)

A Study of Block Cipher Modes for Encryption and Authentication

ブロック暗号モードによる暗号化と認証に関する研究

March 2008

Kazuhiko Minematsu

(2)

A Study of Block Cipher Modes for Encryption and Authentication

ブロック暗号モードによる暗号化と認証に関する研究

March 2008

早稲田大学大学院基幹理工学研究科 数理科学専攻 情報数学研究

Kazuhiko Minematsu

(3)

1

Acknowledgements

I am deeply grateful to my supervisor, Professor Toshiyasu Matsushima, for his excellent ideas and unlimited enthusiasm. I learned a lot from him: the pleasure of researching, the importance of logical thought, and the meaning of life.

I acknowledge Professor Shigeichi Hirasawa and Professor Shin’ichi Oishi for their invaluable advices in the peer-review process. Also, I wish to thank Professor Jun Murakami. I could not start the doctoral course without his generous aid.

Special thanks to the principal researcher at NEC Corporation, Dr. Yukiyasu Tsunoo. He always encouraged me and made warm and helpful advices. Thanks to Etsuko Tsujihara at YDK Inc., for helping implementations of my proposals.

I sincerely appreciate Professor Yoshifumi Ukita at Yokohama College of Commerce. I cannot thank him enough for his empathetic advices and timely comments. I also appreciate Professor Yasunari Maeda at Kitami Institute of Technology for his encouragement and advices.

I wish to thank my colleagues. Especially, great thanks to Naoto Kobayashi, Tota Suko, and Shunsuke Horii (at Waseda University), and Dr. Ryo Nomura, Tomohiko Saito (at Aoyama Gakuin University), and Takahiro Yoshida (at Chuo University) for having fruitful discussions with me. I had spent a great time with you. I also thank to all the members of Matsushima and Hirasawa Laboratories at Waseda University.

Last but not least, I would like to thank my family for their understanding and support. Definitely you are the source of my energy.

(4)
(5)

3

Contents

Acknowledgements 1

1 Introduction 5

1.1 Developments of Symmetric-key Cryptosystem . . . 5

1.2 The Role and Goal of Block Cipher Modes . . . 5

1.3 Contributions of This Thesis . . . 8

2 Preliminaries 11 2.1 Basic Notations . . . 11

2.2 Attack Model . . . 12

2.2.1 Formal Treatment of Cryptographic Attacks . . . 12

2.2.2 Advantage . . . 13

2.2.3 Pseudorandom Function and Its Variants . . . 15

2.2.4 Construction . . . 16

2.3 Indistinguishability of Random Systems . . . 16

2.3.1 How to Prove the Security of a Mode . . . 16

2.3.2 Monotone Event Sequence and Conditional Equivalences . . . 17

2.3.3 Theorems and Lemmas for Proving Indistinguishability . . . 19

2.3.4 The PRF-PRP Switching Lemma . . . 19

3 Building Modes with Differentially-Uniform Permutation 21 3.1 Introduction . . . 21

3.2 Message Authentication Code . . . 21

3.2.1 Definition . . . 21

3.2.2 Carter-Wegman Approach . . . 22

3.2.3 Known Constructions . . . 22

3.3 Building MACs with Differentially-uniform Permutation . . . 23

3.3.1 Basic Idea . . . 23

3.3.2 Building Variable Input Length Universal Hash . . . 24

3.3.3 Complete Description of MT-MAC and PC-MAC . . . 28

3.3.4 AES-based Implementation . . . 29

3.4 Some Variants of MT-MAC and PC-MAC . . . 31

3.4.1 MT-MAC+: a Stateful Variant of MT-MAC . . . 31

3.4.2 How to Reduce the Preprocessing Computation . . . 34

3.4.3 Comparison . . . 37

3.5 Tweakable Block Cipher . . . 38

3.5.1 Brief Overview . . . 38

3.5.2 Security Definition and Previous Proposals . . . 38

3.6 Building Strong Tweakable Block Ciphers . . . 40

3.6.1 A Bug in the Initial XEX and an Attack against OCB1 . . . 40

3.6.2 The Security of Fixed XEX . . . 40

3.6.3 Proof of Theorem 3.6.1 . . . 41

3.6.4 Improving LRW-AES . . . 44

4 Building Modes with Weak Pseudorandom Functions 47 4.1 Introduction . . . 47

4.2 Randomized Encryption via WPRF Expansion . . . 48

(6)

4 Contents

4.2.1 Basic Definitions . . . 48

4.2.2 Pseudorandom Tree . . . 48

4.2.3 On the Difficulty of Achieving Constant Key Size . . . 50

4.2.4 Extended Pseudorandom Tree . . . 50

4.3 Building a Large-Block (Strong) Pseudorandom Permutation . . . 51

4.3.1 Background . . . 51

4.3.2 Building a Large Output PRF . . . 52

4.3.3 Hash-Permute-Expansion: a New Scheme for Large-block Permutation . . . 53

4.3.4 How to Build an SPRP Using HPE Structure . . . 56

4.3.5 Hash-Sum-Expansion: an Improved Scheme for SPRP . . . 57

4.3.6 Comparison . . . 58

4.4 Tweakable Enciphering Scheme . . . 59

4.4.1 Introduction . . . 59

4.4.2 Main Theorem on the Security of Hash-Sum-Expansion . . . 60

4.4.3 Some Variants . . . 62

4.4.4 Implementation Based on a Blockcipher . . . 62

4.4.5 Other Implementations . . . 65

5 Conclusion 67 A Proofs and Miscellaneous Results 69 A.1 Proof of Lemma 3.3.4 . . . 69

A.2 Proof of Theorem 3.3.1 . . . 69

A.3 Proof of Theorem 3.3.2 . . . 70

A.4 Proof of Theorem 3.5.1 . . . 70

A.5 An Attack against OCB1 Using Flawed XEX1 . . . 71

A.6 On the KPA-Security of the 2-Round Feistel Permutation . . . 71

A.7 Proof of Lemma 4.3.2 . . . 72

A.8 Proof of Theorem 4.3.4 . . . 72

A.9 Proof of Lemma 4.4.1 . . . 73

A.10 Proof Sketch of Theorem 4.4.3 . . . 75

Bibliography 77

Publications 83

(7)

5

Chapter 1

Introduction

1.1 Developments of Symmetric-key Cryptosystem

The aim of symmetric-key cryptosystem is to provide a secure communication for legitimate parties who share a secret key, over an insecure (i.e., it might be wiretapped and/or tampered) channel. The history of symmetric-key cryptosystem goes back to the ancient era, for example the Caesar cipher (also called the shift cipher [91]) in the Roman empire. However until the seminal work of Shannon [78], it was more like an art than science.

Shannon [78] proved the famous theorem that exhibits the fundamental limitation of symmetric-key cryptosys- tem. That is, in the information-theoretic sense, the secret key should be as long as a message that has to be securely transmitted. This implies the huge amount of keys has to be communicated over a secure (e.g. by handover) channel.

The invention of public-key cryptography [29] overcame this pessimistic result, by introducing the idea of asymmetric keys. I.e., the key for encryption (public key) and one for decryption (private key) are different, and deriving the latter from the former is as difficult as solving some mathematically hard problems, such as factoring or discrete-log problem.

Public-key encryption achieves a great success, however, symmetric-key encryption, also called cipher, has never be obsolete, or even it is becoming more and more important, since known public-key encryption algorithms are by far slower than the conventional symmetric-key ciphers. Now symmetric-key cipher is an essential tool for everyday life. Just to name a few, the Internet has been supported by many communication protocols, such as SSL or IPSec, using symmetric-key ciphers, and the wireless communications via cell phones can not be secure against eavesdropping without the use of a cipher.

1.2 The Role and Goal of Block Cipher Modes

A common building block of a symmetric-key cryptosystem is a block cipher, denoted by EK. Here, K is the secret key shared by legitimate parties, and EK represents a set of permutation over a message set indexed by K, that is,Ek :X → X is a deterministic permutation over X for any key valuek. IfX ={0,1}n, we call EK an n-bit block cipher. IfK is fixed tok, the encryption of a plaintextxresults in a ciphertext y that satisfies y=Ek(x). The decryption is defined asx=Ek1(y). We can also define ann-bit block cipher as a deterministic function having two inputs: E(k, x) =ywhere E(k,∗) is invertible (see Fig. 1.1).

Interestingly, Shannon was also the initiator of the systematic study on conventional block ciphers. In [78], he proposed some fundamental concepts for building practical and secure block ciphers, such as confusion and diffusion. The first widely-used block cipher, the Data Encryption Standard (DES), was based on his idea, and

E plaintext x

ciphertext y

key k E-1

ciphertext y

plaintext x key k

Fig. 1.1 A Block Cipher.

(8)

6 Chapter 1 Introduction x1

K E

y1

x2

K E

y2

x3

K E

y3 Fig. 1.2 ECB Mode.

x1

K E

y1

x2

K E

y2

x3

K E

y3 nonce

Fig. 1.3 CBC Mode.

the spread of DES stimulated many subsequent studies on cryptanalysis and design of ciphers. Nowadays, we have many practically secure and highly efficient block ciphers, including the Advanced Encryption Standard (AES) [89], the de facto standard block cipher. Due to the efficiency and security issues, most of modern block ciphers accept only a short, fixed-length messages, for example 128-bit or 64-bit. However, real-world applications usually require cryptosystems that can deal with longer messages. Moreover, the security requirement can be different for each applications. Designing a dedicated cipher for each application from scratch would be totally impractical.

A typical solution to this problem is to employ some mode of operation (mode in short) with a block cipher.

A modeF[] is a function that invokes a block cipherEK as an internal module, and realizes a functionF[EK] having desirable input/output spaces, for instance input and output with arbitrarily long lengths. Many block cipher modes has been considered from the appearance of DES. For instance, Electronic Code Book (ECB) mode and Cipher Block Chaining (CBC) are perhaps the oldest proposals for encryption of long message, In Figs. 1.2 and 1.3, both modes are shown, where we encrypts a 3-block plaintext (x1, x2, x3) to obtain the 3-block ciphertext (y1, y2, y3). In Fig. 1.3, nonce is defined as an independent and random value that never repeats. As a receiver of the ciphertext must know the nonce to perform the decryption, nonce is always attached to the ciphertext.

The purpose of this thesis is to build a symmetric-key cryptosystem realizing an encryption and/or authenti- cation, using block cipher modes. Of course, we want to make our proposal secure. But how? In early attempts, the security of a mode was measured by ad-hoc. That is, we first specify a block cipher to be used, and then investigate the security of the mode with that block cipher by trying to find a weakness, for example some de- pendency between the ciphertext and the block cipher’s key, or deviation of the ciphertext from uniform. This approach is very cumbersome, as every change of the underlying cipher would imply the complete reexamination of the mode’s security.

To overcome this problem, our proposals should have provable security, which means that the security of a mode is reduced to the security of underlying block cipher. In this sense, this kind of security proof is also called the security reduction. Very roughly, when we say a mode F[] is provably secure, the outputs of F[EK] look random whenever the outputs of EK also look random. To understand the nature of this security notion, it is good to consider the difference between ECB and CBC modes. In the ECB mode, plaintexts are encrypted block-wise, where the encryption algorithms for all blocks are identical, i.e., EK. From this, it is clear that any change in single block of the plaintext will result in the change in the same block of the ciphertext, and other blocks will not be changed. In other words, we can obtain the (partial) information about the plaintext by observing the ciphertexts. If the plaintext has low entropy, e.g., monochrome images, one can easily get a distorted plaintext. This certainly fails to achieve our goal, i.e., “random-looking ciphertexts”. What is worse is that, this vulnerability can not be fixed by using any other block cipher than EK. Contrastingly, the CBC mode does not have such vulnerability, if the block cipher produces “random-looking ciphertexts” for any distinct

(9)

1.2 The Role and Goal of Block Cipher Modes 7

Adversary

Encryption Oracle Query x

Answer H(x)

H = FKor GK’

2. Make a binary decision

1. Iterate qtimes

Game CPA

(FKor GK’?)

Fig. 1.4 Chosen-Plaintext Attack.

Adversary

Encryption / Decryption Oracle Query (x , b)

Answer H(x) if b= 0,H-1(x) if b= 1 H = FKor GK’

2. Make a binary decision

1. Iterate qtimes

Game CCA

(FKor GK’?)

Fig. 1.5 Chosen-Ciphertext Attack.

plaintexts. Intuitively, any plaintext blocks in the CBC mode will be mapped to uncorrelated ciphertext blocks because the nonces are unpredictable and distinct, and the block cipher is generating random-looking ciphertext blocks. Even if we send the same plaintext (of arbitrarily long) twice, it will be difficult to notice this by observing the corresponding ciphertexts. A detailed analysis shows that if someone can attack the CBC mode, it must be the vulnerability of the underlying block cipher, and not that of the mode. In this sense, CBC mode is provably secure, while ECB mode is not.

Then, one may naturally ask what we mean by ”random-looking”. Does that means passing some statistical tests, such as chi-square or run-length test? Certainly, this is not sufficient. In this thesis, “random-looking”

means topseudorandom, a computational notion first introduced by Yao [87]. A pseudorandom sequence is a ran- dom sequence generated deterministically from a seed (or a key, which is a short uniformly random sequence) than can not be distinguished from uniformly random sequence of the same length for any polynomial-time algorithm.

An efficiently-computable (i.e., polynomial-time) function that accepts a seed and produces a pseudorandom sequence is called a pseudorandom generator (PRG).

It is easy to see that PRG is an ideal model of the stream cipher, as a PRG enables a one-time pad cipher which produces ciphertexts hard to be distinguished from random using any practical algorithm. However, it is not adequate for an ideal model of a block cipher, as PRGs have no inputs. To define the ideal block cipher model, we need to introduce the following game. Suppose a game where one has to distinguish the two independently-keyed functions,FK andGK0. We assume the adversary performs the Chosen-Plaintext Attack (CPA), which is shown in Fig. 1.4. In this game, at time period i, he chooses a plaintextxi and gives it to the encryption oracle, and then the encryption oracle answers the ciphertextyi =H(xi), whereH is eitherFK orGK0. In this game, the goal of adversary is to determine ifH isFK or GK0, based on the informationx1, x2, . . ., andy1, y2, . . ..

In this game, if an n-bit block cipher,EK, can not be efficiently (e.g., polynomial-time computation) distin- guished from the uniform random function (URF), that produces truly random outputs for any distinct inputs, is called a pseudorandom function (PRF). The definition is in Section 2.2. We also have similar definitions, such as a pseudorandom permutation (PRP) and a strong pseudorandom permutation (SPRP), which is hard to be distinguished from uniform random permutation using any Chosen-Ciphertext Attack (see Fig. 1.5).

The existence of PRF has not yet proved or disproved. However the existence of PRG, PRF, and all variants are equivalent to that of a one-way function, which is a function easy to evaluate but hard to invert, and the existence of one-way function is one of the most fundamental assumptions of the computation theory. Therefore, it is widely accepted that assuming a practically-secure block cipher to be a PRF. Moreover, some popular

(10)

8 Chapter 1 Introduction cryptographic functions are securely implemented with a PRF having variable-length input or output. For example, the encryption of variable-length message requires a PRF with variable-length input and output, where it is invertible. This requires that the output length is always not shorter than the input length.

Therefore, the purpose of the mode can be interpreted as (e.g.) building a PRF with variable-length in- put/output using a PRF with fixedn-bit input and output. When the mode is implemented with a real block cipher, its security is guaranteed based on the PRF-assumption of that block cipher.

Short History on the Provable Security Reducing a scheme’s security to the security of its component is an essence of the modern cryptography. Indeed, the security of any known public-key cryptography is always coming with a hardness assumption about some mathematical problem. In the studies of symmetric-key cryp- tosystem, the reduction-based security analysis was initiate by Luby and Rackoff in their seminal paper [50], and this approach was soon widely accepted in the symmetric-key encryption research community. Since the definitions of PRF and its family are essentially asymptotic (see Section 2.2), the previous security analyses were also asymptotic (this corresponds to assuming the block cipher’s input length can be infinitely long). This style is not much useful for the analysis of modes with real-life block ciphers, which usually have fixed, short input length. Then, one important work was done by Bellare et al. [14]. They demonstrated how one could perform the non-asymptotic security reduction and rigorously express the security of a mode in terms of the adversary’s attack resource, such as the number of queries to the encryption oracle. Bellare et al.’s approach is called the concrete security analysis.It is beneficial, as it enables us to explain how much the guaranteed security is, rather than yes/no answer given by the asymptotic analysis. Also, concrete security analysis allows us to compare the securities of two modes having the same functionality.

Now proving a provable security is a standard criteria. For example, NIST (National Institute for Standards and Technology) has defined a number of block cipher modes for encryption and authentication as recommendations, and all modes are provably secure based on the assumption that the block cipher used is PRF or a variant of it.

1.3 Contributions of This Thesis

The purpose of this thesis is to provide symmetric-key cryptographic functions such as encryption or authen- tication faster than the previous solutions using single block cipher, that is, the block cipher modes. For this purpose, this thesis relaxes the definition of the block cipher modes. In particular, we allow us to use multi- ple cryptographic primitives including a block cipher that may have different input/output and security. With this extended definition, our schemes are provably secure (as previous ones), when underlying primitives satisfy security conditions, which can be different for each primitive. Since we have more design options than before, it is possible to substitute some operations in previous schemes with simpler/weaker ones, if it does not harm the provable security. This naturally implies faster solutions than before (even if we can not substitute whole operations with simpler/weaker ones).

Let us describe more details of our approaches, which can be divided into two categories. The first approach is described in Chapter 3. This incorporates the state-of-art block cipher design techniques into the block cipher mode. The main target is the message authentication code (MAC), which is used to authenticate a message communicated over an insecure channel. A MAC function computes an authentication tag for each message, using the secret key. Then, the message and the tag are concatenated and sent to the receiver (see Fig. 1.6).

Here, messages can be arbitrarily long while tags have fixed length. Thus, a MAC function is a keyed function having variable-length input and fixed-length output.

Previously, we have two typical MAC constructions: block cipher-only construction, such as CBC-MAC, and the combined construction using a block cipher and a universal hash function [23], which is also called a Carter- Wegman MAC (CW-MAC) named after the inventors of universal hash function. A universal hash function is non- cryptographic: it can be implemented without any computational assumption using simple algebraic operations such as multiplications over a field, say GF(2128). From this fact, CW-MACs are sometimes much faster than the CBC-MAC. However, to obtain such improved speed, we usually need implementation of (e.g.) field multiplication highly optimized for target platform. In other words, the performance of CW-MACs using algebraic operation- based universal hash functions is very platform-sensitive. This is undesirable for multi-platform applications, such as a client-server system.

As an solution to this problem, the thesis proposes to combineEK and its component. Typically, we assume EK to be anr-round block cipher: it is a cascade of rkeyed permutations (also called round functions). Then, we use ther0-round cipher derived fromEK for some r0< r(see Fig. 1.7).

The proposed scheme is provably secure if such a reduced-round cipher is an²-differentially uniform permutation

(11)

1.3 Contributions of This Thesis 9

Key MAC

Message

Tag

(Message, Tag)

Tag’’ =Tag’ ? Key MAC

Message’

Tag’’

Sender

Tag’

Authentic Fake

yes no Attacker

Receiver (Message’, Tag’)

Fig. 1.6 Message Authentication Code.

...

EK Previous Approach

...

...

EK

Our Approach

...

reduced-round EK

Fig. 1.7 Approaches to MAC.

Table. 1.1 MEDP of reduced-round AES.

Round MEDP

2 228

3 242

4 (and more) 2113

for sufficiently small ², or, equivalently has Maximum Expected Differential Probability (MEDP) ². If f is an

²-differentially uniform permutation, any input pair having the form (X, X+a), where X is uniform and a is a fixed value, would result in the output pair whose differential is close to uniform (the bias is ²). That is, maxa6=0,bPr(f(X)−f(X+a) =b) is at most².

This assumption is quite reasonable, since it provides a theoretical protection against the differential crypt- analysis (DC)[19]. From the famous paper of Nyberg and Knudsen [69], we have huge number of studies on how to provide a protection against DC by a few iteration of simple keyed permutation, and most modern block ciphers are based on these studies. Therefore, modern block ciphers are naturally expected to meet our as- sumption. In fact, we have some concrete examples. The most important one is AES, where 4-round AES is a 2113-differentially uniform permutation [43] while the full AES is 10-round. It is possible to use fewer rounds, however, might be insufficient due to the large bias (2-round AES is only 228-differentially uniform, and 3-round AES is 242-differentially uniform). In addition, it is not known ifr-round AES for 4< r≤10 has significantly smaller²than 2113. Hence, we think 4-round is the well-balanced choice for the complexity and security.

We provide some efficient MACs based on this approach, and show several AES-based implementations having different performance characteristics. All our proposals are about 1.42.5 times faster than the CBC-MAC and other block cipher-based MACs using AES, and as secure as the CBC-MAC based on the same assumption that AES is a PRF. Such schemes seem to be very valuable in practice.

In principle, this approach can be applied to anything that uses a universal hash function. As an example, we describe a construction oftweakable block cipher, which is an extension of a block cipher. A tweakable block cipher accepts a public parameter called tweak in addition to the key and plaintext (ciphertext). Tweak is used to give

(12)

10 Chapter 1 Introduction

Previous Approach

...

Our Approach

...

EK =PRF (or stronger)

FK’=WPRF

... ...

EK =PRF (or stronger)

Fig. 1.8 Approaches to large-block permutation.

a variability of a block cipher, that is, a change of a tweak should work as a change of a key (see Section 3.5 for the formal definition). The formal definition is done by Liskov et al., [49] and they proposed block cipher modes that convert a block cipher into a tweakable one. Their mode was further optimized by Rogaway [77]. In this thesis, we generalize these modes with respect to a component of them, and identifies the component’s conditions to assure the provable security of the whole mode. Consequently, this component is required to be a kind of universal hash function with some additional properties, and it can also be implemented with ²-differentially uniform permutations with minor restrictions. As the 4-round AES meets this requirement, we can obtain an improved performance when we use AES combined with the proposal of this thesis.

In Chapter 4, the second approach is described. The goal is to build two variants of PRF: a pseudorandom permutation (PRP) and a strong PRP (SPRP), using n-bit block ciphers. They are length-preserving permuta- tions, i.e., input and output have the same length, and invertible. Also, we require that their inputs can be long (e.g, mn-bit for any positive integer m >1). In other words, we are going to build a block cipher with a long block length using a block cipher with a short block length. This is quite different from the MAC case, since we have to expand both input and output of a given block cipher.

This problem (or a restricted version of it) has been extensively studied, including famous Luby and Rackoff’s result [50] on the Feistel permutation. All previous proposals used n-bit block PRF (or a stronger one, such as SPRP) as its component. However, this thesis will take a different approach. The key idea is to use a weak pseudorandom function (WPRF) in combination with a PRF (or a stronger function), see Fig. 1.8. WPRF is a strictly weaker function than PRF, as it produces pseudorandom outputs for most of inputs, but not all. That is, outputs of a WPRF can not be distinguished from random if corresponding inputs are independent and random, i.e., a Known-Plaintext Attack (KPA). Note that a weak function is assumed to be faster than a stronger one.

Therefore a mode combining WPRF and PRF is naturally expected to be faster than one using PRF only.

Assume that we want to build an mn-bit PRP/SPRP. Then, for anym >1, this thesis demonstrates that an mn-bit PRP can be built using one PRP andm−1 WPRFs (bothn-bit block), and anmn-bit SPRP can be built using one SPRP andm−1 WPRFs. The core of these proposals is a different structure from Feistel that allows us to incorporate WPRF. Since previous schemes require at leastm PRFs to build anmn-bit PRP/SPRP, the proposed schemes are potentially faster than previous ones as they effectively use a WPRF instead of a stronger function.

These results have an interesting application to the storage (e.g., hard disk) encryption. This thesis also proposes some modes for the storage encryption, using a single block cipher. Although the performance of proposed modes are not very impressive (they are as efficient as previous proposals), our result provides more design freedom to the storage encryption mode, and intuitive explanation why previous modes are secure, since the proposed modes can be seen as a generalization of previous ones.

(13)

11

Chapter 2

Preliminaries

2.1 Basic Notations

The binary space is denoted by Σ. I.e., Σn ={0,1}n. Set of all finite-length binary sequences is denoted by Σ, and set of binary sequences longer than n is denoted by Σn. We also use (Σn)+ to denote the set of binary sequences whose lengths are multiples ofn. The length of binary sequencexis defined as|x|, and a concatenation of two binary sequences, xany y, are denoted by xky. Thus|xky| =|x|+|y|holds true. Please note that the cardinality of a set X is also written by |X |. The bases of all logarithms are assumed to 2, unless otherwise specified. If a random variableX is uniformly distributed overX, we writeX UX. For any sequence of random variables,X1, X2, . . ., letXi denote (X1, . . . , Xi).

Definition 2.1.1. Let X andY be finite sets. A random function (or equivalently a keyed function)FK :X → Y is a random variable (not necessarily uniformly) distributed over the set of deterministic functions{f :X → Y}, where the distribution is defined by a random variable called key, K. Formally, let K (the key ofFK :X → Y) be distributed over K according to the distribution Pr(K = k). Then there exists a deterministic function f : X × K → Y such that

Pr(FK(x) =y) =

k∈K,f(k,x)=y

Pr(K=k), (2.1)

and if Pr(K =k) = 1/|K|for anyk, i.e., when K is uniform overK, the right hand side (r.h.s) of Eq.(2.1)is equal to {k∈ K:f(k, x) =y}/|K|.

If K is fixed to k ∈ K, Fk() denotes a deterministic function f(k,) : X → Y. For random function FK :X → Y,X (Y) is said to be the input (output) space ofFK, that is, the key space is not included. A random permutation EK : X → X is a special case of random function: for any K = k ∈ K, Ek is a deterministic permutation overX. Its inverse is denoted byEk1. In particular, we have

Ek1(Ek(x)) =xfor any k∈ K andx∈ X. If X = Σn,EK is also called an n-bit block cipher.

Note that, in this thesis, the word “random” does not necessarily imply uniformity. It only means it is probabilistic.

Definition 2.1.2. A uniform random function (URF): ΣnΣmis a random function with uniform distribution on all functions Σn to Σm and denoted by Rn,m. Thus the key space of URF has to be large enough to describe all functions: |K|= 2m2n. Of course, key is uniformly distributed over K. Note that the description of URF’s key is omitted. In addition, an n-bit block URF,Rn,n can be abbreviated toRn. A uniform random permutation (URP) on Σn is a random permutation with uniform distribution on alln-bit permutations and denoted by Pn. Its key is uniformly distributed over a set of size2n!. As well as URF, the description of URP’s key is omitted.

When two random functions, FK and GK0, have the same input/output space, we say they are compatible.

Note that their keys,K andK0, need not to have the same length. We will use the following operator to express the composition of two (possibly keyed) functions.

Definition 2.1.3. Let FK :X → Y, andGK0 :Y → Z. LetFK/ G:X → Z be a random function such that FK/ G(x)def=GK0◦FK(x) =GK0(FK(x))for all x∈ X.

(14)

12 Chapter 2 Preliminaries

Elements of GF(2n). Following many existing studies, such as [39, 77], we express the elements of field GF(2n) by then-bit coefficient vectors of the polynomials in the field. We alternatively representn-bit coefficient vectors by integers 0,1, . . . ,2n1. For example, 5 corresponds to the coefficient vector (00. . .0101) (which corresponds to the polynomialx2+ 1) and 1 corresponds to (00. . .01), i.e., the identity element. Forx, y∈Σn, we definex·yas the field multiplication of elements corresponding toxandy. If it is not confusing, we abbreviate it toxy.

On The Notation of Random Functions Expression of a random function is in principle coming with a random variable, i.e., the key, which defines the internal randomness. We will follow this principle in Chapter 2 except for URF and URP, as the key distributions for them are clear. However, we will sometimes omit the descriptions of keys after Chapter 2 for simplicity. A random function will be written in capital letters, such as F orG. Unless otherwise noted, we assume that random functions having different letters are independent, i.e., using independent keys.

2.2 Attack Model

2.2.1 Formal Treatment of Cryptographic Attacks

As described in Introduction, the security analysis of a block cipher mode needs the idea of Pseudorandom Function and its variants. To explain these objects, we need to define the attack model.

Consider the game in which we want to distinguish two compatible random functions, GK andG0K0, using a black-box access to them. The entity who plays this game is called an attacker or a distinguisher. The type of access is classified into a number of categories, most notably the following ones.

Chosen-plaintext attack (CPA): an adversary can access to the encryption oracle, that is, he can obtain GK(x) (or G0K0(x)) for any x. Here, xmay depend on the previous answers from encryption oracle and queries made by the adversary. See also Fig. 1.4.

Known-plaintext attack (KPA): an adversary can access to the encryption oracle, however, each queryx is chosen completely random and independent from previous queries and answers.

Chosen-ciphertext attack (CCA): an adversary can access to the encryption and decryption oracles. For every query, he can arbitrarily choose which oracle to be accessed. When encryption oracle is chosen, it returns GK(x), and when decryption oracle is chosen, it returns GK1(x), where x is arbitrarily chosen by the adversary. See also Fig. 1.5. Obviously, CCA can be defined only whenGK andG0K0 are random permutations.

A formal treatment of an attacker (or distinguisher) is as follows.

Definition 2.2.1. Consider a distinguisher,A, with query spaceX and answer spaceY. Thei-th query (answer) is denoted by Xi ∈ X (Yi ∈ Y), and the final decision is denoted by B Σ. Here, X0 is defined as an empty variable. Then, A is defined by an infinite sequence of two conditional probability distribution functions, (pq(i), pd(i)) fori= 1,2, . . ., where

pq(i):X × Xi1× Yi1[0,1]and pd(i): Σ× Xi× Yi [0,1]

are used for choosing i-th query and i-th final decision, respectively*1 . More precisely, at time period i (1 i q, where q is a pre-specified value), A chooses the i-th query Xi = xi using (xi1, yi1) with probability pq(i)(xi|xi1, yi1), and after the q-th answer, makes the binary decision B = b using (xq, yq) with probability pd(q)(b|xq, yq).

Note thatXiis a random variable possibly dependent withXi1andYi1, where the dependence is determined by the strategy of A. Similarly, Yi is a random variable possibly dependent with Xi and Yi1, where the dependence is determined by the underlying random function, i.e.,GK orG0K0. Note that ifAis a CPA-attacker, pq(i) can be any function:X × Xi1× Yi1 [0,1], as A can arbitrarily (and possibly non-deterministically)

*1Note that pq(i) and pd(i) are not necessary to be defined for all arguments. For example, if one is accessing to a random function, it is not possible to obtain pairs (Xi, Yi) and (Xj, Yj) satisfyingXi=XjbutYi6=Yj. Thus we do not need to define the outputs ofpq(i) andpd(i) if arguments include such pairs: outputs can be arbitrarily defined.

(15)

2.2 Attack Model 13 choose xi, depending on the previous query/answer pairs , xi1 and yi1. Of course, pd(i) is also arbitrary.

However, ifAis a KPA-attacker,pq(i)is always a functionf such thatf(xi, xi1, yi1) = 1/|X |for anyxi∈ Xi and yi1 ∈ Yi1. In case thatA is a CCA-attacker, we need to introduce the following simple trick to convert CCA into CPA.

Definition 2.2.2. Let GK : X → X be a random permutation. Then, hGKi denotes the random function n× {0,1} →Σn such that hGKi(xi, wi) =GK(xi)ifwi= 0 andGK1(xi)ifwi= 1.

From the above definition, the CCA-attacker who wants to distinguish two random permutations overX has query spaceX ×Σ and answer spaceX.

Alternative Expression In any case, the randomness of the adversary is needed to choose queries and binary decision according to the distributions pq(i) for i = 1, . . . , q and pd(q). Hence, once q is specified, the adversary can be interpreted as a sequence of random functionsuch as

(A(1)Kq

1, A(2)Kq

2, . . . , A(q)Kq

q, D(q)Kd

q), (2.2)

whereA(i):Xi1×Yi1→ X is thei-th query-making random function using keyKq1andD(q):Xq×Yq Σ is theq-th decision-making random function using keyKdq. Note that the domain of these keys are not necessarily the same and their distributions can be dependent. Clearly, we have

pq(i)(xi|xi1, yi1) = Pr[A(i)Kq

i(xi1, yi1) =xi] pd(i)(b|xi, yi) = Pr[D(i)Kd

i(xi, yi) =b]

This notation is just for explanation: though it might help readers understand what adversary is, it is quite cumbersome. Thus we will not employ it and simply useA to denote the adversary.

2.2.2 Advantage

Next, we want to define advantage, which is the measure for accuracy of adversary’s prediction. Note that an adversary can have a qualitative parameter, atk ∈ {cpa,kpa,cca}, working as attack type indicator and quantitative parameters such as

q: the number of queries

τ : the total time complexity

Here, τ includes the program size and the worst-case computation time (needed for the selection of queries and the final binary decision) in some fixed RAM model (See [32] for details). When the inputs to the target functions have variable lengths, we can have additional parameters such as `, the maximum length in all messages, orσ, the total message length. The unit of`andσcan be different (e.g., in bits orn-bit blocks), hence we will specify the unit whenever we use them.

In our definition (Def. 2.2.1), the time complexity can be interpreted as the cost for sampling according topq(i) and pd(i) using internal randomness (e.g., coin tosses). Equivalently, the time complexity is considered as the sum of time and memory for computing outputs ofq+ 1 random functions A(1)Kq

1, A(2)Kq

2, . . . , A(q)Kq

q, D(q)Kd

q (where an input ofA(i)Kq

i is given by the inputs and outputs of{A(j)Kq

j}j=1,...,i1) shown in Eq. (2.2).

The list of quantitative parameter is denoted byθ. Ifθdoes not contain the time complexityτ, the adversary has no computational restriction. An adversary is said to be θ−atkif its attack type is atkwith quantitative parameterθ. Then, the maximum advantage for allθ−atkadversaries trying to distinguishGK andG0K0 is:

AdvatkGK,G0

K0(θ)def= max

A:θatk

¯¯Pr[AGK = 1]Pr[AG0K0 = 1]¯¯ (2.3) where AGK = 1 denotes thatA’s final decision is 1, which indicates one ofGK or G0K0 (it corresponds toB Σ in Definition 2.2.1). One can think AGK as a binary random variable whose distribution is defined byA and GK in a complicated manner. It is intuitive to thinkAGK as the binary output of AgivenGK as its argument.

However, note that the adversaryAcan only access to GK via a query-answer manner. I.e.,A can not directly see the program ofGK which includes the key,K. These notations will be used throughout this thesis. For KPA, we assume a generation of quniformly random n-bit plaintexts requires cnq time for some constantc. In most

(16)

14 Chapter 2 Preliminaries cases we assumento be a fixed constant, thus the computational cost for generation ofnq-bit random sequence can be written as O(q).

From definitions of attacks, we naturally have*2 AdvkpaG

K,G0K0(q)AdvcpaG

K,G0K0(q). (2.4)

Moreover, ifGK andG0K0 are random permutations over X, we also have AdvcpaG

K,G0K0(q)AdvccaGK,G0

K0(q). (2.5)

Another important feature of advantage is triangle inequality. More precisely, we have

AdvatkFK,HK00(θ)AdvatkFK,GK0(θ) +AdvatkGK0,HK00(θ) for anyatk∈ {cpa,kpa,cca} andθ. (2.6)

Aspects of Advantage The definition of advantage by Eq. (2.3) is quite common, but not useful to un- derstand how it is evaluated. Thus one may ask for a more intuitive expression. To do this, we introduce the following notation for probability distributions, which will be used throughout this thesis.

Let U ∈ U and V ∈ V be random variables. They can contain multiple random variables, and in particular V can be an empty variable. We define PUenv|V as the (conditional if V is not empty) probability distribution defined by the environmentenv. The conditional probability ofU =ugivenV =vis written asPUenv|V(u, v). We occasionally denote it by Penv(U =u|V =v) if it is more convenient. If conditional probability of U =ugiven V =v can not be defined for a particular (u, v), then the probability is considered as a default value, denoted by

. It is easy to see thatPUenv|V is a function: U × V →[0,1]∪ {⊥}. For example,PYFK

i|XiYi−1(yi, xi) means Pr[Yi=yi|Xi =xi, Yi1=yi1], whereYj=FK(Xj) forj= 1, . . . .

However, PXFKiYi(yi, xi) is ill-defined (i.e., it is a function that outputsfor any input) since the distribution of the inputs,Xi, is not specified. Note that pq(i) (pd(i)) in Def. 2.2.1 equals toPXA

i|Xi−1Yi−1 (PBA|XiYi).

The equality of two conditional probability distributions PUenv|V1 =PUenv|V2 means the equality as functions, that is, for all arguments. This can be naturally extends to the inequality between two distributions.

Let GK and G0K0 be compatible random functions: X → Y. For any adversary A, let A¦GK denote the environment defined byA interacting withGK. Then, it is easy to see that

i=1,...,q

PYFK

i|Xi−1Yi−1=PYFKi|Xi (2.7) and

PXA¦qGYqK= ∏

i=1,...,q

PXA

i|Xi−1Yi−1·PYGK

i|XiYi−1=PXAq|Yq−1·PYGqK|Xq, (2.8) where the last equation follows from Lemma 1 of [57]. Then, the advantage ofAis expressed as

¯¯Pr[AGK = 1]Pr[AG0K0 = 1]¯¯

=¯¯ ∑

xq,yq

PBA|XqYq(1, xq, yq)PXAq¦YGKq (xq, yq)

xq,yq

PBA|XqYq(1, xq, yq)PA¦G

0K0

XqYq (xq, yq)¯¯

=¯¯ ∑

xq,yq

PBA|XqYq(1, xq, yq) (

PXA¦qGYqK(xq, yq)−PXAq¦YG0K0q (xq, yq)) ¯¯ (2.9)

=¯¯ ∑

xq,yq

PBA|XqYq(1, xq, yq)PXAq|Yq−1(xq, yq1) (

PYGqK|Xq(yq, xq)−PYGq0K0|Xq(yq, xq)) ¯¯, (2.10) where the last equation follows from Eq. (2.8).

*2These inequalities can be extended to the case when the computational power is restricted byτ. However, we will not have AdvkpaG

K,G0K0(q, τ)AdvcpaG

K,G0K0(q, τ) unless we assume the sampling of random inputs requires no computation. Instead, we haveAdvkpaG

K,G0K0(q, τ)AdvcpaG

K,G0K0(q, τ+cdlog2|X |eq), wherecdlog2|X |eqdenotes the time for generatingqrandom inputs.

参照

関連したドキュメント

The next lemma implies that the final bound in (2.4) will not be helpful if non- negative weight matrices are used for graphs that have small maximum independent sets and vertices

From the- orems about applications of Fourier and Laplace transforms, for system of linear partial differential equations with constant coefficients, we see that in this case if

It leads to simple purely geometric criteria of boundary maximality which bear hyperbolic nature and allow us to identify the Poisson boundary with natural topological boundaries

Zhang; Blow-up of solutions to the periodic modified Camassa-Holm equation with varying linear dispersion, Discrete Contin. Wang; Blow-up of solutions to the periodic

We formalize and extend this remark in Theorem 7.4 below which shows that the spectral flow of the odd signature operator coupled to a path of flat connections on a manifold

This problem becomes more interesting in the case of a fractional differential equation where it closely resembles a boundary value problem, in the sense that the initial value

(Furthermore, a bound on the number of elementary matrices can be found that depends only on n, and is universal for all fields.) In the case of fields, this can easily be

Hence, for these classes of orthogonal polynomials analogous results to those reported above hold, namely an additional three-term recursion relation involving shifts in the