전자상거래 보안 (암호학과 네트워크보안) 2017.3.29 Chul Ho Rhee richman3@naver.com

현대 블록암호 차분공격 암호 알고리즘이 단지 배타적 논리합 연산으로만 구성된다고 하자. 암호 키 값을 알지 못하더라도, 평문의 차분을 P1 P2 로 정의하고, 암호문의 차분을 C1 C2 로 정의하면, 공격자는 평문차분과 암호문 차분 사이의 관계(C1 C2 = P1 P2 )를 쉽게 발견할 수 있다. P1과 P2의 차분과 C1과 C2의 차분 (C1 C2 = P1 P2 ) 을 이용하면 암호 키의 효과를 없게 할 수 있다. 2 2

현대 블록암호 차분공격 배타적 논리합 연산에 S-박스를 추가한 암호 알고리즘을 가정하자. S-박스를 추가하면, 평문인 P1과 P2의 차분과 암호문 C1와 C2 관계 를 찾는 것을 힘들게 한다. 그러나, 공격자는 평문 차분에 대하여 암호문 차분이 얼마나 발생 하는지 차분표 를 만든다 3 3

현대 블록암호 차분공격 암호 키 길이가 3비트이므로 입력차분은 총 8가지 경우가 생긴다 S-박스 표에 의해 입력차분이 (100)2 이면 출력차분은 (00)2인 경우 2가지, 출력차분이 (01)2 인 경우 2가지, 출력차분이 (10)2 인 경우 4가지 이다 4 4

현대 블록암호 차분공격 공격자는 확률적 정보를 제공하는 차분분포표를 만들 수 있다. 표의 성분은 입력차분에 대하여 출력차분이 발생할 확률을 나타낸다 0 확률은 결코 발생할 수 없는 경우이다 5 5

현대 블록암호 차분공격 공격자는 0.5(50%)의 확률로 P1 P2 = 001이면, C1 C2 = 11 을 만족함을 알 수 있다. 공격자는 암호문 C1 = 00 에 대한 평문 P1 = 010과 암호문 C2 = 11 에 대한 평문 P2 = 011 을 가지고 있다고 하자 첫 번째 쌍 P1 과 C1 을 이용하여 역으로 분석을 시도한다. 두 번째 쌍 P2 과 C2을 이용하여 역으로 분석을 시도한다. 6 6

현대 블록암호 차분공격 위 두 개의 분석을 통하여 키가 K = 011 이거나 K =101임을 확인할 수 있다. 공격자는 정확한 키는 확신할 수 없지만 오른쪽 최상위비트가 1 임을 확신할 수 있다 7 7

DES 암호 8

강의목차 현대 대칭키 암호 DES 개요 DES 암호의 구성요소 DES 암호의 처리과정 DES 암호의 취약키 9 9

DES 암호 비밀키 암호(대칭형 암호) 암호화 및 복호화 키가 동일하다. 비대칭형 암호에 비해 암호 및 복호 속도가 빠르다.(100배 이상) 이에 비밀키 암호는 문서를 암호 하는데 주로 사용된다.  공개키 암호는 비밀키의 암호 또는 전자서명에 생성에 사용됨 동일한 키 암호키 복호키 전자문서 (암호화 된) (복호화 된) Internet 수신자 송신자 10

DES 암호 비밀키 암호 문제점 키 관리 문제 비밀키는 각각 달라야 한다 ( Kab, Kac )  A 사람이 B 와 C 사람과 비밀키 암호통신을 할 경우, 사용하는 비밀키는 각각 달라야 한다 ( Kab, Kac )  n 사람이 암호화 통신할 경우 필요한 키 개수?  n · (n-1)/2 키 분배 문제  송신자가 암호 할 때 사용한 키를 수신자에게 안전하게 전달하는 방법이 필요하다  공개키 암호 사용 11

인증 및 보안기술 전자서명 및 암호기술의 적용사례 DES 암호알고리즘 DES 암호알고리즘 12

