공인인증체계에서 이용되는 보안 알고리즘의 안전성 전자인증센터 과장 이한욱(tubby@kftc.or.kr) I. 들어가는 말 84 II. 보안 알고리즘 종류 85 1. 대칭키 알고리즘 85 2. 알고리즘 87 3. 해쉬 알고리즘 91 III. 공인인증체계에서 보안 알고리즘 활용 93 IV. 보안 알고리즘 공격방법 95 1. 대칭키 알고리즘 공격방법 95 2. 알고리즘 공격방법 96 3. 해쉬 알고리즘 공격방법 97 V. 공인인증체계에서 이용되는 보안 알고리즘 안전성 98 1. 대칭키 알고리즘 안전성 98 2. 알고리즘 안전성 99 3. 해쉬 알고리즘 안전성 100 VI. 향후 전망 101 참고문헌 104 2006. 1 83
Ⅰ. 들어가는 말 2005년 6월에 발생한 인터넷뱅킹 해킹 사건이 2005년 가장 기억에 남는 정보보호 뉴 스로 선정되었다고 한다. 해킹 등으로 인해 개인의 PC가 악의적인 해커에 의해 장악이 된 경우에는 어떤 보안시스템도 제 기능을 다하지 못함에도 불구하고, 해킹 사건을 바라 보는 국민들로서는 인터넷뱅킹이 안전하지 못한 것이 아닌지, 더 나아가 공인인증체계의 보안성에 무슨 문제가 있지 않은지 근심스러운 시각으로 바라본 것이 사실이다. 인터넷 뱅킹이나 공인인증업무를 담당하는 실무자들이야 이런 사건이 발생될 때마다 좌불안석이 되겠지만, 암호학 관계자들은 느긋하다. 오히려 암호학 관계자들이 가장 두려워하는 것 은 보안 알고리즘 취약성과 관련된 연구결과가 나올 때이다. 일반인들은 잘 알지 못하는 사건이지만 2005년 2월 중요한 보안관련 웹사이트에 중국 의 암호학 연구자들에 의해 SHA-1 알고리즘이 깨졌다 1) 라는 글이 게시되었다. SHA-1 알고리즘이 깨졌다 라는 게시물이 사실로 확인된다면 지금 사용하고 있는 거의 대부분 의 보안관련 제품들이 한 순간에 무용지물이 되면서 지금까지 발급된 모든 인증서를 폐 지하여야할 지도 모른다. 따라서 해당 게시물이 구체적인 공격 방법까지 제시된 논문이 아니라 짧은 언급에 불과할 뿐이었지만, 전 세계 암호학 관계자들을 공포의 순간으로 몰 고 가기에 충분한 소식이었다. 이 게시물이 등록된 직후 중국의 암호학 연구자들이 이와 관련된 요약 논문을 발표하면서 이에 관한 진위 여부와 파급효과에 대한 논의가 동시에 진행되었고, 2005년 8월에 CRYPTO 2005 2) 에 정식 논문이 발표된 후 여러 전문가들의 검토와 논의 끝에 보안성에 직접적인 영향을 미치지는 않는다는 결론에 도달하면서 해당 알고리즘의 안전성에 대한 논란은 어느 정도 잦아들었다. 2005년 6월에 발생한 인터넷뱅킹 해킹 사건과 같이 사용자 PC에 대한 해킹으로 인해 인증서 암호가 노출되는 것은 피해가 특정인에 국한된다는 점과 개인의 각별한 주의 및 해킹방지 프로그램과 같은 보안 도구의 활용으로 사고 발생 가능성을 미연에 방지할 수 있다는 점에서 감정적인 부분을 제외하면 업계에 미치는 영향은 크지 않다고 할 수 있다. 하 지만, 보안 알고리즘의 경우 일반인들이 별 관심을 보이지는 않지만 그 취약성이 노출되 면 기업 및 국가 전체가 피해를 입게 되는 치명적인 결과를 초래하게 된다. 따라서 개인 의 PC에 대한 해킹방지의 노력을 기울이는 것 외에도 인터넷뱅킹 등에 접속하였을 때 사 1) 해당 게시물은 B. Schneier라는 암호학 연구자의 개인 블로그(http://www.schneier.com/blog/archives/ 2005/02/sha1_broken.html)에 최초로 게시되었다. 2) CRYPTO는 매년 개최되는 국제 암호학 컨퍼런스의 하나이다. CRYPTO 2005는 2005년 8월에 미국 캘리포니아주 산타 바바라에서 개최되었다. 84 지급결제와 정보기술
공인인증체계에서 이용되는 보안 알고리즘의 안전성 용하는 인증서에 어떤 보안 알고리즘이 적용되고 있으며, 이들이 어느 정도의 보안성을 가지고 있는지 살펴보는 것도 의미 있는 일이 될 것으로 생각된다. 공인인증체계를 기반으로 하는 인터넷뱅킹 및 각종 전자거래에 적용되는 보안 알고리 즘에는 크게 대칭키 알고리즘, 알고리즘 및 해쉬 알고리즘이 있다. 각각의 알고리 즘이 무엇인지는 나중에 설명하기로 하고 여기에서는 일단 세 가지 서로 다른 보안 알고 리즘이 있고 이들이 서로 조화를 이루어 운영된다는 것만 알고 있자. 어떤 시스템이 보안 상 취약하다고 이야기하는 것은 그 시스템의 하부 구조 중에서 가장 보안성이 취약한 부 분을 지칭하는 것이다. 즉, 다른 부분은 모두 완벽한데 한 부분만 보안에 취약하다는 것 은 그 시스템 전체가 보안에 취약하다는 것과 같은 의미이다. 따라서 보안 알고리즘 각각 을 분석하여 어느 것이 가장 취약한지 알아낸다면 우리가 사용하고 있는 공인인증체계가 얼마나 안전한지 판단할 수 있다고 하겠다. 본 고에서는 세 가지 보안 알고리즘이 어떤 역할을 수행하며, 공인인증체계에서는 구체 적으로 어떤 보안 알고리즘이 사용되는지를 알아본 후, 보안상 취약한 부분을 찾기 위해 서 어떤 방법으로 보안 알고리즘을 공격하는지, 현 시점에서 어느 정도의 안전성을 가지 고 있는지 살펴보고자 한다. 아울러 특정 보안 알고리즘의 취약성에 치우치지 않도록 각 보안 알고리즘의 보안강도 3) 는 어느 수준을 유지하는 것이 좋을지에 대해서도 알아보고자 한다. Ⅱ. 보안 알고리즘 종류 1. 대칭키 알고리즘 연인 사이인 두 사람이 다른 사람 몰래 편지를 주고받기로 하고 자물쇠가 달려있는 작 은 상자와 이를 열 수 있는 열쇠를 각자 하나씩 가지고 있다고 가정해 보자. 두 사람은 서 로에게 보낼 편지를 써서 상자에 넣은 후 자물쇠를 잠그고 보낸다면 열쇠를 가지고 있는 3) 보안강도는 어떤 보안 알고리즘의 보안성을 해치기 위해 몇 번의 단위 공격을 반복해야하는 지를 의미하는 것으로 (한 단위 공격에 필요한 시간 반복횟수)의 식으로 표현된다. 일반적으로 단위 공격에 필요한 시간은 고정된 짧은 시간에 처리되므로 반복횟수가 충분히 크다면 고정된 시간의 의미는 상쇄되고 반복횟수만이 의미있는 값으로 남을 것이므로 (반복횟수)의 식으로 간략하게 표현된다. 본 고에서는 보안강도를 표현하기 위해 아주 기초적인 몇 가지 수학적 표현을 사용하고자 한다. 컴퓨터는 비트(Bit)라고 하는 이진수로 데이터를 표현하기 때문에 일상 에서 흔히 사용하는 십진수 형태의 표현보다는 이진수의 표현이 용이하다. n자리의 이진수, 즉 n비트 데이터는 2 n 으로 표현된다. 10 n 이 n자리의 십진수를 표현하는 것과 같은 원리이다. 보안강도를 표기할 때에도 이와 같은 이진수의 표현을 사용하는데, 이는 반복횟수가 컴퓨터의 특정 데이터의 길이와 연관이 있기 때문이다. 2006. 1 85
두 사람만이 비밀편지를 볼 수 있다. 중간에 누군가가 상자를 가로챈다고 하더라도 열쇠 를 가진 두 사람 이외에는 누구도 상자를 열어볼 수 없기 때문에 비밀편지 내용은 누설되 지않게된다. 대칭키 알고리즘은 기본적으로 이러한 상황과 거의 유사하다. 전자문서(비밀편지)가 대 칭키(열쇠)로 암호화되면 똑같은 대칭키를 가지고 있는 상대방만이 이 전자문서를 복호화 할 수 있으며, 누군가가 암호화된 전자문서를 입수하여도 이를 복호화하지는 못하기 때 문에 입수한 사람에게는 아무 의미가 없는 문서가 될 뿐이다(그림1 참조). 군사적인 목적이든 개인적인 목적이든 은밀한 편지를 보내고자 하는 인간의 욕구는 동 서고금을 막론하고 항상 존재하였던 것으로 생각된다. 고대 스파르타시대에 사용된 것으 로 알려지는 스키탈레 암호법 4) 이래로 1970년대 알고리즘이 등장하기 전까지 암 호라고 하면 대부분 대칭키 알고리즘을 의미하는 것이었다. 오늘날 컴퓨터로 계산하는 대칭키 알고리즘은 고도로 어려운 수학적 방법 같은 것을 사용하는 것이 아니고 이전까 지 손으로 계산하여야 했던 여러 과정을 복잡하게 재구성한 것에 지나지 않는다. 대칭키 알고리즘에 사용되는 키는 대칭키, 비밀키, 단일키, 공용키, 관용키 등과 같은 여러 가지 이름이 있지만 키를 바라보는 시각의 차이일 뿐 모두 동일하다. 대칭키 알고리 즘에서는 미리 약속된 대칭키를 사용하지 않을 경우 암호문과 대칭키를 함께 보낼 수 없 기 때문에 암호문을 전달하는 경로와는 다른 경로로 대칭키를 안전하게 전달하여야 한 다. 암호학에서는 대칭키를 전달하는 것을 대칭키 교환 또는 키 교환이라고 하며, 적절한 대칭키 교환 방법이 대칭키 알고리즘을 활용하는 데 있어 가장 어려운 문제의 하나이다. 앞의 비밀편지의 예에서 다음과 같은 생각을 하는 사람이 있을 지도 모른다. 상자를 가 로챈 사람이 지구상에 존재할 수 있는 모든 열쇠를 가지고 있다고 한다면 얼마나 빨리 상 자를 열 수 있을까? 지구상에 서로 다른 열쇠가 1만개 있고 한번 열기를 시도하는데 1초 씩 걸린다고 가정하면 평균적으로 83분 정도면 해당 열쇠를 찾을 수 있다. 대칭키 알고리 즘에도 똑같은 상황을 적용할 수 있을까? 그렇다. 비밀편지와 유사한 사상에서 출발하였 기 때문에 대칭키 알고리즘도 같은 상황에 직면할 수 있으며, 오히려 누구나 간단하게 키 를 만들 수 있기 때문에 어떤 면에서는 상자 열기보다 더 위험할 수 있다. 하지만 서로 다 른 키가 1만개가 아니라 1억 개라면 같은 조건에서 열쇠를 찾는데에는 약 1년 6개월이 필 요하다. 요즘 사용하고 있는 대칭키 알고리즘은 2 128 개( >10 38 ) 정도의 서로 다른 키가 존 재하기 때문에 같은 조건이라면 평균적으로 5 10 30 년이 걸린다. 참고로 지구의 나이는 대략 4.6 10 9 년(46억년) 정도 된다고 한다. 4) 스키탈레 암호법은 기원전 500년경 전후의 스파르타시대에 사용된 것으로 생각되는 암호법으로 원기둥 통에 나무 줄기를 둘러 감싸고 그 위에 글을 쓴 다음, 줄기를 길게 한 줄로 늘어뜨리면 만들어진다. 이것을 해독하려 면 동일한 둘레를 가지는 원기둥이 필요하다. 이 암호법에서는 원기둥 또는 둘레의 길이가 대칭키에 해당된다. 86 지급결제와 정보기술
공인인증체계에서 이용되는 보안 알고리즘의 안전성 <그림1> 대칭키 알고리즘의 활용 대칭키 교환 사용자 사용자 대칭키 대칭키 DearAli : I have reviewed the new... 대칭키 알고리즘 대칭키 알고리즘 DearAli : I have reviewed the new... 암호화 복호화 &β/ И4h19/r βxㅁgt (... xl_ 암호문 전송 &β/ И4h19/r βxㅁgt (... xl_ 대표적인 대칭키 알고리즘으로는 DES 5), triple-des 6), RC4, IDEA, AES 7) 등의 외산 알고리즘과 SEED 8), ARIA 9) 등의 국산 알고리즘이 있다. 우리나라 공인인증체계에서는 SEED를 주로 사용하며 제한적인 부분에서 DES, triple-des, RC4를 사용하고 있다. 2. 알고리즘 대칭키 알고리즘과는 달리 서로 다른 두 개의 열쇠를 사용하는 새로운 자물쇠가 있다고 가정해 보자. 이 자물쇠는 두 개의 열쇠 중 하나로 잠그면, 반드시 잠근 것과는 다른 열쇠 로만 열 수 있다. 즉 첫 번째 열쇠로 잠근 것은 두 번째 열쇠로만 열 수 있고, 두 번째 열 쇠로 잠근 것은 첫 번째 열쇠로만 열 수 있다. 어떤 사람이 자신의 집 현관에 이 자물쇠가 5) DES(Data Encryption Standard)는 1970년대 초 미국 상무부가 정부와 민간의 조달 등에서 사용할 목적으로 공개 모집된 것 중 IBM이 제안한 것을 미국 국가안전보장국(NSA)이 수정해 표준(FIPS PUB 46-2)으로 만든 알고리즘이다. 6) triple-des는 DES의 키 길이가 짧은 약점을 보완하기 위해 DES 알고리즘을 동일하게 사용하면서 키를 2개 또는 3개 사용하여 한 번의 암호화과정에 DES암호화(첫 번째 키)-DES복호화(두 번째 키)-DES암호화(첫 번째 또는 세 번째 키)의 세 단계 DES 연산을 수행하는 알고리즘이다. 7) AES(Advanced Encryption Standard)는 미국 국립표준기술연구소(NIST)가 기존의 DES 알고리즘을 대체 할 차세대 암호 표준을 공개 모집하여 선정한 알고리즘이다. 공개 모집된 알고리즘 중에서 Rijndael 알고리즘 이 최종적으로 AES로 선정되었으며, 2001년 11월 FIPS PUB 197로 표준화되었다. 지난 2005년 11월에는 ISO/IEC 국제표준화회의에서 국제표준으로 확정되었다. 8) SEED는 민간부분에서 정보와 개인프라이버스 보호를 위해 한국정보보호진흥원(KISA)과 한국전자통신연구원 (ETRI) 주도하에 개발된 대칭키 알고리즘이다. 1999년 9월 국내 단체표준화(TTA.KO-12.0004)를 완료하였 으며, 2005년 11월에는 ISO/IEC 국제표준화회의에서 국제표준으로 확정되었다. 9) ARIA는 국가기관 및 지방자치단체간, 대국민 행정서비스 정보보호를 위해 국가정보원과 국가보안기술연구소 (NSRI) 주도하에 학계, 연구소, 정부기관 공동연구로 개발된 대칭키 알고리즘이다. 2006. 1 87
88 설치된 편지함과 첫 번째 열쇠를 함께 놓아두고 두 번째 열쇠는 편지함 주인인 자신이 가 진다고 가정해보자. 누구라도 편지함 주인에게 비밀편지를 보내려고 하면 편지함에 편지 를 넣고 첫 번째 열쇠로 잠그기만 하면 된다. 첫 번째 열쇠로 잠갔기 때문에 두 번째 열쇠 를 가진 편지함 주인 이외에 어떤 사람도 편지함을 열지 못한다. 따라서 누구라도 편지함 주인에게 비밀편지를 보낼 수 있는 것이다. 이와는 반대로 편지함 주인이 편지를 써서 편 지함에 넣고 두 번째 열쇠로 잠근다면 외부인 중 누구라도 첫 번째 열쇠로 열어볼 수 있 고 편지함 주인이 편지를 쓴 것이라는 확신을 가질 수 있다. 첫 번째 열쇠로 열린다는 것 은 두 번째 열쇠로 잠갔다는 것을 의미하며, 이 열쇠는 주인만이 가지고 있기 때문이다 (그림2 참조). 알고리즘은 이와 같은 특성을 가지는 두 개의 키가 존재하는 암호 알고리즘이 다. 첫 번째 열쇠와 같이 외부인 누구에게나 공개되어 있는 것을 라고 하고, 두 번 째 열쇠와 같이 외부에는 알리지 않고 자신만 보관하고 있어야 하는 것을 개인키라고 한 다. 대칭키 알고리즘과는 달리 비밀을 공유하려는 사람들 간에 공유하게 되는 동일한 키 가 없으며, 외부에 공개되는 키가 존재하는 특징 때문에 보통 알고리즘이라고 한다. 알고리즘은 문서를 로 암호화하느냐, 개인키로 암호화하느냐에 따라서 활용되는 분야가 확연히 차이가 난다. 로 암호화한 경우에는 개인키 소유자만이 복호화할 수 있기 때문에 암호로서 효용성을 가진다. 반면에 개인키로 암호화하는 경우 에는 누구나 복호화할 수 있기 때문에 암호로서의 활용은 불가능하다. 대신 개인키 소유 자만이 문서를 암호화할 수 있기 때문에 암호문 작성자를 알리기 위한 용도로 사용되며, 이를 암호화라는 말 대신 전자서명이라고 한다. 우리나라 공인인증체계의 근간을 이루는 전자서명법은 알고리즘의 두 용도 중에서 전자서명만 규정하고 있으며, 문서 암 호화에 대해서는 규정하지 않고 있다. 따라서 전자서명법에서는 개인키를 전자서명생성 정보라고 정의하고 를 전자서명검증정보라고 정의하고 있다. 알고리즘은 대칭키 알고리즘과는 달리 와 개인키가 상호작용을 하여 암 호화와 복호화를 수행하는 만큼 둘 사이에 상당히 복잡한 수학적 관계가 있으리라는 것 은 쉽게 눈치챌 수 있을 것이다. 여기에서는 알고리즘이 실제 어떤 수학적인 원리 를 이용하는지 살펴보자. 알고리즘 중에서 가장 잘 알려져 있는 RSA 알고리즘은 서로 다른 두 소수의 곱 의 형태로 표시되는 큰 수를 원래의 두 소수로 소인수분해하는 것이 어렵다는 문제에 기 반하여 설계되었다. 서로 다른 두 소수 p와 q를 선택하여 두 소수를 곱한 것을 n, 두 소수 보다 1씩 작은 것을 곱한 수를 Ф(n)이라 하자. 식으로 표현하면 n = p q, Ф(n) = (p- 1)(q-1)이 된다. 다음으로 1보다 크고 Ф(n)보다작은정수중에서Ф(n)과 서로소가 되는 e를 선택하자. 마지막으로 e와 d를 곱하여 Ф(n)으로 나눈 나머지가 1이 되는 d를 구한다. 지급결제와 정보기술
공인인증체계에서 이용되는 보안 알고리즘의 안전성 <그림2> 알고리즘의 활용 [ 암호화 과정 ] 저장소에서 상대방의 획득 저장소에 자신의 등록 사용자 저장소 개인키 사용자 개인키 DearAli : I have reviewed the new... 알고리즘 알고리즘 DearAli : I have reviewed the new... 로 암호화 개인키로 복호화 &β/ И4h19/r βxㅁgt (... xl_ 암호문 암호문 전송 &β/ И4h19/r βxㅁgt (... xl_ 암호문 [ 전자서명 과정 ] 저장소에서 상대방의 획득 저장소에 자신의 등록 사용자 저장소 개인키 사용자 개인키 DearAli : I have reviewed the new... 알고리즘 알고리즘 DearAli : I have reviewed the new... 로 복호화 개인키로 암호화 &β/ И4h19/r βxㅁgt (... xl_ 전자서명문 전자서명문 전송 &β/ И4h19/r βxㅁgt (... xl_ 전자서명문 이를 만족하는 n과 e를 라 하고, d를 개인키라고 한다. 그렇다면 두 소수 p와 q를 모를 경우, n과 e로부터 개인키 d를 얼마나 빨리 구해 낼 수 있을까? n이 두소수p와 q의 곱으로 구성되어 있다는 것을 알고 있으므로, n을 소 인수분해하여 p와 q를 구할수만있다면d를 계산할 수 있을 것이다. 하지만 소수 p, q가 충분히 크다면 두 소수의 곱으로부터 원래의 두 소수를 찾는 것은 매우 어려운 일이라고 한다. 300자리 이상의 정수를 소인수분해하는 것은 2027년 이후에나 가능하다는 연구결 과가 있다. 또한 소인수분해를 하지 않고 n과 e로부터 개인키 d를 구하는 방법은 아직 알려진 바가 없다. 2006. 1 89
방금 구한 와 개인키로 전자서명과 전자서명검증을 어떻게 수행하는지 살펴보 자. 전자서명할 문서를 m이라고 하고 전자서명을 수행한 결과값을 c라고 하면 표1과 같은 식으로 전자서명 과정과 전자서명검증 과정을 표현할 수 있다. <표1> RSA알고리즘의 전자서명 및 전자서명검증과정 전자서명과정 전자서명검증과정 c = m d mod n m = c e mod n 증 명 e와 d를 곱하여 Ф(n)으로 나눈 나머지가 1이 되므로 다음 식이 성립한다. e d = kф(n) + 1 (1) 오일러의 totient 함수에 의하면 다음 식이 성립한다. m Ф(n) mod n = 1 (2) c e mod n (m d ) e mod n m ed mod n 계산식(1)을 대입하면 m kф(n)+1 mod n (m Ф(n) ) k m mod n 계산식(2)를 대입하면 1 k m mod n m 현재까지 알려진 전자서명을 위한 알고리즘은 방금 설명한 소인수분해의 어려 움에 기반을 둔 RSA 알고리즘 11) 외에도 유한체의 이산대수 문제의 어려움에 기반을 둔 DSA 알고리즘 12) 과 KCDSA 알고리즘 13), 타원곡선 상의 이산대수 문제의 어려움에 기반 을 둔 ECDSA 알고리즘 14) 등이 있다. 이 중에서 KCDSA 알고리즘은 국산 알고리즘이다. 우리나라 공인인증체계에서는 RSA 알고리즘을 주로 사용하며, 제한적인 환경에서 ECDSA와 KCDSA를 사용할 수 있다. 10) 표1에서 설명하고 있는 방법은 미국국가표준 X9.62에 기술되어 있는 ECDSA 알고리즘의 전자서명 및 전자서 명 검증방법을 위에서 예로 든 곱셈연산에 맞추어 변형한 것이다. 11) RSA는 1977년 R. Rivest, A. Shamir, L. Adleman 3명의 수학자에 의해 개발된 알고리즘으로 RSA는 이들의 머릿글자를 따서 지어졌으며, RSA Security사가 소유권을 가지고 있다. 12) DSA(Digital Signature Algorithm)는 미국 국립표준기술연구소(NIST)에서 개발되었으며, 2000년 1월 미국 전자서명 표준(FIPS 186-2)으로 승인되었다. 13) KCDSA(Korean Certificate-based Digital Signature Algorithm)는 한국통신정보보호학회의 주관 하에 국내 암호학자들이 주축이 되어 1996년 11월에 개발되었으며, 1998년 10월에 국내 표준(TTA.KO-12.0001)으로 제정되었다. 14) ECDSA(Elliptic Curve Digital Signature Algorithm)는 DSA 전자서명을 타원곡선을 이용한 전자서명 알고리즘으로 변형한 것으로 2000년 1월 미국 전자서명 표준(FIPS 186-2)으로 승인되었다. 90 지급결제와 정보기술
공인인증체계에서 이용되는 보안 알고리즘의 안전성 3. 해쉬 알고리즘 요즘 출판되는 책의 맨 뒷면을 보면 책마다 서로 다른 ISBN이 인쇄되어 있는 것을 볼 수 있다. 이 ISBN은 책 분류와 같은 관리 용도로 매우 유용하게 사용될 수 있다. 누군가 가 어떤 책을 가지고 있다면 단지 책의 뒷면을 보는 것만으로도 쉽게 그 책의 ISBN을 알 수 있다. 하지만 ISBN을 알고 있다고 하더라도 컴퓨터나 분류표의 도움 없이 도서관에서 그 번호에 해당하는 책을 찾아내는 것은 대단히 어려운 일이 될 것이다. 일반적으로 해쉬 알고리즘은 ISBN과 같은 특성을 가지는 고정된 짧은 길이의 데이터로 생각할 수 있다. 책보다 좀 더 전산적인 관점으로 이동하여 정수의 범위에서 살펴보도록 하자. 해쉬 알 고리즘을 설명하기 위해 정수의 범위에서 살펴보는 이유는 우리가 표현할 수 있는 모든 전자적 형태의 문서는 하나의 정수로 표현할 수 있기 때문이다. abcd 라는 데이터는 1,633,837,924 15) 라는 정수로 표현된다. 1K바이트의 데이터라면 대략 2,400자리 정도의 정수로 표현된다. 해쉬 알고리즘은 정수의 형태로 표현된 전자문서로부터 고정된 길이의 정수를 얻는 방법을 이용한다. 이제 해쉬 알고리즘을 하나 간단하게 설계해 보자. 정수를 10으로 나눈 나머지를 계산 하는 방법을 새로 설계한 해쉬 알고리즘이라고 가정해보자. 우리가 어떤 정수(가령 위에 서 예를 든 1,633,837,924)를 가지고 있다고 하면 10으로 나눈 나머지 값(4)은 금방 계 산해 낼 수 있다. 하지만 특정한 나머지 값(4)로 부터 우리가 처음 가지고 있던 그 정수를 유추해 내는 것은 거의 불가능하다. 그렇다면 방금 설계한 알고리즘은 해쉬 알고리즘으 로 온당하게 설계된 것일까? 해쉬 알고리즘이 되기 위해서는 또 다른 중요한 문제가 남아 있다. 비록 특정한 나머지 값으로부터 처음 가지고 있던 정수를 유추하는 것은 거의 불가 능하다고 하더라도 같은 나머지 값을 가지는 무수히 많은 정수를 찾을 수 있다는 점이다. 위의 ISBN의 예로 돌아가서 같은 번호를 가지는 서로 다른 책이 무수히 많이 존재한다면 이는 관리상 큰 문제를 야기할 수 있다. 이와 같이 해쉬 알고리즘을 수행한 결과값과 같은 결과값을 가지는 다른 입력을 발견하 였을 경우 이를 해쉬 알고리즘에서 충돌(Hash Collision)이 발생하였다고 한다. 무한대 의 정수 범위의 값을 고정된 크기의 작은 정수로 줄이는 것이기 때문에 해쉬 알고리즘의 충돌은 필연적으로 발생할 수 밖에 없다. 다만 이를 충분히 어렵게 하여 충돌이 발생하는 경우를 찾아내는 것이 시간상으로나 비용상 불가능하게 만드는 것이 해쉬 알고리즘을 설 계하는 가장 기본적인 원칙이다. 15) ASCII 코드로 abcd 는 16진수로 61626364로 표현되며 이를 십진수로 표기하면 1,633,837,924이다. 2006. 1 91
잘 설계된 해쉬 알고리즘은 표2와 같은 특성을 가진다. 해쉬 알고리즘이 갖추어야 할 여섯 가지 특성 중에서 1 3번 항목은 해쉬 알고리즘의 기본적 특성을 설명한 것이고, 4번 항목은 일방향(One-Way) 특성을 나타낸다. 5번과 6번 항목은 모두 해쉬 알고리 즘의 충돌을 얼마나 방지할 수 있는가에 관한 내용으로 5번 항목의 조건을 완화하여 일 반화한 것이 6번 항목에 해당된다. 이는 5번 항목의 충돌을 찾아내는 것 보다는 6번 항목의 충돌을 찾는 것이 더 쉽다는 것으로, 6번 항목의 조건을 만족시키는 것이 해쉬충 돌의 방지라는 면에서 훨씬 강력하다는 것을 의미한다. 일반적으로 5번 항목의 해쉬함 수 특성을 약한 충돌회피성(Weak Collision Resistance)이라고 하고 6번 항목의 해쉬 함수 특성을 강한 충돌회피성(Strong Collision Resistance)이라고 한다. <표2> 해쉬 알고리즘이 갖추어야 할 특성 1 해쉬 알고리즘은 어떤 크기의 입력도 받아 들일 수 있어야 한다. 2 해쉬 알고리즘의 계산 결과는 고정된 길이의 정수로 나타난다. 3 해쉬 알고리즘은 주어진 입력으로부터 쉽게 계산 결과를 얻을 수 있어야 한다. 4 해쉬 알고리즘의 계산 결과가 주어졌을 때 원래의 입력 값을 찾는 것이 불가능하여야 한다. 5 어떤 입력 값이 주어졌을 때 같은 계산 결과를 얻을 수 있는 다른 입력 값을 찾는 것이 불가능하여야 한다. 6 같은 계산 결과를 얻을 수 있는 임의의 서로 다른 두 입력 값을 찾는 것이 불가능하여야 한다. 해쉬 알고리즘은 앞에서 언급한 대칭키 알고리즘과 알고리즘에 비해 상대적으 로 덜 알려져 있지만, 사용빈도 및 중요성은 두 알고리즘보다 높다고 할 수 있다. 해쉬 알 고리즘은 약한 충돌회피성이 있기 때문에 원래의 데이터가 위 변조되었는지 확인하기 위한 용도로 많이 사용되며, 원래의 데이터를 대표할 수 있는 고정된 크기의 값이기 때문 에 전자서명 등의 용도로 활용되고 있다. 부가적으로 난수 생성이나 메시지인증코드 (Message Authentication Code) 등에서도 활용된다. 대표적인 해쉬 알고리즘으로는 MD5, SHA-1 16), SHA-2 17) 등의 외산 알고리즘과 HAS-160 18) 의 국산 알고리즘이 있다. 우리나라 공인인증체계에서는 SHA-1과 HAS-160을 사용할 수 있도록 규정되어 있지 만, 실제 응용분야에서는 SHA-1만 사용하고 있다. 16) SHA-1은 미국 연방정부 전자서명 표준인 DSA를 위해 개발된 해쉬함수로 1995년 4월에 정식 표준으로 승인 (FIPS PUB 180-1)되었다. SHA-1은 160비트 길이의 출력을 낸다. 17) SHA-2는 보다 높은 수준의 안전성이 요구되는 응용을 위해 만들어진 해쉬 알고리즘으로 224, 256, 384, 512비트 길이의 출력을 가진다. SHA-2는 현재 미국 연방정부에서 표준화를 추진 중에 있으며, FIPS PUB 180-2에 기술되어 있다. 18) HAS-160은 한국형 전자서명 표준인 KCDSA에서 사용할 목적으로 개발되었으며, 1998년 10월의 국내 표준 (TTAS.KO-12.0011)으로 제정되었다. 92 지급결제와 정보기술
공인인증체계에서 이용되는 보안 알고리즘의 안전성 Ⅲ. 공인인증체계에서 보안 알고리즘 활용 우리나라에서 이용되는 보안체계의 상당부분, 특히 국민생활과 밀접한 부분에서는 대 부분 공인인증체계를 이용한다. 공인인증체계라고 함은 전자서명법 19) 을 근간으로 발급된 공인인증서를 이용하는 보안체계를 말한다. 일반적으로 인증서를 사용하는 보안체계를 기반구조 20) 라고 하므로 공인인증체계는 기반구조 중에서도 공인 인증서 를 사용하는 좀 더 좁은 범위라 생각하면 된다. 대칭키 알고리즘에서 가장 큰 문제가 키 교환인 것에 반해 알고리즘에서는 공개 키를 어떻게 공개하는지가 가장 큰 문제이다. 를 그냥 인터넷에서 공개한다고 하 면 수많은 중에서 특정인이 공개한 키를 찾기도 어려울 뿐 아니라 누군가에 의해 의 위 변조가 발생할 수도 있기 때문이다. 이러한 문제점은 를 신뢰할 수 있는 제3의 기관의 보증서를 첨부하여 지정된 장소에 저장하게 하면 해결될 수 있다. 이 방법에서 말하는 신뢰할 수 있는 제3의 기관을 인증기관이라고 하고 이 기관에서 발급한 의 보증서를 인증서라고 한다. 일반적으로 보증의 범위는 등록된 가 특정 인의 개인키와 한 쌍을 이루는 것이 확인되었다 는 정도이지만 전자서명법에서는 여기에 그 특정인이 자연인 또는 법인 중 실명의 누구이다 까지 확인해 주는 것으로 되어 있다. 전자서명법에 의해 지정된 공인인증기관이 발급한, 실명이 기재된 인증서를 공인인증서 라고 한다. 인터넷뱅킹, 인터넷 증권거래 등을 포함한 많은 전자거래를 살펴보면 로그인 단계에서 공인인증서를 사용하여 본인을 확인한다. 일반적으로 공인인증서로 로그인 또는 공인인 증서 제출이라는 이름으로 알려져 있지만 정확히는 본인의 공인인증서에 포함된 와 쌍을 이루는 개인키로 전자서명을 생성하여 제출하는 것이다. 개인키를 안전하게 보 관하기 위해 공인인증서 발급 시 이용자가 입력한 공인인증서 암호로 개인키를 암호화하 여 저장하게 되는데 이 암호는 전자서명할 때마다 공인인증서 선택화면에서 매번 입력하 도록 되어 있다. 내부적으로는 좀 더 복잡한 절차가 있기는 하지만 그냥 공인인증서 암호 를 대칭키로 하는 대칭키 알고리즘을 수행한다고 보아도 무방하다. 19) 전자서명법은 전자문서의 안전성과 신뢰성을 확보하고 그 이용을 활성화하기 위하여 전자서명에 관한 기본적인 사항을 정함으로써 국가사회의 정보화를 촉진하고 국민생활의 편익을 증진함을 목적으로 1999년 제정된 법이다. 20) 기반구조는 를 활용하여 암호화 및 전자서명을 제공하는 보안체계로서 암호학에서 말하는 PKI(Public-Key Infrastructure)를 지칭한다. 2006. 1 93
그림3은 인터넷뱅킹 또는 전자거래에서 공인인증서를 발급받은 고객이 어떻게 전자서 명을 생성하며 전자서명을 전송받은 은행 또는 쇼핑몰 서버가 어떻게 전자서명을 검증하 는지에 대한 과정을 나타내고 있다. 그림3에서 대칭키 알고리즘, 알고리즘 및 해 쉬 알고리즘이 모두 사용되고 있음을 알 수 있다. 알고리즘의 경우 문서 전체에 대한 전자서명을 생성할 수도 있으나, 알고리즘에서 처리할 수 있는 문서의 길이 가 제한되어 있기 때문에 전자서명할 문서가 큰 경우에는 적용에 어려움이 있다. 따라서 문서 전체를 대표할 수 있는 작은 크기의 데이터를 이용할 필요성이 있는데 여기에 해쉬 알고리즘이 사용된다. 해쉬 알고리즘은 앞에서 언급한 것처럼 원래의 문서를 대표할 수 있는 고정된 크기의 값이며, 약한 충돌회피성이 있어 원래의 문서를 위조하더라도 같은 해쉬 결과값이 나타나지 않기 때문에 문서에 대한 해쉬 결과값만을 전자서명하더라도 문 서 전체를 전자서명하는 것과 동일한 효과를 얻을 수 있다. <그림3> 인증서를 활용한 전자서명 과정 및 검증과정 해쉬 알고리즘 원문 원문 해쉬 알고리즘 해쉬 결과값 해쉬 결과값 두값이 일치하는지 확인 알고리즘 전자서명 네트워크 전자서명 알고리즘 해쉬 결과값 인증서 인증서 개인키 대칭키 알고리즘 암호화된 개인키 인증서 암호 : 94 지급결제와 정보기술
공인인증체계에서 이용되는 보안 알고리즘의 안전성 Ⅳ. 보안 알고리즘 공격방법 1. 대칭키 알고리즘 공격방법 대칭키 알고리즘의 가장 일반적인 공격방법은 암호화된 문서를 입수하였을 때 이 암호 문으로부터 평문을 얻기 위한 대칭키 값이 무엇인지 찾는 것이다. 이는 검사해야할 대상 인 대칭키를 키 길이 범위만큼 검사해야 한다는 것으로 대칭키 알고리즘의 보안강도를 결정하는 가장 큰 요소가 대칭키 길이라는 것을 의미한다. 지금은 거의 사용되지 않고 있지만 한 때 전 세계적으로 널리 사용되었던 대칭키 알고 리즘으로 DES가 있다. DES는 종래의 암호방식과는 달리 알고리즘을 공개하였기 때문에 전 세계 암호 전문가들의 주목을 받게 되어 20년 가까이 공격의 대상이 되어 왔다. 오늘 날의 관점으로 보면 DES는 56비트라는 비교적 짧은 키 길이를 가지고 있지만 그럼에도 불구하고 키 길이가 짧은 경우에만 당하는 공격 이외의 다른 공격들에는 잘 견뎌내고 있다. DES를 공격하기 위한 시도는 여러 차례 있었지만 가장 성공적인 것은 1998년 전자프런 티어재단(Electronic Frontier Foundation) 21) 에서 제작한 DES Cracker 22) 라는 하드 웨어에 의한 시도이다. $250,000의 비용을 들여 개발한 이 기기로 56시간 만에 암호화 된 문서에서 DES 키를 찾아냈다. 무어의 법칙 23) 을 이용하여 오늘날로 기술 수준으로 환 산한다면 같은 비용으로 약 3시간 이내에 대칭키를 찾을 수 있으며, 같은 시간 안에 찾기 를 원한다면 $2,500 정도의 비용만으로 가능하다. <그림4> DES Cracker의 칩, 보드 및 시스템 사진 자료 : http://www.eff.org/privacy/crypto/crypto_misc/desccracker 21) 전자프론티어재단은 1990년 컴퓨터와 인터넷의 영역에서 표현의 자유와 개인 프라이버시를 포함한 시민의 기본적 자유 수호를 위해 설립된 비영리 비정파적 조직이다. 22) DES Cracker는 1,800개 이상의 Deep Crack이라는 주문제작 칩이 총 27개의 보드에 탑재된 하드웨어로서 초당 92억개의 키를 검사할 수 있는 능력을 가지고 있다(http://www.eff.org/Privacy/Crypto/Crypto_misc/ DESCracker). 23) 무어의 법칙은 마이크로칩의 처리 능력이 18개월마다 2배씩 증가한다는 것으로 인텔의 공동 설립자인 고든 무어 (Gorden Moore) 회장이 1965년도에 한 연설에서 유래한다. 2006. 1 95
1999년에는 인터넷을 통해 연결된 100,000대의 PC를 활용하여 22시간 만에 같은 결 과를 얻었다. 오늘날과 같이 많은 컴퓨터가 인터넷에 연결되어 있는 환경에서는 DES Cracker와 같은 하드웨어의 개발에 의한 공격보다 훨씬 더 현실적이며 위협적이다. 가 령 자발적 참여자에 의한 것이든 웜이나 바이러스 등에 감염되어 자신도 모르는 사이에 공격에 참여하였든 간에 1억 5천만명 24) 이상되는 전 세계 광대역 네트워크 가입자의 컴 퓨터가 잠재적으로 가용한 컴퓨터 자원으로 판단된다. 2. 알고리즘 공격방법 알고리즘은 앞에서 언급한 것처럼 한쪽으로는 수학적으로 간단하지만 그 반대 의 계산은 어려운 문제를 바탕으로 한다. 어려운 쪽의 문제가 해결 불가능한 것이 아니라 현재까지는 적절한 방법을 찾지 못했을 뿐이며, 근본적으로 어려운 쪽의 문제를 쉽게 풀 수 있는 방법이 발견된다면 해당 알고리즘은 그 의미를 상실하게 될 것이다. 하지 만 현실적으로는 이 새로운 방법을 찾는다는 것은 매우 어려운 일로 여겨지고 있다. 알고리즘의 공격방법에는 암호화된 문서를 입수하였을 때 이 암호문으로부터 평문을 얻기 위한 개인키를 찾거나, 입수한 로부터 이와 쌍을 이루는 개인키를 찾 는 방법이 있다. 이는 공격하고자 하는 특정인, 즉 특정한 에 대한 공격방법에 해 당되는 것으로 대칭키 알고리즘 공격방법과 유사하다. 하지만 실제로는 이 방법으로 개 인키를 찾는 것은 거의 불가능할 뿐만 아니라 설사 찾았다고 하더라도 이로부터 얻을 수 있는 효익이 그리 크지 않기 때문에 알고리즘 공격방법으로 잘 사용되지는 않 는다. 대신 알고리즘은 개인키로부터 를 쉽게 계산해 낼 수 있는 성질을 가지므 로 가능한 모든 개인키를 미리 알아내어서 정리해 둔다면 이로부터 어떠한 가 오 더라도 역으로 개인키를 알아낼 수 있다. 이 방법은 알고리즘의 근본적인 공격방 법이며, 특히 공인인증체계에서 이용되는 RSA 알고리즘의 공격방법으로 유용하다. RSA 알고리즘의 경우 두 소수의 곱의 형태로 표시되는 큰 수를 원래의 두 소수로 소인수 분해하는 것이 어렵다는 것에 기반을 둔다. 따라서 누군가가 특정 범위에 해당하는 모든 소수를 구하기만 하면 구해놓은 가장 큰 소수의 제곱 이내에 속하는 어떤 두 소수의 곱이 라도 쉽게 계산해 낼 수 있다. RSA 알고리즘의 공격은 주로 소수 전체를 구하는 방법으 로 이루어지고 있다. 현재 소인수 분해가 어느 수준까지 이루어졌는지를 알기 위해서는 RSA Security사가 제시하고 있는 큰 수의 소인수분해 도전에 대한 결과를 살펴보면 된다. 24) 2004년 말 기준 전 세계 광대역 인터넷 가입자 수는 약 1억 5890만으로 추정된다(ITU Internet Reports 2005). 96 지급결제와 정보기술
공인인증체계에서 이용되는 보안 알고리즘의 안전성 최근의 결과를 보면 2005년 5월에 663비트 정수를 소인수 분해하는데 성공하였는데 25) 이는 1GHz 인텔 CPU를 가진 컴퓨터 한 대를 사용하였을 경우 121년분 26) 의계산량과같다. 3. 해쉬 알고리즘 공격방법 해쉬 알고리즘이 갖추어야 할 특성에서 언급한 여섯 가지 항목 중에서 단 한 가지라도 만족하지 못하면 해쉬 알고리즘이라고 하기 어렵다. 해쉬 알고리즘이 갖추어야 할 여섯 가지 특성 중에서 처음 네 개는 해쉬 함수의 기본적 특성을 설명한 것이기 때문에 공격대 상에서 제외되므로 해쉬 알고리즘에 대한 공격 대상은 마지막 두 항목에 해당하는 해쉬 충돌회피성에 대한 공격으로 제한된다. 이미 언급한 것처럼 강한 충돌회피성을 만족시키 지 못하는 충돌을 찾아내는 것이 약한 충돌회피성을 만족시키지 못하는 충돌을 찾아내는 것 보다 훨씬 쉽다. 강한 충돌회피성에 대한 취약성을 발견하고 이에 대한 공격이 성공하 였을 경우 해당 알고리즘의 안전성에 문제는 있지만 이를 해킹 또는 문서 위조에 직접 사 용할 수는 없기 때문에 시급한 위험으로 판단하기는 어렵다. 하지만 약한 충돌회피성에 보안 취약성이 있다면 문서를 위조하여도 검사자가 위조여부를 확인할 수 없기 때문에 공인인증체계 뿐만 아니라 보안과 관련된 전 분야에 심각한 위협이 초래될 수 있는 만큼 치명적인 일이 된다. 따라서, 강한 충돌회피성에 대한 보안 취약성의 발견은 약한 충돌회 피성에 대한 보안 취약성이 발견되기 이전에 보다 안전한 해쉬 알고리즘으로의 이행을 위한 안전판 구실을 한다고 볼 수 있다. 전 세계적으로 널리 사용되었고 지금도 일부 분야에서 사용되고 있는 해쉬 알고리즘으 로 1992년에 발표된 MD5가 있다. 이 알고리즘 역시 발표 직후부터 관심이 집중되어 많 은 연구가 이루어졌다. 1993년에 최초의 유사충돌이 발견된 이후 꾸준한 연구성과에 의 해 2004년 결국 최초의 충돌이 발견되었다. 연구 결과에 따르면 IBM P960으로 약 1시 간 만에 충돌을 찾아냈다고 한다. 2005년 3월에는 MD5 알고리즘의 충돌을 이용하여 인 증서를 위조할 수 있는 가능성을 보여주는 논문이 발표되었다. 이 논문은 그림5 27) 에서 보 여주는 유효한 두 인증서를 그 증거로 제시하고 있다. 실제로 인증서가 위조된 것이 아니 기 때문에 인증서 충돌이라는 표현을 사용하고 있지만 인증서만 놓고 본다면 인증서 위 25) http://www.rsasecurity.com/rsalabs/node/asp?id=2092 26) 1GHz 컴퓨터로 121년분이라는 것은 이론적으로 121대의 1GHz 컴퓨터로 1년에 계산해 낼 수 있다는 것과 같은 의미이다. 해당 결과는 S. Contini의 홈페이지(http://www.crypto-world.com/FactorRecords.html)에서 확인할 수 있다. 27) 그림3의 두 인증서는 의 일부 내용을 변경하여 동일한 서명값을 가지도록 유도된 것이다. 인증서에 포함 되어 있는 값 이외에 두 인증서의 내용은 완전히 동일하며, 두 인증서의 '손도장' 항목이 다른 것으로 확인 할 수 있다. 인증서 구조의 구체적인 설명은 본 고의 범위를 넘어서는 것이므로 생략한다. 2006. 1 97
조가 일어난 것이라고 볼 수 밖에 없을 것이다. 이미 학계와 산업계에서는 MD5를 안전 하지 않은 알고리즘으로 판단하고 있다. <그림5> MD5충돌로부터 충돌이 유발된 두 인증서 자료 : Colliding X.509 certificates, Cryptology eprint Archive, 재구성 Ⅴ. 공인인증체계에서 이용되는 보안 알고리즘 안전성 1. 대칭키 알고리즘 안전성 대칭키 길이가 n비트일 때 생성될 수 있는 최대 대칭키의 개수는 2 n 이다. 대칭키 길이 가 1비트 길어질 때마다 생성될 수 있는 최대 대칭키의 개수가 2배씩 증가하기 때문에 키 길이가 1비트 당 공격에 소요되는 시간, 즉 보안강도 역시 2배씩 증가한다. 이는 대칭키 알고리즘의 안전성을 높이기 위한 가장 좋은 방법은 대칭키 길이를 충분히 크게 설계하 여야 한다는 의미이다. 일반적으로 보안 알고리즘의 취약성이 분석되지 않은 설계단계에 서의 대칭키 알고리즘의 보안강도는 전체 키 개수의 절반인 2 n-1 이된다. DES 알고리즘의 키길이가 56비트이고 공인인증체계에서 사용 중인 SEED 알고리즘 의 키길이가 128비트이므로 SEED가 DES에 비해 2 72 배 보안강도가 높다. SEED를 공 격하기 위하여 DES Cracker와 같은 하드웨어를 제작한다면 같은 비용을 투입할 경우 98 지급결제와 정보기술
공인인증체계에서 이용되는 보안 알고리즘의 안전성 약10 19 년이 지나야 암호화된 문서에서 SEED 키를 알아낼 수 있다는 의미이다. 이는 현 실적으로 계산 불가능한 범위에 속한다. 2. 알고리즘 안전성 공인인증체계에서 알고리즘으로는 주로 RSA 알고리즘을 사용하고 있다. RSA 알고리즘 역시 대칭키 알고리즘과 같이 길이에 비례하여 보안강도가 결정되는 것 은 같으나 길이가 1비트 증가할 때마다 보안강도가 2배씩 증가하는 것은 아니다. RSA 알고리즘의 보안강도에 대한 연구논문에 따르면 현존하는 가장 빠른 인수분해 알고 리즘 28) 으로 N자리 숫자를 인수 분해할 경우 소요되는 시간을 L(N)이라 하면, L(N) = exp((c+o(1))(log N) 1/3 (log log N) 2/3 ) 이라는 다소 복잡한 수식으로 표현되고, 추가적으 로 L(N) 의 메모리가 필요하다고 한다. 길이가 1비트 증가할 때마다 보안강도가 약 1.02 ~ 1.05배씩 증가하는 것으로 추산되며, 이는 보안강도를 높이기 위해서는 대칭 키 알고리즘에 비해 길이를 더 크게 하여야 한다는 의미이다. 현재 공인인증체계 에서는 일반가입자의 경우 1,024비트 키 길이의 RSA 알고리즘을 사용하고 있다. 앞의 논문에서는 1,024비트 RSA가 <그림6> RSA 알고리즘 키길이에 따른 해독시간 추이 완전히 해독되기까지는 512비 (단위 : 비트) 1280 트 RSA 해독에 걸린 시간의 7? 백만배 가량 걸릴 것으로 추정 1024 하고 있으며, 무어의 법칙을 이 768 용하더라도 완전한 해독은 512 2027년에 가서야 가능할 것으 256 로 보고 있다. 그러나 현재까지 RSA 알고리즘 키 길이에 따른 0 1970 1975 1980 1985 1990 1995 2000 2005 2010 2015 해독 추이를 그래프로 표시한 년도 자료 : http://www.crypto-world.com/factorrecords.html, 재구성 그림6을 살펴보면 1,024비트 키가 해독될 것으로 예상되는 시간은 앞의 논문에서 제시된 2027년 보다 좀 더 빨라질 수도 있을 것으로 보인다. 28) 현존하는 가장 빠른 인수분해 알고리즘은 General Number Field Sieve 이다. 2006. 1 99
3. 해쉬 알고리즘 안전성 해쉬 알고리즘은 대칭키 알고리즘 및 알고리즘과는 달리 별도의 키가 존재하지 않기 때문에 보안강도는 충돌회피성에 의해 결정된다. 해쉬 알고리즘의 충돌은 해쉬 결 과값의 범위에서 발생하게 되므로 설계단계에서 해쉬 알고리즘의 보안강도는 해쉬 결과 값이 최대 n비트의 값으로 표현될 때 약한 충돌회피성의 경우는 2 n-1, 강한 충돌회피성의 경우는 2 n/2 으로 표현된다(표3 참조). 일반적으로 보안강도라고 하면 가장 취약한 부분에 대해 언급하기 때문에 해쉬알고리즘의 보안강도는 이 중 작은 쪽인 2 n/2 로 표현된다. <표3> 해쉬 알고리즘 충돌회피성의 보안강도 [ 약한 충돌회피성의 보안강도 ] 평균적으로 몇 명을 조사했을 때 나와 생일이 같은 사람이 나타날까? 이 문제를 달리 표현하면 나와 생일이 같은 사람이 존재할 확률이 50% 이상이 되기 위해서는 몇 명이 필요한지 계산하는 문제이다. 어떤 사람이 나 와 생일이 같을 확률은 1/365이므로 확률이 1/2 이상이 되기 위해서는 183명 이상이 필요하다. n 1 1 365 2 365 2 = 을 만족하는 n= =183 k=1 즉, 평균적으로 전체 범위 365의 절반에 해당하는 183명을 조사하면 나와 생일이 같은 사람이 만날 수 있다. 이는 어떤 입력 값인 나 가 주어졌을 때, 내 생일 에 해당하는 해쉬 결과값과 같은 '다른 사람'을 찾는 문제 와 동일하므로 약한 충돌회피성과 같은 문제이다. 해쉬 결과값을 최대 n비트의 값으로 표현할 수 있을 때, 약한 충돌회피성에 의해 를 가진다. 1 2 2 n 인 2 n-1 의 보안강도 [ 강한 충돌회피성의 보안강도 ] 강한 충돌회피성 문제는 해쉬 알고리즘 특성은 생일 패러독스라고 하는 생일이 같은 사람이 적어도한쌍이 상 존재할 확률이 50% 이상이 되기 위해서는 몇 명이 필요한가 를 계산하는 고전적인 문제와 동일하다. 생일 패러독스 문제의 해답은 놀랍게도 23명이다. 평균적으로 23명만 조사하면 생일이 같은 한 쌍을 발견할 수 있다. 증명) 주어진 임의의 정수가 1부터 n사이에서 균등한 확률로 분포되어 있다고 하고 이중에서 임의로 k개 (k n)를 선택하였을 경우 적어도 한 쌍이 중복되어 나타날 확률을 P(n, k)라고 하면, n! P(n, k) = 1- 로 표현된다. (n-k)! n k 1 여기서 P(n, k) 인 k를 계산하면 2 k = 2(ln 2) n = 1.17 n n 가 성립한다. 생일 패러독스에서 n이 365이므로 k = 1.17 365 23 해쉬 결과값을 최대 n비트의 값으로 표현할 수 있을 때, 강한 충돌회피성에 의해서 2 n, 즉 2 n/2 의 보안강도를 가진다. 자료 : Network and Internetwork Security Principles and Practice, 재구성 100 지급결제와 정보기술
공인인증체계에서 이용되는 보안 알고리즘의 안전성 공인인증체계에서 사용되는 SHA-1의 경우 최근 중국의 암호학 연구자들에 의해 공격 을 당했다. 물론 해쉬 알고리즘의 강한 충돌회피성에 대한 공격이므로 치명적이라고는 할 수 없지만 보안관계자들을 모두 공황상태에 빠트릴 만한 충격적인 소식이었다. SHA-1의 경우에는 MD5의 보안 취약성에 대한 연구가 활발한 시점에서도 공격이 쉽지 않았기 때 문에 비교적 안전하다고 판단하여 MD5를 대체하는 알고리즘으로서 대부분의 분야에서 SHA-1 알고리즘을 사용하고 있는 시점이었기에 충격은 클 수밖에 없었다. SHA-1은 해 쉬 결과값의 길이가 160비트이므로 보안강도가 2 80 으로 설계되어 있으나 29) 이 공격방법 으로 인해 보안강도가 2 69 으로 크게 떨어졌다. 앞에서 대칭키 알고리즘 DES를 공격한 Deep Cracker과 같은 하드웨어를 설계하여 공격한다고 가정하면 무어의 법칙을 적용하 여 같은 비용을 들일 경우 3년 6개월이면 같은 해쉬 결과값을 가지는 임의의 서로 다른 두 입력값을 찾아낼 수 있다는 의미이다. 문서의 해쉬 결과값을 직접 위조할 수 있는 단계인 약한 충돌회피성에 대한 효과적인 공격방법은 아직까지 알려진 것이 없다. 따라서 현시점에서 SHA-1의 문서위조 검증 능 력에 대한 보안강도는 설계 당시의 약한 충돌회피성 보안강도인 2 159 에 근사하게 유지되 고 있는 것으로 판단된다. 이는 지구상에 있는 모든 컴퓨터를 동원하더라도 수천억년 이 내에 해쉬 결과값을 위조해 낼 수는 없다는 것을 의미한다. Ⅵ. 향후 전망 앞에서 공인인증체계에서 주로 사용되는 RSA 알고리즘, SEED 대칭키 알고리 즘, SHA-1 해쉬 알고리즘의 안전성에 관해 살펴보았다. SHA-1 알고리즘이 보안강도가 떨어진 것은 사실이지만 지금 당장 위조와 관련된 문제에 직면할 가능성은 낮아 보인다. 일반적으로 2010년까지는 SHA-1 알고리즘을 사용할 수 있다고는 하지만 2010년 이전 이라도 보안강도가 더 높은 해쉬 알고리즘으로 교체될 가능성이 높은 것으로 판단된다. RSA 알고리즘은 키의 길이를 늘여갈 수 있는 구조이며, 연도에 따른 길이의 권고 안이 발표되어 있기 때문에 권고안에 따라 점진적으로 키의 길이를 늘여간다면 큰 문제 가 없을 것으로 보인다. SEED 알고리즘은 키의 길이가 고정되어 있지만 컴퓨터 기술이 비약적으로 발전하지 않는다면 향후 수 십년 이내에 보안강도가 크게 훼손되지는 않을 것으로 보인다. DES 알고리즘이 시간이 지나면서 점차 보안강도가 약해져서 다른 알고 리즘으로 대체된 것처럼 SEED도 언젠가는 다른 알고리즘으로 대체될 것으로 보인다. 29) 해쉬 결과값이 160비트의 값으로 표현될 수 있을 때, 강한 충돌회피성의 보안강도는 2 n/2, 즉 2 80 이다. 2006. 1 101
세 가지 보안 알고리즘이 서로 조화를 이루어 공인인증체계의 전체적인 보안시스템을 구성하며, 이 중에서 가장 보안강도가 낮은 쪽으로 보안 취약성이 결정된다는 것은 이미 언급하였다. 앞에서 언급한 바와 같이 각각의 보안 알고리즘의 보안강도가 서로 다르기 때문에 이들의 보안강도를 유사하게 맞추어 주는 작업이 필요할 것으로 보인다. 이제 SEED 알고리즘의 보안강도로 비교대상을 고정시키고 이와 유사한 보안강도를 가지는 해쉬 알고리즘에는 어떤 것이 있는지 RSA 알고리즘의 키 길이는 얼마가 적당한 지 살펴보기로 하자. SEED를 비교대상의 기준으로 삼는 이유는 세 가지 알고리즘 중에 서 보안강도가 가장 높기도 하지만, 당분간 SEED를 대체할 수 있는 대칭키 알고리즘이 없기 때문이기도 하다. SEED의 키 길이는 128비트이므로 보안강도는 2 127 이지만 근사적 으로 2 128 을 기준으로 삼기로 한다. n비트의 해쉬 결과값을 만드는 해쉬 알고리즘은 이미 앞에서 2 n/2 의 보안강도를 가진다 고 하였다. 따라서 SEED의 보안강도 2 128 과 동등해지기 위해서는 해쉬 결과값 출력범위 가 256비트여야 한다. 여기에 해당하는 해쉬 알고리즘 중에서 현 시점에서 가장 유망한 것은 SHA-256 이다. SHA-256은 출력길이가 다른 여러 SHA-2 알고리즘 중의 하나 로서 SHA-1을 대체할 대표적인 해쉬 알고리즘의 하나로 손꼽힌다. SHA-1과 구조적으 로 유사하기 때문에 중국 암호학자들의 해쉬 공격방법에 취약할 수 있다는 주장이 있지 만 SHA-1의 160비트보다 비약적으로 커진 256비트 해쉬 출력길이를 가지기 때문에 해 쉬충돌을 찾아내는 것은 매우 어려울 것으로 예상된다. 현재 공인인증체계에서 발급 중인 공인인증서를 살펴보면 인증기관의 경우 2,048비트 RSA 를 사용하고 일반가입자의 경우 1,024비트를 사용하고 있다. RSA사의 분석 에 의하면 128비트 키길이를 가지는 대칭키 알고리즘과 동등한 보안강도를 가지기 위해 서는 RSA 알고리즘의 길이는 1,620비트가 필요하다고 한다. 따라서 일반가입자 인증서의 RSA 길이도 1,620비트 이상으로 늘여야 할 것으로 생각된다. 지난 인터넷뱅킹 해킹사건을 계기로 조만간 공인인증체계에서 RSA 알고리즘 키길이 확장과 SHA-256 해쉬 알고리즘의 적용이 이루어 질 것으로 보인다. 정부는 지난 2005 년 11월 2일 공인인증서 대중화에 따른 정보보호대책 관련 국정브리핑에서 공인인증서 정보보호대책으로 스마트카드와 USB 토큰 활용을 추진하는 것과 2006년 말까지 RSA 알고리즘 키 길이를 2,048비트로 높이겠다고 발표하였다. 또한 공인인증기관 간의 기술 회의체인 PKI기술실무작업반에서는 2005년 상반기부터 SHA-1 알고리즘을 대체하기 위한 논의가 이루어지고 있다. 102 지급결제와 정보기술
공인인증체계에서 이용되는 보안 알고리즘의 안전성 마지막으로 대칭키 알고리즘 SEED 자체의 보안강도는 상당히 높은 수준이기는 하지 만 한 가지 짚고 넘어가야 할 곳이 있다. 앞서 그림3을 설명하면서 개인키를 저장할 때 보안을 위해 이용자가 입력하는 인증서 암호를 키로 하여 대칭키 암호화를 한다고 설명 하였다. 인증서 암호는 이용자의 편의성과 보안성을 고려하여 영숫자를 포함하여 8자리 이상을 사용하도록 하고 있는데 많은 사람들이 허용 가능한 가장 짧은 길이인 8자리 인증 서 암호를 선택하고 있다. 또한 외우기 쉽게 특정한 단어 뒤에 1 또는 생년, 학번과 같은 한 두 개의 숫자를 붙여서 인증서 암호를 만드는 경향이 강하다. 이와 같은 인증서 암호 는 개인키 파일이 분실 또는 노출되었을 때 쉽게 암호를 해독할 수 있는 빌미를 제공할 수 있다. 사전에 있는 단어를 사용할 경우 아주 짧은 시간 안에 인증서 암호를 찾아낼 수 있다는 것에 유의해야 한다. 따라서 인증서 사용자들은 가능하다면 8자리보다 큰 무작위 문자열, 대소문자의 임의 조합, 문자열 마지막이 아닌 중간 중간에 숫자들을 끼워 넣는 방식 등으로 인증서 암호를 유추해 내기 어렵게 사용하는 것이 필요하다. 그러나 이 방법 역시 키보드 해킹 등의 방법에는 쉽게 무력화된다. 이 문제를 해결하기 위한 근본적인 대 책은 개인키가 외부로 노출되지 않도록 하는 것이며, 스마트카드와 같은 개인 전자서명 매체의 도입이 필요하다고 판단된다. 국정브리핑 내용 중에서 스마트카드와 USB 토큰 활용 추진 역시 이와 맥락을 같이 하고 있다. 지금까지 공인인증체계에서 이용되는 보안 알고리즘의 특성과 보안강도에 관해 살펴보 았다. 현재 사용 중인 알고리즘에서 약간의 취약성이 발견되고 있기는 하지만 현실세계 에서 이런 취약성을 불법적으로 용도로 활용하는 것은 거의 불가능에 가깝다. 오히려 이 러한 취약성에 대한 연구는 현재 기술보다 월등히 높은 수준의 보안강도를 유지하기 위 한 노력으로 이어지는 촉매가 될 것으로 생각된다. 2006. 1 103
<참고문헌> [1] B. den Boer and A. Bosselaers, Collisions for the compression function of MD5, Advances in Cryptology Eurocrypt'93, 1994 [2] A. Lenstra, X. Wang and B. de Weger, Colliding X.509 certificates, Cryptology eprint Archive, Report 2005/067(http://eprint.iacr.org/2005/067) [3] B. Schneier, Applied Cryptography, John Wiley & Sons, 1996 [4] R. D. Silverman, A Cost-Based Security Analysis of Symmetric and Asymmetric Key Lengths, RSA Bulletin #13, 2000. 4 [5] W. Stallings, Network and Internetwork Security Principles and Practice, Prentice Hall, 1995 [6] X. Wang and H. Yu, How to Break MD5 and Other Hash Functions, Advances in Cryptology Eurocrypt'05, 2005. 5 [7] X. Wang, Y.L. Yin and H. Yu, Collision Search Attacks on SHA1, 2005. 2 (http://theory.csail.mit.edu/~yiqun/shanote.pdf) [8] X. Wang, Y.L. Yin and H. Yu, Finding Collisions in the Full SHA-1, CRYPTO 2005, 2005 104 지급결제와 정보기술