[논문]충돌쌍 탐색 공격에 대한 해쉬 함수 안전성 강화에 관한 연구

정은진; 한정훈; 김승주; 원동호

충돌쌍 탐색 공격에 대한 해쉬 함수 안전성 강화에 관한 연구
A Study on Enhancing Hash Function Security against Collision Search Attack 원문보기

정은진 (성균관대학교 정보통신공학부 정보보호연구소) , 한정훈 (성균관대학교 정보통신공학부 정보보호연구소) , 김승주 (성균관대학교 정보통신공학부 정보보호연구소) , 원동호 (성균관대학교 정보통신공학부 정보보호연구소)

단방향 암호화 함수인 해쉬 함수는 2005년 Wang의 새로운 공격법이 발표되면서 안전성에 대한 문제점이 조금씩 드러나기 시작하고 있다. Wang의 새로운 차분 공격법은 현재 가장 널리 사용하고 있는 해쉬 알고리즘인 SHA-1을 이론적으로 $2^{69}$의 계산으로 충돌을 찾을 수 있다고 하였다. 본 논문에서는 차분 공격이 이루어지는 방법과 Wang의 차분 공격이 지니는 두 가지 특성에 대해서 연구하였고, MDx계열의 해쉬 함수의 안전성에 대한 기존의 제시된 해결책과 다른, 한 블록의 모든 워드 값을 변형 처리한 방식을 제안한다.

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

문제 정의

본 논문에서는 Wang 교수가 개발한 차분 공격법에 대한 보완책으로서 새로운 메시지 변수의 수정 처리법을 제안하였다. 향후 안전성을 더 증가시키기 위해 고정 순환이동을 삽입하거나, 각 워드의 마지막 5비트만큼을 취한 가변 순환이동을 삽입하는 방법의 연구가 필요할 할 것이다.
본 논문에서는 Wang의 충돌쌍 공격에 대해 알아보고, 새로운 메시지 변수 수정 방법을 제안하고자 한다. 2장에서는 해쉬 함수의 안전성에 대한 특성과, 생일 공격 이론, MD5의 동작과정에 대해 설명하고, 3장에서는 Wang의 차분 공격법에 대해 알아본다.

가설 설정

4. 모든 블록에 대한 처리가 끝나면 해쉬 값을 출력한다.
5. 연쇄변수를 하나의 값으로 합친다.

이론/모형

이 방법은 블록의 워드들의 값을 변환하여 임의의 두 메시지 블록 M , M′의 워드들에 의해 생기는 차분의 결과를 실제 단계에서 적용하기 어렵도록 하기 위한 방법으로 메시지 선행 처리의 개념을 사용하였다.

성능/효과

또한, 평문과 출력 값을 확장하여 안전성을 향상시킨 SHA-256과, 연쇄변수를 수정한 방식인 FORK-256보다 처리 시간이 빠름을 알 수 있다. 4장에서 설명한 각 워드 사이에 0을 삽입하는 방법을 MD5에 적용한 결과, 기존 알고리즘에 비해 31%, 각각의 워드를 연속으로 중복시키는 방식을 적용한 결과, 97%의 처리 시간이 증가하였다.
4장에서 소개한 여러 방법들과 달리 본 논문에서 제안한 방법은 메시지 변수를 수정한 후, 사용하는 방법으로 기존의 메시지 선행 처리 방법과 같이 기존의 해쉬 함수에 그대로 적용할 수 있다는 점과 메시지를 수정한다는 방법으로 접근한다는 점에서 유사점을 찾을 수 있다. 다만, 기존의 방식은 패딩 전에 메시지를 수정하는 반면, 패딩 후에 메시지 변수를 수정한다는 점에서 다르다.
기존에 제안된 메시지 선행처리 방법과의 MD5 성능을 비교하면 표 2와 같다. SHA-256과 FORK-256의 경우, 동일한 조건하에서 해쉬 값을 출력하는 시간은 제안한 방식에 비해 3배가 소요되었다.
두 번째 방법은 실제 라운드에 들어가게 되는 값인 xi와 xi′들을 각각 한데 합친 X , X′을 얻어내는 것은 현재와 같으나, 길이가 512비트나 되는 블록 X , X′으로부터 M , M′을 얻어내는 것은 계산상으로 불가능하다.
따라서 SHA-1이나 RIPEMD-160과 같은 160비트 출력 길이의 해쉬 함수에이 방법을 적용하더라도 성능의 저하는 없을 것으로 간주된다. 또한, 평문과 출력 값을 확장하여 안전성을 향상시킨 SHA-256과, 연쇄변수를 수정한 방식인 FORK-256보다 처리 시간이 빠름을 알 수 있다. 4장에서 설명한 각 워드 사이에 0을 삽입하는 방법을 MD5에 적용한 결과, 기존 알고리즘에 비해 31%, 각각의 워드를 연속으로 중복시키는 방식을 적용한 결과, 97%의 처리 시간이 증가하였다.
실제로 MD5 해쉬 함수에 4장에서 설명한 Message Whitening, Message Interleaving, 그리고 본 논문에서 제안한 기법을 각각 적용하여 실험한 결과, 다른 기법들과는 달리 본 논문에서 제안한 방식은 해쉬 함수의 처리 시간에 큰 영향을 주지 않았다. 따라서 SHA-1이나 RIPEMD-160과 같은 160비트 출력 길이의 해쉬 함수에이 방법을 적용하더라도 성능의 저하는 없을 것으로 간주된다.

