Articol cercetatori japonezi

8/2/2019 Articol cercetatori japonezi

1/14

C o r r e l a t i o n A t t a c k t o t h e B l o c k C i p h e r R C 5

a n d t h e S i m p l i e d V a r i a n t s o f R C 6

T a k e s h i S h i m o y a m a

3

, K i y o f u m i T a k e u c h i

y

, J u r i H a y a k a w a

y

3 F u j i t s u L a b o r a t o r i e s L T D .

4 - 1 - 1 K a m i k o d a n a k a , N a k a h a r a - k u , K a w a s a k i 2 1 1 - 8 5 8 8 , J a p a n

E - m a i l : s h i m o @ f l a b . f u j i t s u . c o . j p

y D e p t . o f I n f o r m a t i o n S y s t e m E n g i n e e r i n g , C h u o U n i v e r s i t y

1 - 1 3 - 2 7 , K a s u g a , B u n k y o - k u , T o k y o , 1 1 2 - 0 0 0 3 , J a p a n

E - m a i l : f k t a k e u c h , j h a y a k a w g @ t s u j i i - l a b . i s e . c h u o - u . a c . j p

A b s t r a c t . I n A u g u s t 1 9 9 9 , K n u d s e n a n d M e i e r p r o p o s e d a n a t t a c k t o

t h e b l o c k c i p h e r R C 6 b y u s i n g c o r r e l a t i o n s d e r i v e d f r o m

2

t e s t s . I n

t h i s p a p e r , w e i m p r o v e t h e a t t a c k a n d a p p l y t h i s m e t h o d t o t h e b l o c k

c i p h e r R C 5 a n d s i m p l i e d v a r i a n t s o f R C 6 , a n d s h o w s o m e e x p e r i m e n t a l

r e s u l t s . W e s h o w t h i s a p p r o a c h d i s t i n g u i s h t h e r a n d o m p e r m u t a t i o n a n d

R C 5 w i t h o f u p t o 2 0 r o u n d s b y u s i n g c h o s e n c i p h e r t e x t s a t t a c k . W e a l s o

s h o w o u r a p p r o a c h f o r d e r i v i n g t h e l a s t r o u n d k e y o f u p t o 1 7 r o u n d s

R C 5 b y u s i n g c h o s e n p l a i n t e x t a t t a c k . M o r e o v e r , w e s h o w f u l l r o u n d s

R C 5 w i t h s o m e w e a k k e y c a n b e b r o k e n b y u s i n g l e s s e r c o m p l e x i t y t h a n

t h a t o f t h e e x h a u s t i v e s e a r c h . A d d i t i o n a l l y , t h i s m e t h o d c a n b e a p p l i c a b l e

t o s i m p l i e d v a r i a n t s o f R C 6 , t h a t i s , R C 6 - I N F R , R C 6 - N F R , R C 6 - I , w e

o b s e r v e t h e a t t a c k t o t h e s e b l o c k c i p h e r s .

1 I n t r o d u c t i o n

R C 5 i s a b l o c k c i p h e r d e s i g n e d b y R . R i v e s t i n 1 9 9 4 [ 1 0 ] . O n e o f t h e r e a s o n t h a t

m a n y c r y p t o g r a p h e r s w e r e i n t e r e s t e d i n c r y p t a n a l y s i s o f R C 5 c o m e s f r o m i t s

s i m p l e s t r u c t u r e .

K a l i s k i a n d Y i n e v a l u a t e d R C 5 w i t h r e s p e c t t o d i e r e n t i a l a n d l i n e a r c r y p t -

a n a l y s i s [ 3 ] . T h e p a p e r s h o w s t h a t l i n e a r c r y p t a n a l y s i s i s a p p l i c a b l e f o r v e r s i o n s

o f R C 5 w i t h a s m a l l n u m b e r o f r o u n d s . M o r i a i e t a l . , f o u n d s o m e w e a k k e y

a g a i n s t l i n e a r a t t a c k [ 9 ] . A n i m p r o v e m e n t o f K a l i s k i a n d Y i n ' s a t t a c k b y a f a c -

t o r o f u p t o 5 1 2 w a s g i v e n b y K n u d s e n a n d M e i e r [ 4 ] . B i r y u k o v a n d K u s h i l e v i t z

p r o p o s e d d r a s t i c i m p r o v e m e n t o f t h e p r e v i o u s r e s u l t s d u e t o a n o v e l p r a c t i c a l

d i e r e n t i a l a p p r o a c h [ 1 ] . T h e i r a t t a c k r e q u i r e s 2

4 4

c h o s e n p l a i n t e x t s w h i c h i s

s m a l l e r t h a n c o m p l e x i t y o f e x h a u s t i v e k e y s e a r c h . I n t h e i r a p p r o a c h , t h e y s t u d y

m o r e c o m p l e x d i e r e n t i a l s t h a n i n p r e v i o u s w o r k s , a n d d e n e d a m o r e g e n e r a l

n o t a t i o n , s o c a l l e d \ g o o d p a i r , " w i t h r e s p e c t t o d a t a d e p e n d e n t r o t a t i o n s . I n

t h e i r m e t h o d , g o o d p a i r s w e r e s e a r c h e d b y u s i n g H a m m i n g w e i g h t s o f d i e r -

e n c e s f o r e a c h r o u n d , t h e n t h e k e y o f l a s t r o u n d w e r e d e r i v e d . T h e i r a t t a c k i n g

a l g o r i t h m , h o w e v e r , i s r a t h e r c o m p l i c a t e d a n d i t d o e s n o t s e e m s o e a s y t o d i s -

t i n g u i s h g o o d p a i r a n d o t h e r s c o r r e c t l y , b e c a u s e o f i n u e n c e s o f a d d i t i o n o f k e y

t o t h e h a m m i n g w e i g h t s o f d i e r e n t i a l s .


2/14

I n A u g u s t 1 9 9 9 , K n u d s e n a n d M e i e r p o s t e d t o t h e i n t e r n e t n e w s a n i n f o r -

m a t i o n o f t h e i r n e w p a p e r d e a l i n g w i t h c r y p t a n a l y s i s o f R C 6 [ 6 ] . I n t h e p a p e r ,

t h e y u s e d e x t r e m e l y d i e r e n t t e c h n i q u e f r o m t h e p r e v i o u s a p p r o a c h , t h a t i s , c o r -

r e l a t i o n s o b t a i n e d f r o m

2

t e s t . I n t h e i r a p p r o a c h , f o r x i n g e a c h o f t h e l e a s t

s i g n i c a n t v e b i t s i n s o m e w o r d s o f p l a i n t e x t s a n d i n v e s t i g a t e t h e s t a t i s t i c s o f

t h e 1 0 - b i t i n t e g e r o b t a i n e d b y c o n c a t e n a t i n g e a c h o f t h e l e a s t s i g n i c a n t v e b i t s

i n s o m e w o r d s o f c i p h e r t e x t s . T o m e a s u r e t h e e e c t o f t h e d i s t r i b u t i o n o f t h e

t a r g e t b i t s , t h e y f o r c e d t h e v a l u e s o f 1 0 b i t s b y t a k i n g a p p r o p r i a t e p l a i n t e x t s

a n d t h e y c o m p u t e d t h e

2

- v a l u e o f t h e 1 0 b i t i n t e g e r s , t h e n t h e y c o m p a i r e d t o

2

- d i s t r i b u t i o n w i t h 1 0 2 3 f r e e d o m , a n d d i s t i n g u i s h e d R C 6 f r o m a r a n d o m p e r -

m u t a t i o n . T h e y e s t i m a t e d f r o m s y s t e m a t i c e x p e r i m e n t a l r e s u l t s t h a t v e r s i o n o f

R C 6 w h o s e r o u n d i s r e d u c e d c a n b e d i s t i n g u i s h e d f r o m a r a n d o m p e r m u t a t i o n .

