제 Ⅱ부 인증

제 7장 일방향 해시 함수 메시지의 「지문」을 채취한다

7.0 주요 내용 범죄 수사에서는 지문을 이용하는 일이 있다. 특정인의 지문과 현장에 남겨진 지문을 비교해서 그 사람이 사건에 관련되어 있는지 조사한다. 컴퓨터로 처리하는 메시지에 대해서도 「지문」이 있었으면 할 때가 있다. 2개의 메시지가 동일한지 아닌지를 조사할 때 메시지를 직접 비교하는 것이 아니라, 메시지의 지문을 비교하여 판정한다.

7.1 일방향 해시 함수 먼저 앨리스가 등장하는 스토리를 통해서 일방향 해시 함수가 필요해지는 장면을 소개하겠다. 그런 다음 일방향 해시 함수가 갖추어야 할 성질을 설명하겠다.

7.1.1 파일의 진위 어제의 파일 오늘의 적극적 공격자 (맬로리) 변경? 이 두 개의 파일은 같은 파일일까? (무결성 점검)

파일 전체를 안전한 장소에 보존해 두고, 나중에 비교하는 방법 오늘의 파일 어제의 어제 파일의 복사 무결성 확인 비교 안전한 장소에 보존해 둔다 안전한 장소 변경? 적극적 공격자 맬로리

파일을 비교하는 대신에 해시 값을 비교하는 방법 오늘의 파일 어제의 해시값 무결성 확인 비교 안전한 장소에 보존해 둔다 안전한 장소 변경? 적극적 공격자 맬로리 일방향 해시함수

7.1.2 일방향 해시 함수란 일방향 함수의 예를 한 가지 만들어보기로 하자. 입력되는 숫자를 23으로 나누는 메커니즘을 생각해보자. 그리고 그 몫을 소수로 표시했을 때 소숫점 이하 7자리부터 10자리까지 4자리 숫자를 생각해보자.

일방향 해시 함수의 예 345689 를 23으로 나누어보자. 그러면 몫은 15029.95652173913043…… 이 된다. 그래서 소숫점 이하 7자리부터 10자리의 수는 7391이 되고 이 4자리 수가 입력 345689에 대한 출력이 된다. 예로 들은 이 함수는 일방향 함수가 분명하다. 다시 말해서 7391로부터 345689를 계산하고, 6521로부터 87967654를 역으로 계산해낼 함수를 찾을 수 없기 때문이다.

일방향 해시 함수 일방향 해시 함수(one-way hash function)에는 입력과 출력이 각각 1개씩 있다. 입력은 메시지(message)라고 하고, 출력은 해시 값(hash value)이라 한다.

일방향 해시 함수는 메시지를 기초로 해서 해시 값을 계산한다 일방향 해시함수 해시값 345689 23으로 나누고 몫의 소수점 이하 7자리부터 10자리까지 택하기 7391

해시함수의 입력 해시함수에 입력되는 메시지는 인간이 읽을 수 있는 문서일 필요는 없다. 화상 파일이라도, 음성 파일이라도 상관없다. 일방향 해시 함수는 메시지가 실제로 무엇을 나타내고 있는지를 알 필요는 없다. 일방향 해시 함수는 어떤 메시지든지 단지 비트 열로서 취급하며, 그 비트 열을 기초로 해시 값을 계산한다.

해시함수의 출력 해시 값의 길이는 메시지의 길이와는 관계가 없다. 메시지가 1비트라도, 1메가바이트라도, 100기가바이트라도 일방향 해시 함수는 고정된 길이의 해시 값을 출력으로 배출한다. 예를 들면 SHA-1이라는 일방향 해시 함수에서는 해시 값은 항상 160비트(20바이트)이다

해시 값은 항상 고정 길이 일방향 해시함수 (SHA-1) 해시값 20바이트 8바이트 8바이트  일방향 해시함수 (SHA-1) 해시값 20바이트 43 B0 4C 54 3B 67 A2 23 3F 7D 36 2B 7A 2B 49 3C D3 AF 27 4A 사용자 패스워드 512 킬로바이트  73 BF 4C 34 3B 67 A2 45 23 76 3F 76 D2 37 F6 44 47 8F 93 D2 스캐너로부터의 영상 데이터 1.4메가바이트  54 3B 4C 34 3B 62 3C D3 AF A2 45 67 A2 23 3F 7D 43 B0 4C 19 플로피 디스크의 모든 파일 80기가바이트 32 2B 23 70 7A 2B 4F 43 B0 4C 54 3B 49 28 67 A2 23 8F 7D 36 하드 디스크의

7.1.3 일방향 해시 함수의 성질 임의의 길이 메시지로부터 고정 길이의 해시 값을 계산한다 해시 값을 고속으로 계산할 수 있다 메시지가 다르면 해시 값도 다르다 일방향성을 갖는다

충돌(collision) 2개의 다른 메시지가 같은 해시 값을 갖는 것을 충돌(collision)이라고 한다. 일방향 해시 함수를 무결성 확인에 사용하기 위해서는 충돌이 발견되어서는 안 된다.

메시지가 1비트만 달라도 다른 해시 값이 된다 메시지의 00을 01로 바꿨다(1비트의 변경) 00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F 10 11 12 13 14 15 16 17 18 19 1A 1B 1C 1D 1E 1F 20 21 22 23 24 25 26 27 28 29 2A 2B 2C 2D 2E 2F 30 31 32 33 34 35 36 37 38 39 3A 3B 3C 3D 3E 3F 40 41 42 43 44 45 46 47 48 49 4A 4B 4C 4D 4E 4F 50 51 52 53 54 55 56 57 58 59 5A 5B 5C 5D 5E 5F 60 61 62 63 64 65 66 67 68 69 6A 6B 6C 6D 6E 6F 70 71 72 73 74 75 76 77 78 79 7A 7B 7C 7D 7E 7F 80 81 82 83 84 85 86 87 88 89 8A 8B 8C 8D 8E 8F 90 91 92 93 94 95 96 97 98 99 9A 9B 9C 9D 9E 9F A0 A1 A2 A3 A4 A5 A6 A7 A8 A9 AA AB AC AD AE AF B0 B1 B2 B3 B4 B5 B6 B7 B8 B9 BA BB BC BD BE BF C0 C1 C2 C3 C4 C5 C6 C7 C8 C9 CA CB CC CD CE CF D0 D1 D2 D3 D4 D5 D6 D7 D8 D9 DA DB DC DD DE DF E0 E1 E2 E3 E4 E5 E6 E7 E8 E9 EA EB EC ED EE EF F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 FA FB FC FD FE FF 01 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F 10 11 12 13 14 15 16 17 18 19 1A 1B 1C 1D 1E 1F 20 21 22 23 24 25 26 27 28 29 2A 2B 2C 2D 2E 2F 30 31 32 33 34 35 36 37 38 39 3A 3B 3C 3D 3E 3F 40 41 42 43 44 45 46 47 48 49 4A 4B 4C 4D 4E 4F 50 51 52 53 54 55 56 57 58 59 5A 5B 5C 5D 5E 5F 60 61 62 63 64 65 66 67 68 69 6A 6B 6C 6D 6E 6F 70 71 72 73 74 75 76 77 78 79 7A 7B 7C 7D 7E 7F 80 81 82 83 84 85 86 87 88 89 8A 8B 8C 8D 8E 8F 90 91 92 93 94 95 96 97 98 99 9A 9B 9C 9D 9E 9F A0 A1 A2 A3 A4 A5 A6 A7 A8 A9 AA AB AC AD AE AF B0 B1 B2 B3 B4 B5 B6 B7 B8 B9 BA BB BC BD BE BF C0 C1 C2 C3 C4 C5 C6 C7 C8 C9 CA CB CC CD CE CF D0 D1 D2 D3 D4 D5 D6 D7 D8 D9 DA DB DC DD DE DF E0 E1 E2 E3 E4 E5 E6 E7 E8 E9 EA EB EC ED EE EF F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 FA FB FC FD FE FF 일방향 해시함수 (SHA-1) 일방향 해시함수 (SHA-1) 49 16 D6 BD B7 F7 8E 68 03 69 8C AB 32 D1 58 6E A4 57 DF C8 52 FB EC 10 72 00 59 86 D1 A7 EF B6 5B 04 71 41 A1 14 7A FF 메시지가 1비트만 달라져도  전혀 다른 해시 값이 생성된다

