Chap 4. 관용 암호 방식 알고리즘

4.1 3중 DES DES의 brute-force 공격에 대한 잠재적인 취약성 => 대안책 필요 기존의 소프트웨어와 장비에 암호화 강화 DES + 다중키 => 다중 암호화 => Triple DES

2중 DES C=EK2[EK1[P]] P=DK1[DK2[C]]

DES의 56비트 키 K1과 K2에 대해서 K3가 존재 한다고 가정 키의 길이 56 * 2 = 112 암호학적 강도 강화 단일 단계로의 축소 DES의 56비트 키 K1과 K2에 대해서 K3가 존재 한다고 가정 EK2[EK1[P]]=EK3[P] 1992년 가정이 증명됨

중간 결과에 의한 공격 X=EK1[P]=DK2[C] 평문 P를 2^56개의 가능한 모든 키 K1으로 암호한 다음 결과를 테이블로 저장 암호문 C를 키 K2의 가능한 모든 2^56개의 값으로 복호화

3키에 의한 3중 DES 3단계 암호화 과정을 이용 기지 평문 공격의 복잡도 2^112 현실성 없는 공격법 => 공격 불가능 문제점 56*3 = 168 비트의 키를 사용 사실상 사용하기가 어려움

2키에 의한 3중 DES

1979년 Tuchman 에 의해 제안 키 관리 표준 ANS X9.17과 ISO 8732에 의해 채택 현재까지 실용적인 암호 분석 공격이 없음 Coppersmith Brute-force 공격 : 2^112 = 5*10^33 차수로 가능 차분 암호 해독은 단일 DES와 비교하여 10^52이 넘는 지수적인 복잡도를 가짐 장래의 성공적인 공격 가능 유형 Merkle & Hellman OORS 90

4.2 국제 데이터 암호 알고리즘(IDEA : International Data Encryption Algorithm) 스위스 연방 기술 연구소의 Xueja Lai와 James Massey에 의해 1990년에 개발 DES를 대체하기 위해 제안된 관용 암호 알고리즘 중 하나 E-mail 암호를 위한 PGP에 포함 설계원리 64비트 블록의 데이터 입력 128비트의 키를 사용 블록 암호

암호학적 강도 블록길이 통계적 분석을 막을 수 있을 만큼 길어야 함 64비트의 블록이면 충분 키의 길이 모든 키의 탐색(Exhaustive Search)을 효율적으로 막을 수 있을 만큼 커야 함 128비트면 향후에도 안전할 것이라고 여겨짐 혼돈 목적 : 암호문의 통계적 성질이 평문의 통계적 성질에 의존하는지에 대한 결정을 복잡하게 만드는 것 세가지 연산 : XOR, 덧셈, 곱셈 확산 목적 : 각 평문 비트는 모든 암호문 비트에 영향을 끼쳐야 하고, 각 키 비트는 모든 암호문 비트에 영향을 주어야 함

혼돈을 위한 연산 입력 : 16비트 출력 : 16비트 연산 XOR 연산 덧셈연산 : 법을 2^16로 하는 덧셈 곱셈연산 : 법을 2^16+1로 하는 곱셈 => 세가지 연산을 조합함으로써 DES보다 암호해독을 더 어렵게 함

⊙ : Multiplication of integets 확산을 위한 구조 : bit by-bit exclusive-OR : Addition of intergers modulo 216 ⊙ : Multiplication of integets modulo 216 + 1

구현상의 고려 사항 소프트웨어 구현을 위한 설계 원칙 서브블록의 사용 간단한 연산의 사용 하드웨어 구현에 대한 설계 원칙 암호연산은 소프트웨어에 대해 당연히 8, 16, 32비트와 같은 서브 블록에서 동작하도록 한다 IDEA는 16비트 서브 블록을 사용 간단한 연산의 사용 덧셈, 자리 이동 등을 사용하여 쉽게 프로그램 되어야 함 IDEA의 기본 연산은 이 요구사항을 만족 하드웨어 구현에 대한 설계 원칙 암호화 복호화의 유사성 암호화와 복호화는 키를 사용하는 방법에서만 달라야 함 정규구조 VLSI 구현을 용이하게 하기 위한 정규적인 모듈 구조를 가져야 함

IDEA 암호화

IDEA 암호화 입력 평문 64 비트 키 128비트 반복횟수 : 전체 8라운드 알고리즘 입력을 4개의 16비트 서브블록으로 분해 각 반복은 4개의 16비트 서브블록들을 처리 서브키(52개) 각 라운드에 6개의 16비트 서브키를 이용 6*8 = 48 최종 변환은 4개의 서브키 사용

단일 과정 Transformation Sub-encryption

1010 0001 1010 1111 0101

출력 변환 단계

