2021.04.09

"RSA 알고리즘이 깨졌을 때" 암호화의 미래

Peter Wayner | CSO
인터넷의 보안 계층에 갑자기 큰 균열이 생긴다면 어떻게 될까? 이 균열이 암호 알고리즘의 수학적 토대에까지 도달한다면 어떻게 될까? 3월 초, '이는 RSA 암호화 시스템을 파괴한다'는 결론이 담긴 논문이 발표되면서 이런 일이 발생했다.  
 
ⓒ Getty Images Bank

이 주장이 맞다면, 보관 또는 이동 중인 암호화된 데이터가 안전하지 않을 수도 있다. 첫 번째 문제는 저자의 주장이 옳은지 여부를 아는 사람이 아무도 없다는 것이다. 두 번째, 더 큰 문제는 저자의 주장이 맞다면 어떻게 대처해야 할지 확신하는 사람이 아무도 없다는 것이다.

이 기사를 쓰는 시점에 수학자들은 여전히 첫 번째 문제를 고민하고 있다. 그러나 두 번째 문제를 다루고, 갑자기 아주 큰 취약점이 출현했을 때 무엇을 할지 계획을 세우기 시작한 사람들도 있다. 이들은 스위칭을 더 단순하게 만드는 프로토콜로 구현한 여러 알고리즘에서 더 강력한 토대를 만들려 시도하고 있다.

일부 암호학자들은 RSA 대체재를 찾고 있다. 이 알고리즘은 전자 분야에서 양자 효과를 활용하는 새로운 머신들에 취약할 수 있는 단일 암호 알고리즘이기 때문이다. 이들은 세상이 더 민첩해져야 한다고 주장한다. 균열이 많이 나타날 가능성이 있기 때문이다.


큰 수의 인수 분해

이 논문의 제목은 ‘SVP 알고리즘을 이용한 빠른 정수 인수 분해(Fast Factoring Integers by SVP Algorithms)’이다. 

저자는 2011년 요한 볼프강 폰 괴테 대학에서 은퇴한 존경받는 암호학자인 클라우스 슈노르다. 이 사람의 이름이 붙은 디지털 서명 체계가 있을 정도로 슈노르는 저명한 암호학자이다. 

1988년 처음 특허를 받았고, 이후 일부 디지털 화폐들이 효율성과 짧은 서명이라는 장점 때문에 이를 변형해 하용하고 있다. 펄카닷(Polkadot), 쿠사마(Kusama), 질리카(Zilliqa) 블록체인이 대표적인 사례 3가지이다. DLP(Discrete Log Problem)에서 가정되는 난해함이 강점이다.

RSA는 최소한 과거에는 더 광범위하게 도입되었고, 더 오랜 역사를 가진 다른 알고리즘이다. 큰 수를 인수분해하는 복잡성을 활용하는 알고리즘이다. 슈노르가 최근 몇 년 동안 발표한 일련의 논문들을 통해 발전시켜 새로 발표한 방법은 큰 수를 인수분해하는 문제를 수학자들이 때때로 더 작은 수로 정의된 다차원 격자에서 올바른 백터를 찾는 것으로 부르는 문제로 개선한다.

그러나 그의 논문은 이론적이며, 따라서 많은 이가 소프트웨어에 실제 구현했을 때 이런 주장이 실현될지 여부에 의구심을 갖고 있다. 몇몇 사람들은 RSA 키 같이 구축된 큰 수인 도전 문제들을 배포했다. 

RSA를 공격할 수 있는 사람들은 숫자에 대한 인수를 공개해 이를 쉽게 증명할 수 있다. 지금까지 이를 공개적으로 명확히 증명한 사람은 아무도 없다. 이들 시도했던 사람들 가운데 일부는 알고리즘을 작동시킬 수 없었다고 발표했다.


RSA의 약점 해결

새로 발견된 공격에서 비롯된 문제를 해결하는 것은 새롭거나 어려운 일이 아니다. 소프트웨어 업체는 정기적으로 취약점을 수정할 패치를 배포한다. 또 공개적으로 버그 보고서를 요청한다. 사람들에게 발견한 문제를 알려주라고 요청하는 것이다. 하지만 슈노르의 논문이 증명되면 프로토콜의 토대에 존재하는 취약점이 노출되며, 이 프로토콜에 대해 책임을 지는 기업은 단 한 곳도 없을 것이다.

