Chapter 3 Symmetric Key Crypto 블록 암호(Block cipher) Chapter 3 Symmetric Key Crypto

Chapter 3 Symmetric Key Crypto 블록 암호 평문과 암호문은 고정된 길이의 블록으로 구성된다. 설계 목표: 보안과 효율성 하지만 두 가지 목표를 만족하는 블록 암호 방식을 찾는 것은 쉽지 않다. Chapter 3 Symmetric Key Crypto 2

Chapter 3 Symmetric Key Crypto (반복) 블록 암호 암호문은 평문에 반복되는 회전 함수(round function)를 적용하여 생성 회전 함수의 입력은 키와 이전 단계의 회전 함수의 결과이다. 항상 소프트웨어로 구현된다. 전형적인 형태가 Feistel Cipher이다. Chapter 3 Symmetric Key Crypto 3

페이스텔 암호(Feistel Cipher) 평문의 블록을 좌우 반쪽으로 나눈다: Plaintext = (L0,R0) 각 단계(i=1,2,...,n) 다음과 같이 계산한다. Li= Ri1 Ri= Li1  F(Ri1,Ki) 여기서 F는 회전 함수, K는 서브키(subkey) 최종 암호문 = (Ln,Rn) Chapter 3 Symmetric Key Crypto

Chapter 3 Symmetric Key Crypto 페이스텔 암호 복호화: 암호문 = (Ln,Rn) 각 단계(i=n,n1,…,1)에서 다음과 같이 계산한다., Ri1 = Li Li1 = Ri  F(Ri1,Ki) 여기서 F는 회전 함수, Ki는 서브키 평문 = (L0,R0) 이 방식은 어떤 함수 F에서도 적용된다. 하지만 함수 F는 안전한(secure) 함수이어야 한다. 예: 모든 Ri-1와 Ki 에 대해서 F(Ri-1, Ki) = 0 인 함수는 안전하지 않다. Chapter 3 Symmetric Key Crypto

Data Encryption Standard (DES) Chapter 3 Symmetric Key Crypto

Chapter 3 Symmetric Key Crypto DES 1970년대에 개발 IBM Lucifer cipher에 기반을 둠 U.S. 정부 표준 DES 개발에는 논란이 있었다. NSA가 비밀리에 개입됨 개발 단계가 공개되지 않음 키 길이가 축소됨 Lucifer 알고리즘을 약간 변경 Chapter 3 Symmetric Key Crypto

National Security Agency/ Central Security Service Chapter 3 Symmetric Key Crypto

Chapter 3 Symmetric Key Crypto DES DES는 페이스텔 암호 체계를 따른다. 블록 길이 : 64 bits 키 길이 : 56 bits 16 단계(round) 매 단계에서 48 bit의 키를 사용(subkey) 매 단계의 절차는 간단하다. (for a block cipher) 안전성은 주로 “S-boxes”에 달려 있다. 각 S-boxe는 6 bit를 4 bit로 매핑한다. 총 8개의 S-boxes numerology [njù:merled¥i|-rl-] n. 수점술(數占術), 수비학(數秘學) Chapter 3 Symmetric Key Crypto

Chapter 3 Symmetric Key Crypto One Round of DES L expand R S-boxes(8) P Box key Compress 48 32 28 Chapter 3 Symmetric Key Crypto

DES 확장 순열(Expand permutation) Input 32 bits 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 Output 48 bits 31 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 Chapter 3 Symmetric Key Crypto

Chapter 3 Symmetric Key Crypto DES S-box (치환 박스) 8개의 치환 박스(substitution boxes) 각각의 S-box는 6 bit를 4 bit로 매핑한다. 첫번째 S-box의 매핑 input bits (0,5)  input bits (1,2,3,4) 00 01 10 11 Chapter 3 Symmetric Key Crypto

Chapter 3 Symmetric Key Crypto DES P-box (순열 박스) Input 32 bits 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 Output 32 bits 15 6 19 20 28 11 27 16 14 22 25 4 17 30 9 1 7 23 13 31 26 2 8 18 12 29 5 21 10 3 24 Chapter 3 Symmetric Key Crypto

