제 3 장 블록암호 및 DES 단순 DES의 동작 원리 블록 암호방식의 개념 Feistel 암호구조 차분 및 선형 암호 해독 블록 암호설계의 원리

핵심정리 블럭암호는 평문 블록 전체를 가지고 동일한 길이의 암호문을 블록을 생성하는 암/복호화 방식 많은 블럭암호가 Feistel 구조를 띄고 있음 동일한 라운드 수로 구성되어 동작 각 라운드는 데이터의 절반이 치환으로 수행, 이후 데이터의 두 개의 반을 교환하는 순열 수행 원본의 키는 확장되어 각 라운드마다 다르게 사용 DES는 최근까지 가장 널리 사용되는 암호 알고리즘 차등 암호분석과 선형 암호분석은 암호 분석의 중요한 두 가지 방법 DES는 두가지 공격 유형에 매우 강함을 보임

의문 1 무엇이 깨달음인가? 나는 누구인가? 나는 어떤 사람인가? 나는 왜 사는가? 나는 어떻게 살 것인가?

의문 2 무엇이 건강인가? 무엇이 의학인가? 육체적 치유 정신적 치유 사회적 치유 영적인 치유 무엇을 깨달았는가?

의문 3 인간은 감정의 동물이다? ( O, X ) 내 몸은 내 것이다? ( O, X ) 내 몸은 내가 아니다? ( O, X )

단순 DES[Simplified Data Encryption Standard] 알고리즘 8비트 평문, 10비트 키 8비트 암호문 생성 초기순열(IP) 순열, 치환 이용 fk 순열 함수 SW 역 순열(IP-1) 암호문 IP-1(fk2(SW(fk1(IP(평문))))) 복호문 IP-1(fk1(SW(fk2(IP(암호문)))))

S-DES를 위한 키 생성 암호문 복호문 K1 = P8(Shift(P10(key))) IP-1(fk2(SW(fk1(IP(평문))))) 복호문 IP-1(fk1(SW(fk2(IP(암호문))))) K1 = P8(Shift(P10(key))) K2 = P8(Shift(Shift(P10(key)))

S-DES 키의 생성(1/3) K1 = P8(Shift(P10(key))) 10 비트 키 = (k1, k2, k3, k4, k5, k6, k7, k8, k9, k10) P10 = (k3, k5, k2, k7, k4, k10, k1, k9, k8, k6) P10 3 5 2 7 4 10 1 9 8 6 1 2 3 4 5 6 7 8 9 0 예 제 10 비트 key = ( 1 0 1 0 0 0 0 0 1 0 ) P10(key) = ( 1 0 0 0 0 0 1 1 0 0 )

(2/3) K1 = P8(Shift(P10(key))) (Shift(P10(key))): LS-1[키의1st 5비트] & LS-1[키의 2nd 5비트] 첫 번째 다섯 비트와 두 번째 다섯 비트 좌로 순환 이동(1비트 좌측 순환이동) P10 =( k3, k5, k2, k7, k4, k10, k1, k9, k8, k6 ) Shift =( k5, k2, k7, k4, k3, k1, k9, k8, k6, k10 ) 예제) P10 = ( 1 0 0 0 0 0 1 1 0 0 ) LS-1 = ( 0 0 0 0 1 1 1 0 0 0 ) 1 2 3 4 5 6 7 8 9 0

(3/3) K1 = P8(Shift(P10(key))) = P8(LS-1) P8(LS-1) = P8( 0 0 0 0 1 1 1 0 0 0 ) 10 비트에서 8비트 선택 치환 K1 = ( 1 0 1 0 0 1 0 0 ) K2 = P8(Shift(Shift(P10(key)))) = P8(Shift(LS-1)) = P8(LS-2) LS-2 = Shift(LS-1) LS-1의 결과에 2비트 좌측 순환 이동 K2 = P8(LS-2) = P8( 0 0 1 0 0 0 0 0 1 1 ) K2 = ( 0 1 0 0 0 0 1 1 )

