검수요청.png검수요청.png

안전성 증명

해시넷
이동: 둘러보기, 검색

안전성 증명(security proof)이란 암호학의 개념에서, 새로운 공격기술에 대한 안전성을 이론적으로 증명하는 것을 의미한다. 어떤 시스템이 공격자 모형을 이용하여 안전성의 조건을 명시하고, 환원이라고 하는 방식으로 널리 알려진 암호학적 성질이 안전하다는 가정하에 이와 같은 안전성의 조건이 만족한다는 것을 증명한다.

개요

양자암호 프로토콜과 관련된 이론 연구는 크게 두 가지 영역으로 나눌 수 있다. 하나는 새로운 양자 암호 프로토콜의 창안이고, 다른 하나는 기존의 또는 새로이 창안된 프로토콜의 안전성 증명에 대한 연구이다. 이 두 연구는 절대 별개의 것이 아니며, 새로운 프로토콜을 제안하는 경우에는 그 프로토콜의 안전성 증명이 병행되는 것이 보통이다. 그리고 안전성 증명은 크게 무조건 안전성과 실재적 안전성으로 나뉜다. 무조건 안전성은 도청자인 이브가 물리 법칙 내에서 앨리스와 이브, 두 사용자가 안전한 암호 키를 나누어 가질 수 있다는 것이다. 보통 이러한 무조건 안전성 증명은 수학적 정리의 형태를 띤다. 이와 달리 실재적 안전성의 증명은 더욱 실험적인 구현에 중점을 둔다. 앨리스와 밥이 양자암호통신을 구현하기 위하여 사용했던 장치들이 완벽하게 작동할 때 양자암호의 안전성을 증명하는 문제는 아주 간단하다. 반면, 그 장치들이 완벽하지 않을 때는 이브는 그를 이용해서 암호 키에 대한 정보를 얻을 수 있다. 그러나 이브가 키에 대해 가질 수 있는 정보량의 최댓값이 앨리스와 밥 사이의 상호정보량보다 적다면, 앨리스와 밥은 고전적인 오류보정과 비밀 증폭을 통해서 안전한 비밀 키를 생성할 수 있다. 2000년에는 모든 광원과 광검출기의 결점을 이브의 기저에 무관한 공격에 포함된다고 가정하여 안전성을 증명한 연구가 발표되기도 했다. 이 증명은 흔히 Shor-Preskill 증명으로 알려져 있다. 2003년의 Koashi-Preskill 증명은 광검출기가 완전하다고 가정하고 광원이 앨리스의 기저 정보를 이브에게 흘려주진 않았지만 완전하지는 않다는 가정을 한다. 2004년에는 지금까지의 증명 중 실재 양자암호 시스템과 가장 유사하도록 광원과 광검출기가 모두 기저에 대한 정보의 일부를 이브에게 유출할 경우에 대한 안전성을 증명했다.

실재적인 양자암호 시스템에서는 특정한 양자암호 프로토콜을 제안하거나 실재적 안전성을 증명하려 할 때, 도청자가 행동할 수 있는 도청 방법을 하나 상정해놓고 그 도청 방법에 대해 안전함을 보인다. 도청자가 시도할 수 있는 도청 방법은 크게 두 가지로 나눌 수 있는데, 한 번에 하나의 큐빗에 대해서만 접근을 시도하는 개별 공격법과 몇 개의 큐빗에 한꺼번에 접근해서 정보를 얻어내는 통합 공격법이 있다.[1]

암호 알고리즘의 안전성

