현대 암호학 #6

케이요·2021년 10월 25일

대학원 수학 암호학 현대 암호학

현대 암호학

목록 보기

6/6

2021-10-11-현대암호학-6주차.md

Mode of Operations

Mode of Operations

운영 모드 (Mode of operation)
- 블록 암호는 정해진 길이의 블록만 처리 가능
  - ASCII 코드 사용 시 DES (64비트 = 8문자), AES (128비트 = 16문자)
  - 실제 사용하는 평문은 블록 크기보다 더 큰 데이터인 경우가 많음
- 블록 암호를 사용하여 다양한 크기의 데이터를 암호화하는 방식
  - 암호(cipher) : 암호 알고리즘을 이루는 요소 ex) DES, AES
  - 암호 알고리즘(encryption algorithm) : 실제 암호화를 위한 알고리즘 ex) 운영모드
NIST 권장 5가지 운영 모드
- NIST SP 800-38A: Recommendation for Block Cipher Modes of Operation
  - ECB (Electric CodeBook) 모드
  - CBC (Cipher Block Chaining) 모드
  - CFB (Cipher FeedBack) 모드
  - OFB (Output FeedBack) 모드
  - CTR (CounTeR) 모드
평문 / 암호문 블록
- 각 운영 모드는 $N$ 개의 평문 블록 $P_1, ..., P_N$ 을 입력 받고 $N$ 개의 암호문 블록 $C_1, ..., C_N$ 을 출력함
- 평문의 길이가 블록의 배수가 되지 않는다면?

Padding

패딩 (Padding)
- 데이터 마지막 부분의 빈 공간을 채워 완전한 블록으로 만드는 작업
  - 대부분의 경우 평문의 길이는 정확히 블록 크기의 배수가 되지 않음
  - 패딩이 사용되면, 수신자는 복호화와 함께 패딩을 제거하는 방법을 알아야 함
제로 패딩 (Zero Padding, Null Padding)
- 가장 기본적인 패딩 방법
- 부족한 길이 만큼 0 (null 문자)을 채움
  - C.f.) 0x00을 패딩하는 것은 0을 8번 채우는 것과 같음
- But 평문 마지막이 0x00으로 끝나는 경우 복호화 과정에서 함께 제거됨
  (= 패딩의 크기를 알 수 없음)
비트 패딩 (Bit Padding)
- 단일 비트 1을 패딩 값의 최상위 비트로 사용
- 나머지 비트는 0으로 채움
  - C.f.) 0x80 을 패딩 하는 것은 비트열 1000 0000을 채우는 것과 같음
- 메시지가 블록 크기의 배수일 경우
  - 패딩을 하지 않으면 메시지의 일부를 패딩으로 인식하여 제거하게 됨
  - 한 블록 전체를 비트 패딩하는 것이 필요함 (이후 나오는 패딩들도 동일)
바이트 패딩 (Byte padding)
- 최하위 바이트에 패딩된 길이를 표시하여 원본 메시지와 패딩 값을 구분
  - 비트 패딩과 동일하게 메시지가 블록 크기의 배수일 경우 한 블록 전체를 바이트 패딩 해야 함
PKCS#7 패딩
- 추가되어야 하는 패딩 바이트 크기로 패딩 값을 사용
  - 공개키 암호 표준 프로토콜 (public-key cryptography standard) 7번째 문서에 수록
  - 마찬가지로 메시지가 블록 크기 배수이면 한 블록 전체 패딩

ECB Mode

ECB (Electronic cod book) 모드
- 단일 평문 블록에 대하여 동일한 키를 사용하여 단일 암호문 블록을 생성
  - 암호화: $C_i = Enc_k(P_i)$
  - 복호화: $P_i = Dec_k(C_i)$
ECB 모드 특징
- 독립적인 암호화 과정
  - 임의의 순서로 암호화 가능
  - 병렬처리가능
- 같은 평문에 대한 암호문이 항상 일정함
  - 결정적 암호 알고리즘 (deterministic encryption algorithm)
ECB 모드 안전성
- 블록 단위의 패턴 유지
  - 알려진 평문과 암호문쌍을 이용하여 블록의 패턴을 파악할 수 있음
  - 반복적으로 사용되는 메시지 & 정해진 구조를 가지는 메시지를 식별 가능
