Chapter 3 Symmetric Key Crypto
주요 내용 스트림 암호(Stream cipher) 블록 암호(Block cipher) 블록 암호 모드 RC4 블록 암호(Block cipher) Data Encryption Stantard(DES): relatively simple, Advanced Encryption STD(AES) International Data Encrytption Alg.(IEDA) Blowfish, RC6 Tiny Encryption Algorithm 블록 암호 모드 Electronic codebook (ECB) Cipher-block chaining (CBC) Counter (CTR) 대칭키 암호와 무결성(Integrity)
Chapter 3 Symmetric Key Crypto 이 장의 목표 대칭키 암호를 소개 대칭키 암호 알고리즘이 내부적으로 어떻게 동작하고 있는지를 이해한다. “why”보다는 “how”에 초점을 맞춘다. ”why”를 이해하기 위해서는 cryptanalysis를 이해해야 한다. (6장) Chapter 3 Symmetric Key Crypto
Chapter 3 Symmetric Key Crypto 스트림 암호(stream cipher) Chapter 3 Symmetric Key Crypto
Chapter 3 Symmetric Key Crypto 스트림 암호 최근에는 블록 암호 처럼 많이 쓰이지 않는다. n 비트의 키를 긴 키 스트림(long keystream)으로 확장해서 사용한다. 스트림 암호의 기능 StreamCipher(K) = S where K:키, S:키 스트림 S는 일회성 암호(one-time pad)와 같이 사용한다. c0 = p0 s0, c1 = p1 s1, c2 = p2 s2, … p0 = c0 s0, p1 = c1 s1, p2 = c2 s2, … 송신자와 수신자는 동일한 스트림 암호 알고리즘을 사용하고 모두 키 K를 알고 있다. Chapter 3 Symmetric Key Crypto
Chapter 3 Symmetric Key Crypto 스트림 암호 두 가지 스트림 암호를 소개한다. A5/1 linear feedback shift registers에 기초 GSM mobile phone system에서 사용 A5/1은 유럽과 미국에서 사용 A5/2는 강력한 암호를 갖고 있다고 신뢰할 수 없는 나라에서 사용 RC4 changing lookup table에 기초 여러 응용에서 사용 – SSL Chapter 3 Symmetric Key Crypto
Chapter 3 Symmetric Key Crypto
Chapter 3 Symmetric Key Crypto A5/1 는 H/W로 구현되는 대표적인 스트림 암호 3개의 Linear feedback shift registers로 구성 X: 19 bits (x0, x1, x2, …, x18) Y: 22 bits (y0, y1, y2, ………, y21) Z: 23 bits (z0, z1, z2, ………….,z22) X+Y+Z = 64 bits Chapter 3 Symmetric Key Crypto
Chapter 3 Symmetric Key Crypto At each step: m = maj(x8, y10, z10) Examples: maj(0,1,0) = 0 and maj(1,1,0) = 1 If x8 = m then X steps t = x13 x16 x17 x18 xi = xi1 for i = 18, 17, …, 1 and x0 = t If y10 = m then Y steps t = y20 y21 yi = yi1 for i = 21, 20, …, 1 and y0 = t If z10 = m then Z steps t = z7 z20 z21 z22 zi = zi1 for i = 22, 21, …, 1 and z0 = t Keystream bit is x18 y21 z22 Chapter 3 Symmetric Key Crypto
Chapter 3 Symmetric Key Crypto X x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 x14 x15 x16 x17 x18 Y y0 y1 y2 y3 y4 y5 y6 y7 y8 y9 y10 y11 y12 y13 y14 y15 y16 y17 y18 y19 y20 y21 Z z0 z1 z2 z3 z4 z5 z6 z7 z8 z9 z10 z11 z12 z13 z14 z15 z16 z17 z18 z19 z20 z21 z22 매 사이클의 결과는 한 비트(single bit)이다. 키는 3개의 레지스터를 채우는데 사용한다. 매번 레지스터 단계를 수행할지 안 할지 (x8, y10, z10)의 값에 의해 결정된다. 키 스트림 비트는 레지스터들의 맨 오른쪽 비트의 XOR 값이다. Chapter 3 Symmetric Key Crypto
Chapter 3 Symmetric Key Crypto From Wikipedia Chapter 3 Symmetric Key Crypto
Chapter 3 Symmetric Key Crypto X 1 Y 1 Z 1 위의 예에서, m = maj(x8, y10, z10) = maj(1,0,1) = 1 Register X와 Z 단계가 수행되고 , Y 단계는 수행되지 않는다. 키 스트림 비트는 레지스터의 맨 오른쪽 비트의 XOR 값이다. keystream bit : 0 1 0 = 1 Chapter 3 Symmetric Key Crypto
Chapter 3 Symmetric Key Crypto RC4 Chapter 3 Symmetric Key Crypto
Chapter 3 Symmetric Key Crypto RC4 RC4는 소프트웨어로 구현하도록 최적화되었다. 반면에 A5/1은 하드웨어로 구현 RC4는 매 단계에서 키 스트림 바이트(a keystream BYTE)를 만들어낸다. 반면에 A5/1는 키 스트림 비트(a single keystream bit)를 만들어낸다. Chapter 3 Symmetric Key Crypto
Chapter 3 Symmetric Key Crypto RC4 RC4는 아주 간단하다. 이것은 단지 256(28)-byte 값의 순열을 포함하는 lookup table이기 때문이다. 매번 바이트 키 스트림이 만들어질 때, {0,1,2,…255}의 순열을 포함하도록 변경된다. Chapter 3 Symmetric Key Crypto
Chapter 3 Symmetric Key Crypto RC4 초기화 첫단계 – 키를 사용하여 lookup table을 초기화한다. Key: key[i] for i=0,1,…,N-1 where key[i] is a byte Lookup table: S[i] is a byte Key의 길이는 0부터 255 바이트 사이 키는 오직 S를 초기화하는데 사용된다. S[] is permutation of 0,1,…,255 key[] contains N bytes of key for i = 0 to 255 S[i] = i K[i] = key[i (mod N)] next i j = 0 j = (j + S[i] + K[i]) mod 256 swap(S[i], S[j]) next j i = j = 0 Chapter 3 Symmetric Key Crypto
Chapter 3 Symmetric Key Crypto RC4 키 스트림(keystream) 다음 단계 – 키 스트림 바이트는 다음의 알고리즘에 의해서 발생된다. i = (i + 1) mod 256 j = (j + S[i]) mod 256 swap(S[i], S[j]) t = (S[i] + S[j]) mod 256 keystreamByte = S[t] 키 스트림 바이트를 일회성 암호(a one-time pad)와 같이 사용한다. 주의: 처음의 256 바이트는 반드시 폐기한다. 그렇지않으면 공격자가 키를 회복할 수 있다. Chapter 3 Symmetric Key Crypto
Chapter 3 Symmetric Key Crypto 스트림 암호 스트림 암호는 과거에 많이 사용되었다. 하드웨어로 구현하는데 효율적 음성 등과 같이 속도를 따라가는데 적절 하지만 최근에 CPU의 성능이 향상되어 소프트웨어 기반의 암호 방식도 충분히 빠르다. 스트림 암호의 미래는? Shamir: “스트림 암호의 사망” 과장된 얘기인지도 모른다… Chapter 3 Symmetric Key Crypto