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