I부 암호.

Presentation on theme: "I부 암호."— Presentation transcript:

1 I부 암호

2 해시함수와 기타 5장

3 해쉬함수 동기 앨리스가 M에 서명한다고 가정 만약 M이 크면 [M]앨리스 을 계산 비용 큼
앨리스는 M과 S = [M]앨리스 를 밥에게 전송 밥은 M = {S}앨리스 을 확인 참고사항: S 만 전송하면 괜찮은가? 만약 M이 크면 [M]앨리스 을 계산 비용 큼 앨리스가 M 보다 훨씬 적은 h(M)에 서명하다고 가정 앨리스는 M 과 S = [h(M)]앨리스 를 밥에게 전송 밥은 h(M) = {S}앨리스

4 암호학적 해시함수 암호 해시 함수 h(x) 는 다음을 제공해야 함 압축 (Compression)  출력길이가 작아야 함
효율성 (Efficiency)  어떤 x에 대해서도 h(x) 를 계산하기가 쉬워야 함 단방향 (One-way)  주어진 y값에 대해 h(x)=y를 만족하는 x 값을 찾는 것이 어려워야 함 약한 충돌 방지 (Weak collision resistance)  주어진 x와 h(x)에 대해 h(y) = h(x)를 만족하는 y  x 를 찾기 어려워야 함 강한 충돌 방지 (Strong collision resistance)  h(x) = h(y) 를 만족하면서 x  y 인 어떤 x와 y도 찾기 어려워야 함 많은 충돌들이 존재하지만, 찾기가 어려워함 함

5 생일 문제를 위한… 한 방에 N 사람이 있다고 가정

6 생일 문제 한 방에 있는 사람들 중에 2명 또는 그 이상이 같은 생일일 확률이 ½보다 크기 위해서는 얼마나 많은 사람들이 있어야 하나? 1  365/365  364/365   (365N+1)/365 위의 값이 ½과 같기 위해서는: N = 23 놀라운 일인가? 역설적인가? 아니다: “그렇게 되어야만 한다” x와 y의 모든 쌍 들을 비교해야 함으로 365의 제곱근의 대략 값이 그렇게 된다.

7 해시와 생일 만약 h(x)가 N비트이면, 2N 의 다른 해시 값들이 가능 sqrt(2N) = 2N/2
함축된 의미: 안전한 N 비트의 대칭키는 “해독”하기 위해 2N-1 의 작업이 필요하고, 안전한 N 비트의 해시는 “해독”하기 위해 2N/2 작업이 필요하다

8 비 암호 해시 (1) X = (X0,X1,X2,…,Xn-1), 각 Xi 는 한 바이트
hash(X) = X0+X1+X2+…+Xn-1 이라고 가정 이것은 안전한가? 예제: X = ( , ) 해시는 그러나 Y = ( , )의 해시도 동일하다. 쉽게 충돌을 찾을 수 있어 안전하지 않다…

9 비 암호 해시 (2) X = (X0,X1,X2,…,Xn-1) 아래와 같은 해시를 가정
h(X) = nX0+(n-1)X1+(n-2)X2+…+1Xn-1 이 해시는 안전한가? 앞 슬라이드와 달리 적어도 아래는 다르다 h( , )h( , ) 그러나 ( , ) 해시는 ( , ) 해시와 동일하다 단방향은 아니지만 이 해시는 전송 오류를 찾는 (비 암호) 응용분야에 사용

10 비 암호 해시 (3) Cyclic Redundancy Check (CRC) 근본적으로 CRC는 긴 나눗셈 문제의 나머지
전송 오류 탐지에 유용 그러나 충돌을 만들기는 쉬움. CRC 는 가끔 암호 응용 분야(WEP)에 사용되고 있으나 이는 잘못된 것임.

11 인기 있는 암호 해시들 MD5  리베스트가 발명 SHA-1  미 정부 표준 (MD5와 유사)
128 bit output Note: MD5 collision recently found SHA-1  미 정부 표준 (MD5와 유사) 180 비트 출력 많은 다른 해시들이 있지만 MD5와 SHA-1 이 가장 널리 사용 해시는 블록내의 해싱 메시지에 적용

12 암호 해시 설계 요구되는 특성: 쇄도효과 (avalanche effect) 암호 해시 함수들은 수 회전들로 구성
입력의 1 비트의 변경이 출력 비트의 절반에 영향을 주어야 함 암호 해시 함수들은 수 회전들로 구성 보안과 속도를 요구 몇 회전 후에는 쇄도 효과가 나타나야 함 그러나 회전들은 단순해야 함 블록 암호 설계와 유사

