(ii). The syndrome is calculated:

(x + s)H = rG + h(m, e)G + f + xW ’R G RR’1 H T

= f H T = eH“ .

T

(iii). The Berlekamp“Massey algorithm is applied to the above syndrome. The

result of the algorithm will be the error vector e. If w(e) = t , Bob rejects the

signature.

(iv). The hash h(m, e) is recovered from the signature (x, s) and the error vector

e by computing

sW + xW + eW ’R = sR’1 W ’R + xW ’R GW ’R + eW ’R

= eW ’R + h(m, e) + xW ’R GW ’R +

+xW ’R GW ’R + eW ’R

= h(m, e).

(v). Finally, Bob calculates the value h(m, e) and compares it to the last result. If

they are equal, he accepts the signature as valid.

3.5 Cryptanalysis of the Alabbadi“Wicker scheme

Alabbadi and Wicker claimed that their scheme is resistant to the attacks that

proved successful against the Xinmei scheme and also to other attacks. First the

resistance of the Alabbadi“Wicker against the attacks described in Section 3.2 will

be investigated.

3.5.1 Resistance of the Alabbadi“Wicker scheme against attacks

The Alabbadi“Wicker scheme looks similar to the Xinmei scheme (with a hash

function) if the signatures x and s are added:

x + s = rG + h(m, e)G + e + xW ’R G R

= e + [r + h(m, e) + xW ’R ]G R

= (e + h (m, e)S G) R.

30 Digital signature schemes based on error“correcting codes

Note that the modi¬ed scheme retains this property. Alabbadi and Wicker adopted

di¬erent methods to defeat the attacks which are successful against the Xinmei

scheme. First a hash function h is applied to both the message m and the er-

ror vector e to prevent the homomorphism attack in Section 3.2.2. Furthermore a

k“bit vector r of arbitrary (but nonzero) weight has been introduced to the signa-

ture x. Bob cannot solve r from the signature x, and only Alice knows it. Thus

the Alabbadi“Wicker scheme defeats both the chosen“plaintext and the known“

plaintext attack in Section 3.2.2. Lastly the generator matrix G has been split into

two matrices W and V and the public keys (namely W ’R , W and W ) include only

partial information about G (of course, the null space of G is determined by both

H and the polynomial G(z)). So at least it is di¬cult to directly derive the secret

key G from the public keys. A total break appears to be infeasible, primarily be-

cause the public keys do not completely describe G (this is true because the matrix

W = W ’R GW ’R is not of full rank). Eve thus seems to be forced to perform an

exhaustive search through all possible generator matrices for the code C.

However, the Alabbadi“Wicker scheme is not as secure as they claimed. They

state that their digital signature scheme derives its security from the complexity

of three problems: the decoding of general linear error“correcting block codes, the

factoring of large matrices, and the derivation of a matrix from its right inverse.

In the following sections a universal forgery attack against the Alabbadi“Wicker

scheme will be presented.

3.5.2 A universal forgery of the Alabbadi“Wicker scheme

In [AW95], Alabbadi and Wicker analyzed the possibility of a universal forgery,

i.e. being able to sign an arbitrary message given only the public keys. Even though

their attack did not succeed, it did motivate the following attack using analogous

matrices.

Recovering the parity check matrix H

Even if H is not in the usual form, it is still possible for Eve to recover H from the

public keys and the veri¬cation procedure. From the second and the third step in

the veri¬cation of a signature the following equation can be obtained:

(x + s)H = eH T , (3.6)

where x, s and e and H are known to Eve. Note that the matrix dimensions of H T

and H are the same.

Suppose Eve is able to obtain signatures with n independent error vectors ei and

thus the corresponding (xi + si )H (1 ¤ i ¤ n). Then she can solve the parity check

matrix H T from the n Equations (3.6) by setting H T = E ’1 (X + S)H where E,

X and S are the matrices with as ith row respectively ei , xi or si (1 ¤ i ¤ n). The

complexity of solving H T in this way is only O(n3 ).

3.5 Cryptanalysis of the Alabbadi“Wicker scheme 31

˜

Calculating an analogous matrix R

After Eve has successfully recovered the parity check matrix H, she can try to ¬nd

the nonsingular matrix R according to the following method. From (3.3) and (3.4)

the following expression follows:

[H |W ] = R’1 [H T |W ’R ], (3.7)

where H and H T are n — (n ’ k) matrices and W and W ’R are n — k matrices.

So [H |W ], [H T |W ’R ] and R’1 are n — n matrices. Alabaddi and Wicker proved

that [H T |W ’R ] is a singular matrix, so Eve cannot ¬nd R’1 from Equation (3.7).

˜

Even so, she can obtain an analogous matrix R’1 which can also be used to forge a

signature.

Even though [H T |W ’R ] is not a full rank matrix, Eve can obtain a nonsingular

˜

row transformation matrix R’1 from (3.7), which satis¬es the following equations:

˜

H = R’1 H T , (3.8)

˜

W = R’1 W ’R . (3.9)

˜

Of course, it would be best if the matrix R’1 is equal to R’1 . However, Eve has

no way of knowing this. The attack still goes through, even if the two matrices are

˜ ˜

not equal. Eve may calculate the inverse matrix R from R’1 in polynomial time.

˜

The matrix R will play an important role in the following universal forgery.

Universal Forgery for the Alabaddi-Wicker scheme

˜

Eve will now calculate an analogous generator matrix G which should satisfy

˜

GH T = 0k—(n’k) . (3.10)

˜

Note that G is in general not equal to G, the generator matrix used by Alice (just

˜

like with the above R), but again this does not matter.

˜

’R

is a public key, Eve can calculate a left inverse W of W ’R , so

Since W

˜

W W ’R = Ik . (3.11)

˜ ˜ ˜ ˜ ˜

Then Eve calculates V = G + W . Again, in general V = V and W = W .

˜

Since W and W ’R are public keys, Eve can calculate a matrix Y by simple

algebraic means which satis¬es the following equation.

˜

W = W ’R GW ’R = Y W ’R . (3.12)

Now Eve is able to forge the signature of any message m. According to Alabbadi“

Wicker scheme, an n“bit error vector e of weight t is chosen at random. Since r is