S-DES 암호 알고리즘 초기 및 최종 순열 함수 예제) 입력: 8비트 블록 평문 초기순열(IP) 최종 순열 IP-1(IP(X)) = X 예제) X = ( 1 0 1 1 0 0 1 1 ) IP(X) = ( 0 0 1 1 1 1 0 1 ) IP-1(IP(X)) = ( 1 0 1 1 0 0 1 1 ) 최종 순열 1 2 3 4 5 6 7 8

함수 fk(1/4) 순열, 치환 함수 조합 L( Left ) R( Right ) 왼쪽 4비트 R( Right ) 오른쪽 4비트 fk( L, R ) = (L  F( R, SK ), R ) F 함수(확장 순열) n n3 4 2 1 n4 평문 R: (n1, n2, n3, n4)

(2/4) 8비트 서브키 K1 K1 = (k11, k12, k13, k14, k15, k16, k17, k18) XOR S-Box n k 13 14 17 18 2 4 3 1 11 12 15 16 p 0,0 1,0 0,1 1,1 0,2 1,2 0,3 1,3

(3/4) 예제) P = (0100 0111) 이라면 S0: 행 00(P00 P03), 열 10(P01 P02) ; 1,4 요소  행, 2,3 요소  열 S1: 행 01(P10 P13), 열 11 (P11 P12) ; 5,8 요소  행, 6,7 요소  열 S0 = 11, S1 = 11 이 된다. (치환 효과)

(4/4) P4 순열 P4출력은 함수 F의 출력이 된다. 스위치 함수(SW) 두 번째 fk에서는 K2만 다름

S-DES의 분석 Brute-force 공격 가능 10비트 키 210= 1024 기지 평문/암호문 쌍 평문: ( p1, p2, p3, p4, p5, p6, p7, p8) 출력 암호문: ( c1, c2, c3, c4, c5, c6, c7, c8 ) 미지의 키: (k1, k2, k3, k4, k5, k6, k7, k8, k9, k10) 기지 평문 공격: 각 ci는 pj와 kj의 다항식 함수gi 암호 알고리즘은 10개의 미지수를 갖는 8개의 비선형 방정식 알고리즘에서 각각의 순열과 합 연산은 선형 사상 S박스를 통하여 비선형성을 도출 선형 사상을 비선형 사상으로 변경함으로써 암호해독을 난해하게 하는 효과

DES와의 관계 IP-1 · fK16 · SW · fK15 · SW · … … · SW · fK1 IP IP-1 · fk2 · SW · fk1 · IP (평문) 10비트 키에서 2개의 8-비트 서브키 생성 F 함수는 4비트 연산 4행 4열로 구성된 2개의 S 박스 사용 DES는 64-비트 블록단위로 16단계 처리 IP-1 · fK16 · SW · fK15 · SW · … … · SW · fK1 IP 키 56비트에서 16개의 48-비트 서브키 생성 F함수는 32비트 연산 4행 16열로 구성된 8개의 S박스 사용

블록 암호방식의 개념 스트림 암호와 블록 암호 기법 스트림 암호 블록 암호 본 교재는 블록 암호 방식에 초점 한번에 1비트 혹은 1 바이트 Vigenere 암호, Vernam 암호 블록 암호 평문 블록 전체(64비트 – 전형적) 다양한 작동모드 사용 스트림 방식에 비해 응용 범위 넓음 대부분 네트워크 기반 관용 암호 방식에 사용 본 교재는 블록 암호 방식에 초점

스트림 암호 한번에 1비트 혹은 1바이트의 디지털 데이터 스트림을 암호화 키 스트림(ki)은 평문 비트 스트림(pi) 만큼의 길이를 가짐 Bit-stream generation algorithm Key (K) Plaintext (pi) Cryptographic bit stream (ki) Ciphertext (ci)

블록 암호 평문 블록 전체를 가지고 같은 크기의 암호문 블록 생성 전형적으로 64비트 또는 128비트를 사용 b bit Plaintext Encryption algorithm Key (K) Ciphertext b bit