13 MD5

14 MD5 HMD5 처리 과정 fF , ABCD, Yq, T [1-16] 16회
CVq 128 Yq 512 A B C D fF , ABCD, Yq, T [1-16] 16회 A B C D fG , ABCD, Yq, T [17-32] 16회 A B C D fH , ABCD, Yq, T [33-48] 16회 A B C D fI , ABCD, Yq, T [49-64] 16회 mod 232 CVq+1

15 MD5 MD5 초기값 A = 0x B = 0x 8 9 A B C D E F C = 0x F E D C B A 9 8 D = 0x

16 MD5 MD5의 HMD5 상수 T [i]의 값 T [i ] = 232 * ABS (sin (i )) 정수부분; i 는 라디안
T[1] = D76AA478 T[17] = F61E2562 T[33] = FFFA3942 T[49] = F T[2] = E8C7B756 T[18] = C040B340 T[34] = 8771F681 T[50] = 432AFF97 T[3] = DB T[19] = 265E5A51 T[35] = 699D6122 T[51] = AB9423A7 T[4] = C1BDCEEE T[20] = E9B6C7AA T[36] = FDE5380C T[52] = FC93A039 T[5] = F57C0FAF T[21] = D62F105D T[37] = A4BEEA44 T[53] = 655B59C3 T[6] = 4787C62A T[22] = T[38] = 4BDECFA9 T[54] = 8F0CCC92 T[7] = A T[23] = D8A1E681 T[39] = F6BB4B60 T[55] = FFEFF47D T[8] = FD469501 T[24] = E7D3FBC8 T[40] = BEBFBC70 T[56] = 85845DD1 T[9] = D8 T[25] = 21E1CDE6 T[41] = 289B7EC6 T[57] = 6FA87E4F T[10] = 8B44F7AF T[26] = C33707D6 T[42] = EAA127FA T[58] = FE2CE6E0 T[11] = FFFF5BB1 T[27] = F4D50D87 T[43] = D4EF3085 T[59] = A T[12] = 895CD7BE T[28] = 455A14ED T[44] = 04881D039 T[60] = 4E0811A1 T[13] = 6B901122 T[29] = A9E3E905 T[45] = D9D4D039 T[61] = F7537E82 T[14] = FD987193 T[30] = FCEFA3F8 T[46] = E6DB99E5 T[62] = BD3AF235 T[15] = A679438E T[31] = 676F02D9 T[47] = 1FA27CF8 T[63] = 2AD7D2BB T[16] = 49B40821 T[32] = 8D2A4C8A T[48] = C4AC5665 T[64] = EB86D391

17 MD5 MD5의 HMD5 의 기본 동작 A B C D A B C D g X[K] T [i] CLSS CLSS 라운드
g : 기약 함수 F, G, H, I 중의 하나 CLSS=<<<s :32 비트 순환 좌측 쉬프트(로테이션) X[k] : 메시지의 q번째 512비트 블록 중에서 k번째 단어(32비트) T[i] : 행렬 T에서 i번째 단어(32비트) : 법 232 의 덧셈 g X[K] T [i] CLSS CLSS A B C D 라운드 기약함수 g g(b,c,d) 1 F(B,C,D) (BC)+(B D) 2 G(B,C,D) (BD)+(CD) 3 H(B,C,D) BCD 4 I(B,C,D) C(B+D)

18 MD5 라운드 기약함수 g g(b,c,d) 1 F(B,C,D) (BC)+(B D) 2 G(B,C,D)
(BD)+(CD) 3 H(B,C,D) BCD 4 I(B,C,D) C(B+D) BCD FGHI 000 001 010 011 100 101 110 111 0001 1010 0110 1001 0011 0101 1100 1110

19 SHA 알고리즘 Secure Hash Algorithm
NIST(National Institute of Standards and Technology)에서 개발 1993년에 표준으로 발표 (FIPS 180) 1995년에 개선된 버전 발표 (FIPS 180-1) SHA-1 해쉬길이: 160 비트(5개의 32 비트 워드) 입력: 264 비트 보다 작은 임의의 크기의 입력 512비트 단위로 적용 전체 입력의 크기가 512 비트의 배수가 아니면 padding을 한다. 마지막 64 비트에는 실제 크기를 기록한다.

20 SHA 알고리즘 80 word 입력 생성

21 SHA 알고리즘 서명문 형식 패딩 패턴 : 1000 64비트 : 서명문 길이 표시 상위 32비트와 하위 32비트 교환
64비트 : 서명문 길이 표시 상위 32비트와 하위 32비트 교환 L512비트=N  32비트 서명문 M  0 64 서명문 M  0 64 448 mod 512

