암호론 논문 리딩 #2: Even-Mansour Scheme

논문을 읽어가면서 블로그 포스팅을 쓰는거라, 꽤 부족한 점이 많을 것 같다. 많은 지적과 보완은 환영이다.

"Minimalism in Cryptography: The Even-Mansour Scheme Revisited" - Orr Dunkelman, Nathan Keller, Adi Shamir

#1: Introduction

논문의 제목이 보여주듯이, 이 논문의 주제 Even-Mansour Scheme은 가장 단순한 암호화 방법을 고안하는 과정에서 등장한 개념이다. 특히, Even-Mansour Scheme은 가장 단순하고 안전한 블록암호를 고안하는 과정에서 등장했다. 이 논문에서는 Even-Mansour Scheme에 대한 기본적인 내용과 함께, 그의 변형에 대한 공격과 보안성에 대해서 다룬다. 여기서 제시한 공격이 다른 곳에서도 꽤 잘 먹히는듯 하다. 자세한 내용은 후술한다.

#2: The Even-Mansour Scheme

먼저 Even-Mansour Scheme을 정의하고, 기본적인 보안성에 대한 증명과 공격에 대한 내용을 다루어보자.

$n$-bit string에 대한 공개된 permutation $\mathcal{F}$ 하나를 잡는다. 또한, $n$-bit whitening key $K_1, K_2$를 비밀키로 하자. 

이제 $EM_{K_1, K_2}^{\mathcal{F}} (P) = \mathcal{F}(P \oplus K_1) \oplus K_2$로 정의한다. 정말 간단한 암호화 과정이다.

우리가 가정하는 adversary는 다음 두 쿼리를 (다른 말로는, oracle을) 활용해서 공격을 할 수 있다.

adversary는 $E(P) = EM_{K_1, K_2}^{\mathcal{F}} (P)$를 계산할 수 있고, $D(C) = (EM_{K_1, K_2}^{\mathcal{F}})^{-1} (C)$를 계산할 수 있다. 이를 $E$-oracle이라고 한다.

또한, 우리의 adversary는 $\mathcal{F}$-oracle을 불러서, $\mathcal{F}(x)$와 $\mathcal{F}^{-1} (y)$를 계산할 수 있다.

즉, plaintext의 암호화 결과, ciphertext의 복호화 결과를 oracle을 통해서 알 수 있고, $\mathcal{F}$를 이용한 연산도 할 수 있다.

adversary의 목표로 가능한 것은 크게 두 가지로 나뉜다. 첫 번째는 "existential forgery attack"이란 것으로, adversary가 $E(P)=C$가 성립하는 새로운 순서쌍 $(P, C)$를 찾는 것이다. 두 번째는 조금 더 전형적인, 암호화된 메세지 $C$가 주어졌을 때 $E(P)=C$가 성립하는 $P$를 찾는 것이다. 공격의 복잡도는 $E$-oracle의 횟수와 그 종류와 (즉, known/chosen/adaptive chosen) $\mathcal{F}$-oracle의 횟수로 결정된다. $\mathcal{F}$ 자체는 알려져 있지만, $\mathcal{F}$-oracle을 지나치게 많이 활용하면 시간상 문제가 있을 것이다. $E$-oracle은 실제로 뚫어서 얻어내야 하는 것이니, 이 역시 지나치게 많이 쓰기에는 어려움이 있을 것이다. 그러니, 두 oracle의 활용 횟수를 모두 고려하도록 한다. 공격의 성공 확률이란, (첫 번째 경우) 한 번의 시도를 통해서 새로운 $(P, C)$ 순서쌍을 찾거나, (두 번째 경우) $E(P)=C$인 $P$를 찾을 확률으로 정의한다. 이제 본격적으로 보안성과 공격 방식에 대해서 논의할 수 있겠다.