M o r e o v e r , t h e y c o n s t r u c t e d a k e y - r e c o v e r y m e t h o d f o r R C 6 w i t h u p t o 1 5 r o u n d s

w h i c h i s f a s t e r t h a n e x h a u s t i v e k e y s e a r c h .

I n t h i s p a p e r , w e i m p r o v e t h e K n u d s e n a n d M e i e r ' s a t t a c k i n g a l g o r i t h m o b -

t a i n e d f r o m

2

t e s t s , a n d a p p l y t h i s t o t h e R C 5 e n c r y p t i o n a l g o r i t h m . T h e n

w e s h o w t h e e x p e r i m e n t a l r e s u l t s o f a t t a c k i n g t h e R C 5 w i t h r e d u c e d r o u n d s .

O u r c o m p u t a t i n a l e x p e r i m e n t s s h o w t h a t R C 5 w i t h u p t o 2 0 h a l f r o u n d s c a n b e

d i s t i n g u i s h e d f r o m a r a n d o m p e r m u t a t i o n b y u s i n g 2

5 4

c h o s e n c i p h e r t e x t . M o r e -

o v e r , w e s h o w t h a t f u l l r o u n d R C 5 w i t h a w e a k k e y w h i c h i s a v a i l a b l e o n e i n 2

2 0

k e y s i s d i s t i n g u i s h a b l e f r o m r a n d o m p e r m u t a t i o n w i t h l e s s t h a n c o m p l e x i t y o f

e x h a u s t i v e k e y s e a r c h .

F u r t h e r m o r e , w e c o n s t r u c t a n a l g o r i t h m f o r k e y r e c o v e r y u s i n g t h e c o r r e l a t i o n

a n d s h o w t h e c o m p u t a t i o n a l e x p e r i m e n t s . F r o m o u r e x p e r i m e n t s , w e c o n c l u d e

t h a t t h e l a s t r o u n d k e y o f R C 5 w i t h u p t o 1 7 h a l f r o u n d s , o r R C 5 w i t h u p t o f u l l

r o u n d w i t h r e s p e c t t o a w e a k k e y c a n b e r e c o v e r e d b y u s i n g 2

5 4

c h o s e n p l a i n t e x t

a t t a c k w i t h s u c c e s s p r o b a b i l i t y 8 0 % .

A t l a s t , w e o b s e r v e t h e s t r e n g t h o f t h e s i m p l e v a r i a n t s o f R C 6 d e m o n s t r a t e d

i n [ 2 ] , t h a t i s R C 6 - I N F R , R C 6 - N F R a n d R C 6 - I , a g a i n s t o u r i m p r o v e d a t t a c k i n g

a l g o r i t h m s . T h e n w e s h o w R C 6 - I N F R , R C 6 - N F R w i t h u p t o 1 9 r o u n d s , a n d R C 6 -

I w i t h u p t o 1 5 r o u n d s a r e b r e a k a b l e f o r o u r i m p r o v e d d i s t i n g u i s h i n g a l g o r i t h m .

M o r e o v e r w e s h o w f u l l r o u n d R C 6 - I N F R , R C 6 - N F R w i t h r e s p e c t t o a w e a k k e y

e x i s t i n g i n a r a t i o o f o n e t o 2

4 5

a r e b r e a k a b l e b y u s i n g o u r d i s t i n g u i s h i n g a t t a c k .

2 P r e l i m i n a r y

I n t h i s s e c t i o n , w e n o t e s o m e n o t a t i o n s a n d d e n i t i o n s . A t r s t , w e r e c a l l t h e

2

t e s t s f o r d i s t i n g u i s h i n g a r a n d o m s e q u e n c e t a k i n g f r o m u n i f o r m d i s t r i b u t i o n

a n d n o n - r a n d o m s e q u e n c e . ( S e e [ 6 , 7 ] . )

P r o p o s i t i o n 2 . 1 L e t A b e a s e t f a

0

; : : : ; a

m 1

g L e t X = X

0

; : : : ; X

n 1

b e i n -

d e p e n d e n t a n d i d e n t i c a l l y d i s t r i b u t e d r a n d o m v a r i a b l e s t a k i n g f r o m t h e s e t A

u n i f o r m l y . L e t N

a

j

( X ) b e t h e c a r d i n a l i t y o f v a r i a b l e s i n X w h i c h i s e q u a l t o a

j


3/14

T a b l e 1 . T h e c h i - s q u a r e d i s t r i b u t i o n s w i t h 3 1 a n d 1 0 2 3 d e g r e e s o f f r e e d o m

l e v e l 0 . 5 0 . 9 0 0 . 9 5 0 . 9 9 0 . 9 9 9

2

3 0 . 3 3 4 1 . 4 2 4 4 . 9 9 5 2 . 1 9 6 1 . 0 9

2

d i s t r i b u t i o n o f 3 1 d e g r e e s o f f r e e d o m

l e v e l 0 . 5 0 . 9 0 0 . 9 5 0 . 9 9 0 . 9 9 9

2

1 0 2 2 . 0 1 0 8 0 . 9 4 1 0 9 8 . 9 2 1 1 3 0 . 8 9 1 1 6 8 . 8 5

2

d i s t r i b u t i o n o f 1 0 2 3 d e g r e e s o f f r e e d o m

F i g . 1 . R C 5 e n c r y p t i o n a l g o r i t h m

S [1]S [0]

S [i+1]


4/14

l s 5 ( A ) : l e a s t s i g n i c a n t 5 b i t s o f a 3 2 b i t s w o r d A

( A B ) : p l a i n t e x t o f R C 5 ( 3 2 b i t s * 2 )

( A

B

) : c i p h e r t e x t o f R C 5 ( 3 2 b i t s * 2 )

( A

i

B

i

) : o u t p u t o f i - t h h a l f r o u n d , e s p e c i a l l y , ( A

0

B

0

) = ( A B )

a n d ( A

r

B

r

) = ( A B )

x

i

: a m o u n t s o f d a t a d e p e n d e n t r o t a t i o n i n t h e i - t h h a l f r o u n d ,

t h a t i s l s 5 ( A

i

)

y

i

: x

r i + 1

3

2

t e s t s o f R C 5

I n t h i s s e c t i o n , w e e x p l a i n t h e

2

t e s t s f o r p l a i n t e x t s a n d c i p h e r t e x t s o f R C 5 . T h e

n o t a t i o n s a r e f o l l o w e d f r o m t h e p r e v i o u s s e c t i o n . W e e x a m i n e 4 d i e r e n t t y p e s

o f

2

t e s t s . F o r e a c h t e s t , w e o b s e r v e t h e

2

s t a t i s t i c s o f 5 b i t i n t h e p l a i n t e x t s

o r c i p h e r t e x t s .

T e s t 1 : F i x l e a s t s i g n i c a n t 5 b i t s o f p l a i n t e x t A t o 0 , a n d c o m p u t e

2

o f l e a s t

s i g n i c a n t 5 b i t s o f c i p h e r t e x t A

T e s t 2 : F i x l e a s t s i g n i c a n t 5 b i t s o f p l a i n t e x t A a n d B t o 0 a n d c o m p u t e

2

o f l e a s t s i g n i c a n t 5 b i t s o f c i p h e r t e x t A

T e s t 3 : F i x l e a s t s i g n i c a n t 5 b i t s o f c i p h e r t e x t B

t o 0 , a n d c o m p u t e

2

o f

l e a s t s i g n i c a n t 5 b i t s o f p l a i n t e x t B

T e s t 4 : F i x l e a s t s i g n i c a n t 5 b i t s o f c i p h e r t e x t A

a n d B

t o 0 a n d c o m p u t e

2

o f l e a s t s i g n i c a n t 5 b i t s o f p l a i n t e x t B

I f R C 5 w a s i d e a l r a n d o m p e r m u t a t i o n , t h e d i s t r i b u t i o n o f t h e