22 SHA 알고리즘 512 비트 입력은 80개의 32비트 블록으로 확장 4 라운드, 라운드 당 20 단계
5 개의 32 비트 초기 값을 사용 A = 0x B = 0xefcdab89 C = 0x98badcfe D = 0x E = 0xc3d2e1f0

23 SHA 알고리즘

24 SHA 알고리즘

25 SHA-1과 MD5의 차이점 특성 MD5 SHA-1 다이제스트 길이 처리의 기본단위 처리 단계수 최대 메시지 크기
기약 논리 함수 덧셈 상수 128비트 512비트 64(16*4) 무한대 4 64 160비트 80(20*4) 264

26 HMAC(Hashed-MAC) 대칭 블록 암호에 기반한 MAC계산 FIPS PUB 113 (데이터인증)
암호 해쉬 함수가 대칭 블록 암호보다 빠름 암호 해쉬 함수에 대한 라이브러리 코드의 입수 용이 암호 해쉬 함수에 대한 수출 제한 없음 MD5와 같은 해쉬 함수는 비밀키에 의존하지 않음 => 비밀키를 기존의 해쉬 알고리즘에 결합 HMAC : RFC 2104, IP보안을 위한 MAC의무 구현사항 선정(SSL에서 사용)

27 HMAC 설계 목표 가용한 해쉬 함수를 변경 없이 사용 가능해야 함 해쉬 함수는 소프트웨어로 구현 가능, 무상입수 용이
내장 해쉬 함수 교체 용이(해쉬함수의 블랙 박스화) 성능 저하 없이 해쉬 함수의 원래 성능 계속 유지 간단한 방법으로 키 조작 인증 메커니즘의 암호학적 분석 이해가능

28 HMAC 구조 을 b/8번 반복 을 b/8번 반복

29 처리과정 b비트 스트링 K+ 생성 : 비밀키 K의 왼쪽에 0을 첨가 b비트 블록 Si를 생성 : K+ 와 ipad를 XOR
M을 Si 에 추가 : Msg1=[Si||M] 3단계의 Msg1에 해쉬를 적용 b비트 블록 S0를 생성 : K+ 와 opad를 XOR 단계 4에서 만들어진 해쉬함수 적용결과에 S0를 추가 6단계의 결과에 해쉬함수를 다시 적용 HMACK(M)=H[(K+ XOR opad)||H(K+ XOR ipad)||M]]

30 HMAC의 안전성 공격 시나리오 : 공격자는 해쉬 알고리즘과 디폴트 IV를 알고 있음.
그러나 K(비밀키)를 모르기 떄문에 메시지와 코드의 짝을 생성할 수 없음. ->128비트 길이의 해쉬코드 공격을 위해서는 동일한 키로 생성된 264의 블록(273 bit)을 필요로 함 250,000년 동안 키의 변경없이 연속적인 메시지 스트림 조사 속도가 중요한 경우, 내장 해쉬함수로 SHA-1나 RIPEMD160 보다 MD5 사용이 바람직함.(속도가 빠름)

31 해시 용도 인증 (HMAC) 메시지 무결성 (HMAC) 메시지 지문 데이터 변조 탐지 전자서명 효율성
대칭키 암호가 할 수 있는 어떤 것도 가능

32 온라인 입찰 앨리스, 밥, 찰리가 입찰자라 하자. 앨리스는 A, 밥은 B, 찰리는 C 금액으로 입찰
상호 입찰금이 비밀로 지키질 것을 신뢰하지 못함. 앨리스, 밥, 찰리는 해시 h(A), h(B), h(C)를 제출 모든 해시는 온라인 상에 게시 그리고 A, B, C 를 공개 해시는 입찰금을 공개하지 않음.(단방향) 해시 전송후는 입찰금을 변경할 수 없음.(충돌)

33 5장. 해시함수 및 기타 비밀 공유

34 샤미르의 비밀 공유 두 점이 한 선을 결정 (X0,Y0): 앨리스 Y (X1,Y1): 밥
앨리스와 밥은 비밀 S를 찾기 위해 서로 협조해야만 함 실수보다 이산수로 작업 m  n 경우 “n 중의 m” 체계를 만들기 용이 Y (X1,Y1) (X0,Y0) (0,S) X 2 중의 2

35 샤미르의 비밀 공유 (X0,Y0) : 앨리스 Y (X1,Y1) : 밥 (X2,Y2) : 찰리
세 사람 중 두 사람만 협조하면 비밀 S를 찾을 수 있다. 한 사람이 S를 찾을 수는 없다. “3 중에 2” 체계 Y (X0,Y0) (X1,Y1) (X2,Y2) (0,S) X 3 중에 2