adversary가 $D$번 $E$-oracle을 사용하고, $T$번 $\mathcal{F}$-oracle을 사용했다고 하자. 여기서 $D$는 data의 약자이고, $T$는 time의 약자인 것 같다. 왜 이런 약자를 사용하는지는 꽤 당연한 것 같다. 중요한 사실은, adversary의 성공 확률이 $\mathcal{O}(DT/2^n)$이라는 것이다. 그러니, 기본적으로 공격을 하려면 $DT$가 $\Omega (2^n)$ 정도는 되어야 한다. 여기서 oracle의 총 사용 횟수가 $\Omega(2^{n/2})$ 정도는 되어야 함도 알 수 있다. 증명의 outline을 살펴보자. 

$E$-oracle을 $s$번, $\mathcal{F}$-oracle을 $t$번 활용하면 얻는 것은 $E$-pair와 $\mathcal{F}$-pair의 집합 $S = \{ (P_i, C_i) \}_{i=1,2, \cdots s}$와 $T = \{(X_j, Y_j)\}_{j=1,2, \cdots ,t}$다. 

이제 $K_1$이 $S, T$에 대하여 나쁘다는 것은, $i, j$가 존재하여 $P_i \oplus K_1 = X_j$가 성립한다는 것이다. 그렇지 않다면, $K_1$은 좋다고 하겠다. 비슷하게, $K_2$가 $S, T$에 대하여 나쁘다는 것은, $i, j$가 존재하여 $Y_j \oplus K_2 = C_i$가 성립한다는 것이다. 그렇지 않다면 $K_2$는 좋다고 하겠다. 또한, $K_1, K_2$가 둘 다 좋다면 $(K_1, K_2)$를 $S, T$에 대하여 좋은 쌍이라고 하겠다. 좋은 쌍의 개수는 적어도 $(2^n-st)^2$ 이상이니, $2^{2n} - 2st \cdot 2^n$만큼은 있다. 또한, $(K, \mathcal{F})$가 (물론, $K = (K_1, K_2)$다) $S, T$와 consistent 하다는 것은, $C_i = K_2 \oplus \mathcal{F}(P_i \oplus K_1)$과 $\mathcal{F}(X_j) = Y_j$이 모든 $i, j$에 대하여 성립한다는 것이다. 

Step 1: 비밀키와 permutation에 대한 모든 분포가 uniform하다고 가정했을 때, $(K, \mathcal{F})$가 $S, T$와 consistent하다는 가정에서 $K=k$가 성립할 조건부확률이 모든 $S, T$에 대해 좋은 키 $k \in \{0, 1\}^{2n}$에 대하여 같다는 것을 보인다. 베이즈 정리에서, 이는 $K=k$일 때 $(K, \mathcal{F})$가 $S, T$와 consistent 할 확률이 모든 좋은 키 $k \in \{0, 1\}^{2n}$에 대하여 같음을 보이면 충분하다. $k=(k_1, k_2)$가 좋은 키라고 가정하자. $k$를 고정하고 생각을 하면, $E$-pair의 집합 $S$를 $\mathcal{F}$-pair의 집합 $S'$으로 바꿀 수 있다. $(P_i, C_i)$를 $(P_i \oplus k_1, C_i \oplus k_2)$로 바꿔주면 된다. 또한, $k$가 좋은 키이므로 $S'$과 $T$는 아예 겹치지 않는다. 그러니 consistent 할 확률은 결국 $\mathcal{F}$가 서로 다른 $s+t$개의 pair와 consistent 한 것과 동치이다. 이는 $k$와 무관함이 자명하다. 증명 끝.

Step 2: 성공 확률은 정답에 해당하는 키가 나쁜 키가 되어있을 확률과 정답에 해당하는 키가 좋은 키인 상황에서 adversary가 답을 얻어내는데 성공할 확률의 합 이하임을 증명한다. 이걸 열심히 계산하고 식을 정리하면, 우리가 원하는 결과를 얻을 수 있다고 한다. 논문에서는 뒤에 관련 논의가 사용되지 않는다는 이유로 자세한 설명을 생략했다. Step 2의 내용은 Even-Mansour를 제시한 오리지널 논문에 있다. 이는 나중에 정리해서 올리도록 노력해보겠다.