- 블록 재사용 (Block Replay) 공격
  - 키를 모르더라도 복사 및 덮어쓰기를 통해 원하는 대로 암호문을 수정 가능
ECB에서의 CTS(Ciphertext Stealing) 기법
- CTS(Ciphertext Stealing, 암호문 스틸링) 기법
  - 패딩 메시지 크기 = 암호문 크기 > 원본 메시지 크기
  - 패딩 대신 암호화된 이전 메시지 블록의 뒷부분을 가져와서 덧붙이는 방식
  - 데이터의 크기에 따라 통신 비용이 결정되는 환경에서 유용하게 사용
  - $T_{N-1} = Enc_K(P_{N-1}) → C_N = head_m(T_{N-1})$
  - $T_N = P_N | tail_{n-m} → C_{N-1} = Enc_K(T_N)$
ECB 모드에서 오류 확산
- 암호문 생성 또는 메시지를 전송하는 과정에서 예상치 못한 에러가 발생 가능
- ECB 모드에서는 에러가 발생한 블록 외 다른 블록의 비트는 영향을 받지 않음
  - 블록들 간 암/복호화 과정이 독립적이기 때문임
  - 오류 확산이 없다고 표현함 (여기서 오류 발생 블록은 확산된 건 아니니까)
ECB 모드 활용
- 하나의 평문을 한 번 암호화하는 제한적인 경우에만 사용이 권고됨
- 세션키 암호화와 같이 매우 특별한 용도로만 사용

CBC Mode

CBC (Cipher block chaining) 모드
- 평문 블록을 바로 앞 블록의 암호문과 XOR 연산 후 암호화하여 암호문 블록 생성
  - 암호화: $C_i = Enc_k(P_i \oplus C_{i-1}), C_0 = IV$
  - 복호화: $P_i = Dec_k(C_i) \oplus C_{i-1}, C_0 = IV$
CBC 모드 특징
- 초기 벡터 (Initialization Vector, IV) 사용
  - 첫 번째 평문 블록을 암호화하기 위해 사용
  - $IV$ 는 $C_0$ 으로 두고 암호문과 함께 전송
- 병렬 처리 복호화
  - 암호화 과정은 순차적으로 이뤄져야 하므로 병렬 처리가 불가능함
  - 복호화 과정은 암호문들이 다 주어지므로 병렬 처리 가능
CBC 모드 안전성
- 확률적 암호 알고리즘 (probabilistic encryption algorithm)
  - 암호화 할 때마다 초기 벡터를 바꿔서 임의화(randomization) 제공
  - 같은 평문이 암호화될 때 마다 통계적으로 독립된 다른 암호문이 생성
- 초기 벡터 설정
  - 논스(Number used only once, Nonce)를 생성하여 IV로 사용
    1. 송신자가 난수를 만들어 그대로 수신자에게 전송
    2. 서로 동기화된 카운터를 사용
  - 실제 환경에서는 기밀성보다 무결성이 더 중요함
- 연결성(Chaining)
  - 모든 블록들이 연결되어 있으므로 블록끼리 더 이상 독립적이지 않음
  - 평문 내 동일한 블록( $P_i = P_j$ )에 대응하는 암호문 블록도 서로 다름( $C_i ≠ C_j$ )
  - ECB 모드에서 보이는 블록 패턴들이 더 이상 보이지 않음
  - 블록단위의 재사용이 불가능 함
CBC 모드에서의 오류 확산
- 암호문 전송 중 오류( $C_i$ )가 발생하여도 해당 블록과 다음 블록에만 영향을 줌
  - i번째 블록 복호화 : $Dec_k(C_i) \oplus C_{i-1} = P_i$
  - i+1번째 블록 : $Dec_k(C_{i+1}) \oplus C_i = P_{i+1}$
  - i+1번째 이후 : $Dec_k(C_{i+2}) \oplus C_{i+1} = P_{i+2}$ ( $C_i$ 영향 없음)
  - 자기 복구 (self-recovering): 그 다음 블록까지 오류가 전파되지 않고 복호화가 됨

