analysis of Skipjack.” Proceedings of Fast Software

schedule as well as round-reduced versions of

Encryption”FSE 2001, Lecture Notes in Computer

Science, vol. 2335, ed. M. Matsui. Springer-Verlag, GOST. The basic attack has been extended into

Berlin, 328“335. a slide-with a twist, a technique where encryption

[4] Hwang, K., W. Lee, S. Lee, S. Lee, and J. Kim (2002). is slid against decryption and complementary slide

“Saturation attacks on round Skipjack.” Fast Soft-

ware Encryption”FSE 2002, Lecture Notes in Com-

F1 F 2 F 3 . . . Fr

P0 C1

puter Science, vol. 2365, eds. J. Daemen and V.

Rijmen. Springer-Verlag, Berlin, 100“111. F1 F 2 F 3 . . . Fr

P1 C2.

[5] Knudsen, L.R., M. Robshaw, and D. Wagner (1999).

Fig. 1. A typical slide attack

“Truncated differentials and Skipjack.” Advances

588 Sliding window exponentiation

Like 2k -ary exponentiation, it generalizes binary

technique [2], where the inputs to the rounds do

not have to be identical but may have the differ- exponentiation and is parameterized by a positive

integer k, where the case k = 1 is the same as bi-

ence which is canceled out by a difference in the

keys. In the same paper another generalization nary exponentiation. Sliding window exponenti-

of the technique for the case of a composition of ation can be considered an improved variant of

2k -ary exponentiation: with identical k ≥ 2, slid-

strong round functions is given.

It is clear that slide-attack would apply to ing window exponentiation needs storage for fewer

any iterative construction which has enough self- group elements and usually performs less applica-

tions of the group operation than 2k -ary exponenti-

similarity in its rounds. It could be applied

to block-ciphers as described above, to stream- ation. However, the algorithms for sliding window

exponentiation are slightly more complicated. 2k -

ciphers (see for example resynchronization attack

ary exponentiation uses the 2k -ary representation

on WAKE-ROFB [1]) or to MAC and hash-

