강진건, 이제상, 성재철, 홍석희, 류희수,

Vol. 19, No. 2, pp. 63-74, 4월. 2009
10.13089/JKIISC.2009.19.2.63, Full Text:
Keywords: HMAC, NMAC, MD4, Key-Recovery, Near Collision, Differential Path
Abstract

2005년 Wang이 MD 계열 전용 해쉬함수에 대한 분석 결과를 발표함에 따라, MD 계열 전용 해쉬함수를 이용한 메시지 인증 프로토콜에 대한 분석 결과 또한 다수 발표되었다. CRYPTO'07에서 Fouque, Leurent, Nguyen은 Wang의 충돌쌍 공격을 이용한 MD4, MD5 기반 HMAC/NMAC의 내부 키 복구 공격과 외부 키 복구 공격을 소개하였다[4]. EUROCRYPT'08에서 Wang, Ohta, Kunihiro는 근사 충돌쌍(near-collision)을 이용한 MD4 기반 HMAE/NMAC의 외부 키 복구 공격을 소개하였다[2]. 즉, Wang 등은 새로운 근사 충돌쌍 특성을 이용하여 기 제안된 Fouque의 분석 방법을 향상시킴으로서 오라클 질의량을 $2^{88}$에서 $2^{72}$으로 감소시켰으며, MD4계산량 또한 $2^{95}$에서 $2^{77}$으로 감소시켰다. 본 논문에서는 분할-정복(divide and conquer) 공격을 이용한 새로운 MD4 기반 HMAC/NMAC의 외부 키 복구 공격 알고리즘을 제시한다. 본 논문에서 제시하는 분할-정복 공격을 이용한 공격알고리즘은 $2^{77.1246}$의 오라클 질의량과 $2^{37}$의 MD4 계산량으로 HMAC/NMAC의 외부 키를 복구할 수 있는 향상된 공격 방법이다.

Statistics
Cite this article