암호 알고리즘의 안전성은 다음과 같다.

  • 무조건적 안전성: 절대적 안전성이라고도 한다. 무한한 컴퓨터 자원을 가져도 암호 알고리즘을 해독할 수 없는 경우를 의미한다. 공격자가 무한한 계산 능력을 갖췄다고 하더라도 암호문으로부터 평문에 대한 그 어떤 정보도 얻을 수 없으며, 암호문을 수신하기 전에 평문에 대한 사전 정보량과 암호문을 수신한 후 정보량이 같을 때 무조건 안전성을 만족한다. 무조건 안전성의 예로 일회용 패드를 들 수 있다.
  • 계산적 안전성 : 암호 알고리즘을 해독하기 위한 지금까지 알려진 가장 우수한 공격 방법을 사용하더라도 불합리하게 많은 컴퓨터 시간을 요구할 경우 공격 방법의 기준이 된다. 원리적으로 해독이 가능하지만 해독에 필요한 계산량이 많아서 실제로는 해독이 불가능한 상황이며, 정당한 수신자의 복호화 시간과 비밀정보를 모르는 공격자의 복호화 시간의 상대적 차이를 이용한 안전성이다.
  • 증명 가능 안전성: 인수분해 문제와 같이 어렵다고 알려진 문제와 비교하여 판단한다. 안전성에 대한 절대적인 증명은 아니다. 어렵다고 알려진 문제와 등가일 경우를 의미한다.
  • 의미론적 안전성: 암호문이 주어졌을 때 효율적으로 계산할 수 있는 모든 것을 암호문이 없어도 계산할 수 있어야 한다. 다항식 계산 능력을 갖춘 공격자는 암호문으로부터 평문에 대한 어떤 정보도 얻을 수 없다.
  • 구별 불가 안전성: 두 개의 메시지 중에서 하나를 암호화한 암호문이 주어졌을 때, 공격자가 어떤 평문을 암호화한 것인지 맞힐 수 있는 확률이 50%보다 높지 않아야 한다.
  • NM 특성: 암호문에 대응되는 평문을 알지 못하는 경우, 이 암호문을 의미 있는 다른 암호문을 변경하는 것이 불가능하다면 암호 알고리즘은 NM 특성을 제공하는 것이다. NM 특성은 의미론적 안전성보다 강한 특성이다.[2]

암호 알고리즘의 안전성은 해독하는 데 필요한 노력으로 측정된다. 보통 대칭 암호 알고리즘의 경우에는 전사 공격을 통해 암호를 해독할 수 있다. 즉, 현재 실제로 사용되고 있는 암호 알고리즘들은 무조건 안전한 것이 아니다. 알고리즘이 절대적으로 안전하다는 것은 무한한 컴퓨팅 자원이 있어도 공격을 성공적으로 진행할 수 없다는 뜻이다. 전사 공격을 통해 해독을 할 수 있더라도 거기에 드는 시간이나 컴퓨팅 능력에는 현실성이 없기 때문에 실제로 사용하는 데 전혀 문제가 없다. 이처럼 어떠한 암호 알고리즘을 지금까지 알려진 가장 우수한 공격 방법으로 공격해서 성공하는데 소요되는 시간이 너무 방대한 시간과 컴퓨팅 능력을 요구하는 경우, 이 알고리즘은 계산적으로 안전하다고 부른다. 공개키 암호 알고리즘도 대칭 암호 알고리즘과 마찬가지로 전사 공격 측면에서는 계산적으로 안전하다. 그러나 이들은 대체로 어렵다고 알려진 수학 문제들에 의존하기 때문에 전사 공격을 하는 것보다는 이러한 수학 문제를 푸는 편이 더 빠르다. 하지만 공개키 암호 알고리즘에 사용되는 수학 문제를 푸는 것 자체가 난이도가 상당히 어렵다고 알려져 있다. 다시 말하자면, 의존하는 수학 문제를 절대 풀 수 없다고 따로 증명된 것은 아니지만 지금까지 알려진 어떤 방법을 사용하더라도 불합리하게 많은 시간과 비용을 부담해야 한다. 이처럼 알고리즘의 안전성이 어렵다고 알려진 다른 문제와 등가일 경우, 이 알고리즘은 증명 가능한 안전성을 가지고 있다고 부른다.[3]

개념

현대 암호학의 기본적인 원리 세 가지는 다음과 같다.

  1. 어떤 암호학적 문제를 해결하기 위한 첫 번째 단계는 안전성에 대한 엄격하고 정확한 정의를 생성하는 것이다.
  2. 암호학적 구조의 안전성이 증명되지 않은 가정에 의존할 때, 이 가정이 반드시 명시되어야 한다. 그리고, 이 가정은 가능한 최소화되어야 한다.
  3. 암호학적 구조는 위 1번의 정의에 대해서 안전성 증명이 명확히 되어야 한다. 그리고, 2번 원리에 따라 관련된 가정을 명시해야 한다.

특히 1번 원리는 안전한 암호 설계를 위한 목표를 제시하고, 다양한 응용 환경에서 어떤 암호 기법이 적합한지 선택지를 제시한다. 또, 주어진 암호기법에 대한 비교 분석을 진행할 수 있으며, 3번 원리는 안전성 증명 개념에 해당한다.

  • 환원 접근법: 가정 X가 참인 경우, 시공 Y는 주어진 정의에 따라 안전하다.
  • 명제(A AND B → C): 위조를 할 수 없는 고정길이 메시지 서명과 충돌 저항성을 가진 해시함수가 존재하면 위조할 수 없는 가변 길이 메시지 서명 또한 존재한다.
  • 대우명제: 가변길이메시지 서명을 위조하면 고정길이 메시지 서명을 위조하거나 해시함수의 충돌 쌍을 찾을 수 있다.

