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

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

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

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

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 5

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 6

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

현대 블록암호 2개 라운드 처리과정 8 비트 평문이 라운드 키와 배타적 논리합 연산으로 서로 섞인다 2 비트씩 분할되어 4 개의 S-박스로 입력된다 S-박스의 출력 값은 P-박스 를 통해 전치된 후, 다음 라운드의 입력 값이 된다 2개의 라운드로 구성된 합성함수 8 8

현대 블록암호 용어 확산(Diffusion) 혼돈(Confusion) 암호문과 평문 사이의 관계를 숨기는 기능을 한다 확산기능을 통해 공격자가 언어의 출현빈도(언어의 통계적 특성)에 의한 암호문 해독을 불가능하게 한다 혼돈(Confusion) 암호문과 키 사이의 관계를 숨기는 기능을 한다 공격자가 암호문을 이용하여 키를 찾는 것을 불가능하게 한다 9 9

현대 블록암호 실제 암호 확산과 혼돈 성질이 많을 수록 좋은 암호가 된다. 확산과 혼돈 성질을 향상시키기 위해 좀 더 큰 평문 블록, 많은 S- 박스, 많은 라운드를 사용한다 더 많은 라운드를 사용할수록 평문과 암호문과의 관계 더욱 숨기게 되고(확산), 라운드 키 k i 개수의 증가로 암호문과 키와의 관계도 숨기는 효과를 얻게 된다 10 10

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)로 출력한다 11

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 12

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

DES 암호의 2가지 성질 쇄도효과(Avalanche effect) 평문의 작은 차이가 암호문에서 상당한 차이를 야기하는 것을 말한다 1 비트만 다른 2개의 평문 블록을 동일한 키를 가지고 암호한 출력 값들의 차이를 보자. 암호문 1 암호문 2 14

DES 암호의 2가지 성질 쇄도효과(Avalanche effect) 2 개의 평문 블록이 가장 오른쪽 1 개 비트만 다를지라도, 암호문은 29 개의 비트가 다름을 알 수 있다.(A : 10,B : 11,C : 12,D : 13,E :14,F : 15) 4 7 8 9 F D 4 7 암호문 1 1 1 1 1 A 4 E D 5 C 1 암호문 2 1 1 1 1 6 E 8 2 A 5 F 1 암호문 1 1 1 1 1 5 A 6 3 F E A 3 암호문 2 1 1 1 1 15

DES 암호의 2가지 성질 쇄도효과(Avalanche effect) 2 개의 평문 블록이 가장 오른쪽의 비트만 다를지라도, 암호문은 29 개 의 비트가 달라져 있다. 이것은 평문의 약 1.5 퍼센트가 변하는 것은 암호문에서 약 45 퍼센트의 변화를 만들어낼 수 있다는 것을 의미한다. 아래 표는 각 라운드에서 발생하는 변화를 보여준다. 그리고 세 번째 라운드에서 이미 상당한 변화들이 생김을 알 수 있다. 16

DES 암호의 2가지 성질 완비성 효과 (Completeness effect) 완비성 효과라는 것은 암호문의 각 비트는 평문의 많은 비트들에 의존해야 한다는 것을 말한다. DES 는 P-박스와 S-박스에 의해 확산(diffusion)과 혼돈(Confusion) 효과를 얻는데, 확산과 혼돈으로 매우 강한 완비성 효과를 구현할 수 있다. 17

DES 암호의 취약 키 취약 암호키(Weak keys) DES 암호에는 4 개의 취약 암호 키가 있다 64비트 암호 키에서 패리티 비트를 제거한 후, PC-1 테이블을 처리한 결과가 모두 1 또는 0 이거나, 반은 1이고 반은 1로 구성된다 18

DES 암호의 취약 키 취약 암호키의 문제점 취약키로 평문 블록을 암호 한 후, 그 결과에 동일한 취약키로 또 암호하면 원래의 평문 블록을 얻게 된다 19

