[0x00] Slide Attack and Its Applications #1

c0np4nn4·2022년 3월 15일

Paper block cipher cryptanalysis slide attack

Paper Review

목록 보기

1/1

Abstract

암호학에서 널리 쓰이는 블록암호는 대용량 데이터를 암호화 하도록 설계되었다.
기술이 발전함에 따라, 블록암호는 작은 데이터를 암호화 하는 데에도 쓰이기 시작했다.
이러한 암호 시스템을 경량화 암호(lightweight)라 부른다.
경량화 암호도 암호 분석(cryptanalysis) 기법들로 테스트되어야 한다.
보통 차분 공격과 선형 공격으로 테스트한다.
하지만, 라운드 수가 증가할수록 이 공격들은 덜 효율적이게 된다.
이러한 관점에서, 라운드 수와 독립적인 Slide Attack이 개발되었다.

본 논문에서는 Slide Attack의 기초와 블록암호에서 어떻게 동작하는지에 초점을 맞춘다.
덧붙여, Slide Attack을 이해하는데 도움이 되는 몇몇 응용도 제공한다.
게다가, 여기서는 변형된 PRESENT 암호를 통해 경량화 암호에 대한 실용적인 공격에 대해 소개한다.

Keywords : Slide Attack, Block Ciphers, Lightweight Cryptography, Cryptanalysis

오른쪽 바에 있으므로 생략

Chapter 1. Introduction

1.1 Cryptology

암호학의 주요 관심사는 통신과 데이터 저장공간의 보안이다.
이를 위해 수학, 통계학, 컴퓨터 공학, 그리고 전자 공학의 이론들을 이용한다.
권한을 가진 사람을 제외한 모든 이들로부터 정보를 숨기는 것을 목적으로 한다.
게다가, 인증(Authentication), 기밀성(Confidentiality), 데이터 무결성(Data-Integrity), 부인 방지(Non-Repudiation) 등은 암호학적 구조로부터 제공된다.

암호화 기법(cryptography)은 상대방으로부터 통신에서 보안을 얻을 수 있는 기술이다.
암호 공격 기법(cryptanalysis)은 반대로 암호화 알고리즘의 안전성을 분석하는 작업이다.
이 둘은 계속 발전해오면서 서로 서로 상호작용해왔다.
암호 공격 기법 개발자가 알고리즘을 부수면, 암호화 기법 개발자는 알고리즘을 개선하여 가능하다면 공격 방법으로부터 안전성을 확보하고, 그러지 못하면 알고리즘은 쓸모가 없게 된다.
컴퓨터의 연산 능력이 증가함에 따라, 단순한 브루트포스 공격도 많아졌다.
그러므로, 암호학자들은 그들의 암호화 알고리즘을 계속해서 개발해야만 하며, 새로운 암호 기법을 개발해야 한다.

1.2 Description of Cryptography

현대 암호에서 암호화 기법에 대한 접근은 크게 두 가지로 나눌 수 있다.
- 대칭키 알고리즘
- 비 대칭키 알고리즘
일반적으로, 대칭키 알고리즘은 암호화와 복호화 과정에서 서로 같은 키를 사용한다.
이 키는 전송자와 수신자가 공유하고 있어야만 한다.
반면에, 비대칭키 알고리즘은 개인 키와 공개 키로 불리는 두 가지 키를 활용한다.
두 키는 수학적으로 풀기 어려운 문제를 기반으로 함께 만들어진다.
비대칭키 알고리즘의 기본 아이디어는 공개 키는 다른 모두와 공유하되 개인 키는 본인 키는 개인이 보관하고 있다는 것이다.
누구나 그 사람의 공개키로 메세지를 암호화 할 수 있다.
하지만, 수신자의 비밀키가 없이는 암호문을 복호화 하는 것이 거의 불가능하다.
비대칭키 알고리즘은 대칭키와 비교했을 때 더 많은 컴퓨터 연산이 필요하고 느리지만, 참여자들이 키를 공유할 필요가 없다는 장점이 있다.
대칭키 알고리즘을 사용할 경우, 우선은 비대칭키 알고리즘으로 키를 공유하는 단계를 거치는데, 이를 키 공유(key exchange)라 한다.
본 논문에서 비대칭키 알고리즘은 관심사가 아니다.

1.2.1 Stream Ciphers

스트림 암호는 대칭키 알고리즘의 한 갈래로, 평문 비트열을 키-스트림 비트열과 결합하여 암호문 비트열을 얻는다.
전체 암호문이 얻어질 때까지 이를 반복한다.
작업을 수행하기 위해서 키-스트림은 평문만큼 길어야 한다.
이를 위해, 짧은 키로부터 충분히 길고 랜덤처럼 보이는 키-스트림을 만들어내는 여러 방법이 있다.

1.2.2 Block Ciphers

블록암호는 대칭키의 또 다른 갈래로, 대용량 데이터를 블록 단위로 암호화하며 블록의 단위는 암호화 과정, 라운드 수, 프로토콜 등을 기준으로 정해진다.
일반적으로, 블록 암호는 하나의 비밀키를 갖는다.
이 키는 라운드 키를 생성하는 데 이용된다.
암호 알고리즘의 라운드가 성공적으로 적용되었을 때, 암호문을 얻을 수 있다.
복호화는 단순히 암호화 과정의 역(inverse)이다.

블록암호는 크게 SPN 구조와 Fiestel 구조로 나뉜다.

1.3 Cryptanalysis of Block Ciphers

암호학에서, 암호화 기법은 케르히호프 원리(Kerckhoffs' Principle)에 따라 알고리즘이 공개될 것으로 가정한다.
비밀로 유지하는 것은 오직 키 값이다.
보안성을 높이는 주된 기술은 서로 다른 라운드 키를 이용해서 알고리즘을 반복적으로 적용하는 것이다.
따라서, 암호화의 라운드 수는 라운드 함수를 몇 번이나 반복하는지에 따라 결정된다.
라운드마다 키를 제공하기 위해, 마스터 키(입력받은 키)를 사용해서 키 스케쥴링을 한다.
알고리즘의 안전성(보안성)은 오직 이 키에만 의존해야 한다.

블록암호에 대한 generic attack 시나리오는 공격자가 이미 알고 있는 (평문-암호문) 쌍에 대해 가능한 모든 $n$ -bit 의 키 값을 시도해서 실제 키를 찾는 것이다.
이 공격법을 Brute Force 혹은 Exhaustive Search라 부른다.
Brute Force를 불가능하게 만들기 위해, 블록암호 설계자들은 큰 키 스페이스를 이용한다.

공격자에 대한 각기 다른 가정에 따라, 각기 다른 공격 시나리오가 있다.
- Ciphertext Only Attack : 공격자가 오직 암호문만 갖고 있다고 가정한다.
- Known-Plaintext Attack : 공격자가 (평문-암호문) 쌍의 일부를 갖고 있다고 가정한다. 이 방법은 키를 복원하는 것에 초점을 맞춘다.
- Chosen-Plaintext Attack : 공격자가 평문의 bit 를 조작하여 암호문의 bit가 어떻게 바뀌는지 알 수 있다고 가정한다. 이 방법은 키의 일부, 혹은 전체를 복원하는 것에 초점을 맞춘다.
- Chosen-Ciphertext Attack : 공격자가 암호문을 임의로 복호화 할 수 있는 상태라 가정한다.
- Adaptive Chosen Plaintext/Ciphertext Attack : 공격자는 암호화/복호화를 모두 할 수 있다고 가정한다. 공격자가 암호화/복호화 이후의 평문/암호문으로부터 기대하는 바에 따라, 암복호화 작업을 계속 할 수 있다.

1.3.1 Complexity

이상적인 공격방법을 선택하기 위해, 공격자는 얼마나 많은 데이터 공간과 시간이 필요한지 고려해야 한다.
- Time Complexity : 알고리즘이 시작된 후 끝날 때까지 걸리는 전체 시간을 의미한다. 암호화가 몇 번 일어났는지를 통해 계산할 수 있다.
- Data Complexity : 공격을 위해 필요한 (평문-암호문) 쌍의 크기를 측정한다.
- Memory Complexity : 공격을 위해 필요한 저장 공간을 의미한다.

1.3.2 Linear and Differential Cryptanalysis

선형(Linear) 공격과 차분(Differential) 공격은 블록암호의 키를 복원하는데 중요한 두 가지 공격 방법이다.
기본적으로, 선형공격의 아이디어는 암호의 비선형적인 연산의 선형 근사를 찾는 것이다.
반면, 차분공격은 입력값과 출력값의 쌍의 차이에 대한 확률을 기반으로 한다.

1.4 About this Thesis

라운드 수를 증가시킴으로써 보안성을 확보하는 것이 충분하다고 여겨지지만, 몇몇 연구자들은 이 아이디어를 바꾸는 방향을 생각하고 있다.
이러한 관점에서, 1999년에 Alex Biryukov 와 David Wagner가 제안한 Slide Attack은 성공적인 공격 방법이다.
기본적으로, 이 공격은 알고리즘의 라운드 함수와 키 스케쥴 함수가 충분히 안전하지 않을 때 성공한다.
Slide Attack의 주요 특징은 라운드 수와 독립적이라는 것이다.
몇몇 암호 알고리즘에서 Slide Attack은 time/data complexities 를 감소 시키는데 굉장히 효과적인 방법으로 밝혀졌다.

이 논문의 구성은 다음과 같다. Chapter2에서는 이 논문의 서두(preliminaries)가 있다. Chapter3에서는 slide attack의 수학적 배경과 기본지식들을 설명한다. Chapter3는 또한 몇몇 블록암호 구조에 적용될 수 있는 generic technique을 포함한다. Chapter4에서는 slide attack의 응용들이 있다. Chapter5에서는 결론을 적었다.

Chpater2. Preliminaries

이 장에서는 slide attack의 preliminaries를 소개한다.
우선, 블록암호 알고리즘의 기본적인 두 가지 타입에 대해 논한다.
이후, low cost environment 를 위한 경량화 암호를 두 가지 예시 알고리즘과 함꼐 소개한다. (PRESENT, KeeLoq)
마지막으로, Slide Attack의 복잡도를 계산하는데 중요한 개념인 Birthday Paradox에 대해 자세히 설명한다.

2.1 Block Ciphers

1장에서 언급했듯이, 블록암호는 평문을 고정된 크기의 블록으로 나누고 한 블록씩 암호화 한다.
암호화 과정은 반복적인 라운드 함수로부터 적용된다.

당연하게도 블록암호는 매우 다양한 설계 기준이 있다. 하지만, 일반적으로 SPN 구조와 Feistel 구조로 범주화된다.

2.1.1 Substitution-Permutation Networks(SPNs)

블록암호의 가장 중요한 방법 중 하나는 바로 SPN 이다.
기본적으로, SPN은 평문과 키를 입력값으로 받는다.
우선, 평문 블록은 키 스케쥴링으로부터 얻은 라운드 키와 XOR 연산된다.
이 연산을 $Round\;\;0$ 이라 한다.
이후, 연산된 값은 작은 블록들로 나뉘어지고, 각각의 작은 블록들은 비선형적인 레이어(S-Box)를 통해 confusion을 충족시킨다.
게다가, 위 단계를 거친 후 permutation 연산과 라운드 키와의 XOR 연산을 통해 diffusion 속성도 충족한다.
상기한 일련의 연산과정을 라운드라 부른다.
이러한 라운드들이 반복적으로 적용되며, 최종적으로 암호문을 얻을 수 있다.
아래 그림은 SPN 을 나타낸 것이다.

2.1.1.1 Advanced Encryption Standard (AES)

AES는 가장 유명한 SPN의 예시 이다.
이는 벨기에 암호학자 Vincent Rijmen과 Joan Daemen의 Rijndael 암호의 변형이다.
NIST에서 주관한 AES 공모전에서 우승한 뒤 AES 표준이 되었다.

AES는 키 길이에 따라 세 가지 변형이 있는데, 각각의 키 길이가 128, 196, 256비트이고 라운드 수는 10, 12, 14이다.
각각의 버전은 평문 블록으로 128비트 크기를 갖는다.
우선, 첫 번쨰 라운드 전에 추가적인 AddRoundKey 연산을 한다.
각각의 라운드는 SubByte(SB), ShiftRows(SR), MixColumn(MC), 그리고 AddRoundKey(ARK) 단계로 구성되어 있다.
그리고, 라운드 키는 키 스케쥴링 알고리즘에 의해 매 라운드마다 제공된다.
마지막 라운드에서 MixColumn 연산은 생략한다.
암호화 과정은 아래와 같다.

2.1.2 Feistel Structure

Feistel 구조는 두 번째로 인기있는 블록 암호 구조이다.
독일의 암호학자 Horst Feistel가 IBM에서 일할 때 발명했다.
DES, Blowfish, TEA 등 매우 많은 암호들이 이 구조를 이용한다.
Feistel 구조에서, 암복호화 과정은 매우 비슷하고, 때때로 완전히 동일하기도 하다.
일반적으로, 일반적으로 각 라운드마다 라운드 키를 생성하기 위한 키 스케줄 알고리즘을 $F$ 라 부르며, Feistel Function 이라 부른다.
평문 $P_i$ 는 같은 크기의 $L_i, \; R_i$ 로 나눠지며 아래의 연산을 거친다.

L_{i+1} = R_{i} \\ R_{i+1} = L_{i}\,\oplus\,F(R_i,\,k_i+1)

2.1.2.1 Data Encryption Standrad(DES)

DES는 가장 인기있는 Fiestel Network 이다.
초기에는 Horst Feistel에 의해 Lucifer 라는 이름으로 설계되었다.
이후, NSA(National Security Agency)에 의해 조금 변형되어 DES라는 이름으로 사용되었다.

DES는 56-bit의 키를 이용한다.
하지만, 라운드 키는 48-bit 이다.
평문의 길이는 64-bit이다.
매 라운드마다, 32-bit의 블록은 Feistel Function으로 들어간다.
Feistel Function 내부에서, 32-bit 블록은 48-bit로 확장(expand)된 뒤 48-bit의 라운드 키와 XOR 연산을 진행한다.
그 후 Substitution을 진행하고, S-Box를 통해 32-bit로 압축된다.
마지막으로, Permutation을 한 번 한다.
Feistel Function의 결과값은 이후 다른 블록과 XOR 하고 두 블록은 자리를 바꾼다.
아래는 DES의 개념도이다.

2.2 Lightweight Cryptosystems

DES나 AES같은 블록암호들은 큰 용량의 데이터를 암호화하는 데 쓰인다.
그리고 이는 저장용량의 크기 및 CPU Power에 대한 비용이 커지는 결과로 이어진다.
하지만, 마이크로칩의 기술 발달로 낮은 비용(low cost)로 동작하는 암호 알고리즘에 대한 수요가 생겼다.
이러한 알고리즘들을 경량 알고리즘이라 한다.
일반적으로, 경량화 알고리즘은 블록 암호의 일종이다.
낮은 비용으로 동작해야 하기 때문에 이러한 종류의 암호들은 primitive key generation algorithm을 사용하고, 적은 수의 non-linear truth table을 사용한다.
이러한 구조의 경량화 시스템은 안전하지 않은 것처럼 보인다.
하지만, 경량화 알고리즘들은 많은 라운드 수를 돌면서 차분공격이나 선형공격에 대한 기본적인 보안 정도를 달성한다.

2.2.1 PRESENT

PRESENT 암호는 Andrey Bogdanov, Lars R.Knudsen, Gregor Leander, Axel Poschmann, Yannick Seurin, Matthew J. B. Robshaw, Christof Paar, 그리고 C.Vikkelsoe 에 의해 2007년 세상에 공개되었다.
Ultra-Lightweight Block Cipher 라는 이름으로도 알려져있다.

PRESENT는 SPN 구조를 기반으로 한 블록암호이다.
이는 31 라운드로 구성되며, 평문 블록의 크기는 64-bit 이다.
키 사이즈는 80, 128비트로 두 가지 옵션이 있다.
암호화 과정은 기본적인 SPN과 완전히 동일하다.
매 라운드마다 64비트 평문은 라운드 키와 XOR된다.
XOR 이후 S-Box와 Permutation을 거친다.
31번째 반복이 끝난 뒤, 마지막으로 라운드 키와 XOR 하여 암호문을 얻는다.

[그림 출처](https://www.iacr.org/archive/ches2007/47270450/47270450.pdf)

키 스케쥴링

라운드 키 $k_i$ 는 80 또는 128 비트의 마스터 키로부터 생성된다.
여기서는 80 비트의 키 스케쥴링에 관해서만 논한다.
사용자가 80 비트의 마스터 키를 저장했다고 하자.

K = k_{79}k_{78}\dots k_{0}

키 스케쥴링은 마스터 키를 계속해서 업데이트 해나가는 방식으로 진행된다.
$i$ 번째 라운드 키 $K_i$ 는 마스터 키 $K$ 의 맨 왼쪽(MSB)부터 64비트의 값으로 결정된다.
- $K$ 는 소문자 $k$ 를 갖고, $K_i$ 는 그리스 문자 $\kappa$ 를 갖는 것에 주의하자.
즉,

K = k_{79}k_{78}\dots k_{0} \\ K_i = {\kappa}_{63}{\kappa}_{62}\dots{\kappa}_{0} \\

일떄, $K_i=k_{79}k_{78}\dots{k}_{16}$ 인 것이다.
이 라운드 키 $K_i$ 를 얻은 뒤에는 마스터 키 $K$ 를 왼쪽으로 61 bit 만큼 rotate 시킨다.
이후 $K$ 의 Left-Most Significant 4개 bit를 S-box를 통해 치환한다.
마지막으로, ${k}_{19}{k}_{18}{k}_{17}{k}_{16}{k}_{15}$ 값이 round counter 값과 XOR 된다.
round counter는 각각의 라운드마다 고유하게 결정된 값이다.

키 스케쥴링 과정을 수식으로 정리하면 아래와 같다.
$K$ 가 마스터 키, $K_i$ 는 $i$ 번째 라운드 키, $K'$ 는 새롭게 업데이트 된 마스터 키 라고 할 때,

K == k_{79}k_{78}\dots k_{0} \\ K_i = k_{79}k_{78}\dots{k}_{16} \\ \, \\ K' = \text{rotateLeft\_61bits}(k_{79}k_{78}\dots k_{0}) \\ [k_{79}k_{78}k_{77}k_{76}]=\text{Sbox}[k_{79}k_{78}k_{77}k_{76}] \\ [k_{19}k_{18}k_{17}k_{16}k_{15}]=[k_{19}k_{18}k_{17}k_{16}k_{15}] \oplus\text{round\_coutner}

2.2.2 KeeLoq Block Cipher

KeeLoq 암호는 경량화 블록 암호로 Microchip Technology 회사에 의해 키 없이도 출입하는 시스템, 자동차 인증 시스템 등 무선 인증 어플리케이션에 사용하기 위해 개발되었다.
굉장히 효율적인 하드웨어 구현을 통해 매우 낮은 비용으로 보안 인증을 제공한다.
그렇기에 2007년에 Bogdanov에 의해 Cryptanalysis가 나오기 전까지 해당 필드에서 선호되던 암호였다.

2.2.1 Encryption of KeeLoq

KeeLoq는 경량화 암호 시스템으로, 64비트의 키와 32비트 블록을 사용한다.
이는 528번의 반복되는 라운드와 하나의 키 비트가 매 라운드마다 사용된다.
KeeLoq의 라운드 연산은 NLFSR(Non-Linear Feedback Shift Register)의 반복과 동치이다.
보다 상세하게 이를 수식으로 표현하면,

Y^{(i)}=(y^{i}_{31}, \dots, y^{(i)}_{0}) \in\{0,1\}^{32}

$Y^{(i)}$ 를 라운드 $i\in[0,528)$ 에서 쓰이는 입력값(평문)이라 두자. 그리고,

K=(k_{63}, \dots, k_{0}) \in\{0,1\}^{64}

$K$ 를 키로 두자.

평문 $P=Y^{(0)}$ 은 라운드 0의 입력값이다.
암호문 $C=Y^{(528)}$ 은 528번의 라운드 후의 출력값이다.
라운드 함수는 아래 수식으로 표현될 수 있다.

\phi^{(i)}=NLF(y^{(i)}_{31},y^{(i)}_{26},y^{(i)}_{20},y^{(i)}_{9},y^{(i)}_{1})\,\oplus\,y^{(i)}_{16}\,\oplus\,y^{(i)}_{0}\,\oplus\,k_{i(\bmod64)} \\ \, \\Y^{(i+1)}=(\phi^{(i)}, y^{(i)}_{31},\dots,y^{(i)}_{1})

[그림 출처](https://etd.lib.metu.edu.tr/upload/12621522/index.pdf)

Algebraic Normal Form (ANF)로 NLF함수를 나타내면 아래와 같다.

NLF(x_4, x_3, x_2, x_1, x_0)\,=\,x_4x_3x_2\;\oplus\;x_4x_3x_1\;\oplus\;x_4x_2x_0\;\oplus\;x_4x_1x_0\\\;\oplus\;x_4x_2\;\oplus\;x_4x_0\;\oplus\;x_3x_2\;\oplus\;x_3x_0\;\oplus\;x_2x_1\;\oplus\;x_1x_0\;\oplus\;x_1\;\oplus\;x_0

NLF는 5개의 변수를 입력 받아 $3A5C742E_x$ 값을 출력값으로 내는 함수이다.
다시 말해, $NLF(i)$ 는 상수 $3A5C742E$ 의 $i$ 번째 비트를 출력하는 함수이다.

라운드 역함수는 복호화에 사용되며 아래와 같다. ( $i$ 는 $528$ 에서 시작하여 $1$ 로 내려간다.)

\theta^{(i)}=NLF(y^{(i)}_{30},y^{(i)}_{25},y^{(i)}_{19},y^{(i)}_{8},y^{(i)}_{0})\,\oplus\,y^{(i)}_{15}\,\oplus\,y^{(i)}_{31}\,\oplus\,k_{i-1(\bmod64)} \\ \, \\Y^{(i-1)}=(y^{(i)}_{30},\dots,y^{(i)}_{0},\theta^{(i)})

2.2.2.2 The IFF Protocol based on KeeLoq

KeeLoq를 기반으로 한 두 개의 프로토콜로, Code Hopping과 Identify Friend or Foe (IFF)가 있다.
후자는 필요한 데이터를 수집할 수 있는 기회를 제공한다.
여기서 필요한 데이터란, 예를 들어, Slide Attack을 수행하기 위한 (평문-암호문) 쌍 등이 있다.
??인코더의 범위 내에서 트랜스폰더를 이용해서 데이터를 수집할 수 있다.
??그러므로, 오직 다음의 IFF 프로토콜을 다음 절에서 언급한다.
자동차 인증에서 주로 쓰이는 IFF는 challenge-response 프로토콜로써 encoder(e.g. car key)와 decoder(e.g. car)의 두 파트너 간의 프로토콜이다.

우선, 32-bit 의 challenge가 decoder로부터 encoder로 보내진다.
encoder가 이 challenge를 받으면, KeeLoq로 이를 공유된 키로 암호화하고 decoder에게 암호된 challenge를 다시 보낸다.
그럼 challenge가 암호화 되었음을 아는 decoder는 이 암호된 challenge가 encoder로부터 온 것인지 확인할 수 있다.
결국, 두 암호된 challenge가 동일하면 decoder는 자동차의 잠금을 해제한다.
만약, 두 암호된 challenge가 동일하지 않다면, 인증에 실패했으므로 알람을 울린다.

이 프로토콜에서는 encoder가 신호에 의해 활성화되고, challenge는 encoder가 등장했을 때 자동으로 시작하는 것에 주목할 수 있다.
그러므로, encoder에 대해 배터리나 활성화 버튼 등은 따로 필요 없다.

2.3 Birthday Paradox

Birthday Paradox란 $n$ 개의 서로 다른 객체가 있을 때, $\sqrt n$ 개의 객체를 무작위로 선택하면, 높은 확률( $P>1/2$ )로 충돌이 있을 것이라는 문제이다.
Slide Attack에서는 Slid Pair라는 (평문-암호문) 쌍의 충돌이 필요하다.

2.3.1 Outline of the Birthday Paradox

$P(k)$ 가 $n$ 개의 서로 다른 객체에서 선택된 서로 다른 $k$ 개의 객체들이 모두 다를 확률을 나타낸다고 해보자.
그럼 Pigeonhole Principle(비둘기 집 원리)에 의해 $P(k)=0\;(\text{if}\;\;k>n)$ 이다.
우리는 여기서 $P(k) > \frac{1}{2}\;(\text{if}\;\;k > \sqrt{n})$ 임을 증명하고자 한다.

$P(k)$ 를 수식으로 나타내면 아래와 같다.

P(k) = 1\,\cdot\,(1-\frac{1}{n})\,\cdot\,(1-\frac{2}{n})\,\cdots\,(1-\frac{k-1}{n})

이를 Maclaurin expansion (매클로린 급수)로 표현하면 아래와 같다.

e^{x}=\sum\limits_{r=0}^{\infty}{\frac{x^r}{r!}}\, =\,1\,+\,x\,+\,\frac{x^2}{2!}\,+\,\frac{x^3}{3!}\,+\,\cdots

그러므로 우리는 아래의 근사를 쓸 수 있다.

e^x \approx 1+ x

따라서,

e^{-x} \approx 1-x

이 근사를 사용하면, $P(k)$ 를 다음과 같이 추정할 수 있다.

P(k) \approx1\,\cdot\,e^{-1/n}\,\cdot\,e^{-2/n}\,\cdots\,e^{-(k-1)/n}\,\cdot\, \\ =e^{\frac{-1\,\cdot\,(1+2+\cdot\cdot+(k-1))}{n}} \\ =e^{\frac{-k\,\cdot\,(k-1)}{2n}} \\ \approx e^{\frac{-k^2}{2n}}

이 때, 최소한 50%의 확률로 충돌이 일어나게 하는 $k$ 값을 찾고자 한다.
즉, $P(r)\,<\,\frac{1}{2}$ 를 일으키는 최소한의 $\forall\,r\;\ge\;k$ 를 찾고자 한다.
그러므로 아래 부등식을 풀어야 한다.

e^{\frac{-k^2}{2n}}\,<\,\frac{1}{2}

양 변에 자연로그를 잡고 풀면 아래와 같다.

-\frac{k^2}{2n} < -\ln2 \\ \, \\ \leftrightarrow \frac{k^2}{2n} > \ln2 \\ \, \\ \leftrightarrow k^2 > 2\ln2 \cdot n \\ \, \\ \leftrightarrow k > \sqrt{2\ln2 \cdot n} \approx \sqrt{n}

Chapter 3. Slide Attack

Slide Attack은 블록 암호에 적용되는 암호 공격 기법이다.
블록 암호는 보통 라운드 수를 증가시켜서 차분 공격과 선형 공격에 대한 안전성을 같이 증가시킨다.
이러한 공격방법들과는 반대로, Slide Attack은 라운드 수에 독립적이다.
본 논문에서는 Slide Attack에 대해 깊이 파고들어 수학적 관점에서까지 확장한다.
본 절에서는 Slide Attack이 동작하는 방법을 자세히 살펴본다.

우선, 라운드 수가 $r$ 인 블록 암호가 있다고 가정하자.
공격을 수행하기 위해서는 블록 암호가 약한 키 스케쥴링을 한다고 가정한다.
기본적인 시나리오에서는 암호화 과정 $E$ 가 동일한 키에 의존하는 함수 $F$ (하나 이상의 라운드 일 수 있음)의 결합으로 표현되며, 아래와 같이 쓸 수 있다.

E\;:\;F\,\circ\,F\,\circ\,\cdots \circ\,F\,\circ\,F\,=\,F^s

또한, 다음의 두 (인풋-아웃풋) 쌍을 알고 있을 때 키 $k$ 를 쉽게 복원할 수 있다는 가정도 필요하다.

F_k(x_1) = y_1 \\ F_k(x_2) = y_2

이러한 가정들을 토대로, 암호화 함수(알고리즘)을 수식으로 표현하면 아래와 같다.

E_k\,:\,F^{s}_{k}\,:\,\mathbb{Z}^{n}_{2}\,\rightarrow\,\mathbb{Z}^{n}_{2}

$F_{k}$ 하나가 $r$ 라운드의 함수라고 하면, 전체 암호화 함수는 $F^{s}_k$ 이므로, 전체 라운드 수는 $r\,\cdot\,s$ 가 된다.
$\mathbb{Z}^{n}_{2}$ 에서의 $n$ 은 블록의 크기를 의미한다.
이러한 암호를 성공적으로 공격한다는 의미는 $F_k$ 에서 사용하는 키 $k$ 를 얻는다는 의미이다.
공격은 아래의 조건을 만족하는 (평문-암호문)쌍 ( $(P_i, C_i)\,,\;(P_j, C_j)$ )을 찾았을 때, 함수 $F$ 에 대해 가정했던 취약점(키를 쉽게 복원할 수 있다는 가정)을 통해 키 $k$ 를 복원하는 것을 목표로 한다.

\text{for}\;\;E_k(P_i) = C_i\,,\;\;E_k(P_j) = C_j \\ F_k(P_i) = P_j \\ F_k(C_i) = C_j \\

정의 3.1

$E_k$ 를 $E_k=F^{s}_{k}$ 라 하자(라운드 수는 $F_k$ 의 라운드 수가 $c$ 일 때, $c\,\cdot\,s$ ).

그리고 $C_i=E_k(P_i),\,C_j=E_k(P_j)$ 임을 가정한다.

이 때, $F_k(P_i) = P_j\,,\;\;F_k(C_i) = C_j$ 를 만족하는 두 평문, 암호문 쌍 $(P_i, C_i)\,,\;(P_j, C_j)$ 를
Slid Pair라 부른다.

위 개념을 시각적으로 보이면 아래와 같다.

그림에서 볼 수 있듯이, 두 암호화 과정에서 한 과정을 옆으로 밀어 놓은(slide) 형태이다.

평문 $P$ 에 대한 암호문 $C$ 의 $(P,\,C)$ 가 가질 수 있는 경우의 수가 $2^n$ 임을 생각해보자.
라운드 함수를 $F$ 라 할 때, $P'=F(P)$ 인 $P'$ 는 결정되어 있다.
따라서, $((P_i, C_i)\,,\;(P_j, C_j))$ 는 경우의 수로 $2^n\,\cdot\,2^n\,=\,2^{2n}$ 을 가지고, 이 때 Slid Pair는 $(P_i, C_i)$ 와 $(P_{i}^{'},\,C_{i}^{'})$ 이므로 $2^n$ 을 가진다.

따라서, Slid Pair를 찾기 위해서는 모든 $2^{2n}$ 개의 페어를 찾아야만 한다.
이는 힘든 작업이지만, 공격을 위해서는 이뤄야만 하는 부분이다.

Birthday Paradox에 따르면 $\sqrt{2^{n}}=2^{n/2}$ 개의 무작위로 선택된 (평문-암호문) 쌍은 최소한 하나의 slid pair를 갖고 있을 것으로 기대된다.
그러므로, 공간 복잡도는 $2^{n/2}$ 이고 시간 복잡도는 $2^n$ 이므로 Slide Attack은 유용하지 않은 것으로 보인다.

Slide Attack의 주요 이슈는 이러한 복잡도와 비용을 줄이는 것이다.
Birthday Paradox는 공간 복잡도를 줄이는 적절한 접근이다.
반면, F 함수의 속성을 이용하면, 시간 복잡도를 줄이기 위한 Filtering Condition을 정의할 수 있다.

시간복잡도를 줄이기 위해 두 가지 Alternative Slide Attack 방법이 있다.
각각 Complementation Slide와 Sliding with a Twist이다.
일반적으로 이들은 키 스케쥴링이 동일하지 않은 라운드 키를 제공할 때 filtering condition을 찾는데 더욱 효과적이다.

Complementation Slide Attack

Complementation Slide Attack은 Slid Pairs 사이에서 filtering condition을 찾는 것을 목표로 한다.
만약 키 스케쥴 알고리즘이 $K_0$ 와 $K_1$ 라는 서로 다른 두 라운드 키만을 생성한다면, Slid Difference 라고 부르는 $\Delta=K_0\oplus K_1$ 를 계산한다.
이 $\Delta$ 값은 평문 쌍과 암호문 쌍에서도 그대로 보존된다.
아래 수식을 통해 이를 확인할 수 있다.

\langle P^{'}_{L}, P^{'}_{R} \rangle = \langle P_{R}, P_{L} \oplus f(K_0 \oplus P_{R}) \rangle \oplus \langle \Delta , \Delta \rangle \\ \, \\ \langle C^{'}_{L}, C^{'}_{R} \rangle=\langle C_R, C_L\oplus f(K_1 \oplus C_R \oplus \Delta)\rangle \oplus \langle \Delta, \Delta \rangle

[그림 출처](https://www.iacr.org/archive/eurocrypt2000/1807/18070595-new.pdf)

그러므로, $n/2$ 비트에 대한 filtering condition이 위 식으로부터 얻어진다.
이를 수식으로 표현하면 아래와 같다.

P^{'}_{L} \oplus C^{'}_{L}=P_{R} \oplus C_{R}

따라서, slid pair를 찾으면 $\Delta$ 를 추출할 수 있고, 모든 라운드 키를 위 식을 통해 복원할 수 있다.

Sliding with a Twist