NEAT 암호 (4) 동작 원리와 설계 사상

※ 본 프로젝트는 offensive research가 아닌 defensive 관점에서 진행한 학술적인 연구입니다.

✉ 윤형준 encrypt@kakao.com

---

[목차]

Overview

Defenition

Operation

Notation

Lemma 1. F와 InvF의 관계

Lemma 2. F/InvF 함수와 Round Key/dec Round Key의 관계

Lemma 3. XL/dXL의 involution 성질

Lemma 4. XL과 dXL의 역함수 관계

Lemma 5. XL과 dXL의 관계

Theorem 1. NEAT Enc/Decryption

Theorem 2. Involution Structure

Conclusion

---

Overview

우리가 접할 수 있는 대부분의 공개 암호 알고리즘은 specification을 제공한다.

덕분에 operation이나 set에 대한 정의, 동작 원리, 수학적 배경, design decision을 포함하는 설계 사상 등을 알 수 있다.

하지만 NEAT는 그 어떤 정보도 공개하지 않았기 때문에 리버싱을 통해 알고리즘을 분석한 뒤에 수학적인 관점에서 접근할 수밖에 없다.

'만약 NEAT의 specification을 만들 수 있다면 얼마나 좋을까!'라고 생각했지만 너무 귀찮을 것 같아서 안 한다.

대신 동작 원리를 파악/증명하고 설계 사상을 밝혀내는 것에만 집중하기로 했다.

본 파트에서는 NEAT의 암복호화에 대한 증명을 위한 여러 Collorary들을 정의했고 증명한다.

그리고 NEAT 알고리즘이 involution structure임을 증명한다.

특히 후자는 NEAT 암호 알고리즘의 구현체를 리버싱하는 것만으로는 알 수 없는 사실이기 때문에 더욱 흥미로웠다.

---

Defenition

먼저 NEAT에서 사용하는 operation과 notation을 정의한다.

---

Operation

(3) 알고리즘 분석 파트에서 정의한 연산과 똑같이 정의한다.

• Bitwise XOR on 16-bit ($\oplus$)

• Addition on $2^{16}$ ($\boxplus$)

• Multiplication on $2^{16}+1$ ($\odot$)

• Data-dependent Rotation on 16-bit ($\lll$)

---

Notation

증명을 위해 몇가지 notation을 정의하고 사용한다.

• index

  프로그래밍에서 흔히 대괄호로 표현하는 index notation을 아래와 같이 정의하자.

  $X=\{x_0, x_1, x_2, x_3, x_4, x_5, x_6, x_7\}$일때, $X[i]$는 vector(array) $X$의 $i$번째 원소. $(0\le i\le 7)$

  예) $x[7] = x_7$

  (이렇게 막해도 되나? computer science랑 수학을 섞어서 증명하는건 처음이라.. )

• overline

  overline notation을 다음과 같이 정의하자.

  $\text{let}\ x = [x_0, x_1, x_2, x_3, x_4, x_5, x_6, x_7]\ \text{then}\ \overline{x} = [x_4, x_5, x_6, x_7, x_0, x_1, x_2, x_3]$

  vector(array)의 좌우를 swap한다.

---

Lemma 1. F와 InvF의 관계

• Lemma 1.

💡

let round key $K = \{k_0, k_1, k_2, k_3\}$ and input $X = \{x_0, x_1, x_2, x_3\}$. If $(k_0 \odot k_2) = (k_1\odot k_3) = e$, then $InvF(X, K) = F^{-1}(X, K)$. $(i.e.\ F \cdot InvF = I)$. ($e$ : multiplicative identidy, $I$ : identity function)

$(k_0 \odot k_2) = (k_1\odot k_3) = e$라는 조건은 Key Schedule을 통해 만들어진 Round Key라면 만족할 수 있다.

즉 같은 round function에 있는 $F$와 $InvF$가 역함수 관계임을 증명하는 유용한 정리다.

• $F, InvF$ 그림

  

  [그림1] A structure of F function

  

  [그림2] A structure of InvF function