RSA라고 불리는 한 회사가 알고리즘과 상당한 역사를 같이 하지만 특허는 만료되었고, 현재 인터넷에서 사용되는 대부분 RSA는 여기에서 나온 것이 아니다. 많은 인기 라이브러리가 오픈소스이며, 커뮤니티에 의해 유지되고 있다.

더 심각한 문제는 약점이 존재한다면 다른 많은 취약점이나 버그처럼 새 코드 몇 줄로 이 취약점을 해결할 수 없다는 것이다. 새 알고리즘 테스트와 배포에 시간이 걸리기 때문에 해결책이 등장하기까지 몇 년이 걸릴 수 있다.

많은 암호화 패키지가 다른 키 길이를 가진 다른 알고리즘을 사용하는 옵션을 지원하기 때문에 새 알고리즘으로 바꾸는 것은 그렇게 어렵지 않을 수도 있다. 더 큰 도전과제는 퍼블릭 키 검증에 사용하는 인증서 계층을 유지하는 인증 인프라를 업데이트하는 것이다. 현재 주요 브라우저에는 여러 인증 기관의 루트 인증서가 탑재되어 있으며, 상당수는 RSA에 의존한다.

브라우저(그리고 다른 도구들)에서 루트 인증서를 교체하려면 새 버전을 보내야 한다. 루트 인증서가 아주 강력하기 때문에 까다로울 수도 있는 문제다. 예를 들어, 공격자를 보증하는 가짜 인증서를 주입해 다른 사이트를 가장하도록 만드는 공격도 있다. 베리사인(Verisign)과 아마존(Amazon), 고우대디(GoDaddy), 인트러스트(Entrust) 등 일부 주요 인증 기관의 인증서들은 모두 RSA 알고리즘에 의존하고 있다.


양자와 관련된 질문들

향후 구현될 양자 컴퓨터에 대비해 무엇을 할지에 대한 문제 또한 고민거리다. 암호화 관련 커뮤니티는 이미 양자 컴퓨터에 저항할 수 있는 대체재를 찾고 있는 중이다. 양자 컴퓨터가 곧 구현될 수 있다는 두려움 때문에 몇 년 전부터 이런 노력이 시작되었다. 

피터 쇼오가 개발한 가장 잘 알려진 양자 컴퓨터 알고리즘이 수를 인수분해할 수 있어 RSA 같은 알고리즘을 위협할 수 있기 때문이다. 현재 개발된 머신은 아주 강력하지는 않으며, 인수분해 한 가장 큰 수가 21이다. 그러나 더 강력한 모델들이 출현할 전망이다.

이 하나의 알고리즘만 위협이 되는 것이 아니다. 큰 수를 인수분해하는 것은 부분적으로 경제적 가치 때문에 매력적인 도전과제이기 때문이다. 예를 들어, 엘리 구지엔과 니콜라스 상구어드가 발표한 새 논문은 특별한 종류의 메모리를 사용하기 때문이다. 실현되지는 않았지만, 이 디자인은 약 반년 이내에 RSA 기반 루트 인증서에 사용된 2048비트의 수를 인수분해할 수도 있다.


RSA가 아닌 새로운 암호화 시스템 

이런 이론적 결과들 때문에 NIST(National Institute of Standards and Technology)는 2016년에 RSA의 대체재를 찾기 위한 콘테스트를 시작했다. 

대체재들을 선별, 2019년에 26명의 준결승 진출 대체재, 2020년에 7명의 결승 진출 대체재를 선정했다. 아직까지 심사를 하고 있다. 위원회가 연구를 할 8가지 대체재 후보를 선정하기로 결정했기 때문이다. 향후 몇 년간 대체재를 선택할 수 있게 되기 희망하지만, 코로나 19가 진행 속도를 늦추고 있다.

3가지 수학적 방식을 기준으로 결승 진출 대체재를 선정한다. NIST가 ‘가장 유망한 범용 알고리즘’으로 발표한 것 가운데 하나는 격자(Lattices)를 사용하며, 이 격자에서 하나의 요소나 벡터를 찾는 난이도에 의존한다. 3종류의 암호화 체계(CRYSTALS-KYBER, NTRU, SABER)와 2종류의 서명 알고리즘(CRYSTALS-DILITHIUM and FALCON)이 있다.