이 증명을 통해서, 키에 대한 non-trivial information을 얻는 것 역시 $DT = \Omega (2^n)$을 필요로 함을 알 수 있다.

증명 자체가 "좋은 키는 그냥 adversary가 보기엔 다 똑같다"라는 느낌이 강하니까, 직관적으로도 잘 이해되는 부분이다.

이전에 제시된 Even-Mansour에 대한 attack이 간략하게 설명되어 있는데, 간략하게 설명되어 있어서 그런지 이해하기가 조금 어려운 것 같다. 

이 논문에 제시된 공격들이 더욱 강력하므로, 그 공격들만을 우선 읽어보고 다시 돌아와야 할 것 같다.

#3: The Slidex Attack and a Tight Bound on the Security of the Even-Mansour Scheme

우선 기존에 알려진 공격 방법인 Slide with a Twist Attack을 살펴보자. 

만약 두 plaintext $P, P^*$가 $P \oplus P^* = K_1$을 만족한다고 하자. 이제 이를 암호화하면 어떻게 될까?

$E(P) = \mathcal{F}(P \oplus K_1) \oplus K_2 = \mathcal{F}(P^*) \oplus K_2$고, 마찬가지로 $E(P^*) = \mathcal{F}(P) \oplus K_2$가 성립한다.

그러니 결론적으로 $E(P) \oplus \mathcal{F}(P) = E(P^*) \oplus \mathcal{F}(P^*)$를 얻는다. 이제 공격을 설계해보자.

adversary가 이미 알고 있는 plaintext/ciphertext 순서쌍 $(P_i, E(P_i))$을 총 $2^{(n+1)/2}$개 들고 있다고 하자. 

즉, $E$-oracle을 "known" 형태로 이용한다. 이제 $\mathcal{F}$-oracle을 $2^{(n+1)/2}$번 사용하여, $\mathcal{F}(P_i)$를 얻는다. 

커다란 배열을 하나 준비하고, $(E(P_i) \oplus \mathcal{F}(P_i), i)$를 정렬된 형태로 저장한다. 

이제 $E(P_i) \oplus \mathcal{F}(P_i) = E(P_j) \oplus \mathcal{F}(P_j)$인 $i, j$를 효율적으로 찾을 수 있다.

이제, $K_1 = P_i \oplus P_j$, $K_2 = E(P_i) \oplus \mathcal{F}(P_j)$를 계산하고 이를 실제 키로 추측한다.

birthday paradox의 입장으로 생각하면, $P_i \oplus P_j = K_1$이 성립하는 $i, j$가 존재할 확률은 꽤 높다.

또한, 실제로 collision이 일어나는 순서쌍의 개수는 평균적으로 크지 않을 것이라는 점도 직관적으로 이해할 수 있다.

이 공격에서 $D = T = 2^{(n+1)/2}$이고, $DT = 2^{n+1}$이다. 여기서 $DT = \Omega (2^n)$임도 확인할 수 있다.

Slidex Attack은 위 과정을 일부분 변형해서 생각한다. 두 plaintext $P, P^*$가 $P \oplus P^* = K_1 \oplus \Delta$를 만족한다 하자.

이 경우, 식을 전개해보면 $E(P) = \mathcal{F}(P^* \oplus \Delta) \oplus K_2$와 $E(P^*) = \mathcal{F}(P \oplus \Delta) \oplus K_2$를 얻는다.

즉, $E(P) \oplus \mathcal{F}(P \oplus \Delta) = E(P^*) \oplus \mathcal{F}(P^* \oplus \Delta)$를 얻는다.

