해시 함수
파일의 변경 유무 어제의 파일 오늘의 적극적 공격자 (맬로리) 변경? 이 두 개의 파일은 같은 파일일까? (무결성 점검)
파일 전체를 안전한 장소에 보존하고 나중에 비교 오늘의 파일 어제의 어제 파일의 복사 무결성 확인 비교 안전한 장소에 보존해 둔다 안전한 장소 변경? 적극적 공격자 맬로리
파일을 비교하는 대신 해시값을 비교 변경? 오늘의 파일 어제의 해시값 무결성 확인 비교 안전한 장소에 보존해 둔다 안전한 장소 적극적 공격자 맬로리 일방향 해시함수
일방향 해시 함수(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 하드 디스크의
해시 함수의 성질 임의의 길이 메시지로부터 고정 길이의 해시 값을 계산한다 해시 값을 고속으로 계산할 수 있다 메시지가 다르면 해시 값도 다르다 일방향성을 갖는다
충돌(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비트만 달라져도 전혀 다른 해시 값이 생성된다
충돌 내성(Collision resistance) 암호 기술에서 사용되는 일방향 해시 함수는 충돌 내성을 가질 필요가 있다 메시지 해시값 일방향 해시함수 다른 해시값 다른 메시지 해시값이 충돌하지 않는다
해시 함수의 일방향성 메시지 일방향 해시함수 해시값 메시지로부터 해시 값을 계산할 수 있다 해시 값으로부터 메시지를 계산해낼 수 없다
일방향 해시 함수의 예