Hash Length extension attack

Hash Length extension attack - 길이 확장 공격

2020. 3. 31. 20:57

CTF에서 크립토계열 문제들을 보면 이따금씩 등장하는 공격기법이다.

딱히 어려운 공격법은 아니니 곧바로 예시를 들면서 설명을 들어가자.

HMAC(Hash-based Message Authentication Code)

HMAC이 뭐냐면 Hash 기반의 MAC이다. 여기서 MAC은 Message Authentication Code인데, 일종의 전자서명이라고 보면 된다.

만약 A라는 사람이 B에게 "마트에서 계란 5개 사와"라는 메시지를 보낸다고 치자. 그런데 이 메시지가 B에게 도착했는데, A가 보낸게 맞고 다른 공격자가 임의로 변조시킨 메시지가 아니라는것을 알고 싶다고 하자.

이때 쓰이는 것이 MAC이다. A와 B가 공통적으로 공유하는 키 값이 있다고 하고, 공격자는 이 키를 모른다고 하자.

그러면 A는 메시지를 보내면서 key 값 뒤에 메시지를 붙인 뒤 해쉬를 취한 값으로 서명값을 만든다.

다음과 같은 모양이 나오게 된다.

signature = sha256( key + message )

만약 공유하는 비밀 키의 내용이 "CarpeDiem"이라고 하자.

그러면 서명값은 sha256("CarpeDiem마트에서 계란 5개 사와") 의 값이되게 된다.

그리고 이 서명값을 메시지와 같이 보낸다고 하자.

그러면 B는 메시지와 서명값을 받고, 본인이 가지고 있는 키를 기반으로 서명값을 만들었을때 이 서명값이 전달된 서명값과 일치하면 이 메시지는 A가 만든것이 맞다는 것을 알 수 있다.

공격자는 A와 B가 공유하고 있는 키 값을 알 수 없으므로 정당한 서명값을 만들 수 없다.

이러한 HMAC을 쓰는 경우 특정 조건이 맞으면 이 해쉬 길이 확장공격을 사용할 수 있다.

이 공격으로 공유되는 비밀 키 값은 알수가 없지만, 어떤 메시지와 서명값의 쌍을 안다면 메시지 뒤에 다른 문자열이 추가된 메시지와 그에 맞는 정당한 서명값을 만들 수 있다.

사전 조건

공격을 하기 위해 필요한 조건들은 몇 가지 정보들이다. 다음 내용들을 알면 공격이 가능하다.

1. 키의 길이

2. message의 내용

3. message에 대한 정당한 서명값

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

만약 아까 이야기한 예시를 계속해서 들면 키의 길이가 CarpeDiem인 것은 모르더라도 9글자인 것을 알고, "마트에서 계란 5개 사와"가 메시지인 것을 알고, 이 메시지에 대한 서명 값이 0xdeadbeef라는 것을 안다고 가정하자.

그러면 이 정보를 바탕으로 공격자는 뒤에 공격자가 원하는 메시지가 추가된 메시지와 서명값을 만들어낼 수 있다.

가령 공격자가 "그리고 고기도 2kg 사와"라는 메시지를 뒤에 추가하려고 한다고 하자.

그러면 이 공격을 통해서 공격자는 "마트에서 계란 5개 사와 그리고 고기도 2kg 사와"라는 메시지에 대한 정당한 서명값을 알아낼 수 있다.

실제로는 기존 문장과 추가 된 문장 사이에 Null byte 값들이 여러개 추가될 수 있다.

공격 예시

여기서 설명하는 내용은 위키 백과와 같은 예시이다.

원래 데이터가 아래와 같다고 하자

Original Data: count=10&lat=37.351&user_id=1&long=-119.827&waffle=eggo

Original Signature: 6d5f807e23db210bc254a28be2d6759a0f5f5d99

여기에 공격자는 마지막에 파라메터를 추가하고자 한다.

Desired New Data: count=10&lat=37.351&user_id=1&long=-119.827&waffle=eggo&waffle=liege

그러면 공격이 이루어진 데이터는 다음과 같은 형태를 띄게 된다.

New Data: count=10&lat=37.351&user_id=1&long=-119.827&waffle=eggo\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\x00\x00\x00 \x00\x00\x02\x28&waffle=liege

New Signature: 0e41270260895979317fff3898ab85668953aaa2

사이에 Null byte들이 많이 들어가게 되는데, 저 Null byte로 해시함수를 계산할때 내부 구조를 적절히 바꾸어서 하는 방식이라고 한다.