CFB Mode

CFB (Cipher feedback) 모드
- 평문 블록을 바로 앞 암호문 블록이 암호화된 결과와 XOR하여 해당 암호문 블록 생성
- 블록 암호를 스트림 암호로 변환
  - 블록 암호를 직접 이용하지 않고 키 스트림 생성기(KSG)를 구현하는 데 이용
  - 암호화: $C_i = P_i \oplus s_i, s_i = KSG(k, C_{i-1}), C_o = IV$
  - 복호화: $P_i = C_i \oplus s_i, s_i = KSG(k, C_{i-1}), C_0 = IV$
CFB 모드 특징
- 블록 사이즈와 상관없이 암호화 단위를 가변적으로 선택 (= 패딩이 필요 없음)
- 키 스트림 생성기 사용
  - 쉬프트 레지스터를 이용하여 원하는 크기의 비밀 키를 생성
CFB 모드 안전성
- 초기벡터 IV 재사용 문제
  - IV는 비밀일 필요는 없지만 유일하게 사용해야 함
  - 동일한 IV를 반복해서 사용했다면 첫번째 블록에 대하여 차분분석이 가능함
  - $C_1 = P_1 \oplus Enc_k(C_0), C'_1 = P'_1 \oplus Enc_k(C_0)$
    - $\therefore C_1 \oplus C'_1 = P_1 \oplus P'_1$
CFB 모드 오류확산
- 전송 중에 발생한 오류(1비트)는 쉬프트 레지스터를 빠져 나올 때까지 영향을 줌
  - 자기 동기식 (self-synchronizing) : 일부분 실패 이후 다시 정상적인 복호화 가능 (= 특정 길이 이상의 암호문이 있으면 키 스트림이 자동으로 동기화)

OFB Mode

OFB (Output feedback) 모드
- 스트림 암호
- 쉬프트 레지스터에 이전 평문 블록과의 XOR 연산에 사용된 키 스트림을 채움
  - CFB에서는 쉬프트 레지스터에 이전 암호문 블록을 채움
  - 암호화: $C_i = P_i \oplus s_i, s_i = KSG(k, s_{i-1}), s_0 = IV$
  - 복호화: $P_i = C_i \oplus s_i, s_i = KSG(k, s_{i-1}), s_0 = IV$
OFB 모드 특징 및 오류 확산
- 키 스트림이 평문 & 암호문과 독립적으로 생성됨
  - 사전에 미리 키 스트림 값을 계산할 수 있음
  - 평문의 오류는 암호문의 같은 위치에서만 나타남 (= 오류가 파급되지 않음)
  - 동기식 스트림 암호 (synchronizing stream cipher) : 정상적인 복호화를 위해서는 키 스트림이 동기화 되어야 함
OFB 모드 안전성
- 항상 다른 IV를 사용해야 함
  - 재사용 시 모든 블록에 대하여 차분 정보 노출 (HW3 2번)

CTR Mode

CTR (Counter) 모드
- 스트림 암호
- 피드백 없이 평문 블록과 키 스트림을 XOR 연산하여 암호문 블록 생성
- 카운터 값으로 키 스트림을 독립적으로 생성
  - 카운터 값은 IV로 초기화되고 정의된 규칙으로 변화
  (간단한방법: $ctr := ctr + 1$ )
  - 암호화: $C_i = P_i \oplus Enc_k(ctr)$
  - 복호화: $P_i = C_i \oplus Enc_k(ctr)$
CTR 모드 특징
- ECB 모드와 OFB 모드의 장점을 모두 가지고 있음 (= 병렬처리 & 전처리 가능)
- n비트 블록이 입력될 때 까지 처리 불가능 (키 스트림을 그대로 사용할 경우)
- 카운터 값은 공개되므로 블록의 순서와 상관없이 복호화 가능
CTR 모드 안전성
- IV 재사용 불가
  - OFB와 동일하게 모든 블록에 대하여 차분 정보가 노출
CTR 모드 오류확산
- OFB모드와 동일
- 평문과 암호문의 한 비트 오류는 각각 대응되는 암호문과 평문의 한 비트에만 영향