DES 암호역사 역사 1977년에 미국 표준국(NIST)이 연방정부의 정보 처리용 표준 암호 기술(FIPS: Federal Information Processing Standard 46)로 선정됨 DES는 IBM이 1971년에 만든 LUCIFER 알고리즘의 변형임  LUCIFER는 64bit의 블록에 128bit의 암호화 키를 사용 DES 는 평문을 64 bit (8문자)씩 블록으로 나누고, 64 bit 의 암호키 (실제 56 비트) 사용하여, 64 bit의 암호문을 생성한다  64 비트 암호 키 가운데 8 비트는 check digit 로 사용된다 DES의 S-Box 의 설계원리가 비공개로 초기에 많은 논란이 있었다  정부의 NIST가 복호할 수 있도록 Trapdoor(비밀문)을 둔 것으로 의심 13

DES 암호특징 특징 평문을 64 비트 단위로 나누어 각 블록에 치환(Substitution)과 전치 (Transposition)를 16 회 반복적으로 처리하여 암호화 한다 언어적 통계적 특성(문자 출현빈도)을 이용한 암호분석에 잘 견딘다. DES의 가장 좋은 암호분석 방법은 모든 키를 다 적용하는 방법이다  전수조사 공격 (brute force attack) 최근 반도체 칩 기술의 발달로 64비트 암호 키에 의한 DES 암호는 쉽게 해독 가능하다. 암호학자들은 56 비트의 암호키 길이를 112 비트로 늘려서 암호하는 2 중 DES, 3 중 DES 사용을 권고하고 있다. 14

DES 암호해독 해독 DES 의 가능한 모든 암호 키(56 비트)의 개수는 2 ≒ 7.2 10 이다 시도 해야 한다  1 µs 시간당 1 개의 암호해독을 처리하는 경우 1142년이 걸리지만,  1 µs 시간당 1 백만 개의 암호해독을 처리하는 경우 10 시간이 걸림 97년 RSA Data Security 회사에서 “DES Challenge” 행사개최 함  Rocke Verser 가 96 days 만에 암호를 해독하였다 98년 7월에 EFF 단체에서 2만5천 달러로 DES 해독기라는 특수목적 장비를 제작하여 DES 암호문을 3일 이내에 해독하였다고 발표 DES 암호는 더 이상 안전하지 않다 56 16 55 16 15

현대 대칭키 암호 개요 모든 키 탐색에 필요한 시간 전사적 공격은 가능한 모든 키를 암호문에 적용하여 평문을 찾아내 는 공격법이다 평균적으로 가능한 모든 키의 절반이 시도되어야 평문을 찾아낼 수 있다. 키 크기 가능한 키의 수 복호 시간 ( 1µs 당 1 복호) 복호 시간( 1µs 당 10 6 복호) 32 비트 232 = 4.3 × 109 231 µs = 35.8 분 2.15 ms 56 비트 256 = 7.2 × 1016 255 µs = 1142 년 10.01 hours 128 비트 2128 = 3.4 × 1038 2127 µs = 5.4 × 1024 년 5.4 × 1018 년 168 비트 2168 = 3.7  1050 2167 µs = 5.9 × 1036 년 5.9 × 1030 년 26 문자 26 ! = 4 × 1026 2×1026 µs = 6.4× 1012 년 6.4 × 106 년 모든 키 탐색을 위해 요구되는 평균시간 16

DES 암호 해독 DES 는 5년 마다 안전성에 대한 검증을 받았다  83년, 87년, 93년에 안전성에 대한 검증 및 승인하였다 미국 NIST 는 97년에 새로운 연방정부의 정보처리용 암호표준인 AES(Advanced Encryption Standard) 선정을 추진하였다.  2001년에 “Rijndael”을 AES로 발표하였다  http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf 17

DES 암호 개념도 2개의 전치박스(P-박스)와 16개의 라운드로 구성 전치작업 전치 작업 18