Feistel 암호 구조의 유도 n비트 평문을 입력으로 n비트 블록처리하여 n비트 암호문을 출력 역으로 n 비트 암호문 입력에 대해 n비트 평문 출력(역의 성립: reversible, 비단수형: nonsingular) 복호화가 가능하기 위해서는 각 평문 블록에 대하여 유일한 암호문 블록을 생성(역이 성립) 2n 가지의 서로 다른 블록 존재 가능 역이 가능한 사상만으로 제한 할 경우 2n! 가능한 사상의 개수: (1)2n (2)2n-1 (2)2n-2 … … 1 Plaintext Ciphertext 00 11 01 10 Plaintext Ciphertext 00 11 01 10 Reversible Mapping Irreversible Mapping

n 비트 : n 비트 블록 치환( n=4 인 경우) 4비트입력으로 16개 값 중 하나 선택하고 , 내부 치환에 의하여 16개 출력 값 중 하나 대응하여 4비트 출력

Feistel 암호 방식 두 개 이상의 기본 암호연산자를 계속적으로 수행(치환, 순열 번갈아 수행) 확산과 혼돈 Shannon 치환: 평문의 각 원소 또는 원소의 그룹을 다른 원소에 사상 순열: 평문 원소의 순서는 순열의 순서대로 재배치 확산과 혼돈 Claude Shannon 소개(SHAN49) 통계적 분석에 기초한 암호 해독 방지 Shannon “매우 이상적인 암호는 암호문에 대한 모든 통계적 정보가 사용된 키와 독립적이어야 한다.” 확산(diffusion) 평문의 통계적 구조가 암호문에 광범위하게 분산(평문과 암호문 관계 복잡) 각 평문 숫자가 다수의 암호문 숫자 값에 영향 yn = mn+i (mod 26) ; M = m1, m2, m3, … :문자 메시지 혼돈(confusion) 암호문의 통계적 구조와 암호 키 값 사이의 관계 복잡 키를 이용한 암호문 생성 방법 복잡( 키 추론 어려움)

Feistel 암호 구조 처리구조 고전 Feistel 구조 하나의 반복 구조 길이 2w 비트인 평문 블록(L0, R0) 분할 처리 K로부터 유도된 n개의 키(Ki) 사용 n회의 동일한 반복 구조 실행 고전 Feistel 구조 하나의 반복 구조 오른 쪽 반 R0에 반복 함수 F 적용 반복 서브키 K1 적용(K  Ki) 왼쪽 반 L0와 XOR(치환 작용) 좌우 양쪽 결과를 교환(순열 작용)

Feistel 암호 설계의 고려사항 빠른 소프트웨어 암/복호화 어플리케이션 또는 유틸리티 함수에 내재 알고리즘의 실행속도가 중요 분석의 용이성 암호 해독의 취약성에 대한 알고리즘의 분석이 쉬움 고도의 신뢰성과 보안 강도를 위한 개발 용이

설계 특성 블록 크기(64비트) 큰 블록은 보안 강화하지만 암/복호 속도는 저하 암/복호 속도를 고려 64비트 일반적 키 크기(128비트) 큰 키는 보안 강화 하지만 암/복호 속도는 저하 암/복호 속도를 고려하여 128비트 일반적(64비트 이하는 해독 용이) 반복 수 다중 반복과정은 보안성 강화 16회 반복이 일반적 서브키 생성 알고리즘 서브키 생성 방법이 복잡할수록 강력 반복함수 적용되는 반복함수가 복잡할수록 강력

Feistel 복호 알고리즘 암호화 마지막 반복 복호화 과정 암호화과정의 역 순서 처리 첫 반복 LE16 = RE15 RE16 = LE15  F(RE15, K16) 복호화 과정 암호화과정의 역 순서 처리 첫 반복 LD1 = RD0 = LE16 = RE15 RD1 = LD0  F(RD0, K16) = RE16  F(RE15, K16) = [LE15  F(RE15, K16)]  F(RE15, K16) = LE15

암호화 마지막 반복 암호 알고리즘의 i 번째 반복 과정은 LE16 = RE15 RE16 = LE15  F(RE15, K16) LEi = REi-1 REi = LEi-1  F(REi-1, KI) 역으로 정리하면 REi-1 = LEi LEi-1 = REi  F(REi-1, Ki) = REi  F(LEi, Ki) 복호화 그림에서 ( i-1 ) 번째 복호결과를 만들기 위한 ( i )번째 입력형식 증명

