β 2 (x) (xS(x) + 1) ≡ S(x)±2 (x) (mod G(x)).

Multiplying this equation by the inverse1 of S(x), one sees that β 2 (x)T (x) ≡ ±2 (x)

(mod G(x)) for some polynomial T (x). Since the characteristic is 2, the Frobenius

1 If

this inverse does not exist, G(x) is not irreducible. Then one can work modulo the irreducible

factors of G(x) and apply the Chinese Remainder Theorem. This is possible since G(x) has no

multiple zeroes.

6 Preliminaries and notation

map y ’ y 2 is an automorphism, and thus is it possible and well-de¬ned to take

the square root of an element of the ¬eld1 Fqm [x]/(G(x)). So there exists a unique

polynomial R(x) satisfying T (x) = R2 (x). Thus the key equation becomes

R(x)β(x) ≡ ±(x) (mod G(x)).

On this form, Euclid™s extended algorithm can be applied as described earlier.

1.2.2 The Maximal Error Property

Now the following property of a decoding algorithm At shall be investigated.

This property will play a crucial role in Chapter 2.

Property 1.2.2 (Maximal Error Property ) On input of a vector y ∈ Fn , the q

decoding algorithm At will return a codeword c in C at distance ¤ t to y if such a

codeword exists. Otherwise, it will return an error“message.

Note that this property in fact states that the decoding algorithm At will not

try to correct t + 1 errors. This is not possible in general if t = d’1 . However,

2

even then it might be possible to correct t + 1 errors in a few isolated cases.

Proposition 1.2.3 states a property of the two main algorithms to determine the

pair σ(x), ω(x) satisfying the Key Equation (1.3). One of the main algorithms

is Euclid™s algorithm which was described in the previous subsection. The other

is the Berlekamp“Massey algorithm [MS77, Section 9.6], which tries to the pair

{σ(x), ω(x)} by solving a set of simultaneous linear equations, namely the general-

ized Newton identities [MS77, Theorem 24, Chapter 8] It is important to note that

the Berlekamp“Massey algorithm is successful if and only if Euclid™s algorithm is;

they also lead to the same result. This is irrespective of whether S(x) is an actual

syndrome polynomial Sy (x). The behavior of the Berlekamp“Massey algorithm and

Euclid™s algorithm with “bad” input, i.e. when inputting a syndrome polynomial of

a vector y at distance more than t from the code, is the same.

These two decoding algorithms for Goppa codes have the maximal error property:

Proposition 1.2.3 Let C be a Goppa code with designed error“correcting capability

t (so r = t in the binary case, and r = 2t otherwise), and let At be either Euclid™s

extended algorithm or the Berlekamp“Massey algorithm for decoding C. Then At

has the maximal error property.

Proof: First, suppose the characteristic of Fq is not equal to 2, suppose that

y ∈ Fn is the input to At and suppose that At outputs a vector v in Fn (so no

q q

error“message is returned). As the implementation is not assumed to explicitly

check that the output is actually a codeword, v does not need to be a codeword.

Certainly, if y is of the form (1.2) then At will output c. However, to prove the

proposition the converse has to be shown, i.e. that equality holds in (1.2) with

c = v.

To this end, the decoding process is analyzed. First the decoding process tries

“ using either Euclid™s or Berlekamp“Massey™s algorithm “ to ¬nd two polynomials

1.2 Coding Theory 7

σy (x) and ωy (x) of the correct degrees and satisfying the Key Equation (1.3). If

this fails, an error“message is assumed to be returned. On the other hand, if σy (x)

and ωy (x) are determined, the decoding process determines the presumed set of

error locations E = {1 ¤ i ¤ n|σy (γi ) = 0}. If E has cardinality strictly less than

deg(σy (x)), an error“message is assumed to be given. Next, the decoding process

determines a vector e of weight at most t by

ωy (γi )/σy (γi ) if i ∈ E ,

ei =

0 otherwise.

Note that all ei with i ∈ E are necessarily non“zero, as otherwise the σy and

ωy would not be relatively prime, and thus the degree of σy would not be minimal.

Finally, the decoding process determines v = y ’ e , which is returned by At .

