[논문]MJH 해쉬 함수 역상 공격

이주영; 김종성

doi:10.13089/jkiisc.2016.26.2.315

MJH 해쉬 함수 역상 공격
A Preimage Attack on the MJH Hash Function 원문보기

情報保護學會論文誌 = Journal of the Korea Institute of Information Security and Cryptology, v.26 no.2, 2016년, pp.315 - 318

이주영 (세종대학교 수학통계학부) , 김종성 (국민대학교 수학과)

초록
AI-Helper

본 논문에서 우리는 이중 블록 길이 블록 암호 기반 해쉬 함수 MJH에 대한 새로운 역상 공격을 제안한다. MJH 해쉬 함수가 n 비트 블록 암호에 기반하여 2n 비트를 출력할 때, 기존 공격은 $O(2^{3n/2})$회의 질의를 요구하였으나, 본 논문에서는 이를 더욱 개선시켜 $O(n2^n)$의 계산량 및 같은 수준의 메모리를 사용하여 역상을 찾을 수 있음을 보인다.

Abstract ▼ AI-Helper

In this paper, we present a new preimage attack on MJH, a double-block-length block cipher-based hash function. Currently, the best attack requires $O(2^{3n/2})$ queries for the 2n-bit MJH hash function based on an n-bit block cipher, while our attack requires $O(n2^n)$ queries...

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

본 절에서는 MJH 해쉬함수에 대한 새로운 역상 공격을 제안한다. 공격은 다음과 같이 구성된다.

제안 방법

또한 O(2^3n/2)회의 질의로 역상을 찾을 수 있다는 것이 알려져 있으며, 이는 이상적인 2n 비트 해쉬 함수가 2n 비트의 역상 안전성을 제공해야 한다는 점을 감안할 때, 만족스럽지 못한 수준이라 하겠다. 본 과제에서는 이 공격을 더욱 개선시켜 O(n 2ⁿ)의 계산량과 같은 수준의 메모리를 요구하는 새로운 역상 공격을 제안한다.
본 논문에서 O(2^3n/2)회의 질의를 사용하는 기존 MJH 해쉬 함수 역상 공격을 개선하여, O(n 2ⁿ)의 계산량 및 이와 같은 수준의 메모리를 요구하는 새로운 역상 공격을 제안하였다. 본고에서 사용한 바와 같이 이진트리를 구성하여 역상을 찾는 공격이 다른 종류의 블록 암호 기반 해쉬 함수에도 적용되는지 살펴보는 것이 향후 흥미로운 연구 주제가 될 것으로 보인다.

성능/효과

추가적으로, L이 표현하는 길이가 n(n+c)보다 커야 하는데(이유는 뒤에 밝혀지겠지만), 대부분의 패러미터에서 랜덤한 64 비트 값 L 이 n(n+c)보다 작게 될 확률은 미미하므로 이 확률은 무시해도 좋다. 결론적으로, 목표 해쉬값의 역 상으로 맨 마지막 블록을 찾을 때에, 이 블록이 길이 n(n+c) 이상의 메시지의 패딩된 마지막 블록이 될 수 있도록 하려면, 대략 O((n+c)2ⁿ)의 계산량이 요구된다 하겠다.
전체 계산량을 분석하면, 우리는 질의-응답 목록의 생성에 계산량 O(n 2ⁿ), 저장에 메모리 O(n 2ⁿ)을 사용하여 MJH의 목표 해쉬값에 대한 역상을 찾게 된다.

후속연구

)의 계산량 및 이와 같은 수준의 메모리를 요구하는 새로운 역상 공격을 제안하였다. 본고에서 사용한 바와 같이 이진트리를 구성하여 역상을 찾는 공격이 다른 종류의 블록 암호 기반 해쉬 함수에도 적용되는지 살펴보는 것이 향후 흥미로운 연구 주제가 될 것으로 보인다.

질의응답

핵심어	질문	논문에서 추출한 답변
	MJH 해쉬 함수는 무엇을 출력하는가?	본 논문에서 우리는 이중 블록 길이 블록 암호 기반 해쉬 함수 MJH에 대한 새로운 역상 공격을 제안한다. MJH 해쉬 함수가 n 비트 블록 암호에 기반하여 2n 비트를 출력할 때, 기존 공격은 $O(2^{3n/2})$회의 질의를 요구하였으나, 본 논문에서는 이를 더욱 개선시켜 $O(n2^n)$의 계산량 및 같은 수준의 메모리를 사용하여 역상을 찾을 수 있음을 보인다.
	MJH 해쉬 함수는 무엇에 기반하는가?	본 논문에서 우리는 이중 블록 길이 블록 암호 기반 해쉬 함수 MJH에 대한 새로운 역상 공격을 제안한다. MJH 해쉬 함수가 n 비트 블록 암호에 기반하여 2n 비트를 출력할 때, 기존 공격은 $O(2^{3n/2})$회의 질의를 요구하였으나, 본 논문에서는 이를 더욱 개선시켜 $O(n2^n)$의 계산량 및 같은 수준의 메모리를 사용하여 역상을 찾을 수 있음을 보인다.
	MJH 해쉬 함수는 무엇을 제공하는가?	MJH 해쉬 함수는 임의의 ε > 0에 대하여, O(2(1-ε)n)회의 질의까지 충돌 안전성이 보장된다는 것이 알려져 있다[3]. 따라서 거의 최적의 안전성을 제공하지만, 실제 사용되는 패러미터(예를 들어, n = 128)의 경우에는 안전성 상계에 곱해지는 상수의 영향을 무시하지 못하여 만족할 만한 수치를 제공하지는 못할 것으로 보인다.

참고문헌 (4)

M. Bona, "A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory," 3rd Edition, pp. 134-136, May 2006.
D. Hong and D. Kwon, "Cryptanalysis of Double-Block-Length Hash Modes MDC-4 and MJH," IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, Vol. E97-A, No. 8, pp. 1747-1753, August 2014.

상세보기
L. R. Knudsen, F. Mendel, C. Rechberger and S. S. Thomsen, "Cryptanalysis of MDC-2," Eurocrypt 2009, LNCS 5479, pp. 106-120, April 2009.
J. Lee and M. Stam, "MJH: a faster alternative to MDC-2," Designs, Codes and Cryptography, Vol. 76. Issue 2. pp. 179-205, August 2015.

상세보기

저자의 다른 논문 :

LOADING...

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증