DES (Data Encryption Standard) 특징 1977년 미 상무성의 국립 표준국(National Bureau of Standards)에서 연방 정보처리 표준 채택 46(FIPS PUB46) 64비트 블럭 암호 알고리즘 56비트 키를 사용 64비트 중 8비트는 parity check로 사용 기본 구조 round 수 : 16 round 복호화는 암호화의 역순 최근에는 DES암호화를 세 개의 키로 세 번 반복함으로써 암호의 강도를 높인 Triple-DES를 사용 치환과 전치 혼합방법, 블럭 암호, 관용암호방식

DES의 역사 1960년 후반 : Feistel에 의해 컴퓨터 암호 과제 선정 1971년 : LUCIFER 개발(128bit 키 사용) 1973년 : Tuchman-Meyer과제로 DES 개발 1977년 : 데이터 암호 표준으로 채택 1994년 : NIST에서 재사용 인가 1999년 : 3중 DES의 표준 발표(FIPS PUB 46-3)

DES의 역사 전용 암호시스템 미연방 정부에 의해 공개 암호 표준화 작업 진행 타 그룹간의 통신에 불리==> 데이터 암호화 표준이 필요 미연방 정부에 의해 공개 암호 표준화 작업 진행 표준화 검토(1972),적합한 암호 알고리즘 조사 1973년 5월: 암호방식 공모(1차) 1974년 8월: 2차 공모 IBM이 요건을 갖춤 NBS가 요건을 NSA에 의뢰

1975년~1977년: 일반 comment, 계약 체결 1977년: NBS(NIST)가 DES를 표준 암호 알고리즘으로 채택 U.S.banks have been adopted DES NBS postponed guarantee term of DES from till 1988 to till 1993 NSA proposed CCEP(Commercial COMSEC Endorsement Program;상용 통신 안전 보증 계획)instead of DES U.S. bank expect to continue the use of DES

DES 암호화 DES의 알고리즘의 일반적 모형 처리 단계 평문: 64bit 키: 56bit + 8bit(패리티) 초기순열 단계(IP) 16라운드 반복 좌우 교환단계 역초기순열 단계(IP-1)

. . . LE0 RE0 LE1 RE1 LE2 RE2 F LD0=RE16 RD0=LE16 LD1=RE15 RD1=LE15 Round 1 Round 2 K1 K2 LD0=RE16 RD0=LE16 Round 16 Round 15 LD1=RE15 RD1=LE15 LD2=RE14 RD2=LE14 LD14=RE2 RD14=LE2 LD15=RE1 RD15=LE1 LD16=RE0 RD16=LE0 K15 K16 LE14 RE14 LE15 RE15 LE16 RE16

초기순열 단계 64비트 평문 메시지 M 순열 X = IP(M) M1 M2 M3 M4 M5 M6 M7 M8

DES의 순열 표 (a) 초기 순열 IP (64  64) (b) 역초기 순열 IP-1 (64  64) © 확장순열(32  48) (b) 역초기 순열 IP-1 (64  64) (d) 순열함수(32  32)

DES의 기본 구조 (단일 반복 과정)

f 함수의 구성도 8개의 S-box로 구성 각 S-box는 6비트 입력, 4비트 출력 생성

S-box Table S1 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13 예) 0 1 1 0 1 1 ------ 6비트 입력 행 (1행) 열 (13열) ‘011011’를 4비트로 출력 : “0 1 0 1”

DES의 기본 구조 (키 생성부) : 키 c0 c1 c2 c15 d0 d1 d2 d15 K1 K2 K16 순열선택-1 좌측 시프트 c1 c2 c15 d0 d1 d2 d15 순열선택-2 K1 K2 K16 :

