대칭키암호 성재철 서론현대의정보화시대에사용되고있는암호 (Cryptography) 기술은 Secret(crypto) 을 writing(graphy) 하는것으로정의된다. 인터넷통신이나무선통신에서수신자와송신자이외의비허가된개체가메시지를읽을수없도록감추는프라이버시보호서비스나수신자에게메시지나개체의정당성을확인시켜주는인증서비스등컴퓨터및통신상의보안문제를해결하기위해필요한기술적방법을제시하는기술이다. 암호기술은인류역사상가장오래된직업으로서고대 Egyptians은유적에암호화된상형문자를사용했으며, Phaistos의고대유적 (Cretan-Minoan, BC 17세기 ) 은여전히해독불가하다. 또한 Herodotus( 그리스, BC 5세기 ) 는암호문의전송에관한방법기술을제시하였으며, 고대 Hebrews인은성서의특정단어를암호화하였다. 또한 Julius Ceasar는 Ceasar Cipher라불리는단수대치암호를사용하여전쟁을치렀으며, Roger Bacon(13세기 ), Geoffrey Chaucer 등도암호방법을사용하였다. 또한 Leon Alberti(15세기 ) 는 Cipher Wheel을개발하였고, Blaise de Vigenere(1585년 ) 는 Poly Alphabetic Substitution Cipher에관한암호학책을저술하였다. 1790 년경에는 36개의디스크를이용하여 Jefferson Cylinder가개발되었고, 1817년 Wadsworth에의해고안되었으며, 1869 년경 Wheatstone에의해발전된 Wheatstone Disc도있다. 20세기에서는 2차세계대전에사용된 Enigma Rotor Machine 등암호기술은인류역사의발전에크게기여하였다. 현대적암호기술은 1976년 Diffie-Hellman이제안한키교환프로토콜에서시작된다. 기존의단순한암호프로토콜을바탕으로해쉬 (Hash) 알고리즘등다양한요구조건을수용하여안전성이증명가능하며다양한이용이가능하도록발전하고있다. 현대암호에서사용되는기본개념은다음과같다. 1) 암호학 (Cryptography): 읽을수있는메시지를읽을수없는메시지로변환및복원하는데필요한원리및방법을제공하는과학이다. 2) 평문 (Plaintext): 원래의의미있는혹은읽을수있는메시지이며, 인터넷이나이동통신을통해전달되고자하는모든데이터가해당된다. 3) 암호문 (Ciphertext): 평문이암호화과정을통해변환된무의미한혹은읽을수없는메시지이며, 실제통신매체를통해전달되는데이터이다. 4) 암호화 (Cipher): 읽을수있는메시지를읽을수없는메시지로변환하는알고리즘이며크게대칭키방식과공개키방식등으로분류한다. 아래그림에서왼쪽의평문을오른쪽의암호문으로변환하는과정을암호화라고하며, 고대의시저의암호화과정을적용하면암호문으로부터평문의정보를추측할수있다. 그러나현대의방법을사용하면, 암호문과평문의상관관계를전혀찾아낼수없다. 5) 키 (Key): 수신자또는송신자가이용하는암호화에필요한비밀정보이거나또는비밀정보와연관된공개된정보이다. 저자약력성재철교수는고려대학교수학과암호학이학박사 (2002) 로서, 한국정보보호진흥원선임연구원 (2002-2003) 을거쳐현재서울시립대학교수학과에재직중이다. (jcsung@uos.ac.kr) 그림 1. 평문 ( 좌 ) 과암호문 ( 우 ) 비교. 2
트이상의데이터라도그값을대표하는 160비트또는 256 비트등의소량의특정값 (Hash value) 을계산함으로써원본데이터중단한개의비트의데이터삭제, 추가, 변조등을검출할수있는해쉬알고리즘 (Hash Algorithm) 이있다. 블록암호 그림 2. 암호기술로드맵. 6) 암호화 (Encryption): Cipher와 Key를사용하여평문을암호문으로변환하는과정이며, 모든상용알고리즘은공개된다. 7) 복호화 (Decryption): Cipher와 Key를사용하여암호문을원래의평문으로변환하는공개되는과정이다. 8) 암호분석 (Cryptanalysis): 암호해독이라고도하는과정이며, 복호화에사용될키에대한정보없이암호문을평문으로변환하거나키에관한정보를찾는기술이다. 9) 암호학 (Cryptology): Cryptography와 Cryptanalysis의총칭이며, 창과방패를모두연구하는학문이며, 주로수학, 전산, 전자공학등다양한학문이모두결합되어야하는종합학문분야이다. 암호기술의주요연구분야다양한분야에적용되고있는암호기술은사용목적에따라암호알고리즘과암호프로토콜등의분야로구분된다. 암호의핵심을담당하는암호알고리즘은크게대칭키암호 ( 관용암호 ) 와공개키암호로분류한다. [3,4] 대칭키암호는암호를주고받는송신자와수신자가비밀통신을하기전에비밀키를미리분배하여야한다. 반면에공개키암호는암호화하는키와복호화하는키를분리하여암호화하는키는공개하고, 복호화하는키는비밀리에보관하는방식이다. 공개키암호방식은대칭키암호의사전키공유의문제를해결하고자개발된방식으로대칭키방식에비해보다수학적이지만, 암호화및복호화하는시간이대칭키방식보다오래걸린다. 따라서일반적으로사전키공유는공개키암호를이용하여키를송신자와수신자가공유한후, 이후대칭키암호를이용하여비밀통신을수행하는하이브리드 (Hybrid) 형식을주로사용한다. 또한이미제시된충분한양의 0 또는 1 값으로부터다음에제시될값 (0 또는 1) 을 1/2보다더큰확률로예측할수없도록하는의사난수발생알고리즘 (Pseudo Random Number Generators) 이있다. 그리고수백테라비 암호화 (Encryption) 라는것은의미있는데이터 x를자신만이알고있는비밀정보인키 K를이용하여적당한함수에의해랜덤한형태의데이터 y로변환하는과정이다. 이를수학적으로표현하면다음과같다. 여기서, n은평문과암호문의비트길이이고 k는키의비트길이이다. 또한비밀키 K가고정되면 E K( ) 는전단사함수가된다. 대칭키암호는블록암호와스트림암호로구분한다. 메시지를블록단위 ( 보통 n이 64 이상 ) 로암호화하는것을블록암호라하고비트혹은바이트단위 ( 보통 n이 1 혹은 8) 로암호화하는것을스트림암호라한다. 일반적으로긴길이의메시지나파일의경우는 64-비트의블록암호라하면메시지를 64-비트단위로나눈후, 각단위별로암호화함을의미한다. 현대암호의관점에서최초의블록암호는 1977년미국에서개발하여표준으로사용한 DES(Data Encryption Standard) 알고리즘이다. 이블록암호는 n = 64이고 k = 56이다. 즉블록길이는 64비트이고키길이는 56비트이다. [5] DES 내부알고리즘은대치 (Substitution) 와치환 (Permutation) 을일정한횟수반복하면평문이해독이어렵게잘섞인다는샤논 (Shannon) 의정보이론에근거하여만들어졌다. 여기서대치라는것은어떠한문자를다른문자로바꾸는것을의미하는것으로고전암호의시저암호와같은형태의변환을의미한다. 치환이라는것은문자들을서로순서를바꾸어놓은것으로고전암호의스키테일암호와같은변환이다. 따라서 DES 는고전암호인시저암호와스키테일암호를적절히조합하여만든암호라할수있다. 암호분석 (Cryptanalysis) 은케르코프원리 (Kerckhoff s Principle) 를기반으로하여이루어진다. 케르코프원리라는것은암호 [1] 박영수, 암호이야기 - 역사속에숨겨진코드 (2006). [2] 김동현외, 코드브레이커 - 암호해독의역사 (2005). [3] 원동호, 현대암호학 (2004). [4] D. Stinson, Cryptography - Theory and Practice (3rd ed.) (2006). [5] National Institute of Standards and Technology, FIPS 46-3: Data Encryption Standard (1999). 3
알고리즘의안전성은암호알고리즘자체의메커니즘을숨기는것이아니라, 비밀키를찾는것의어려움에기반한다는것이다. 즉암호알고리즘이어떻게구성되었는지를비밀로하는것이아니라알고리즘자체는공개된다는가정에서그알고리즘의비밀요소인키를찾거나평문의정보를얻는것이다. 현대암호는이러한가정에서안전성을다루고있다. 그렇다면 DES의안전성이란과연무엇을의미하는가? 일반적인관점에서 DES를분석한다는것은암호문 C가도청되었을경우평문 M을알아내든지비밀키 K를찾는것이다. 만약공격자가비밀키 K를찾는다면그공격자는암호화함수 E K 의역함수 E K 1 를이용하여 E K 1 (C ) 를계산하여평문을알아낼수있다. 따라서공격자의가장큰목표비밀키 K를찾는키복구공격 (Key Recovery Attack) 이다. 이키복구공격중가장쉽게생각할수있는것이모든가능한키를조사하여키를찾아내는전수조사공격 (Exhaustive Search Attack) 이다. 당연히현대에개발된일반적인블록암호의경우전수조사공격을하는것은쉬운작업이아니다. DES는 56비트의키 K를가지고평문 64비트 (8바이트 ) 의평문을변환하는함수이다. DES의내부를구성하는알고리즘은개발당시의하드웨어환경에최적으로구현이가능하고그당시의암호분석기법으로는분석이어렵게설계되었다. 키길이가 56비트이므로전수조사공격을수행하기위해서는 2 56 번의연산이필요하다. DES의개발당시컴퓨터의계산능력이지금에비해서는현저히떨어졌기때문에이것을계산하는것은몇억년이상걸리는작업이므로거의불가능할것으로판단되었다. 하지만, 1990년대말에들어오면서, 컴퓨팅능력의발달로인해이 2 56 번의연산은현실적으로가능해졌고, 1999년 DES 전용칩인 Deep Crack과 Network 로연결된 distributed.net이공동으로참여한 DES Challenge III 프로젝트에의해 22시간만에키가복구되었다. DES 알고리즘은블록암호분석의시발점이되었다. 1980 년대에는 DES에대한취약점이많이분석되었고세계각국에서는 DES를모방한암호가많이개발되었다. 하지만, DES 를포함한대부분의블록암호는 1990년대초이스라엘의암호학자 E. Biham과 A. Shamir에의해개발된차분분석법 (Differential Cryptanalysis) [6] 과일본의암호학자 M. Matsui 에의해개발된선형분석법 (Linear Cryptanalysis) [7] 에의해분석되었다. DES의경우, 차분분석에의해약 2 48 의복잡도로분석되었고선형분석에의해약 2 43 의복잡도로분석되었다. 이는전수조사보다공격계산량이적다. 일반적으로암호알고리즘에서는공격복잡도가전수조사공격보다적을경우알고리즘이해독되었다고말한다. 그러나두공격의경우필요한 ( 평문, 암호문 ) 쌍의수가각각 2 48 과 2 43 이되어실제적인 그림 3. DES Challenge III 에사용된전용칩과보드. 공격의적용가능성면에서는의문이될수있으나전수조사보다복잡도가낮기때문에해독되었다고볼수있다. 1990년대들어전수조사보다공격복잡도가낮은차분분석과선형분석의개발과전수조사공격의실제적구현가능성은 DES의치명적인약점으로작용되어새로운알고리즘의개발이요구되어졌다. 이러한요구에맞춰 1997년미국에서는차세대블록암호표준 AES(Advanced Encryption Standard) 프로젝트를시작하였다. 이프로젝트에서는과거 DES가정부주도로비밀리에개발된것에반해, 전세계의암호학자를대상으로새로운암호개발을독려하여공개적인평가를통해안전하고효율적인암호를만들고자하였다. 암호알고리즘의설계기준은전수조사관점에서 DES를세번암호화한것보다안전해야하고현재까지개발된블록암호의분석기법에도취약성이없어야한다는것이었다. 전세계에걸쳐약 20여개의알고리즘이제안되어, 3년여의공개검증절차를거쳐벨기에에서개발된 Rijndael 알고리즘이새로운블록암호표준으로개발되었다. 이알고리즘은 2000년미국 NIST의표준블록암호 AES가되었다. [7] AES의블록길이는 128비트이고키길이는 128비트이다. 블록길이와키길이가두배이상늘어났다. 전수조사의관점에서 DES보다 2 72 배향상되었다. 이는 DES가해독되는데하루걸린다면 AES는 2 72 일걸림을의미한다. 즉, 현재및향후최소한 10년간은컴퓨팅능력의획기적인발전이없는한전수조사공격으로는해독이불가능함을의미한다. AES 알고리즘의경우도전체적인설계의논리는 DES와같이치환과대치의반복으로구성되어있다. 하지만 DES보다는암호학적공격내성에강하도록수학적으로안전한암호논리를기반으로설계되어졌다. 2001년이전에개발된정보보 [6] E. Biham and A. Shamir, Differential Cryptanlaysis of the Full 16-round DES, Advances in Cryptology - CRYPTO'92 (Springer-Verlag, 1992). [7] M. Matsui, The First Experimental Cryptanalysis of DES, Advances in Cryptology - CRYPTO'94 (Springer-Verlag, 1994). 4
호제품이나소프트웨어에는 DES가탑재되어있고, 그이후개발된제품에는 AES 알고리즘이사용되고있다. DES와 AES 이외에도다양한형태의알고리즘이제안되고있으나 DES나 AES과비교하면실제널리사용되는블록암호는거의없다고볼수있다. 앞으로 AES의암호에대해새로운공격방법이개발되거나전수조사공격이용이해지기전에는 AES가계속세계적표준으로널리사용될것으로전망된다. 스트림암호스트림암호는블록암호에비해상대적으로는사용빈도가낮으나, 블록암호에비해경량및고속동작이용이하여무선환경이나스트리밍서비스등과같은환경에서많이사용되고있다. 스트림암호의경우과거에는주로하드웨어구현이용이한 LFSR(Linear Feedback Shift Register) 에기반을둔알고리즘을설계하여왔으나, 근래에는다양한응용환경개발과인터넷서비스에서스트리밍기법이많이이용되면서블록암호알고리즘보다고속동작이가능한소프트웨어기반의스트림암호개발이많아지고있다. LFSR 자체만으로는안전성을제공하지못하므로, LFSR 기반의스트림암호알고리즘은높은주기성과좋은통계적성질을갖는 LFSR들을결합하여알고리즘을설계된다. 이러한 LFSR 기반의스트림암호알고리즘은주로유럽을중심으로 1970년대부터 1990년대초까지연구되었다. GSM에사용되는스트림암호 A5나블루투스에사용되는 E0 암호등의대부분의알려진상용암호제품에사용되는스트림암호알고리즘이 LFSR 기반으로설계되어졌다. 암호기술이전세계적으로일반화된 1990년대부터소프트웨어구현에적합한스트림암호알고리즘이등장하기시작하였다. RSA사에서개발한 RC4가 1990년대초개발된대표적소프트웨어구현이용이하도록설계된대표적알고리즘이다. [9] RC4 알고리즘은앞서살펴본블록암호의구조보다는훨씬간단하다. 이알고리즘은카드게임에서카드를뒤섞는셔플링 (Shuffling) 기법을이용한다. 송신자는비밀키를이용하여모든가능한바이트의수인 256개를뒤섞는다. 그런후특정한위치의두지점을이용하여 256개의가능한바이트중하나를고른후그값을키스트림으로사용하여평문과 XOR 연산으로암호화한다. 이후, 다시두개의위치만바꾸어섞은후다시특정위치의바이트를키스트림으로반복하여사용한다. 이러한연산을필요한만큼하여키스트림을얻는방식이다. 이러한기법을테이블셔플링방식이라한다. RC4는최초개발당시알고리즘구조에대해서는비공개 그림 4. LFSR 의구조. 이었으나, 1990년대중반알고리즘에대한구조가알려진후, 알고리즘에대한많은취약점이제시되었다. RC4의등장은소프트웨어구현이용이한스트림암호알고리즘의개발및분석에대한연구의시발점이되었다. 1990년대후반에들어오면서다양한설계논리를바탕으로한스트림암호가등장하였다. 블록암호에비해소프트웨어구현을기반으로한스트림암호는설계및분석기법의부족으로인해, 대부분의소프트웨어기반의스트림암호는기존의블록암호설계논리, 해쉬함수의설계논리혹은 LFSR의설계논리를바탕으로설계되었다. 스트림암호의가장대표적인분석기법은상관공격 (Correlation Attack) 기법이다. 이분석기법은 1985년 T. Siegenthaler에의해그공격의개념이소개되었고, 1989년 W. Meier와 O. Staffelbach에의해공격알고리즘이제시되었다. 이후, 이공격의개념을이용하여다수의 LFSR 기반스트림암호뿐아니라, Summation generator 등에도적용되었다. 또한, 일반적인스트림암호의안전성분석에활용될수있도록상관공격알고리즘의효율성및공격복잡도를개선시킨다양한연구결과가개발되었다. 최근에는 LFSR 기반스트림암호뿐아니라, 일반적인스트림암호의안전성분석에기본적인분석방법으로활용되고있다. 상관공격과더불어스트림암호의분석에가장많이활용되고있는기법이대수적공격 (Algebraic Attack) 이다. 이분석법은처음에는공개키암호에적용된분석방법이었으나, 2000 년초이분석방법을블록암호의분석기법으로활용하는방법이 Courtois에의해소개되었다. 하지만대수적공격기법은블록암호의분석보다는스트림암호의공격에실질적으로적용되면서더욱효과적인분석방법으로활용되고있다. 이외에도스트림암호의대표적인분석방법으로 TMTO (Time Memory Trade Off) 공격, 구별공격등여러종류의분석방법이존재한다. 그러나일반적인스트림암호의분석 [8] National Institute of Standards and Technology, FIPS 197: Advanced Encryption Standard (2002). [9] R. Rivest, RC4, unpublished work (A description of RC4 appears in B. Schnier, Applied Cryptography) (1996). 5
방법은각알고리즘의설계논리에따라분석방법도상이하고체계적인분석알고리즘의부재로인해, 스트림암호의안전성을제대로평가할만한분석방법이정비되어있지않다. 따라서블록암호에비해스트림암호의경우개발자가안전성에대한확신을제대로얻지못하고있는실정이다. 해쉬함수 블록암호와스트림암호로구분되는대칭키암호알고리즘과더불어암호알고리즘에서가장널리사용되는프리미티브는바로해쉬함수이다. 해쉬함수는대칭키암호나공개키암호와는달리키가없는암호알고리즘이다. 즉, 비밀요소가없다는것이다. 그러면비밀요소가없는암호알고리즘이어떻게정보보호에서중요한요소로사용될수있을까? 암호학적해쉬함수는전자서명등에서의메시지압축, 키생성, 난수생성등에널리사용되는중요한암호학적함수이다. 데이터의위 변조및인증을제공하는암호학적무결성제공알고리즘으로는해쉬함수 (Hash Function) 와메시지인증코드 (Message Authentication Code) 가있다. 여기서, 해쉬함수는키가없는암호알고리즘이고, MAC은키가있는해쉬함수 (Keyed Hash Function) 로인증의도구로사용된다. 해쉬함수는임의의메시지 x를입력으로받아고정된길이 n비트를출력하는다대일 (Many-to-One) 함수이다. 출력길이로는현재 160비트를사용하고있으며, 안전성을증대하기위해 256비트를사용할것으로전망된다. 해쉬함수는주로전자서명알고리즘과결합하여사용되므로, 공인인증서에필수적인요소로사용되고있다. 이러한이유로해쉬함수의안전성은대부분의암호응용분야에중요한역할을하는요소이다. 암호학적해쉬함수가갖추어야할안전성은다음의세가지이다. - 역상저항성 (Preimage Resistance): 주어진출력 y에대해 h(x) = y를만족하는 x를구하는것이계산상어려워야한다. - 제 2 역상저항성 (Second Preimage Resistance): 주어진입력 x에대해같은출력을내는, 즉 h(x) = h(x ), x ( x) 를구하는것이계산상어려워야한다. - 충돌저항성 (Collision Resistance): 같은출력 (h(x) = h(x )) 을갖는임의의서로다른입력 x와 x 를찾는것이계산상어려워야한다. 해쉬길이가 n비트인해쉬함수가역상저항성과제 2 역상 [10] National Institute of Standards and Technology, FIPS 180-1: Secure Hash Standard (1995). 저항성을갖추기위해서는 2 n 보다효과적인공격기법이없어야한다. 즉, 역상저항성과제 2 역상저항성의안전성은 n비트이다. 이에반해, 충돌저항성에대한안전성은생일공격에의해 n/2비트이다. 따라서우리가일반적으로고려하는해쉬함수는충돌저항성공격에안전한해쉬함수 ( 충돌저항해쉬함수 ) 이다. 이에대한안전성은 n/2 비트이다. 전세계적으로가장널리사용되고있는 160-비트해쉬함수인 SHA-1 [10] 의해쉬길이는는 160비트로그안전성은 80 비트이다. 현재의컴퓨팅능력으로는 2 80 을계산하는것은상당히힘든수준이다. 하지만 SHA-1의경우 2005년중국의암호학자 Wang에의해취약성이발견되었다. 이공격은 2 80 보다낮은복잡도인약 2 63 복잡도로공격가능한것이다. 이복잡도는충돌저항성의안전성이 2 80 보다 2 17 배빠르게계산이가능하다는것을의미한다. 만약 1초에 2 21 번 SHA-1 연산능력 ( 현재의 PC 레벨에서실현가능한최대의컴퓨팅능력 ) 을가진컴퓨터가있다면 1년에는 2 46 번계산이가능하게된다. 따라서약 8백만 (=2 23 ) 대의컴퓨터가동원된다면 1년내에 2 63 의계산이가능하다는결론을얻을수있다. DES의알고리즘의취약성으로인해 AES 프로젝트를통해 AES 알고리즘이개발된블록암호의경우와같이해쉬함수의경우에도현재표준으로사용되고있는 SHA-1의취약성이발견되어미국을중심으로새로운차세대해쉬함수공모사업인가칭 AHS(Advanced Hash Standard) 사업에대한준비가 2005년말부터진행되고있다. 하지만해쉬함수의경우작은길이의메시지로부터큰길이의메시지를모두처리해야하기때문에비교적계산이쉽게설계되어야한다. 또한기존의공격등에대해서도높은안전성이요구된다. 따라서다른암호알고리즘에비해효율성과안전성을두루갖춘해쉬함수를설계하는것은어려운일이될것으로전망된다. 결론본원고에서는정보보안에서중추적역할을담당하는암호기술중기밀성기능의핵심적역할을하는대칭키암호의개념및최근동향을살펴보았다. 또한무결성기능을담당하는해쉬함수에대해서도살펴보았다. 현재아무리안전한알고리즘이라할지라도몇년후에는쉽게해독이될수있는것이암호이다. 컴퓨팅능력은나날이발전하고새로운분석기법도계속개발되고있다. 따라서암호알고리즘은그때그때의 state-of-the-art에의해재평가되어야한다. 이렇게급변하는암호기술의시대적추세에발맞추어나가기위해서는최신기술의개발및습득에최선의노력을다해야할것이다. 6