Hash Length Extension 공격 방법

※ 본 내용은 공부 목적으로 작성된 내용입니다 ※ 잘못된 부분이 있으면 언제든지 댓글로 알려주세요!

 

보통 Length Extension 공격은 크립토말고 웹이랑 연계해서 나올 때가 있어 내용을 정리했습니다

 

MAC(Message Authentication Code)

 

MAC (Message Authentication Code)은 일종의 전자서명이라 생각하면 된다 

예를 들어 A라는 사람이 B에게 "떡볶이를 사와" 라는 메시지를 보낸다고 하자

이때 A가 보낸게 맞고 다른 사람이 이 메시지를 변조한 메시지가 아니라는 것을 알고 싶을 때 A와 B가 공통적으로 공유하는 키 값을 사용한다 (공격자는 이 키값을 모른다)

 

A는 메시지를 보내면서 key 값 뒤에 전달하고자 하는 메시지를 붙인 뒤 해시를 취한 값으로 다음과 같은 서명값을 만들게 된다

signature = hash($key+$msg)

 

여기서 key가 musa면 hash(musa떡볶이를 사와)값이 된다

 

그리고 이 서명값이 포함된 메시지를 B에게 보내면 B는 전달받은 메시지와 서명 값을 확인한 뒤, 자신이 가진 키를 이용해 동일한 방식으로 서명 값을 생성한다 생성된 서명 값이 전달된 값과 일치하면, 해당 메시지가 A에 의해 만들어졌음을 확인할 수 있다

 

Hash Length Extension Attack이란?

 

Length Extension Attack은 위에서 설명한 MAC(Message Authentication Code)에서 공격으로, MD(Merkle damgard) 방식을 사용하는 Hash 함수에서 발견되는 취약점입니다

 

대상 Hash 함수들 : MD5, SHA-1, SHA-2 등

 

MD(Merkle damgard) 방식은 블록 기반 해시 함수의 설계 구조 중 하나로, 입력 데이터를 고정된 크기의 블록으로 나누고, 순차적으로 처리하여 최종 해시값을 생성하는 방식입니다 (이때 블록 크기를 맞춰야 하기 때문에 패딩을 추가하여 작동함)

 

이 점을 이용해서 키값을 몰라도 이미 완성된 서명값과 원본 메시지만 알고 있으면 이 뒤에 새로운 메시지를 추가해서 서 서명값을 만들어낼 수 있다 이러한 해시 값을 확장하는 공격을 Length Extension Attack 즉 '길이 확장 공격'이다

 

하지만 이 공격을 하기 위해 아래 조건들이 필요하다

1. 키의 길이
2. 메시지 내용
3. 메시지에 대한 올바른 서명값
4. MD(Merkle damgard) 방식인지 확인 (MD5, SHA-1, SHA-2)

예를 들어 올바른 서명값에 musa 메시지를 추가해서 보내보자

 

원본 메시지 : hello

키 : secret

signature : SHA-1(key|msg) = 5112055c05f944f85755efc5cd8970e194e9f45b

추가할 메시지 : musa

 

MD5, SHA-1, SHA-2를 포함한 알고리즘들은 64byte의 블록 크기(패딩 추가 후)가 맞춰져야 한다

패딩 과정에서 0x80으로 시작하고 그 뒤에 0x00으로 채운 후, 추가할 메시지의 길이를 64비트(8byte)로 추가하는 방식이다

 

그래서 실제 signature에 적용된 패딩값은 hello\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x28입니다

 

0x80 x00 : 50byte 패딩 (키 길이가 6byte이므로 (64[블록크기]-6=58))

0x28 : 8byte

이런식으로 패딩이 적용됩니다 여기에 musa메시지를 추가하면 0x28뒤에 musa 문자가 붙여집니다

 

import hlextend

sha = hlextend.new('sha1')
print(sha.extend(b'musa', b'hello', 6, '5112055c05f944f85755efc5cd8970e194e9f45b'))
print(sha.hexdigest()) # <- musa 메시지가 추가된 새로운 서명값 생성

#aadb8979a2e710d9d1ba27c7131a2d185a116dc7

 

추가로 이 패딩 과정을 도와주는 hlextend과 hashpumpy가 있습니다

만약 키 길이가 모른다 해도 키 길이부분에 1~n까지 브루트포스를 이용해서 추가할 수 있다

 

자세한 내용은 아래 github 내용을 참고해 보세요

GitHub - stephenbradshaw/hlextend: Pure Python hash length extension module

 

Length Extension Attack 대응 방안

 

MD(Merkle damgard) 방식을 사용하는 Hash 함수에서 발견되는 취약점이기 때문에 이 방식을 사용하지 않는 해시 함수(SHA-3)를 사용하면 된다

또 다른 방식으로는 md5, sha1,sha2 알고리즘을 이중으로 해시하면 된다

 

[ 참고 자료 ]

Hash Length extension attack - 길이 확장 공격

 

Length extension attack - Wikipedia

 

Length extension attack