« 2024/05 »
일	월	화	수	목	금	토
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30	31

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

✉ 윤형준 encrypt@kakao.com

Overview

본 (3) 알고리즘 분석 파트에서는 NEAT 구현체를 리버싱하여 분석한 NEAT 암호의 동작 과정을 정리한다.

NEAT

NEAT(National Encryption AlgoriThm)는 국정원에서 만든 암호 알고리즘으로 1997년 국가기관용 표준암호로 제정되었다.

암호 알고리즘의 표준 문서나 명세서를 제공하고 있지 않은 비공개 암호 알고리즘으로 security through obscurity에 보안성을 일부 의존하고 있다.

NEAT는 블록암호이며 현대 블록암호가 대부분 그러하듯 substitution과 permutation에 암호 안전성을 의존하는 SPN(Substitution Permutation Network) 구조다.

NEAT의 Round function은 128-bit의 block을 암호화하는데, 64-bit의 round key와 8-bit의 round xcon을 사용한다

round function을 12번 반복한 뒤에 half round를 수행한다. 이때 half Round에서는 final swap을 수행한다.

final swap은 암복호화의 구조를 통일하려는 시도로 보이는데 자세한 내용은 (4) 동작 원리와 설계 사상에서 다룰 예정이다.

Defenition

먼저 NEAT에서 사용하는 수학적인 개념과 연산을 정의한다.

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

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

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

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

XOR( $\oplus$ ), Addition( $\boxplus$ ), Multiplication( $\odot$ )은 국제 표준암호 IDEA와 동일한 연산 사용한다.

두 연산은 non-linearity와 부가적인 안전성을 위해 Addition과 Multiplication을 서로 다른 group 위에 정의했다.

$(2^{16}, \oplus)$ 와 $(2^{16}+1, \odot)$ 로 정의할 수 있다.

특히 Multiplication은 프로세서의 clock cycle과도 연관이 있다. modulo $p$ 를 $2^{16}+1$ 인 소수로 설정하여 집합 $\delta = [1, \dots, p-1]$ 의 고정된 값에 어떤 곱셈 연산이 다시 $\delta$ 로 bijection 됨을 보장할 수 있다. 게다가 $0$ 을 $p-1 = 2^{16}$ 으로 표현함으로써 16-bit의 수를 전부 표현할 수 있다.

이를 위해 실제 구현에서는 $0$ 을 $0\text{x}10000$ 으로 취급하여 계산하고, 계산 결과가 $0\text{x}10000$ 인 경우 다시 $0$ 으로 설정해 준다.

Data-dependent Rotation( $\lll$ )은 MARS나 RC5와 같은 암호 알고리즘에서 사용하는 연산과 유사한다.

이는 differential cryptanalysis와 linear cryptanalysis에 저항성을 가지고 있다고 알려져 있다.

$a \lll b$ 일 때, $b$ 의 $\text{least signicant}$ $lg(w)$ (low-order bits)인 $w$ -bit 만큼 rotate한다.

Encryption

암호화는 12번의 Round function 이후 half Round function과 final swap으로 이루어져 있다.

Round function

다음은 round funcion의 그림이다.

128-bit의 input을 64-bit의 L(Left)과 R(Right)로 나눈다. 그리고 L, R을 각각 F, InvF의 input으로 사용한 뒤 그 output을 XL(Xor Layer)의 input으로 사용한다.

다음은 half round funcion의 그림이다.

[그림2] A structure of half round function

half Round 함수에서는 Xor Layer가 포함되어 있지 않고, 대신 final swap을 수행한다.

이는 암복호화 구조를 통일하려는 블록암호 알고리즘에서 흔히 볼 수 있는 구조다.

특히 final sawp을 이용해 NEAT 구현체에서 찾아볼 수 없었던 독특한 성질을 증명해낼 수 있었다.

F function

다음은 round function에서 사용하는 F function의 그림이다.

앞서 정의한 연산들을 모두 사용한다.

F function은 round function의 input 중 절반인 64-bit L을 input으로 사용한다

$k_0$ 와 $k_1$ 는 라운드 키의 일부다. 64-bit인 라운드 키 $K = \{k_0, k_1, k_2, k_3\}$ 의 상위 두 16-bit에 해당한다. 나머지 32-bit는 InvF function에서 사용한다.

NEAT와 동일한 XOR, Add, Mul 연산을 사용하는 블록 암호 IDEA, MESH에서는 Multiplication과 Addition의 조합을 MA-box 또는 MA-structure라고 부른다. 그래서 NEAT의 F 함수도 MARX-box라고 부르는 게 어떨가 생각을 하기도 했다. 하지만 MARX(마르크스..)는 사람 이름 같기도 하고, NEAT가 Feistel Network의 특징을 일부 가지고 있어서 F-fucntion이라고 명명했다.

InvF function

다음은 InvF function의 그림이다.

InvF는 F의 연산 순서를 반대로 수행하면서 덧셈 연산은 뺄셈으로, left rotation은 right rotation으로 치환한 형태다.

사실 Multiplication 대신 Division을 사용해야 F function의 역함수가 된다.

다만 $(k_1 \odot k_3) = (k_2\odot k_4) = e$ 인 경우 $F^{-1}\cdot F = I$ 가 성립한다. ( $e$ : multiplicative identity, $I$ : identity funciton)

즉, k값에 따라 F 함수와 InvF 함수는 역함수 관계가 될 수 있다.

이는 암복호화 과정의 증명에 쓰인다

Xor Layer

다음은 XL의 그림이다.

XL은 그림으로 나타내는 것이 매우 부정확하기 때문에 실제 코드를 참고하는 편이 좋다.

