위키원
안전성 증명
안전성 증명(security proof)란 암호학의 개념에서, 새로운 공격기술에 대한 안전성을 이론적으로 증명하는 것을 의미한다. 어떤 시스템이 공격자 모형을 이용하여 안전성의 조건을 명시하고, 환원이라고 하는 방식으로 널리 알려진 암호학적 성질이 안전하다는 가정하에 이와 같은 안전성의 조건이 만족한다는 것을 증명한다.
개요
양자암호 프로토콜과 관련된 이론 연구는 크게 두 가지 영역으로 나눌 수 있다. 하나는 새로운 양자 암호 프로토콜의 창안이고, 다른 하나는 기존의 또는 새로이 창안된 프로토콜의 안전성 증명에 대한 연구이다. 이 두 연구는 절대 별개의 것이 아니며, 새로운 프로토콜을 제안하는 경우에는 그 프로토콜의 안전성 증명이 병행되는 것이 보통이다. 그리고 안전성 증명은 크게 무조건 안전성과 실재적 안전성으로 나뉜다. 무조건 안전성은 도청자인 이브가 물리 법칙 내에서 앨리스와 이브, 두 사용자가 안전한 암호 키를 나누어 가질 수 있다는 것이다. 보통 이러한 무조건 안전성 증명은 수학적 정리의 형태를 띤다. 이와 달리 실재적 안전성의 증명은 더욱 실험적인 구현에 중점을 둔다. 앨리스와 밥이 양자암호통신을 구현하기 위하여 사용했던 장치들이 완벽하게 작동할 때 양자암호의 안전성을 증명하는 문제는 아주 간단하다. 반면, 그 장치들이 완벽하지 않을 때는 이브는 그를 이용해서 암호 키에 대한 정보를 얻을 수 있다. 그러나 이브가 키에 대해 가질 수 있는 정보량의 최댓값이 앨리스와 밥 사이의 상호정보량보다 적다면, 앨리스와 밥은 고전적인 오류보정과 비밀 증폭을 통해서 안전한 비밀 키를 생성할 수 있다. 2000년에는 모든 광원과 광검출기의 결점을 이브의 기저에 무관한 공격에 포함된다고 가정하여 안전성을 증명한 연구가 발표되기도 했다. 이 증명은 흔히 Shor-Preskill 증명으로 알려져 있다. 2003년의 Koashi-Preskill 증명은 광검출기가 완전하다고 가정하고 광원이 앨리스의 기저 정보를 이브에게 흘려주진 않았지만 완전하지는 않다는 가정을 한다. 2004년에는 지금까지의 증명 중 실재 양자암호 시스템과 가장 유사하도록 광원과 광검출기가 모두 기저에 대한 정보의 일부를 이브에게 유출할 경우에 대한 안전성을 증명했다.
실재적인 양자암호 시스템에서는 특정한 양자암호 프로토콜을 제안하거나 실재적 안전성을 증명하려 할 때, 도청자가 행동할 수 있는 도청 방법을 하나 상정해놓고 그 도청 방법에 대해 안전함을 보인다. 도청자가 시도할 수 있는 도청 방법은 크게 두 가지로 나눌 수 있는데, 한 번에 하나의 큐빗에 대해서만 접근을 시도하는 개별 공격법과 몇 개의 큐빗에 한꺼번에 접근해서 정보를 얻어내는 통합 공격법이 있다.[1]
암호 알고리즘의 안전성
암호 알고리즘의 안전성은 다음과 같다.
- 무조건적 안전성: 절대적 안전성이라고도 한다. 무한한 컴퓨터 자원을 가져도 암호 알고리즘을 해독할 수 없는 경우를 의미한다. 공격자가 무한한 계산 능력을 갖췄다고 하더라도 암호문으로부터 평문에 대한 그 어떤 정보도 얻을 수 없으며, 암호문을 수신하기 전에 평문에 대한 사전 정보량과 암호문을 수신한 후 정보량이 같을 때 무조건 안전성을 만족한다. 무조건 안전성의 예로 일회용 패드를 들 수 있다.
- 계산적 안전성 : 암호 알고리즘을 해독하기 위한 지금까지 알려진 가장 우수한 공격 방법을 사용하더라도 불합리하게 많은 컴퓨터 시간을 요구할 경우 공격 방법의 기준이 된다. 원리적으로 해독이 가능하지만 해독에 필요한 계산량이 많아서 실제로는 해독이 불가능한 상황이며, 정당한 수신자의 복호화 시간과 비밀정보를 모르는 공격자의 복호화 시간의 상대적 차이를 이용한 안전성이다.
- 증명 가능 안전성: 인수분해 문제와 같이 어렵다고 알려진 문제와 비교하여 판단한다. 안전성에 대한 절대적인 증명은 아니다. 어렵다고 알려진 문제와 등가일 경우를 의미한다.
- 의미론적 안전성: 암호문이 주어졌을 때 효율적으로 계산할 수 있는 모든 것을 암호문이 없어도 계산할 수 있어야 한다. 다항식 계산 능력을 갖춘 공격자는 암호문으로부터 평문에 대한 어떤 정보도 얻을 수 없다.
- 구별 불가 안전성: 두 개의 메시지 중에서 하나를 암호화한 암호문이 주어졌을 때, 공격자가 어떤 평문을 암호화한 것인지 맞힐 수 있는 확률이 50%보다 높지 않아야 한다.
- NM 특성: 암호문에 대응되는 평문을 알지 못하는 경우, 이 암호문을 의미 있는 다른 암호문을 변경하는 것이 불가능하다면 암호 알고리즘은 NM 특성을 제공하는 것이다. NM 특성은 의미론적 안전성보다 강한 특성이다.[2]
암호 알고리즘의 안전성은 해독하는 데 필요한 노력으로 측정된다. 보통 대칭 암호 알고리즘의 경우에는 전사 공격을 통해 암호를 해독할 수 있다. 즉, 현재 실제로 사용되고 있는 암호 알고리즘들은 무조건 안전한 것이 아니다. 알고리즘이 절대적으로 안전하다는 것은 무한한 컴퓨팅 자원이 있어도 공격을 성공적으로 진행할 수 없다는 뜻이다. 전사 공격을 통해 해독을 할 수 있더라도 거기에 드는 시간이나 컴퓨팅 능력에는 현실성이 없기 때문에 실제로 사용하는 데 전혀 문제가 없다. 이처럼 어떠한 암호 알고리즘을 지금까지 알려진 가장 우수한 공격 방법으로 공격해서 성공하는데 소요되는 시간이 너무 방대한 시간과 컴퓨팅 능력을 요구하는 경우, 이 알고리즘은 계산적으로 안전하다고 부른다. 공개키 암호 알고리즘도 대칭 암호 알고리즘과 마찬가지로 전사 공격 측면에서는 계산적으로 안전하다. 그러나 이들은 대체로 어렵다고 알려진 수학 문제들에 의존하기 때문에 전사 공격을 하는 것보다는 이러한 수학 문제를 푸는 편이 더 빠르다. 하지만 공개키 암호 알고리즘에 사용되는 수학 문제를 푸는 것 자체가 난이도가 상당히 어렵다고 알려져 있다. 다시 말하자면, 의존하는 수학 문제를 절대 풀 수 없다고 따로 증명된 것은 아니지만 지금까지 알려진 어떤 방법을 사용하더라도 불합리하게 많은 시간과 비용을 부담해야 한다. 이처럼 알고리즘의 안전성이 어렵다고 알려진 다른 문제와 등가일 경우, 이 알고리즘은 증명 가능한 안전성을 가지고 있다고 부른다.[3]
개념
현대 암호학의 기본적인 원리 세 가지는 다음과 같다.
- 어떤 암호학적 문제를 해결하기 위한 첫 번째 단계는 안전성에 대한 엄격하고 정확한 정의를 생성하는 것이다.
- 암호학적 구조의 안전성이 증명되지 않은 가정에 의존할 때, 이 가정이 반드시 명시되어야 한다. 그리고, 이 가정은 가능한 최소화되어야 한다.
- 암호학적 구조는 위 1번의 정의에 대해서 안전성 증명이 명확히 되어야 한다. 그리고, 2번 원리에 따라 관련된 가정을 명시해야 한다.
특히 1번 원리는 안전한 암호 설계를 위한 목표를 제시하고, 다양한 응용 환경에서 어떤 암호 기법이 적합한지 선택지를 제시한다. 또, 주어진 암호기법에 대한 비교 분석을 진행할 수 있으며, 3번 원리는 안전성 증명 개념에 해당한다.
- 환원 접근법: 가정 X가 참인 경우, 시공 Y는 주어진 정의에 따라 안전하다.
- 명제(A AND B → C): 위조를 할 수 없는 고정길이 메시지 서명과 충돌 저항성을 가진 해시함수가 존재하면 위조할 수 없는 가변 길이 메시지 서명 또한 존재한다.
- 대우명제: 가변길이메시지 서명을 위조하면 고정길이 메시지 서명을 위조하거나 해시함수의 충돌 쌍을 찾을 수 있다.
증명 가능한 안전성
암호 알고리즘의 안전성을 평가하는 전통적인 방법은 공격자로부터 공격을 받았을 때 그 공격을 얼마나 오래 버티고 견디고 살아남을 수 있는가에 달려있다. 즉 공격자에게 취약점이 발견되고 처음에 설계했던 기분보다 암호를 더 빠르게 해독한다면 그 알고리즘은 안전하지 않은 것으로 판단하고 폐기한다. 반면에 오랜 시간 동안 효율적인 공격 방법이 발견되지 않으면 안전한 알고리즘으로 평가받아왔다. 그러나 이러한 방식은 체계적인 평가 방법이라고 볼 수 없으며, 암호학자들 안전성을 어떻게 수학적으로 증명하는지에 관해 관심을 가지고 접근한다. 이것이 바로 증명 가능한 안전성이다. 제시된 암호 알고리즘이 정확히 어떤 목표를 가졌는지 상세하게 정의하고, 공격자에게 어디까지 허용할 것인지 정의한 뒤에, 이러한 환경에서 제시된 암호 알고리즘이 안전한가에 대해 수학적으로 접근하고 증명한다. 공격자에게 최대한 많은 능력을 부여해도 암호 알고리즘의 보안 목표가 안전하게 잘 지켜질 수 있다는 것을 보여주기 위함이다. 공격자에게 능력을 제공하는 모델로는 오라클이라는 개념을 사용한다. 예를 들어 공개키 암호 알고리즘의 안전성을 분석하기 위하여 질의자와 공격자 간의 다음과 같은 게임을 생각해본다. 공격자는 공개키와 쌍이 되는 개인 키가 없지만, 어떤 암호문에 대해서도 그걸 복호화해서 평문을 출력해주는 복호화 오라클에 접근할 수 있는 권한을 갖고 있다.
오라클을 이용하는 공격자와 질의자 사이의 게임
- 먼저 공격자는 복호화 오라클을 마음대로 시험해 볼 수 있다. 어떤 암호문이라도 복호화 오라클에 질의를 하면 그에 해당하는 평문을 얻어 볼 수 있다.
- 다음 단계로 공격자는 같은 길이의 두 개의 메시지 M1과 M2를 선택해서 질의자에게 제시한다.
- 질의자는 그중 임의로 하나를 골라서 공개키로 암호화하여 암호문을 만들고 공격자에게 제시한다. 두 메시지 중에서 어떤 것을 선택했는가는 공격자에게 밝히지 않는다.
- 공격자는 복호화 오라클에 암호문을 질의할 수 있는데, 여기서 조건은 위의 단계에서 질의자가 제시했던 암호문만은 질의할 수 없다는 것이다.
- 최종적으로 질의자가 어떤 메시지를 골랐는가에 대해 공격자가 맞춘다면 공격자는 게임에서 이긴다.
위 게임의 공격자는 자신이 복호화 오라클에 질의할 수 있다는 사실을 알고 있고, 따라서 게임에서 이기기 위해 자신에게 가장 유리한 전략대로 질문할 것이다. 공격자는 여러 차례 질문을 던지면서 얻은 경험을 토대로 다음번에는 좀 더 유리한 질의를 만들 수 있다. 이러한 공격을 바로 적응적 선택 암호문 공격이라고 한다. 만약 암호 알고리즘이 안전하다면 이런 게임에서 공격자가 암호문에서 평문이 둘 중 어느 것인지 구분할 수 없어야 한다. 이러한 안전성의 개념을 구별 불가능성(indistinguishability)이라고 한다. 공격자에게 질의 된 암호문을 직접 해독할 수 있는 능력을 제외한 가능한 한 많은 능력을 제공하더라도, 공격자가 두 메시지 중 어느 것이 암호화됐는지 구별할 수 없다면 해당 알고리즘은 공개키 암호 알고리즘으로서 아주 안전한 알고리즘이라고 평가할 수 있다. 이러한 증명 가능한 안전성 개념은 안전한 암호 알고리즘을 설계하기 위해서 필수적인 안전성 평가 방식에 해당한다.[4]
적용
블록 암호
블록 암호는 암호학 용어로, 기밀성 있는 정보를 정해진 블록 단위로 암호화하는 대칭키 암호 시스템이다. 만약 암호화하려는 정보가 블록의 길이보다 길다면, EDB, CBC, OFB, CFB, CTR과 같은 특정한 운용 모드가 사용된다. 블록 암호 알고리즘은 고전된 크기의 키를 사용하여 고정된 크기의 블록 단위로 암호화 복호화 연산을 수행하며, 암호화 키와 복호화 키가 같은 알고리즘을 말한다. 블록 암호에 대한 안전성 증명 방법으로는 선택 평문 공격인 차분 공격과 알려진 평문 공격인 선형공격 등이 있다.
- 차분 공격
- 차분 분석법의 차분 특성(differential characterist)은 블록 암호 알고리즘을 공격하는데 사용되는 편이다. 즉, 확률이 충분히 큰 차분 특성이 존재한다고 할 때, 차분 분석법을 사용하여 몇 비트의 비밀키 정보를 복구할 수 있다. 한편, Lai, Massey, Murph는 그 역이 성립되지 않는다는 점을 알리고 차분 공격에 대한 강도를 반영하는 척도로써 차분 특성을 대신하여 차분(differential)을 제안했다. 차분은 차분 특성들의 집합이다. 어떤 암호의 최대 차분 특성 확률이 낮다고 해서 그 암호가 차분 분석에 대해 안전하다고 할 수는 없으나, 최대 차분 확률이 아주 낮으면 그 알고리즘은 일반적인 차분 분석에 안전함이 알려져 있다. 또, Nyberg, Knudsen은 처음으로 최대 차분 확률이 충분히 낮은 블록 암호 알고리즘의 예를 제시했으며, 이러한 성질을 증명 가능한 안전성이라고 부른다.
- 선형 분석법
- 암호공격의 한 방법으로, 암호화 과정에서의 근사적인 선형 관계식을 찾는 것이 목적이다. 마쓰이 미쓰루의 논문에서 처음 공개되었다. 해당 논문에서는 선형 공격으로 FEAL 암호를 공격하는 방법을 제시했다. 선형 분석도 차분 분석과 함께 블록 암호를 공격하는데 널리 응용되는 방법으로, 차분 분석과 마찬가지로 처음에는 선형 분석의 특성을 이용한다. 그러나 최소 선형집합(linear hull)이라고 불리는 특성 집합이 소개되면서, 선형 분석에 대한 강도의 엄밀한 척도로 여겨졌다. 위의 차분 분석에서 언급한 최대 차분 확률이 충분히 낮은 블록 암호 알고리즘의 예는 최소 선형집합이 작아서 선형 분석에 대해서도 증명 가능한 안전성을 지닌다. 하지만 계산의 효율성은 별로 좋지 않다는 단점이 있다.[5]
한계
엄연히 말하면 안전성 증명은 증명이라고 볼 수 없다. 증명 과정이 겨우 '증명되지 않은' 가설로 환원하는 정도이거나, 랜덤 오라클 모델처럼 존재하지 않는 가상의 이론적인 모형을 사용하기 때문이다. 이론 전산학적인 관점에서 본다면, 안전성을 증명하는 데는 다음과 같은 두 가지 문제점이 있다.
- 대부분의 암호학적 성질이 계산 복잡도 이론의 기본적인 가정인 P≠NP로 환원할 수 있는지도 제대로 알려지지 않았다.
- P≠NP 자체도 증명되지 않았다.
이러한 이유로 안전성 증명은 제대로 된 증명과 두 단계나 떨어져 있음을 알 수 있다. 오늘날 암호학이 이론적인 연구에서 그치는 것이 아니라 실제로 널리 사용되면서, 안전성 증명에 대한 관심이 증가하고 있다. 무한에 가까운 큰 값을 사용해서 증명하는 점근적인 증명보다는 작은 변숫값에 대한 안전성 증명을 더욱 중요하게 여기고 있으며, 이런 이유로 많은 사람이 안전성 증명을 위해 '정확한 안전성'(exact security)이나 '구체적 안전성'(concrete security)이라는 이름으로 더욱 의미 있는 것으로 생각하고 있다.[6]
각주
- ↑ 노태곤, 김헌오, 홍종철, 윤천주, 성건용, 정태형, 〈[양자암호통신기술]〉, 《전자통신동향분석제20권》, 2005-10
- ↑ 김정출, 〈암호화 개요〉, 《티스토리》, 2016-03-04
- ↑ z0ro, 〈[제1장 암호알고리즘 개요]〉, 《index-of》,
- ↑ 증명 가능한 안전성 네이버 지식백과 - https://terms.naver.com/entry.nhn?docId=3432504&cid=58445&categoryId=58445
- ↑ 김명환, 이인석, 백유진, 김우환, 강성우, 〈[안전성 증명 가능한 블록 암호 알고리즘 FRAC]〉, 《서울대학교 자연과학대학 수리과학부》
- ↑ 안전성 증명 위키백과 - https://ko.wikipedia.org/wiki/%EC%95%88%EC%A0%84%EC%84%B1_%EC%A6%9D%EB%AA%85
참고자료
- 안전성 증명 위키백과 - https://ko.wikipedia.org/wiki/%EC%95%88%EC%A0%84%EC%84%B1_%EC%A6%9D%EB%AA%85
- 증명 가능한 안전성 네이버 지식백과 - https://terms.naver.com/entry.nhn?docId=3432504&cid=58445&categoryId=58445
- 김명환, 이인석, 백유진, 김우환, 강성우, 〈[안전성 증명 가능한 블록 암호 알고리즘 FRAC]〉, 《서울대학교 자연과학대학 수리과학부》
- 노태곤, 김헌오, 홍종철, 윤천주, 성건용, 정태형, 〈[양자암호통신기술]〉, 《전자통신동향분석제20권》, 2005-10
- 김정출, 〈암호화 개요〉, 《티스토리》, 2016-03-04
같이 보기
