MD5 해시 충돌

feanor의 이미지

MD5 해시 충돌이 발견되었습니다.

http://sparcs.kaist.ac.kr/~tinuviel/md5col/ 에서 두 파일을 다운받아서 md5sum을 계산해 보세요. 파일은 다른데 md5sum은 같습니다.

더 자세한 사정은 http://www.rtfm.com/movabletype/ 를 읽어보세요. 뭔가 대단한 일이 벌어지긴 한 것 같습니다.

--feanor

Mins의 이미지

얼마전까지 시험을 위해 지긋지긋한 암호관련 내용들을 쳐다봤는데..
이런 글을 보니 참 기분이 야릇하네요.

임의로 충돌되는 해쉬값을 만들수? (찾을수?) 있다는건가요?

저게 실제로도 원하는 결과를 조작하고서 정상적인 hash 값을 만들수 있는 단계 까지는 아니겠죠?

그렇다면 md5 자체가......

sh.의 이미지

암호화에 대해서 잘 아는것이 아니라서 궁금합니다만..

흔히 볼 수 있는 암호화에 대한 자료들에서도

MD5는 충돌이 발견된 적이 있으며

MD5보다는 SHA1을 사용하도록 권장하고 있던데요,

충돌이 이번에 처음 밝혀진것이었나요?

feanor의 이미지

네, MD5 충돌은 처음입니다. 말씀하신 것은 MD4 같군요.

--feanor

feanor의 이미지

하나 더. 이번 MD5 충돌을 발표한 논문에 따르면, MD5 충돌을 만드는 데 IBM P690 기계에서 1시간밖에 걸리지 않았다고 합니다.

http://eprint.iacr.org/2004/199/

--feanor

신승한의 이미지

어제 /. 에 갔더니 한바탕 난리들을 벌이고 있더군요..
잼나는 사건이 하나 더!.. :lol:

happibum의 이미지

Mins wrote:

임의로 충돌되는 해쉬값을 만들수? (찾을수?) 있다는건가요?

저게 실제로도 원하는 결과를 조작하고서 정상적인 hash 값을 만들수 있는 단계 까지는 아니겠죠?

http://zdnet.com.com/2100-1105_2-5313655.html 에서 발췌하였습니다.

Quote:
MD5's flaws that have been identified in the past few days mean that an attacker can generate one hash collision in a few hours on a standard PC. To write a specific backdoor and cloak it with the same hash collision may be much more time-intensive.
랜덤여신의 이미지

대용량 파일도 아니고... 겨우 128byte 의 작은 파일 2개가 충돌하다니... 조금 의외인걸요 ;)
이론상으로는 충분히 있을 수 있는 일이였겠지요?

dhunter의 이미지

실제 가능성이 있을정도로 높은 유사성을 보이는 파일이라 몹시 곤란하군요. 이래서야 파일전송 무결성 체크섬으로는 좀 어렵지 않나 싶을지도... :(

from bzImage
It's blue paper

hyunuck의 이미지

인클루드 wrote:
대용량 파일도 아니고... 겨우 128byte 의 작은 파일 2개가 충돌하다니... 조금 의외인걸요 ;)
이론상으로는 충분히 있을 수 있는 일이였겠지요?

이론상으로 절대로 불가능한 일이 일어난거에요.....
angpoo의 이미지

hyunuck wrote:
인클루드 wrote:
대용량 파일도 아니고... 겨우 128byte 의 작은 파일 2개가 충돌하다니... 조금 의외인걸요 ;)
이론상으로는 충분히 있을 수 있는 일이였겠지요?

이론상으로 절대로 불가능한 일이 일어난거에요.....

MD5는 겨우 128비트 즉 16바이트입니다.
같은크기의128바이트의 파일이면서 같은 MD5해시값이 존재하는 다른 파일이 존재한다는게 이상할건 없습니다..
단지 이런걸 아주 쉽게 찾거나 만들 수 있다면 문제가 될 수 있죠.

이론상 불가능하다고 증명된일은 일어나지 않습니다.
확률적으로 불가능하다고 볼만한 일들은 종종일어나죠.

ixevexi의 이미지

당나귀를 애용하는 저로서는 :(

궁금한데 당나귀의 해쉬는 MD5가 맞나요?
만약 맞다면 P2P의 해쉬값을 검색한 후 엉뚱한 파일을 넣는 방법으로
저작권법을 보호할 수도 있겠는데요...

마치 소리바다의 가짜 MP3처럼요..

C++, 그리고 C++....
죽어도 C++

최종호의 이미지

hyunuck wrote:
인클루드 wrote:
대용량 파일도 아니고... 겨우 128byte 의 작은 파일 2개가 충돌하다니... 조금 의외인걸요 ;)
이론상으로는 충분히 있을 수 있는 일이였겠지요?

이론상으로 절대로 불가능한 일이 일어난거에요.....

해쉬값이 충돌하는게 왜 불가능한 일인가요?
비둘기집 정리 (pigeon hole principle) 에 따르면 당연히 충돌이 가능한것일텐데요.

http://zimmer.csufresno.edu/~larryc/proofs/proofs.pigeonhole.html

단지, MD5가 생성해 내는 해쉬값이 충분히 uniform하고 충돌의 가능성이 적다는 것이 꼭 그렇지 않다는 것 아닌가요?

angpoo의 이미지

ixevexi wrote:
당나귀를 애용하는 저로서는 :(

궁금한데 당나귀의 해쉬는 MD5가 맞나요?
만약 맞다면 P2P의 해쉬값을 검색한 후 엉뚱한 파일을 넣는 방법으로
저작권법을 보호할 수도 있겠는데요...

마치 소리바다의 가짜 MP3처럼요..


이뮬등 소스가 공개 되어있으니
그냥 Md5값을 맘데로 조절해서 보낼 수 있도록 고치는게 훨씬 쉽죠.

그런데 그정도는 잘못된 부분을 확인해서 그부분만 다시받는게 가능한걸로 압니다.