• ${proof}$

  $F$의 input을 $\{x_0, x_1, x_2, x_3\}$라고 하자. (각 $x_i$는 16-bit)

  그러면 $F$의 output인 $\{y_0, y_1, y_2, y_3\}$는 각각 다음과 같다. ($F$ 단순 전개)

  $y_0 = rot_{left}(x_0 \boxplus (x_2 \oplus x_3))$

  $y_1 = \{k_0\odot(x_0\oplus x_1)\} \boxplus rot_{left}(x_0 \boxplus (x_2 \oplus x_3))$

  $y_2 = \{k_1\odot(x_2\oplus x_3)\} \boxplus rot_{left}(x_0 \boxplus (x_2 \oplus x_3))$

  $y_3 = rot_{left}(x_3 \boxplus (x_0 \oplus x_1))$

  이 $\{y_0, y_1, y_2, y_3\}$를 $InvF$의 input으로 사용할 경우 그 output인 $\{z_0,z_1,z_2,z_3\}$ 은 다음과 같다. ($InvF$ 단순 전개)

  $z_0 = x_0 \odot k_1\odot k_3$

  $z_1 = x_1 \odot k_0 \odot k_1 \odot k_2\odot k_3$

  $z_2 = x_2 \odot k_0 \odot k_1 \odot k_2\odot k_3$

  $z_3 = x_3 \odot k_0\odot k_2$

  이때 $(k_0 \odot k_2) = (k_1\odot k_3) = e$인 경우 $\{z_0,z_1,z_2,z_3\}=\{x_0,x_1,x_2,x_3\}$가 된다.

  즉 $F \cdot InvF = I$가 성립한다.

---

Lemma 2. F/InvF 함수와 Round Key/dec Round Key의 관계

• Lemma 2.

💡

NEAT의 round function에 $XL$이 없다면, $Dec(Enc(X)) = X$

$XL$ 없이 $F, InvF$만으로 이루어진 round function을 사용하는 NEAT를 가정하자.

단 half round는 존재하기 때문에 final swap은 수행한다.

그러면 $F/InvF$의 성질과 Key Schedle 방식에 의해 $D(E(P))=D(C)=P$임을 보일 수 있다.

• round function, half round function 그림

  

  [그림3] A structure of round function

  

  [그림4] A structure of half round function