Chapter 3 Symmetric Key Crypto DES 서브키(Subkey) 56 bit DES key : (0,1,2,…,55) Left half key bits, LK 49 42 35 28 21 14 7 50 43 36 29 22 15 8 1 51 44 37 30 23 16 9 2 52 45 38 31 Right half key bits, RK 55 48 41 34 27 20 13 6 54 47 40 33 26 19 12 5 53 46 39 32 25 18 11 4 24 17 10 3 Chapter 3 Symmetric Key Crypto

Chapter 3 Symmetric Key Crypto DES 서브키(Subkey) For rounds i=1,2,...,16 Let LK = (LK circular shift left by ri) Let RK = (RK circular shift left by ri) Left half of subkey Ki(24bits)는 다음과 같은 LK 비트들로 구성된다. 13 16 10 23 0 4 2 27 14 5 20 9 22 18 11 3 25 7 15 6 26 19 12 1 Right half of subkey Ki(24bits)는 다음과 같은 RK 비트들로 구성된다. 12 23 2 8 18 26 1 11 22 16 4 19 15 20 10 27 5 24 17 13 21 7 0 3 Chapter 3 Symmetric Key Crypto

Chapter 3 Symmetric Key Crypto DES 서브키(Subkey) 단계 1, 2, 9, 16에서 shift ri = 1, 그리고 나머지 단계에서는 ri = 2 LK의 비트 8,17,21,24는 매 단계에서 생략된다. RK의 비트 6,9,14,25는 매 단계에서 생략된다. Compression permutation은 LK와 RK의 56비트 중에서 48비트의 서브키를 생성해 낸다. Key schedule은 서브키를 생성한다. Chapter 3 Symmetric Key Crypto

Chapter 3 Symmetric Key Crypto 마지막으로 DES에 대해서 첫 단계 전에 초기 순열 P를 수행한다. 마지막 단계에서 좌우측 반쪽을 교환한다. 암호문을 생성하기 위해서 (R16,L16)에 마지막 순열 (inverse of P)을 적용한다. 이러한 것은 보안과는 상관이 없다. Chapter 3 Symmetric Key Crypto

Chapter 3 Symmetric Key Crypto DES의 안전성(security) DES의 안전성은 대부분 S-boxes에 달려 있다. S-box를 제외한 다른 것들은 선형(linear) 30년 동안의 치밀한 분석 결과 DES에 “뒷 문(back door)”은 없는 것으로 밝혀졌다. 공격은 exhaustive key search를 사용한다. 결론 DES의 설계자들은 그들이 무엇을 하는지를 알았고 그들의 시대에 훨씬 앞서 있었다. Chapter 3 Symmetric Key Crypto

Exhaustive Key Search 시간 Key size (bits) 가능한 키의 수 실행 시간 (만약 1 decypt/us) (만약 106 decypt/us) 32 56 128 168 232=4.3X109 256=7.2X1016 2128=4.3X1038 2168=4.3X1050 231us=35.8 min 255 us=1142 yrs 2127 us=5.4X1024 yr 2167 us=5.9X1036 yr 2.15 ms 10.01 hrs 5.4X1018 yrs 5.9X1030 yr

Chapter 3 Symmetric Key Crypto Triple DES 논리적 접근 방법은 triple DES 키를 3배로 한다. 하지만 실제로, Triple DES는 C = E(D(E(P,K1),K2),K1) P = D(E(D(C,K1),K2),K1) 실제 키의 크기는 112 bit이다. Chapter 3 Symmetric Key Crypto

Chapter 3 Symmetric Key Crypto Triple DES 왜 2개의 키를 사용하여 Encrypt-Decrypt-Encrypt (EDE)으로 암호화하는가? (왜 3개의 키를 사용하여 EEE로 하지 않는가?) Single DES와의 Backward compatible를 위해서 If K1=K2=K then E(D(E(P,K),K),K) = E(P,K) And 키의 길이는 112 bits이면 충분히 안전하다. 오늘날 3DES는 널리 사용되고 있으나, AES의 등장으로 3DES는 시간이 지날수록 사라져 갈 것이다. Chapter 3 Symmetric Key Crypto

Advanced Encryption STD (AES) Chapter 3 Symmetric Key Crypto