DES 암호의 취약 키 준 취약 암호키(Semi weak keys) DES 암호에는 6개 쌍의 준 취약키가 있다 2가지 형태의 라운드 키만 생성하고 각 형태의 라운드 키는 8번 반복 한다 각 쌍의 준 취약 키는 순서만 다를 뿐 동일한 라운드 키를 생성한다 20

DES 암호의 취약 키 준 취약 암호 키 첫 번째 키 쌍으로 생성된 라운드 키이다 첫 번째 준 취약 키로 만들어진 라운드 키 1은 두 번째 준 취약 키로 만들어진 라운드 키 16과 동일하다 . 나머지 라운드 키도 동일하다 21

DES 암호의 취약 키 가능한 취약 암호키(possible weak keys) 취약 암호 키 등을 선택할 확률 48 개가 있다 48 개가 있다 4가지 형태의 라운드 키만 생성한다 취약 암호 키 등을 선택할 확률 DES는 2 개의 원소로 이루어진 키 집합을 갖는다. 취약 키, 준 취약 키, 가능한 취약 키의 총 개수는 64(4 + 12 + 48) 이다. 이런 키들이 선택될 확률은 8.8 × 10 이기 때문에, 이들 키들이 선택되는 것은 거의 불가능하다 56 -16 22

2중 DES 와 3중 DES 23

DES 알고리즘 2중 DES 2개의 서로 다른 키(K1, K 2 )로 2번 암호 및 복호한다  2 중 DES 암호 : C = E k2 (E k1(m) )  2 중 DES 복호 : m = D k1 (D k2(c)) 24

DES 알고리즘 2중 DES 안전성 2 중 DES 의 키 길이는 112 비트(k1, k2 각각 56 비트)이다 그러나 중간충돌공격(meet-in-the –middle)을 하면 키를 2 번만 찾으면 k1, k2 키를 찾을 수 있다 112 57 25

DES 알고리즘 중간충돌공격 공격자가 한 쌍의 평문과 암호문 ( m, c )을 가지고 있다면 다음과 같은 성질이 만족된다  E k1(m) = M = D k2(c)  평문 m 에 2 개의 모든 가능한 k1 을 적용하여 암호 한 중간결과인 M 값을 테이블에 정렬한다  2 개의 모든 가능한 k2 을 C 에 적용하여 복호한 값도 테이블에 정렬 한다  2 개의 테이블에 정렬된 암호된 값과 복호된 값 사이에 일치하는 항목에 대한 k1 , k2 값을 찾는다. 56 56 26

DES 알고리즘 중간충돌공격 27

DES 알고리즘 2중 DES의 안전성 k1 , k2 값을 찾는데 2·2 번의 계산작업이 필요하다 암호 및 복호 결과를 테이블에 정렬한 후, 일치하는 항목을 찾는 작업 소요시간이 필요하다 따라서 이중 DES 에서의 암호분석에 걸리는 작업소요 시간은 약 2 정도이다 결과적으로 2중 DES는 단일 DES 에 비하여 안전성이 증가되었다고 보기 어렵다 56 64 28

DES 암호알고리즘 3중 DES 2개의 서로 다른 키 (K1 , K2) 로 암호 할 경우 암호-복호-암호 순으로 반복한다 복호 할 경우 복호-암호-복호 순으로 반복한다  3중 DES 암호 : C = E K1 (D K2 (E K1 (m) ) ) Encrypt-Decrypt-Encrypt  3 중 DES 복호 : m = D K1 (E K2 (D K1 (C) ) ) Decrypt-Encrypt- Decrypt 3중 DES의 유효한 암호공격은 아직 발표되지 않았다 29

DES 알고리즘 삼중 DES 처리개념도

AES (Advanced Encryption Standard) 31

