제10장 메시지 인증과 해쉬 함수 Message Authentication and Hash Functions 2007. 12.

목 차 10.1 메시지 인증 개요 10.2 인증 함수 10.3 메시지 인증코드 10.4 해쉬 함수 10.5 해쉬 함수와 MAC 보안 2

10.1 메시지 인증 개요 메시지 인증이란? 전송 중인 메시지 내용의 무결성을 보장하기 위한 방법 메시지 인증 메시지 암호화 방식 해쉬함수를 이용한 방식 MAC(Message Authentication Code)가 대표적 방식 초기에는 DES의 CBC 운영 모드를 이용하여 MAC생성 최근에는 해쉬 함수 기반의 MAC생성 방식을 주로 사용 3

10.1 메시지 인증 개요 메시지 인증 일반 모델 M | | C Source Destination K 만일 수신된 MAC과 계산된 MAC이 일치한다면 수신자는 메시지가 변경되지 않았다고 확신할 수 있음 수신자는 합법적 송신자로부터 메시지가 왔다고 확신함 M | | C Compare K CK(M) Source Destination K 4

10.1 메시지 인증 개요 메시지 인증의 필요성 1.노출(disclosure): 제3자에게 메시지 내용이 노출 2.트래픽 분석(traffic analysis): 통신 주체 사이의 어떤 트래픽 형태를 발견 3.위장(masquerade): 부정한 출처로부터의 메시지 삽입 4.내용수정(content modification): 메시지 내용의 변경 5.순서수정(sequence modification): 메시지들의 순서 수정 6.시간수정(timing modification): 메시지의 지연과 재전송 7. 부인(repudiation) : 메시지의 송신이나 수신 부인 5

10.2 인증 함수 10.2.1 메시지 암호화 10.2.2 메시지 인증 코드 10.2.3 해쉬 함수 6

10.2 인증 함수 메시지 인증  (2단계로 동작) 인증자(authenticator) 생성 단계 인증자 검증 단계 인증자 생성 함수의 유형 메시지 암호화 : 전체 메시지의 암호문이 인증자로 제공 메시지 인증 코드(MAC : Message Authentication Code) 초기에는 DES의 CBC 운영 모드를 이용하여 MAC생성 최근에는 해쉬 함수 기반의 MAC생성 방식을 주로 사용 해쉬 함수 7

10.2.1 메시지 암호화 1) 관용 암호 방식의 이용 기밀성 제공 A와 B 만이 K를 공유하고 암/복호화 가능 단순한 인증 제공 K를 아는 A만이 해당 암호문 작성 가능 서명 제공 불가 수신자가 메시지 위조 가능; 송신자가 메시지 부인 그림 11.1(b) 8

10.2.1 메시지 암호화(cont’) 2) 단순 공개키 암호 방식의 이용 기밀성 제공: 메시지를 복호화할 수 있는 사용자는 B 뿐임 인증은 제공하지 못함: 아무나 B의 공개키를 이용할 수 있음 E M D KU KR EKU (M) b 그림 11.1(b) 9

10.2.1 메시지 암호화(cont’) 3) 단순 공개키 암호 방식의 이용(2) 인증과 디지털 서명은 제공하나 기밀성은 제공하지 않음 기밀성 제공 누구나 A의 공개키를 가질 수 있고 복호화가 가능 인증과 디지털 서명 제공 A 만이 메시지를 생성할 수 있음 B도 암호문의 구성은 할 수 없음 E M D KR a KU EKR (M) 그림 11.1(c) 10

10.2.1 메시지 암호화(cont’) 4) 공개키 암호방식의 2중 적용 M E D 인증과 디지털 서명 제공 KUa 로 복호화 될 수 있는 암호문은 KRa 소유자만 작성 가능 기밀성 제공 KUb로 암호화된 이미지는 KRb 소유자만 복호화 가능 M E D KR a EKR (M) KU b EKU [EKR (M)] 그림 11.1(d) 11