DES 키의 단계별 계산표 순열선택1 (PC-1) 57 49 41 33 25 17 9 1 58 50 42 34 26 18 64 56 C0, D0 : 각 28비트 57 49 41 33 25 17 9 1 58 50 42 34 26 18 10 2 59 51 43 35 27 19 11 3 60 52 44 36 63 55 47 39 31 23 15 7 62 54 46 38 30 22 14 6 61 53 45 37 29 21 13 5 28 20 12 4 순열선택2 (PC-2) 56->48 48비트 키 출력 생성 14 17 11 24 1 5 3 28 15 6 21 10 23 19 2 4 26 8 16 7 27 20 13 2 41 52 31 37 47 55 30 40 51 45 33 38 44 49 39 56 34 53 46 42 50 36 29 32

Key 쉬프트 스케줄 라운드 수 좌측 쉬프트 수 1 1 2 1 3 2 4 2 5 2 6 2 7 2 8 2 9 1 10 2 11 2 12 2 13 2 14 2 15 2 16 1

DES 복호화 서브키 역순 사용 암호화와 같은 알고리즘 사용 Feistel 구조

DES 예제 DES 예제 44 Round Ki Li Ri IP 5a005a00 3cf03c0f 1 1e030f03080d2930 Bad22845 2 0a31293432242318 99e9b723 3 230723118201d0c1d 0bae3b9e 4 05261d3824311a20 42415649 5 3325340136002c25 18b3fa41 6 123a2d0d04262a1c 9616fe23 7 021f120b1c130611 67117cf2 8 1c10372a2832002b C11bfc09 9 04292a380c341f03 887fbc6c 10 2703212607280403 600f7e8b 11 2826390c31261504 F596506e 12 12071c241a0a0f08 738538b8 13 300935393c0d100b C6a62c4e 14 311e09231321182a 56b0bd75 15 283d3e0227072528 75e8fd8f 16 2921080b13143025 25896490 IP-1 da02ce3a 89ecac3b 44

DES 예제 DES 쇄도효과 : 평문변화 평문이나 키의 작은 변화가 암호문에 대하여 중요한 변화를 일으키게하는 효과 평문이나 키를 1비트 바꿀 때 암호문의 여러비트가 변함 Round δ 02468aceeca86420 12468aceeca86420 1 3cf03c0fbad22845 3cf03c0fbad32845 2 bad2284599e9b723 bad3284539a9b7a3 5 3 99e9b7230bae3b9e 39a9b7a3171cb8b3 18 4 0bae3b9e42415649 171cb8b3ccaca55e 34 4241564918b3fa41 acaca55ed16c3653 37 6 18b2fa419616fe23 d16c3653cf402c68 33 7 9616fe2367117cf2 cf402c682v2cefbc 32 8 67117cf2c11bf609 2b2cefbc99f91153 Round δ 9 c11bfc09887fbc6c 99f911532eed7d94 32 10 887fbc6c600f7e8b 2eed7d94d0f23094 34 11 600f7e8bf596506e d0f23094455da9c4 37 12 f596506e738538b8 455da9c47f6e3cf3 31 13 738538b8c6a62c4e 7f6e3cf34bc1a8d9 29 14 6a62c4e56b0bd75 4bc1a8d91e07d409 33 15 56b0bd7575e8fd8f 1e07d4091ce2e6dc 16 75e8fd8f25896490 1ce2e6dc365e5f59 IP-1 da02ce3a89ecac3b 057cde97d7683f2a 45

DES 예제 DES 쇄도효과 : 키변화 46 Round δ 02468aceeca86420 12468aceeca86420 1 1 3cf03c0fbad22845 3cf03c0f9ad628c5 3 2 bad2284599e9b723 9ad628c59939136b 11 99e9b7230bae3b9e 9939136b768067b7 25 4 0bae3b9e42415649 768067b75a8807c5 29 5 4241564918b3fa41 5a8807c5488dbe94 26 6 18b3fa419616fe23 488dbe94aba7fe53 7 9616fe2367117cf2 aba7fe53177d21e4 27 8 67117cf2c11bfc09 177d21e4548f1de4 32 Round δ 9 c11bfc09887fbc6c 548f1de471f64dfd 34 10 887fbc6c600f7e8b 71f64dfd4279876c 36 11 600f7e8bf596506e 4279876c399fdc0d 32 12 f596506e738538b8 399fdc0d6d208dbb 28 13 738538b8c6a62c4e 6d208dbbb9bdeeaa 33 14 c6a62c4e56b0bd75 b9bdeeaad2c3a56f 30 15 56b0bd7575e8fd8f d2c3a56f2765c1fb 16 75e8fd8f25896490 2765c1fb01263dc4 IP-1 da02ce3a89ecac3b ee92b50606b62b0b 46