DES 암호 개념도 i 64비트 평문 64비트 암호키(56비트) 16 회 반복 PC : Permuted Choice IP : Initial Permutation IP L i-1 R i-1 L i = R i-1 R i = L i-1  f (R i-1, K i ) L i R i -1 PC-2 PC-1 C i-1 D i-1 Left-Shift C i D i K i 64비트 평문 64비트 암호문 64비트 암호키(56비트) 16 회 반복 i = 1,2,… 16 L16 R16 19

DES 암호 구성요소 전치박스 초기 전치박스와 최종 전치박스는 역관계이다 초기전치 58번째 입력 비트는 1번째 출력 비트가 된다 최종전치 1번째 입력 비트는 58번째 출력 비트가 된다 초기전치 58번째 입력 비트 값은 최종전치 58번째 출력 비트 값과 동일하다 20

DES 암호 구성요소 전치박스 아래 테이블은 초기 전치박스와 최종 전치박스의 전치관계를 테이블로 나타낸 것이다. 21

DES 암호 구성요소 전치박스 평문의 입력 값이 다음과 같은 16 진수일 때, 초기전치에 의한 출력 값을 찾아보자 입력 값은 최상위 비트 위치로부터 15 번째 비트와 64 번째 비트에 1의 값이 있기 때문에, 64 비트 출력 값은 두 군데의 비트에만 1의 값을 갖는다. 2바이트 64비트 평문(8바이트) 1 2 3 ……. 13 14 15 16 …. 36 37 38 …. 52 53 …. 61 63 64 1 16진수 64비트 평문 22

DES 암호 구성요소 전치박스 입력 값은 15 번째와 64 번째 비트 값만 1이고, 나머지 비트 값들은 모두 0 이다. 초기전치에서 입력 값의 15 번째 비트는 출력 값의 63 번째 비트가 되고, 입력 값의 64 번째 비트는 출력 값의 25 번째 비트가 된다 따라서 출력 값은 25번째와 63번째 1의 값을 가진다 .... .... .... .... 1 2 3 16 17 24 25 26 32 33 37 38 … 48 56 …. 57 61 63 64 1 초기전치 후 64비트 평문 23

DES 암호 구성요소 라운드 라운드는 초기전치 박스의 출력 값 또는 이전 라운드 함수의 출력 값 L i-1 과 R i-1 을 입력으로 받아서 다음 라운드의 입력 값 L I 과 R i 를 생성한다 각 라운드는 암호 혼합기(Mixer)와 스와퍼(Swapper)로 구성된다 DES 알고리즘은 16개의 라운드 함수로 구성된다

DES 암호 라운드 마지막 16번째 라운드 에는 스와퍼가 없다 25

DES 암호 구성요소 DES 함수( f 함수) 아래그림은 각 라운드에 사용되는 f (R i-1, K i) 함수의 세부 구조이다 48 비트의 라운드키를 적용한다. 32 비트출력 26

DES 암호 구성요소 확장 P-박스 R i-1 32비트이고 K i 는 48비트 이므로, R i-1 32 비트를 48 비트로 확장 시켜서 전치한다 각 4 비트 값이 6 비트 값으로 확장되는데, 입력 비트 1, 2, 3, 4 는 출력 비트 2, 3, 4, 5 로 되고, 출력 비트 1은 이전 입력 값의 4번째 비트로 부터 나오고, 출력 비트 6은 다음 입력 값의 1번째 비트로부터 나온다 확장전치 27

DES 암호 구성요소 S-박스 S-박스는 평문의 입력 비트를 치환시킨다. 사용한다 S-박스의 6비트의 입력 값 중 1과 6은 행을 결정하고, 2에서 5 까지는 열을 결정한다 28

DES 암호 구성요소 S-박스 S-박스 1 테이블 29

DES 암호 처리과정 64비트 평문 64비트 암호키(56비트) 16 회 반복 PC : Permuted Choice IP : Initial Permutation IP L i-1 R i-1 L i = R i-1 R i = L i-1  f (R i-1, K i ) L i R i -1 PC-2 PC-1 C i-1 D i-1 Left-Shift C i D i K i 64비트 평문 64비트 암호문 64비트 암호키(56비트) 16 회 반복 i = 1,2,… 16 L16 R16 30