NIST는 또 로버트 맥엘리스가 1978년 개발한 더 오래된 서명 기반 방식을 선택했다. 이는 일반적인 오류 수정 코드에 적합한 솔루션을 찾는 난이도에 의존한다. 이런 수학적 구성은 일반적으로 데이터 저장과 전송에서의 오류 복구에 사용된다. 그러나 맥엘리스는 올바른 암호 키를 가진 사람을 제외한 다른 사람들은 오류 복구가 어렵도록 구성을 바꾸는 방법을 발견했다. 마지막 결승 진출 대체재는 공격자가 해결하기 어려운 많은 변수로 다항식을 구성하는 이른바 레인보우(Rainbow) 코드이다.

토대가 되는 부분에 대한 더 많은 연구를 장려하기 위해 몇몇 대체재도 이름이 올랐다. 일부는 결승 진출 대체재와 유사한 수학적 토대를 사용한다. 반면 완전히 다른 방식에 의존하는 경우도 있다. 예를 들어, SPHINCS+는 해시 된 값에서 서명을 만든다.

RSA 대체재를 기존의 것과 쉽게 교체하지 못할 수도 있다. 훨씬 더 느린 것도 있으며, 서명 생성 및 데이터 암호화에 있어 동일한 옵션을 제공하지 않는 것도 있다. 많은 대체재가 훨씬 더 큰 키를 이용하며, 활발히 진행되는 연구 가운데 상당수는 유사한 키를 사용하는 변형을 찾는 연구다. 수백 바이트에 불과한 기존 키보다 훨씬 더 큰 500킬로바이트 이상의 키들이 많다.

퍼블릭 키 암호화를 만드는 데 도움을 줬던 암호 전문가인 위트필드 디피는 새로운 대안에는 더 많은 컴퓨팅이 요구될 수 있다고 말했다. 디피는 “캐싱을 더 많이 해야 할 것이다. 계산 측면에서 양자 이후의 시스템이 기존보다 더 비싸다면, 예를 들어 1월 2일에 이베이나 아마존과 키를 협상하기 위해 1분간 계산을 하고, 이를 연중 유지하고, 그런 다음 고전적으로 인증을 해야 할 수도 있다”라고 설명했다.

기존 프로토콜은 통상 각 상호작용마다 새 키를 협상한다. 디피는 계산 측면에서 더 비싼 키 생성을 더 적게 실행시키면 전반적인 비용이 동일해지지만, 전방향 안정성과 서명의 증거 값이 감소하는 대가를 치룬다고 덧붙였다.

1970년대 퍼블릭 키 암호에 대한 연구를 시작했던 또 다른 수학자인 마틴 헬먼은 몇몇 독창적인 알고리즘을 결합한 새 프로토콜을 개발하는 것이 나을 수도 있다고 주장했다. 

일부 데이터를 암호화하기 위해 임의의 키를 생성하는 하나의 알고리즘에 의존하는 대신, 프로토콜은 여러 알고리즘을 실행시키고, 이런 알고리즘들의 키를 하나의 키로 결합해야 한다(XOR을 매개체로 하거나, 더 정교한 일방향 함수를 통해).

헬먼은 10년 넘게 특정 알고리즘의 붕괴에 대비하는 방법을 생각했다. 이런 종류의 장기적인 보안을 추가하면 갑자기 강력한 공격 위협이 출현했을 때 발생할 수 있는 ‘공포’를 막을 수 있다.

이런 재앙적인 문제가 발생하지 않더라도, 인수분해나 다른 공격에 대한 알고리즘의 진화에 기반을 둔 작은 발전이 계속 쌓일 수 있다고 말했다. 치명적인 문제를 대비하는 좋은 계획은 몇 년 동안 느리게 증가하는 성능에 대비하는 것에도 도움이 될 수 있다. 

헬먼은 “현재 비밀인 일부 데이터는 50년, 100년이 지나도 여전히 비밀이어야 한다. 미래의 발전은 현재 보호되고 있는 데이터에 위험한 영향을 초래할 수 있다”라고 말했다. editor@itworld.co.kr 