이제 $d \le n$을 하나 잡고, 다음과 같은 공격을 시도할 수 있겠다.

먼저 이미 알고 있는 plaintext/ciphertext 순서쌍 $(P_i, E(P_i))$를 $2^{(d+1)/2}$개 들고 있다고 하자.

즉, $E$-oracle을 "known" 형태로 이용한다. 이제 $\Delta_1, \Delta_2, \cdots $를 총 $2^{n-d}$개 준비한다.

각 $\Delta_l$에 대하여, $\mathcal{F}$-oracle을 이용하여 $\mathcal{F}(P_i \oplus \Delta_l)$을 각 $i = 1, 2, \cdots , 2^{(d+1)/2}$에 대해 계산한다.

커다란 배열을 하나 준비하고, $(E(P_i) \oplus \mathcal{F}(P_i \oplus \Delta_l) , i)$를 정렬된 형태로 저장한다. 배열은 총 $2^{n-d}$개 있을 것이다. 이 중 아무 곳에서나 collision이 일어나면, 즉 $E(P_i) \oplus F(P_i \oplus \Delta_l) = E(P_j) \oplus F(P_j \oplus \Delta_l)$이면, $K_1 = P_i \oplus P_j \oplus \Delta_l$, $K_2 = E(P_i) \oplus F(P_j \oplus \Delta_l)$을 실제 키로 추측한다.

비슷하게, $P_i \oplus P_j \oplus \Delta_l = K_1$인 $i, j, l$이 있을 확률은 꽤 높다. 

또한, 실제로 collision이 일어나는 순서쌍의 개수는 평균적으로 크지 않을 것이라는 점도 직관적으로 이해할 수 있다.

이 공격에서 $D = 2^{(d+1)/2}$이고, $T = 2^{(d+1)/2} \cdot 2^{n-d}$이다. 그러니 여기서도 $DT = 2^{n+1}$이다.

이 새로운 공격의 장점은 역시 $d \le n$을 마음대로 선택할 수 있다는 점이 되겠다. 

#4: The New Single-Key Even-Mansour Scheme

이제 Even-Mansour Scheme의 변형에 대해서 다룬다. 지금까지는 비밀키가 $K_1, K_2$ 두 개가 있었다. 비밀키를 두 개 사용하지 말고, 그냥 하나의 비밀키를 두 번 사용하면 어떨까? 이 생각으로 등장한게 Single-Key Even-Mansour Scheme이다.

$\mathcal{F}$는 $n$-bit string에 대한 공개된 permutation이고, $K$는 $n$-bit 비밀키다.

이때, $SEM_{K}^{\mathcal{F}} (P) = \mathcal{F}(P \oplus K) \oplus K$라 하자. $K_1 = K_2 = K$라고 보면 되겠다.

공격에 대한 기본적인 정의는 동일하다. 또한, 놀랍게도 보안성에 대한 증명은 기존 Even-Mansour와 동일하다고 한다.

결국, Single-Key Even-Mansour에서도 공격을 제대로 하려면 $DT = \Omega (2^n)$을 필요로 한다고 한다.

그러니, 비밀키로 필요한 bit의 개수를 절반으로 줄이면서 동일한 수준의 보안성을 유지할 수 있다는 결론을 얻는다.

Single-Key Even-Mansour에 대한 공격을 생각해보자. 당연히 위에서 다룬 모든 공격은 여기서 적용된다.

하지만, Single-Key의 경우에는 더욱 간단한 공격 방식이 존재한다. 물론, 복잡도는 여전히 $DT = \Omega (2^n)$이다.

$P$를 plaintext라고 하고, $x = P$, $y = P \oplus K$, $z = \mathcal{F}(P \oplus K)$, $w = E(P) = \mathcal{F}(P \oplus K) \oplus K$라 하자.

여기서 중요한 점은 $x \oplus w = y \oplus z$라는 점이다. 이제 $D \le 2^n$을 아무거나 하나 잡자.