10.2.2 메시지 인증 코드 암호학적 점검 값인 MAC을 메시지에 추가하는 방식 암호학적 점검값 비밀키를 사용하여 생성된 작은 크기의 데이터 블록 메시지와 키의 함수 : MAC = Ck(M) 메시지+MAC을 전송하고 수신측에서는 계산한 MAC 과 수신한 MAC을 비교하여 인증 수신자는 메시지 변경이 없음을 확신함 수신자는 합법적인 송신자로부터 메시지가 왔음을 확신함 메시지 내에 순서번호가 있는 경우 수신자는 합법적 순서를 확신함 송수신자 같은 키를 사용하므로 디지털 서명 기능은 제공하지 못함 12

10.2.2 메시지 인증 코드(cont’) 1) 암호학적 점검값 사용(1) 메시지 내용 인증 K를 모르는 공격자가 메시지와 대응되는 점검값 구성 불가 출처 인증 K를 아는 A 만이 올바른 점검값 작성하여 전송 가능 M | | C Compare K CK(M) Source Destination 13

10.2.2 메시지 인증 코드(cont’) 2) 암호학적 점검값 사용(2) 인증 제공 : A와 B만이 K1을 공유 평문 + 인증 : 평문 즉시 사용 가능, 인증은 필요시 수행 M | | C Compare K1 Source Destination E D K2 EK [M||CK (M)] 1 2 CK (M) 14

10.2.2 메시지 인증 코드(cont’) 3) 암호학적 점검값 사용(3) 인증 제공 : A와 B만이 K1을 공유 암호문 + 인증 : 복호화후 평문 사용가능,인증을 위해서는 암호문 필요 C K1 M | | E K2 Compare D EK [M] 2 CK (EK [M]) 1 15

10.2.3 해쉬 함수 해쉬함수(hash function): 임의의 길이에 이진 문자열을 고정된 길이의 이진 문자열(해쉬값, 메시지 다이제스트, 메시지 지문)로 매핑하여 주는 함수 임의의 비트열 고정 비트열 Hash function 16

10.2.3 해쉬 함수 1) 해쉬 함수 사용 (1) 인증 제공 H(M)을 관용키 암호화 방식으로 보호함 기밀성 제공 A와 B만이 K를 공유 M | | H Compare Destination E D K EK[M||H(M)] H(M) Source (a) 17

10.2.3 해쉬 함수(cont’) 2) 해쉬 함수 사용(2) 인증 제공 H(M)만을 관용키 방식으로 암호학적 보호 메시지 내용 무결성 보장 기밀성을 요구하지 않는 응용에서 처리 부하 경감 M | | H E K EK[H(M)] D Compare 18

10.2.3 해쉬 함수(cont’) 3) 해쉬 함수 사용(3) 인증 제공 H(M)을 공개키 암호 방식으로 보호 디지털 서명 A만이 EKRa[H(M)]을 생성 가능 Destination Source M | | H E KR EKR [H(M)] D KU Compare a 19

10.2.3 해쉬 함수(cont’) 4) 해쉬 함수 사용(4) 인증(디지털 서명) 제공 공개키 방식 사용, EKRa[H(M)] 기밀성 제공 메시지도 암호화, A와 B만이 K를 공유 M | | H Compare KRa KUa E D K EK[M||EKR [H(M)]] a EKR H(M) 20

10.2.3 해쉬 함수(cont’) s 5) 해쉬 함수 + 비밀값 사용(1) M | | H S : A 와 B 공통의 비밀값 인증 제공: A와 B만이 S를 공유 암호화 회피 이유 암호화 소프트웨어는 느리고, 하드웨어는 비용 증대 아주 작은 데이터 블록에도 동일한 암호화 절차 필요 s M | | H Compare H(M||S) 21

10.2.3 해쉬 함수(cont’) s 6) 해쉬 함수 + 비밀값 사용(2) M | | E D 인증 제공 A와 B만이 S를 공유 기밀성 제공 A와 B만이 암/복호키 K를 공유 M | | H s E D K EK[M||H(M||S)] Compare H(M||S) 22

10.3 메시지 인증 코드 10.3.1 MAC의 요구 조건 10.3.2 DES에 기초한 메시지인증 코드 23