• ${proof}$

  $i$번째 round key를 아래와 같이 정의하자.

  $\text{let}\ i\text{-th\ round\ key} = \{a_i, b_i, c_i, d_i\}$ (16-bit x 4)

  아래와 같이 암호화 13라운드 복호화 13라운드를 위해 키스케줄을 했다고 가정하자. (round key 13개와 dec round key 13개)

  암호화를 위한 13개의 round key 생성

  $\text{[enc round\ 1]}: \{a_1, b_1, c_1, d_1\}$

  $\text{[enc round\ 2]}: \{a_2, b_2, c_2, d_2\}$

  $\cdots$

  $\text{[enc round\ 12]}: \{a_{12}, b_{12}, c_{12}, d_{12}\}$

  $\text{[enc round\ 13]}: \{a_{13}, b_{13}, c_{13}, d_{13}\}$

  ---

  복호화를 위한 13개의 dec round key 생성

  $\text{[dec round\ 1]}: \{c^{-1}_{13}, d^{-1}_{13}, a^{-1}_{13}, b^{-1}_{13}\}$

  $\text{[dec round\ 2]}: \{c^{-1}_{12}, d^{-1}_{12}, a^{-1}_{12}, b^{-1}_{12}\}$

  $\cdots$

  $\text{[dec round\ 12]}: \{c^{-1}_{2}, d^{-1}_{2}, a^{-1}_{2}, b^{-1}_{2}\}$

  $\text{[dec round\ 13]}: \{c^{-1}_{1}, d^{-1}_{1}, a^{-1}_{1}, b^{-1}_{1}\}$

  ---

  평문을 $P = \{L||R\}$ 라고 하자.

  $i$번째 round function의 output을 아래와 같이 정의하자.

  $i\text{-th\ round output} = \{L_i||R_i\}$

  그리고 아래와 같은 notation을 사용한다.

  $F(X, K)$: $X$는 암호화 하려는 64-bit 입력. $K$는 round key ($\{k_0, k_1\}$만 사용)

  $InvF(X, K)$: $X$는 암호화 하려는 64-bit 입력. $K$는 round key ($\{k_2, k_3\}$만 사용)

  ---

  암호화를 진행하면 각 라운드의 output은 아래와 같다.

  $\text{[enc round 1 output] :}$

  $L_1 = F(L, \{a_1, b_1\})$

  $R_1 = InvF(R, \{c_1, d_1\})$

  $\text{[enc round 2 output] :}$

  $L_2 = F(L_1, \{a_2, b_2\})$

  $R_2 = InvF(R_1, \{c_2, d_2\})$

  $\cdots$

  $\text{[enc round 11 output] :}$

  $L_{11} = F(L_{10}, \{a_{11}, b_{11}\})$

  $R_{11} = InvF(R_{10}, \{c_{11}, d_{11}\})$

  $\text{[enc round 12 output] :}$

  $L_{12} = F(L_{11}, \{a_{12}, b_{12}\})$

  $R_{12} = InvF(R_{11}, \{c_{12}, d_{12}\})$

  $\text{[enc half round output] :}$

  $R_{13} = F(L_{12},\{a_{13}, b_{13}\})$

  $L_{13} = InvF(R_{12}, \{c_{13}, d_{13}\})$

  ---

  복호화를 진행하면 각 라운드의 output은 아래와 같다.

  $\text{[dec 1 round output] :}$

  $L'_1 = F(InvF(R_{12}, \{c_{13}, d_{13}\}), \{c^{-1}_{13}, d^{-1}_{13}\}))$

  $R'_1=InvF(F(L_{12},\{a_{13}, b_{13}\}), a^{-1}_{13}, b^{-1}_{13})$

  이때 $c_{13}\odot c^{-1}_{13} = d_{13}\odot d^{-1}_{13}=e$ 이므로 Collorary 1. 에 의해

  $F(InvF(R_{12}, \{c_{13}, d_{13}\}), \{c^{-1}_{13}, d^{-1}_{13}\})) = R_{12}$

  마찬가지로 $a_{13}\odot b^{-1}_{13} = a_{13}\odot b^{-1}_{13}=e$ 이므로 Lemma 1. 에 의해

  $InvF(F(L_{12},\{a_{13}, b_{13}\}), a^{-1}_{13}, b^{-1}_{13}) = L_{12}$

  따라서 $\text{[dec round 1 output]}$은 $\text{[enc round 12 output]}$과 같다.

  즉 $L'_1 = R_{12}$이고 $R'_1 = L_{12}$이다.

  $\text{[dec 2 round output] :}$

  $L'_2 = F(R_{12})$

  $R'_2 = InvF(L_{12})$

  $R_{12},\ L_{12}$는 $\text{[enc round 11 output]}$이므로 각각

  $L_{12} = F(L_{11}, \{a_{11}, b_{11}\})$이고

  $R_{12} = InvF(R, \{c_{11}, d_{11}\})$이다.

  따라서

  $L'_2 = F(R_{12}) = F(InvF(R_{11}, \{c_{11}, d_{11}\}))$

  $R'_2 = InvF(L_{12}) = InvF(F(L_{11}, \{a_{11}, b_{11}\}))$

  이고, 마찬가지로 Collorary 1. 에 의해 아래와 같다.

  $F(InvF(R_{11}, \{c_{11}, d_{11}\})) = R_{11}$

  $InvF(F(L_{11}, \{a_{11}, b_{11}\})) = L_{11}$

  따라서 $L'_2 = R_{11}$이고 $R'_2 = L_{11}$이다.

  이와 유사하게 $\text{[dec round 12]}$까지 진행하면 output은 다음과 같다.

  $L'_{12} = R_1$

  $R'_{12} = L_1$

  마지막으로 $\text{[dec half round]}$에서 final swap을 수행하면 다음과 같다.

  $L'_{13} = L$

  $R'_{13} = R$

  복호화까지 수행한 결과 다시 $P=\{L||R\}$가 된다.

  ---

  정리하자면 다음과 같다.

  $P=\{L||R\}$일때, $Enc(P)=\{R_{13}||L_{13}\}$이다.

  $Dec(Enc(P)) = Dec(\{R_{13}||L_{13}\} ) = \{L'_{13}||R'_{13}\} = \{L||R\} = P$

  따라서 $Dec(Enc(P)) = P$를 만족한다.

