k k k k

Fig. 1. Rule A and Rule B

Then the multi-exponentiation result is computed Interleaved sliding window exponentiation es-

using that table of powers. The following algo- sentially interleaves the operations of n single

rithm shows how this computation can be imple- exponentiations using left-to-right sliding window

mented including left-to-right scanning of expo- exponentiation, saving many of the squarings. In

nents up to b bits. The algorithm accesses the bits groups where computing inverses of elements is

e j[i] of the binary representations possible very quickly, it is possible to similarly in-

terleave the operations of n single exponentiations

b’1

using left-to-right signed digit exponentiation for

ej = e j[i]2i , e j[i] ∈ {0, 1}

faster multi-exponentiation.

i=0

Bodo M¨ ller

o

of the exponents; the notation e j[i . . . h] is short-

hand for ν=h e j[ν]2ν’h .

i

References

A ← identity element

[1] Moller, B. (2001). “Algorithms for multi-

for j = 1 to n do

exponentiation.” Selected Area in Cryptography”

window position j ← ’1 SAC 2001, Lecture Notes in Computer Science,

for i = b ’ 1 down to 0 do vol. 2259, eds. S. Vaudenay and A.M. Youssef.

Springer-Verlag, Berlin, 165“180.

A ← A—¦ A

[2] Straus, E.G. (1964). “Problems and solutions: Ad-

for j = 1 to n do dition chains of vectors.” American Mathematical

if window position j = ’1 Monthly, 71, 806“808.

[3] Yen, S.-M., C.-S. Laih, and A.K. Lenstra (1994).

and e j[i] = 1 then

“Multi-exponentiation.” IEE Proceedings”Compu-

h←i ’k+1 ters and Digital Techiques, 141, 325“326.

if h < 0 then

h←0

SKIPJACK

while e j[h] = 0 do

h← h+1 Skipjack [6] is the secret key encryption algorithm

window position j ← h (see symmetric cryptosystem) developed by the

E j ← e j[i . . . h] NSA for the Clipper chip initiative (including the

Capstone chip and the Fortezza PC card). It was

if window position j = i then

implemented in tamper-resistant hardware and

A ← A —¦ G j,E j its structure was kept secret since its introduction

window positioni ← ’1 in 1993.

On June 24, 1998, Skipjack was declassi¬ed,

return A

and its description was made public on the web

The algorithm as written can be improved by a site of NIST [6]. It is an iterative block cipher with

simple optimization: while A still has its initial 64-bit block, 80-bit key and 32 rounds. It has two

value, omit the statement A ← A —¦ A, and use a types of rounds, called Rule A and Rule B. Each

direct assignment A ← G j,E j instead of the ¬rst as- round is described in the form of a linear feedback

signment A ← A —¦ Gj,E j . With this optimization, an shift register with an additional nonlinear keyed

interleaved sliding window exponentiation takes G permutation. Rule B is basically the inverse of

up to n + b ’ 1 squarings and on average about Rule A with minor positioning differences. Skip-

jack applies eight rounds of Rule A, followed by

b’1

n · 2k’1 ’ 1 + eight rounds of Rule B, followed by another eight

k+1

rounds of Rule A, followed by another eight rounds

general group operations. of Rule B. The original de¬nitions of Rule A and

Slide attack 587

Rule B are given in Figure 1, where counter is the in Cryptology”CRYPTO™99, Lecture Notes in Com-

puter Science, vol. 1666, ed. M. Wiener. Springer-

round number (in the range 1 to 32), G is a four-

Verlag, Berlin, 165“180.

round Feistel permutation whose F function is de-

[6] NIST (1998). “SKIPJACK and KEA algorithm spec-

¬ned as an 8 — 8-bit S box, called F Table, and each

i¬cation.” Technical Report, http://csrc.nist.gov/

round of G is keyed by eight bits of the key.

CryptoToolkit/skipjack/skipjack-kea.htm. Version

The key schedule of Skipjack takes a 10-byte

2.0.

key, and uses four of them at a time to key each G

permutation. The ¬rst four bytes are used to key

the ¬rst G permutation, and each additional G per-

mutation is keyed by the next four bytes cyclically,

SLIDE ATTACK

with a cycle of ¬ve rounds.

Skipjack has been subject to intensive analy-

Slide attack is generic attack designed by

sis [2“5]. For example, Skipjack reduced to (the

Biryukov and Wagner [1, 2]. It can be applied in

¬rst) 16 rounds can be attacked with 217 cho-

both known plaintext or chosen plaintext scenar-

sen plaintexts and 234 time of analysis [5], which

ios. It can be viewed as a variant of a related key

may be reduced to 214 texts and 216 steps using

attack, in which a relation of the key with itself

the yoyo-game approach [1]. Attacking the mid-

is exploited. The main feature of this attack is

dle 16 rounds of Skipjack requires only 3 cho-

that it realizes a dream of cryptanalysts: if the

sen plaintexts and 230 time of analysis. The cur-

cipher is vulnerable to such an attack, the com-

rently most successfull attack against the cipher is

plexity of the attack is independent of the num-

the imposible differential attack which breaks 31

ber of rounds of the ciphel. A typical slide of

rounds out of 32, marginally faster than exhaus-

one encryption against another by one round (un-

tive search.

der the same key) is shown in Figure 1. If the

In addition, it is worth noting that Skipjack can

equation F1 (P0 , K1 ) = P1 holds, the pair is called

be attacked by a generic time-memory tradeoff ap-

a slid pair. The attacker would then obtain two

proach requiring 280 steps of precomputation and

equations:

254 80-bit words (i.e., 260 bits) of memory, but then

each search for a key requires only 254 steps of F1 (P0 , K1 ) = P1 , Fr (C0 , Kr ) = C1 ,

computation.

where the second equation would hold for free

Alex Biryukov due to sliding. These equations involve only a

single round function, and thus could be solved

by the attacker for the secret subkeys K1 , Kr of

References

these rounds. The attacker may create properly

slid pairs (P0 , P1 ) by birthday paradox or by care-

[1] Biham, E., A. Biryukov, O. Dunkelman, E. Richard-

ful construction. For an arbitrary cipher the attack

son, and A. Shamir (1999). “Initial observations on

has complexity of 2n/2 known-plaintexts, where n

skipjack: Cryptanalysis of Skipjack-3XOR.” Selected

Areas in Cryptography, SAC™98, Lecture Notes in is the blocksize. For a Feistel cipher complexity is

Computer Science, vol. 1556, eds. S.E. Tavares and reduced to 2n/4 chosen plaintexts.

H. Meijer. Springer-Verlag, Berlin, 362“376. Several ciphers or slight modi¬cations of exist-

[2] Biham, E., A. Biryukov, and A. Shamir (1999). ing ciphers have been shown vulnerable to such

“Cryptanalysis of Skipjack reduced to 31 rounds us-

attacks: for example the Brown-Seberry variant

ing impossible differentials.” Advances in Crypto-

of the Data Encryption Standard (DES) [3] (rota-

logy”EUROCRYPT™99, Lecture Notes in Computer

tions in key-schedule are by seven positions, in-

Science, vol. 1592, ed. J. Stern. Springer-Verlag,

stead of varying 1, 2 rotations as in the original

Berlin, 12“23.

DES), DES-X, the Even-Mansour scheme [4], ar-

[3] Granboulan, L. (2001). “Flaws in differential crypt-