T E L KO M NIK A , V o l . 1 1 No . 2 , J u n e  2 0 1 3 p p 3 8 1 ~ 3 9 2 IS S N: 1 6 9 3 - 6 9 3 0 a ccr e d i te d  b y D GH E   ( D I K T I ) , D e c r e e  N o : 5 1 /D i kti / K e p /2 0 1 0 3 8 1 Re c e i v e d De c e m b e r   3 0 2 0 1 2 ; R e v i s e d M a r c h  1 2 , 2 0 1 3 ; A c c e p t e d M a r c h  2 5 , 2 0 1 3 O n   t h e S e cu r it y o f  NM A C a n d  It s V ar ian t s F a n b a o  L iu 1 , Ch a n g x ia n g S h e n 2 , T a o  X i e 3 , D e n g g u o  F e n g 4 1 Sc h o o l   o f   C o m p u t e r,   N a t i o n a l   U n i v e rs i t y   o f   D e f e n s e   T e c h n o l o g y ,   C h a n g s h a ,   4 1 0 0 7 3 ,   H u n a n ,   P. R .   C h i n a 2 Sc h o o l   o f   C o m p u t e r, Be i j i n g   U n i v e rs i t y o f   T e c h n o l o g y ,   Be i j i n g ,   1 0 0 1 2 4 ,   P.   R .   C h i n a 3 T h e   C e n t e r f o So f t - C o m p u t i n g a n d   C ry p t o l o g y ,   N U D T ,   C h a n g s h a ,   4 1 0 0 7 3 ,   H u n a n ,   P.   R .   C h i n a 4 St a t e   Ke y   L a b   o f   I n f o rm a t i o n   Se c u ri t y , C h i n e s e   A c a d e m y o f   Sc i e n c e s ,   Be i j i n g ,   P .   R .   C h i n a e - m a i l : l i u f a n b a o @ y a h o o . c o m . c n 1 Ab s t r a k Be rd a s a rk a n   p a d a   t i g a   p e n d e k a t a n   k o n s t r u k s i   a w a l   M AC ( M e s s a g e   Au t h e n t i c a t i o n   C o d e ) , Ka m i m e n g u s u l k a n   d a n   m e l a k u k a n   a n a l i s i s   t e rh a d a p   b e b e r a p a   v a r i a n   d a ri   N M AC .   Ka m i   m e n g u s u l k a n b e b e ra p a   p e m u l i h a n   s e r a n g a n   k u n c i   p a d a   v a ri a n   N M AC   t e rs e b u t ,   s e b a g a i   c o n t o h ,   k i t a   d a p a t   m e m u l i h k a n k u n c i d a l a m   y a n g   e k u i v a l e n   d a ri   N M AC   p a d a   s e j u m l a h O ( 2 n / 2 ) o p e ra s i M AC ,   p a d a s e t t i n g   k u n c i   y a n g b e rh u b u n g a n .   Ka m i   m e n g u s u l k a n   N M AC - E,   s u a t u   v a ri a n   N M AC   d e n g a n   s e c r e t   e n v e l o p e ,   u n t u k   m e n c a p a i p ro s e s   y a n g   l e b i h   e f i s i e n   d a n   t a n p a   k e h i l a n g a n p a d a   s i s i   s e k u ri t i ,   y a n g   h a n y a   m e m b u t u h k a n   s a t u p a n g g i l a n   p a d a   f u n g s i   h a s h   y a n g   m e n d a s a r i ,   b u k a n   p a d a   d u a   s p e rt i   y a n g   a d a   p a d a   H M AC . K a ta   k u n c i :   N M AC , k e y i n g   h a s h   f u n c t i o n ,   e q u i v a l e n t   k e y   r e c o v e r y , M AC f o rg e ry ,   b i rt h d a y   a t t a c k Ab s t r a c t Ba s e d   o n   t h e t h re e   e a rl i e r M AC   ( M e s s a g e   Au t h e n t i c a t i o n   C o d e )   c o n s t ru c t i o n   a p p r o a c h e s ,   w e p ro p o s e   a n d   a n a l y z e   s o m e v a ri a n t s   o f   N M AC .   W e   p r o p o s e     s o m e   k e y   re c o v e r y   a t t a c k s   t o     t h e s e     N M AC v a ri a n t s ,   f o r     e x a m p l e ,   w e   c a n     re c o v e   t h e     e q u i v a l e n t     i n n e   k e y     o f   N M AC     i n     a b o u t   O ( 2 n / 2 )   M AC o p e ra t i o n s ,   i n     a   re l a t e d   k e y     s e t t i n g .   W e     p ro p o s e     N M AC - E,   a     v a ri a n t   o f   N M AC w i t h     s e c re t     e n v e l o p ,     t o a c h i e v e     m o r e     p ro c e s s     e f f i c i e n c y     a n d     n o     l o s s     o f   s e c u r i t y ,   w h i c h   n e e d s   o n l y   o n e   c a l l   t o   t h e     u n d e rl y i n g h a s h     f u n c t i o n ,   i n s t e a d   o f   t w o   i n v o c a t i o n s   i n   H M AC . K e y w o r d s :   N M AC , k e y i n g   h a s h   f u n c t i o n ,   e q u i v a l e n t   k e y   re c o v e ry ,   M A C f o rg e ry ,   b i rt h d a y   a t t a c k 1 . In t r o d u c t io n HM A ( Ha s h - b a s e d   M e s s a g e A u t h e n ti c a t i o n   Co d e )   [ 2 ] [ 3 ],  a d e r i v a ti v e   o f NM A C ( Ne s te d   M e s s a g e   A u t h e n ti c a t i o n   C o d e ) i s   a p r a c ti c a l l y   a n d c o m m o n l y   u s e d w i d e l y s ta n d a r d i z e d   m e s s a g e   a u t h e n t i c a ti o n   c o d e   ( M A C )   c o n s tr u c ti o n HM A h a s   t wo   a d v a n ta g e s . F i r s t,    HM A c a n   m a k e    u s e   o f   c u r r e n   h a s h    f u n c ti o n s   th e    m o s   w i d e l y   u s e d   o n e s   a r e   b a s e d o n   M e r k l e - Da m g ˚ a r d   c o n s tr u c ti o n   [5 ] [1 4 ] wi th o u t m o d i f i c a ti o n   S e c o n d i i s   p r o v a b l e   s e c u r e u n d e r   t wo   a s s u m p ti o n s   th a t   th e     k e y e d   c o m p r e s s i o n     fu n c ti o n     o f   th e     u n d e r l y i n g     h a s h     f u n c ti o n a n d  t h e  k e y  d e r i v a t i o n  f u n c ti o n    i n  HM A C a r e  p s e u d o r a n d o m   f u n c ti o n s    ( P RF s )  [2 ]. A f te r   s o m e   p r e v a l e n i t e r a te d   h a s h   f u n c ti o n s   w e r e   b r o k e n   [1 0 ][2 3 ][2 4 ][2 5 ][2 7 ],  th e s e c u r i t y   o f   NM A   a n d     H M A   i n s ta n t i a t e d   wi th     th o s e     h a s h     f u n c ti o n s     w e r e   a n a l y z e d     [ 4 ][ 7 ][2 1 ][2 6 ],  w h i c h     e m p h a s i z e d     th a NM A   a n d     HM A   i n s ta n ti a te d   w i t h     b r o k e n     h a s h f u n c ti o n s   a r e   we a k . T h e r e     a r e     m a i n l y     th r e e     k i n d s     o a p p r o a c h e s     to     c o n s tr u c M A   a l g o r i th m s     b y k e y i n g   h a s h   f u n c ti o n s     i n   e a r l y   d a y s s e c r e t   p r e f i x s e c r e s u f f i x   a n d   s e c r e t   e n v e l o p   a p p r o a c h e s [2 0 ].  T h e   s e c r e t   p r e f i x a p p r o a c h   p r e p e n d s a   s e c r e k e y   K   t o   th e   m e s s a g e   M b e f o r e   h a s h i n g c o m p u ta ti o n wh i c h   i s   th e   b a s i c   d e s i g n   u n i o f   NM A C   a n d   H M A C.  T h e   s e c r e s u f f i x   a p p r o a c h a p p e n d s   a s e c r e k e y   K   to   th e   m e s s a g e M   b e f o r e h a s h i n g   c o m p u ta ti o n T h e   s e c r e e n v e l o p a p p r o a c h   i n v o l v i n g     t w o     k e y s p r e p e n d s     a   s e c r e   k e y   K 1 a n d a p p e n d s     a   s e c r e   k e y   K 2 to th e     m e s s a g e   M r e s p e c ti v e l y   b e f o r e   h a s h i n g     c o m p u ta t i o n B a s e d   o n   th e s e a p p r o a c h e s   a n d d i f f e r e n k e y   d i s tr i b u ti o n s we   p r o p o s e   s o m e   NM A C   v a r i a n ts   ( a l s o   a r e   HM A v a r i a n ts ) a n d a n a l y z e   t h e i r   s e c u r i t y b y   c h e c k i n g   wh e th e r   th e y   a r e   r e s i s ta n t o   k n o wn   a tt a c k s f o r   a   b e tte r c h o i c e . Evaluation Warning : The document was created with Spire.PDF for Python.
IS S N: 1 6 9 3 - 6 9 3 0 T E L KO M NIK A V o l . 1 1 ,  No . 2 , J u n e 2 0 1 3 : 3 8 1 3 9 2 3 8 2 T h i s     p a p e r   h o w e v e r   a n a l y z e s     th e     s e c u r i t y     o f   NM A   a n d     i ts     v a r i a n ts   b a s e d     o n th e   a s s u m p ti o n   t h a th e   u n d e r l y i n g     h a s h   f u n c ti o n s   a r e   s e c u r e   ( c o l l i s i o n   r e s i s ta n c e   CR ) , i n s te a d   o f   th a i n s ta n t i a t e d   wi th     b r o k e n     h a s h     f u n c ti o n s   W e   a l s o   p o i n   o u   th a th e a s s u m p ti o n   o f   CR  i s   a   s tr o n g e r     n o ti o n     th a n     th e     o r i g i n   a s s u m p ti o n   o f   th a t h e     u n d e r l y i n g c o m p r e s s i o n   f u n c ti o n     i s   a   P RF     [2 ].  W e   th e n     f i n d   th a NM A i s   n o s e c u r e   e n o u g h   to   s o m e e x t e n t,    f o r   e x a m p l e   i ts   i n n e r   k e y   i s   v u l n e r a b l e     t o   e q u i v a l e n t   k e y   r e c o v e r y   a tta c k w h i c h   n e e d s O ( 2 n /2 )  o n - l i n e   q u e r i e s  a n d   o f f - l i n e  c o m p u ta t i o n s i n   a  r e l a t e d   k e y  s e t ti n g . In th i s   p a p e r we p r o p o s e   s o m e   v a r i a n ts   o f   NM A C, a n d   a n a l y z e th e i r   s e c u r i t y b a s e d o n th e   a s s u m p ti o n   th a t h e u n d e r l y i n g   h a s h f u n c t i o n s   a r e s e c u r e W e   f i r s   p o i n t     o u t     th a N M A C 1 l i k e   th e     k e y e d     i n p u   v e r s i o n     H 2 - M A   p r o p o s e d     i n     [3 1 ],  i s   v u l n e r a b l e     to     e q u i v a l e n   k e y r e c o v e r y     a t ta c k   w i t h     c o m p l e x i t y     a b o u t 2 n/2 o n - l i n e   q u e r i e s T h e     s e c u r i t y     o f   NM A C 1 a n d     H 2 - M A C     a r e     to ta l l y     d e p e n d e n   o n     th e     c o l l i s i o n   r e s i s ta n c e   o f   th e     u n d e r l y i n g     h a s h     f u n c ti o n , i n s te a d   o f  th e   P RF   p r o p e r t y w h i c h  d i r e c tl y    v i o l a te s    th e  c l a i m e d  p r o v a b l e   s e c u r i t y . F u r th e r w e p o i n o u t th e   i n n e r   k e y o f   NM A i s v u l n e r a b l e   to e q u i v a l e n k e y   r e c o v e r y   a tta c k i n a r e l a te d   k e y s e tt i n g   T h e s e c u r i t y   s tr e n g t h o f   NM A C d e p e n d s   o n o n e   o f   i ts   t wo   k e y s e v e n   i f i t’ s b o th   k e y s a r e   i n d e p e n d e n t l y   a n d r a n d o m l y   g e n e r a te d . W e   a l s o   p r o p o s e   a   m o r e   s e c u r e v a r i a n t N M A C - E wh i c h  h a s  s o m e  a d v a n t a g e s  c o m p a r e d  to  NM A C,  a n d   HM A C - E . T h i s   p a p e r   i s   d i v i d e d   i n t o   s e v e n   s e c ti o n s S e c t i o n   2   r e c a l l s   th e r e l a te d   d e f i n i t i o n s a n d b a c k g r o u n d S e c ti o n   3   p r o p o s e s   a n d c r y p a n a l y z e s s o m e   N M A v a r i a n ts   i n c l u d i n g   NM A w i t h s e c r e p r e f i x   a p p r o a c h   S e c ti o n   4   p r o p o s e s   a n d   a n a l y z e s   th e s e c u r i t y   o f s o m e N M A v a r i a n ts wi th   s e c r e s u f f i x a p p r o a c h   W e p r e s e n a n d   a n a l y z e   a b e tte r   c h o i c e o f   NM A v a r i a n wi th   th e m o d i f i e d   v e r s i o n   o f   th e   s e c r e e n v e l o p   a p p r o a c h i n s e c ti o n   5 S e c t i o n   s i x p r e s e n ts   s o m e r e l a te d   wo r k W e  c o n c l u d e   th e  p a p e r   i n  t h e   l a s t s e c t i o n . 2 . P r e l im in a r ie s 2 .1  No t a t io n s L e h   b e   a   c o m p r e s s i o n   f u n c ti o n   m a p p i n g     { 0 ,   1 } n × { 0 1 } b →{ 0 ,   1 } n ,   a n d   l e t   H   b e   a c o n c r e te h a s h   f u n c ti o n m a p p i n g     { 0 1 } * →  { 0 ,   1 } n L e t IV   b e t h e i n i ti a l   c h a i n i n g   v a r i a b l e   o f H . L e k d e n o te   a s e c r e k e y   wi th   b   b i ts   a n d   K d e n o t e   a s e c r e k e y   wi th   n   b i ts r e s p e c ti v e l y   x | | y d e n o te s     t h e     c o n c a t e n a t i o n   o f   t w o   b i t     s tr i n g s     x   a n d     y .   | G |   d e n o te s     th e     n u m b e r o f   e l e m e n ts o f  th e  s e t G . p a d ( M )   d e n o te s   th e  p a d d i n g   b i ts  o f  M    i n   M e r k l e - Da m g ˚ a r d  s t y l e . 2 .2  NM A C NM A [ 2 [ 3 ],  p r o p o s e d   b y   B e l l a r e   e a l . i s   th e   b a s i s   o f   th e   m o s w i d e l y   u s e d c r y p to g r a p h i c a l g o r i t h m   H M A C   NM A   i s   b u i l t f r o m   i te r a te d   h a s h     f u n c t i o n H w h e r e   th e     I V o f  H  i s  r e p l a c e d    wi t h  a  s e c r e t n - b i t  k e y  K   , th e  NM A a l g o r i th m   i s  d e f i n e d  a s : N M A C ( Kout, Kin ) ( M )   H ( K out ,   H ( K in ,   M ) ) ( 1 ) W h e r e k e y s   K i n ,   K o u t { 0 1 } n i n   NM A a r e   to   r e p l a c e   th e     I V     o f h a s h   f u n c t i o n H     b e f o r e f u r th e r p r o c e s s . In  p r a c t i c e , b o t h  k e y s a r e r a n d o m l y  a n d i n d e p e n d e n tl y g e n e r a te d  [ 3 ]. 2 .3   S e c u r it y No t io n s  o f  M A C A u n i v e r s a l   f o r g e r y a t ta c k   r e s u l ts   i n   th e a b i l i t y   to f o r g e   M A Cs   f o r   a n y   m e s s a g e .   A s e l e c ti v e   f o r g e r y   a tt a c k r e s u l ts   i n a   M A C   ta g   o n   a   m e s s a g e   o f   th e a d v e r s a r y s   c h o i c e A n e x i s te n t i a l   f o r g e r y   m e r e l y   r e s u l ts   i n   s o m e   v a l i d   m e s s a g e / M A C   p a i r   n o a l r e a d y   k n o w n   t o   th e a d v e r s a r y . 3 . T h e  s e c u r it y  o f  S o m e   V a r ia n t s  w it h  S e c r e t  P r e f i x 3 .1    T h e  s e c u r it y  o f  NM A C 1 ( t h e  k e y e d I V  v e r s io n o f  H 2 - M A C ) W e  d e f i n e NM A C 1 t h r o u g h   k e y e d IV   a p p r o a c h  a s : ( N M A C 1 ) Kin ( M )   H ( H ( K in ,   M ) ) ( 2 ) W h e r e   th e IV   o f th e o u te r   h a s h i n g   o f NM A C 1 i s   n o r e p l a c e d   w i t h   a n y   s e c r e k e y . A Evaluation Warning : The document was created with Spire.PDF for Python.
T E L KO M NIK A IS S N: 1 6 9 3 - 6 9 3 0 O n  th e   S e c u r i ty  o f N M A C a n d  Its   V a r i a n ts   ( F a n b a o   L i u ) 3 8 3 k e y e d i n p u v e r s i o n o f   NM A C 1 wa s   a l s o p r o p o s e d   b y Y a s u d a   a s H 2 - M A [ 3 1 ],   wh i c h   i s s h o w n a s   ( 3 ) It  w a s   c l a i m e d   th a H 2 - M A g e ts   r i d   o f   th e   d i s a d v a n t a g e   o f   th e   s e c r e k e y   m a n a g e m e n t wi th o u l o s i n g th e   o r i g i n a l   a d v a n t a g e   o f   HM A C.  W a n g     a n n o u n c e d     a n   a t ta c k   t o   r e c o v e r     th e e q u i v a l e n   k e y   o f   H 2 - M A   i n s ta n t i a t e d   w i th     th e     b r o k e n     M D5   [2 5 ][2 7 ],  w i th   a b o u   2 9 7     o n - l i n e M A o p e r a t i o n s     [2 2 ].  Ho we v e r L i u   e a l p o i n te d     o u t     th a th e     a b s e n c e   o f   th e     o u te r     k e y   i s   a r e a l     t h r e a to     th e     s e c u r i ty     o f   H 2 - M A [1 2 ],  th e y     c o u l d     r e c o v e r     th e   e q u i v a l e n k e y   u s i n g b i r th d a y   p a r a d o x    wi th  c o m p l e x i t y    o f  a b o u t  O ( 2 n /2 )   M A C o p e r a ti o n s . H 2 - M A C K ( M )   H ( H ( K | | p a d | | M ) ) ( 3 ) O n - L in e  Bir t h d a y   A t t a c k  f o r  E x is t e n t ia l  F o r g e r y   A t t a c k . If   w e   a p p l y   o n - l i n e   b i r t h - d a y   a tt a c k   to   NM A C 1 o r a c l e a f te r     a b o u   2 n /2 q u e r i e s we   c a n g e a   c o l l i s i o n   p a i r   ( M M )   wi th   t h e   s a m e   l e n g th   wh i c h   s a ti s f i e s N M A C 1 ( M )   N M A C 1 ( M ) T h e n f o r   a r b i tr a r y   m e s s a g e x th e     e q u a t i o n N M A C 1 ( M | | p a d ( M ) | | x )   N M A C 1 ( M | | p a d ( M ) | | x ) a l wa y s h o l d s T h i s     m e a n s     th a we   c a n     g e n e r a t e     v e r i f i a b l e     f o r g e r y     o f   NM A C 1   w e   f i r s   q u e r y     t h e c o r r e s p o n d i n g   M A v a l u e   o f M | | p a d ( M ) | | x , a n d   w e   g e th e   v e r y   M A v a l u e   f o r M | | p a d ( M ) | | x , e v e n tu a l l y . T h i s     k i n d     o f   a tta c k   i s     a p p l i c a b l e     to     a l l     M A   a l g o r i th m s       i n s ta n ti a te d   w i t h     M e r k l e - Da m g ˚ a r d     h a s h f u n c ti o n s ,     a l s o   n o t i c e d     b y     Y a s u d a     [2 9 ].   He n c e t h e   r e s o f th e   p a p e r   w i l l n o t d i s c u s s  th e  s p e c i f i e d  a tta c k  a g a i n . E q u iv a le n t Ke y  Re c o v e r y A t t a c k  t o  NM A C 1 . W e   u s e   th e   s a m e   te c h n o l o g i e s   to   r e c o v e r th e   e q u i v a l e n k e y o f   NM A C 1 a s   i n   [1 2 o f   H 2 - M A C, w i th s l i g h m o d i f i c a ti o n s   to a c h i e v e   m o r e   e f f i c i e n c y W e g e n e r a te   th e g r o u p   o n e   G 1 u s i n g H ( x ) , i n s te a d   o f H ( H ( C ,   M i ) ) i n   [ 1 2 ],  wh i c h c a n   r e d u c e   a l e a s h a l f o f th e   s p a c e a n d   t i m e   W e a p p l y   t h e   g e n e r a l i z e d   b i r t h d a y a tt a c k   w i th   t w o   g r o u p s   [8 to   N M A C 1 a n d   t h e n   r e c o v e r   i ts e q u i v a l e n t k e y K e H ( K in ,   M j ) . He r e W e   f i r s d e f i n e th e   n o ta t i o n N 2 a s N 2 H ( x ) wh e r e x i s   a n   n - b i i n p u ( k e y ) . x c a n b e   v i e we d   a s x   ( C ,   M ) , wh e r e   C i s   a   c o n s ta n t a n d   M   i s t h e   i n p u t m e s s a g e G e n e r a l l y N 2 i s th e   n o n - k e y   v e r s i o n   o f   NM A C 1 W e   u s e   d i f f e r e n n - b i t     i n p u   m e s s a g e s x i s   ( 0     2 n −  1 ) to g e n e r a te     th e   c o r r e s p o n d i n g   N 2 v a l u e s   a n d     u s e     d i f f e r e n   1 - b l o c k     m e s s a g e s     M j s   ( 0   j     2 n 1 )     to     g e n e r a te     th e   c o r r e s p o n d i n g     NM A C 1 v a l u e s . T h e   o v e r a l l   s tr a te g y o f e q u i v a l e n k e y r e c o v e r y  a tt a c k to  NM A C 1 i s  s h o wn  a s  f o l l o w s . 1 . G e n e r a te   a g r o u p   o n e   G 1 wi th   r   =   2 n / 2 e l e m e n ts b y c o m p u ti n g   th e c o r r e s p o n d i n g   v a l u e s o f H ( x i ) f o r  r  d i f f e r e n t x i s wh i c h  c a n  b e r a n d o m l y  g e n e r a t e d . 2 . G e n e r a te   a g r o u p   t w o   G 2 wi th   s   =   2 n / 2 e l e m e n ts b y   q u e r y i n g   th e c o r r e s p o n d i n g   v a l u e s to NM A C 1 o r a c l e   wi th   th e   s e c r e k e y   K i n f o r   s   d i f f e r e n t   M j s w h e r e   M j s   a r e   a l s o   r a n d o m l y g e n e r a te d . 3 . T h e r e   w i l l b e   s o m e   p a i r s ( x i ,   M j ) th a s a t i s f i e s ( N M A C 1 ) Kin ( M j )   N 2 ( x i ) wi th   g o o d p r o b a b i l i t y [8 ]. 4 . Ho w e v e r we c a n n o t k n o th a wh e t h e r x j H ( K in ,   M j ) f u r th e r   h o l d s we   n e e d   to   k i c k o u th e u n s a ti s f i e d   p a i r s w h i c h w i l l   b e   d i s c u s s e d l a te r   i n k e y   s e l e c ti o n . A f te r   th a t w e   h a v e a   p a i r th a s a t i s f i e s x i H ( K in ,   M j )   a n d   ( N M A C 1 ) Kin ( M j )   = N ( x i ) .   S o   w e   f i n d   o u th e   e q u i v a l e n k e y   o f NM A C 1 o f K e H ( K i n ,   M j )   x i . 5 . L e   p a d 0 a n d     p a d 1 b e   th e     p a d d i n g     b i ts     o f   M j a n d M j | | p a d 0 | | x r e s p e c ti v e l y   f o r   a r b i tr a r y m e s s a g e   x W e g e n e r a te   th e i n te r m e d i a te   v a l u e   o f H ( K in ,   M j | | p a d 0 | | x ) b y   c o m p u ti n g y   = h ( K e , x | | p a d 1 ) , a n d c a l c u l a te   H ( y )  f u r th e r , a n d g e t N M A C 1 ( K i n ,   M j | | p a d 0 | | x ) , e v e n t u a l l y . Ke y   S e le c t io n T o   s e l e c a   p a i r   th a s a ti s f i e s x i H ( K in ,   M j ) we   a l w a y s   a s s u m e   th a e a c h   p a i r   we   h a v e i s   th e   r i g h p a i r T o   c o n f i r m   th e   a s s u m p ti o n w e   f i r s t r a n d o m l y   g e n e r a te a n   a r b i tr a r y   m e s s a g e   α; a n d   th e n   w e   g e n e r a te   th e   p a d d i n g   b i ts   p a d   o f   th e   M j | | p a d 0 | | α;  t h i r d we   c o m p u te   N 2 ( α )   =   h ( x i , α | | p a d )   a n d q u e r y   t h e c o r r e s p o n d i n g   r e s u l θ o f   M j | | p a d 0 | | α  t o   NM A C 1 o r a c l e we   n o te   t h a θ m a y  b e c o m p u te d  a s f o l l o ws . θ   N M A C 1 ( K in ,   M j | | p a d 0 | | α )   H ( h ( H ( K in ,   M j ) ,   α | | p a d ) ) ( 4 ) Evaluation Warning : The document was created with Spire.PDF for Python.
IS S N: 1 6 9 3 - 6 9 3 0 T E L KO M NIK A V o l . 1 1 ,  No . 2 , J u n e 2 0 1 3 : 3 8 1 3 9 2 3 8 4 F i n a l l y we  c h e c k  i f  N 2 ( α )  =  θ  h o l d s i f  s o , ( x i ,   M j ) i s  th e  r i g h t  p a i r . O th e r wi s e d i s c a r d  th a t p a i r . S u c c e s s  p r o b a b ilit y  a n d   Co m p le x it y . T h e   p r o b a b i l i t y P r ( | G 1   G 2 |   0 ) th a th e r e   a r e   n o d i s ti n c e l e m e n t i n   th e   i n te r s e c t i o n   o f th e   t w o   g r o u p s   i s d e n o te d   b y P   ( 2 n r s 0 ) L e s p   d e n o te   t h e   s u c c e s s   p r o b a b i l i t y   o f   th e   a b o v e a tta c k   ( a l e a s o n e   c o l l i s i o n   p a i r   e x i s ts ) th e n   w e   c a n   g e th e   v a l u e   o f   s p   b y c o m p u ti n g   s p =   1 P ( 2 n r s 0 ) 0 . 6 3 2   [1 2 ] .   T h e   e l e m e n ts   o f   g r o u p   G 1 c o m p u te d   b y N 2 n e e d   2 n /2 o f f - l i n e   N 2 c o m p u ta ti o n s   ( N 2 j u s c o n s i s ts   o f   o n e   h a s h   c o m p u ta ti o n ) T h e e l e m e n ts   o f g r o u p   G 2 c o m p u te d b y NM A C 1 n e e d   2 n/2 o n - l i n e   NM A C 1 q u e r i e s W e   c a n   s to r e   th e   v a l u e s   o f   b o t h   g r o u p s   u s i n g h a s h  ta b l e s . T h e n  th e  a b o v e  a l g o r i t h m  w i l l r e q u i r e  O ( 2 n /2 )  t i m e  a n d  s p a c e  to  c o m p l e te . W e   c a n   u s e   th e     r e c o v e r e d     e q u i v a l e n   k e y   K e to   l a u n c h     a n y     s e l e c ti v e   f o r g e r y   a tta c k   to NM A C 1 wi th o u     a d d i t i o n a l   o n - l i n e     q u e r y   w h i c h     c l a i m s     th a th e     s e c u r i t y     o f   NM A C 1 i s b r o k e n He n c e w e p o i n o u th a t th e   s e c u r i t y   o f NM A C 1 i s   s o l e l y d e p e n d e n o n th e   c o l l i s i o n r e s i s ta n c e  o f  th e  u n d e r l y i n g  h a s h  f u n c ti o n n o t t h e  s tr e n g th   o f  th e  u s e d  k e y . 3 .2 T h e  s e c u r it y o f  NM A C 2 W e  d e f i n e  NM A C 2 a s : ( N M A C 2 ) Kout ( M )   H ( K out ,   H ( M ) ) ( 5 ) W h e r e th e   i n n e r   k e y K i n i s   o m i tte d . T h i s   v a r i a n t N M A C 2 wa s   a l s o n o t e d   b y B e l l a r e   e a l i n   [3 ]. T h e o u te r   h a s h i n g   o n l y a c c e p ts   H ( M )   a s   l e g a l   i n p u t ,   wh i c h i s   a n   n - b i v a l u e T h o u g h   w e   c a n l e a r n   t h e   v a l u e   o f   H ( K out H ( M ) )   e a s i l y w e c a n n o t u s e   th a t i n f o r m a ti o n   t o l a u n c h   th e e x te n s i o n a tta c k to  NM A C 2 . O f f - L in e Bir t h d a y   A t t a c k  t o NM A C 2 W e f i r s a p p l y   a n   o f f - l i n e   b i r th d a y   a tt a c k   to   H ( M ) . A f te r   a b o u t 2 n /2 o f f - l i n e   c o m p u ta ti o n s , we   c a n   g e a   c o l l i s i o n p a i r   ( M ,M ) w h i c h   s a t i s f i e s H ( M )   H ( M )   a n d   N M A C 2 ( M )   N M A C 2 ( M ) , e v e n tu a l l y . T h e n , N M A C 2 ( M | | p a d ( M ) | | x )   N M A C 2 ( M | | p a d ( M ) | | x ) a l wa y s   h o l d s ,   f o r   a r b i tr a r y m e s s a g e   x It  m e a n s   th a we   c a n   g e n e r a te     v e r i f i a b l e   f o r g e r y   to   N M A C 2 w e   f i r s q u e r y   f o r   th e M A v a l u e  o f M | | p a d ( M ) | | x a n d   g e t t h e   M A C  v a l u e  f o r M | | p a d ( M ) | | x , e v e n tu a l l y . 3 .3 T h e  s e c u r it y o f  NM A C 3 W e  d e f i n e  NM A C 3 a s : ( N M A C 2 ) Kio ( M )   H ( K io ,   H ( K i o , M ) ) ( 6 ) W h e r e th e  i n n e r  a n d o u t e r  k e y s a r e b o th  s e t to   K i o . T h e   o n - l i n e   b i r th d a y   a tt a c k  f o r   e x i s te n ti a l   f o r g e r y a p p l i e d   to N M A C 1 i s   a l s o   a p p l i c a b l e   to   N M A C 3 wi th   a n y m o d i f i c a ti o n . F u r t h e r w e   p o i n o u th a th e   o f f - l i n e b i r th d a y   a tta c k   to   g e e x i s te n ti a l f o r g e r y  i s  a l s o A p p l i c a b l e  to NM A C 3 a f te r  s o m e  o p ti m i z a ti o n . W e  s h o w  th e  s tr a te g y   a s  f o l l o w s : 1 . Q u e r y   t h e   c o r r e s p o n d i n g   M A C v a l u e   o f M 0 t o   th e N M A C 3 o r a c l e w h i c h wi l l   a n s w e r H ( K io , H ( K io ,   M 0 ) ) . 2 . A s s u m e   th e   u n k n o wn H ( K io , M 0 )   b e   x 0 a n d   p a d 0 b e   t h e p a d d i n g   b i ts o f x 0 W e   a l r e a d y   k n o w th e   c o r r e s p o n d i n g   v a l u e   o f H ( K io ,   x 0 ) ( a n   e q u i v a l e n t   k e y o f th e   i n n e r   h a s h i n g ) w h i c h   i s NM A C 3 ( M 0 ) . 3 . B a s e d   o n   th e   k n o w n H ( K io ,   x 0 ) we   l a u n c h   a n   o f f - l i n e   b i r th d a y   a t ta c k   to   f i n d   a   c o l l i s i o n   p a i r ( M x ,   M x ) s a t i s f y i n g H ( K io ,   x 0 | | p a d 0 | | M x )   H ( K io ,   x 0 | | p a d 0 | | M x ) . 4 . F o r  a r b i tr a r y  m e s s a g e x we  c a n l a u n c h  a v e r i f i a b l e  f o r g e r y   a tta c k . Ho w e v e r s i n c e   t h e   v a l u e   o f H ( K io ,   M 0 ) i s   u n k n o wn h o w to   u s e   t h e   a b o v e   i n f o r m a ti o n   to l a u n c h a v e r i f i a b l e  f o r g e r y  a tt a c k  i s  s ti l l  a n  o p e n  p r o b l e m . 3 .4 T h e  s e c u r it y o f  NM A C A s p o i n te d   o u t b y   B e l l a r e   e a l .,  t h e   o n - l i n e   b i r th d a y   a t ta c k   f o r   e x i s te n ti a l   f o r g e r y   a tta c k i s   a l s o a p p l i c a b l e   to N M A [2 ],  h e r e   we   o m i th e   d e ta i l s   Ho we v e r w e f u r th e r n o ti c e th a w e c a n g e n e r a te   e x i s te n ti a l f o r g e r y   f o r   NM A C,  b y   a n   o f f - l i n e   b i r th d a y   a tta c k w h i c h   i s   s h o w n   a s   th e Evaluation Warning : The document was created with Spire.PDF for Python.
T E L KO M NIK A IS S N: 1 6 9 3 - 6 9 3 0 O n  th e   S e c u r i ty  o f N M A C a n d  Its   V a r i a n ts   ( F a n b a o   L i u ) 3 8 5 a tta c k  to  NM A C 2 , o n c e  th e  i n n e r  k e y  K i n i s   l e a k e d . Re l a te d K e y   A tta c k to  Re c o v e r th e   E q u i v a l e n t I n n e r   K e y . T o   r e c o v e r   th e   e q u i v a l e n i n n e r   k e y K e wi th   n - b i t w e h a v e   th e   f o l l o w i n g s e tt i n g   f o r o u r r e l a te d - k e y   a tta c k s o n   NM A C. T h e r e a r e   t w o   o r a c l e s   NM A C ( Ko u ,Ki n ) a n d NM A C ( K ou t Ki n ) . W e   s e t th e  r e l a t i o n   b e t we e n ( K o u t K i n ) a n d   ( K o ut , K i n )  a s  f o l l o ws : K out K ou t   a n d K in { C o n s ta n ts } W h e r e th e s e   two   o r a c l e s   s h a r e   th e   s a m e   o u te r   k e y a n d   th e   i n n e r   k e y   o f   NM A C ( K ou t Ki n ) c a n b e a n y  k n o w n  n - b i t Co n s ta n ts ,  s u c h  a s  th e I V   o f H . T h e  o v e r a l l  s tr a t e g y  o f th e   e q u i v a l e n t i n n e r  k e y r e c o v e r y  a tt a c k  to  NM A i s  s h o wn  a s  f o l l o w s . 1 . Q u e r y   NM A C ( Ko u t,   K i n ) o r a c l e f o r th e   c o r r e s p o n d i n g   v a l u e s o f   2 n /2 d i f f e r e n   M i s s to r e th e i r v a l u e s i n  g r o u p   o n e  G 1 . 2 . Q u e r y   N M A C ( Ko u t’,  Ki n ) o r a c l e   f o r th e   c o r r e s p o n d i n g   v a l u e s o f   2 n / 2 d i f f e r e n   M j s s to r e th e i r v a l u e s i n  g r o u p   t w o  G 2 . 3 . A   p a i r     ( M i M j )   s a ti s f i e s   N M A C ( Ko ut  ,Ki n ) ( M i )   =   N M A C ( Ko u t ,   Ki n ) ( M j )   ( th e     g e n e r a l i z e d   b i r t h d a y a tta c k   w i th     t wo     g r o u p s )   a n d     f u r th e r     s a ti s f i e s   H ( K i n ,   M i )   =   H ( K i n M j )   ( a n   i n n e r   c o l l i s i o n h a p p e n s ) . 4 . S i n c e H ( K in ,   M i )   H ( K in ,   M j ) a n d   w e   k n o w th e   v a l u e o f   K i n   a n d     M j h e n c e w e   c a n c a l c u l a te  t h e v e r y  v a l u e  o f K e H ( K in ,   M i )   H ( K in ,   M j ) . W e   c o n c l u d e   th a th e   e q u i v a l e n i n n e r   k e y   o f   NM A C   i s to ta l l y   d e p e n d e n t o n   th e   g e n e r a l i z e d b i r th d a y   a tta c k n o th e   s tr e n g th   o f   th e   u s e d   i n n e r   k e y i n   th e r e l a t e d   k e y s e tt i n g . H o w e v e r i f th e o u te r   k e y   K o u t o f   NM A i s   l e a k e d t h e n ,   i t n e e d s   a   g e n e r a l i z e d   b i r th d a y   a tt a c k   to   r e c o v e r   t h e e q u i v a l e n i n n e r  k e y   to b r e a k  th e e n t i r e  s y s te m , s h o wn a s  th e  a tt a c k  to  NM A C 1 . F r o m   th e s e   a tt a c k s w e   c l a i m   th a th e s e c u r i t y   o f NM A i s   d e p e n d e n o n   th e   s e c r e c y   o f o n e   o f   th e   k e y s e v e n   i f i t’ s b o th   k e y a r e   i n d e p e n d e n tl y   a n d r a n d o m l y   g e n e r a te d . A s   p o i n te d o u b y   th e     e d i to r s     o f   Cr y p to l o g y     e P r i n t   A r c h i v e   i n   o u r   p r e l i m i n a r y     v e r s i o n   o f   th i s   p a p e r th e e q u i v a l e n k e y   r e c o v e r y   a t ta c k   to   NM A i s   n o a p p l i c a b l e   t o   th e   p r a c t i c a l   H M A C,  s i n c e   th e HM A C  k e y s  a r e  d e r i v e d  f r o m  a  b a s e  k e y , a n d  t h e r e    e x i s ts  n o  r e l a te d   k e y . 4 T h e  s e c u r it y o f S o m e   V a r ia n t s w it h  S e c r e t S u f f i x In   th i s   s e c ti o n w e   d i s c u s s   th e s e c u r i t y   o f s o m e   NM A v a r i a n ts   NM A C - S i w i t h s e c r e t s u ff i x a p p r o a c h . W e    f i r s t     p r o v e     th a th e     s e c u r i t y     o f   o r i g i n a l     s e c r e   s u ff i x   i s   to ta l l y     d e p e n d e n t o n     th e   c o l l i s i o n   r e s i s ta n c e     ( CR )     o f   th e     u n d e r l y i n g     h a s h     f u n c ti o n   W e th e n   d i s c u s s th e s e c u r i t y   o f s o m e  v a r i a n ts  o f  NM A w i th  s e c r e t s u f f i x  a p p r o a c h . 4 .1 T h e  S e c u r it y o f  H  ( M | | K ) F o r     a n     n - b i   k e y   K w e   wi l l   p r o v e     a s   f o l l o w s th e     s e c u r i t y     o f   th e     s e c r e   s u ff i x   M - S   i s to ta l l y     d e p e n d e n   o n   t h e     c o l l i s i o n   r e s i s ta n c e     o f   th e     u n d e r l y i n g     h a s h     f u n c ti o n   i n s te a d     o f th e  s tr e n g th e n  o f  th e  k e y . T h e o r e m  1 T h e     s e c u r i t y     o f   H ( M | | K )   i s   to ta l l y   d e p e n d e n   o n   th e   c o l l i s i o n   r e s i s ta n c e     o f   t h e u n d e r l y i n g   h a s h  f u n c ti o n    H , i n s t e a d    o f  th e  s tr e n g th e n   o f  th e   u s e d  k e y . W e   p r o v e   T h e o r e m   1   b y   g i v i n g   th e   c o m p l e x i t y   o f   th e   wo r s c a s e   o f   th e   k e y   r e c o v e r y   a tt a c k a n d b e s c a s e   a tt a c k r e s p e c ti v e l y w h i c h a r e   a l l   b a s e d   o n   th e   a s s u m p ti o n   th a th e   m e s s a g e M   i s m u l ti p l e s   o f b y te s   T h e   w o r s c a s e   o f th e   k e y r e c o v e r y   a tta c k   i s   th a w e a s s u m e   th e c o l l i s i o n a tta c k   o f   h a s   n o   c o n tr o l   o v e r   t h e   c o n te n t   o f   th e   c o l l i s i o n   p a i r   ( M ,   M ) T h e   b e s c a s e   i s   th a w e a s s u m e   th e   c o l l i s i o n   a tta c k   h a s   f u l l c o n tr o l   o v e r s o m e b y t e s   o f th e   c o l l i s i o n   p a i r W e   n o ti c e   th a t th e c o m p l e x i t y   o f th e   c o l l i s i o n   a tt a c k   i s   2 n /2 h a s h   c o m p r e s s i o n s   b y   a n   o f f - l i n e   b i r th d a y   a tt a c k , f o r   a   h a s h   f u n c ti o n   w i th   n - b i o u t p u t T h e   a tta c k   i s   b a s e d   o n   th e   s l i c e - b y - s l i c e   k e y   r e c o v e r y o f tr a i l  k e y i n  s e c r e t e n v e l o p  a p p r o a c h , p r o p o s e d  b y   P r e n e e l  e a l [1 6 ]. Evaluation Warning : The document was created with Spire.PDF for Python.
IS S N: 1 6 9 3 - 6 9 3 0 T E L KO M NIK A V o l . 1 1 ,  No . 2 , J u n e 2 0 1 3 : 3 8 1 3 9 2 3 8 6 P r o o f T h e  B e s t Ca s e . S i n c e   th e     c o l l i s i o n   a tta c k   h a s     f u l l   c o n tr o l     o v e r   s o m e   b i ts     o f   th e   c o l l i s i o n   p a i r , to r e c o v e r     e a c h     b y t e     o f   th e     k e y     K o n l y     ( 2 8   1 )     c o l l i s i o n   p a i r s     m u s t     b e   g e n e r a te d     i n   th e wo r s c a s e S o   w e   n e e d   t o g e n e r a t e   ( 2 8   1 ) ( n / 1 6 )   c o l l i s i o n   p a i r s   to   r e c o v e r   th e   f i r s n /2   b i ts   o f K a n d   we   c a n   r e c o v e r   th e   l a s n /2   b i ts   o f   K th r o u g h b r u te   f o r c e a tta c k w h i c h   n e e d s   2 n /2 h a s h c o m p r e s s i o n s S o   th e to t a l   c o m p l e x i t y   o f th e   f u l l   k e y   r e c o v e r y   a tt a c k   i s   2 n /2 × ( 2 8   1 ) × ( n /1 6 )   + 2 n/2 <  2 n /2+ 8+ l og2 n /1 6 h a s h  c o m p r e s s i o n s . T h e   W o r s t Ca s e . S i n c e   t h e   c o l l i s i o n   a tta c k   h a s   n o   c o n tr o l   o v e r   a n y   b i o f   th e   c o l l i s i o n   p a i r to   r e c o v e r   th e j - th   ( 1 j n /8 )   c h a r a c te r   o t h e   k e y K , 2 8• j c o l l i s i o n   p a i r s   m u s t   b e   f i r s t g e n e r a te d .     S o   we   c a n r e c o v e r   t h e   f i r s n /4   b i ts   o f   th e   k e y   b y g e n e r a ti n g   ( 2 8 +   2 8• 2 +   •  •  •  +   2 n/4 ) c o l l i s i o n   p a i r s a n d   we c a n   r e c o v e r   th e   l a s 3 •n /4   b i ts th r o u g h   b r u te f o r c e   a tta c k w h i c h   n e e d s 2 3• n /4 h a s h c o m p r e s s i o n s . T h e   to ta l   c o m p l e x i t y   i s 2 n /2 ( 2 8 +   2 8• 2 +   •  •  •  +   2 n /4 )   +   2 3• n /4 2 n /2+ n /4+ 1 h a s h c o m p r e s s i o n s . T a b l e  1 .   Co m p l e x i t y  o f  K e y Re c o v e r y   A tt a c k to S e c r e S u f f i x A p p r o a c h A l l  i n  a l l   th e n , th e  c o m p l e x i t y   o f  th e  k e y  r e c o v e r y  t o  H ( M | | K )  r a n g e s  f r o m  2 n /2+ 8+ l og 2 n /`16 to   2 n /2+ n /4+ 1 h a s h   c o m p r e s s i o n s w h i c h   m e a n s   th a th e   s e c u r i t y   o f   M - S   i s   d e p e n d e n o n   th e   c o l l i s i o n r e s i s ta n c e     o f   th e     u n d e r l y i n g     h a s h     f u n c ti o n     i n s t e a d     o f th e     s tr e n g th   o f   th e     k e y He r e w e a s s u m e   th a t h e u n d e r l y i n g   h a s h f u n c ti o n   i s s e c u r e ,   i n   f a c t,  f o r   s o m e   a p p l i c a t i o n s   wi th   b r o k e n h a s h f u n c ti o n s ; th e s i tu a ti o n  i s to ta l l y  i n d a n g e r .  F o r  e x a m p l e A P O P   ( A u th e n ti c a t i o n P o s t O f f i c e P r o to c o l ) w h i c h   i s   i n s ta n ti a te d wi t h   b r o k e n   M D 5 , a p p l i e s   s e c r e t s u f f i x a p p r o a c h a n a tta c k e r c a n  r e c o v e r  th e p a s s w o r d   a s l o n g  a s  3 5 2   b i ts   i n p r a c ti c a l  ti m e [1 1 ]. W e   l i s   th e     c o m p l e x i t y     o f   k e y   r e c o v e r y     a t ta c k   to     H ( M | | K )   i n   T a b l e     1 wi th     d i f f e r e n t l i m i ta ti o n s   o n     th e     i n p u t m e s s a g e     M   . W o r d   m e a n s   t h a t M   m u s b e   m u l ti p l e s   o f 3 2 - b i wo r d s . Ho w e v e r a s   s h o wn   i n T a b l e   1 ,   w e   p o i n t   o u t h a t b o t h   th e b e s a n d   w o r s c a s e s   a r e e x h a u s ti v e k e y s e a r c h i f  th e  m e s s a g e M  i s m u l ti p l e s  o f n  b i ts . 4 .2 T h e  s e c u r it y o f  NM A C - S 1 W e  d e f i n e NM A C - S 1 a s : ( N M A C - S 1 ) Kin ( M )   H ( H ( M | | K in ) ) ( 7 ) W h e r e th e   o u te r   k e y   K o u t i s   o m i tte d   T h e   o f f - l i n e   b i r th d a y   a tt a c k   c a n   b e   a p p l i e d   t o   NM A C - S 1 . F u l l   K e y   R e c o v e r y A tta c k   to   NM A C - S 1 W e   c a n   d i r e c tl y   a p p l y   th e   f u l l   k e y   r e c o v e r y   a tt a c k   to H ( M | | K i n ) , s i n c e   th e   o u te r   h a s h i n g   d o e s   n o h i d e   t h e   i n n e r   c o l l i s i o n A f te r   th a t,   w e   c a n   f u l l y r e c o v e r   th e   i n n e r   k e y   o f   NM A C - S 1 a n d th e n   c a n c o n s tr u c a n y   v e r i f i a b l e   f o r g e r y . T h e c o m p l e x i t y  o f th e  k e y  r e c o v e r y  a t ta c k  to  NM A C - S 1 c a n b e  s h o wn T a b l e  1 . 4 .3 T h e s e c u r it y o f  NM A C - S 2 W e  d e f i n e  NM A C - S 2 a s : ( N M A C - S 2 ) Kout ( M )   H ( H ( M ) | | K out ) ( 8 ) W h e r e th e   i n n e r   k e y   K i n i s   o m i tte d . T h e   o f f - l i n e   b i r th d a y   a tt a c k c a n   b e a p p l i e d   to   N M A C - S 2 . Ho w e v e r i s e e m s th a n o k e y   r e c o v e r y   a tt a c k   to   NM A C - S 2 c a n   b e l a u n c h e d   a s NM A C - S 1 . Evaluation Warning : The document was created with Spire.PDF for Python.
T E L KO M NIK A IS S N: 1 6 9 3 - 6 9 3 0 O n  th e   S e c u r i ty  o f N M A C a n d  Its   V a r i a n ts   ( F a n b a o   L i u ) 3 8 7 H ( M )   i s   n   b i ts   l o n g a n d   K ou t i s   a l s o   n   b i ts w h i c h   m e a n s   th a t h e   c o n c a te n a ti o n   o f   b o th   a r e i n s i d e   o n e   b l o c k s o   th e   s l i c e - b y - s l i c e   k e y   r e c o v e r y   s tr a te g y   c a n b e   a p p l i e d   E x h a u s ti v e s e a r c h m u s b e p e r f o r m e d   to   b r e a k   th e o u t e r   k e y K o u t wh o s e c o m p l e x i t y   i s 2 n M A C c o m p u ta ti o n s . 4 .4 T h e  s e c u r it y o f  NM A C - S 3 W e  d e f i n e  NM A C - S 3 a s : ( N M A C - S 3 ) Kio ( M )   H ( H ( M | | K io ) | | K io ) ( 9 ) W h e r e th e   i n n e r   a n d   o u te r   k e y s a r e   e q u a l . T h e   o f f - l i n e   b i r t h d a y   a tt a c k   c a n   b e a p p l i e d   t o NM A C - S 3 . Ke y     Re c o v e r y   A t t a c k t o  NM A C - S 3 W e c a n   d i r e c tl y   a p p l y   t h e f u l l k e y   r e c o v e r y   a tt a c k   to   H ( M | | K i o ) s i n c e   th e o u te r   h a s h i n g d o e s n o h i d e   th e   i n n e r   c o l l i s i o n A f te r   th a t,  we   c a n   f u l l y   r e c o v e r   th e   i n n e r   k e y   K i o w h i c h   i s   a l s o th e   o u t e r   k e y o f   NM A C - S 3 F i n a l l y w e c a n   c o n s tr u c a n y   v e r i f i a b l e   f o r g e r y T h e   c o m p l e x i t y   o f th e  k e y  r e c o v e r y   a tt a c k  to  NM A C - S 3 wh i c h   i s  a n a l o g o u s  to  NM A C - S 1 i s  a l s o  s h o wn  i n T a b l e   1 . 4 .5 T h e  s e c u r it y o f  NM A C - S W e  d e f i n e  NM A C - S   a s : ( N M A C - S ) ( Kin,   Kout ) ( M )   H ( H ( M | | K in ) | | K out ) W h e r e th e   i n n e r   a n d   o u te r   k e y s   a r e   d i f f e r e n t.  T h e   o ff - l i n e   b i r th d a y   a tta c k   c a n   b e   a p p l i e d   to NM A C - S . In n e r  Ke y  Re c o v e r y A t t a c k  t o  NM A C - S . W e   c a n   d i r e c tl y   a p p l y   t h e f u l l   k e y   r e c o v e r y   a tt a c k to   H ( M | | K i n ) ,   s i n c e th e   o u te r   h a s h i n g d o e s n o h i d e th e   a p p e a r a n c e o f th e   i n n e r c o l l i s i o n . A f te r   th a t we c a n   f u l l y r e c o v e r   th e   i n n e r k e y K i n o f   NM A C - S   Ho we v e r wi th K i n we   c a n t d i r e c t l y   c o n s tr u c t a n y   v e r i f i a b l e   f o r g e r y , th a n k s to th e   o u te r   h a s h i n g   w i t h   t h e   u n k n o w n   K o u t . T h e   o u t e r   k e y K o u t c a n b e r e c o v e r e d   l i k e K i n , wh i c h   i s   a l s o a n a l y z e d   i n NM A C - S 2 It  s e e m s   th a we   h a v e   to   a p p l y   a d d i ti o n a l   o f f - l i n e   b i r th d a y a tta c k  to  H ( M ) , f o r  a m e a n i n g f u l  e x i s t e n t i a l f o r g e r y . 4 .6 Co u n t e r p a r t  f o r t h e  K e y  Re c o v e r y A t t a c k t o  N M A C - S   V a r ia n t s T o a v o i d   t h e   f u l l k e y r e c o v e r y   a tt a c k to   NM A C - S   V a r i a n ts w e   m o d i f y th e   i n n e r h a s h i n g f o r m   H ( M | | K i n ) . W e a l wa y s   a s s u m e   th a t n | b , w h i c h   m e a n s   th a t b   i s th e   m u l ti p l e s o f   n L e p a d n ( 1 | | 0 * )  b e th e p a d d i n g   b i ts o f  M , p a d n i s  d e f i n e d   a s n | ( | M |   | p a d n | ) ( 1 0 ) W e  r e - d e f i n e  th e   i n n e r h a s h i n g  f o r m a s : H ( M | | p a d n | | K in ) W h e r e th e   i n n e r   k e y   K i n r e s i d e s   a s   a   wh o l e p a r o n th e i n p u b l o c k W e   h a v e   th e   f o l l o wi n g th e o r e m  f o r th e  k e y  r e c o v e r y   a tt a c k . T h e o r e m  2 S l i c e - b y - s l i c e   k e y   r e c o v e r y   s tr a te g y c a n n o t b e   a p p l i e d   t o H ( M | | p a d n | | K in ) f o r l a u n c h i n g   k e y r e c o v e r y  a tt a c k . P r o o f   S i n c e n | b a n d n | ( | M |   | p a d n | ) , a n d | K i n |   n ,   th e n   n | ( | M | | p a d n | | K in | ) h e n c e n o s l i c e c a n   b e m a d e  to  th e  k e y   K i n . Ho w e v e r , th e   NM A C - S   V a r i a n ts   a f te r   m o d i f i c a ti o n   a r e   s ti l l   v u l n e r a b l e   to   o f f - l i n e   b i r th d a y   a tta c k f o r  e x i s te n ti a l  f o r g e r y  a tt a c k . Evaluation Warning : The document was created with Spire.PDF for Python.
IS S N: 1 6 9 3 - 6 9 3 0 T E L KO M NIK A V o l . 1 1 ,  No . 2 , J u n e 2 0 1 3 : 3 8 1 3 9 2 3 8 8 5 . T h e  s e c u r it y o f  a n   N M A V a r i a n t w it h  S e c r e t E n v e lo p In   l a s t w o   s e c ti o n s w e   d i s c u s s   th e s e c u r i t y   o f NM A v a r i a n ts   wi th   s e c r e p r e f i x   a n d s e c r e s u ff i x r e s p e c ti v e l y   In   th i s   s e c ti o n we   d i s c u s s   th e s e c u r i t y   o f a n   N M A v a r i a n t NM A C - E wi th  s e c r e e n v e l o p   a p p r o a c h . 5 .1       NM A C - E  w it h   M o d if i e d  S e c r e t   E n v e lo p W e     p r o p o s e     NM A C - E     wi th     m o d i f i e d     v e r s i o n     o f   th e     s e c r e   e n v e l o p a p p r o a c h , wh i c h     h a s   th e   a d v a n t a g e   o f   b o th   e q u i v a l e n k e y   r e c o v e r y   r e s i s t a n c e     a n d   s l i c e - b y - s l i c e   k e y r e c o v e r y   r e s i s ta n c e   T h e     m o d i f i c a ti o n     i s   s tr a i g h tf o r wa r d we   p a d     th e     i n p u   m e s s a g e   M     wi th p a d n wh i c h   c a n   b e   s o m e   f i x e d   c o n s ta n ts b e f o r e   a p p e n d i n g     t h e   o u te r   k e y   K   W e   d e f i n e NM A C - E  a s : N M A C - E ( K ) ( K ,   M | | p a d n | | K ) W h e r e K  i s  a r a n d o m l y  g e n e r a te d   n - b i t k e y . M   | | p a d n i s m u l ti p l e s  o f n   b i ts . 5 .2 T h e  s e c u r it y o f  NM A C - E O ff - L i n e  B i r th d a y   A tt a c k  Re s i s ta n c e . NM A C - E   i s   r e s i s ta n t o   o f f - l i n e   b i r t h d a y   a tt a c k   f o r   e x i s te n ti a l   f o r g e r y , th a n k s   t o th e s e c r e IV th e   k e y K . W i th o u a n y   k n o w l e d g e   a b o u t h e   IV th e   o f f - l i n e   b i r th d a y   a tta c k   to   f i n d a  c o l l i s i o n  p a i r  c a n b e   l a u n c h e d . E q u iv a le n t Ke y  Re c o v e r y A t t a c k  Re s is t a n c e . NM A C - E   i s   r e s i s ta n t   to   e q u i v a l e n k e y   r e c o v e r y   a tta c k , th a n k s   to th e   a p p e n d e d   k e y K . E v e n   i f th e   a tt a c k e r c a n   f i n d   o u t h e r e s u l o f NM A C - E ( K ) e a s i l y n o e x te n s i o n   a tta c k c a n   b e l a u n c h e d ;  h e n c e , n o  e q u i v a l e n t  k e y  r e c o v e r y  a tta c k  h a p p e n s . S lic e - b y - S li c e  K e y R e c o v e r y A t t a c k  R e s i s t a n c e . NM A C - E  i s a l s o  r e s i s ta n to s l i c e - b y - s l i c e  k e y  r e c o v e r y   a tta c k  a s  p r o v e n  i n T h e o r e m  2 . Div id e - a n d - Co n q u e r  E x h a u s t iv e - S e a r c h Ke y  Re c o v e r y . T h e   d i v i d e - a n d - c o n q u e r   e x h a u s ti v e - s e a r c h   k e y   r e c o v e r y   [ 1 6 ] c a n n o t b e a p p l i e d     t o NM A C - E   s i n c e   o u r   s c h e m e   u s e   o n e   k e y ,   a n d     a   b r u te     f o r c e   a tt a c k   s h o u l d     b e   p e r f o r m e d     to f i n d  o u t   th e   k e y . T h e  a tt a c k s  p e r f o r m e d  to  NM A C a l s o  s h o w t h a i i s  n o t  n e c e s s a r y  to  b i n d  t wo k e y s  to  s tr e n g th e n  t h e   M A C s c h e m e . O n - L in e  Bir t h d a y   A t t a c k . T h e   o n - l i n e   b i r th d a y   a tta c k   i s a p p l i c a b l e   to   NM A C - E , a f te r   a b o u t 2 n /2 o n - l i n e   M A C q u e r i e s , a  c o l l i s i o n  p a i r  m a y   b e  f o u n d   th a t N M A C - E ( M )   N M A C - E ( M ) . W e   l i s th e s e c u r i t y   p r o p e r ti e s   o f a l l   NM A v a r i a n ts   d i s c u s s e d   i n   t h i s   p a p e r i n T a b l e   2 O F B A R s t a n d s   f o r   o ff - l i n e   b i r th d a y   a tta c k   r e s i s ta n c e O NB A s ta n d s   f o r   o n - l i n e   b i r th d a y   a tt a c k r e s i s ta n c e   E K R A m e a n s     e q u i v a l e n t     k e y   r e c o v e r y     a tta c k   r e s i s ta n c e ,     S S K RA m e a n s s l i c e - b y - s l i c e     k e y     r e c o v e r y     a tt a c k   r e s i s ta n c e     DCE S K R s ta n d s       f o r     d i v i d e - a n d - c o n q u e r e x h a u s ti v e - s e a r c h  k e y  r e c o v e r y  r e s i s ta n c e . f m e a n s th e r e  o n l y o n e  k e y  e x i s ts . T a b l e  2 .   S e c u r i t y   Co m p a r i s o n b e t we e n  NM A V a r i a n ts M A C O F B A R O N B A R E K R A R S S K R A R D C E S K R R N M A C 1 Y e s N o N o Y e s f N M A C 2 Y e s N o N o Y e s f N M A C 3 Y e s N o N o Y e s N o N M A C Y e s N o N o Y e s N o N M A C - S 1 N o N o Y e s N o f N M A C - S 2 N o N o Y e s N o f N M A C - S 3 N o N o Y e s N o N o N M A C - S N o N o Y e s N o N o N M A C - E Y e s N o Y e s Y e s f Evaluation Warning : The document was created with Spire.PDF for Python.
T E L KO M NIK A IS S N: 1 6 9 3 - 6 9 3 0 O n  th e   S e c u r i ty  o f N M A C a n d  Its   V a r i a n ts   ( F a n b a o   L i u ) 3 8 9 P e r f o r m a n c e   A n a l y s is  o f  NM A C - E . NM A C - E   u s e s   o n l y   o n e   c a l l   o f   th e   u n d e r l y i n g h a s h   f u n c ti o n b u i n tr o d u c e s   a m e s s a g e p a d d i n g   p r o c e s s c o m p a r e d   to NM A C.     H o w e v e r s i n c e   th e   p a d d i n g     h a p p e n s     a t   th e   ta i l   o f   th e m e s s a g e   M   a n d   th e   f i l l i n g   b i ts   o f   p a d   a r e   s o m e   c o n s ta n ts w h i c h     a i m s     to     a l i g n     th e     i n p u t b l o c k   M   to     b e   m u l ti p l e s     o f   b   b i ts   t h e     c o s   o f   p a d d i n g     i s   n e g l i g i b l e e s p e c i a l l y   f o r   l o n g m e s s a g e M o r e o v e r NM A C - E   p r o c e s s e s o n l y   o n e   m o r e   b l o c k , c o m p a r e d   to th e   i n n e r   h a s h i n g o f  NM A C.  He n c e ,  th e  NM A C - E  i s  e f f i c i e n th a n  NM A C. 5 .3       S e c u r it y  P r o o f  f o r  N M A C - E W e   f i r s r e c a l l th e T h e o r e m   3 .1   o f   [1 ];  i s a y s   th a H * i s   a   p f - V I - P RF i f   th e   u n d e r l y i n g c o m p r e s s i o n   f u n c ti o n   h   i s   a n   F I - P RF w e   l i s th e   d e t a i l   o f   th e   T h e o r e m   a s   f o l l o w w h e r e   w e c h a n g e  th e  n o t i o n s  to  s u i ta b l e   th i s   p a p e r . T h e o r e m 3 .1  o f [ 1 ] . L e h   b e   a f u n c ti o n   f a m i l y wi th   Do m ( h )   =   { 0 ,   1 } b , Ra n g e ( h )   = { 0 ,   1 } n ,   a n d   k e y   l e n g th   n . S u p p o s e   h   i s   ( t,  q 1 ε ) - s e c u r e   a n d   l e l   1 T h e n   h * i s ( t,  q l ε ) - s e c u r e a g a i n s p r e f i x - f r e e d i s ti n g u i s h e r s w h e r e t −  c q . ( n   b ) . ( T ime ( h )   lo g   q ) ε   q He r e c   i s   a   s p e c i f i c s m a l l   c o n s ta n w h o s e v a l u e   c a n   b e   d e te r m i n e d   f r o m   th e   p r o o f F o r   th e d e ta i l   o f th i s  p r o o f , p l e a s e  r e f e r  [1 ]. In [ 1 ],  a   c o n s tr u c ti o n   c a l l e d     F acsc w a s p r o p o s e d   t o   c o n s tr u c t V I - P RF     f a m i l y δ A F * , b a s e d     o n a n   F I - P RF . δ A F    i s  c o n s tr u c te d  a s  f o l l o w s . G i v e n    a  f a m i l y    F    wi th k e y  l e n g t h n  +  δ , h a v i n g  k e y ( K d )   wh e r e K { 0 ,   1 } n a n d   d { 0 ,   1 } δ ,   le t δ A F K, d ( x )   F ( x | | d ) f o r   a l l b - b i t x F i n a l l y , δ A F * i s   a   V I - P RF wh i c h   i s p r o v i d e d   b y Co r o l l a r y   4 .2 o f  [1 ]. Co r o lla r y 4 .2  o f [ 1 ] . L e h   b e   a   f u n c ti o n     f a m i l y   wi th   Do m ( h )   =   { 0 ,   1 } b Ra n g e ( h )   = { 0 1 } n ,     a n d     k e y   l e n g t h n . S u p p o s e  h   i s ( t, q , 1 ε ) - s e c u r e  a n d   l e t l 1 . T h e n δ - A h *   i s ( t, q l , ε ) - s e c u r e wh e r e t −  c q . ( n   b   ( lo g δ ) . T ime ( h )   ( n   b ) . lo g   q ) ϵ l q ϵ   b lq 2 α . Ho w e v e r we   c a n t   g e t   th e   c o n c l u s i o n t h a NM A C - E   i s   a   V I - P RF     d i r e c tl y   b a s e d   o n   th e   b o t h c o n c l u s i o n s   o f   [1 ],  s i n c e   a n o th e r     p a r   p a d d i n g     i s   i n s e r te d     b e t w e e n     th e   m e s s a g e   M     a n d   th e δ  k e y  K i 2  i n  NM A C - E . W e   n o ti c e   th a NM A C - E ( K )   = H ( K M   | | p a d n   | | K ) wh e r e M   i s f i r s t p a d d e d   w i th s o m e f i x e d   b i ts , a n d   th e n tr a n s f e r r e d   to   b e   p r o c e s s e d   b y H. W e   d i v i d e   th e   p r o o f   o f th a t ; NM A C - E   i s   a P RF   i f th e u n d e r l y i n g   h i s   a   d u a l   P RF ,   i n to t w o   p a r ts   F i r s t w e p r o v e   th a t   H ( K ,   M   | | p a d n )   i s   a p f - V I - P RF S e c o n d we   p r o v e   th a N M A C - E   i s   a P RF   u n d e r   th e s o l e   a s s u m p ti o n   t h a t th e u n d e r l y i n g  c o m p r e s s i o n f u n c ti o n   h i s  a  P RF . T h e o r e m  3 . If   th e c o m p r e s s i o n   f u n c ti o n   h o f   th e u n d e r l y i n g   h a s h f u n c ti o n   i s a   P RF th e n H * ( K ,   M | | p a d n ) , wh e r e  p a d n i s  th e  p a d d i n g   b i ts  o f M   wi th o u l e n g th i n f o r m a ti o n i s  a  p f - V I - P RF . P r o o f   F r o m   th e T h e o r e m   3 .1 o f   [1 ],  w e   k n o w   th a H * ( K M )   i s   a   p f - P RF   i f th e   u n d e r l y i n g c o m p r e s s i o n   f u n c ti o n   h   i s   a   P RF   S i n c e   t h e   c o n te n o f   p a d n ( t h e   n u m b e r   o f   0 s   to   b e   f i l l e d )   i s to ta l l y   d e te r m i n e d b y   th e   l e n g th   o f   M wh i c h   m e a n s   i i s   o b v i o u s l y   k n o w n H e n c e M | | p a d n i s   n o t p r e f i x - fr e e w e   c a n d i r e c tl y   g e t th e   c o n c l u s i o n   th a t H * ( K ,   M | | p a d n ) i s   a   p f - V I - P RF i f   th e u n d e r l y i n g  h i s  a   P RF . B a s e d   o n   th e   T h e o r e m   3   a n d   th e   c o r o l l a r y   4 .2   o f   [1 ] w e   c a n g e t th e   c o n c l u s i o n   th a t NM A C - E   i s   a P RF   u n d e r   th e s o l e   a s s u m p ti o n   th a t h e u n d e r l y i n g   c o m p r e s s i o n fu n c ti o n   h i s   a P RF . Evaluation Warning : The document was created with Spire.PDF for Python.
IS S N: 1 6 9 3 - 6 9 3 0 T E L KO M NIK A V o l . 1 1 ,  No . 2 , J u n e 2 0 1 3 : 3 8 1 3 9 2 3 9 0 T h e o r e m  4 . If   th e   c o m p r e s s i o n     f u n c ti o n     h   o f   th e   u n d e r l y i n g     h a s h   f u n c ti o n       i s   a   P RF th e n     N M A C - E ( K ) c o n s tr u c ti o n H * ( K ,   M | | p a d n | | K   )   wh e r e   p a d n i s   th e   p a d d i n g   b i ts   o f   M   w i t h o u l e n g t h   i n f o r m a ti o n , i s  a  V I - P RF . P r o o f .  T h i s th e o r e m  c a n b e c o n d u c te d   d i r e c t l y   b a s e d o n  th e T h e o r e m  3 a n d  t h e   Co r o l l a r y 4 .2  o f  [1 ]. 5 .4       HM A C - E T o   u ti l i z e   th e   a d v a n t a g e   o f   NM A C - E   a n d   t o   e m p l o y   th e   u n d e r l y i n g     h a s h   f u n c ti o n s   a s   a b l a c k  b o x  l i k e  HM A C,  we  a l s o  p r o p o s e   a  “ HM A C”    v e r s i o n   o f  th e  N M A C - E ,   n a m e d   HM A C - E . W e  d e f i n e  HM A C - E   a s : HM A C - E   HM A C - E ( K ) ( K | | M   | | p a d n | | K ) W h e r e K  i s  a n  n - b i t k e y . HM A C - E     i s   a   P RF     u n d e r     th e     s o l e   a s s u m p ti o n   th a t h e     u n d e r l y i n g h a s h     f u n c ti o n     i s a   d u a l   P RF   th e     p r o o f   i s   s i m i l a r   to   th e     s e c u r i t y     p r o o f   o f   NM A C - E ,     f o r   th e     l a c k   o f   s p a c e we o m i th e   d e ta i l s . HM A C - E   c a l l s   th e u n d e r l y i n g   h a s h f u n c ti o n   o n l y o n c e wh e r e a s   HM A C r e q u i r e s   t w o i n v o c a t i o n s   o f H, a n d   HM A C - E   i n v o l v e s n o k e y   d e r i v a ti o n HM A C - E   c a n   a c h i e v e m o r e p r o c e s s  e f f i c i e n c y , c o m p a r e d  to HM A C, a n d wi th o u l o s s o f  s e c u r i t y . 6 . R e la t e d  W o r k T h e   E NM A C a l g o r i t h m   [ 1 5 i n c r e a s e s   e f f i c i e n c y   o v e r   HM A u s i n g   a   s e c r e t - p r e f i x a p p r o a c h f o r   s h o r m e s s a g e s T h e   M D P   c o n s tr u c t i o n   [9 ]   o p e r a te s   a s   a   s e c r e t - p r e f i x   M A C a l g o r i th m   f o r m e s s a g e s   o a n y   l e n g th   b y   a p p l y i n g   a   p e r m u ta ti o n .   T h e   S a n d wi c h   c o n s tr u c ti o n [3 0 i s   s i m i l a r   to   o u r p r o p o s e d   NM A C - E , b u i t s u f f e r s l o w   e f f i c i e n c y   o v e r s h o r m e s s a g e s c o m p a r e d   to o u r   s c h e m e . T h e   L - L a n e   H M A c o n s t r u c ti o n   [ 2 9 wa s p r o p o s e d   to a v o i d th e g e n e r a l b i r th d a y   a tta c k   to   HM A C T h e   B NM A C a l g o r i th m   [ 2 8 a i m   to   i m p r o v e   e f f i c i e n c y   o v e r HM A C u s i n g   s i n g l e   k e y   a p p r o a c h   T h e     H 2 - M A   c o n s tr u c ti o n   [ 3 1 ],  o m i tti n g     th e     o u te r     h a s h o f   HM A C,  te n d s     to     i m p r o v e     e f f i c i e n c y   o v e r   HM A   w i t h     p r o v a b l e     s e c u r e   b u   r e c e n t r e s e a r c h     s h o w s   th a i i s   v u l n e r a b l e     to   e q u i v a l e n   k e y   r e c o v e r y     a t ta c k   [1 2 b a s e d     o n   th e a s s u m p ti o n  t h a th e  u n d e r l y i n g    h a s h  f u n c ti o n    i s   ( w e a k )  c o l l i s i o n  r e s i s t a n c e . 7 . Co n c lu s io n a n d  F u t u r e W o r k B a s e d   o n th e   th r e e   e a r l i e r a p p r o a c h e s   to c o n s tr u c M A C a l g o r i th m s   a n d   d i f f e r e n k e y d i s tr i b u ti o n s we   p r o p o s e   a   s e r i e s   o f   NM A v a r i a n ts w e   a l s o   a n a l y z e   th o s e   v a r i a n ts   i n   o r d e r   t o f i n d   a b e tte r   a n d m o r e   s e c u r e   o n e .   W e   f i n d   a   v a r i a n o f   NM A C, n a m e d   NM A C - E w i th   t h e m o d i f i e d   v e r s i o n   o f   th e   s e c r e e n v e l o p   a p p r o a c h a n d   c a n wi th s ta n d   a l l   k n o w n   a tt a c k s   to   M A C a l g o r i th m s . W e   n o ti c e   th a a l l   k i n d s   o f   NM A v a r i a n ts b a s e d   o n   M e r k l e - Da m g ˚ a r d   c o n s tr u c t   h a s h f u n c ti o n s a r e v u l n e r a b l e   to th e   o n - l i n e   b i r th d a y   a t ta c k   f o r   v e r i f i a b l e   f o r g e r y .   In   f a c t,  a   p a i r ( M i , M j ) w h i c h h a s   th e   s a m e   M A C v a l u e   a f te r   a b o u t 2 n /2 o n - l i n e   q u e r i e s i s a c c e p ta b l e to   s o m e e x te n t.  It  i s n o a f o r g e r y   i n th i s   s i t u a t i o n s i n c e   we   h a v e a l r e a d y q u e r i e d   th e   M A C o r a c l e   f o r th e i r   c o r r e s p o n d i n g M A C   r e s u l ts . T h e   o n l y   p r o b l e m   i s   th a t,   th e r e   a r e   s o   m a n y   c o l l i s i o n   p a i r s a f te r  th e  c o n c a t e n a ti o n  o f  a r b i tr a r y  m e s s a g e  x , o n c e  a   c o l l i s i o n  p a i r  i s  f o u n d . Re f e r e n c e s [ 1 ] Be l l a r e   M ,   C a n e t t i   R ,   Kra w c z y k   H .   P s e u d o ra n d o m   f u n c t i o n s   re v i s i t e d :   t h e c a s c a d e   c o n s t r u c t i o n a n d i t s   c o n c re t e   s e c u r i t y .   F o u n d a t i o n s   o f   C o m p u t e Sc i e n c e .   An n u a l I EEE  Sy m p o s i u m o n   0 .   1 9 9 6 ;   5 1 4 . [ 2 ] Be l l a r e     M .   N e w Pro o f s   f o r N M AC   a n d   H M A C :     Se c u ri t y w i t h o u t   C o l l i s i o n - R e s i s t a n c e .   I n :   D w o rk   C ( e d . ) Ad v a n c e s i n   C ry p t o l o g y - C R Y P T O   2 0 0 6 ,   L e c t u re N o t e s   i n   C o m p u t e r S c i e n c e ,   v o l .     4 1 1 7 . H e i d e l b e rg : Sp ri n g e Be r l i n . 2 0 0 6 : 6 0 2 6 1 9 . [ 3 ] Be l l a r e     M .   C a n e t t i   R ,   Kr a w c z y k   H .   Ke y i n g   H a s h   F u n c t i o n s   f o M e s s a g e   Au t h e n t i c a t i o n .   I n :   Ko b l i t z   N Evaluation Warning : The document was created with Spire.PDF for Python.