Week 3 - 3DES, AES, 스트림 암호화

1️⃣ 3DES (트리플 DES)

💡 특징

• 168비트 키 길이:
• DES는 원래 56비트 키를 사용하지만, 3DES에서는 DES를 3번 적용하면서 56비트 키 3개를 사용하여 총 168비트의 키 길이를 가진다.
• 이를 통해 DES에 비해 보안성을 높이며, 무차별 대입 공격(Brute Force Attack)에 대한 저항성을 강화했다.

• 근본적인 암호화 알고리즘은 DES와 동일:
• 3DES는 DES의 알고리즘 자체를 사용하지만, 이를 세 번 반복해 암호화-복호화-암호화 과정을 거친다. 이를 통해 기존 DES에 비해 암호화 과정이 훨씬 복잡해졌다.

🔍 암호화 과정

• 암호화(E)-복호화(D)-암호화(E):
• 3DES는 일반적으로 키 를 사용하여 다음과 같은 방식으로 암호화를 수행한다:
1. 첫 번째 암호화: 로 평문을 암호화.
2. 두 번째 복호화: 로 암호문을 복호화.
3. 세 번째 암호화: 로 다시 암호화.
• 키가 2개일 경우, 로 설정하여 두 개의 키만 사용하기도 한다.

🔍 문제점

• 소프트웨어 성능 저하:
• 3DES는 DES 알고리즘을 3번 반복하기 때문에 연산량이 증가하고, 이로 인해 소프트웨어적으로 구현했을 때 성능이 떨어지는 문제가 있다.

• 64비트 블록 크기:
• 3DES는 여전히 64비트 블록 크기를 사용한다. 이는 대량의 데이터를 암호화할 때 블록의 반복 패턴이 생길 수 있어 보안에 취약할 수 있다.

• 하드웨어 구현의 한계:
• DES는 하드웨어에서 쉽게 구현할 수 있도록 설계되었으나, 3DES는 복잡한 연산으로 인해 하드웨어로 구현할 경우 성능에 한계가 있다.

2️⃣ AES

📌 AES의 기본 특성과 암호화 과정

• 블록 길이: 128비트 블록 단위로 암호화가 이루어진다.

• 키 길이: AES는 128, 192, 256비트 키를 사용할 수 있으며, 일반적으로 128비트 키가 많이 사용된다.

• Feistel 구조가 아님: AES는 Feistel 구조가 아닌 Substitution-Permutation Network (SPN) 구조를 따른다. 이는 파이스텔 구조와 달리, 블록 전체에 대한 비선형 대체와 순열을 적용한다.

1. 128비트 입력 데이터:
• 128비트 입력 데이터를 8비트 × 16개의 토막으로 분리한다. 이를 16바이트의 상태 행렬로 구성한다.

2. 라운드 키 추가 (Add Round Key):
• 라운드 키는 초기 입력 키로부터 키 스케줄링을 통해 생성된 각 라운드의 키이다.
• 초기 상태에서 첫 번째 Add Round Key 연산을 통해 입력 데이터와 키의 XOR 연산을 수행한다.

3. AES 암호화 라운드:
• 총 10회 라운드(키 길이에 따라 더 많을 수도 있음)를 수행하여 암호화를 완성한다.
• 각 라운드는 다음과 같은 단계로 구성된다:
1. Substitute Bytes (S-박스 대체): S-박스를 사용하여 비선형 대체를 수행해 데이터의 예측 가능성을 줄인다.
2. Shift Rows (행 이동): 각 행을 왼쪽으로 순환 이동하여 데이터를 섞는다.
3. Mix Columns (열 혼합): 데이터를 열 단위로 혼합하여 더 복잡하게 변형한다. 이 단계는 마지막 라운드에서 생략된다.
4. Add Round Key (라운드 키 추가): 라운드 키와 상태를 XOR하여 추가적인 보안을 제공한다.

4. Add Round Key 단계에서만 키 사용:
• 라운드마다 Add Round Key 단계에서 라운드별로 다른 키가 사용된다. 각 라운드는 키 스케줄링에 의해 확장된 키를 사용하며, 이를 통해 매 라운드마다 데이터가 고유하게 변형된다.

📌 각 라운드 구조

1. SubBytes (S-박스 대체)

• SubBytes 단계에서는 입력된 각 바이트를 S-박스를 사용해 비선형적으로 대체한다.

• S-박스는 16×16 크기의 치환 표로, 각 입력 바이트를 고유한 다른 값으로 변환한다. 이는 암호화의 비선형성을 제공해 암호문을 더 예측 불가능하게 만든다.

• 이 단계는 각 바이트에 독립적으로 적용되며, 암호문의 균일한 패턴을 제거하여 공격자가 원래 데이터를 추정하기 어렵게 한다.

2. ShiftRows (행 이동)