AES 암호 알고리즘 AES의 개요 AES 는 2001년 미국 국립기술 표준원(NIST) 에서 공표한 대칭 키 암호 알고리즘이다. AES는 128 비트 평문을 128 비트 암호문으로 만드는 알고리즘이다. AES는 128, 192, 256 비트의 암호 키를 사용하고 키 크기에 따라 각각 10, 12, 14 라운드를 갖는 3 가지 버전이 있다. 암호 키의 크기가 달라도 라운드 키는 모두 128 비트이다. 라운드 키 수는 라운드 수보다 하나 더 많다.  라운드 키의 수 = Nr + 1 ( Nr : 라운드 수) 32

AES 암호 알고리즘 AES의 개념도 33

34

AES 암호 알고리즘 데이터 단위 바이트(Byte) 워드(Word)  4 바이트 블록(Block)  16 바이트  16 바이트 스테이트(State)  16 바이트  4 × 4 행렬  Src (r: 행, c: 열) 35

AES 암호 알고리즘 블록을 스테이트로 표현하기 블록 값이 열 순으로 정렬됨 36

AES 암호 알고리즘 블록을 스테이트로 표현하기(예) 평문블록 “ AES uses a matrix” 을 스테이트로 표현해보자 평문블록은 14 개 문자이기에 에 가짜 문자 “ZZ”를 추가하여 16 바이트로 만든다 각 문자에 0~25 까지 정수로 표현한 후, 그 정수 값을 16 진수로 나타냄 17 17 37

AES 암호 알고리즘 라운드 함수 AES는 마지막 라운드를 제외한 각 라운드에서 4개의 변환을 사용한다  SubBytes  ShiftRows  MixColumns  AddRoundKey 라운드 함수에 적용되기 전에 AddRoundKey 변환을 적용한다 마지막 라운드에서는 3개의 변환만 사용한다(MixColumns 제외) 38

AES 암호 알고리즘 라운드 함수 AES 라운드의 각 변환은 하나의 스테이트를 입력 으로 받아서 다른 스테이트 를 생성한다 39

AES 암호 알고리즘 라운드 함수 40

AES 암호 라운드의 변환 바이트 치환 변환(Substitute Bytes Trans.) SubBytes는 AES의 암호화 과정에서 사용되는 치환함수이다. 각 바이트를 4 비트씩 2개의 16진수로 계산하여 왼쪽 4비트를 S-박스 의 행을, 오른쪽 4비트를 열을 지정하여 테이블을 읽는다. 16번의 변환이 일어난다 41

AES 암호 라운드의 변환 바이트 치환 변환(SubBytes) 두 개의 바이트 (5A)16 과 (5B)16은 1개 비트만 다르지만, SubBytes 변환으로 (BE)16 과 (39)16 으로 변환되어 4개 비트가 달라진다 42

AES 암호 라운드의 변환 바이트 치환 변환(SubBytes) 43

AES 암호 라운드의 변환 바이트 역치환 변환(InvSubBytes) 44

AES 암호 라운드의 변환 바이트 치환 변환(SubBytes) 평문의 입력 블럭을 SubBytes 변환으로 처리한 후, InvSubBytes 를 통해서 원래의 값으로 복원할 수 있다. 17 F0 45

AES 암호 라운드의 변환 행 이동변환(ShiftRows) 바이트 단위로 왼쪽 이동을 통하여 전치를 한다 이동하는 바이트 수는 행 번호에 의존한다

AES 암호 라운드의 변환 열 혼합변환(MixColumns) 열 단위로 4개 바이트에 대하여 상수 정방행렬과 연산하여 각 바이트내의 비트들을 서로 섞어 새로운 바이트를 생성한다. 상수행렬 47

AES 암호 라운드의 변환 열 혼합변환(MixColumns) 다음은 열 단위로 4개 바이트에 대하여 16진수 상수 정방행렬과 연산하는 방법이다  16진수 곱셈을 의미한다 48

AES 암호 라운드의 변환 혼합변환(MixColumns) 다음은 열 단위로 4개 바이트에 대하여 16진수 상수 정방행렬과 연산하는 방법이다  16진수 곱셈을 의미한다 49

Thanks Chul Ho Rhee richman3@naver.com 50