메시지 인증(Message authentication)은 보안에 있어서 중요한 이슈이다. 이는 어떤 메시지를 키와 함께 암호화 하여 수신측에서 이를 검사하여 인증하는 식으로 진행되는데, 디지털 서명(Digital sign)의 개념도 이와 비슷하다고 할 수 있다. 이러한 디지털 서명,메시지 인증에서 메시지는 (주로 키와 함께) 해쉬(hash)되어 그 결과값이 전송된다. 따라서 좋은 해쉬 알고리즘의 개발이 중요한 문제가 되었는데, 제안된 여러 알고리즘들 중 유명한 것이 MD5 Hash Algorithm이다.
MD5 알고리즘은 Ron Rivest가 1990년에 개발한 MD4알고리즘을 개선한 것으로써, 빠른 software implementation을 위해 디자인된 hash function을 기반으로 하고 있다. 우선, 해쉬 function들이 message authentication등의 용도에 유용하게 쓰일려면 아래 3가지 사항에 있어서 견고한 방어책이 있어야 한다.
.inversion - 주어진 해쉬 값으로부터 message를 알아 내는 것
.collision - 두 개 이상의 서로 다른 message가 같은 해쉬 값을 갖는 것.
.forgery - secret key에 대한 지식 없이 message authentication code를 산출하는 것.
여기서 해쉬 function들은 임이 길이의 message들을 고정 길이의 해쉬 값으로 변환한다. 해쉬 함수는 일단 계산 속도가 빨라야 한다. 그러면서 위의 3사항에 대하여 견고한 해쉬 함수를 고안하는 것은 아주 어려운 일이라고 할 수 있다.
그러나 이 md5 알고리즘이 중국의 한 여교수가 MD5 알고리즘을 "MD5 is Dead" 라는 이름으로 풀었다. 따라서 디지털 증거에 대한 조작의 가능성이 생겼기 때문에 이제, MD5 해시는 법적인 효력이 발생하지 않게 되었다.
이후 MD5가 깨지고, SHA-1(Secure Hash Algorithm) 이라는 알고리즘이 나오게 되었다.
배경 및 특징
1. 1992년 MIT의 Ronald Riivest가 개발
2. Message는 임의의 길이를 가짐 단 264 biits 이하
3. Message는 512biits 단위 block들로 분할되며, 이것은 각각
4. 16개의 32-biit sub-bllock으로 분할됨
5. Message Padding (Littlle Endian 적용)
– 512bits의 배수 길이가 되도록 0으로 padding
– 마지막 block에서 64bits 구간은 Length Field로 사용
6.Message Digest 결과는 128bits
– 32bits X 4 sub-blocks
md5가 정보검색에 어떻게 쓰이는가?
문서 중복 검사
• 해시 값을 키(Key)로하고 링크를 값(value)으로 하는 튜플을 색인에 저장
– 충돌의 위험이 있기 때문에 대용량 색인에는 문제가 있다.
– 하지만 해시 속도가 빠른편이다.
– 속도를 희생해서 정확도를 증진할것인가? 아니면 정확도를 올리고 속도를 희생할 것인가?
• 따라서 일반적으로 Ediit Diistance의 개념으로 중복 검사를 실시하거나 싱걸링(shiingle)을 이용해서 한다.
참조 : MD5_Hash_Algorithm.pdf , Hash.pdf