DES 암호 처리과정  64비트(56비트)의 암호 키로부터 생성된 서브키 K1, K2, …, K16 64 비트의 평문을 초기전치(IP : Initial Permutation) 테이블을 통하여 평문의 문자를 재배열한다 실선 상자 안의 과정이 16회(round) 반복한다  초기전치를 통하여 64비트가 32비트의 L0 , R0 로 분할된다  i = 1,2…. 16 까지 아래의 연산을 수행한다  64비트(56비트)의 암호 키로부터 생성된 서브키 K1, K2, …, K16 에 의해 L1, R1, L2, R2, L3, R3……. L16, R16 까지 연산한다  L i = R i-1 , R i = L i-1  f (R i-1, K i ) 에 의해  함수 f 는 P-박스에 의한 전치(Permutation)와 S-Box 에 의한 치환 (Substitution) 을 처리한다(확산과 혼돈 구현) 31 31

DES 암호 처리과정 16 라운드의 결과인 L16 , R16 를 초기 전치(IP)의 역 전치인 IP 를 거쳐 64 비트의 암호문(C ) 을 생성함  C = IP (L16 , R16 ) -1 -1 32 32

Expansion/permutation Permutation/contraction DES 암호 세부처리과정 64(56) bit key • • • • • XOR Left shift(s) K i f 48 32 32 bits 28 bits Expansion/permutation (E-Table) Substitution/Choice (S-box) Permutation (P) Li - 1 Ri - 1 Li Ri C i - 1 D i - 1 Permutation/contraction (permuted choice 2) C i D i permuted choice 1 33

DES 암호 세부처리과정 R i-1 입력 32비트는 E-Table 의 확대전치(Expansion/Permutation) 과정을 거쳐 48비트로 확대됨  E(R i-1 )는 R i –1 의 32 비트 중 16비트는 2회씩 나타남  1, 4, 5, 8, 9, 12, 13, 16, 17, 20, 21, 24, 25, 28, 29, 32 번째 비트는 2회씩 반복하여 나타남 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 32 1 2 3 4 5 4 5 6 7 8 9 8 9 10 11 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 12 13 12 13 14 15 16 17 16 17 18 19 20 21 20 21 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 22 23 24 25 24 25 26 27 28 29 28 29 30 31 32 1 출력 입력 34

DES 암호 세부처리과정 확대전치 E-Table의 결과인 E(R i-1 ) 는 서브키 K i 와 EX-OR 된 이후 6 비트씩 8 개의 S-Box에 입력되어 32비트의 결과를 생성함  S-Box 의 입력 Bj = b1 b2 b3 b4 b5 b6 가 Sj –Box 표에 의하여 b1 b6 은 행을 지정, b2 b3 b4 b5 는 열을 지정하여 해당 값이 S j -Box 의 결과가 됨  S 1 -Box 의 입력 값 B1 = 110110 일 경우 b1 b6 = 10 이므로 행 2에 해당하고, b2 b3 b4 b5 = 1011 이므로 열 11로 지정되어 2행 11열에 위치한 7 인 값을 4비트(0111)로 출력한다 35

DES 암호 S-BOX 처리과정  Key S1 S2 S3 S4 S5 S6 S7 S8 R i , i = 1,2,3…16 E R(32 bits) Key E E-Table 48 bits K(48 bits)  6 bit 6 bit 6 bit 48 bit S1 S2 S3 S4 S5 S6 S7 S8 4 bit 4 bit 4 bit P 32 bit 32 bits R i , i = 1,2,3…16 36