adversary가 이미 plaintext/ciphertext 순서쌍 $(P_i ,E(P_i))$를 $D$개 들고 있다고 하자.

즉, $E$-oracle을 "known" 형태로 이용한다. 이제 배열을 준비하고 $(P_i \oplus E(P_i), i)$를 정렬된 상태로 들고 있는다.

이제 임의의 값 $X_1 , X_2, \cdots X_{2^n/D}$를 잡고, $\mathcal{F}$-oracle을 이용한다. 

각 $j$에 대하여, $X_j \oplus \mathcal{F}(X_j)$를 들고 가서 미리 준비해놓은 배열에서 탐색한다. 

만약 $P_i \oplus E(P_i) = X_j \oplus \mathcal{F}(X_j)$인 $i, j$를 찾았다면 $K = P_i \oplus X_j$를 키로 추측한다.

분석 자체는 Slide with a Twist Attack과 큰 차이가 없으므로, 여기서도 생략한다.

#5: The Security of Other Variants of the Even-Mansour Scheme

첫 번째 variant는 XOR 대신 덧셈을 사용하는 Even-Mansour Scheme이다. 

즉, $AEM_{K_1, K_2}^{\mathcal{F}}(P) = \mathcal{F}(P + K_1) + K_2$다. 여기서 모든 덧셈은 $\pmod{2^n}$으로 한다.

이 variant가 기존 Even-Mansour Scheme 이상의 보안성을 가짐은 같은 방법으로 증명할 수 있다.

즉, 여기서도 성공적인 공격을 위해서는 $DT = \Omega (2^n)$이 기본적으로 필요하다.

앞선 공격들은 은근히 XOR 연산의 성질들을 많이 사용하였다. 대표적으로, $A \oplus B = C$면 $A = B \oplus C$라는 점을 꽤 사용하였다.

하지만 slidex attack에 대하여 조금 더 생각하면 이 variant에 대한 공격도 할 수 있다.

두 plaintext $P, P^*$가 $P + P^* = -K_1 + \Delta$를 만족한다고 하자.

그러면 $E(P) = \mathcal{F}(P + K_1) + K_2 = \mathcal{F}(-P^* + \Delta) + K_2$고, $E(P^*) = \mathcal{F}(-P+\Delta) + K_2$를 얻는다.

즉, $E(P) + \mathcal{F}(-P+\Delta) = E(P^*) + \mathcal{F}(-P^* + \Delta)$를 얻는다.

결국 똑같은 방법으로 배열에 $(E(P_i) + \mathcal{F}(-P_i + \Delta), i)$를 저장하면 된다.

분석과 공격의 자세한 디테일은 역시 위에서 설명한 공격들과 큰 차이가 없으므로, 여기서는 생략한다.

두 번째 variant는 permutation 대신 involution을 사용하는 Even-Mansour Scheme이다.

involution 구조 자체가 암호론에서 꽤 자주 등장하는 구조이니, 이를 Even-Mansour에 적용한 것이다.

$\mathcal{I}$를 $n$-bit string의 집합에 대한 involution 중 하나라 하자. 

이제 $IEM_{K_1, K_2}^{\mathcal{I}} (P) = \mathcal{I}(P \oplus K_1) \oplus K_2$라 정의하자.

involution을 이용하니, $\mathcal{F}$-oracle 대신 $\mathcal{I}$-oracle이라는 이름으로 바꾸어서 논의하겠다.

이 경우, $K_1 \oplus K_2$의 값을 $E$-oracle을 $2^{(n+1)/2}$번 활용하여 얻을 수 있다. $\mathcal{I}$-oracle은 사용하지 않는다.

$E(P) = C$이고 $E(P^*) = C^*$라 하자. 만약 $P \oplus C^* = K_1 \oplus K_2$라면, $P \oplus K_1 = C^* \oplus K_2$가 된다.