증명 가능한 안전성

암호 알고리즘의 안전성을 평가하는 전통적인 방법은 공격자로부터 공격을 받았을 때 그 공격을 얼마나 오래 버티고 견디고 살아남을 수 있는가에 달려있다. 즉 공격자에게 취약점이 발견되고 처음에 설계했던 기분보다 암호를 더 빠르게 해독한다면 그 알고리즘은 안전하지 않은 것으로 판단하고 폐기한다. 반면에 오랜 시간 동안 효율적인 공격 방법이 발견되지 않으면 안전한 알고리즘으로 평가받아왔다. 그러나 이러한 방식은 체계적인 평가 방법이라고 볼 수 없으며, 암호학자들 안전성을 어떻게 수학적으로 증명하는지에 관해 관심을 가지고 접근한다. 이것이 바로 증명 가능한 안전성이다. 제시된 암호 알고리즘이 정확히 어떤 목표를 가졌는지 상세하게 정의하고, 공격자에게 어디까지 허용할 것인지 정의한 뒤에, 이러한 환경에서 제시된 암호 알고리즘이 안전한가에 대해 수학적으로 접근하고 증명한다. 공격자에게 최대한 많은 능력을 부여해도 암호 알고리즘의 보안 목표가 안전하게 잘 지켜질 수 있다는 것을 보여주기 위함이다. 공격자에게 능력을 제공하는 모델로는 오라클이라는 개념을 사용한다. 예를 들어 공개키 암호 알고리즘의 안전성을 분석하기 위하여 질의자와 공격자 간의 다음과 같은 게임을 생각해본다. 공격자는 공개키와 쌍이 되는 개인 키가 없지만, 어떤 암호문에 대해서도 그걸 복호화해서 평문을 출력해주는 복호화 오라클에 접근할 수 있는 권한을 갖고 있다.

오라클을 이용하는 공격자와 질의자 사이의 게임

  1. 먼저 공격자는 복호화 오라클을 마음대로 시험해 볼 수 있다. 어떤 암호문이라도 복호화 오라클에 질의를 하면 그에 해당하는 평문을 얻어 볼 수 있다.
  2. 다음 단계로 공격자는 같은 길이의 두 개의 메시지 M1과 M2를 선택해서 질의자에게 제시한다.
  3. 질의자는 그중 임의로 하나를 골라서 공개키로 암호화하여 암호문을 만들고 공격자에게 제시한다. 두 메시지 중에서 어떤 것을 선택했는가는 공격자에게 밝히지 않는다.
  4. 공격자는 복호화 오라클에 암호문을 질의할 수 있는데, 여기서 조건은 위의 단계에서 질의자가 제시했던 암호문만은 질의할 수 없다는 것이다.
  5. 최종적으로 질의자가 어떤 메시지를 골랐는가에 대해 공격자가 맞춘다면 공격자는 게임에서 이긴다.

위 게임의 공격자는 자신이 복호화 오라클에 질의할 수 있다는 사실을 알고 있고, 따라서 게임에서 이기기 위해 자신에게 가장 유리한 전략대로 질문할 것이다. 공격자는 여러 차례 질문을 던지면서 얻은 경험을 토대로 다음번에는 좀 더 유리한 질의를 만들 수 있다. 이러한 공격을 바로 적응적 선택 암호문 공격이라고 한다. 만약 암호 알고리즘이 안전하다면 이런 게임에서 공격자가 암호문에서 평문이 둘 중 어느 것인지 구분할 수 없어야 한다. 이러한 안전성의 개념을 구별 불가능성(indistinguishability)이라고 한다. 공격자에게 질의 된 암호문을 직접 해독할 수 있는 능력을 제외한 가능한 한 많은 능력을 제공하더라도, 공격자가 두 메시지 중 어느 것이 암호화됐는지 구별할 수 없다면 해당 알고리즘은 공개키 암호 알고리즘으로서 아주 안전한 알고리즘이라고 평가할 수 있다. 이러한 증명 가능한 안전성 개념은 안전한 암호 알고리즘을 설계하기 위해서 필수적인 안전성 평가 방식에 해당한다.[4]

적용

블록 암호