---

Lemma 3. XL/dXL의 involution 성질

• Lemma 3.

💡

$XL$ and $dXL$ are $\text{involutional function}$. $(i.e.\ XL\cdot XL=I\ and\ dXL\cdot dXL=I)$

$XL$과 $dXL$은 XOR 연산만으로 이루어져 있으므로, $X$와 $xcon$이 고정되어 있다면 당연히 involution function이다.

하지만 당연한 사실일수록 증명이 까다로운 법..

$XL$이 프로그래밍에서 쉽게 볼 수 있는 배열의 index라는 개념을 사용하기 때문에 notation을 정의하는 것이 조금 힘들었다.

이 Lemma는 NEAT의 암복호화의 증명에 사용된다.

• $XL$과 $dXL$ 알고리즘

  # XL (for encryption)
  x[xcon[0]] ^= x[xcon[2] + 4]
  x[xcon[1]] ^= x[xcon[3] + 4]
  x[xcon[4] + 4] ^= x[xcon[6]]
  x[xcon[5] + 4] ^= x[xcon[7]]
  
  # dXL (for decryption)
  x[xcon[0] + 4] ^= x[xcon[2]]
  x[xcon[1] + 4] ^= x[xcon[3]]
  x[xcon[4]] ^= x[xcon[6] + 4]
  x[xcon[5]] ^= x[xcon[7] + 4]

• ${proof}$

  we must show that $XL\cdot XL= dXL\cdot dXL = I$ ($I$ : Identity function)

  $\text{xcon} = \{c_0,c_1,c_2,c_3,c_4,c_5,c_6,c_7\}$, input $X = \{x_0, x_1, x_2, x_3, x_4, x_5, x_6, x_7\}$라고 하자.

  $Y = XL(X, xcon)$은 다음과 같이 표현할 수 있다.

  $X[c_0] = X[c_0]\oplus X[c_2 + 4]$

  $X[c_1] = X[c_1]\oplus X[c_3 + 4]$

  $X[c_4 + 4] = X[c_4 + 4]\oplus X[c_6]$

  $X[c_5 + 4] = X[c_5 + 4]\oplus X[c_7]$

  그리고 $Z=XL(XL(X, xcon), xcon)$은 다음과 같이 표할 수 있다.

  $X[c_0] = X[c_0] \oplus X[c_2 + 4] \oplus X[c_2 + 4]$

  $X[c_1] = x[c_1] \oplus X[c_3 + 4] \oplus X[c_3 + 4]$

  $X[c_4 + 4] = X[c_4 + 4] \oplus X[c_6] \oplus X[c_6]$

  $X[c_5 + 4] = X[c_5 + 4] \oplus X[c_7] \oplus X[c_7]$

  XOR의 성질에 의해 다음과 같이 전개할 수 있다. (since $A\oplus A = I$)

  $X[c_0] = X[c_0] \oplus X[c_2 + 4] \oplus X[c_2 + 4] = X[c_0] \oplus I = X[c_0]$

  $X[c_1] = X[c_1] \oplus X[c_3 + 4] \oplus X[c_3 + 4] = X[c_1] \oplus I = X[c_1]$

  $X[c_4 + 4] = X[c_4 + 4] \oplus X[c_6] \oplus X[c_6] = X[c_4 + 4] \oplus I = X[c_4 + 4]$

  $X[c_5 + 4] = X[c_5 + 4] \oplus X[c_7] \oplus X[c_7] = X[c_5 + 4] \oplus I = X[c_5 + 4]$

  $XL(XL(X, xcon), xcon) = X$이다.

  따라서 $XL$은 involution function이다.

  이와 유사하게 전개하면 $dXL(dXL(X, xcon), xcon) = X$이다.

  따라서 $dXL$은 involution function이다.