또한, $\mathcal{I}$가 involution이므로 $\mathcal{I}(P \oplus K_1) = \mathcal{I}^{-1} (C^* \oplus K_2)$를 얻는다.

그런데 $C = \mathcal{I}(P \oplus K_1) \oplus K_2$이고, $P^* = \mathcal{I}^{-1} (C^* \oplus K_2) \oplus K_1$이다.

그러니 식을 정리하면 $C \oplus K_2 = P^* \oplus K_1$이고, 즉 $P \oplus C = P^* \oplus C^*$를 얻는다.

이제 쉽다. $E$-oracle을 "known" 형태로 $2^{(n+1)/2}$번 사용한 다음, $(E(P_i) \oplus P_i, i)$를 정렬한 상태로 준비하고 collision을 찾기만 하면 된다. 

여기서 $E(P_i) \oplus P_i = E(P_j) \oplus P_j$라면, $P_i \oplus E(P_j) = K_1 \oplus K_2$를 추측하면 된다. 

즉, adversary는 $DT = \Omega (2^n)$을 만족하지 않으면서 non-trivial information을 얻을 수 있다.

즉, 기존 Even-Mansour의 보안성을 가지지 않는 variant임을 알 수 있다. 왜 그럴까?

기존 증명을 생각해보면, 비밀키를 고정했을 때 주어진 input/output 쌍과 consistent 하게 될 확률이 비밀키와 무관함을 이용하여 증명을 했다. 그런데 여기서는 involution 구조가 있어서, $\mathcal{I}(x)=y$라는 정보는 강제로 $\mathcal{I}(y)=x$라는 정보를 추가한다. 이 점을 더 생각해보면, consistent 하게 될 확률이 비밀키에 의해 달라질 수 있음을 알 수 있다. 어떻게 보면, 공격 자체가 이 점을 상당히 활용하고 있음도 알 수 있다.

신기한 점은, involution 구조에 Single-Key Even-Mansour를 덮으면 이런 문제가 없다는 것이다. 다른 말로 하면, involution 구조를 가정하면 Single-Key가 Two-Key보다 보안성이 강력하다는 것이다. 암호화 과정 전체가 involution이 되고, 계산을 조금 해보면 consistent 하게 될 확률이 비밀키에 의해 달라지지 않음을 확인할 수 있다. 정확하게 말하면, 증명에서 등장하는 $S'$과 $T$ 사이의 dependency가 비밀키와 무관함을 알 수 있다. 여러모로 흥미로운 결과가 된다.

추가적인 관찰은, Two-Key로 암호화를 한 상태에서 $K_1 \oplus K_2$의 값이 유출이 되면, 결과적으로 비밀키 하나로 암호화를 한 것과 동일하다는 것이다. 

어쨌든, involution을 활용하고자 할 때 비밀키를 두 개 쓰는 것은 위험하다.

이제 involution 구조에 XOR 대신 덧셈을 사용하면 어떻게 되는지 보자.

동일한 과정을 거쳐서 $K_1 + K_2$를 복원할 수 있다. $C^* - P = K_1 + K_2$를 가정으로 하고 계산하면 된다.

이제 $K_1 + K_2$를 안다는 가정에서, 암호화 과정은 결국 $CISEM(P) = \mathcal{I}(P+K_1) - K_1$과 동일하게 된다.

이는 기존 Even-Mansour과 동일한 보안성을 가짐을 알 수 있다. 공격도 비슷하게 할 수 있다.

한편, involution 구조에 XOR 대신 덧셈을 사용할 때 두 키가 같다면, 즉 $K_1 = K_2$라면, 여기서 $2K_1$을 복원할 수 있다. 

즉, $K_1$을 사실상 (비트 하나 제외하고) 복원할 수 있다. 이건 그냥 암호가 제대로 깨진 것이라고 봐야 한다.