서브키 생성 Z(128bits) z1 z2 z3 z4 z5 z6 z7 z8 z15 z2 z9 z10 z11 z12 z13 25 z9 z10 z11 z12 z13 z14 z15 z22 z23 50 z16 z17 z18 z19 z20 z21 128비트의 암호키 입력 1) Z1, Z2, …, Z8 까지의 8개의 서브키 생성 <= 각각 16비트 2) 키를 25비트 왼쪽 순환 이동 첫 비트부터 그 다음의 서브키를 8개 생성 3) 52개의 서브키를 추출할 때까지 2번 반복

암호/복호화

IDEA 복호화 복호를 위한 서브키 생성 Z1-1, -Z2, -Z3, Z4-1 142페이지 표 4.2 기존 알고리즘의 연산 XOR => XOR 하면 이전 값 복원 예) 키 : 1111, 연산값: 1001 XOR: 1111(+)1001(+)1111 덧셈: 1111+1001-1111 곱셈: 1111*1001*x 1111*x mod 2^5-1 = 1

4.3 Blowfish Bruce Schneier에 의해 개발된 대칭 블록 암호 방식 특성 64비트 블록의 평문을 암호화 빠른 속도 : 32비트 마이크로 프로세스에서 1 바이트 당 18클럭 사이클의 속도로 암호화 간결성 : 5K 이내의 메모리에서도 실행가능 단순성 : 간단한 구조로 구현이 쉽고 알고리즘의 강도 결정이 용이함 보안의 가변성 : 키의 길이는 가변적이며 448비트만큼 길어질 수 있어 높은 속도와 보안성 사이의 균형이 가능 64비트 블록의 평문을 암호화

키 사이즈 : 32비트에서 448비트 범위 생성 18개의 32비트 서브키 32비트 엔트리를 갖는 4개의 8*32 S박스 생성 키는 K-배열에 저장 K1, K2, …, Kj 1<= j <= 14 서브키는 P-배열에 저장 P1, P2, …, P18

P-배열과 S-박스 생성 법 우선 P-배열과 4개의 S-박스를 차례로 상수 phi의 소수부 비트를 이용하여 초기화함. 그러므로 phi의 소수부의 맨 왼쪽 32비트 부터 계속 P1, P2, …, P18이 됨. 필요 시 K-배열의 워드를 재 사용하여 P-배열과 K-배열을 비트 단위 XOR 연산을 수행 P1= P1 XOR K1, P2= P2 XOR K2 … 현재의 P-배열과 S-배열을 이용하여 모두 0인 64비트 블록을 암호화, P1과 P2를 암호문으로 대체 현재의 P-배열과 S-배열을 이용하여 단계 3)의 결과를 암호화하고 P3와 P4를 암호문으로 대체 이 과정을 계속하여 P의 모든 요소와 S의 모든 요소를 차례로 매 단계마다 계속 변하는 Blowfish 알고리즘의 결과를 이용하여 갱신

갱신 처리 과정 P1, P2 = EP,S[0] P3, P4 = EP,S[P1||P2] … S1,0, S1,1 = EP,S[P17||P18] S4,254, S4,255= EP,S[S4,252, S4,253] EP,S[Y]는 배열 S와 P로 Blowfish를 이용하여 Y를 암호화해서 생성된 암호문

최종적인 S와 P를 생성키 위해서 Blowfish 암호 알고리즘이 총 521회 필요 비밀키가 자주 바뀌는 응용에는 적합하지 않음 빠른 실행을 위해서는 P와 S-배열은 알고리즘이 사용될 때마다 키로부터 유도하기 보다는 테이블에 저장 소요되는 메모리는 4K 바이트가 넘는다. Blowfish는 메모리 용량이 제한된 스마트카드와 같은 응용에는 적합하지 않음

암호화 및 복호화 기본연산 덧셈 : 2^32을 법으로 하는 연산 비트 XOR 연산 알고리즘 for i = 1 to 16 do REi = LEi-1 Pi; LEi = F[REi] REi-1; LE17 = RE16 P18 ; RE17 = LE16 P17;

F[a,b,c,d]= ((S1,a+S2,b) S3,c)+S4,d

복호화 서브키의 역순을 사용 암호화와 같은 방향으로 복호화 수행 알고리즘 for i = 1 to 16 do RDi = LDi-1 P19-1; LDi = F[RDi] RDi-1; LD17 = RD16 P1 ; RD17 = LD16 P2;

논의 사항 Blowfish의 특성 책에 소개된 것 중 가장 강력한 관용 암호 알고리즘 암호해독이 매우 어려움 서브키와 S 박스들이 Blowfish 자신의 반복 적용에 의해 생성 데이터 양쪽 모두에 대해서 연산이 수행됨 고전 Feistel 암호와의 차이점