XL은 다른 블록암호 알고리즘에서는 찾아볼 수 없는 독특한 구조를 가진다. XL과 조금이라도 비슷한 알고리즘을 찾기 위해 survey들을 찾아보았지만 100개가 넘는 블록암호 알고리즘 중 단 하나도 비슷한 구조가 없었다.

XL은 각각 64-bit의 input인 L과 R을 중 절반을 서로 XOR한다.

먼저 $0,1,2,3$ 중 하나의 값으로 이루어진 $1024(8 \times 124)$ 개의 상수 값들인 XBox에서 일련의 8개 값을 읽어온다. 이때 읽어온 8개의 값을 XCon(XL Constant)라고 하자.

XCon의 값들인 $c\ (0\le c\le3)$ 또는 $c+4$ 를 XL 함수의 입력 $(L || R) = \{x_1,x_2,\dots,x_8\}$ 의 index로 사용하여 $x_i$ 들을 XOR한다.

이때 R의 값 두 개(각 16-bit)를 가져와 L의 값 두 개와 XOR하고, L의 값 두 개를 가져와 R의 값 두 개와 XOR한다. 이렇게 L에서 2개의 16-bit 값이, R에서 2개의 16-bit 값이 변하는데 이때 변하는 값은 XCon에 의존한다.

XCon은 Round Key로부터 파생되는 position에 따라 결정되며 각 라운드마다 다르게 쓰이므로 Round XCon이라고 하는 것이 정확하다.

NEAT 구현체에서는 암호화할 때와 복호화할 때 서로 다른 XL을 사용한다.

복호화할 때 사용하는 XL을 편의상 dXL이라고 하자.

pseudo code는 아래와 같다.

// 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]

XL과 dXL은 수학/암호학적으로 정말 재미있는 관계를 가진다. 이는 구현체에 나타나지 않은 NEAT의 성질을 증명하는 데 사용된다.

Decryption

NEAT의 복호화 함수는 암호화 함수와 거의 동일하다.

구현체에서 찾아볼 수 있었던 함수의 구조상 차이점은 XL뿐이었다. 앞서 말했듯이 복호화 함수에서는 XL 대신 dXL을 사용한다.

또 다른 차이점은 복호화용 round key와 복호화용 round xcon을 사용한다는 것이다. 이는 각각 dec round key, dec round xcon이라고 부른다.

Key Schedule

Key Schedule은 암호화에 사용하는 round key와 round xcon을 만드는 과정이다.

round key는 각 64-bit이고, half round에서도 사용되므로 총 13개의 round key를 만들어야 한다.

round xcon은 각 8-bit이고, half round에서 사용되지 않으므로 총 12개의 round xcon을 만들어야 한다.

round key

먼저 round key는 암복호화에 쓰이는 round function을 이용해 생성한다.

round function은 input/output이 각 128-bit이다. 따라서 64-bit의 round key 13개를 만들기 위해 round function을 총 7번 반복한 뒤 13개의 round key만 사용한다.

앞서 말했듯이 round function은 round key와 round xcon이 필요한 함수다. 그래서 키 스케줄을 할 때는 round key 대신 상수 KCon = [0xFD56, 0xC7D1, 0xE36C, 0xA2DC]을 사용하고, round xcon 대신 position = 0에 해당하는 fixed xcon = [0, 1, 0, 1, 2, 3, 2, 3]을 사용한다.

round xcon

round xcon을 만들 때 round key를 사용한다.

한 라운드의 round key $K = \{k_0, k_1, k_2, k_3\}$ 가 있을 때, $\text{posotion} = \{(k_0\oplus k_3)\ \&\ 0\text{x}7F\ \} \times 8$ 이라고 하자. 이때 pos를 XBox의 index로 사용하여 round xcon을 생성한다.

Decryption Key Schedule

decKey Schedule은 복호화에 사용하는 dec round key와 dec round xcon을 만드는 과정이다.

round key는 각 64-bit이고, half round에서도 사용되므로 총 13개의 round key를 만들어야 한다.

round xcon은 각 8-bit이고, half round에서 사용되지 않으므로 총 12개의 round xcon을 만들어야 한다.

dec round key

dec round key는 round key를 이용해 만든다.

한 round key를 $K = \{k_0, k_1, k_2, k_3\}$ 이라고 하면 dec round key는 $dK = \{k^{-1}_2, k^{-1}_3, k^{-1}_0, k^{-1}_1\}$ 이다.

이때 $k^{-1}_i$ 는 $k_{i}$ 의 modular multiplicative inverse에 해당한다. ( $\text{i.e.}\ \ k_i \cdot k^{-1}_i = e$ , $e$ : multiplicative identity)

그리고 dec round key를 적용할 때는 순서를 반대로 적용한다.

dec round xcon

dec round xcon은 round xcon의 순서만 반대로 사용한다.

이때 dec round xcon을 생성하는 방식에 따라 NEAT를 완전한 involution function으로 만들 수 있음을 증명할 수 있다!

Conclusion

(3) 알고리즘 분석과 (4) 동작 원리와 설계 사상이 본 프로젝트의 메인이 아닐까 하는 생각이 든다.

본 파트는 프로젝트를 시작하기 전 처음으로 세운 목표였다.

암복호화 과정의 증명과 NEAT가 가지는 Involution에 성질과 같은 설계 사상은 다음 파트에서 다룬다.

Uploaded by Notion2Tistory v1.1.0

NEAT 암호 (5) 구현 (0)	2021.02.08
NEAT 암호 (4) 동작 원리와 설계 사상 (0)	2021.02.08
NEAT 암호 (2) 리버싱 (0)	2021.02.08
NEAT 암호 (1) 개요 (0)	2021.02.08
정수론 (9) The Quadratic Reciprocity Law (0)	2021.02.07

topcue