functions (see for example a recent slid pair dis- of exponents, which can be considered as looking at

covery for SHA-1 by Saarinen [5]. the binary representation through ¬xed windows

In practice the attack seems easy to avoid by of width k:

breaking the similarity of the round transforms

001110100011001010

by applying round counters (as is done for ex-

ample in Skipjack) or different random constants The sliding window method is based on the obser-

in each round (as in Rijndael/AES, SHA-256 and vation that fewer windows of width up to k can

many other constructions). Whether such simple suf¬ce to cover all nonzero exponent bits if one

changes are indeed suf¬cient is a matter of further allows the windows to take arbitrary positions.

research. Also, one can arrange for all windows to be odd-

valued (i.e., have a 1 as the rightmost bit). Then

Alex Biryukov the bits covered by each single window correspond

to a value in the set Bk = {1, 3, . . . , 2k ’ 1}, and

References the number of possible window values is less than

with the 2k -ary exponentiation method. Covering

the binary representation of the exponent by such

[1] Biryukov, A. and D. Wagner (1999). “Slide attacks.”

windows yields a base-two representation of the

Proceedings of Fast Software Encryption”FSE™99,

exponent that uses the digit set {0} ∪ Bk . One pos-

Lecture Notes in Computer Science, vol. 1636,

ed. L.R. Knudsen. Springer-Verlag, Berlin, 245“ sible way to determine windows for a given ex-

259. ponent is to look at the binary representation of

[2] Biryukov, A. and D. Wagner (2000). “Advanced slide the exponent from left to right, starting a new

attacks.” Advances in Cryptology”EUROCRYPT

window whenever a nonzero bit is encountered,

2000, Lecture Notes in Computer Science, vol. 1807,

choosing the maximum width up to k for this par-

ed. B. Preneel. Springer-Verlag, Berlin, 589“606.

ticular window such that the rightmost bit is also

[3] Brown, L. and J. Seberry (1990). “Key scheduling in

nonzero:

DES type cryptosystems.” Advances in Cryptology”

AUSCRYPT™90, Lecture Notes in Computer Science, 00 1110100011001010

vol. 453, eds. J. Seberry and J. Pieprzyk. Springer-

’ 70100003000050

Verlag, Berlin, 221“228.

[4] Even, S. and Y. Mansour (1997). “A construction of Another possibility is to look at the binary repre-

a cipher from a single pseudorandom permutation.”

sentation of the exponent from right to left, start-

Journal of Cryptology, 10 (3), 151“162.

ing a new width-k window whenever a nonzero bit

[5] Saarinen, M.-J.O. (2003). “Cryptyanalysis of block

is encountered:

ciphers based on SHA-1 and MD5.” Proceedings

of Fast Software Encryption”FSE 2003, Lecture 0 01110100011001010

Notes in Computer Science, vol. 2887, ed. T.

’ 300500003000050

Johansson. Springer-Verlag, Berlin, 36“44.

Such left-to-right scanning or right-to-left scan-

ning yields a representation

l’1

SLIDING WINDOW e= ei 2i , ei ∈ {0} ∪ Bk .

EXPONENTIATION i=0

In the following we assume that we have such a

Sliding window exponentiation is an approach for representation of some positive integer e with l

chosen minimal; thus, el’1 = 0.

computing powers in any group (or semigroup).

Sliding window exponentiation 589

The left-to-right sliding window exponentiation starting the exponentiation; here, right-to-left

method computes ge , where g is an element of the scanning can be used to determine it digit by digit

group (or semigroup), as follows. First the powers when it is needed. The algorithm as written can

for odd exponents 1 up to 2k ’ 1 are computed and be optimized similarly to the right-to-left 2k -ary

exponentiation method to avoid (at least) 2k’1 ap-

stored:

plications of the group operation. The idea used to

G1 ← g

perform sliding window exponentiation in right-

A← g—¦g to-left fashion is due to Yao [3]; the sub-algorithm

for d = 3 to 2k ’ 1 step 2 do d

shown above for computing d∈{1,3,...,2k ’1} Bd is

due to Knuth [1, answer to exercise 4.6.3“9].

Gd ← Gd’2 —¦ A

The number of group operations performed dur-

Then ge is computed using the tables of powers ing a sliding window exponentiation with max-

G1 = g, G3 = g3 , . . . , G2 K ’1 = g2 ’1 :

K

imum window width k depends on the length l

of the sliding window representation and on the

A ← Gel’1

number of digits in the representation el’1 , . . . , e0

for i = l ’ 2 down to 0 do

that are non-zero. For any b-bit exponent (2b’1 ¤

A ← A—¦ A e ¤ 2b ), the length l is bounded by b ’ k < l ¤ b.

if ei = 0 then Assume that left-to-right or right-to-left scanning

is performed on a sequence of independently and

A ← A —¦ Gei

uniformly random bits; then a new window will

return A

be started on average every k + 1 bits. For b-

bit exponents, one bit is necessarily nonzero, and

Note that in practice it is not necessary to com-

pletely derive the representation el’1 , . . . , e0 be- both scanning techniques will usually have an

unused part in the ¬nal window when the end

fore starting the exponentiation; instead, left-to-

of the exponent is reached. The expected num-

right scanning can be used to determine it digit

ber of nonzero values among el’1 , . . . , e0 for ran-

by digit when it is needed without storing it com-

dom b-bit exponents lies between b/(k + 1) and

pletely. Left-to-right sliding window exponentia-

1 + (b ’ 1)/(k + 1).

tion is a slight modi¬cation of the method de-

Using the upper bounds to derive estimates for

scribed in [2, proof of Theorem 3]; the idea to use

average performance that are on the safe side (i.e.

variable windows is from [2, p. 912])

Like binary exponentiation and 2k -ary expo- slightly pessimistic) gives b squaring operations