블록 암호는 암호학 용어로, 기밀성 있는 정보를 정해진 블록 단위로 암호화하는 대칭키 암호 시스템이다. 만약 암호화하려는 정보가 블록의 길이보다 길다면, EDB, CBC, OFB, CFB, CTR과 같은 특정한 운용 모드가 사용된다. 블록 암호 알고리즘은 고전된 크기의 키를 사용하여 고정된 크기의 블록 단위로 암호화 복호화 연산을 수행하며, 암호화 키와 복호화 키가 같은 알고리즘을 말한다. 블록 암호에 대한 안전성 증명 방법으로는 선택 평문 공격인 차분 공격과 알려진 평문 공격인 선형공격 등이 있다.

  • 차분 공격(differential cryptanalysis)
차분 분석법의 차분 특성은 블록 암호 알고리즘을 공격하는데 사용되는 편이다. 즉, 확률이 충분히 큰 차분 특성이 존재한다고 할 때, 차분 분석법을 사용하여 몇 비트의 비밀키 정보를 복구할 수 있다. 한편, Lai, 매시, 머피는 그 역이 성립되지 않는다는 점을 알리고 차분 공격에 대한 강도를 반영하는 척도로써 차분 특성을 대신하여 차분(differential)을 제안했다. 차분은 차분 특성들의 집합이다. 어떤 암호의 최대 차분 특성 확률이 낮다고 해서 그 암호가 차분 분석에 대해 안전하다고 할 수는 없으나, 최대 차분 확률이 아주 낮으면 그 알고리즘은 일반적인 차분 분석에 안전함이 알려져 있다. 또, 니버그, 크누센은 처음으로 최대 차분 확률이 충분히 낮은 블록 암호 알고리즘의 예를 제시했으며, 이러한 성질을 증명 가능한 안전성이라고 부른다.[5] 차분 공격은 입력값의 변화에 따른 출력값의 변화를 이용하는데, 일반적으로 선택 평문 공격을 가정하며, 일반적인 차분공격 과정은 다음과 같다.
비트 평문 및 그 평문과 비슷한 다른 평문 을 준비하고, 이들의 XOR 차이를 라고 가정한다. 그리고 를 각각 암호화한 결과를 라고 정의해서 이들의 XOR 차이를 로 둔다. 이상적인 경우에는 어떤 에 대해 특정 가 나타날 확률은 이다. 그러나 암호에 취약점이 존재한다면 이 확률은 더 크게 나타날 수 있다. 이때 를 차분이라고 부른다. 차분 공격은 이러한 차분 쌍을 찾아내는 것을 목표로 삼는다. 차분 쌍을 이용하여 블록 암호의 키를 찾는 공격을 할 수도 있다. 블록 암호가 대입-치환 네트워크 구조일 때, 마지막 라운드를 제외한 나머지 과정에서 차분 현상이 일어나면 마지막 라운드에 입력되는 값의 차이를 일정 확률로 알 수 있다. 이는 출력값의 차이를 관측할 수 있어서 마지막 라운드에 더해지는 키의 일부로 알 수 있기 때문이다.
차분 공격은 앨리 바이햄아디 샤미르가 1980년대 후반에 발견한 방법이다. 이들은 차분 공격 외에도 여러 블록 암호와 암호학적 해시 함수의 취약성을 발표했으며, DES의 취약성을 연구하면서 DES가 차분 공격에 강하게 설계되었다는 사실을 발견하기도 했다. 그후 1994년, IBM의 DES팀에 있던 돈 포커스미스가 1974년에 IBM이 차분 공격을 발견했고, IBM 내부에서는 이를 'T-attack'이라고 불렀다는 사실과 DES의 설계 목적 중 하나가 이에 문제가 없게 하기 위함이었음을 알렸다.[6]
  • 선형 공격(linear cryptanalysis)
암호공격의 한 방법으로, 암호화 과정에서의 근사적인 선형 관계식을 찾는 것이 목적이다. 마쓰이 미쓰루의 논문에서 처음 공개되었다. 해당 논문에서는 선형 공격으로 FEAL 암호를 공격하는 방법을 제시했다. 선형 분석도 차분 분석과 함께 블록 암호를 공격하는데 널리 응용되는 방법으로, 차분 분석과 마찬가지로 처음에는 선형 분석의 특성을 이용한다. 그러나 최소 선형집합(linear hull)이라고 불리는 특성 집합이 소개되면서, 선형 분석에 대한 강도의 엄밀한 척도로 여겨졌다. 위의 차분 분석에서 언급한 최대 차분 확률이 충분히 낮은 블록 암호 알고리즘의 예는 최소 선형집합이 작아서 선형 분석에 대해서도 증명 가능한 안전성을 지닌다. 하지만 계산의 효율성은 별로 좋지 않다는 단점이 있다.[5]
공격 방법을 수식으로 표현하자면 다음과 같다. 선형 공격은 먼저 암호화 과정에서의 근사적인 선형 관계성을 찾는데, 어떤 암호화 함수가 입력값 를 받아 암호화된 출력값 을 반환한다고 할 때 다음과 같은 형태의 관계식들이 어떤 확률로 성립되는지를 관측한다.