---

Lemma 4. XL과 dXL의 역함수 관계

• Lemma 4.

💡

If $xcon = \{c_0, c_1, c_2, c_3, c_0, c_1, c_2, c_3\}$, then $dXL(X, xcon) = XL^{-1}(X, xcon)$.

일반적인 경우 $dXL$이 $XL$의 역함수가 아님을 증명한다.

$F$와 $InvF$는 까다롭지 않은 조건하에 역함수 관계가 성립한다.

$XL$과 $dXL$은 $xcon$이 $\{c_0, c_1, c_2, c_3, c_0, c_1, c_2, c_3\}$ 꼴인 경우 역함수 관계다.

• ${proof}$

  $X=\{x_0, x_1, x_2, x_3, x_4, x_5, x_6, x_7\}$와 $xcon = \{c_0, c_1, c_2, c_3, c_0, c_1, c_2, c_3\}$에 대해 $XL(X, xcon)$을 전개하면 다음과 같다.

  $X[c_0] = X[c_0] \oplus X[c_2 + 4]$

  $X[c_1] = X[c_1] \oplus X[c_3 + 4]$

  $X[c_0+4] = X[c_0+4] \oplus X[c_2]$

  $X[c_1+4] = X[c_1+4] \oplus X[c_3]$

  $dXL(X, xcon)$을 전개하면 다음과 같다.

  $X[c_0+4] = X[c_0+4] \oplus X[c_2]$

  $X[c_1+4] = X[c_1+4] \oplus X[c_3]$

  $X[c_0] = X[c_0] \oplus X[c_2+4]$

  $X[c_1] = X[c_1] \oplus X[c_3+4]$

  연산 순서만 바뀌었을 뿐 결과는 같은 것을 알 수 있다.

---

Lemma 5. XL과 dXL의 관계

• Lemma 5.

💡

${XL(X, xcon)} = {dXL(X, \overline{xcon})} = \overline{dXL(\overline{X}, xcon)}$

$XL$과 $dXL$은 까다로운 조건에서만 역함수 관계가 성립한다.

그래서 그런지 Lemma 5. 도 복잡하게 생겼다.

복잡해서 쓸데없어 보이지만, 놀랍게도 NEAT의 암복호화를 증명하는데 쓰인다.

그리고 더 놀랍게도 NEAT를 완벽한 involution 암호로 사용할 수 있음을 증명하는데 크게 기여한다!

