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