Chapter 3 Symmetric Key Crypto AES 역사(1) DES를 대체할 암호 방식이 필요 DES는 이미 과거의 유물이 됨 exhaustive key search에 안전하지 않음: 특수 목적의 DES 크랙커와 인터넷에서 분산 계산 공격 3DES는 공격에는 안전하다. 하지만, 효율적인 소프트웨어 코드가 없다. 너무 속도가 느리다: DES를 3번 해야 된다. 64-bit 블록 크기: 효율과 안전을 위해서 더 큰 블록 크기가 필요 그래서, 3DES는 장기적으로 해결책이 되지 못함 1997년, NIST는 공식적으로 발전된 암호 알고리즘 표준을 정하기 위해서 공모를 하였다. Chapter 3 Symmetric Key Crypto

Chapter 3 Symmetric Key Crypto AES 역사(2) 목표: 정부와 민간 부문에서 사용할 DES를 대체할 수 있는 알고리즘을 찾음 AES 요구사항 저작권 없이 전세계에서 사용할 수 있도록 비밀없는(unclassified), 공개된 암호화 알고리즘 알고리즘은 반드시 대칭키(symmetric key) 방식이어야 함 블록 암호 방식과 블록 크기는 최소한 128 비트, 키 크기는 128- , 192-, 그리고 256 비트 1998년 NIST 15개의 AES 후보 알고리즘을 발표 Chapter 3 Symmetric Key Crypto

Chapter 3 Symmetric Key Crypto AES 역사(3) AES를 선택하는 기준: 안전성, 견고성(Robustness), 속도 1999년 15개 중에서 5개로 후보를 좁혔다. MARS, RC6, Rijndael, Serpent, and Twofish. 5개의 알고리즘 모두 안전한 것으로 인정받았다. 2000년 10월 2일 NIST는 Rijndael 을 선정 발표 Joan Daemen과 Vincent Rijmen이 만듬 Chapter 3 Symmetric Key Crypto

Chapter 3 Symmetric Key Crypto AES 특징(1) 다양한 플랫폼에서 사용할 수 있으며 소프트웨어와 하드웨어에서 효율적으로 동작할 수 있도록 설계 페이스텔 암호 형태가 아님 반복적인 블록 암호 (DES와 같음) 페이스텔 암호 형태가 아님(DES와 다름) “Secure forever” – Shamir Chapter 3 Symmetric Key Crypto

Chapter 3 Symmetric Key Crypto AES 특징(2) 제안된 Rijndael 가변의 블록 크기 : 128,192, 256-bits, 가변의 키 크기 : 128-, 192-, or 256-bits. 가변의 반복 단계(round) : (10, 12, 14): 10 if B = K = 128 bits 12 if either B or K= 192 and the other≤ 192 14 if either B or K = 256 bits 그러나 주목할 점은 AES의 블록 크기는 128-bit. Chapter 3 Symmetric Key Crypto

Chapter 3 Symmetric Key Crypto AES 개요(1) 정의: State→ 4X4 array of bytes 128 bits = 16 bytes 가변의 rounds (10, 12, 14): 10 if K = 128 bits 12 if K = 192 bites 14 if K = 256 bits 각 round에서 128-bit round key 사용 128 bits = 16 bytes = 4 words Nr rounds에 대해서 Nr+1 round key가 필요 10 rounds, 128-bit 키에 대해서 44 words 필요 Chapter 3 Symmetric Key Crypto

Chapter 3 Symmetric Key Crypto AES 개요(2) 각 round는 4개의 함수 사용 (3 “계층”) 4 함수: 1 순열과 3 치환 3 계층: 선형, 비선형, 키 덧셈 순열(Permutation) 선형 혼합 계층: ShiftRow (State) 치환(Substitution) 비선형 계층: ByteSub (State, S-box) 비선형 계층: MixColumn (State) 키 덧셈 계층: AddRoundKey (State, KeyNr) Chapter 3 Symmetric Key Crypto

AES: High-Level Description State: 4 X 4 바이트 행렬: 128 bits = 16 bytes State = X AddRoundKey(State, Key0) (op1) for r = 1 to Nr - 1 SubBytes(State, S-box) (op2) ShiftRows(State) (op3) MixColumns(State) (op4) AddRoundKey(State, KeyNr) endfor SubBytes(State, S-box) ShiftRows(State) Y = State Chapter 3 Symmetric Key Crypto