2021.04.09

"RSA 알고리즘이 깨졌을 때" 암호화의 미래

Peter Wayner | CSO
인터넷의 보안 계층에 갑자기 큰 균열이 생긴다면 어떻게 될까? 이 균열이 암호 알고리즘의 수학적 토대에까지 도달한다면 어떻게 될까? 3월 초, '이는 RSA 암호화 시스템을 파괴한다'는 결론이 담긴 논문이 발표되면서 이런 일이 발생했다.  
 
ⓒ Getty Images Bank

이 주장이 맞다면, 보관 또는 이동 중인 암호화된 데이터가 안전하지 않을 수도 있다. 첫 번째 문제는 저자의 주장이 옳은지 여부를 아는 사람이 아무도 없다는 것이다. 두 번째, 더 큰 문제는 저자의 주장이 맞다면 어떻게 대처해야 할지 확신하는 사람이 아무도 없다는 것이다.

이 기사를 쓰는 시점에 수학자들은 여전히 첫 번째 문제를 고민하고 있다. 그러나 두 번째 문제를 다루고, 갑자기 아주 큰 취약점이 출현했을 때 무엇을 할지 계획을 세우기 시작한 사람들도 있다. 이들은 스위칭을 더 단순하게 만드는 프로토콜로 구현한 여러 알고리즘에서 더 강력한 토대를 만들려 시도하고 있다.

일부 암호학자들은 RSA 대체재를 찾고 있다. 이 알고리즘은 전자 분야에서 양자 효과를 활용하는 새로운 머신들에 취약할 수 있는 단일 암호 알고리즘이기 때문이다. 이들은 세상이 더 민첩해져야 한다고 주장한다. 균열이 많이 나타날 가능성이 있기 때문이다.


큰 수의 인수 분해

이 논문의 제목은 ‘SVP 알고리즘을 이용한 빠른 정수 인수 분해(Fast Factoring Integers by SVP Algorithms)’이다. 

저자는 2011년 요한 볼프강 폰 괴테 대학에서 은퇴한 존경받는 암호학자인 클라우스 슈노르다. 이 사람의 이름이 붙은 디지털 서명 체계가 있을 정도로 슈노르는 저명한 암호학자이다. 

1988년 처음 특허를 받았고, 이후 일부 디지털 화폐들이 효율성과 짧은 서명이라는 장점 때문에 이를 변형해 하용하고 있다. 펄카닷(Polkadot), 쿠사마(Kusama), 질리카(Zilliqa) 블록체인이 대표적인 사례 3가지이다. DLP(Discrete Log Problem)에서 가정되는 난해함이 강점이다.

RSA는 최소한 과거에는 더 광범위하게 도입되었고, 더 오랜 역사를 가진 다른 알고리즘이다. 큰 수를 인수분해하는 복잡성을 활용하는 알고리즘이다. 슈노르가 최근 몇 년 동안 발표한 일련의 논문들을 통해 발전시켜 새로 발표한 방법은 큰 수를 인수분해하는 문제를 수학자들이 때때로 더 작은 수로 정의된 다차원 격자에서 올바른 백터를 찾는 것으로 부르는 문제로 개선한다.

그러나 그의 논문은 이론적이며, 따라서 많은 이가 소프트웨어에 실제 구현했을 때 이런 주장이 실현될지 여부에 의구심을 갖고 있다. 몇몇 사람들은 RSA 키 같이 구축된 큰 수인 도전 문제들을 배포했다. 

RSA를 공격할 수 있는 사람들은 숫자에 대한 인수를 공개해 이를 쉽게 증명할 수 있다. 지금까지 이를 공개적으로 명확히 증명한 사람은 아무도 없다. 이들 시도했던 사람들 가운데 일부는 알고리즘을 작동시킬 수 없었다고 발표했다.


RSA의 약점 해결

새로 발견된 공격에서 비롯된 문제를 해결하는 것은 새롭거나 어려운 일이 아니다. 소프트웨어 업체는 정기적으로 취약점을 수정할 패치를 배포한다. 또 공개적으로 버그 보고서를 요청한다. 사람들에게 발견한 문제를 알려주라고 요청하는 것이다. 하지만 슈노르의 논문이 증명되면 프로토콜의 토대에 존재하는 취약점이 노출되며, 이 프로토콜에 대해 책임을 지는 기업은 단 한 곳도 없을 것이다.

