Identification.DVI


Mathematical Problems of Computer Science 33, 127{134, 2010.

Data E ncr yption, Authentication and Key

P r edistr ibution Schemes for Wir eless

Sensor N etwor ks

A r a A le xa n ia n , H a ko b A s la n ya n a n d A r m e n S o g h o ya n

Yerevan State University

Abstract

This paper investigates some security aspects of wireless sensor networks. Par-
ticularly symmetric encryption, authentication and key predistribution schemes are
proposed. Encryption and authentication schemes are based on a secret key which
is a table of strong generators of a permutation group (as per Sims algorithm). The
ciphertext of a plaintext of size N is a single permutation over n = 2N + 1 elements.
Encryption/Decryption processes are simple and easy to perform for a wireless node
with limited abilities.

Key predistribution scheme deals with all the node and network limitations and
requirements existing in wireless sensor networks and gives a secure key predistribution
scheme under the assumption that nodes are not physically captured for t0 time after
being deployed, where t0 is time necessary for invoking the key establishment phase of
proposed scheme, which is in practice should be some seconds.

Refer ences

[1 ] Y e e W e i L a w, Je r o e n D o u m e n a n d P ie t e r H a r t e l, \ S u r ve y a n d b e n c h m a r k o f b lo c k
c ip h e r s fo r wir e le s s s e n s o r n e t wo r ks " , ACM Transactions on Sensor Networks TOSN,
vo l. 2 , n u m b e r 1 , p p . 6 5 -9 3 , 2 0 0 6 .

[2 ] R . R ive s t , \ Th e R C5 E n c r yp t io n A lg o r it h m " , 1 9 9 4 L e u ve n W o r ks h o p o n Fa s t S o ft wa r e
E n c r yp t io n , S p r in g e r -V e r la g , p p . 8 6 -9 6 , 1 9 9 5 .

[3 ] R . R ive s t , M. R o b s h a w, R . S id n e y a n d Y . Y in , \ Th e R C6 T M B lo c k Cip h e r . S p e c i¯ c a t io n
ve r s io n 1 .1 " , 1 9 9 8 .

[4 ] J. D a e m e n a n d V . R ijm e n , A E S P r o p o s a l: R ijn d a e l, 1 9 9 9 .

[5 ] M. Ma t s u i, \ N e w B lo c k E n c r yp t io n A lg o r it h m MIS TY " , F ast Software E ncryption, 4th
International W orkshop, F SE 97, vo l. 1 2 6 7 o f L N CS .,S p r in g e r -V e r la g , p p . 5 4 -6 8 , 1 9 9 7 .

[6 ] 3 r d Ge n e r a t io n P a r t n e r s h ip P r o je c t , \ S p e c i¯ c a t io n o f t h e 3 GP P Co n ¯ d e n t ia lit y a n d
In t e g r it y A lg o r it h m s D o c u m e n t 2 " , K A S U MI S p e c i¯ c a t io n . E TS I/ S A GE , S p e c i¯ c a t io n
V e r s io n : 1 .0 , 1 9 9 9 .

[7 ] K . A o ki, T. Ic h ika wa , M. Ma t s u i, S . Mo r ia i, J. N a ka jim a a n d T. To kit a , \ S p e c i¯ c a t io n
o f Ca m e llia . A 1 2 8 -B it B lo c k Cip h e r " , N ip p o n Te le g r a p h a n d Te le p h o n e Co r p o r a t io n
a n d Mit s u b is h i E le c t r ic Co r p o r a t io n , S p e c i¯ c a t io n V e r s io n 2 .0 , 2 0 0 1 .

1 2 7



1 2 8 Data Encryption, Authentication and Key Predistribution Schemes for Wireless Sensor Networks

[8 ] A . P e r r ig , R . S z e wc z yk , V . W e n a n d e t a l., \ S P IN S : s e c u r it y p r o t o c o ls fo r s e n s o r
n e t wo r ks " , J ournal of W ireless Networks, vo l. 8 , n u m b e r 2 , p p . 5 2 1 -5 3 4 , 2 0 0 2 .

[9 ] C. K a r lo f ,N . S a s t r y a n d D . W a g n e r , \ Tin yS e c : a lin k la ye r s e c u r it y a r c h it e c t u r e fo r
wir e le s s s e n s o r n e t wo r ks " , P roceedings of the 2nd International Conference & E mbedded
Networked Sensor Systems, B a lt im o r e , U S A , 2 0 0 4 .

[1 0 ] J.N . A l-K a r a ki a n d A .E . K a m a l, \ R o u t in g t e c h n iqu e s in wir e le s s s e n s o r n e t wo r ks : A
s u r ve y" , IE E E W ireless Communications., vo l. 1 1 , n u m b e r 6 , p p . 6 -2 8 , 2 0 0 4 .

[1 1 ] W . D i± e a n d M. E . H e llm a n , \ N e w D ir e c t io n s in Cr yp t o g r a p h y" , IE E E Transactions
on Information Theory, vo l. IT-2 2 , n u m b e r 6 , p p . 6 4 4 -6 5 4 , 1 9 7 6 ..

[1 2 ] R . L . R ive s t , A . S h a m ir a n d L . M. A d le m a n , \ A m e t h o d fo r o b t a in in g d ig it a l s ig n a t u r e s
a n d p u b lic -ke y c r yp t o s ys t e m s " , Communications of the ACM , vo l. 2 1 , n u m b e r 2 , p a g e s
1 2 0 -1 2 6 , 1 9 7 8 .

[1 3 ] L . E s c h e n a u e r a n d V . D . Glig o r , \ A ke y m a n a g e m e n t s c h e m e fo r d is t r ib u t e d s e n s o r
n e t wo r ks " , P roceedings of the 9th ACM Conference on Computer and Communication
Security, p a g e s 4 1 -4 7 , 2 0 0 2 .

[1 4 ] H . Ch a n , A . P e r r ig a n d D . S o n g , \ R a n d o m ke y p r e d is t r ib u t io n s c h e m e s fo r s e n s o r
n e t wo r ks " , P roceedings of the 2003 IE E E Symposium on Security and P rivacy, p p . 1 9 7 -
2 1 3 , 2 0 0 3 .

[1 5 ] S . A . Ca m t e p e a n d B . Y e n e r , Co m b in a t o r ia l d e s ig n o f ke y d is t r ib u t io n m e c h a n is m s
fo r wir e le s s s e n s o r n e t wo r ks , IE E E /ACM Transactions on Networking (TON), vo l. 1 5 ,
n u m b e r 2 , p p . 3 4 6 -3 5 8 , 2 0 0 7 .

[1 6 ] Y . X ia o , V . K r is h n a R a yi, B o S u n , X . D u , Fe i H u a n d M. Ga llo wa y, \ A s u r ve y o f ke y
m a n a g e m e n t s c h e m e s in wir e le s s s e n s o r n e t wo r ks " , Computer Communications, vo l. 3 0 ,
n u m b e r 1 1 -1 2 , p p . 2 3 1 4 -2 3 4 1 , 2 0 0 7 .

[1 7 ] H . Ch a n , A . P e r r ig , a n d D . S o n g , \ K e y D is t r ib u t io n Te c h n iqu e s fo r S e n s o r N e t wo r ks ',
W ireless Sensor Networks, T. Zn a t i e t a l., e d s , 2 0 0 4 .

[1 8 ] A . A le xa n ya n , A lg e b r a ( Gr o u p s , R in g s , Fie ld s ) , Y e r e va n U n ive r s it y P u b lis h e r , In A r -
m e n ia n , 2 0 0 6 ,.

[1 9 ] M. B r o wn , D . Ch e u n g , D . H a n ke r s o n , J. L . H e r n a n d e z , M. K ir ku p a n d A . Me n e z e s ,
\ P GP in c o n s t r a in e d wir e le s s d e vic e s " , 9th USE NIX Security Symposium, 2 0 0 0 .

[2 0 ] D . W . Ca r m a n , P .S . K r u u s a n d B . J. Ma t t ., \ Co n s t r a in t s a n d a p p r o a c h e s fo r d is t r ib u t e d
s e n s o r n e t wo r ks s e c u r it y" , N A I L a b , S e p t e m b e r , n u m b e r 0 0 -0 1 0 , 2 0 0 0 .

[2 1 ] S e r e g e L a n g , A lg e b r a , S p r in g e r S c ie n c e +B u s in e s s Me d ia , In c ., 2 0 0 2 .

[2 2 ] B .L V a n d e r V a r d e n , A lg e b r a , S p r in g e r V e r la g , 1 9 6 8 .



A. Alexanian, H. Aslanyan and A. Soghoyan 1 2 9

²Ýɳñ ë»Ýëáñ³ÛÇÝ ó³Ýó»ñÇ ïíÛ³ÉÝ»ñÇ Í³Íϳ·ñÙ³Ý, ÇÝùÝáõÃÛ³Ý
ѳëï³ïÙ³Ý ¨ µ³Ý³ÉÇÝ»ñÇ µ³ßËÙ³Ý ë˻ٳݻñ ѳٳñ

². ²É»ùë³ÝÛ³Ý, Ð. ²ëɳÝÛ³Ý ¨ ². êáÕáÛ³Ý

²Ù÷á÷áõÙ

²ß˳ï³ÝùáõÙ ¹Çï³ñÏí³Í »Ý ³Ýɳñ ë»Ýëáñ³ÛÇÝ ó³Ýó»ñÇ ³å³ÑáíáõÃÛ³ÝÁ
í»ñ³µ»ñáÕ áñáß ËݹÇñÝ»ñ: سëݳíáñ³å»ë ³é³ç³ñÏíáõÙ »Ý ïíÛ³ÉÝ»ñÇ ëÇÙ»ïñÇÏ
ͳÍϳ·ñÙ³Ý, ÇÝùÝáõÃÛ³Ý Ñ³ëï³ïÙ³Ý ¨ µ³Ý³ÉÇÝ»ñÇ µ³Å³ÝÙ³Ý ë˻ٳݻñ:
̳Íϳ·ñÙ³Ý ¨ ÇÝùÝáõÃÛ³Ý Ñ³ëï³ïÙ³Ý ë˻ٳݻñÇ µ³Ý³ÉÇ ¿ ѳݹÇë³ÝáõÙ
ï»Õ³¹ñáõÃÛáõÝÝ»ñÇ ËÙµÇ áõÅ»Õ ÍÝÇãÝ»ñÇ µ³½ÙáõÃÛ³Ý ³ÕÛáõë³ÏÁ (ÇÝãå»ë êÇÙëÇ
³É·áñÇÃÙáõÙ): Øáõïù³ÛÇÝ ïíÛ³ÉÝ»ñÇ N ã³÷³ÝÇ ( N µ³Ûà å³ñáõݳÏáÕ) µÉáÏÁ
ͳÍϳ·ñ»Éáõó ëï³óíáõÙ ¿ n = 2 N + 1 ï³ññ»ñÇó ϳ½Ùí³Í Ù»Ï ï»Õ³¹ñáõÃÛáõÝ:
̳Íϳ·ñÙ³Ý ¨ í»ñͳÝÙ³Ý ·áñÍáÕáõÃÛáõÝÝ»ñÁ å³ñ½ »Ý ¨ ϳñáÕ »Ý ϳï³ñí»É
ë³Ñٳݳ÷³Ï Ñݳñ³íáñáõÃÛáõÝÝ»ñ áõÝ»óáÕ ³Ýɳñ ë»Ýëáñ³ÛÇÝ Ñ³Ý·áõÛóÇ ÏáÕÙÇó:
´³Ý³ÉÇÝ»ñÇ µ³Å³ÝÙ³Ý ëË»Ù³Ý Ñ³ßíÇ ¿ ³éÝáõÙ ³Ýɳñ ë»Ýëáñ³ÛÇÝ ó³Ýó»ñáõÙ ³éϳ
µáÉáñ ë³Ñٳݳ÷³ÏáõÙÝ»ñÝ áõ å³Ñ³ÝçÝ»ñÁ ¨ ï³ÉÇë ¿ µ³Ý³ÉÇÝ»ñ µ³Å³ÝÙ³Ý ³å³Ñáí
ë˻ٳ ³Ý»Éáí ÙdzÛÝ Ù»Ï »Ýó¹ñáõÃÛáõÝ, ³ÛÝ ¿‘ ѳݷáõÛóÝ»ñÁ ï»Õ³¹ñí»Éáõó Ñ»ïá t0
ųٳݳÏÇ ÁÝóóùáõÙ ã»Ý »ÝóñÏíáõÙ ýǽÇÏ³Ï³Ý Ñ³ñÓ³ÏÙ³Ý: ²Ûëï»Õ t0 -Ý ó³ÝóÇ
ѳݷáõÛóÝ»ñÇ ÙÇç¨ Ñ³Õáñ¹³ÏóÙ³Ý µ³Ý³ÉÇÝ»ñÇ Ñ³ëï³ïÙ³Ý Ñ³Ù³ñ ³ÝÑñ³Å»ßï
ųٳݳÏÝ ¿, áñÁ Çñ³Ï³ÝáõÙ ï¨áõÙ ¿ í³ÛñÏÛ³ÝÝ»ñ: