지난글에서 얘기했던 컨퍼런스에서 발표된 결과중 간단하게 소개할수 있는게 있어서 한번..

 

Collision finding problem은 어떤 해쉬함수 에 대해 를 만족하는 쌍 을 찾는 문제이다 (이라고 가정하자)

• 만약 이 문제를 임의의 함수 에 대해 생각한다면 고전적으로는 시간이 정도가 필요하다.
• 반면 양자컴퓨터를 이용하면 BHT algorithm을 이용하면 정도에 찾을수 있음이 알려져 있다.

그런데 사실 현실의 Hash function은 완전히 random function은 아니고, 특정한 구조를 가진 함수들을 쓴다. 그래서 암호학에서 구체적인 Hash function의 (collision-resistance에 대한) 안전성에 대한 연구의 목표는 위 일반적인 공격(=generic attack)보다 빠른 공격을 찾는게 된다.

실제로 Hash function들은 주로 비슷한 구조의 함수를 여러번 적용하는 형태로 만들어진다. (예를들어 SHA3는 어떤 구조를 12+번정도 반복함) 이런 구조가 적용된 횟수를 라운드라고 하고, 많은 공격에서 실제 구조보다 약간 작은 라운드만 반복했을때를 타겟으로 잡고 연구한다. 이런 공격을 Reduced-round attack이라고 함. 실제 Hash는 알려진 Reduced-round attack의 최대 라운드보다 몇개정도 큰 라운드로 고정해서 사용한다.

최근 학계에서는 Hash function 같은 경우는 여러가지 이유로 양자컴퓨터를 이용한 공격이 아주 드라마틱한 결과를 이끌어낼거라고 생각은 안하는것 같다. 어느정도는 기존에 알려진 공격들의 서브루틴들이 양자알고리즘으로 바뀌었을 때 빨라지는정도로만 안전성이 위협을 받을것이라고 추측하고 있음. 특히 Round는 지금과 똑같이 써도 되지 않을까 막연히 (아무런 논의없이) 가정하고 있는것으로 보인다.

 

그런데 Hosoyamada Akinori와 Yu Sasaki에 따르면 그 예상이 완전히 옳지는 않다고 한다. Rebound attack이라는 방식이 기존에는 Whirlpool과 AES-MMO라는 두 Hash function을 각각 5,6라운드에 대한 Reduced-round attack이 알려져 있었는데, 이번에 이를 양자컴퓨터를 잘 이용해서 변형하면 6,7라운드에 대해 generic attack보다 빠르게 공격할수 있다고 한다.

즉 Hash function의 양자컴퓨터에 대한 안전성이 generic attack에 대한 공격속도의 증가 말고도 뭔가 구조적인 문제가 조금 더 있을 수 있다는 결론을 얻게된다. 다만 현실적인 공격은 여전히 하는게, 양자컴퓨터도 없고, Whirlpool같은 경우 10라운드를 쓰는데 여전히 그건 한참 남았으니 -_-..