RSA라고 불리는 한 회사가 알고리즘과 상당한 역사를 같이 하지만 특허는 만료되었고, 현재 인터넷에서 사용되는 대부분 RSA는 여기에서 나온 것이 아니다. 많은 인기 라이브러리가 오픈소스이며, 커뮤니티에 의해 유지되고 있다.

더 심각한 문제는 약점이 존재한다면 다른 많은 취약점이나 버그처럼 새 코드 몇 줄로 이 취약점을 해결할 수 없다는 것이다. 새 알고리즘 테스트와 배포에 시간이 걸리기 때문에 해결책이 등장하기까지 몇 년이 걸릴 수 있다.

많은 암호화 패키지가 다른 키 길이를 가진 다른 알고리즘을 사용하는 옵션을 지원하기 때문에 새 알고리즘으로 바꾸는 것은 그렇게 어렵지 않을 수도 있다. 더 큰 도전과제는 퍼블릭 키 검증에 사용하는 인증서 계층을 유지하는 인증 인프라를 업데이트하는 것이다. 현재 주요 브라우저에는 여러 인증 기관의 루트 인증서가 탑재되어 있으며, 상당수는 RSA에 의존한다.

브라우저(그리고 다른 도구들)에서 루트 인증서를 교체하려면 새 버전을 보내야 한다. 루트 인증서가 아주 강력하기 때문에 까다로울 수도 있는 문제다. 예를 들어, 공격자를 보증하는 가짜 인증서를 주입해 다른 사이트를 가장하도록 만드는 공격도 있다. 베리사인(Verisign)과 아마존(Amazon), 고우대디(GoDaddy), 인트러스트(Entrust) 등 일부 주요 인증 기관의 인증서들은 모두 RSA 알고리즘에 의존하고 있다.


양자와 관련된 질문들

향후 구현될 양자 컴퓨터에 대비해 무엇을 할지에 대한 문제 또한 고민거리다. 암호화 관련 커뮤니티는 이미 양자 컴퓨터에 저항할 수 있는 대체재를 찾고 있는 중이다. 양자 컴퓨터가 곧 구현될 수 있다는 두려움 때문에 몇 년 전부터 이런 노력이 시작되었다. 

피터 쇼오가 개발한 가장 잘 알려진 양자 컴퓨터 알고리즘이 수를 인수분해할 수 있어 RSA 같은 알고리즘을 위협할 수 있기 때문이다. 현재 개발된 머신은 아주 강력하지는 않으며, 인수분해 한 가장 큰 수가 21이다. 그러나 더 강력한 모델들이 출현할 전망이다.

이 하나의 알고리즘만 위협이 되는 것이 아니다. 큰 수를 인수분해하는 것은 부분적으로 경제적 가치 때문에 매력적인 도전과제이기 때문이다. 예를 들어, 엘리 구지엔과 니콜라스 상구어드가 발표한 새 논문은 특별한 종류의 메모리를 사용하기 때문이다. 실현되지는 않았지만, 이 디자인은 약 반년 이내에 RSA 기반 루트 인증서에 사용된 2048비트의 수를 인수분해할 수도 있다.


RSA가 아닌 새로운 암호화 시스템 

이런 이론적 결과들 때문에 NIST(National Institute of Standards and Technology)는 2016년에 RSA의 대체재를 찾기 위한 콘테스트를 시작했다. 

대체재들을 선별, 2019년에 26명의 준결승 진출 대체재, 2020년에 7명의 결승 진출 대체재를 선정했다. 아직까지 심사를 하고 있다. 위원회가 연구를 할 8가지 대체재 후보를 선정하기로 결정했기 때문이다. 향후 몇 년간 대체재를 선택할 수 있게 되기 희망하지만, 코로나 19가 진행 속도를 늦추고 있다.

3가지 수학적 방식을 기준으로 결승 진출 대체재를 선정한다. NIST가 ‘가장 유망한 범용 알고리즘’으로 발표한 것 가운데 하나는 격자(Lattices)를 사용하며, 이 격자에서 하나의 요소나 벡터를 찾는 난이도에 의존한다. 3종류의 암호화 체계(CRYSTALS-KYBER, NTRU, SABER)와 2종류의 서명 알고리즘(CRYSTALS-DILITHIUM and FALCON)이 있다.