쇄도 효과(Avalanche Effect) 평문이나 키의 작은 변화가 암호문에 대하여 중요한 변화 발생

DES의 강점 56비트 키 사용 평균 탐색시간 10시간으로 축소 미 정부의 채택 이후 DES의 보안 수준에 대한 우려가 지속 usec당 하나의 암호를 수행하는 장치 1백만개로 구성된 병렬기계 구성 평균 탐색시간 10시간으로 축소 1998년 7월 EFF(Electronic Frontier Foundation)가 $250,000 이하의 비용으로 제작된 ‘DES해독기’를 통해 DES 알고리즘 해독

DES 알고리즘의 성질에 대한 우려 DES 알고리즘 자체 성질을 이용한 해독 가능성 8개의 치환 표 또는 S-box 전체 알고리즘에 대한 설계기준이 공개된 적이 없다. S-box의 약점에 대해 알고 있는 공격자가 해독할 수 있게 설계 됐을 가능성에 대한 의혹 제기 수년간 S-box의 수많은 정규성과 예측 못할 동작이 발견 그럼에도 S-box에 대하여 치명적인 약점을 발견한 사람은(적어도 그러한 발견이 공개된 적은)아직까지 없다.

Timing 공격 암호문을 복호화 하는데 걸리는 시간을 관측하여 키 또는 평문의 정보를 획득 입력에 따라 처리시간이 다르다는 것을 이용 아직까지는 성공 사례가 없으나 흥미로운 연구

차분 및 선형 암호 해독 차분 암호 해독 (Differential Cryptanalysis) DES에 적용해서 널리 알려짐 255 미만의 복잡도로 DES를 해독 247의 선택평문을 가지고 247 차수로 DES를 해독 선형 암호 해독 (Linear Cryptanalysis) 247 기지 평문으로 해독가능 기지 평문이 선택 평문보다 구하기 쉽지만 DES공격으로서의 선형 암호 해독은 가능성이 없다. 선형 암호 해독의 타당성 주장이 약하다.

블록 암호설계의 원리 DES의 설계기준 S-Box 설계기준 출력비트가 입력비트와 유사해서는 안됨 입력들 사이에 0이 아닌 6비트 차이는 그러한 차이를 나타내는 입력은 32쌍 중 오직 8쌍은 같은 출력을 야기 3개의 S박스의 경우 이 설계기준을 따름 52

블록 암호설계의 원리 DES의 설계기준 순열P 설계기준 i번째 반복에서 각 S박스로부터의 4개의 출력 비트가 분산되어 2비트는 (i+1)번째 반복의 중간비트에 영향을 미치고 다른 2비트는 양끝 비트에 영향을 줌 각 S박스의 출력 4비트는 다음 반복에서 6개의 다른 S박스에 영향을 주며, 같은 S박스에 영향을 주지 않음 2개의 S박스 j, k에서 j=k에 대하여 Sj의 한 출력비트는 Sk의 중간비트에 영향을 주어서는 안됨 알고리즘의 확산을 증가시키기 위한 기준 53

블록 암호설계의 원리 라운드의 수 라운드의 수가 많으면 F함수가 약하더라도 암호 해독은 어려움 전사적 키 탐색 공격 이상의 노력이 요구되도록 라운드 수 선정 F함수 설계 치환 결과를 복구하기 난해해야 함 엄격한 쇄도 기준 모든 i와 j에 대하여 어떤 입력비트 i가 바뀌면 S박스의 출력비트 j는 ½의 확률로 바뀌어야 함 비트 독립기준 입력비트 i가 바뀌면 출력비트 j, k가 바뀌어야 함 54