Now to see that v is a member of C, we consider the polynomials σe (x) and

ωe (x) (corresponding to e written as e = 0 + e ), i.e. Se (x)σe (x) ≡ ωe (x)

(mod G(x)). First the observation is made that the pair (σe (x), ωe (x)) is equal

to the pair (σy (x), ωy (x)). That σy (x) = σe (x) is trivially true, because the error

vectors in y = v + e and e = 0 + e are equal. That ωy (x) = ωe (x) follows

from the fact that both are polynomials of degree ¤ deg(σy (x)) ’ 1 that coincide

on deg(σy (x)) distinct points.

So

Sy (x)σy (x) ≡ ωy (x) = ωe (x) ≡ Se (x)σe (x) ≡ Se (x)σy (x) (mod G(x)),

that is

(Sy (x) ’ Se (x))σy (x) ≡ 0 (mod G(x)).

The polynomials G(x) and σy (x) are relatively prime, because a common factor

would also divide ωy (x) by the Key Equation (1.3) and this contradicts the fact that

the degree of σy (x) was minimal. Hence, it follows that Sv (x) = Sy (x) ’ Se (x) = 0,

i.e. v ∈ C. This concludes the proof that y is of the form as described in equation

(1.2). It also concludes the proof of the proposition in the non“binary case.

The proof that the output v of At is of the form of Equation (1.2), with v ∈ C,

is similar to the non“binary case.

8 Preliminaries and notation

Chapter 2

Adaptive chosen ciphertext attacks

on the McEliece cryptosystem

Summary. Attacks are introduced in which a malicious sender or an adaptive

eavesdropper Eve has an oracle which allows her to ¬nd out whether a ciphertext

does, or does not, decrypt properly. From this information Eve can extract the

plaintext that was encrypted. In this chapter it is shown that the McEliece public“

key cryptosystem is susceptible to these kinds of attacks. This chapter is based on

joint work with E. Verheul and H.C.A. van Tilborg [VDT02].

2.1 Introduction

In the last decade, several forms of attacks have been published where some of

the inputs of an encryption system with a secret ¬xed key are adaptively chosen.

By letting each new input (either plaintext or ciphertext) depend on the previous

outputs and by looking at certain aspects of the resulting output at each step,

additional secret information of the cryptosystem (for example the ¬xed key) may

be determined. Among the studied aspects of the output are:

• the di¬erences in the output when the di¬erences in the plain inputs are known,

see [BS93], [Mat93];

• some statistical or number“theoretic aspects of the output of the cryptosystem

when errors are in¬‚icted to the cryptosystem itself (e.g. by radiation), see for

instance [BS97], [BDL97];

• so-called side-channel attacks, where the generation of the output is studied

instead of the output itself. For instance, one can study the execution time

when the precise complexity of the underlying cryptographic process is known

[Koc96], or the power consumption of the cryptographic algorithm [KJJ99].

In this chapter, we will look at a di¬erent setting. Here the attacker Eve has

access (for instance by interception) to one or more encrypted messages (called

9

10 Adaptive chosen ciphertext attacks on the McEliece cryptosystem

ciphertexts) sent by Alice to a receiver Bob. Eve™s aim is to recover the plaintext(s)

of those messages.

Also suppose that Eve has access to an oracle that can tell her whether a ci-

phertext deciphers correctly or not. Oracles similar to this one were studied by

Goldwasser, Micali and Tong in [GMT82]. Note that this oracle is weaker then

the one that is usually supposed to be at Eve™s disposal: Eve only gains knowledge

whether or not the ciphertext is valid, but she is not given the decrypted ciphertext.

In practice, such an oracle might be easy to obtain: Eve may have access to

Bob™s decryption device or Eve might be an active eavesdropper. Another realistic

possibility is that Bob™s decryption device is in fact automated, and will send an

automatic reply if the decryption somehow went wrong, asking for a retransmission.

This reply can then be intercepted and used by Eve.

This setting was used in [Ble98] to attack protocols based on the RSA encryp-

tion standard PKCS #1. In this chapter, an e¬cient attack against the McEliece

cryptosystem will be presented. The general idea of this attack is based on the