• ${proof}$

  먼저 $XL(X, xcon) = dXL(X, \overline{xcon})$임을 보이려 한다.

  $X=\{x_0, x_1, x_2, x_3, x_4, x_5, x_6, x_7\}$와 $xcon = \{c_0, c_1, c_2, c_3, c_4, c_5, c_6, c_7\}$에 대해 $XL(X, xcon)$을 전개하면 다음과 같다.

  $X[c_0] = X[c_0] \oplus X[c_2 + 4]$

  $X[c_1] = X[c_1] \oplus X[c_3 + 4]$

  $X[c_4+4] = X[c_4+4] \oplus X[c_6]$

  $X[c_5+4] = X[c_5+4] \oplus X[c_7]$

  $X=\{x_0, x_1, x_2, x_3, x_4, x_5, x_6, x_7\}$과 $\overline{xcon} = \{c_4, c_5, c_6, c_7, c_0, c_1, c_2, c_3\}$에 대해 $dXL(X, \overline{xcon})$을 전개하면 다음과 같다.

  $X[c_4+4] = X[c_4+4] \oplus X[c_6]$

  $X[c_5+4] = X[c_5+4] \oplus X[c_7]$

  $X[c_0] = X[c_0] \oplus X[c_2 + 4]$

  $X[c_1] = X[c_1] \oplus X[c_3 + 4]$

  $XL(X, xcon)$과 비교했을 때 연산 순서만 바뀌었을 뿐 결과는 같은 것을 알 수 있다.

  따라서 $XL(X, xcon) = dXL(X, \overline{xcon})$이다.

  ---

  이제 ${XL(X, xcon)} = \overline{dXL(\overline{X}, xcon)}$임을 보이려 한다.

  그림을 그리면 참 쉽지만 수식으로 증명하려면 notation이 상당히 복잡해진다.

  두 개의 첨자가 필요하다.

  먼저 위 첨자(superscript)는 $xcon$의 index에 의해 결정된다.

  $xcon[0]$부터 $xcon[3]$까지는 $x^l$, $xcon[4]$부터 $xcon[7]$까지는 $x^r$로 표시하자.

  아래 첨자(subscript)는 $x$의 index에 의해 결정된다.

  $x[0]$부터 $x[3]$까지는 $x_i$, $x[4]$부터 $x[7]$까지는 $x_j$로 표시하자.

  그리고 $XL$이나 $dXL$로 인해 값이 XOR된 경우 아래 첨자에 $*$를 마킹할 것이다.

  예를 들어 $x[c_0] = x[c_0] \oplus x[c_2+4]$를 실행할 경우 $x^l_{i*}$로 표현하고, $x[c_4 + 4] = x[c_4 + 4]\oplus x[c_6]$을 실행한 경우 $c_{j*}^r$로 표현한다.

  ${XL(X, xcon)}$을 수행하면 $\{x^l_{i*} ,x^l_i\}\in y^l$, $\{x^r_{j*} ,x^r_j\}\in y^r$이 된다.

  $dXL(\overline{X}, xcon)$을 수행하면 $\{x^l_{j*}, x^l_j\} \in y^l$, $\{x^r_{i*}, x^r_i\} \in y^r$이 된다.

  이때 $dXL(\overline{X}, xcon)$를 swap하면 $x$의 index만 바뀌므로 $\overline{dXL(\overline{X}, xcon)}$은 아래와 같다.

  $\{x^l_{i*}, x^l_i\} \in y^l$, $\{x^r_{j*}, x^r_j\} \in y^r$

  이때 $XL$에서 $*$를 마킹한 원소와 $dXL$에서 $*$를 마킹한 원소의 index가 같음은 단순 전개로 확인할 수 있으므로 생략한다.

  따라서 $XL(X, xcon)$과 $\overline{dXL(\overline{X}, xcon)}$이 같은 원소를 갖는 set이 된다.

  따라서 ${XL(X, xcon)} = \overline{dXL(\overline{X}, xcon)}$다.

---

Theorem 1. NEAT Enc/Decryption

💡

Theorem 1. (A proof of decrytion) $Dec(Enc(X)) = X$

앞서 정의하고 증명한 여러 Lemma들은 바로 이 Theorem을 위한 여정이었다고 해도 과언이 아니다!

실제로 NEAT가 어떻게 암호화/복호화가 가능한 블록암호인지 증명을 하려 했고, 그 과정에서 사용한 여러 Lemma를 정의했다.

일부 notation을 생략하거나 축소했는데도 증명이 상당히 길다.