이상적인 암호화 함수는 이 확률이 이어야 하지만, 암호화 방법에 따라서 이 확률이 과 크게 다를 수도 있다. 이러한 선형 관계식을 찾는 방법은 암호화 과정에 따라 다르다. 대입-혼합 네트워크의 경우에는 혼합 과정이 선형적이고, S-박스의 대입 과정에서만 비선형적인 변환이 일어난다. 따라서 S-박스의 연산을 선형 과정으로 근사화할 방법을 찾는 것이 목표이다. 근사 선형 관계성을 찾았다면 이를 통해 선택 평문 공격을 수행할 수 있다. 암호화 모듈에 임의의 입력값을 입력할 수 있을 때, 관계식에서 입력값 부분과 출력값 부분이 얼마나 일치하는가에 대한 횟수를 측정한다. 이 횟수를 기반으로 암호화 키 비트들에 대한 관계식을 확률적으로 추측 할 수 있다.[7]

한계

엄연히 말하면 안전성 증명은 증명이라고 볼 수 없다. 증명 과정이 겨우 '증명되지 않은' 가설로 환원하는 정도이거나, 랜덤 오라클 모델처럼 존재하지 않는 가상의 이론적인 모형을 사용하기 때문이다. 이론 전산학적인 관점에서 본다면, 안전성을 증명하는 데는 다음과 같은 두 가지 문제점이 있다.

  1. 대부분의 암호학적 성질이 계산 복잡도 이론의 기본적인 가정인 P≠NP로 환원할 수 있는지도 제대로 알려지지 않았다.
  2. P≠NP 자체도 증명되지 않았다.

이러한 이유로 안전성 증명은 제대로 된 증명과 두 단계나 떨어져 있음을 알 수 있다. 오늘날 암호학이 이론적인 연구에서 그치는 것이 아니라 실제로 널리 사용되면서, 안전성 증명에 대한 관심이 증가하고 있다. 무한에 가까운 큰 값을 사용해서 증명하는 점근적인 증명보다는 작은 변숫값에 대한 안전성 증명을 더욱 중요하게 여기고 있으며, 이런 이유로 많은 사람이 안전성 증명을 위해 '정확한 안전성'(exact security)이나 '구체적 안전성'(concrete security)이라는 이름으로 더욱 의미 있는 것으로 생각하고 있다.[8]

각주

  1. 노태곤, 김헌오, 홍종철, 윤천주, 성건용, 정태형, 〈[양자암호통신기술]〉, 《전자통신동향분석제20권》, 2005-10
  2. 김정출, 〈암호화 개요〉, 《티스토리》, 2016-03-04
  3. z0ro, 〈[제1장 암호알고리즘 개요]〉, 《index-of》,
  4. 증명 가능한 안전성 네이버 지식백과 - https://terms.naver.com/entry.nhn?docId=3432504&cid=58445&categoryId=58445
  5. 5.0 5.1 김명환, 이인석, 백유진, 김우환, 강성우, 〈[안전성 증명 가능한 블록 암호 알고리즘 FRAC]〉, 《서울대학교 자연과학대학 수리과학부》
  6. 차분 공격 위키백과 - https://ko.wikipedia.org/wiki/%EC%B0%A8%EB%B6%84_%EA%B3%B5%EA%B2%A9
  7. 선형 공격 위키백과 - https://ko.wikipedia.org/wiki/%EC%84%A0%ED%98%95_%EA%B3%B5%EA%B2%A9
  8. 안전성 증명 위키백과 - https://ko.wikipedia.org/wiki/%EC%95%88%EC%A0%84%EC%84%B1_%EC%A6%9D%EB%AA%85

참고자료

같이 보기


  검수요청.png검수요청.png 이 안전성 증명 문서는 암호 알고리즘에 관한 글로서 검토가 필요합니다. 위키 문서는 누구든지 자유롭게 편집할 수 있습니다. [편집]을 눌러 문서 내용을 검토·수정해 주세요.