4.4 RC5 Ron Rivest에 의해 개발된 대칭 암호 알고리즘 특성 하드웨어 및 소프트웨어의 적합성 : 마이크로프로세서에서 일반적으로 사용되는 기본 연산만 사용 빠른 속도 : 단어 단위로 처리, 기본 연산은 한번에 데이터 단어 전체를 처리 다른 단어 길이 프로세서에의 적응성 : 단어 당 비트수를 매개변수로 이용, 매개변수가 다르면 다른 알고리즘이 됨 반복 수의 가변성 가변 길이의 키 단순성 : 구현이 쉽고 알고리즘의 강도 결정이 용이 낮은 메모리 요구량 : 스마트 카드나 기타 한정된 메모리를 사용하는 장치에 적당 높은 보안성 : 적당한 매개변수로 높은 보안성 제공 데이터 의존적인 순환 이동 : 데이터 양에 따라 결정되는 회전 이동을 채용=> 암호 해독에 대한 알고리즘의 강도를 높여 줌

RC5 매개변수 w : 단어의 비트 수, 16, 32, 64 r : 반복횟수, 0,1,…,255 b : 비밀 키 K 내의 8비트 바이트수 0,1,…,255

키확장 총 t개의 서브키를 생성 두개의 각 서브키가 각 반복에 사용됨 추가적인 2개의 서브키는 어떤 반복의 일부가 아닌 별도의 연산에 사용됨 t = 2r + 2 각 서브키의 길이는 한 단어(w비트) 서브키는 S[0], S[1],…, S[t-1]라 부르는 t-단어 배열에 저장

키 확장과정

암호화 LE0 = A + S[0] ; RE0 = B + S[1]; For i = 1 to r do LE i = ((LE i-1  1 RE i-1 -1 )  RE i-1 -1) + S[2 i]; RE i = ((RE i-1 -  1 LE i-1 -1 )  LE i-1 -1) + S[2 i+1];

복호화 For i = r down to 1 do RDi-1 =((RDi - S[2  I +1]  LDi )  LDi ); LDi-1 = ((LDi - S[2  i]  RDi )  RDi ); B = RD0- S[1]; A = LD0 – S[0];

RC5 모드 블록 암호 모드 : 고정크기의 입력블록을 취하여 키에 의한 변환을 하여 같은 크기의 암호 블록을 생성, 그림 3.1의 ECB 모드와 동일 CBC모드 : RC5를 위한 블록연결(CBC) 모드, 그림 3.2 CBC-Pad 모드 : 임의 길이의 평문을 처리하는 CBC유형의 알고리즘 CTS 모드 : 암호문을 훔쳐내는 모드로서 역시 CBC 유형의 알고리즘, 임의길이의 평문을 받아서 같은 길이의 암호문을 생성

4.5 CAST-128 1997년 Carlisle Adams와 Stafford Tavares에 의해 개발된 대칭 암호 알고리즘 40비트에서 128비트 사이에 8 비트씩 증가하는 다양한 크기의 키를 사용 64비트의 평문블록 => 64비트의 암호문블록 16회 반복하는 고전적 Feistel 네트워크 구조 각 반복 과정에 두개의 서브키를 사용

암호화 기본연산 덧셈과 뺄셈 : 법 2^32으로 수행 비트 XOR 연산 왼쪽 순환 이동 : 단어 x의 y비트이동, x<<<y 암호 알고리즘 L 0 ll R 0 = plaintext For I= 1 to 16 do Li = R i-1 ; Ri = L i-1  Fi [R i-1 , Kmi , Kri ]; = ciphertext R16 ll L16

치환박스 8개의 8*32 S박스를 사용 S1 ~ S4 : 암호화와 복호화에 사용 S5 ~ S8 : 서브키 생성에 사용 8비트 입력은 배열의 행을 선정 그 행의 32비트 값이 출력 S박스는 고정된 값을 포함

서브키 생성 우선 128비트 키의 각 바이트를 다음과 같이 표기 X0X1X2X3X4X5X6X7X8X9XAXBXCXDXEXF Km1,…,Km16 : 16개의 32비트 마스킹 서브키(r 1개) Kr1,…,Kr16 : 16개의 32비트 회전 이동 서브키(r1) 각 서브키의 최하위 5비트만 사용됨 z0 …zF : 중간(임시) 바이트 K1,…,K32 : 중간(임시) 32비트 단어 그림 4.15 참조 (163 페이지)

논의사항 고정된 S박스 사용 임의의 랜덤 값보다는 암호학적 강도 제공 길이가 256인 32개의 다른 이진 bent 벡터를 선택

4.7 개선된 대칭 블록 암호의 특징 가변 키 길이 혼합 연산자 데이터 의존 회전 이동 키 의존 회전 이동 키 의존 S박스 긴 키 스케쥴 알고리즘 가변적 F 가변적 평문/암호문 블록 길이 가변적 반복 횟수 매 반복 시 양쪽 데이터 절반의 연산