DES 암호 S-BOX 테이블 S 1 S 2    S 8 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 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 1 S 1 2 3 15 1 8 14 6 11 3 4 9 7 2 13 12 0 5 10 3 13 4 7 15 2 8 14 12 0 1 10 6 9 11 5 0 14 7 11 10 4 13 1 5 8 12 6 9 3 2 15 13 8 10 1 3 15 4 2 11 6 7 12 0 5 14 9 S 2    13 2 8 4 6 15 11 1 10 9 3 14 5 0 12 7 1 15 13 8 10 3 7 4 12 5 6 11 0 14 9 2 7 11 4 1 9 12 14 2 0 6 10 13 15 3 5 8 2 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11 S 8 37

DES 암호 세부처리과정 S-Box의 출력 결과인 32비트는 다시 P –Table에 의한 전치 (Transposition/permutation) 과정을 거쳐 f (R i -1, K i ) 결과가 됨 이어서 Li-1  f (R i-1, K i ) 를 연산한다 출력 입력 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 16 7 20 21 29 12 28 17 1 15 23 26 5 18 31 10 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 2 8 24 14 32 27 3 9 19 13 30 6 22 11 4 25 P - Table 38

Expansion/permutation Permutation/contraction DES 암호 라운드 키 생성과정 64(56) bit key • • • • • 32 bits 32 bits permuted choice 1 Li - 1 Ri - 1 28 bits 28 bits C i - 1 D i - 1 Expansion/permutation (E-Table) Left shift(s) Left shift(s) 48 48 F XOR K i Permutation/contraction (permuted choice 2) 48 Substitution/Choice (S-box) 32 Permutation (P) 32 XOR C i D i Ri Li 39

DES 암호 라운드 키 생성과정 f 함수계산에 입력되는 라운드 키 K i 는 64비트 암호 키 K 에 의해 생성된다 56, 64 비트)마다 패리티 비트로 활용된다  암호 키 K 에서 실제 암호에 사용되는 길이는 56 비트 이다 40

DES 암호 라운드 키 생성과정 암호 키 56 비트를 PC-1(Permuted Choice-1) 테이블에 따라 전치한 후, 28비트의 길이로 C0, D0 구분한다 C i, D j 는 각각 LS i (Left Shift) 테이블에 의해 왼쪽으로 시프트 된 후, PC-2 테이블에 따라 56 비트가 48 비트로 축소된다  C i = LS i (C i-1), D i = LS i (D i-1)  K i = PC-2 ( C i, D i ) 41

DES 암호 PC-1 및 PC-2 전치테이블 C 0 D 0 PC-2 전치테이블 PC-1 전치테이블 Round number 1 2 3 4 5 6 7 1 2 3 4 5 6 7 8 1 2 3 4 57 49 41 33 25 17 9 1 58 50 42 34 26 18 2 59 51 43 35 27 11 3 60 52 44 36 55 47 39 31 23 15 7 62 54 46 38 30 22 6 61 53 45 37 29 21 13 5 28 20 12 4 17 11 24 1 5 3 28 6 21 10 23 19 12 4 26 8 16 7 27 20 13 2 52 31 37 47 55 30 40 51 45 33 48 44 49 39 56 34 53 46 42 50 36 29 32 C 0 1 2 3 4 D 0 PC-2 전치테이블 PC-1 전치테이블 Round number 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Bits rotated 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1 Left-Shifts Table 42

DES 암호 키 스케줄러 1 2 3 4 5 6 7 8 9 10 11 12 10 51 34 60 49 17 33 57 2 9 19 42 3 35 26 25 44 58 59 1 36 27 18 41 22 28 39 54 37 4 47 30 5 53 23 29 61 21 38 63 15 20 45 14 13 62 55 31 K 1 2 43 26 52 41 9 25 49 59 1 11 34 60 27 18 17 36 50 51 58 57 19 10 33 14 20 31 46 29 63 39 22 28 45 15 21 53 13 30 55 7 12 37 6 5 54 47 23 K 2  59 42 3 57 25 41 36 10 17 27 50 11 43 34 33 52 1 2 9 44 35 26 49 30 5 47 62 45 12 55 38 13 61 31 37 6 29 46 4 23 28 53 22 21 7 63 39 K 16 43

Thanks Chul Ho Rhee richman3@naver.com