• ShiftRows 단계에서는 상태 행렬 내의 각 행을 왼쪽으로 순환 이동한다. 이는 데이터의 바이트 순서를 섞어 암호문의 예측 가능성을 줄이는 데 기여한다.
• 첫 번째 행은 그대로 유지된다.
• 두 번째 행은 한 번 왼쪽으로 이동한다.
• 세 번째 행은 두 번 왼쪽으로 이동한다.
• 네 번째 행은 세 번 왼쪽으로 이동한다.

• 이 과정은 바이트 간의 관계를 복잡하게 만들어, 동일한 바이트 패턴이 남지 않도록 한다.

3. MixColumns (열 혼합)

• MixColumns 단계에서는 각 열을 수학적으로 변환하여 데이터 간의 상호작용을 증가시킨다.

• 고정된 행렬과의 곱셈을 통해 각 열을 변환하게 되는데, 이 연산은 Galois Field(유한체)에서 이루어진다. 각 바이트는 열의 다른 바이트와 상호작용하여 새로운 바이트 값으로 변경된다.

• 이 과정은 암호문의 확산을 증가시키고, 블록 전체의 데이터를 더 복잡하게 섞어 암호문의 안전성을 높이는 역할을 한다.

• 마지막 라운드에서는 MixColumns 단계는 생략된다.

4. AddRoundKey (라운드 키 추가)

• AddRoundKey 단계에서는 상태 행렬의 각 바이트에 해당 라운드의 라운드 키를 XOR 연산으로 결합한다.

• 이 라운드 키는 초기 입력 키로부터 키 스케줄링 알고리즘을 통해 생성된 것으로, 각 라운드마다 다른 키를 사용한다.

• XOR 연산은 데이터를 비밀키와 결합하여 데이터를 암호화하고, 각 라운드마다 다른 키가 사용되기 때문에, 매 라운드 결과가 서로 달라져 공격자가 추적하기 어렵게 된다.

3️⃣ 유용한 보안 이슈

📌 ECB (Electronic Codebook)

1. ECB(Electronic Codebook) 모드는 가장 단순한 블록 암호 방식이다.
• 각각의 평문 블록은 동일한 키로 암호화되며, 같은 평문 블록은 항상 같은 암호문을 생성한다.
• 이 때문에, 만약 데이터에 반복되는 패턴이 있다면 암호문에서도 이 패턴이 그대로 남는다.
• 암호 해독자는 암호문에 있는 규칙을 쉽게 이용할 수 있다. 예를 들어, 반복되는 데이터가 있을 경우 동일한 블록이 동일하게 암호화되므로 이를 통해 평문의 구조를 유추할 수 있다.

2. 운용 모드와 ECB 취약점 극복
• 운용 모드는 대형 시퀀스에 대한 대칭키 블록 암호화의 보안을 향상시키기 위해 고안된 방법들이다. 각 운용 모드는 ECB 모드의 보안적 약점을 극복하기 위한 방안을 제공한다.
• ECB 모드의 취약점을 극복하기 위해, 여러 가지 운용 모드(예: CBC, CFB, OFB, CTR 등)가 제안되었다.
• 예를 들어, CBC(Cipher Block Chaining) 모드는 이전 블록의 암호문을 다음 블록의 평문과 XOR 연산하여 패턴이 나타나지 않도록 한다. 이로 인해 반복되는 패턴이 사라지며, 암호문이 더 안전해진다.

4️⃣ 스트림 암호화

• 의사 난수 (Pseudorandom) 비트 생성기: 의사 난수 비트 생성기는 스트림 암호화에서 매우 중요한 역할을 한다. 키 스트림을 생성하기 위해 의사 난수 생성기를 사용하며, 이 키 스트림은 평문과 XOR 연산을 통해 암호문을 만든다.
1. 숫자와 같은 랜덤 스트림 생성: 의사 난수 생성기는 마치 랜덤한 숫자처럼 보이는 랜덤 스트림을 생성한다. 이는 진짜 난수는 아니지만, 충분히 예측 불가능한 형태로 만들어지는 값이다.
2. 입력 키 없이는 예측 불가능: 입력 키가 없다면, 생성된 키 스트림을 예측하는 것은 매우 어렵다. 이는 스트림 암호화의 보안성을 유지하는 중요한 요소이다.
3. 평문 바이트로 XOR 키 스트림이 출력: 평문 데이터는 생성된 키 스트림과 XOR 연산을 통해 암호화된다. 복호화할 때도 동일한 키 스트림과 암호문을 XOR 연산하여 평문을 복원한다.

• 설계 고려사항
1. 암호화 시퀀스의 주기: 암호화 시퀀스가 충분히 길어야 한다. 키 스트림이 반복되면 보안성이 떨어지므로, 주기가 긴 의사 난수 생성기를 사용해야 한다.
2. 키 스트림의 속성: 키 스트림은 랜덤 숫자의 속성과 유사해야 한다. 이는 공격자가 키 스트림을 예측하거나 패턴을 발견하는 것을 어렵게 만든다.
3. 충분한 길이의 키 사용: 충분한 길이의 키를 사용하여 보안성을 강화해야 한다. 키의 길이가 짧을 경우, 무차별 대입 공격을 통해 키를 추정할 가능성이 높아진다.