10.3 메시지 인증 코드 암호학적 점검 값 또는 메시지 인증 코드 (MAC) 또한 Cryptographic checksum이라고도 부름 키에 종속된 일방향성 해쉬함수: MAC = CK(M) M : 가변 길이 메시지 K : 송신자와 수신자만의 공유 비밀키 CK (M) : 고정 길이의 인증자 비밀키를 공유한 사람만이 메시지의 생성과 인증이 가능 MAC 자체는 메시지 기밀성이나 서명기능을 제공하지 않음 24

10.3.1 MAC의 요구 조건 공격자가 CK(M’)=CK(M)인 M’을 구성이 계산적으로 어려워야 함 n이 점검값 비트수 일 때 CK(M)=CK(M’)일 확률은 2-n 메시지의 어떤 부분이나 특정 비트들이 특별히 취약해서는 안됨 공격자가 “취약지점”에서 M의 변형을 시도 가능 25

10.3.2 DES에 기초한 메시지 인증 코드 FIPS PUB 113과 ANSI 표준(X9.17)이 널리 사용됨 ON 또는 가장 왼쪽 M 비트를 DAC(Data Authentication Code)로 사용 16 ≤ M ≤ 64 D1 (64 bits) D2 DES encrypt K (56 bits) + O1 O2 Time = 1 Time = 2 DN – 1 ON – 1 Time = N – 1 DN ON Time = N • • • DAC (16 to 64 bits) 26

10.4 해쉬 함수 10.4.1 해쉬 함수의 요구 조건 10.4.2 단순 해쉬 함수 10.4.3 블록 체이닝 기법 27

10.4 해쉬 함수(Hash function) M(메시지) Message Digest (Fixed Length) h=H(M) 메시지 모든 비트들에 대한 함수 즉, 쇄도 효과가 큼 정의 임의의 길이 메시지(M)를 취해서 정해진 크기(h)의 Message Digest를 만드는 일방향성 함수(H) 디지털 서명, 인증, 무결성, 부인 봉쇄 등의 서비스 제공 M(메시지) Message Digest (Fixed Length) h=H(M) 28

10.4.1 해쉬 함수의 요구 조건 어떤 크기의 메시지 M에도 적용 가능 H는 고정된 크기의 hash code를 생성 H(M)은 주어진 M에 대하여 계산하는 것이 쉬워야 함 H(x) = h인 x을 찾는것이 계산적으로 불가능(one-way) h(x)가 주어졌을 때 h(x’)=h(x)인 x’( ≠x)을 찾는 것은 계산적으로 어렵다. h(x’)=h(x)인 서로 다른 임의의 두 입력 x와 x’을 찾는 것은 계산적으로 어렵다. ⇒ 생일 공격의 방어 가능 [NECH92]: [NECH92]: 메시지 메시지 인증에 인증에 유용한 유용한 해쉬함수의 해쉬함수의 특징 특징 요구사항 요구사항 1. 어떤 크기의 메시지 M에도 적용 가능 2. H는 고정된 크기의 hash code를 만듦 3. H(M)은 어떤 주어진 M에 대해서도 계산하는 것이 쉬워야 한다. 4. 주어진 hash code h에 대해, Ø H(x) = h인 x을 찾는 것이 계산적으로 실행불가능(one-way) 5. 어떠한 블록 x에 대해서도, H(y) = H(x)인 어떤 (y ¹ x) 쌍을 찾는 것 이 계산적으로 불가능 6. H(x) = H(y)인, 어떤 (x, y) 쌍을 찾는 것이 계산적으로 실행 불가능 (collision-free) 29

10.4.2 단순 해쉬 함수 모든 블록의 비트 단위 XOR연산을 한다. 가장 단순한 해쉬 함수들 중의 하나 생성 과정 Ci = bi1 Å bi2 . . . Å bim Ci는 i번째비트 해쉬코드 m는 블록 수 bij는 j 번째 블록의 i 번째 비트 Å 는 XOR 연산 30

10.4.3 블록 체이닝 기법 비밀키 없는 CBC 기술에 기반한 해쉬 함수 Rabin의 제안 메시지 M을 고정된 크기의 블록 M1, M2, , MN으로 나누고, 해쉬 코드 G를 계산하기 위해서 DES와 같은 관용 암호 시스템을 이용 H0 = 초기값 Hi = EMi [Hi-1] G = HN CBC 와 유사하나 비밀키가 없음 생일공격에 취약 알고리즘이 DES이고 오직 64-비트 해쉬 코드를 생성 31