36 샤미르의 비밀 공유 (X0,Y0) : 앨리스 (X1,Y1) : 밥 Y (X2,Y2) : 찰리 3 점이 포물선을 결정
비밀 S를 찾기 위해서는 세명이 모두 협조 “3 중에 3” 체계 “4 중에 3” 체계를 만들 수 있나? Y (X0,Y0) (X1,Y1) (X2,Y2) (0,S) X 3 out of 3

37 정보공유의 예 조건부 키  키가 어떤 곳에 저장된다는 가정 키는 법원의 명령에 의해 사용될 수 있다
키를 저장하는 FBI를 신뢰할 수가 없는 것이 문제 이 경우 비밀 공유 체계를 사용 세 개의 정부 기관이 있다고 하면 키를 사용하기 위해 적어도 두 개 기관이 협조하도록 할 수 있다

38 정보공유의 예제 Point (X0,Y0) : FBI Y Point (X1,Y1) : DoJ Point (X2,Y2) : DoC
대칭키: K Point (X0,Y0) : FBI Point (X1,Y1) : DoJ Point (X2,Y2) : DoC 키 K를 복구하기 위해서는 3개의 기관 중 2개 이상이 협조해야만 한다. 한 개의 기관은 K를 복구할 수 없다. Y (X0,Y0) (X1,Y1) (X2,Y2) (0,K) X

39 5장. 해시함수 및 기타 암호학에서 난수

40 난수 난수는 키를 생산하기 위해 사용되었다 임시로 사용될 때 난수가 사용
대칭키 RSA: 소수들 디피-헬먼: 비밀 값 임시로 사용될 때 난수가 사용 가끔은 순서대로 하는 것이 괜찮을 때가 있음. 또 다른 경우는 임시로 사용되는 수가 난수일 필요가 있음. 난수들은 시뮬레이션, 통계 등의 응용 분야에서도 사용. 그러나 이 때는 “통계적” 난수들이 통상 사용됨.

41 무작위 진정한 난수는 정의하기 어려움. 엔트로피가 무작위 측정으로 사용 “진정한” 무작위 의 좋은 근원
방사능 물질의 붕괴  그러나 핵 컴퓨터는 대중적이지 않음. H/W 장비  시장에서 가용 용암램프  무질서의 행동에서 무작위 추출

42 5장. 해시함수 및 기타 정보 은닉

43 정보 은닉 디지털 워터마킹 스테가노그래피 예제: “투명” 식별자를 자료에 첨가
음악이나 소프트웨어의 불법 배포를 막기 위해 사용 스테가노그래피 비밀 통로 채널 코보트 채널 형태 예제: 자료를 음악이나 이미지에 은닉

44 워터마크 “마크”를 데이터에 첨가 여러 종류의 워터마크 투명  마크가 미디어 내 인지되지 않은 상태 가시  일급비밀 마크
강한  공격 시에도 읽을 수 있는 상태 약한  공격 시에는 손상

45 워터마크 강하고 투명한 마크- 디지털 음악에 첨가 약하고 투명한 마크- 디지털 음성파일에 첨가
만약 해적 음악이 인터넷에서 출현하면, 근원지를 추적할 수 있다 약하고 투명한 마크- 디지털 음성파일에 첨가 만약 워터마크를 읽을 수 없으면, 수신자는 음성파일이 변경되었음을 알 수 있다 (무결성) 여러 형태의 혼합형들이 사용 될 수 있다 즉, 가시적이며 강하고 투명한 워터 마크

46 워터마크 예제 (1) 미 지폐에 포함된 워터마크 우측 부분에 이미지 삽입 지폐를 불빛에 보면 삽입 정보를 볼 수 있음.

47 워터마크 예제 (2) 투명 워터마크를 사진에 첨가 1 인치2 전체 사진을 재생하기에 충분한 정보
1 인치2 전체 사진을 재생하기에 충분한 정보 만약에 사진이 손상되면, 워터마킹을 읽어 전체 사진을 재생할 수 있다고 주장!

48 스테가노그래피 헤로도토스에 의하면 (그리스 440BC) 역사적으로 보면, 스테가노그래피가 암호보다 더 많이 사용 되었음!
노예의 머리를 면도 메시지를 쓴 후에 머리카락이 자란 후에 메시지 전달을 위해 노예를 보냄 메시지를 읽기 위해 노예 머리를 다시 면도(페르시아의 침공 경고 내용) 역사적으로 보면, 스테가노그래피가 암호보다 더 많이 사용 되었음!