2

v a l u e i s

s i m i l a r t o t h e

2

d i s t r i b u t i o n o f 3 1 = 2

5

0 1 d e g r e e s o f f r e e d o m . S o , w e s e t

u p t h e t h r e s h o l d b y 4 5 i n o r d e r t o d i s t i n g u i s h f r o m a r a n d o m p e r m u t a t i o n . T h e

s e q u e n c e w h o s e

2

v a l u e e x t e n d s m o r e t h a n 4 5 c a n b e d i s t i n g u i s h f r o m a r a n d o m

p e r m u t a t i o n i n p r o b a b i l i t y 9 5 % . ( S e e T a b l e 1 . )

T a b l e 2 s h o w s t h e r e s u l t s o f

2

t e s t s . E a c h e n t r y o f

2

v a l u e i s a n a v e r a g e

o f 1 0 0

2

v a l u e o f d i e r e n t 1 0 0 k e y s . T h e n u m b e r s d e n o t e d b y b o l d c h a r a c t e r

a r e t h e

2

v a l u e s a t t h e r s t c o m i n g o v e r 4 5 . T h e s e e x p e r i m e n t s s h o w t h a t e a c h

a d d i t i o n a l t w o h a l f r o u n d s r e q u i r e a b o u t 2

6

t i m e s a s m a n y t e x t s t o g e t a b o u t

t h e s a m e

2

v a l u e . T h e r e s u l t s o f t h e T e s t 1 a n d T e s t 3 s h o w t h a t t h e e a c h

n u m b e r o f r e q u i r e d d a t a a r e a l m o s t s a m e . O n t h e o t h e r h a n d , e a c h t h e n u m b e r

o f r e q u i r e d e l e m e n t s i n T e s t 2 i s 2

3

t i m e s a s m a n y a s c o r r e s p o n d i n g o n e o f T e s t

4 , b e c a u s e o f t h e i n u e n c e s o f t h e i n i t i a l k e y S [ 1 ] . I t m e a n s t h a t i f t h e v a l u e o f

d a t a d e p e n d e n t r o t a t i o n a t t h e r s t r o u n d i s x e d 0 , t h e

2

v a l u e o f t h e t a r g e t

b i t s i n t h e o u t p u t o f l a s t r o u n d b e c o m e s m u c h m o r e l a r g e r .

4 D i s t i n g u i s h i n g a l g o r i t h m a n d w e a k k e y

B y t h e e x a m i n a t i o n d e s c r i b e d i n t h e p r e v i o u s s e c t i o n , w e c o n c l u d e t h a t t h e b e t t e r

w a y i n o r d e r t o d i s t i n g u i s h t h e R C 5 e n c r y p t i o n a n d a r a n d o m p e r m u t a t i o n i n


5/14

T a b l e 2 . E v a l u a t i o n s o f t h e

2

t e s t s ( T e s t 1 , . . . , T e s t 4 , a v e r a g e o f 1 0 0 k e y s )

T e s t 1 ( x l s 5 ( A ) = 0 ) T e s t 2 ( x l s 5 ( A ) = l s 5 ( B ) = 0 )

4 h a l f r o u n d s

# d a t a 2

1 0

2

1 1

2

1 2

2

1 3

2

1 4

2

1 5

2

3 0 3 3 3 7 4 1 4 7 6 6


# d a t a 2

1 6

2

1 7

2

1 8

2

1 9

2

2 0

2

2 1

2

3 0 3 1 3 4 4 1 5 2 7 0


# d a t a 2

2 2

2

2 3

2

2 4

2

2 5

2

2 6

2

2 7

2

2 9 3 1 3 1 3 4 4 6 6 3

1 0 h a l f r o u n d s

# d a t a 2

2 8

2

2 9

2

3 0

2

3 1

2

3 2

2

3 3

2

3 1 3 1 3 2 3 5 5 1 7 2


# d a t a 2

6

2

7

2

8

2

9

2

1 0

2

1 1

2

3 1 3 1 3 4 4 0 5 7 8 2


# d a t a 2

1 2

2

1 3

2

1 4

2

1 5

2

1 6

2

1 7

2

2 9 3 2 3 5 4 0 4 7 6 1


# d a t a 2

1 8

2

1 9

2

2 0

2

2 1

2

2 2

2

2 3

2

3 2 3 2 3 6 4 2 5 5 8 1


# d a t a 2

2 4

2

2 5

2

2 6

2

2 7

2

2 8

2

2 9

2

3 2 3 3 3 6 4 2 5 5 9 0

T e s t 3 ( x l s 5 ( A

0

) = 0 ) T e s t 4 ( x l s 5 ( A

0

) = l s 5 ( B

0

) = 0 )


# d a t a 2

1 0

2

1 1

2

1 2

2

1 3

2

1 4

2

1 5

2

3 1 3 2 3 4 3 8 4 7 5 9


# d a t a 2

1 6

2

1 7

2

1 8

2

1 9

2

2 0

2

2 1

2

3 0 3 3 3 5 4 0 4 9 6 6


# d a t a 2

2 2

2

2 3

2

2 4

2

2 5

2

2 6

2

2 7

2

2 9 3 1 3 1 3 4 4 6 6 3


# d a t a 2

2 8

2

2 9

2

3 0

2

3 1

2

3 2

2

3 3

2

3 0 3 1 3 3 3 5 5 0 6 9


# d a t a 2

3

2

4

2

5

2

6

2

7

2

8

2

1 2 1 1 3 9 4 8 6 2 9 4


# d a t a 2

9

2

1 0

2

1 1

2

1 2

2

1 3

2

1 4

2

3 2 3 4 3 6 3 9 4 7 6 0


# d a t a 2

1 5

2

1 6

2

1 7

2

1 8

2

1 9

2

2 0

2

3 2 3 4 3 8 4 4 6 5 1 0 1


# d a t a 2

2 1

2

2 2

2

2 3

2

2 4

2

2 5

2

2 6

2

3 2 3 4 3 5 4 2 5 6 8 5

t h e f o u r c o n d i t i o n s d e s c r i b e d i n T e s t 1 t o T e s t 4 , i s t h e c o n d i t i o n i n T e s t 4 . W e

c o n s i d e r a f o l l o w i n g a l g o r i t h m . I t i s o n e o f t h e c h o s e n c i p h e r t e x t a t t a c k .

A l g o r i t h m 4 . 1 ( D i s t i n g u i s h i n g a t t a c k )

I n p u t : R C 5 a l g o r i t h m o r r a n d o m p e r m u t a t i o n , n : a n u m b e r ;

O u t p u t : a n s w e r t h a t I n p u t i s R C 5 o r n o t ;

f o r i f r o m 1 t o n

L e t A

B

b e a r a n d o m n u m b e r s u c h t h a t l s 5 ( A

) = l s 5 ( B

) = 0 ;

( A B ) = d e c r y p t e d m e s s a g e o f ( A

B

) ;

c o u n t u p t h e c o u n t e r m a p [ l s 5 ( B ) ;

c a l c u l a t e

2

o f t h e m a p ;


6/14

T a b l e 3 . P r e c i s e l y e x a m i n a t i o n o f

2

a n d n u m b e r o f d a t a i n T e s t 4

( a v e r a g e o f 4 0 0 k e y s , m a c h i n e : 2 4 * U l t r a S P A R C 3 6 0 M H z )

# h a l f r o u n d s 6 7 8 9 1 0 1 1 1 2

# d a t a ( l o g 2 ) 1 2 . 3 2 1 5 . 7 1 1 8 . 5 8 2 1 . 3 1 2 4 . 0 9 2 7 . 8 1 3 0 . 1 7

2

4 5 4 6 4 6 4 5 4 5 4 6 4 5

T a b l e 4 . E s t i m a t i o n o f t h e n u m b e r o f r e q u i r e d t e x t f o r d i s t i n g u i s h i n g a t t a c k

# h a l f r o u n d s 1 3 1 4 1 5 1 6 1 7 1 8 1 9 2 0 2 1 2 2 2 3 2 4

# d a t a ( l o g

2

) 3 3 . 2 8 3 6 . 2 5 3 9 . 2 2 4 2 . 1 9 4 5 . 1 6 4 8 . 1 3 5 1 . 1 5 4 . 0 7 5 7 . 0 4 6 0 . 0 1 6 2 . 9 8 6 5 . 9 5