10.4.4 블록 체이닝 기법(cont’) key E Hi key E Hi 개선된 제안 1)Hi= EMi[Hi-1] Å Hi–1 2)Hi= EHi-1[Mi] Å Mi 두 가지 구조 모두 다양한 공격에 취약 E key Hi Mi Hi –1 E key Hi Hi–1 Mi 32

10.5 해쉬 함수와 MAC 보안 10.5.1 생일 공격(Birthday Attacks) 10.5.2 Brute-Force 공격 10.5.3 암호학적 분석 33

10.5.1 생일 공격 생일 공격은 전사적 공격의 일종 Birthday Paradox(생일 역설) 23명 중, 같은 생일을 가진 사람이 두 사람 이상 있을 확률이 1/2보다 크다 증명 M개의 통에 N개의 구술을 임의로 넣는다. M개의 통 중에 2개이상 구술이 들어 있는 통이 있을 확률: Prob = 1-(N개의 구술 모두 다른 통에 들어갈 확률) 34

10.5.2 Brute-Force 공격 1)해쉬 함수 Brute-force 공격에 대한 해쉬 함수의 강도는 오직 알고리즘에 의해 생성되는 해쉬 코드의 길이에 의존 해쉬 함수의 특성 일방향성: 입력을 모르는 해쉬값 y가 주어졌을 때, h(x’)=y를 만족하는 x를 찾는 것은 계산적으로 어렵다. 약한 충돌회피성: h(x)가 주어졌을 때 h(x’)=h(x)인 x’( ≠x)을 찾는 것은 계산적으로 어렵다. 강한 충돌회피성: h(x’)=h(x)인 서로 다른 임의의 두 입력 x와 x’을 찾는 것은 계산적으로 어렵다. 35

10.5.2 Brute-Force 공격(cont’) 2) 메시지 인증 코드 MAC에 대한 전사적 공격은 알려진 메시지-MAC 쌍이 있어야 가능하므로 더욱 어려움 코드 길이가 n-비트인 경우 충돌을 찾는 brute-force 방식은 무작위 비트 열 y를 선택해 H(y)=H(x) 인지 확인 공격이 가능한지의 여부는 MAC과 키의 상대적 크기에 따라 결정됨 계산적 어려움(Computation resistance) : 하나 또는 그 이상의 문서-MAC쌍들 (xi, CK(xi))이 제공된 경우, 새로운 입력 값 x ≠ xi가 되는 (x, CK(x))를 계산하는 것은 불가능 36

10.5.2 Brute-Force 공격(cont’) 공격의 형태 키 공간 공격 : 키 크기가 k일 경우 2k 이상 MAC 값 공격 : MAC의 크기가 n 일 경우 2n 공격 노력 : min(2k, 2n) ⇒ 따라서 min(k, n) ≥ 128을 만족하여야 함 37

10.5.3 암호학적 분석 이상적인 해쉬 함수 또는 MAC에 대한 암호학적 강도는 brute-force 효율성과 같거나 큼 1) 해쉬 함수들 Merkle에 의해 제안된 구조 MD5, SHA-1, RIPEMD-160 등 현재 사용 대부분의 해쉬 함수 구조 입력 메시지를 고정길이(b-비트)인 L개의 블록으로 분할 마지막 블록은 입력된 전체 메시지의 길이를 포함함 해쉬 알고리즘은 두 개의 입력으로 n-비트의 출력을 생성 최종 CV(Chaining Variable)가 해쉬 값으로, “블록 크기(b) > 해쉬 값 길이(n)”가 되어 압축이 이루어짐 공격은 함수 f 의 구조와 f 의 충돌들을 효율적으로 찾는 것에 촛점을 둠 38

10.5.3 암호학적 분석(cont’) 그림 11.10 : 안전한 해쉬 함수 39

10.5.2 암호학적 분석(cont’) 2) 메시지 인증 코드 MAC의 구조가 해쉬 함수의 구조보다 더욱 다양함 40

41