NIST는 또 로버트 맥엘리스가 1978년 개발한 더 오래된 서명 기반 방식을 선택했다. 이는 일반적인 오류 수정 코드에 적합한 솔루션을 찾는 난이도에 의존한다. 이런 수학적 구성은 일반적으로 데이터 저장과 전송에서의 오류 복구에 사용된다. 그러나 맥엘리스는 올바른 암호 키를 가진 사람을 제외한 다른 사람들은 오류 복구가 어렵도록 구성을 바꾸는 방법을 발견했다. 마지막 결승 진출 대체재는 공격자가 해결하기 어려운 많은 변수로 다항식을 구성하는 이른바 레인보우(Rainbow) 코드이다.

토대가 되는 부분에 대한 더 많은 연구를 장려하기 위해 몇몇 대체재도 이름이 올랐다. 일부는 결승 진출 대체재와 유사한 수학적 토대를 사용한다. 반면 완전히 다른 방식에 의존하는 경우도 있다. 예를 들어, SPHINCS+는 해시 된 값에서 서명을 만든다.

RSA 대체재를 기존의 것과 쉽게 교체하지 못할 수도 있다. 훨씬 더 느린 것도 있으며, 서명 생성 및 데이터 암호화에 있어 동일한 옵션을 제공하지 않는 것도 있다. 많은 대체재가 훨씬 더 큰 키를 이용하며, 활발히 진행되는 연구 가운데 상당수는 유사한 키를 사용하는 변형을 찾는 연구다. 수백 바이트에 불과한 기존 키보다 훨씬 더 큰 500킬로바이트 이상의 키들이 많다.

퍼블릭 키 암호화를 만드는 데 도움을 줬던 암호 전문가인 위트필드 디피는 새로운 대안에는 더 많은 컴퓨팅이 요구될 수 있다고 말했다. 디피는 “캐싱을 더 많이 해야 할 것이다. 계산 측면에서 양자 이후의 시스템이 기존보다 더 비싸다면, 예를 들어 1월 2일에 이베이나 아마존과 키를 협상하기 위해 1분간 계산을 하고, 이를 연중 유지하고, 그런 다음 고전적으로 인증을 해야 할 수도 있다”라고 설명했다.

기존 프로토콜은 통상 각 상호작용마다 새 키를 협상한다. 디피는 계산 측면에서 더 비싼 키 생성을 더 적게 실행시키면 전반적인 비용이 동일해지지만, 전방향 안정성과 서명의 증거 값이 감소하는 대가를 치룬다고 덧붙였다.

1970년대 퍼블릭 키 암호에 대한 연구를 시작했던 또 다른 수학자인 마틴 헬먼은 몇몇 독창적인 알고리즘을 결합한 새 프로토콜을 개발하는 것이 나을 수도 있다고 주장했다. 

일부 데이터를 암호화하기 위해 임의의 키를 생성하는 하나의 알고리즘에 의존하는 대신, 프로토콜은 여러 알고리즘을 실행시키고, 이런 알고리즘들의 키를 하나의 키로 결합해야 한다(XOR을 매개체로 하거나, 더 정교한 일방향 함수를 통해).

헬먼은 10년 넘게 특정 알고리즘의 붕괴에 대비하는 방법을 생각했다. 이런 종류의 장기적인 보안을 추가하면 갑자기 강력한 공격 위협이 출현했을 때 발생할 수 있는 ‘공포’를 막을 수 있다.

이런 재앙적인 문제가 발생하지 않더라도, 인수분해나 다른 공격에 대한 알고리즘의 진화에 기반을 둔 작은 발전이 계속 쌓일 수 있다고 말했다. 치명적인 문제를 대비하는 좋은 계획은 몇 년 동안 느리게 증가하는 성능에 대비하는 것에도 도움이 될 수 있다. 

헬먼은 “현재 비밀인 일부 데이터는 50년, 100년이 지나도 여전히 비밀이어야 한다. 미래의 발전은 현재 보호되고 있는 데이터에 위험한 영향을 초래할 수 있다”라고 말했다. editor@itworld.co.kr 


X