1 i n 2

5

k e y s 3 0 . 3 1 3 3 . 2 8 3 6 . 2 5 3 9 . 2 2 4 2 . 1 9 4 5 . 1 6 4 8 . 1 3 5 1 . 1 5 4 . 0 7 5 7 . 0 4 6 0 . 0 1 6 2 . 9 8

1 i n 2

1 0

k e y s 2 7 . 3 4 3 0 . 3 1 3 3 . 2 8 3 6 . 2 5 3 9 . 2 2 4 2 . 1 9 4 5 . 1 6 4 8 . 1 3 5 1 . 1 5 4 . 0 7 5 7 . 0 4 6 0 . 0 1

1 i n 2

1 5

k e y s 2 4 . 3 7 2 7 . 3 4 3 0 . 3 1 3 3 . 2 8 3 6 . 2 5 3 9 . 2 2 4 2 . 1 9 4 5 . 1 6 4 8 . 1 3 5 1 . 1 5 4 . 0 7 5 7 . 0 4

1 i n 2

2 0

k e y s 2 1 . 4 2 4 . 3 7 2 7 . 3 4 3 0 . 3 1 3 3 . 2 8 3 6 . 2 5 3 9 . 2 2 4 2 . 1 9 4 5 . 1 6 4 8 . 1 3 5 1 . 1 5 4 . 0 7

1 i n 2

2 5

k e y s 1 8 . 4 3 2 1 . 4 2 4 . 3 7 2 7 . 3 4 3 0 . 3 1 3 3 . 2 8 3 6 . 2 5 3 9 . 2 2 4 2 . 1 9 4 5 . 1 6 4 8 . 1 3 5 1 . 1

1 i n 2

3 0

k e y s 1 5 . 4 6 1 8 . 4 3 2 1 . 4 2 4 . 3 7 2 7 . 3 4 3 0 . 3 1 3 3 . 2 8 3 6 . 2 5 3 9 . 2 2 4 2 . 1 9 4 5 . 1 6 4 8 . 1 3

1 i n 2

3 5

k e y s 1 2 . 4 9 1 5 . 4 6 1 8 . 4 3 2 1 . 4 2 4 . 3 7 2 7 . 3 4 3 0 . 3 1 3 3 . 2 8 3 6 . 2 5 3 9 . 2 2 4 2 . 1 9 4 5 . 1 6

1 i n 2

4 0

k e y s 9 . 5 2 1 2 . 4 9 1 5 . 4 6 1 8 . 4 3 2 1 . 4 2 4 . 3 7 2 7 . 3 4 3 0 . 3 1 3 3 . 2 8 3 6 . 2 5 3 9 . 2 2 4 2 . 1 9

i f

2

4 5 t h e n r e t u r n t h e a n s w e r \ I n p u t i s R C 5 " ;

e l s e r e t u r n t h e a n s w e r \ I n p u t i s a r a n d o m p e r m u t a t i o n " ;

I n o r d e r t o e s t i m a t e t h e c o m p l e x i t y o f A l g o r i t h m 4 . 1 , w e c o m p u t e t h e n u m b e r

o f r e q u i r e d e l e m e n t s t h a t t h e

2

v a l u e e x c e e d s t h e 4 5 m o r e p r e c i s e l y , f o r e a c h

r o u n d s o f R C 5 . T a b l e 3 s h o w s t h e r e s u l t s . F r o m T a b l e 3 , w e c a l c u l a t e t h e r e l a t i o n

b e t w e e n t h e n u m b e r o f r e q u i r e d e l e m e n t s a n d t h e n u m b e r o f r o u n d s b y u s i n g

t h e m e t h o d o f l e a s t s q u a r e s ;

l o g

2

