HMAC/NMAC-MD4에 대한 향상된 키 복구 공격 (Improved Key-Recovery Attacks on HMAC/NMAC-MD4)

서지정보

· 발행기관 : 한국정보보호학회
· 수록지 정보 : 정보보호학회논문지 / 19권 / 2호 / 63 ~ 74페이지
· 저자명 : 강진건, 이제상, 성재철, 홍석희, 류희수

초록

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

영어초록

In 2005, Wang et al. discovered devastating collision attacks on the main hash functions from the MD4 family. After the discovery of Wang, many analysis results on the security of existing hash-based cryptographic schemes are presented. At CRYPTO’07, Fouque, Leurent and Nguyen presented full key-recovery attacks on HMAC/NMAC-MD4 and NMAC-MD5[4]. Such attacks are based on collision attacks on the underlying hash function, and the most expensive stage is the recovery of the outer key. At EUROCRYPT'08, Wang, Ohta and Kunihiro presented improved outer key recovery attack on HMAC/NMAC-MD4, by using a new near collision path with a high probability[2]. This improves the complexity of the full key-recovery attack on HMAC/NMAC-MD4 which proposed by Fouque, Leurent and Nguyen at CRYPTO'07: The MAC queries decreases from to , and the number of MD4 computations decreases from to . In this paper, we propose improved outer key-recovery attack on HMAC/NMAC-MD4 with MAC queries and MD4 computations, by using divide and conquer paradigm.

참고자료

· 없음