뭬야? md5 가 깨졌다고?

Slashdot 을 읽고있는데 Practical Exploits of Broken MD5 Algorithm 이란 글이 눈에 들어오는것 아닌가?

아날로그식 md5 알고리즘 전개 ^^

예로 부터 파일무결성 보증을 위한 대표수단으로 사용된 md5(message digest 5)!
대표적인 source tarball 배포시 integrity 를 위해서는 md5 checksum 을 사용하는게 불문율 아니었나...

그렇다. md5 란 hash 계의 대명사로 1991년 탄생과 더불어 지금까지 각종 영역에서 두루 영향을 미쳐온 cryptographic hash 알고리즘인 것이다.
hash 함수인 관계로 당연히 근본적으로 역함수가 존재하지 않는 함수이다.

하지만, 128bit 로 정해진 해쉬 값이기 때문에 경우의 수는 겨우
2^128 = 340,282,366,920,938,463,463,374,607,431,768,211,456 개
밖에 되지않는다. 겨우 말이다... ^^;

1991년 Ronald Rivest(RSA 설립자)에 의해 만들어진 md5 는 Ronald Rivest 의 message digest 해쉬 알고리즘 중 다섯번째로 만들어진것이기에 md5 란 이름을 갖게 되었다.

1993년 이래로 꾸준히 collision(동일한 해쉬값을 갖는 서로 다른 입력값)이 존재한다고 위험성이 계속 경고되어왔다고 한다.

과연 그랬나? -.- 왜 나만 모르고 있었던건가?

그러다가 2004년 8월에 드디어 수학적 이론으로 무장된 md5 collisions analytical attack 방법이 발표된 모양이다.(읽어보는건 도저히 무리... 도대체 뭔 소리를 적어놓은거야! 버럭!!! -.- )

참고1, 참고2

Slashdot 의 글은 Exploiting MD5 collisions (in C#) 이란 이름 하에 이걸 보여주고 있는 거였다.

그럼, md5 기반 하에 있는 모든 코드들이나 디지털 서명들은 무용지물이란 이야기인가?
게다가, Wang 등의 짱께 선생님들에 따르면 SHA 까지도 모조리 collision 이 생각보다 적은 시간 아래 찾아질 수 있다는데...

이런 해쉬함수들은 모조리 폐기처분 해야된다는 말일까?

이에 대한 모범답안은 아니오이다. 즉, 여전히 유효하게 사용하는게 바람직하다.

broken MD5 의 예제들은 하나같이 collision 을 보여줌으로써 unique 한 입력값들의 해쉬값이 항상 unique 하게 다르지않다를 보여주고 있다. 즉, 반례를 든 셈이다.
하지만, 해쉬함수의 정의가 해쉬값 자체가 unique 함을 뜻하지는 않는기 때문에 참인 명제에 대한 반례를 듦으로써 명제 자체가 틀렸다를 뜻하지 못한다. 헉헉...
md5 의 경우, 앞에서도 말했듯이 2^128 개의 경우의 수이므로 표본집단의 개수가 2^128 을 넘기면 당연히 중복될 가능성이 있는것이다.

attacker 들은 존재하지 않는 역함수를 만들어낸 것이 아니라(당연히 역함수는 없으므로), collision 셋트를 찾아낸 것이다.
이를 가리켜 collision attack 이라고 한다. 즉, collision 이 쉽게 만들어지면 만들어질 수록 그만큼 해당 hash 알고리즘이 취약하다고 볼 수 있다.

정작 문제가 되는 것은 주어진 해쉬값에 대해서 입력값을 바로 찾아버리는 preimage attack 이다.
즉, 역함수가 존재하지 않더라도 brute force 로라도 입력값을 찾아내버린다면 hash 알고리즘의 의미가 없어져버리기 때문이다.

하지만, 현재까지 md5 나 SHA 에 있어서 preimage attack 이 행해졌다는 얘기는 없다.

참고

다만, collision attack 이 본격적으로 구현되어지고 있는 등 md5 의 취약함에 대한 우려때문에 Microsoft 사에서는 md5 함수를 내부적으로 더이상 사용하지 않도록 방침이 정해지는 등, proactive 한 움직임이 나타나고 있다고 볼 수 있는 것이다.

결론을 이야기해보자.
입력값을 제공하는 사람은 손쉽게 hash 값이 같은 collision 을 만들어낼 수 있다. 즉, 원본 제공자는 원본의 내용을 바꿔가며 md5 값이 같은 collision set 를 만드는게 가능하다는 얘기다.
중요한건 collision set 가 찾아지도록 공격자가 원본까지도 함께 바꿔가야한다.
(원본을 바꾸지않고, md5 값이 같은 가짜 사본을 만드는게 바로 preimage attack 이니까.)

md5 에만 의존한 파일무결성 보증은 이제 완벽한 것이라 볼 수 없다. 왜냐하면, 원본 및 md5 값을 제공하는 제공자 측에서 이미 collision set 를 만들어놓고 원본을 제공하는 malicious incident 가 충분히 생길 수 있기 때문이다.