Chapter 3 Symmetric Key Crypto AES AddRoundKey 서브키와 블록을XOR: 128-bits 블록으로 가정 RoundKey (subkey) 는 key schedule 알고리즘에 의해서 결정 AES key schedule 알고리즘의 설명은 생략 Chapter 3 Symmetric Key Crypto

Chapter 3 Symmetric Key Crypto AES BytesSub Assume 128 bit block, 즉 4ⅹ4 bytes ByteSub은 AES의 “S-box” 두 수학적 연산의 비선형(nonlinear) (하지만 invertible) 결합 Chapter 3 Symmetric Key Crypto

Chapter 3 Symmetric Key Crypto AES BytesSub 비선형 S-Box (각각의 바이트에 독립적으로)를 사용한 바이트 치환 S-box는 16x16 array로 표현, 열과 행은 16진수 비트로 인덱스된다. 8 bits는 다음과 같이 대체된다.: 8 bits : hexadecimal number (r,c), 그러면 (sr,sc) = binary(Sbox(r, c)) Chapter 3 Symmetric Key Crypto

Chapter 3 Symmetric Key Crypto AES “S-box” 예: 16진수 53 은 ED로 대체된다. Last 4 bits of input First 4 bits of input Chapter 3 Symmetric Key Crypto

Chapter 3 Symmetric Key Crypto AES ShiftRow Cyclic shift rows Chapter 3 Symmetric Key Crypto

Chapter 3 Symmetric Key Crypto AES MixColumn 각 행에 적용되는 비선형, 역가능 연산 (커다란)lookup table로 구현된다. Chapter 3 Symmetric Key Crypto

Chapter 3 Symmetric Key Crypto AES 복호화 복호화를 위해서 절차는 반드시 역가능(invertible)해야 한다. AddRoundKey의 역은 용이:  는 자신이역(inverse)이다. MixColumn는 역가능하다 : 역(inverse)도 lookup table로 구현 가능 ShiftRow의 역은 용이: 다른 방향으로 cyclic shift하면 된다. ByteSub도 역가능: 역(inverse)도 역시lookup table로 구현 가능 Chapter 3 Symmetric Key Crypto

Chapter 3 Symmetric Key Crypto 다른 블록 암호들 IDEA Blowfish RC6 TEA Chapter 3 Symmetric Key Crypto

Chapter 3 Symmetric Key Crypto Block Cipher Modes Chapter 3 Symmetric Key Crypto

Chapter 3 Symmetric Key Crypto 여러 블록으로 구성된 메시지 여러 개의 블록으로 구성된 메시지를 어떻게 암호화할 것인가? 각 블록 마다 다른 키를 사용할 것인가? 각 블록을 독립적으로 암호화할 것인가? 현재 블록의 암호화는 이전 블록과 연관(chain)을 갖도록 하면 어떨까? 블록으로 채워지지 않을 경우 어떻게 할 것인가? Chapter 3 Symmetric Key Crypto

동작 모드(Modes of Operation) Electronic Codebook (ECB) mode Obvious thing to do 각 블록을 독립적으로 암호화한다. 하지만 심각한 문제점이 존재한다. Cipher Block Chaining (CBC) mode 블록들을 연결하여 암호화한다. ECB보다 훨씬 안전하고 실질적으로 별도의 작업을 요구하지 않는다. Counter Mode (CTR) mode 스트림 암호와 같이 동작 랜덤 액세스 경우 주로 사용된다. Chapter 3 Symmetric Key Crypto

ECB(Electronic Codebook) Mode 표기법: C=E(P,K) 주어진 평문: P0, P1, …, Pm, … 블록 암호를 사용하는 간단 명료한 방법 암호화 복호화 C0 = E(P0, K), P0 = D(C0, K), C1 = E(P1, K), P1 = D(C1, K), C2 = E(P2, K),… P2 = D(C2, K),… 고정된 키(K)를 갖고, 전자 코드북을 만드는 방법이다. 새로운 키에 대해서 새로운 코드북이 만들어진다. Chapter 3 Symmetric Key Crypto