( # d a t a ) = + r + "

w h e r e r i s a n u m b e r o f h a l f r o u n d s a n d " i s a b i a s . T h e n w e h a v e = 0 5 3 3 =

2 9 7 " = 0 1 7 T h i s m e a n s t h a t e a c h a d d i t i o n a l o n e h a l f r o u n d s , A l g o r i t h m 4 . 1

r e q u i r e s a l m o s t 2

3

t i m e s a s m a n y t e x t s t o g e t a b o u t t h e s a m e

2

v a l u e o n a v e r a g e .

T a b l e 4 s h o w s t h a t t h e e s t i m a t e d n u m b e r o f r e q u i r e d t e x t s f o r A l g o r i t h m 4 . 1 .

I n A l g o r i t h m 4 . 1 , s i n c e t h e 1 0 b i t s i n c i p h e r t e x t b i t s a r e x e d z e r o , t h e t o t a l

a m o u n t s o f a d m i s s i b l e t e x t s i s 2

5 4

. F r o m T a b l e 4 , ( b y o m i t t i n g t h e s m a l l b i a s , )

o u r d i s t i n g u i s h a t t a c k c a n b e a p p l i c a b l e r e d u c e d R C 5 w i t h u p t o 2 0 h a l f r o u n d s .

N o w , w e c o n s i d e r t h e w e a k k e y . F r o m t h e a s s u m p t i o n o f A l g o r i t h m 4 . 1 ,

a m o u n t o f a d a t a d e p e n d e n t r o t a t i o n i n t h e l a s t r o u n d i s x e d 0 . M o r e o v e r i f t h e

c o n d i t i o n l s 5 ( S [ r + 1 ] ) = 0 h o l d s , t h e a m o u n t o f r o t a t i o n s o f l a s t t w o r o u n d s a r e

0 . I n t h i s c a s e , t h e l a s t r o u n d d o e s n o t i n u e n c e t h e

2

v a l u e , t h a t i s t h e s e c u r i t y

l e v e l i s e q u a l t o t h a t o f r 0 1 r o u n d s R C 5 . T h i s c a s e h a p p e n e v e r y o n e i n 2

5

k e y s . I n t h e s a m e w a y , i f t h e c o n d i t i o n l s 5 ( S [ r + 1 ] ) = = l s 5 ( S [ r 0 t + 2 ] ) = 0


7/14

h o l d s , t h e s e c u r i t y l e v e l a g a i n s t A l g o r i t h m 4 . 1 i s a s s a m e a s r 0 t r o u n d s R C 5 .

T h e r e i s o n e w e a k k e y i n 2

5 t

S i n c e , i t i s e a s y t o c h e c k w h e t h e r t h e k e y i s a w e a k k e y o r n o t , w e c a n n d

t h e f o l l o w i n g w e a k k e y .

k e y

0

= f 5 b , 2 d , 1 6 , 0 b , 7 a , 3 d , 9 e , c f , 7 e , 3 f , 9 f , c f , a f , d 7 , e b , 7 5 g

1 6

I n t h i s k e y , w e c a n c h e c k l s 5 ( S [ 1 9 ] ) = = l s 5 ( S [ 2 5 ] ) = 0 . T h e r e f o r e t h e 2 4

h a l f r o u n d R C 5 e n c r y p t i o n w i t h k e y

0

h a s t h e s a m e s e c u r i t y a s 1 7 = 2 4 0 7 h a l f

r o u n d s R C 5 . F r o m T a b l e 4 , t h i s R C 5 e n c r y p t i o n a l g o r i t h m i s d i s t i n g u i s h e d f r o m

r a n d o m p e r m u t a t i o n i n 2

4 5 1 6

n u m b e r o f d a t a .

5 K e y r e c o v e r y a l g o r i t h m

I n t h i s s e c t i o n , w e p r o p o s e a n k e y r e c o v e r y a l g o r i t h m b y u s i n g t h e

2

s t a t i s t i c s

o f R C 5 w i t h r h a l f r o u n d s .

5 . 1 K n u d s e n , M e i e r ' s a p p r o a c h

I n [ 6 ] , K n u d s e n e t a l . p r o p o s e d a n a l g o r i t h m f o r k e y r e c o v e r o f t h e e x t e n d e d k e y

o f t h e r s t r o u n d o f R C 6 b y u s i n g

2

s t a t i s t i c s . T h e i r a p p r o a c h u s e s t h e p r o p e r t y

t h a t t h e z e r o a m o u n t s o f t h e r s t r o u n d s d a t a d e p e n d e n t r o t a t i o n g r o w t h s t h e

2

v a l u e . F i r s t o f a l l , w e t r y t o m o d i f y t h e i r a p p r o a c h t o a k e y r e c o v e r y o f R C 5 .

A l g o r i t h m 5 . 1 ( K n u d s e n , M e i e r ( m o d i e d ) )

I n p u t : R C 5 e n c r y p t i o n a l g o r i t h m o f u n k n o w n s e c r e t k e y

O u t p u t : c a n d i d a t e o f l s 5 ( S [ 1 ] )

f o r e a c h p l a i n t e x t ( A B ) , w h e r e l s 5 b ( A ) = 0

c o m p u t e c i p h e r t e x t ( A

B

) ;

s

0

= 3 2 0 l s 5 ( B ) m o d 3 2 ;

y

1

= l s 5 ( A

) ;

c o u n t u p t h e m e m o r y m a p [ s

0

[ y

1

;

f o r e a c h s

0

2

[ s

0

=

2

o f m a p [ s

0

;

r e t u r n s s u c h t h a t

2

[ s = m a x f

2

[ s

0

j s

0

= 0 ; : : : ; 3 1 g ;

I n o r d e r t o o b t a i n t h e h i g h s u c c e s s r a t e o f t h e a b o v e k e y r e c o v e r y a l g o r i t h m ,

t h e a v e r a g e o f

2

i s f a r s m a l l e r t h a n t h e a m o u n t o f

2

i n t h e c a s e o f z e r o r o t a t i o n .

T a b l e 5 s h o w s t h e e x p e r i m e n t o f

2

v a l u e o f e a c h r o t a t i o n n e a r l y e q u a l t o 0 .

T h o u g h t h e a m o u n t o f

2

a t t h e 0 r o t a t i o n a l w a y s h i g h e s t ,

2

v a l u e s n e a r o f 0

s t i l l l a r g e , s o t h e a v e r a g e o f

2

i s n o t s m a l l . B y t h i s r e a s o n , w e c a n n o t o b t a i n

h i g h s u c c e s s r a t e o f t h i s a l g o r i t h m . I n f a c t , f r o m t h e e x p e r i m e n t a l r e s u l t s o f t h e

a l g o r i t h m , w e h a v e o n l y 2 0 { 3 0 % o f s u c c e s s p r o b a b i l i t y , a t m o s t . ( S e e F i g u r e 2 .

T h e l i n e o f s u c c e s s s h o w s t h e t i m e s t h a t t h e a n s w e r i s c o r r e c t , a n d t h e l i n e o f

n e a r l y s h o w s t h e t i m e s t h a t t h e a n s w e r i s i n t h e r a n g e o f c o r r e c t k e y 6 1 m o d

3 2 6 8 m e a n t h e c o r r e s p o n d t o 6 r o u n d s a n d 8 r o u n d s , r e s p e c t i v e l y )


8/14

T a b l e 5 . D a t a d e p e n d e n t r o t a t i o n o f 1 s t r o u n d a n d

2

v a l u e s

6 h a l f r o u n d o f R C 5 ( a v e r a g e o f 5 0 0 t e s t s )

d a t a 2 6 2 7 2 8 2 9 3 0 3 1 0 1 2 3 4 5 6

2

1 2

3 1 3 1 3 2 3 4 3 6 3 8 4 3 4 0 3 5 3 3 3 1 3 1 3 1

2

1 3

3 1 3 2 3 3 3 9 4 1 4 5 5 5 4 9 3 9 3 8 3 3 3 1 3 1

2

1 4

3 2 3 3 3 7 4 7 5 1 6 1 7 9 6 9 4 8 4 6 3 5 3 3 3 2

2

1 5

3 4 3 5 4 4 6 2 7 3 9 1 1 2 7 1 0 6 6 7 6 1 4 0 3 5 3 5

F i g . 2 . S u c c e s s p r o b a b i l i t y o f r e c o v e r i n g 5 b i t s o f k e y b y u s i n g m o d i e d K n u d s e n ,

M e i e r ' s a p p r o a c h

10

20

30

40

50

60

70

80

90

100

14 16 18 20 22 24 26 28

probability

number of data (log)

"nearly_6""success_6"


5 . 2 R e c o v e r i n g t h e l e a s t s i g n i c a n t 5 b i t s o f t h e l a s t r o u n d k e y

I n t h i s s e c t i o n , w e s h o w a n a l g o r i t h m f o r r e c o v e r i n g t h e l e a s t s i g n i c a n t 5 b i t s

o f t h e l a s t r o u n d k e y S [ r + 1 ] b y u s i n g c h o s e n p l a i n t e x t a t t a c k .

S u p p o s e t h e l e a s t s i g n i c a n t 5 b i t s o f e a c h w o r d s o f p l a i n t e x t s i s x e d 0 .

( N a m e l y ( l s 5 ( A ) = l s 5 ( B ) = 0 ) . ) I n t h i s s e c t i o n , w e o n l y u s e t h e c i p h e r -

t e x t s ( A

B

) c o r r e s p o n d i n g t o t h e p l a i n t e x t ( A B ) w h i c h s a t i s f y t h e c o n d i t i o n

l s 5 ( A

) = 0 . ( I n t h e n e x t s e c t i o n , w e a l s o u s e t h e t e x t s s u c h t h a t l s 5 ( A

) = 0

f o r c o n s t r u c t i n g t h e w h o l e p r o c e d u r e r e c o v e r i n g t h e l a s t r o u n d 3 2 b i t s k e y . ) W e

n o t e t h a t t h e a m o u n t o f l a s t r o u n d d a t a d e p e n d e n t r o t a t i o n y

1

i s a l w a y s 0 .

T h e n , w e h a v e y

2

= l s 5 ( B

) 0 l s 5 ( S [ r + 1 ] ) m o d 3 2 . T h e r e f o r e , l s 5 ( A

r 2

) =

( ( A

0 S [ r ) n y

2

) m o d 3 2 . S i n c e S [ r ] i s x e d v a l u e , t h e

2

v a l u e s o f ( ( A

0

S [ r ) n y

2

) m o d 3 2 a n d ( A

n y

2

) m o d 3 2 a r e a l m o s t s a m e . I n g e n e r a l , t h e

2

s t a t i s t i c s o f l s 5 ( A

r 2

) i s m u c h l a r g e r t h a n

2

s t a t i s t i c s o f l s 5 ( A

r

) . N o w , w e

c o n s i d e r t h e

2

v a l u e o f l s 5 ( A

r 2

) . W e m e n t i o n t h a t , s i n c e w e s u p p o s e t h a t

l s 5 ( A

) = 0 , w h e n y

2

s a t i s e s y

2

4 o r 2 8 y

2

, s o m e o f b i t s i n t h e l s 5 ( A

r 2

)

a r e x e d . T h e r e f o r e , i t i s m e a n i n g l e s s f o r c o m p u t e t h e

2

v a l u e o f l s 5 ( A

r 2

)


9/14

e x c e p t f o r t h e c a s e o f 5 y

2

2 7 . T h e a l g o r i t h m i s d e s c r i b e d i n A l g o r i t h m 5 . 2 .

T h e m e m o r y r e q u i r e m e n t o f t h i s p r o c e d u r e i s 2

1 5

w o r d s ( a t m o s t 1 2 8 K b y t e ) ,

a n d t h e d o m i n a n t s t e p o f c o m p u t a t i o n a l c o m p l e x t y i s t h e e n c r y p t i o n s t a g e .

A l g o r i t h m 5 . 2 ( S h i m o y a m a , T a k e u c h i , H a y a k a w a ( 1 ) )

I n p u t : R C 5 e n c r y p t i o n a l g o r i t h m o f u n k n o w n s e c r e t k e y ;

O u t p u t : c a n d i d a t e s l s 5 ( S [ r + 1 ] ) ;

f o r e a c h p l a i n t e x t ( A B ) , w h e r e l s 5 b ( A ) = l s 5 b ( B ) = 0


B

) ;

i f l s 5 ( A

) = 0

f o r e a c h c a n d i d a t e s s

0

2 f 0 ; : : : ; 3 1 g o f l s 5 ( S [ r + 1 ] )

y

2

= l s 5 ( B

) 0 s

0

m o d 3 2 ;

i f y

2

5 a n d y

2

2 7 ;

z

2

= l s 5 ( A

o y

2

) ;

c o u n t u p t h e m e m o r y m a p [ s

0

[ y

2

[ z

2

;

f o r e a c h s

0

y

2

2

[ s

0

[ y

2

=

2

o f m a p [ s

0

[ y

2

;

f o r e a c h s

0

a v e [ s

0

= a v e r a g e o f

2

[ s

0

[ y

2

;

r e t u r n s s u c h t h a t a v e [ s = m a x f a v e [ s

0

j s

0

= 0 ; : : : ; 3 1 g ;

[ S p e c i a l C r i t e r i o n

O c c a s i o n a l l y , t h e r e i s a c a s e t h a t t h e e a c h c o u n t e r s a t i s e s t h e c o n d i t i o n

m a p [ s

0

[ y

2

] [ 0 ] = = m a p [ s

0

[ y

2

] [ 3 1 ] = 0

f o r s o m e s

0

y

2

. I n t h i s c a s e , t h e c o r e e c t k e y i s ( y

2

+ s

0

) m o d 3 2 i n h i g h p r o b -

a b i l i t y . S o r e t u r n y

2

+ s

0

m o d 3 2 . B y u s i n g t h i s c r i t e r i o n , w e c a n e a s i l y o b t a i n

t h e s o l u t i o n , i n t h i s s p e c i a l c a s e .

F i g u r e 3 s h o w s t h a t t h e s u c c e s s p r o b a b i l i t y o f t h e A l g o r i t h m 5 . 2 f o r r o u n d s

6 a n d 8 o b t a i n e d f r o m 1 0 0 t i m e s o f c o m p u t e r e x p e r i m e n t s . E a c h o f s u c c e s s 6

a n d s u c c e s s 8 m e a n s t h e p r o b a b i l i t y t h a t t h e a n s w e r s o f 5 b i t s i s c o r r e c t , f o r 6

r o u n d s a t t a c k a n d 8 r o u n d s a t t a c k , r e s p e c t i v e l y , n e a r l y 6 a n d n e a r l y 8 m e a n s

t h e p r o b a b i l i t y t h a t d i e r e n c e o f a n s w e r a n d c o r r e c t v a l u e i s a t m o s t 6 1 . F o r

6 r o u n d s , w e h a v e s u c c e s s p r o b a b i l i t y m o r e t h a n 5 0 % b y u s i n g 2

1 8

d a t a , a n d

7 0 % b y u s i n g 2

2 0

. M o r e o v e r , t h e p r o b a b i l i t y t h a t t h e b i a s i s a t m o s t 6 1 , i s m o r e

t h a n 8 0 % w i t h 2

2 0

d a t a , a n d 9 0 % w i t h 2

2 1

d a t a . I n 8 r o u n d s , f o r e a c h s u c c e s s

p r o b a b i l i t y , t h e c o r r e s p o n d i n g n u m b e r o f p l a i n t e x t s i s i n c r e a s e d b y a c o n s t a n t

f a c t o r o f a b o u t 2

6

5 . 3 R e c o v e r y o f t h e l a s t r o u n d k e y

I n t h i s s e c t i o n , w e c o n s t r u c t a n a l g o r i t h m f o r r e c o v e r i n g t h e a l l b i t s o f l a s t

r o u n d k e y . S u p p o s e l s 5 ( A

) = i . T h e n t h e a m o u n t o f l a s t r o u n d d a t a d e p e n d e n t

r o t a t i o n y

1

i s e q u a l t o i s o y

2

= ( ( B

0 S [ r + 1 ] ) o i ) 8 i m o d 3 2 . L e t s

i

=

( S [ r + 1 o i ) m o d 3 2 . S i n c e t h a t t h e d i e r e n c e o f y

i

a n d ( ( B

0 ( s

i

n i ) ) o i ) 8


10/14

F i g . 3 . S u c c e s s p r o b a b i l i t y o f r e c o v e r i n g 5 b i t s o f t h e l a s t r o u n d k e y

( i m p l e m e n t e d )

0

10

20

30

40

50

60

70

80

90

100

14 16 18 20 22 24 26 28

probability




( e s t i m a t e d )

0

10

20

30

40

50

60

70

80

90

100

44 46 48 50 52 54 56

probability



i m o d 3 2 i s a t m o s t 6 1 , w e u s e ( ( B

0 ( s

i

n i ) ) o i ) 8 i m o d 3 2 i n s t e a d o f y

i

T h e a l g o r i t h m , d e s c r i b e d b e l o w , i s c o n s t r u c t e d b y t h e s a m e w a y d e s c r i b e d i n

t h e p r e v i o u s s e c t i o n .

A l g o r i t h m 5 . 3 ( S h i m o y a m a , T a k e u c h i , H a y a k a w a ( 2 ) )

I n p u t : R C 5 e n c r y p t i o n a l g o r i t h m o f u n k n o w n s e c r e t k e y ;

O u t p u t : c a n d i d a t e s S [ r + 1 ;

f o r e a c h p l a i n t e x t ( A B ) , w h e r e l s 5 b ( A ) = l s 5 b ( B ) = 0


B

) ;

y

1

= l s 5 ( A

) ;

f o r e a c h c a n d i d a t e s s

y

1

2 f 0 ; : : : ; 3 1 g o f l s 5 ( S [ r + 1 o y

1

)

y

2

= l s 5 ( ( B

0 ( s

y

1

n y

1

) ) o y

1

) m o d 3 2 ;


11/14

i f y

2

5 a n d y

2

2 7 ;

z

2

= l s 5 ( A

o y

2

) ;

c o u n t u p t h e m e m o r y m a p [ y

1

[ s

y

1

[ y

2

[ z

2

;

f o r e a c h y

1

s

y

1

y

2

2

[ y

1

[ s

y

1

[ y

2

=

2

o f m a p [ y

1

[ s

y

1

[ y

2

;

f o r e a c h y

1

s

y

1

a v e [ y

1

[ s

y

1

= a v e r a g e o f

2

[ y

1

[ s

y

1

[ y

2

;

f o r e a c h y

1

k e y [ y

1

= s

0

s u c h t h a t a v e [ s

0

= m a x f a v e [ i j i = 0 ; : : : ; 3 1 g ;

c o n c a t i n a t e k e y [ y

1

a n d d e r i v e 3 2 b i t k e y S ;

r e t u r n S ;

W e c o m m e n t t h a t f o r c o n c a t i n a t e t h e 3 2 c a n d i d a t e s o f 5 b i t s t o 3 2 b i t i n t e g e r ,

w e c a n u s e a n y e r r o r c o r r e c t i n g a l g o r i t h m , b y u s i n g t h e p r o p e r t y t h a t e a c h 5 b i t s

s o l u t i o n i s d i e r e n t f r o m t h e c o r r e c t v a l u e a t m o s t 6 1 i n h i g h p r o b a b i l i t y .

A t t h e e n d o f t h i s s e c t i o n , w e d i s c u s s t h e w e a k k e y . T h e k e y r e c o v e r i n g

a l g o r i t h m d e s c r i b e d i n t h i s s e c t i o n , w e s u p p o s e t h e l e a s t s i g n i c a n t 5 b i t s o f

e a c h w o r d s o f p l a i n t e x t s a r e x e d z e r o . F r o m t h e s a m e r e a s o n o f t h e e x i s t e n c e

o f w e a k k e y s a g a i n s t d i s t i n g u i s h i n g a t t a c k , i f t h e c o n d i t i o n l s 5 ( S [ 0 ] ) = 1 1 1 =

l s 5 ( S [ t ] ) = 0 h o l d s , t h e s e c u r i t y o f t h e r r o u n d s R C 5 e n c r y p t i o n u s i n g t h i s k e y

i s a s s a m e a s t h e s e c u r i t y l e v e l o f r 0 t + 1 h a l f r o u n d R C 5 .

F o r e x a m p l e , i n t h e c a s e t h a t t h e k e y s a t i s f y l s 5 ( S [ 0 ] ) = = l s 5 ( S [ 8 ] ) = 0 ,

2 4 r o u n d R C 5 w i t h t h i s k e y h a s t h e s a m e s e c u r i t y o f 1 7 h a l f r o u n d s . T h i s k e y

c a n b e f o u n d e v e r y o n e i n 2

4 5

k e y s . I n t h i s c a s e , f r o m F i g u r e 3 , w e c a n d e r i v e

t h e l a s t r o u n d k e y b i t s w i t h t h e s u c c e s s p r o b a b i l i t y 8 0 % .

6 A p p l i c a t i o n t o t h e s i m p l i e d v a r i a n t s o f R C 6

I n [ 2 ] , C o n t i n i e t a l . p r e s e n t e d t h e s o m e s i m p l i e d v a r i a n t s o f R C 6 , t h a t i s R C 6 - I ,

R C 6 - N F R , R C 6 - I N F R , a n d t h e c r y p t a n a l y z e d t o t h e s e f a m i l i e s . K n u d s e n e t a l .

p r o p o s e d t h e a t t a c k i n g m e t h o d t o R C 6 i n [ 6 ] . I n t h i s s e c t i o n , w e c o n s i d e r t h e

s e c u r i t y a g a i n s t t h e a t t a c k u s i n g

2

s t a t i s t i c s f o r t h e s i m p l i e d v a r i a n t s R C 6 - I ,

R C 6 - N F R , R C 6 - I N F R .

E a c h v a r i a n t h a s r e d u c e d r o u n d f u n c t i o n F c o m p a r e d w i t h R C 6 . ( S e e F i g u r e

4 a n d T a b l e 6 . ) E v e r y o n e o f s i m p l i e d v a r i a n t s i s n o t o n e o f t h e r e a l w o r l d b l o c k

c i p h e r , b u t p r o t o t y p e b l o c k c i p h e r f o r c o m p a r i n g t h e s e c u r i t y w i t h t h a t o f R C 6 ,

h o w e v e r , w e t h i n k t h a t c r y p t a n a l y s i s o f t h e s e v a r i a n t s m a y b e m e a n i n g f u l .

W e m e n t i o n t h a t t h e l e a s t s i g n i c a n t 5 b i t s o f t h e o u t p u t o f t h e r o u n d f u n c -

t i o n o f 3 v a r i a n t s a r e o b t a i n f r o m o n l y 5 i n p u t b i t s . T h e r e f o r e , w e c a n a p p l y t h e

A l g o r i t h m 5 . 2 t o e a c h v a r i a n t s w i t h a l i t t l e m o d i c a t i o n . T h e r e m a i n i n g p r o b l e m

i s a r e l a t i o n o f

2

v a l u e a n d n u m b e r o f r o u n d s .

W e o b s e r v e t h e f o l l o w i n g t w o t e s t s .

T e s t 1 : F i x l e a s t s i g n i c a n t 5 b i t s o f p l a i n t e x t A a n d C t o 0 , a n d c o m p u t e

2

o f l e a s t s i g n i c a n t 5 b i t s o f c i p h e r t e x t A a n d C


12/14

T a b l e 6 . R o u n d f u n c t i o n F o f v a r i a n t s o f R C 6

R C 6 - I N F R R C 6 - I R C 6 - N F R R C 6

F ( x ) = x x n 5 x 2 ( 2 x + 1 ) ( x 2 ( 2 x + 1 ) ) n 5

F i g . 4 . V a r i a n t s o f R C 6

S [1]S [0]

S[2i]


13/14

T a b l e 7 .

2

t e s t s t o t h e R C 6 v a r i a n t s

T e s t 1 : ( x l s b ( A ) , l s b ( C ) )

# r o u n d s I N F R N F R I R C 6

2 2

1 3

( 1 1 5 9 ) 2

1 3

( 1 1 2 2 ) 2

1 3

( 1 1 0 7 ) 2

1 4

( 1 1 7 8 )

4 2

2 5

( 1 1 5 2 ) 2

2 6

( 1 1 2 6 ) 2

2 9

( 1 1 7 1 ) 2

3 0

( 1 1 5 6 )

T e s t 2 ( x l s b ( A ) , l s b ( B ) , l s b ( C ) , l s b ( D ) )

# r o u n d s I N F R N F R I R C 6

2 2

7

( 1 1 9 3 ) 2

7

( 1 1 2 2 ) 2

1 3

( 1 1 0 0 ) 2

1 3

( 1 1 0 0 )

4 2

1 6

( 1 1 0 9 ) 2

1 7

( 1 1 0 2 ) 2

2 2

( 1 1 4 1 ) 2

2 9

( 1 1 7 1 )

6 2

2 8

( 1 1 6 4 ) 2

3 0

( 1 1 4 1 )

s a m e s e c u r i t y l e v e l a s 2 0 0 i r o u n d ,

l s 5 ( S [ 0 ] ) = = l s 5 ( S [ 2 i + 1 ] ) = 0

E s p e c i a l l y , i n t h e c a s e t h a t l s 5 ( S [ 0 ] ) = = l s 5 ( S [ 3 ] ) = 0 , 2 0 r o u n d R C 6 - I N F R ,

R C 6 - N F R c a n b e d i s t i n g u i s h i n g f r o m t h e r a n d o m p e r m u t a t i o n b y u s i n g l e s s e r

c o m p l e x i t y c o m p a i r e d w i t h e x h a u s t i v e s e a r c h .

7 C o n c l u s i o n

I n t h i s p a p e r , w e i m p r o v e d t h e K n u d s e n a n d M e i e r ' s a t t a c k i n g a l g o r i t h m o b -

t a i n e d f r o m

2

t e s t s , a n d a p p l i e d t h i s t o t h e R C 5 e n c r y p t i o n a l g o r i t h m . T h e n

w e s h o w e d t h e e x p e r i m e n t a l r e s u l t s o f a t t a c k i n g t h e R C 5 w i t h r e d u c e d r o u n d s .

O u r c o m p u t a t i n a l e x p e r i m e n t s s h o w e d t h a t R C 5 w i t h u p t o 2 0 h a l f r o u n d s c a n

b e d i s t i n g u i s h e d f r o m a r a n d o m p e r m u t a t i o n b y u s i n g 2

5 4

c h o s e n c i p h e r t e x t .

M o r e o v e r , w e s h o w e d t h a t f u l l r o u n d R C 5 w i t h a w e a k k e y w h i c h i s a v a i l a b l e

o n e i n 2

2 0

k e y s i s d i s t i n g u i s h a b l e f r o m r a n d o m p e r m u t a t i o n w i t h l e s s t h a n c o m -

p l e x i t y o f e x h a u s t i v e k e y s e a r c h .

F u r t h e r m o r e , w e c o n s t r u c t e d a n a l g o r i t h m f o r k e y r e c o v e r y u s i n g t h e c o r r e -

l a t i o n a n d s h o w e d t h e c o m p u t a t i o n a l e x p e r i m e n t s . F r o m o u r e x p e r i m e n t s , w e

c o n c l u d e d t h a t t h e l a s t r o u n d k e y o f R C 5 w i t h u p t o 1 7 h a l f r o u n d s , o r R C 5

w i t h u p t o f u l l r o u n d w i t h r e s p e c t t o a w e a k k e y c a n b e r e c o v e r e d b y u s i n g 2

5 4

c h o s e n p l a i n t e x t a t t a c k w i t h s u c c e s s p r o b a b i l i t y 8 0 % .

A t l a s t , w e o b s e r v e d t h e s t r e n g t h o f t h e s i m p l e v a r i a n t s o f R C 6 d e m o n s t r a t e d

i n [ 2 ] , t h a t i s R C 6 - I N F R , R C 6 - N F R a n d R C 6 - I , a g a i n s t o u r i m p r o v e d a t t a c k i n g

a l g o r i t h m s . T h e n w e s h o w e d R C 6 - I N F R , R C 6 - N F R w i t h u p t o 1 9 r o u n d s , a n d

R C 6 - I w i t h u p t o 1 5 r o u n d s a r e b r e a k a b l e f o r o u r i m p r o v e d d i s t i n g u i s h i n g a l g o -

r i t h m . M o r e o v e r w e s h o w e d f u l l r o u n d R C 6 - I N F R , R C 6 - N F R w i t h r e s p e c t t o a

w e a k k e y e x i s t i n g i n a r a t i o o f o n e t o 2

4 5

a r e b r e a k a b l e b y u s i n g o u r d i s t i n g u i s h -

i n g a t t a c k .


14/14

W e r e m a r k t h a t f u r t h e r i m p r o v e m e n t o f t h i s a t t a c k w i l l b e c o n s i d e r d . I t

m a y b e a l s o i n t e r e s t i n g t h a t t h e s i m i l a r a t t a c k s c a n b e a p p l i c a b l e o r n o t t o

a n o t h e r t y p e o f b l o c k c i p h e r , f o r e x a m p l e M A R S . F u r t h e r m o r e , i t s t i l l r e m a i n

s o m e i m p o r t a n t p r o b l e m o f h o w t o p r o t e c t o r d e s i g n b l o c k c i p h e r s t o b e s e c u r e ,

e s p e c i a l l y t o h a v e p r o v a b l e s e c u r i t y , a g a i n s t t h e a t t a c k s b y u s i n g

2

s t a t i s t i c s ,

b u t t h e s e a r e f u t u r e w o r k s .

R e f e r e n c e s

1 . A . B i r y u k o v , E . K u s h i l e v i t z , \ I m p r o v e d C r y p t a n a l y s i s o f R C 5 , " A d v a n c e s i n C r y p -

t o l o g y - E u r o c r y p t o ' 9 8 , L e c t u r e N o t e s i n C o m p u t e r S c i e n c e 1 4 0 3 , p p . 8 5 - 9 9 ,

S p r i n g e r V e r l a g , 1 9 9 8 .

2 . S . C o n t i n i , R . L . R i v e s t , M . J . B . R o b s h a w a n d Y . L . Y i n . " I m p r o v e d A n a l y s i s o f

S o m e S i m p l i e d V a r i a n t s o f R C 6 , " L . K n u d s e n , e d i t o r , F a s t S o f t w a r e E n c r y p t i o n ,

L e c t u r e N o t e s i n C o m p u t e r S c i e n c e , 1 6 3 6 p p . 1 - 1 6 , S p r i n g e r V e r l a g , 1 9 9 9 .

3 . B . K a l i s k i , Y . Y i n , \ O n D i e r e n t i a l a n d L i n e a r C r y p t a n a l y s i s o f t h e R C 5 E n -

c r y p t i o n A l g o r i t h m , " A d v a n c e s i n C r y p t o l o g y - C R Y P T O ' 9 5 , L e c t u r e N o t e s i n

C o m p u t e r S c i e n c e 9 6 3 , p p . 1 7 1 - 1 8 4 , S p r i n g e r - V e r l a g , 1 9 9 5 .

4 . L . K n u d s e n , W . M e i e r , \ I m p r o v e d D i e r e n t i a l A t t a c k s o n R C 5 , " N . K o b l i t z , e d i t o r ,

A d v a n c e s i n C r y p t o l o g y - C r y p t o ' 9 6 , L e c t u r e N o t e s i n C o m p u t e r S c i e n c e 1 1 0 9 , p p .

2 1 6 - 2 2 8 , S p r i n g e r - V e r l a g , 1 9 9 6 .

5 . J . K e l s e y , B . S c h n e i e r , a n d D . W a g n e r . " M o d n C r y p t a n a l y s i s , w i t h a p p l i c a t i o n s

a g a i n s t R C 5 P a n d M 6 , " I n L . K n u d s e n , e d i t o r , F a s t S o f t w a r e E n c r y p t i o n , L e c t u r e

N o t e s i n C o m p u t e r S c i e n c e 1 6 3 6 , p p . 1 3 9 - 1 5 5 , S p r i n g e r V e r l a g , 1 9 9 9 .

6 . L . K n u d s e n , W . M e i e r , \ C o r r e l a t i o n s i n R C 6 , " p r i v a t e c o m m u n i c a t i o n , 1 9 9 9 . ( a v a i l -

a b l e a t h t t p : / / w w w . i i . u i b . n o / ~ l a r s r / p a p e r s / r c 6 . p s )

7 . D . E . K n u t h . " T h e A r t o f C o m u p t e r P r o g r a m m i n g , " V o l . 2 . A d d i s o n W e s l e y , 1 9 8 1 .

8 . A . S e l c u k , \ N e w R e s u l t s i n L i n e a r C r y p t a n a l y s i s o f R C 5 , " S . V a u d e n a y , e d i t o r , F a s t

S o f t w a r e E n c r y p t i o n , L e c t u r e N o t e s i n C o m p u t e r S c i e n c e 1 3 7 2 , p p . 1 - 1 6 , S p r i n g e r

V e r l a g , 1 9 9 8 .

9 . S . M o r i a i , K . A o k i , a n d K . O h t a , " K e y - D e p e n d e n c y o f L i n e a r P r o b a b i l i t y o f R C 5 " ,

I E I C E T r a n s a c t i o n s o n F u n d a m e n t a l s o f E l e c t r o n i c s , C o m m u n i c a t i o n s a n d C o m -

p u t e r S c i e n c e s , V o l . E 8 0 - A , N o . 1 , ( J a n . , 1 9 9 7 ) .

1 0 . R . R i v e s t , \ T h e R C 5 E n c r y p t i o n A l g o l i t h m , " F a s t S o f t w a r e E n c r y p t i o n , S e c o n d

I n t e r n a t i o n a l W o r k s h o p , L e c t u r e N o t e s i n C o m p u t e r S c i e n c e 1 0 0 8 , p p . 8 6 - 9 6 ,

S p r i n g e r - V e r l a g , 1 9 9 5 .

T h i s a r t i c l e w a s p r o c e s s e d u s i n g t h e L

aT

E

X m a c r o p a c k a g e w i t h L L N C S s t y l e

Articol cercetatori japonezi

Documents

Transcript of Articol cercetatori japonezi