후속연구

본 논문에서는 Wang 교수가 개발한 차분 공격법에 대한 보완책으로서 새로운 메시지 변수의 수정 처리법을 제안하였다. 향후 안전성을 더 증가시키기 위해 고정 순환이동을 삽입하거나, 각 워드의 마지막 5비트만큼을 취한 가변 순환이동을 삽입하는 방법의 연구가 필요할 할 것이다.

핵심어

질문

논문에서 추출한 답변

해쉬 함수를 공격하는 방법으로는 어떤 것들이 있는가?

해쉬 함수를 공격하는 방법은 세 가지로, 먼저 주어진 해쉬 값을 가지고 입력인 평문을 찾는 공격법인 “preimag e attack”과, 어떠한 입력에 대한 해쉬 값을 가지고 동일한 해쉬 값을 찾아 그에 해당하는 입력을 구하는 “second preimage attack”이 있다. 마지막으로 가장 공격하기 쉬우면서 본 논문에서 논의하게 될 공격법인 “collision attack”은 동일한 해쉬 값을 갖는 충돌쌍을 찾는 방법으로 생일 공격(birthday attack)이라는 이론을 근거로 다른 두 가지 공격 방법에 비해 공격 성공률이 월등히 높다[3].

MD5는 무엇인가?

MD5는 128비트 해쉬 값을 생성하는 해쉬 함수이다. 각 블록당 총 4라운드 64단계로 구성되어 있으며, MD5 해쉬 함수의 동작 알고리즘은 다음과 같다[5].

MD5의 각 블록은 몇단계로 구성되어 있는가?

MD5는 128비트 해쉬 값을 생성하는 해쉬 함수이다. 각 블록당 총 4라운드 64단계로 구성되어 있으며, MD5 해쉬 함수의 동작 알고리즘은 다음과 같다[5].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, 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

연합인증

충돌쌍 탐색 공격에 대한 해쉬 함수 안전성 강화에 관한 연구
A Study on Enhancing Hash Function Security against Collision Search Attack 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper

문제 정의

가설 설정

이론/모형

성능/효과

후속연구

질의응답

이 논문을 인용한 문헌

관련 콘텐츠

원문 보기

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

충돌쌍 탐색 공격에 대한 해쉬 함수 안전성 강화에 관한 연구 A Study on Enhancing Hash Function Security against Collision Search Attack 원문보기

초록 AI-Helper

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

가설 설정

이론/모형

성능/효과

후속연구

질의응답

이 논문을 인용한 문헌

관련 콘텐츠

원문 보기

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

충돌쌍 탐색 공격에 대한 해쉬 함수 안전성 강화에 관한 연구
A Study on Enhancing Hash Function Security against Collision Search Attack 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper