Journal of the Korea Academia-Industrial cooperation Society Vol. 15, No. 11 pp. 6815-6820, 2014 http://dx.doi.org/10.5762/kais.2014.15.11.6815 ISSN 1975-4701 / eissn 2288-4688 RFID system 을위한 AES 암호프로세서설계에관한연구 강영진 1* 1 원광대학교전자공학과 Study of the Cryptographic Processor Design appropriate for the RFID system Young-Jin Kang 1* 1 Dept. of Electronic Engineering, Wonkwang University 요약유비쿼터스활성화에따른 RFID/USN 환경조성은매우빠르게증가되고있다. 그러나 RFID/USN 환경에적합한보안환경은보안위협증가속도에따르지못하는것이현실정이다. 그러므로본논문은 RFID/USN에적합한 MSNR 을제안하였다. 제안된 MSNR 은기존 AES에비하여 1.3배의처리율증가를보였으며, 전체적인시스템효율면에서 2배의성능향상을보임을확인하였다. 그러므로 MSNR 은 RFID/USN 등과같은환경적자원제약조건을극복하기에적합한암호알고리즘으로사료된다. Abstract The creation of a RFID/USN environment has increased rapidly due to the activation of ubiquitous security environment suitable for RFID/USN environment but has failed to comply with the speed of security threats. Therefore, this thesis presents MSNR suitable for RFID/USN. The MSNR presented showed an increase in the processing rate of 1.3 times compared to the existing AES and showed 2 fold improvement in performance in terms of the overall system efficiency. Therefore, MSNR is considered to be a password algorithm suitable to overcome the conditions of environmental resource conditions, such as RFID/USN. Key Words : MSNR, RFID, USN, Cryptographic, Processor 1. 서론현재 RFID/USN 의사용범위가증대됨에따라노드망에대한보안의중요성이더욱강조되고있다. 그러므로다양한보안기법들이 RFID/USN 에적용되고있지만다양한공격에대한방어기법으로아직은부족한상태이다 [1]. 이에본논문은 RFID/USN에사용되는암호알고리즘의성능향상을위하여 2000년도에표준화된 AES 알고리즘을더욱발전시켜처리속도증가및노드망보안성을보다우수하게유지하고자하였다. 제안된방식은 AES에대하여처리율증가및망관리편리성을위한 MSNR(Management of Speed and Network for Rijndael) 기법이며 AES 및다른대칭형암호시스템들과비교하여성능분석을수행하였다. 제안된 MSNR 암호알고리즘은기존대칭형암호알고리즘에비하여처리속도가빠르며비트및바이트연산을혼용함과동시에한주기를 N등분하는 PRN (Pseudo-Random Number) 을사용하여망관리가우수하도록하였다. 그러므로 MSNR 은복잡해져가는노드망을가지는 RFID/USN 환경에매우필요한암호시스템중의하나가될것으로사료된다. 본논문은원광대학교 2013학년도교내연구과제로수행되었음. * Corresponding Author : Young-Jin Kang(Wonkwang Univ.) Tel: +82-63-850-6743 email: yjkang@wonkwang.ac.kr Received September 30, 2014 Revised November 5, 2014 Accepted November 6, 2014 6815
한국산학기술학회논문지제 15 권제 11 호, 2014 2. N- 등분 PRN 을포함하는 MSNR 암호알고리즘 RFID/USN 에보안을강화하기위하여다양한기법들이제시되고있으나제한적인환경이라는특징때문에일반적인암호알고리즘을 RFID/USN 환경에적용하기에는무리가따른다. 그러므로본논문에서는처리시간, 소비전력, 크기등을고려한구현상의문제해결과노드증가로인한보안자원의효율성등을위하여 MSNR 기법을제안하였으며이를 AES인 Rijndael 암호알고리즘에적용하였다. 제안된 MSNR 기법은기존 AES와유사하게기본연산자로배타적논리합을사용하며처리수행단위는바이트를사용하였다. 바이트연산은처리속도를매우높게수행할수있다는장점과더불어역추적이어렵기때문에비도증가에도매우우수한특성을가진다. 또한기존 Feistel 과 SPN 구조를혼용하기때문에암 / 복호화의동시수행이가능하여 Rijndael[2,3] 또는 Serpent[4] 암호알고리즘에서발생되는효율저하가발생하지않는다. 이러한특징은 AES에대한충분한전제조건을만족함과동시에 AES 다음버전에대한내용을제시할수있다. 이러한특징으로인하여 MSNR 기법이가미된암호알고리즘은실시간처리및비도그리고구현상의문제점, 노드증가로인한관리문제등을해결할수있다. 2.1 MSNR 암호알고리즘 MSNR 암호알고리즘에사용되는입 / 출력 / 키블록크기는 128 비트이며평문, 암호문그리고키의크기도 1:1:1이된다. MSNR 암호알고리즘은 AES 암호알고리즘과마찬가지로다음과같은네가지기능블록을포함하며각단계를거치는동안바이트단위의변환으로구성된라운드를이용하여암 / 복호화를수행한다. ⅰ) Inv/SubByte : 조건상태 (CS : Condition State) 기능을가진 S-box 를이용하여바이트치환수행기능 ⅱ) Inv/ShiftDiagonal : CS에대한행방향이동기능 ⅲ) Inv/MixColumn : CS의각열에해당하는바이트들의혼합기능 ⅳ) AddRoundKey : CS와라운드키에대한 1:1 덧셈 기능평문 / 암호문 128 비트의입력은 CS 블록으로초기저장된다. CS는 MSNR 암호알고리즘을형성하기위한비선형특성을가진상태를의미한다. CS는식 (1) 및 Fig. 1과같이외부에서주어지는파라미터를가지고현재상태를결정하며결정된현재상태는불확실한미래상태를형성하는기준값이된다. (1) CS는입력으로사용되는여러가지파라미터를이용하여키값을생성하는데필요한자료를만드는동시에암 / 복호화하는과정중에치환변환을제어하는기능을수행한다. Plain/ CipherText Key Value PRN SEED CS Boundary Calculator To KeyExpander To Transformation [Fig. 1] Characteristic of a condition state 식 (1) 에서 mod 8은입력데이터들에대한모듈러연산을의미하는것으로서입력값들에대한포맷을바이트로변환하기위한과정이다. 또한 PRN[5] SEED는식 (2) 와같이입력데이터와키값을이용하여생성한다. (2) 식 (2) 에의하여생성된 SEED는식 (3) 과같은 PRN 을통하여 2 바이트의출력값을산출하게된다. (3) 산출된 2 바이트중 odd 정보는 MSNR 의내부바이트치환제어에사용되어지며, even 정보는키확장제어에사용된다. odd와 even 정보는예측불가함수를생성하는기능을가짐으로서내부치환정보가외부로유출될가능성이적으며, 입력데이터와키정보만을가지고생성된것이 6816
RFID system 을위한 AES 암호프로세서설계에관한연구 기때문에별도의프로세싱이필요없다. 식 (3) 은이동통신망에서사용되는 PRN과동일한방정식으로서 2바이트를하나의방정식으로간주하여출력값을산출하게된다. CS는초기라운드키와배타적논리합을수행한후 n 번의라운드를수행하게된다. 모든라운드가실행되면암 / 복호화를마치게된다. 이러한 MSNR 암호알고리즘에대한전체적인흐름은 Fig. 2와같다. MSNR 암호알고리즘의가장큰특징은 Fig. 2에서보는바와같이암 / 복호화가동시에수행된다는점이다. 제어신호에의하여암 / 복호모드가결정되며처리되어지는연산은순 / 역으로동작한다. 각라운드마다 Inv/SubByte, Inv/ShiftDiagonal, Inv/MixColumn, Inv/AddRoundKey 에대한데이터값들은 CS & PRN에의하여별개로동작하게된다. 그러므로라운드수에따라서비도가결정된다. Plain/CipherText Key 기존 AES들은데이터와키의길이를 128, 192, 256 비트들로가변시키며, 변화하는길이에따라최적화된라운드수를결정하게된다. 그러므로기존 AES인경우데이터의블록길이에따라라운드수가결정된다. 이러한결과로인하여, 데이터심볼크기를파악하게될경우, 라운드수를파악할수있으며라운드수와키및데이터와의 DC 및 LC에의하여크래킹이가능해진다. 그러나 MSNR 인경우고정된블록및키크기를가지고있어도내부적으로라운드수에따라데이터내용이변화되므로라운드수를데이터심볼크기만을가지고파악할수없다는장점이있다. (4) Permutation Permutation 2.1.1 Inv/SubByte 변환 Inv/SubByte 변환은바이트단위로구성된 S-box 를 CS & PRN 이용하여 CS에의한외부상태값들을각각의레지스터에저장하고, 저장된값들은각각독립적으로존재하는바 AddRoundKey Inv/SubByte MOIN Key Generator 이트들을비선형적으로변형하여비선형변형된바이트집합을생성하게된다. Inv/SubByte 변환에사용되는 S-box 는역변환이가능하며유한체 GF( 2 8 ) 에서곱에대한역이존재하며식 (5) 와같이정의되는 affine 변환 Inv/ShiftDiagonal 을 GF( 2 8 ) 에적용할수있는비선형변환이가능한함 Inv/MixColumn AddRoundKey Round Key 0 Round Key 1... Round Key n- 1 수들의집합이다. no Last Round? (5) yes InvPermu Cipher/PlainText [Fig. 2] The algorithm of the MSNR 이러한네가지변환을 MOIN(Minimum Operation for Inverse/Non-inverse) 이라고정의하면식 (4) 와같다. 여기에서 ab는 CS & PRN의출력정보중내부정보를변환시켜주는부분인 a 부분의비트블록을의미하며 0 i 7일때 는각각독립적으로분리되어동작하는바이트들의 i 번째해당비트이고 는특정 ac 바이트블록의 i 번째비트를의미한다. mod8은내부연산시바이트단위로수행되지만실제적인연산은비트단위이다. 그러므로비트와바이트에대한분리표 6817
한국산학기술학회논문지제 15 권제 11 호, 2014 현을위하여모듈러연산을유한체 GF( 8 2 ) 상에나타냄으로서 MSNR 암호알고리즘은 1 바이트연산이기준이된다는것을나타낸다. 이변환을행렬형태로표현하면식 (6) 과같다. 여기에서 ab' 는변환된새로운상태배열을의미하며 ~ 는 S-box에대한값이며 PN 0 는랜덤수를, α는 PRN에대한 SEED값을의미한다. 2.1.2 Inv/ShiftDiagonal 변환 Inv/ShiftDiagonal 변환은데이터상태배열의행및열단위를기준으로대각선방향으로동시에이루어진다. 이러한변환은식 (7) 과같은방정식으로표현할수있다. + (6) (7) 식 (7) 에서각상태배열에대하여행과열이대각을중심으로변환됨을알수있다. 이러한대각변환은역치환및계산수행이용이할뿐만아니라랜덤성을보장하게된다. 그러므로 Inv/ShiftDiagonal 변환은 Rijndael 또는 Serpent 암호알고리즘과같은계산속도의 1/2배의특성을가지며비도는 2배증가를가지게된다. 식 (7) 과같이대각방향으로이동되는 Inv/ShiftDiagonal 변환은행번호가 0인첫행첫열은 3번 0번 shift 되며, 마지막행및열은 0번 3번이동하게된다. 이와같은대각변환은같은행에있는바이트들이행의번호가낮은위치로이동하는결과를가져오며행번호가낮은위치의바이트는상위행의위치로이동하게된다. Inv/ShiftDiagonal 변환은대각변환을이용하여변환되기때문에역변환도동일한과정으로변환하게된다. 2.1.3 Inv/MixColumn 변환 Inv/MixColumn 변환은고정된다항식인 a( x) 를곱하여새로운변환배열을생성한다. 이때전체변환식은 곱셈연산이기본이된다. 즉변환된함수 s'( x) 는변환전함수인 s( x) 에대하여 a( x) 를곱한형태를가지게된다. 이러한 s'( x)=a( x) s( x) 곱셈형태는식 (8) 과같이표현된다. s' 0 s' 1 = s' 2 s' 3 02 01 03 03 s 0 01 03 03 02 s 1 (8) 03 03 02 01 s 2 03 02 01 03 s 3 식 (8) 의결과값은상태배열에서네개의바이트열들로식 (9) 와같이변환된다. 식 (9) 에서동일한계수값에대하여연속적인계산을요구하는항이존재하게된다. 이러한동일연산은배타적논리합을이용하면소거되므로식 (9) 를다시정리하면식 (10) 과같이변형될수있다. s' 0 =({02} s 0 ) ({01} s 1 ) ({03} s 2 ) ({03} s 3 ) s' 1 =({01} s 0 ) ({03} s 1 ) ({03} s 2 ) ({02} s 3 ) s' 2 =({03} s 0 ) ({03} s 1 ) ({02} s 2 ) ({01} s 3 ) s' 3 =({03} s 0 ) ({02} s 1 ) ({01} s 2 ) ({03} s 3 ) (9) (10) 식 (10) 을이용하여 Inv/MixColumn 변환을수행하면 Fig. 3과같이상태배열의일부만이변환된다는것을알수있다. Inv/ShiftDiagonal 변환과비슷하게대각변환을수행하고있지만, Inv/MixColumn 변환은 에해당하는대각변환만을수행하게된다. 즉, MSNR 암호알고리즘의대각변환을수행함에있어식 (11) 과같이대각변환이구별되어진다. S 0,1 S 0,0 S 0,2 S 0,3 S 1,1 S 1,0 S 1,2 S 1,3 S 2,1 S 2,0 S 2,2 S 2,3 S 3,1 S 3,0 S 3,2 S 3,3 Inv/MixColumn S' S' 0,1 0,0 S' 1,0 S' 1,3 S' 3,1 S' 2,2 S' 2,3 S' 3,2 [Fig. 3] Inv/MixColumn transformation 6818
RFID system 을위한 AES 암호프로세서설계에관한연구 (11) 식 (11) 과같이하나의상태배열에대하여대각변환을 x 방향과 - x 방향으로수행함으로서전체대각을변환시킬수있다. 이러한대각변환은기존암호알고리즘과같이곱셈연산을수행해야하는번거로움을줄일수있다. 제안된 MSNR 암호알고리즘은식 (10) 과같이다른값들에대해서만곱셈계산을수행함으로서수행속도의단축및자리올림현상이발생하지않으며동시에반대방향으로대각변환을수행함으로서비도를향상시킬수있다. 2.1.4 AddRoundKey 변환 AddRoundKey 변환은라운드키와상태배열 (CS) 을더하는연산을수행한다. 각라운드키는키스케쥴로부터천이상태가발생될때마다별개의독립된값을산출하며, 산출된값들은식 (12) 와같은연산을수행한다. (12) 여기에서 는라운드수행에대한키스케쥴워드 이며, 는 CS & PRN에대한라운드수행범위를의미한다. AddRoundKey 변환은라운드범위에따라서계산되는횟수는다르지만계산되어지는양은동일하게단순더하기기능만을수행하게된다. 2.2 MSNR 키스케쥴링 일반적인암호알고리즘은키생성알고리즘및키스케줄링작업을수행한다. 이러한키스케줄링작업은보다복잡한키를생성하기위한수단으로서알고리즘의안전도에절대적인역할을수행한다. MSNR 암호알고리즘의경우, 키스케줄링을라운드에따라변화하는방법을사용하지않고, 단지 CS & PRN 방법을사용하여생성한다. 암호문을생성하고자하는평문의일부를이용하여 PRN의 SEED로사용하고 PRN은각 event가발생할때마다라운드과정으로인식하여암호화에필요한키를생성하게된다. 이러한키생성은각라운드마다필요한별개의키를효율적으로생성할수있으며생성된키를이용하여암호화를수행할경우라운드를구별하는기준점을별도로설정할필요성 이없어지게된다. 키생성은 PRN의 event 발생때마다변화하는값을이용하며내부의암호문은 MOIN 블록, 즉네단계의변환을수행할때마다변화하는동시에 PRN의값이변환을조절하게된다. 이러한이유로다른암호알고리즘에서는키와암호문과의크기조절을위하여키길이의확장및축소과정을거치게되지만, MSNR 암호알고리즘은이러한키길이의조작을별도로수행할필요성이없다. 3. MSNR 암호시스템설계및모의실험 MSNR 암호알고리즘의구현은 VHDL을이용하여 Top-down 방식으로진행하였으며회로합성은 Synopsys Design Analyser Ver. 1999.10, QUARTUS 7.0을사용하였고, 모의실험에사용된툴은 Synopsys VHDL Debegger, ModelSim 5.8C를사용하였다. 구현을위한테스트베드는 ALTERA Cyclone EP1C6Q240C8N 디바이스를사용하였다. 입력데이터 128 비트에대하여키값역시 128 비트이며키값 128 비트중일부데이터는입력데이터와 2진곱연산을수행한후 PRNG SEED 값으로사용된다. 암호 / 복호모드에따라서 PRNG의 even, odd가결정되며결정된 PRNG는키정보를 SEED값으로받아랜덤한키정보를출력한다. MSNR 암호시스템은입력 128 비트에대하여출력 128 비트를산출하며암호문또는평문에대하여평문또는암호문을출력하게된다. 암 / 복호화를수행하는데있어필요한정보인키정보는실제적으로암 / 복호화를수행할때는필요없으며, 단지새로운키정보를생성하기위한기본자료로활용될뿐이다. Table 1은기존암호시스템과제안된 MSNR 암호시스템을상호비교분석한표이다 [6-9]. Table 1에서기존대칭형블록암호시스템에비하여 MSNR 암호시스템이처리율면에서 130% 증가됨을확인하였다. 또한라운드횟수와비도에의한암호효율측면에서 MSNR 암호시스템은암호화에사용되어지는키정보가내부 CS와 PRN에의하여생성되며암 / 복호화가동일한시스템에서동시에실행가능함으로서기존블록암호시스템에비하여암 / 복호측면에서 2배의효율을가짐을알수있다. 그러므로전체적인시스템효율은기존블록암호시스템에비하여 MSNR 암호시스템이 2배의 6819
한국산학기술학회논문지제 15 권제 11 호, 2014 성능을가짐을알수있다. 이와같이 MSNR 암호알고리즘은기존블록암호알고리즘에비하여 RFID/USN 과같은자원제약조건을가진환경에서효율적임을확인할수있었다. [Table 1] Analysis Table for performan of MSNR @50MHz structure No. of Rounds Length of data (bits) Length of key (bits) Ratio (Mbps) DES Feistel 16 64 56 31.6 3DES Feistel 48 64 112/168 15.6 SEED Feistel 16 128 128 313.7 Serpent SPN 32 128/192/256 128 197.3 AES SPN 10 128/192/256 128 387.9 MSNR Feistel & SPN 10 128 128 532.0 4. 결론 현대사회는 RFID/USN 등과같은노드망에의한다양한응용분야의확산이매우빠르다. 그러나 RFID/ USN 등은환경적자원제약이라는단점으로인하여보안을유지하기위한암호알고리즘을선택하기매우힘들다. 이에본논문에서는이러한 RFID/USN 자원제약에적합한암호알고리즘인 MSNR 블록암호알고리즘을제안하였다. 제안된 MSNR 암호시스템은암호화를수행하는자원으로서자체정보만을가진다. 또한처리시간및비도는동시다발적인연산으로인하여기존대칭형암호시스템에비하여처리율면에서 130% 증가를가져왔다. 또한암 / 복호화를하나의시스템으로처리가능하므로전체적인시스템효율면에서 2배의성능을가짐을확인하였다. 본논문에서제안한 MSNR 암호알고리즘은기존암호알고리즘에비하여높은전송률및시스템효율을가지며, 특정길이의키결정을수행할필요가없는구조적기반알고리즘이기때문에시스템복잡도가매우낮고처리시간이빠르다. 그러므로제안된새로운 MSNR 암호알고리즘은 RFID/USN 등과같은환경적자원제약조건을극복하기에적합한암호알고리즘으로사료된다. References [1] "information protection in ubiquitous environments", http://www.eic.re.kr, 2008. 11. [2] N. Ferguson, J. Kelsey, S. Lucks, B. Schneier, M. Stay, D. Wagner, and D. Whiting, "Improved Cryptanalysis of Rijndael", Seventh Fast Software Encryption Workshop, Springer-Verlag, 2000. [3] NIST, "AES Algorithm (Rijndael) Information", http://csrc.nist.gov/archive/aes/rijndael [4] I. Damaj, M. Itani, H. Diab, "Serpent Cryptography on Static and Dynamic Reconfigurable Hardware," aiccsa, pp.680-684, IEEE International Conference on Computer Systems and Applications, 2006. DOI: http://dx.doi.org/10.1109/aiccsa.2006.205163 [5] NIST, "pseudo-random number generator", http://www. itl.nist.gov/div897/sqg/dads/html/pseudorandomnumber Gen.html [6] Microelectronic Systems Laboratory, "Implementation of DES Algorithm Using FPGA Technology", http://www. alagger.com/des-vhdl/report.pdf, 2002. [7] "DES and 3DES cores", http://www.heliontech.com/ des.htm [8] SEED block cryptographic algorithm, http://service2.nis. go.kr/pw_certified/seed.jsp [9] "A candidate block cipher for the advanced encryption standard", http://www.cl.cam.ac.uk/~rja14/serpent.html 강영진 (Yung-Jin Kang) [ 정회원 ] < 관심분야 > 초고주파및광통신 1989 년 2 월 : 건국대학교대학원전자공학과 ( 공학박사 ) 1982 년 3 월 ~ 현재 : 원광대학교전자공학과교수 6820