그러니 덧셈을 활용한 Even-Mansour에 single-key variant를 추가하고 싶다면, $CSEM(P) = \mathcal{F}(P+K_1) - K_1$을 이용하는 것이 더욱 보안성 측면에서 좋다. $\mathcal{F}$가 involution인 경우에도 보안성이 입증되어 있기 때문이다.

이 모든 내용을 정리하는 표가 논문의 Table 2로 제시되어 있다. 중요한 표이니, 여기에도 올린다.

#6: Memoryless Attacks on the Even-Mansour Scheme

이제 목표는 메모리를 적게 사용하면서 Even-Mansour를 공격하는 것이다. 지금까지 살펴본 공격들은 배열에 $E$-oracle을 통해서 얻을 값들을 정렬된 상태로 저장한다. 하지만 우리가 $2^{n/2}$ 스케일의 데이터를 저장하기에는 무리가 있다. 그러니 메모리를 절약하면서 Even-Mansour를 공격하는 방법을 다루는 것은 충분한 가치가 있는 일이라고 볼 수 있다. 여기서는 $D, T$가 $\mathcal{O}(2^{n/2})$이면서, 메모리는 상수만큼만 필요한 공격을 제시한다. 

특히, 이는 앞서 제시한 slide with a twist 공격을 변형한 것으로 볼 수 있는 공격 방식이다.

메모리를 절약하는 알고리즘 중 잘 알려진 것은 Floyd의 cycle detection 알고리즘이다. 여기서도 이를 활용한다.

결국 우리는 $E(P) \oplus F(P)$가 겹치는 것을 찾고 싶은 것이니, cycle detection을 활용할 수 있다.

$P_1$을 임의로 잡고, $P_1$에 대한 $E, \mathcal{F}$-oracle을 이용하여 $E(P_1)$, $\mathcal{F}(P_1)$을 계산한다. 이를 통해서 $P_2 = E(P_1) \oplus \mathcal{F}(P_1)$을 계산한다. 이 과정을 총 $\mathcal{O}(2^{n/2})$번 반복하여, $P_1, P_2, \cdots $를 얻는다. 여기에서 Floyd의 cycle detection 알고리즘을 돌리면, $E(P_i) \oplus \mathcal{F}(P_i) = E(P_j) \oplus \mathcal{F}(P_j)$인 $P_i, P_j$를 찾을 수 있고, 여기서 키를 추측할 수 있다. 기본적인 분석은 slide with a twist attack과 동일하다. 여기서 중요한 점은, Floyd의 알고리즘을 이용했기 때문에 메모리는 상수만큼만 필요하며, $E$-oracle을 날리는 $P_i$가 이전 계산 결과에 depend 하기 때문에 여기서는 "known" 형태로 $E$-oracle을 사용하는 것이 아니라, "adaptive chosen" 형태로 $E$-oracle을 사용해야 한다. 조금 더 강력한 oracle을 사용해야 한다고 보면 되겠다.

또한, 여기서는 $E$-oracle을 $\mathcal{O}(2^{n/2})$ 급으로 사용할 수 없는 경우, 확장하기가 어려움을 알 수 있다.

slidex attack은 $E$-oracle의 사용횟수와 $\mathcal{F}$-oracle의 사용 횟수에 대한 tradeoff를 제공하지만, 이를 memoryless 방식으로 확장하기에는 어려움이 있다. 그래서 $D << 2^{n/2}$를 가정한 상태에서 memoryless attack을 하는 방법은 이 논문에서 제시한 하나의 open problem이다. single-key variant에서도 마찬가지로 이를 생각할 수 있다. $D, T$가 $\mathcal{O}(2^{n/2})$이면서 memoryless attack을 하는 것은 어렵지 않으나, $D << 2^{n/2}$를 가정한 상태에서 memoryless attack을 하는 것은 어렵다. 이 역시 하나의 open problem으로 남기면서, 논문의 main text는 끝난다.