앞에서 예로 들었던 일방향 함수 위의 예제에서 우리가 입력으로 사용한 값은 A = 345689 이었고 출력으로 얻은 출력 값은 7391이었다. 이제 동일한 일방향 함수에 새로운 입력으로 B = 232.8395049993 을 넣어보자. 그러면 몫은 10.1234567391 가 된다. 따라서 출력되는 값은 7391이 된다. 이것을 보면 두 개의 서로 다른 입력 A와 B에 대해서 동일한 출력 값을 배출한다는 것을 알 수 있다.

충돌 내성(collision resistance) 암호 기술에서 사용되는 일방향 해시 함수는 충돌 내성을 가질 필요가 있다

일방향 해시 함수의 충돌 내성 메시지 해시값 일방향 해시함수 다른 해시값 다른 메시지 해시값이 충돌하지 않는다

일방향 해시 함수의 일방향성 메시지 일방향 해시함수 해시값 메시지로부터 해시 값을 계산할 수 있다 해시 값으로부터 메시지를 계산해낼 수 없다

7.1.4 해시 함수관련 용어 일방향 해시 함수는 등으로 불린다. 일방향 해시 함수의 입력이 되는 메시지는 메시지 다이제스트 함수(message digest function), 메시지 요약 함수, 혹은 암호적 해시 함수 등으로 불린다. 일방향 해시 함수의 입력이 되는 메시지는 프리・이미지(pre-image)라고 불리는 일도 있다.

7.1.4 해시 함수관련 용어 일방향 해시 함수의 출력이 되는 해시 값은 라고도 불린다. 무결성은 메시지 다이제스트(message digest)나 핑거프린트(fingerprint) 라고도 불린다. 무결성은 완전성이나 보전성 이라고도 불리는 경우도 있다.

7.2 일방향 해시 함수의 응용 예

7.2.1 소프트웨어의 변경 검출 어떤 사람이 특정 웹 사이트에서 소프트웨어를 다운로드 받는다고 했을 때 자신이 다운받아 입수한 소프트웨어가 원래 웹 사이트 주인이 올려놓은 소프트웨어와 동일한 것인지 아니면 어떤 공격자나 악의를 가진 사람에 의해서 수정된 내용의 소프트웨어인지 확인하기 위해 일방향 해시 함수가 사용된다

소프트웨어 변경 검출을 위해 일방향 해시 함수를 사용한다 해시값 소프트웨어의 무결성 확인 일방향 해시함수 비교 통신 부하의 분산을 위해 밀러 사이트로부터 소프트웨어를 입수한다 무결성의 확인을 위해 오리지널 사이트로부터 해시 값을 입수한다 미러 사이트 사용자 오리지널 사이트 소프트웨어 변경 검출을 위해 일방향 해시 함수를 사용한다

7.2.2 패스워드를 기초로 한 암호화 일방향 해시 함수는 패스워드를 기초로 한 암호화(password based encryption; PBE)에서 사용되는 일이 있다.  PBE에서는 패스워드와 솔트(의사난수 생성기로 생성한 랜덤 값,salt)를 섞은 결과의 해시 값을 구해 그것을 암호화 키로 사용한다. 이 방법으로 패스워드에 대한 사전 공격을 막을 수 있다.

7.2.3 메시지 인증 코드 일방향 해시 함수를 사용해서 메시지 인증 코드를 구성할 수 있다. 메시지 인증 코드란 「송신자와 수신자만이 공유하고 있는 키」와 「메시지」를 혼합해서 그 해시 값을 계산한 값이다. 메시지 인증 코드를 사용하여 통신 중의 오류나 수정 그리고 「거짓 행세」를 검출하는 것이 가능해 진다.

7.2.4 디지털 서명 디지털 서명에 일방향 해시 함수가 사용된다. 디지털 서명의 처리에는 시간이 많이 걸리기 때문에 디지털 서명을 메시지 전체에 직접 행하는 일은 별로 없다. 일방향 해시 함수를 사용해서 메시지의 해시 값을 일단 구하고, 그 해시 값에 대해 디지털 서명을 행한다.

7.2.5 의사난수 생성기 일방향 해시 함수를 사용해서 의사난수 생성기를 구성할 수 있다. 암호 기술에 이용하는 난수에서는 「과거의 난수 예로부터 미래의 난수 예를 예측하는 것은 사실상 불가능」이라는 성질이 필요해진다. 그 예측 불가능성을 보증하기 위해 일방향 해시 함수의 일방향성을 이용한다.

7.2.6 원타임 패스워드 일방향 해시 함수를 사용해서 원타임 패스워드(one-time password)를 구성할 수 있다. 원타임 패스워드는 정당한 클라이언트인지 아닌지를 서버가 인증할 때에 사용된다. 이 방식에서는, 일방향 해시 함수를 써서 통신 경로 상에 흐르는 패스워드가 1회 한정(one-time)이 되도록 고안되어 있다. 이 때문에 패스워드가 도청되어도 악용될 위험성이 없다.

7.3 일방향 해시 함수의 예

7.3.1 MD4와 MD5 MD는 메시지 다이제스트(Message Digest)의 약자이다. MD4 Rivest가 1990년에 만든 일방향 해시 함수로 128비트의 해시 값을 갖는다 그러나 Dobbertin에 의해 MD4의 해시 값의 충돌을 발견하는 방법이 고안되어 현재는 안전하다고 할 수 없다.

7.3.1 MD4와 MD5 MD5 MD4를 만든 Rivest가 1991년에 만든 일방향 해시 함수로 128비트의 해시 값을 갖는다 여기서 입력은 512-비트 블록들로 처리된다. 전수공격과 암호해독에 대한 우려가 심각해진 최근 몇 년을 제외하면 MD5 는 가장 널리 사용되던 안전한 해시 함수이었다.

7.3.2 SHA-1, SHA-256, SHA-384, SHA-512 SHA(Secure Hash Algorithm)은 NIST(National Institute of Standards and Technology)에서 만들어진, 160비트의 해시 값을 갖는 일방향 해시 함수이다. 1993년에 미국의 연방정보처리표준규격(FIPS PUB 180)으로서 발표된 것을 SHA라 부른다 1995년에 발표된 개정판 FIPS PUB 180-1을 SHA-1이라 부른다. SHA-1의 메시지의 길이에는 상한이 있지만, 264비트 미만이라는 대단히 큰 값이므로 사실상 현실적인 적용에는 문제가 없다.

SHA-256, SHA-384, SHA-512 2005년에 NIST에서는 SHA-1에 대한 승인을 취소한다고 선언했고 2010년까지 새로운 SHA 버전들로 대체한다고 했다. 하지만 이미 NIST에서는 2002년에 NIST는 새 표준인 FIPS 180-2 를 내놓았는데 이때 해시 값이 각각 256, 384와 512 비트인 3 개의 새로운 SHA 버전들을 정의했다. 이들은 각각 SHA-256, SHA-384와 SHA-512이다.

SHA 매개변수 비교 (단위: 비트)

7.3.3 RIPEMD-160 RIPEMD-160은 1996년에 Hans Dobbertin, Antoon Bosselaers, Bart Preneel에 의해 만들어진, 160비트의 해시 값을 갖는 일방향 해시 함수이다. RIPEMD-160은 European Union RIPE 프로젝트로 만들어진 RIPEMD라는 일방향 해시 함수의 개정판이 된다.

7.4 일방향 해시 함수 SHA-1 대표적인 일방향 해시 함수인 SHA-1에 대해서 자세하게 설명한다. 긴 메시지를 어떤 식으로 「해시」하고 있는가를 확인해 보자.

7.4.1 전체의 흐름 SHA-1은 264비트 미만의 메시지를 기초로 해서 160비트의 해시 값을 계산하는 일방향 해시 함수이다.

160비트의 값을 계산하는 순서 패딩 W0~W79 계산 블록 처리 단계 1 처리

일방향 해시 함수 SHA-1의 개요 일방향 해시함수 SHA-1 메시지 패딩 입력블록 512비트 W0~W79 32비트×80개 초기 상태 160비트 (A,B,C,D,E 32비트×5개 블록의 처리 80단계 내부 상태 해시값 최종 상태 일방향 해시함수 SHA-1

SHA-1 : 패딩 0비트 이상 264비트 미만의 길이를 갖는다. SHA-1에서는 이후의 처리를 하기 쉽게 하기 위해 맨 처음에 패딩(padding)을 행한다. 패딩이라는 것은 「메워 넣기」라는 의미이다. 여기서는 메시지 다음에 여분의 데이터를 부가하여 메시지의 길이가 512비트의 정수배가 되도록 하는 것을 가리킨다. 이 512비트의 집합을 입력 블록이라 부른다.

SHA-1 : W0~W79의 계산 패딩이 끝난 다음에는 입력 블록 단위의 처리가 된다. 입력 블록 512비트마다 32비트× 80개의 값(W0~W79)을 계산한다. 이 80개의 값은 「(4) SHA-1 : 단계 1 처리」에서 사용한다. 우선 입력 블록 512비트를 32비트× 16개로 분할하여 W0~W15처럼 이름을 붙여 간다. 그리고 W16부터 W79는 아래와 같이 계산한다.

W16계산과 일반 Wt 의 계산 W16 = (W0⊕W2⊕W8⊕W13)을 1비트 회전 Wt = (Wt-16⊕Wt-14⊕Wt-8⊕Wt-3)을 1비트 회전

01001000 01100101 01101100 01101100를 1비트 회전한 모양 1

SHA-1 :블록의 처리 입력 블록에 대해 80 단계씩의 처리를 행한다(그림 7-13 참조). 입력 블록의 정보를 기초로 내부 상태(160비트)를 변화시킨다. 이것을 모든 블록에 대해 행한다. 내부 상태 160비트는 A, B, C, D, E라는 이름이 붙은 32비트× 5개의 버퍼로 표현되어 있다.

입력 블록 512비트로 부터 80개의 32비트로 부터(W0~W79)을 생성 입력블록 512비트 W0 W1 W2 W3 W4 W5 W6 W7 W8 W9 W10 W11 W12 W13 W14 W15 32비트 16개로 분해 XOR 1bit 회전 W16 W17 W18 W19 W20 W63 W65 W71 W76 W79 Wt-16 Wt-14 Wt-8 Wt-3 Wt 입력 블록 512비트로 부터 80개의 32비트로 부터(W0~W79)을 생성

입력 블록 512비트를 160비트의 내부 상태에 섞어 넣는다(80 단계) A버퍼 32비트 B버퍼 C버퍼 D버퍼 E버퍼 단계 0 단계 1 단계 2 단계 3 단계 77 단계 78 단계 79 덧셈 1블록 처리 전의 내부 상태 160비트 1블록 처리 후의 내부 상태 160비트 입력 블록 512비트를 160비트의 내부 상태에 섞어 넣는다(80 단계)

SHA-1 : 1 단계 처리 「(3) SHA-1 : 블록 처리」에 등장한 1 단계의 내용은 그림 7-14에 나타난 처리가 된다. W0~W79를 기초로, 내부 상태(즉 A, B, C, D, E의 값)를 변화시켜 가는 복잡한 처리이다. A~E의 버퍼의 초기값은 그림 7-14 에 나타나 있다.

1 단계 처리 1단계 처리 전의 내부 상태 160비트 덧셈 1단계 처리 후의 내부 상태 160비트 A버퍼 32비트 B버퍼 C버퍼 D버퍼 E버퍼 덧셈 1단계 처리 전의 내부 상태 160비트 1단계 처리 후의 내부 상태 160비트 A버퍼의 초기값 67 45 23 01 B버퍼의 초기값 EF CD AB 89 C버퍼의 초기값 98 BA DC FE D버퍼의 초기값 10 32 54 76 E버퍼의 초기값 C3 D2 E1 F0 단계 의존의 논리함수 ft 5비트 회전 입력 블록과 단계에 의존하는 수 Wt 단계에 의존하는 정수 Kt f0~f19=(B and C) or (not B and D) f20~f39=B xor C xor D f40~f59=(B and C) or (C and D) or (D and B) f60~f79=B xor C xor D K0~K19= 5A 82 79 99 K20~K39= 6E D9 EB A1 K40~K59= 8F 1B BC DC K60~K79= CA 62 C1 D6 1 단계 처리

7.5 일방향 해시 함수 SHA-512 SHA의 다른 버전들도 구조는 거의 비슷하다 입력 데이터는 길이가 1024 비트인 블록으로 나누어서 처리된다.

SHA-512를 사용하는 메시지 다이제스트 생성

1024비트 한 개에 대한 SHA-512 처리 

7.6 일방향 해시 함수에 대한 공격 암호에 대한 공격에 비해 일방향 해시 함수에 대한 공격은 상상하기 어렵다. 구체적인 2개의 스토리를 통해서 일방향 해시 함수에 대한 공격을 생각해 보자.

7.6.1 전사공격(공격 스토리1) 앨리스는 컴퓨터로 계약서 파일을 만들고 있다. 일이 끝나서 계약서 파일을 회사의 컴퓨터 상에 두고, 계약서 파일의 해시 값만을 이동저장장치인 USB에 보존해서 집으로 가지고 돌아왔다. 밤에 적극적 공격자 맬로리가 컴퓨터에 침입해 왔다. 맬로리는 앨리스의 계약서 파일을 발견하고, 그 안의 「앨리스의 지불 금액은 백만 원으로 한다.」 부분을, 「앨리스의 지불 금액은 일억 원으로 한다.」 로 변경하고자 한다

어떻게 하면 해시 값을 바꾸지 않고, 「백만 원」→「일억 원」의 변경을 행할 수 있을까? 단지 변경만 해서는 안 된다는 것을 알고 있다. 다음 날 앨리스가 와서 해시 값을 재계산 한 다음에 자신의 플로피 디스크에 저장해놓았던 해시값과 비교를 할 것을 맬로리는 알고 있기 때문이다. 파일을 1비트라도 변경하면 앨리스가 알게 된다.

문서의 의미를 생각한다 맬로리는 문서 파일의 의미를 생각한다. 그리고 「문서의 의미를 바꾸지 않고 얼마만큼 파일을 수정할 수 있을까」를 생각해보았다. 예를 들어보면 아래의 문장은 거의 같은 의미를 나타내고 있다.

동일한 의미의 문장 앨리스의 지불 금액은 일억 원(一億원)으로 한다. 앨리스의 지불 금액은 일억 원(壹億원)으로 한다. 앨리스의 지불 금액은 100000000원으로 한다. 앨리스의 지불 금액은 \100000000으로 한다. 앨리스의 지불 금액은, 일억 원(一億원)으로 한다. 앨리스가 지불하는 금액은 일억 원으로 한다. 앨리스는 일억 원을 지불하는 것으로 한다. 대금으로서, 앨리스는 일억 원을 지불한다.

문장의 중복성 맬로리는 문서의 내용은 동일하면서 표현만 다른 문서들을 이용하여 「일억 원 지불의 계약서」를 기계적으로 대량 작성한다. 앨리스가 만든 오리지널의 「백만 원 계약서」와 같은 해시 값을 생성하는 것이 발견되면, 맬로리는 대단히 기쁠 것이다. 일억 원 계약서와 백만 원 계약서를 교환할 수 있기 때문이다. 파일을 교환하고 맬로리는 떠난다. 이것으로 파일의 내용이 수정되어 버렸다.

다음 날 앨리스는 계약서의 해시 값을 계산해서, 자신이 집으로 가지고 돌아간 어젯밤의 해시 값과 비교한다. 일치하므로 안심하고 계약서에 사인한다. 하지만, 맬로리의 개정에 의해 계약의 내용은 백만 원에서 일억 원으로 바뀌어 있다.

「약충돌내성」을 깨는 공격 이것은 일방향 해시 함수의 「약충돌내성」을 깨고자 하는 공격이다. SHA-1의 경우, 해시 값이 160비트이므로, 2160회의 시행 횟수를 행하면 목적하는 메시지가 발견될 것이라고 기대할 수 있다. 현재는 이 2160회의 시행 횟수인 1461501637330902918203684832716283019655932542976 회 는 현실적이지 않다고 간주되고 있기 때문에 안전하다.

7.6.2 생일 공격(공격 스토리2) 맬로리는 해시 값이 같은 값을 갖는 「백만 원 계약서」와 「일억 원 계약서」를 미리 만들어 둔다. 그리고 맬로리는 시치미를 떼고 「백만 원 계약서」를 앨리스에게 건네주고, 해시 값을 계산시킨다. 그 다음에 맬로리는 스토리1과 마찬가지로 「백만 원 계약서」와 「일억 원 계약서」를 살짝 바꾼다.

「강충돌 내성」을 깨는 공격 여기에서 맬로리가 행한 공격은 특정의 해시 값을 생성하는 메시지를 구하는 것이 아니라, 해시 값은 뭐든지 괜찮고, 어쨌든 같은 해시 값을 생성하는 2개의 메시지를 구하는 것이었다. 이와 같은 공격을 일반적으로 생일 공격(birthday attack)이라 부른다. 이것은 일방향 해시 함수의 「강충돌 내성」을 깨고자 하는 공격이다.

생일 퀴즈 랜덤으로 선택한 N명의 그룹을 생각한다. N명 중 적어도 2명의 생일이 일치할 확률이 「2분의 1」이상이 되도록 하기 위해서는 N은 최저 몇 명이 될까? (2월29일은 제외하고 생각한다.)

답 N=23일 때 이 값은 약 0.507297이므로 ½보다 큰 값을 가진자

생일 퀴즈를 일반화해보자 「1년의 일수가 Y일 있다고 하고, N명으로 구성된 그룹 안에서 적어도 2명의 생일이 일치할 확률이 2분의 1 이상이 되기 위한 최저의 N은 얼마인가?」

답 근사적인 계산을 행하면 Y가 매우 클 때에는, 일년의 일수에 대한 제곱근인 ………. (*)

스토리2에서 맬로리가 행한 생일 공격 (1) 맬로리는 백만 원 계약서를 N개 작성한다(N은 후술). (4) 일치하는 것이 발견되면 그 백만 원 계약서와 일억 원 계약서를 가지고 앨리스를 속이러 간다.

N의 길이 여기서 문제가 되는 것은 N의 크기이다.

생일공격 성공조건 앨리스가 사용하는 일방향 해시 함수가 M비트 길이의 해시 값을 갖는다고 하자. M비트 길이의 해시 값이 취할 수 있는 모든 수는 2M개 이다 앞의 식 (*)에 의하면, 이므로, N = 2M/2이라면 맬로리는 1/2의 확률로 생일 공격에 성공하게 된다.

생일공격 성공조건 해시 값이 160비트라고 하자. 그 경우, 일방향 해시 함수에 대한 전사공격의 시행 횟수는 2160회였다. 그러나 같은 일방향 해시 함수에 대한 생일 공격의 시행 횟수는 280회이다. 전사공격에 비해 생일 공격의 시행 횟수는 대단히 적어진다는 것에 주의하라. 현재 280=1208925819614629174706176회는 현실적이지 않다고 간주되고 있으므로 생일공격이라는 측면에서만 보면 SHA-1은 안전해 보인다.

안전하지 않은 SHA-1 2005년 2월에 한 연구팀이 SHA-1에 대한 한 가지 공격에 대해서 설명했는데, 269 번의 연산을 사용해서 동일한 SHA-1 해시 값을 출력하는 두 개의 서로 다른 메시지를 찾을 수 있다는 것을 보였다. 여기서 이 연산의 숫자는 SHA-1에서 생일공격을 하기 위해 280 번의 연산이 필요하다고 생각했던 것 보다 훨씬 적은 숫자이다. 이미 이러한 위협 때문에 NIST에서는 2005년에 SHA-1에 대한 승인을 취소하였고 2010년까지 SHA-256, SHA-384와 SHA-512같은 새로운 SHA로 대체한다고 하였다

7.7 일방향 해시 함수로 해결할 수 없는 문제 일방향 해시 함수는 「수정 또는 변경」을 검출할 수 있지만, 「거짓 행세」를 검출하는 것은 못 한다. 이를 위해서는 무결성 외에 인증이라는 절차가 필요해진다. 인증을 수행하기 위한 기술이 메시지 인증 코드와 디지털 서명이다.