더 이상 이 블로그는 운영되지 않습니다. 새 블로그로 가 주세요.
SHA-1도 깨졌다!
2005/02/16 PM 03:00 | 소식/수학, 과학 | 12 comments | 0 trackbacks | AllBlog: vote, to pocket
저번에 MD5랑 SHA-0 깨졌다는 소리를 들은 적이 있는데... SHA-1도 중국 사람들에 의해 깨졌다는 소식이 들렸다. 이런... 믿을 만한 것들이 다 깨지니 불안해 죽겠군 -,.-;
SHA-1에서 충돌(collision; 서로 다른 두 평문에 대해 같은 해쉬값이 대응되는 경우)을 찾는 데 일반적인 무작위 공격은 280번의 해쉬 연산이 필요하지만 이 방법에 따르면 269번의 해쉬 연산만이 필요하다고 한다. 58-round SHA-1은 나도 잘 모르겠는데... 아마 일반적인 SHA-1(80-round)에서 앞의 58개만 떼어서 쓰는-_- 것 같아 보인다만 아무튼 이 SHA-1 변형은 233번의 연산만으로 충돌을 찾아 낼 수 있다고 한다.
뭐... 저 쪽에서도 아직 논문이 발표되지 않아서 확실하지는 않아 보이지만 적어도 얼마정도는 믿을 만하다고 하고 있으니... 그 새 위키백과에도 올라 오고; 쩝쩝.... 앞으로 무슨 해쉬 알고리즘 써야 하는 거지? -_-; (그냥 md5 써 이 놈아)
TrackBack URL: http://sapzil.info/soojung/trackback.php?blogid=494
Comment: 토끼군 (2005/02/16 PM 04:23)
azurespace: 하지만 슈퍼 컴퓨터에서 감당할 수 있을 정도로 내려 갔다는 건 충분히 화제가 될 만 하지. brute-force보다는 낫잖아?
Comment: Powring (2005/02/16 PM 08:11)
낄낄...
지문인식....[...]
홍채인식...,[...]
Comment: 토끼군 (2005/02/16 PM 08:18)
Powring: http://xenofreaks.com/htm/freaky/ars.htm 이런 인식 시스템도 있죠...
Comment: 인클루드 (2005/02/16 PM 10:00)
방금 KLDP BBS 에서 보고 왔습니다. 하긴... 슈퍼컴퓨터에서 돌린다고 하면 1000배 빨라진 것은 무척 위험해진 것이군요... -_-!
Comment: 토끼군 (2005/02/16 PM 10:06)
저 지수가 5x 대로만 내려 가도 상당히 큰 발전이지요... :S
Comment: azurespace (2005/02/16 PM 10:08)
어차피 해쉬라는 방법 특성상, 어떤 규약을 사용해도 가능한 조합의 수를 좁히는 것이 가능하지.
Comment: 토끼군 (2005/02/16 PM 10:16)
azurespace: 사실 컴퓨터가 좀 더 발전하면 저런 것이 무의미해질 수도 있지...
Comment: daybreaker (2005/02/17 AM 12:43)
만약 양자컴퓨터가 빠른 시일 내에 현실화된다면 n bit 계산방식이 가능해질 것이고, 그때가 되면 지금처럼 어려운 인수분해에 의존하는 암호화체계는 모두 소용없을 거라는 전망이 있지..
그래도, 그 전까지 일반적인 용도로 사용하다가 충돌이 일어날 가능성은 거의 없겠지?? (설마가 사람잡는다던데..-_-)
Comment: 토끼군 (2005/02/17 AM 02:49)
daybreaker: 한 namespace 안에서 충돌이 일어 날 가능성은 희박해 보이지. 하지만 지금까지 생성된 모든 해쉬 값들 중에서는 충돌이 일어 났을 수도 있을 것 같다.
Comment: cwryu (2005/02/17 AM 04:36)
저번의 MD5의 경우도 그렇지만, 해시값이 같은 경우를 꽤 빠르게 찾을 수 있다고 해도, 그걸 이용해서 지금 그 알고리즘을 사용하고 있는 분야를 무력화시킬 수 있다는 이야기는 아닙니다. 실제로 그 충돌을 찾아내서 악의적인 목적으로 이용할 수 있으려면 원하는 형태로 조작하면서 해시값을 유지시키는 경우를 찾는다던가 그래야 하니까요.
Comment: 토끼군 (2005/02/17 AM 11:57)
cwryu: 너무 난리를 치는 것 같아 보이긴 합니다만, collision을 발견했다는 것은 적어도 cryptanalysis 분야에서는 충분히 의미 있는 일이라고 생각합니다. 물론 저번 MD5 때나 이번 일이나 collision을 발견한 것 뿐이기 때문에 (이건 시간이 지나면 어떻게든 일어 날 일이긴 하죠. 의도적으로 발견하는 게 어려울 뿐...) 실제로 악용할 수 있는 정도까지 연구가 이루어지려면 한참 남았죠.
예전에 찾아 봤었는데 방금 말씀하신 대로 임의의 평문 a에 대해서 hash(a)==hash(b)인 다른 평문 b를 찾아 내는 것이 어렵다는 걸 보장하는 것을 second preimage resistant라고 하더군요. 둘 다 이게 깨지지는 않았으니까 아직 크게 문제는 없다고 생각합니다. :)
Comment: azurespace (2005/02/16 PM 04:16)
어차피 2^80이나 2^69나 개인용 컴퓨터에선 감당하기 힘들지.