Chapter 3 Symmetric Key Crypto ECB Mode Chapter 3 Symmetric Key Crypto

ECB 복사-붙여쓰기(Cut and Paste) 공격 평문이 다음과 같다고 하자. “Alice digs Bob. Trudy digs Tom.” 64-bit 블록을 사용한다고 가정하자: P0 = “Alice di”, P1 = “gs Bob. ”, P2 = “Trudy di”, P3 = “gs Tom. ” 암호문: C0, C1, C2, C3 Trudy가 다음과 같이 복사-붙여넣기 공격을 했다: C0, C3, C2, C1 그러면 복호화된 평문은 다음과 같다. “Alice digs Tom. Trudy digs Bob.” Chapter 3 Symmetric Key Crypto

Chapter 3 Symmetric Key Crypto ECB의 약점 Pi = Pj라고 하자. 그러면 Ci = Cj이 되고 Trudy는 Pi = Pj임을 알 수 있다. 이것은 Trudy가 Pi 혹은 Pj 를 모른다고 하더라도 약간의 정보를 알려주는 셈이다. 공격자에게 암호해석을 위해서 공짜로 어떤 정보도 제공해서는 안 된다. Trudy는 Pi을 알고 있을지도 모른다. 이것이 심각한 문제일까? -> 다음의 슬라이드 Chapter 3 Symmetric Key Crypto

Chapter 3 Symmetric Key Crypto ECB 모드로 암호화된 Alice Alice’의 압축되지 않은 이미지를 ECB (TEA)를 사용하여 암호화하였다. 어떻게 이렇게 되었는가? 동일한 평문의 블록  동일한 암호문! 해결책은??? -> 다음 슬라이드 Chapter 3 Symmetric Key Crypto

Cipher Block Chaining(CBC) Mode 랜덤 초기 벡터(random initialization vector), IV가 CBC 모드를 초기화하기 위해서 요구된다. IV는 랜덤, 하지만 비밀일 필요는 없다. 암호화 복호화 C0 = E(IV  P0, K), P0 = IV  D(C0, K), C1 = E(C0  P1, K), P1 = C0  D(C1, K), C2 = E(C1  P2, K),… P2 = C1  D(C2, K),… Chapter 3 Symmetric Key Crypto

Chapter 3 Symmetric Key Crypto CBC 모드 약점 암호화가 순차적으로 이루어진다. (즉, 병렬화를 할 수 없다.), 메시지는 블록 크기에 맞추어져야 한다.(블록 크기에 맞지 않을 경우 padding 필요) Chapter 3 Symmetric Key Crypto

Chapter 3 Symmetric Key Crypto CBC 모드 동일한 평문 블록은 다른 암호문 블록을 만들어 낸다. 복사와 붙여넣기(Cut and paste) 공격은 여전히 가능하다. 하지만 훨씬 복잡하다.(and will cause garbles) 만약 C1이 오류가 발생하였다면, 즉, C1이 G가 되었다면, P1  C0  D(G, K), P2  G  D(C2, K) 하지만 P3 = C2  D(C3, K), P4 = C3  D(C4, K),… 오류로부터 자동적으로 복원할 수 있다! Chapter 3 Symmetric Key Crypto

Chapter 3 Symmetric Key Crypto CBC 모드로 암호화된 Alice Alice’의 압축되지 않은 이미지를 CBC (TEA)를 사용하여 암호화하였다. 왜 이렇게 되었는가? 동일한 평문일지라도 다른 암호문을 만들어낸다! Chapter 3 Symmetric Key Crypto

Chapter 3 Symmetric Key Crypto Counter (CTR) 모드 CTR은 랜덤 엑세스에서 주로 사용된다. 암호화 복호화 C0 = P0  E(IV, K), P0 = C0  E(IV, K), C1 = P1  E(IV+1, K), P1 = C1  E(IV+1, K), C2 = P2  E(IV+2, K),… P2 = C2  E(IV+2, K),… EBC도 랜덤 액세스에서 사용할 수 있다!!! Chapter 3 Symmetric Key Crypto

Chapter 3 Symmetric Key Crypto Counter (CTR) Mode Chapter 3 Symmetric Key Crypto