• ${proof}$

  엄밀하게 말하면 $F/InvF$는 $F(X, rk)$와 같이 표기하고, $XL/dXL$은 $XL(X, xcon)$과 같이 표기해야한다.

  하지만 저런 notation을 사용할 경우 수식이 너무 길어진다..

  이미 6개의 Lemma에서 특정 라운드에서 함수의 특징을 정리했으니 본 증명에서는 간단히 input $X$만 표기하려한다.

  ---

  let $P = \{L||R\}$.

  $\text{[enc round\ 1]}:$

  $(L_1 || R_1) = XL(F(L) || InvF(R) )$

  $\text{[enc round\ 2]}:$

  $(L_2 || R_2) = XL(F(L_1) || InvF(R_1) )$

  $\cdots$

  $\cdots$

  $\text{[enc round\ 12]}:$

  $(L_{12} || R_{12}) = XL(F(L_{11}) || InvF(R_{11}) )$

  $\text{[enc round 13]}:$

  $(L_{13}||R_{13}) = \overline{(F(L_{12}) || InvF(R_{12})} = InvF(R_{12})||F(L_{12})$

  $\therefore L_{13} = InvF(R_{12})$ and $R_{13} = F(L_{12})$

  ---

  $\text{[dec round\ 1]}:$

  $(L'_{1}||R'_{1}) = dXL(F(L_{13})||InvF(R_{13}))$

  $\text{[dec round\ 2]}:$

  $(L'_{2}||R'_{2}) = dXL(F(L'_{1})||InvF(R'_{1}))$

  $\cdots$

  $\cdots$

  $\text{[dec round\ 12]}:$

  $L'_{12}||R'_{12} = dXL(F(L'_{11})||InvF(R'_{11}))$

  $\text{[dec round\ 13]}:$

  $L'_{13} || R'_{13} = \overline{F(L'_{12})||InvF(R'_{12})} = InvF(R'_{12})||F(L'_{12})$

  $\therefore L'_{13} = InvF(R'_{12})$ and $R'_{13} = F(L'_{12})$

  ---

  이제 $Dec(Enc(P))=P$를 보이는 것은 $L'_{13} = L, R'_{13} = R$ 임을 보이는 문제로 바뀌었다.

  in $\text{[dec round\ 1]}$

  $(L'_{1}||R'_{1}) = dXL(F(L_{13})||InvF(R_{13}))$

  $=dXL(F(InvF(R_{12})||InvF(F(L_{12}))))$ (since $L_{13} = InvF(R_{12}),\ R_{13} = F(L_{12})$)

  $= dXL(R_{12}||L_{12})$ (by Collorary 1.)

  이때 아래와 같은 전개 방식을 Method (A)라고 하자.

  • Method (A)

    in $\text{[enc round\ 1]}$

    $(L_{12}||R_{12}) = XL(F(L_{11})||InvF(R_{11}))$

    이때 양변을 swap 하면 아래와 같다.

    $(R_{12}||L_{12}) = \overline{XL(F(L_{11})||InvF(R_{11}))}$

    그리고 양변에 $dXL$을 취하면 아래와 같다.

    $dXL(R_{12}||L_{12}) = dXL(\overline{XL(F(L_{11})||InvF(R_{11}))})$

    이때 Collorary 5.에 의해

    $dXL(R_{12}||L_{12}) = \overline{(F(L_{11})||InvF(R_{11}))} = (InvF(R_{11}))||F(L_{11}))$

    $\therefore dXL(R_{12}||L_{12}) = (InvF(R_{11})||F(L_{11}))$

  Method (A)에 의해 $(L'_1 || R'_1) = dXL(R_{12}||L_{12})= (InvF(R_{11})||R(F_{11}))$

  in $\text{[dec round\ 2]}$

  $(L'_{2}||R'_{2}) = dXL(F(L'_{1})||InvF(R'_{1}))$

  이때 $L'_1$과 $R'_1$을 대입하면 아래와 같다.

  $(L'_{2}||R'_{2})\\ = dXL(F(InvF(R_{11})) || InvF(F(L_{11})))\\= dXL(R_{11}||L_{11})$

  그리고 Method (A)처럼 전개하면,

  $dXL(R_{11}||L_{11}) = InvF(R_{11})||F(L_{11})$.

  $\therefore (L'_{2}||R'_{2}) = (InvF(R_{11}||F(L_{11})))$

  이와 유사하게 $\text{[dec round\ 12]}$라운드 까지 진행하면,

  $(L'_{12}||R'_{12}) = (InvF(R_1)||F(L_1))$.

  in $\text{[dec round\ 13]}$

  $L'_{13} = InvF(R'_{12}), R'_{13} = F(L'_{12})$

  이때 $L'_{13}$과 $R'_{13}$을 각각 대입하면,

  $(L'_{13}||R'_{13}) = (InvF(F(L_1)) || F(InvF(R_1)))$

  그리고 Collorary 1. 에 의해

  $(L'_{13}||R'_{13}) = (L_1||R_1)$

  $\therefore Dec(Enc(P)) = Dec(C) = P$

