Even-Mansour 블록 암호 security는 2^(n/2) 증명

Even-Mansour 블록 암호란 $n$비트 스트링을 $n$비트 스트링으로 암호화하는 대칭키 암호 시스템이다.

 

어떤 퍼뮤테이션 $F : \{0, 1\}^n \rightarrow \{0, 1\}^n$이 고정되어 있고(이는 공개적으로 알려져 있다.), 키는 $n$비트 스트링 $K_1, K_2 \in \{0, 1\}^n$이다.

 

암호화 방식은 $M \in \{0, 1\}^n$ 평문을 받아서 $C = E_{K_1, K_2} (M) = K_2 \oplus F(K_1 \oplus M)$ 으로 구현한다.

 

$F$ 퍼뮤테이션의 역도 계산 가능하므로 복호화는 $M = K_1 \oplus F^{-1} (K_2 \oplus C)$ 로 쉽게 처리할 수 있다.

 

 

 

암호론 교수님께서 본 암호의 security가 $2^{n/2}$ 임을 증명하라고 숙제를 내주셨다.

 

못 풀어서 논문을 찾아보았다. Daemen(1991)에서 CPA-CCA 공격에 대한 증명을 했다.

 

간단하다. $E_K$를 계산해주는 $E$-오라클과, $F$ 퍼뮤테이션을 계산해주는 $F$-오라클이 있다고 하자. $\Delta M \in \{0, 1\}^n \setminus `000...0'$을 하나 임의로 골라서 다음을 만족하는 non-overlapping tuple을 많이 만들자.

• $M_i, M_i' \in \{0, 1\}^n$과 $C_i = E_K(M_i), C_i' = E_K(M_i')$의 순서쌍. (단 $M_i \oplus M_i' = \Delta M$)
• $A_j, A_j \in \{0, 1\}^n$과 $B_j = F(A_j), B_j' = F(A_j')$의 순서쌍. (단 $A_j \oplus A_j' = \Delta M$)

각각 $E$와 $F$ 오라클의 입출력 값을 모아놓은 것이다. 만일 $C_i \oplus C_i' = B_j \oplus B_j'$을 만족하는 $(i, j)$ pair를 찾을 수 있다면 높은 확률로 키를 추론할 수 있다. ($F$가 랜덤한 퍼뮤테이션이라면 $x \neq y$에 대해 $F(x) \oplus F(x \oplus \Delta M) = F(y) \oplus F(y \oplus \Delta M)$을 만족할 확률은 $1/{2^n}$ 밖에 되지 않기 때문이다.) 이런 경우를 collision이 발생하는 것이라고 정의하자.

 

$(M_i, M_i', C_i, C_i')$ 순서쌍의 개수를 $k$, $(A_j, A_j', B_j, B_j')$ 순서쌍의 개수를 $m$이라고 하자. Birthday attack이다. 필요한 튜플의 개수는 $O(2^{n/2})$개 이다. (??? 사실 이 부분은 잘 이해를 못했습니다)

 

그러므로 이 알고리즘을 통한 CPA-CCA 공격량의 기대값은 $2^{n/2}$ 이다.

 

 

 

-----------------------------------------------------------------------------------------------------------------------------

 

과연 이 방법이 최선일까? 더 좋은 방법은 없을까? 혹은 더 좋은 공격 방법이 없다는 것을 어떻게 증명할 수 있을까?

 

Even-Mansour(1993)의 논문이 흥미로워 블로그에 요약한다.

 

정리 numbering은 논문의 번호와 동일하게 진행한다.

 

 

 

-----------------------------------------------------------------------------------------------------------------------------

 

우선 $K_1, K_2$를 쌍으로 묶은 $2n$비트 키를 $K = \langle K_1, K_2 \rangle$라고 하자.

 

암호화 함수를 $E_K$, 복호화 함수를 $D_K$라고 한다.

 

CPA-CCA 방식을 모두 사용한 공격 방식을 채택한다.

 

목표는 어떤 한 암호문 $C_0 \in \{0, 1\}^n$의 복호화를 성공시키는 것이다. 즉, $E_K(M') = C_0$를 만족하는 $M'$을 찾는 것이다.

 

다음 4가지 오라클을 사용할 수 있다고 하자.

• $F$-오라클. $x \in  \{0, 1\}^n$에 대해, $F(x)$를 계산한다.
• $F^{-1}$-오라클. $x \in \{0, 1\}^n$에 대해, $F^{-1}(x)$를 계산한다.
• $E$-오라클. $M \in \{0, 1\}^n$에 대해, $E_K(M)$을 계산한다.
• ($C_0$-Restricted) $D$-오라클. $C \in \{0, 1\}^n \setminus \{C_0\}$에 대해, $D_K(C)$를 계산한다.

 

새로운 공격 방식을 정의한다.

 

EFP(existential forgery problem) 공격 방식이다. CPA-CCA와 마찬가지로 $E_K$, $D_K$에 대한 접근이 가능하지만, 이 쿼리로 밝혀지지 않은 순서쌍 $(M, C)$ s.t. $E_K(M) = C$를 찾는 것이다.

 

엄밀하게 정의하기 위해 사용하는 네 가지 오라클을 정의한다.

• $F$-오라클. $x \in  \{0, 1\}^n$에 대해, $F(x)$를 계산한다.
• $F^{-1}$-오라클. $x \in \{0, 1\}^n$에 대해, $F^{-1}(x)$를 계산한다.
• $E$-오라클. $M \in \{0, 1\}^n$에 대해, $E_K(M)$을 계산한다.
• $D$-오라클. $C \in \{0, 1\}^n \setminus \{C_0\}$에 대해, $D_K(C)$를 계산한다.

 

3, 4번 쿼리로 $E_K(M) = C$를 만족할 수 있는 순서쌍 $(M, C)$들을 많이 찾을 수 있다. 그렇게 찾아지지 않은 어떤 순서쌍 $(M', C')$을 찾으면 EFP 공격이 성공했다고 정의한다.

 

CPA-CCA와 둘 중 뭐가 더 어렵다고 얘기하기는 애매하다.. CPA-CCA는 주어진 암호문만 풀면 되는데 그 암호문이 하필 제일 어려운 것일수도 있고, EFP는 아무거나 풀면 되는데 차라리 풀어야하는 암호문 하나가 주어지는게 더 편할지도 모른다. 왜냐하면 3번 쿼리를 이용해서 $E_K(M) = C_0$를 만족하는지 질의해봄으로써 정답을 확신할 수 있기 때문이다.

 

 

자주 쓰는 CPA-CCA를 두고, 왜 EFP를 정의했는가. 바로 다음 정리에서 나온다.

 

Theorem 3.1. 만약 CPA-CCA를 $t(n)$의 복잡도로 $\epsilon(n)$ 이상 확률으로 공격 가능하다면, EFP를 $t(n)$의 복잡도로 $\epsilon(n) / t(n)$ 이상 확률로 공격 가능하다.

 

증명은 마치 말장난인 것 처럼 무지 간단하다. CPA-CCA 방식으로 공격하는데 적어도 한 번 이상 $E_K(M) = C_0$를 만족하는지 체크하는 $E$-오라클 사용이 존재한다고 가정할 수 있다. $E$-오라클을 사용하는 순간을 임의로 선택해서 $(M, C_0)$를 반환하게 하면 맞을 확률은 $1/t(n)$ 이상이다. 그래서 EFP 공격 성공확률은 $\epsilon(n) / t(n)$ 이상이다.

 

이 말장난같은 증명으로 다음 정리가 유도된다. 적어도 EFP보다는 CPA-CCA가 더 어렵다는 것이다. 풀어 적으면 다음과 같다.

 

Corollary 3.2. 다항시간 복잡도로 EFP 공격 성공 확률이 negligible하면, CPA-CCA 공격도 마찬가지로 가능하다.

 

한 마디로 EFP로 공격하는게 어려우면 CPA-CCA는 더 어렵다는 것이다.

 

(단, $E, F$-오라클같은 특수한 개념이 있는 이 암호 시스템에서만 적용 가능하고, 일반적으로 성립하는 사실은 아니라고 한다.)

 

 

 

-----------------------------------------------------------------------------------------------------------------------------

 

$E/D$ 오라클과 $F/F^{-1}$ 오라클 사용 결과를 저장하자. 전자를 $E$-pair라고 하고, 후자를 $F$-pair라고 한다.

 

몇 번의 오라클 사용 후 모인 $E$-pair 집합을 $S = \{(M_i, C_i)\}$, $F$-pair 집합을 $T = \{(A_j, B_j)\}$라고 하자. 또한, 이 오라클들을 효율적으로 써서 중복되는 원소가 없다고 가정하자.

 

 

이제 키가 good 한 것과 bad 한 것을 정의한다.

• $\exists (M_i, C_i) \in S, (A_j, B_j) \in T$ s.t. $M_i \oplus K_1 = A_j$이면 $K_1$은 bad 하다. 아니면 good 하다.
• $\exists (M_i, C_i) \in S, (A_j, B_j) \in T$ s.t. $C_i \oplus K_2 = B_j$이면 $K_2$은 bad 하다. 아니면 good 하다.

$l = |S|, m = |T|$라고 하면 bad한 $K_1$이나 $K_2$의 개수는 각각 $lm$개 이다.

 

만약 $K = (K_1, K_2)$가 가능한 키 이면, $K_1$ is good iff $K_2$ is good는 어렵지 않게 증명할 수 있다. 즉 $K$가 good 일 조건은 $K_1$과 $K_2$가 모두 good 한 것으로 정의한다.

 

전체적으로 보았을 때, good 키의 개수는 $2^{2n} - 2lm 2^n$개 이상이고, bad 키의 비율은 $2lm / 2^n$ 이하이다.

 

Good, bad 키를 정의한 이유는 간단하다. 실제 키가 $S$, $T$에 대해 bad 하다면 공격자는 몇 번의 추가 질의만으로 키를 간파할 수 있다. 앞으로의 증명은 대부분의 키는 사실 good 하고, 서로 구분할 수 없기 때문에 공격자가 오라클을 굉장히 많이 사용하지 않으면 성공하기 쉽지 않다는 식으로 진행된다.

 

 

이제 획득한 자료 $S, T$로 알 수 있는 공격자의 지식의 범위에 대해 정의한다.

 

어떤 퍼뮤테이션 $\pi$가 $(K, S, T)$ 확장이라는 것은, ($K = \langle K_1, K_2 \rangle$)

• $\forall (A_j, B_j) \in T$에 대해 $\pi (A_j) = B_j$를 만족하며,
• $\forall (M_i, C_i) \in S$에 대해 $\pi(M_i \oplus K_1) \oplus K_2 = C_i$를 만족할 때를 의미한다.

즉, 위 두 가지 특성을 만족하는 퍼뮤테이션의 집합을 확장이라고 정의한 것이다.

 

여기서 잠깐! 퍼뮤테이션 $F$는 고정되어있고 주어지는 것이라고 했는데 갑자기 왠 퍼뮤테이션?

--> 아무리 $F$가 주어진다고 해도 그것이 복잡하게 구성된다면, $F/F^{-1}$ 오라클을 충분히 많이 사용한 것이 아니라면 제대로 아는 것이라 단정할 수 없다. 공격량이라는 것은 복잡도(즉, 오라클의 사용 횟수)와 직접적으로 관련이 있으므로 '주어진 지식 범위 내에서 유추 가능한(consistent한) 퍼뮤테이션의 집합'을 정의하여 간주하는 것이 안전하다.

 

또한, 키와 퍼뮤테이션의 쌍 $(K, \pi)$가 consistent하다는 것은,

• $\forall (A_j, B_j) \in T$에 대해 $\pi (A_j) = B_j$를 만족하며,
• $\forall (M_i, C_i) \in S$에 대해 $\pi(M_i \oplus K_1) \oplus K_2 = C_i$를 만족할 때를 의미한다. (단 $K = (K_1, K_2)$)

즉 확장 퍼뮤테이션을 아무거나 잡아서 키랑 묶으면 consistent해진다.

 

 

Lemma 4.3. 키와 퍼뮤테이션의 분포가 uniform하다고 가정하자. $S, T$ 집합이 주어지고 그에 대한 good 키의 집합을 $\mathcal K$라고 하자. 임의의 $\kappa \in \mathcal K$에 대해, 다음 확률은 항상 동일하다.

$$ Pr_{K, F} [ K = \kappa \: :\: \text{$(K, F)$는 $S$, $T$에 대해 consistent 하다.} ] $$

 

증명은 생각보다 간단하다. 베이지안 정리를 이용하여 조건부 확률을 풀어 적으면 결국

$$ Pr_{K, F} [ \text{$(K, F)$는 $S$, $T$에 대해 consistent 하다.} \: :\: K = \kappa ] $$

임을 증명하는 것과 동치이다.

 

키가 주어지면 가능한 퍼뮤테이션 확장의 개수가 항상 일정함을 증명하면 되는데, $S = \{(M_i, C_i)\}$을 $S' = \{(M_i \oplus K_1, C_i \oplus K_2)\}$로 생각하면 $S' \cap T = \emptyset$이다.($\kappa$가 good 하기 때문이다.)

 

이게 결국 퍼뮤테이션의 입-출력을 모아놓은 튜플이다. $|S| + |T|$가 일정하다면 가능한 퍼뮤테이션 확장의 개수는 항상 일정하다.

 

 

 

-----------------------------------------------------------------------------------------------------------------------------

 

이제 메인 정리를 증명하자.

 

Theorem 4.4. $K$와 $F$가 uniformly random하게 주어졌다고 가정하자. 임의의 EFP 공격 알고리즘 $A$가 성공할 확률은

$$ O \left( \frac{lm}{2^n} \right) $$

이다. 단 $l, m$은 각각 $E/D$ 오라클 호출 횟수와 $F/F^{-1}$ 오라클 호출 횟수이다.

 

공격자가 추정 가능한 키와 퍼뮤테이션을 묶어 $L$으로 나타내겠다. 처음 $L_0 = (K, F)$라고 하자. 초기 $K, F$는 uniformly random하게 선택된다. 다음과 같은 동작을 반복한다.

 

$A$ 알고리즘에서의 $i$번 오라클 사용 직전 모아진 $E$-pair의 집합을 $S^{(i)}$, $F$-pair의 집합을 $T^{(i)}$라고 하자.

1. $K^{(i)} = (K_1^{(i)}, K_2^{(i)})$를 $S^{(i)}$와 $T^{(i)}$에 대해 good 하도록 uniformly random하게,
2. $F^{(i)}$를 $(K^{(i)}, S^{(i)}, T^{(i)})$ 확장 퍼뮤테이션의 원소가 되도록 uniformly random하게 선택한다.
3. 그 후 $L^{(i)} = (K^{(i)}, F^{(i)})$라고 묶어 정의한다.
4. 새로 오라클을 사용한 결과에 대해 여전히 직전 키 $K^{(i-1)}$이 good 하다면 다시 1번부터 반복한다.
5. $K^{(i-1)}$이 bad 해진다면 반복을 중단한다. 그리고 $A$ 알고리즘이 성공했다고 선언한다.

5번 과정에서 $A$ 알고리즘이 성공했다고 가정하는 이유는(실제로 성공하지 않았을 가능성이 크지만).. Adversary 측의 성공 확률을 굳이 높여줘도 $O(lm/2^n)$를 넘어가지 않음을 증명하면 되기 때문이다.

 

$i = l+m+1$번의 오라클 사용 직전 good 키의 개수는 최소 $2^{2n} - 2lm 2^n$개 이상이다. 임의로 고른 $K^{(i)}$가 $i$번째 오라클의 출력으로 인해 bad로 바뀔 확률은 얼마일까. $E/D$ 쿼리 $(M_i, C_i)$에 대해 bad일 확률은 최대

$$ \frac{2m 2^n}{2^{2n} - 2lm 2^n} = \frac{2m}{2^n - 2lm} $$

이고, $F/F^{-1}$ 쿼리 $(A_i, B_i)$에 대해 bad일 확률은 최대

$$ \frac{2l 2^n}{2^{2n} - 2lm 2^n} = \frac{2l}{2^n - 2lm} $$

이다. 최종적으로 $|S| = l$, $|T| = m$가 되었다고 가정하자. 그렇다면 위 반복에서 5번 과정에서 끝나는 확률은($K^{(i)}$가 bad해질 확률) 최대

$$ \frac{4lm}{2^n - 2lm} = O \left( \frac{lm}{2^n} \right) $$

이다.

 

 

이제 5번 과정으로 끝나지 않고 $A$ 알고리즘의 모든 오라클 호출에 대해 1-4번 과정만 반복했다고 가정하자.

 

$A$ 알고리즘이 최종적으로 반환한 $(M, C)$ 값을 고려한다. 마지막 추정 키 $K^{(l+m)}$가 $S^{(l+m)} \cup \{(M, C)\}$와 $T^{(l+m)}$에 대해 bad 할 확률은

$$ \frac{2m}{2^n - 2lm} = O \left( \frac{lm}{2^n} \right) $$

이다.

 

그렇지 않고 $K^{(l+m)}$이 good이라고 하면 $A$가 알아낸 정보만으로는 다른 모든 good 한 키들과 서로 구분 할 수 없는 상황이 된다.(Lemma 4.3.) 실제로 답을 맞출 확률은 good 키의 개수 분의 1이 된다. 왜냐하면 서로 다른 good 키에 대해 $M$을 암호화한 결과가 서로 다를 것이며, $C = E_K(M)$이 성립할 확률도 uniform하게 분포할 것이기 때문이다.

 

Good 키만 고려하자. $K_2^{(l+m)} \oplus F(K_1^{(l+m)} \oplus M)$으로 될 수 있는 값의 경우의 수는 $2^n - (m+l)$가지다. 그러므로 $A$ 알고리즘이 성공적으로 새로운 답 $(M, C)$를 추론 성공할 확률은($C = E_K(M)$일 확률)

$$ \frac{1}{2^n - m - l} = O \left( \frac{lm}{2^n} \right) $$

이다.

 

정리하면, [$K^{(i)}$가($i \leq l+m$) bad 일 확률] + [$A$ 알고리즘이 성공할 확률]이 $O(lm/2^n)$이 된다는 것이므로, $A$ 알고리즘이 EFP 공격을 성공할 확률도 $O(lm/2^n)$이 된다.

 

 

 

-----------------------------------------------------------------------------------------------------------------------------

 

그러므로 EFP 공격을 negligible하지 않게 성공시키기 위한 최소 오라클 호출 횟수는 $O(2^{n/2})$회 이다. 마찬가지로 CPA-CCA 공격도 그 이상이 필요하다.

 

 

정말 많은 것을 얻었던 논문이었다. 우선 Daemon(1991)에서 쓰이는 birthday paradox를 이용한 충돌 공격이 생각보다 암호 분석에서 많이 쓰인다는 것을 깨달았다. 수업 시간에 PA, CPA-CCA에 대해 대략적으로 배웠지만 엄밀하게 정의해본 적은 없었다. 생각보다 엄밀하게 정의하고 증명에서 용의하게 사용할 수 있음을 느꼈다. 또한 알고리즘의 lower bound를 구하는 방식이 신기했다. 오라클을 많이 사용해도 알 수 있는 정보량은 굉장히 적고, 수많은 다른 가능성으로부터 구분할 여지가 전혀 없음을 통해서 했다. Good 키라는 기준을 두고 분석하기 쉬운 상황에서만 분석하도록 증명을 유도하며, 그렇지 않은 상황이 발생할 확률도 줄여버림으로써 깔끔하게 분석하는 것이 신기했다. 이를 통해 확률 알고리즘의 분석 과정에 대한 아주 기초적인 가이드라인을 알게 된 것 같다.

 

 

 

참고문헌

 

[1] J. Daemen. (1991). Limitations of the Even-Mansour Construction. Proceedings of AisaCrypt.

[2] S. Even and Y. Mansour. (1993). A Construction of a Cipher from a Single Pseudorandom Permutation. Journal of Cryptology, 10, 151-161.