(i). Eve alters the ciphertext slightly in such a way that there is a reasonable

probability that the message still deciphers correctly and submits the altered

message to her oracle.

(ii). Knowledge on whether the altered ciphertext deciphers correctly or not re-

veals new information and opens interesting new possibilities for adapting the

ciphertext.

Eve will continue to alter messages in this way, until she has retrieved enough

secret information. It is very likely that Eve will have to send a considerable number

of altered messages.

The aim of this attack is to recover the plaintext of a given ciphertext.

In this chapter, attacks on the McEliece [McE78] public“key cryptosystem will

be discussed. It is thus assumed that Eve has a validly encrypted McEliece message

for Bob which she can alter and for which she is able to ¬nd out (e.g. by using her

oracle) if the altered message remains a validly encrypted McEliece message.

The outline of this chapter is as follows: ¬rst the McEliece public“key cryptosys-

tem will be described in Section 2.2. Section 2.3 is the main part of this chapter;

there an e¬ective message-recovery attack on the McEliece public“key cryptosystem

will be described based on the maximal error correcting property of the two widely

used decoding algorithms (See Property 1.2.2). In Section 2.4 some countermeasures

against the described attack are considered.

Related Work

The attack described here di¬ers from the one in [Ber97] where it is assumed

that the (original) sender, instead of an eavesdropper, sends the same message more

than once using di¬erent random error vectors. Also, an independent description of

an algorithm, similar to ours, has appeared in [HGS99]. However, their algorithm

2.2 The McEliece Public“Key Cryptosystem 11

is signi¬cantly less e¬cient. Also, their conclusion that the McEliece cryptosystem

should not be used because of this attack is unsupported - in Section (2.4) e¬ective

countermeasures will be discussed.

2.2 The McEliece Public“Key Cryptosystem

In 1978, McEliece [McE78] proposed a public“key cryptosystem based on the

general di¬culty of decoding. Consider a generator matrix G, generating a q“ary

code C with parameters [n, k, d], which is constructed by a user Bob. Let 0 ¤ t ¤

e = (d ’ 1)/2 and let At be an e¬ective decoding algorithm for C that can correct

at most t errors.

Now, to use this in a cryptographic setting, Bob generates a random, invertible,

q“ary, k — k matrix S and a random permutation matrix P of size n — n. The public

key of Bob is G = SGP together with the value of t. The matrices, S, G, P are kept

secret. The idea is that G , although it generates a codespace C which is equivalent

to C, behaves like a “random” generator matrix for which the decoding problem is

hard.

Now suppose that another user, say Alice, wants to encrypt a message m ∈ Fk q

for Bob. To this end she generates a random error vector e of weight w(e) ¤ t and

forms:

r = mG + e (= mSGP + e). (2.1)

Note that in some variants the weight of the error vector e is always exactly equal

to t. On delivery, Bob calculates

rP ’1 = (mS)G + eP ’1 .

As eP ’1 has the same weight as e, Bob can determine mS (and eP ’1 ) from

rP ’1 by means of his e¬ective decoding algorithm At . Since S is a invertible matrix,

Bob can easily determine m, for instance by the method of Gaussian elimination.

More in particular, in the original scheme McEliece proposed to use binary (i.e.

q = 2), irreducible Goppa codes, with n = 1024, k ≈ 524 and t = 50. There exist

many (di¬erent) codes of these parameters, they are easy to generate (randomly)

and e¬cient decoding algorithms for them are easy to ¬nd. McEliece™s construction

can be extended to larger classes of codes (for instance non“binary Goppa codes).

No details will be given here as that is not necessary for the attack; it su¬ces to

mention the following bounds on the security“related parameters of the system.

Assumption 2.2.1 (The security of McEliece cryptosystem) The following ob-

servations can be made on the parameters of a McEliece public“key cryptosystem:

Sec“1. k ≈ n/2 ≥ 512: this makes “syndrome decoding” as well as an exhaustive

search for ¬nding the nearest codeword to the received word infeasible;

12 Adaptive chosen ciphertext attacks on the McEliece cryptosystem

Sec“2. 50 ¤ t ¤ 100: this makes all kinds of techniques that are based on guess-

ing/¬nding k (almost) error free coordinates less time consuming than the

methods in Sec“1, but still infeasible (see [BKT99; Dum96; McE78]).

The maximal error property (Property 1.2.2) states that the decoding algorithm

At , on input r, never returns an element c ∈ C at distance more than t from r. It is

important to realize that if too many transmission errors have occurred, the received

vector r may be at distance ¤ t from another codeword than the transmitted one.

In this case At will not return an error message. The probability that this occurs,

will be of importance in the analysis of the attack and will be discussed in Section

2.3. Recall (see Proposition 1.2.3) that the two relevant decoding algorithms for

Goppa codes have the maximal error property.

2.3 An adaptive chosen ciphertext attack

Now the attack on the McEliece cryptosystem will be described.

Algorithm 2.3.1 [Adaptive chosen ciphertext attack on McEliece]

Assume that the decoding algorithm At used in a McEliece cryptosystem has

the maximal error property. Let r be the ciphertext sent by Alice and intercepted

by Eve (it is of the form rA = mG + eA ). Then Eve does the following:

Step 1. Increase the number of errors made by Alice to exactly t.

In order to increase the number of errors to the maximum, Eve repeatedly

changes a random coordinate arbitrarily (though each coordinate is selected

at most once) and sends the resulting codeword to Bob until an error message

is returned, i.e. the message is not accepted as a valid McEliece ciphertext.

Once this occurs, Eve knows that this message contains exactly one error too

much, and thus that the previous message she sent to Bob has the maximum

number of errors. She now goes on to Step 2 with this message r .

Step 2. Determine enough error“free coordinates.

Once Eve knows she has a message r with exactly t errors, she can start

probing a random coordinate (di¬erent from all preceding choices, including

those made in Step 1) by changing this arbitrarily in r , and sending the

mutated message to Bob. If an error message is returned, this coordinate

was error“free. Once enough error“free coordinates are determined, Eve can

determine the plaintext in Step 3.

Step 3. Determine the plaintext.

Once Eve knows enough error“free coordinates, she can solve the matrix equa-

tion r = mG for the plaintext m by using Gaussian elimination on the

columns corresponding with the (known) error“free coordinates.

Before analyzing this algorithm, we introduce the following notion.

2.3 An adaptive chosen ciphertext attack 13

De¬nition 2.3.2 The weight distribution {Aw } of an [n, k, d] code C will be called

approximately binomial if (in the context of the problem here) the weight distribution

may be approximated as follows:

n

(q ’ 1)w

w

Aw ≈ , d ¤ w ¤ n. (2.2)

q n’k

Note that in this case,

n n n

(q ’ 1)w (1 + (q ’ 1))n

= q k = |C|,

w

Aw ≈ =

q n’k q n’k

w=0 w=0

as it should be. Certainly the weight distribution of Fn itself is binomial (in this

q

case the approximation in (2.2) is actually an equality). We are not familiar with

any result on how well the weight distribution of Goppa codes can be approximated

by the binomial distribution, but based on [KFL85; KL95] and [MS77, Section 9.10]