---

Theorem 2. Involution Structure

💡

Theorem 2. (An involution feature of NEAT) If $\overline{xcon}$ is used instead of $xcon$ for decrypt, NEAT is involution.

NEAT 암복호화 증명을 마무리하기 두 줄 전, Lemma 5. 를 이용하면 NEAT가 involution이 될 것이라는 생각이 들었다.

그리고 실제로 복호화용 dec round xcon을 살짝 비틀면 NEAT가 involution이 됨을 확인했다.

dec round xcon을 모두 swap하면 NEAT가 involution이 된다.

찾기도 힘들었고 아주 유용하게 쓸 수 있는 특징인데 증명은 Lemma 5. 를 이용하면 매우 간단하다.

• ${proof}$

  복호화용 $xcon$인 dec round xcon을 모두 swap했다고 가정하자.

  즉 $xcon$ 대신 $\overline{xcon}$을 사용한다.

  그러면 $dXL(X, xcon)$대신 $dXL(X, \overline{xcon})$을 적용해야 한다.

  이때 Lemma 5. 에 의해 $dXL(X, \overline{xcon})$를 $XL(X, xcon)$로 치환할 수 있다.

  그럼 복호화 과정은 다음과 같다.

  $\text{[dec round\ 1]}:$

  $(L'_{1}||R'_{1}) = XL(F(L_{13})||InvF(R_{13}))$

  $\text{[dec round\ 2]}:$

  $(L'_{2}||R'_{2}) = XL(F(L'_{1})||InvF(R'_{1}))$

  $\cdots$

  $\cdots$

  $\text{[dec round\ 12]}:$

  $L'_{12}||R'_{12} = XL(F(L'_{11})||InvF(R'_{11}))$

  $\text{[dec round\ 13]}:$

  $L'_{13} || R'_{13} = \overline{F(L'_{12})||InvF(R'_{12})} = InvF(R'_{12})||F(L'_{12})$

  $\therefore L'_{13} = InvF(R'_{12})$ and $R'_{13} = F(L'_{12})$

  ---

  이는 NEAT의 암호화 과정과 동일한 구조임을 알 수 있다.

  즉 NEAT의 암호화를 이용해 복호화를 할 수 있다.

  따라서 NEAT는 involution structure다.

---

Conclusion

NEAT의 암복호화 과정을 증명했고, 추가로 NEAT가 involution이 될 수 있음을 보였다.

코드를 작성해서 실행해보면 간단히 보일 수 있는 것들을 증명하려 하니 굉장히 어려웠다.

다만 조금 이상한 점이 있다.

NEAT를 설계한 분들(국정원)이 의도적으로 NEAT를 involution으로 만든 게 아닌가?

도대체 왜 구현체에서는 암호화 함수와 복호화 함수를 다르게 구현한 것일까?

NEAT를 실제로 구현한 분들(개발자)은 NEAT의 specification을 받았을 것이고, 이를 토대로 구현했을 것이라고 생각한다. 그럼 NEAT를 구현한 분들이 의도적으로 암복호화가 분리된 알고리즘을 준 건가?

내가 고민해도 알 수 없겠지만 🧐 이번 파트는 굉장히 흥미로웠다.

다음은 NEAT를 C와 Python으로 구현하여 오픈소스로 공개하는 과정을 정리할 계획이다.

---

Uploaded by Notion2Tistory v1.1.0