Hash Length Extension 공격

1. HMAC(Hash-based Message Authentication Code)

HMAC란, Hash 기반의 MAC이다. 여기서 MAC이란 Message Authentication Code로 일종의 전자서명으로, 메시지가 변하지 않았다는 것을 증명하기 위한 코드라고 볼 수 있다. HMAC을 사용하여 통신하는 과정은 다음과 같다.

 

 

1) Alice는 공개키(Lotte)를 이용하여 보낼 데이터의 HMAC 값을 생성한다

2) 데이터(Message)와 생성된 HMAC(Signature) 값을 Bob에게 전달한다.

3) Bob은 공유하고 있는 공개키(Lotte)를 이용하여 받은 데이터의 HMAC(Signature) 값을 생성한 후 전달받은 HMAC 값과 비교하여 데이터가 정상인지 확인한다.

 

 

 

2. Hash Length Extension 개요

웹 어플리케이션에서 입력 값 검증을 할 경우 무결성을 위해서 Hash 값으로 검증하는 기법인 HMAC을 사용하는 경우가 있다. 이 때 공격자는 hash value를 만드는 SecretKey 값을 알지 못하더라도 원하는 데이터를 추가하여 시그너처를 생성할 수 있는데, 이를 Hash Length Extension Attack 이라고 한다. 이 공격을 통해서 SecretKey 없이 사용자에게 변조된 데이터를 전달 할 수 있다.

 

Hash Length Extexnsion Attack 이 가능한 상세 조건은 다음과 같다.

 

1. 공격자가 키의 길이를 알고 있는 경우

2. 공격자가 Message의 내용을 알고 있는 경우

3. 공격자가 Message에 대한 정당한 서명값

4. 해시 알고리즘의 종류가 Merkle-Damgard Construction에 기반한 알고리즘의 경우(MD5, SHA-1, SHA-2)

 

위 조건이 모두 충족될 경우 Hash Length Extension Attack 이 가능해지는데, 상세 프로세스는 다음과 같다.

 

 

 

 

3. Hash Length Extension 공격 예시 상세 분석

위 그림에서 사용 된 값이 다음과 같다고 예시를 들어보자.

 

- 키 값 = "rootable"

- 메시지 = "user"

- 암호화 알고리즘 = md5()

- 서명값(Signature) = hash(secret||data) = e4ff40aabfd7bbcd96aa5a5a8d2e2701

 

서버에 값을 전달 할 때, 서명값인 H_Hack과 추가된 메시지 값인 Message_Hack를 보내기위해서는 먼저 추가된 메시지값인 Message_Hack을 알아내야 한다. 즉, 원본 메시지에 추가 메시지를 추가해야하는데, 그전에 먼저 원본 메시지인 Alice 메시지(Message_Alice)에 패딩을 해야한다.

 

STEP 1) Padding (변조된 메시지 만들기)

해시(secret + data)를 계산할 때 문자열은 하나의 '1' 비트와 여러 '0' 비트로 패딩되며, 뒤이어 문자열의 길이가 따라온다. 이것을 hex 형태로 보면 패딩은 0x80 뒤에 여러 0x00 바이트 및 길이가 붙는 형식으로 이루어진다.  여기서 0x00 바이트와 길이에 예약된 바이트 수 및 길이가 인코딩되는 방식은 알고리즘과 블록 사이즈에 따라 달라진다.

 

MD4, MD5, SHA-1, SHA-256을 포함한 많은 알고리즘들은 64로 나누었을 때 나머지가 56바이트일 때까지 패딩된다. 이를 다시 말하자면 길이가 전체 블록(64바이트)보다 8바이트 낮을 때까지 패딩된다. 왜냐하면 8바이트는 인코딩된 길이 필드의 사이즈이기 때문이다.

 

길이 필드의 바이트 순서 또한 알고리즘에 따라 달라지는데 MD4, MD5는 little-endian인 반면, SHA 알고리즘을은 big-endian이다.

 

여기까지의 내용을 우리의 예시에 적용시켜보도록 하겠다.

 

secret와 data를 연결한 length("rootableuser")는 12(0x0c) 바이트 또는 96(0x60) 비트이다. 따라서 우리는 12 바이트의 데이터, ("rootableuser"), 44 바이트의 패딩 (80 00 00 ....), 그리고 8 바이트의 리틀엔디안 길이 필드 (60 00 00 00 00 00 00 00), 총 64 바이트 ( 또는 한 block)을 가지고 있다. 

 

 

이것을 함께 나타내면 다음과 같다.

 

- 키 값 = secret

- 메시지 = “user”

- 80 00 00 ... = 0x80으로 시작하는 44 byte의 패딩

- 60 00 00 00 00 00 00 00 = 리틀 엔디안으로 나타낸 bit 길이 

 

이것이 그림상에서의 Message_Alice로, 원본 메시지 이다.

 

STEP 2) 공격 수행

위에서 Alice의 원본 메시지(Message_Alice) 데이터를 확인하였으므로 메시지를 추가하여보자

 

먼저 문자열에 추가할 메시지인 "hacker"를 추가해보자. 이것은 다음과 같다.

 

이것이 그림상에서의 Message_Hack 값이 되겠다. 이 값을 해시하여 H_Hack 값을 메시지와 함께 Bob에게 보내면 된다.

 

 H_Hack을 알아내기 위해서 python 에서 hashpumpy 를 이용하면 된다. 사용법은 다음과 같다

 

import hashpumpy

hash,message = hashpumpy.hashpump('Know Hash(H1)','Known Message(M1)','Message to appen(M2)',KeyLength)

 

 

 

 

STEP 3) 서버에서의 계산

그렇다면 서버에서는 어떻게 검증할까, 서버에서의 방식을 알아보자.

서버는 비밀키를 문자열 앞에 붙일 것이므로 우리는 비밀키를 제외한 문자열을 전송해야 한다.

 

그럼 서버는 여기에 비밀키를 추가하여 다음과 같은 문자열이 만들어진다.

 

그리고 이 문자열의 해시는 다음과 같다.

2ae22da066e3311036d6edc5924db87a

 

해당 해시값을 구하는 python 코드는 다음과 같다

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

import hashlib secret="rootable" data="user" string="" append="hacker" string+=secret string+=data string+="\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"\         "\x60\x00\x00\x00\x00\x00\x00\x00" string+=append print hashlib.md5(string).hexdigest()