💡 블록 암호화 vs 스트림 암호화

1. 데이터 처리 단위:
• 블록 암호화는 고정된 크기의 블록 단위로 데이터를 처리한다.
• 스트림 암호화는 연속적인 비트 또는 바이트 단위로 데이터를 처리한다.

2. 암호화 방식:
• 블록 암호화는 입력 데이터를 고정 크기 블록으로 나누고, 각 블록을 독립적으로 암호화한다.
• 스트림 암호화는 키 스트림을 사용해 데이터를 비트 단위로 XOR 연산하며, 실시간으로 데이터를 암호화하는 데 적합하다.

3. 보안성:
• 블록 암호화의 경우, 특정 운용 모드(예: ECB 모드)를 사용할 때 반복되는 패턴이 암호문에서 드러날 수 있어 보안 취약점이 발생할 수 있다.
• 스트림 암호화는 키 스트림이 충분히 랜덤하다면 보안성이 높지만, 키 스트림이 반복되거나 예측 가능할 경우 보안 취약점이 생길 수 있다.

4. 적용 사례:
• 블록 암호화는 일반적으로 파일 암호화, 데이터베이스 암호화 등에서 사용된다.
• 스트림 암호화는 네트워크 통신, 음성 데이터와 같이 연속적인 데이터 흐름을 다루는 상황에서 많이 사용된다.

5️⃣ RC4 (Rivest Cipher 4) 알고리즘

📌 RC4의 동작 원리

1️⃣ 초기화 단계

• S 배열: 크기가 256인 배열로, 0부터 255까지의 숫자로 초기화된다.

• T 배열: 비밀 키를 기반으로 초기화된 배열로, S 배열의 초기 순열을 설정하기 위해 사용된다.

1. S 배열 초기화: S[i] = i로 초기화된다. 여기서 i는 0부터 255까지의 인덱스를 가진다.

2. T 배열 초기화: 키 길이에 맞춰 T[i]는 비밀 키(k)의 반복된 값으로 초기화된다.



for i = 0 to 255 do
S[i] = i;
T[i] = K[i mod keylen];

3. S 배열 섞기 (Key Scheduling Algorithm, KSA):



• j 값을 반복적으로 업데이트하면서 S 배열의 값을 섞는 작업을 수행한다.
• j = (j + S[i] + T[i]) % 256를 계산한 후, S[i]와 S[j]를 교환한다.
• 이를 통해 비밀 키에 기반한 초기 순열이 S 배열에 설정된다.

/* Initial Permutation of S */
j = 0;
for i = 0 to 255 do
	j = (j + S[i] + T[i]) mod 256;
	Swap(S[i], S[j]);

2️⃣ 키 스트림 생성 단계 (Pseudo-random Generation Algorithm, PRGA)

• 키 스트림 생성 과정:
1. S 배열의 두 인덱스 i와 j를 사용하여 반복적으로 값을 업데이트한다.
2. i는 i = (i + 1) % 256으로 증가하고, j는 j = (j + S[i]) % 256으로 업데이트된다.
3. S[i]와 S[j]를 교환한 후, 키 스트림의 다음 값 t는 S[i] + S[j]로 결정된다.
4. 키 스트림 값 S[t]가 생성되며, 이는 평문과 XOR 연산을 수행하여 암호문을 생성한다.

/* Stream Generation */
i, j = 0
while (true)
	i = (i + 1) mod 256;
	j = (j + S[i]) mod 256;
	Swap(S[i], S[j]);
	t = (S[i] + S[j]) mod 256;
	k = S[t];

📌 RC4의 특징

1. 쉬운 구현: 단순한 구조와 빠른 실행 속도로 인해 소프트웨어적으로 구현하기 쉽다. 이는 RC4가 네트워크 통신 등에서 널리 사용되었던 이유 중 하나이다.

2. 셔플링 기법 기반: RC4는 셔플링 기법을 사용하여 S 배열을 섞고, 이를 통해 키 스트림을 생성한다. 이 방식은 간단하면서도 비밀 키에 의한 보안성을 제공한다.

3. 비트 단위 스트림 암호화: RC4는 1바이트 단위로 스트림을 암호화하며, 평문의 각 바이트가 키 스트림의 해당 바이트와 XOR 연산을 통해 암호화된다.

• RC4는 과거에 널리 사용되었으나, 시간이 지나면서 보안 취약점이 발견되었다. 특히 초기 몇 바이트의 키 스트림이 약하다는 문제로 인해 다양한 키 복구 공격이 가능해졌다.

• 현재는 AES와 같은 더 강력한 암호화 알고리즘이 RC4를 대체하고 있다.