[Crypto] 해시 함수와 취약점 (Basic)

Intro

이 글에서는 비교적 간단한 해시 함수에 대해서 다루고, Crypto 분야 CTF를 기준으로 할 때 이러한 해시 함수에서 나타날 수 있는 초보적인 취약점에 대해 서술한다. 구체적으로, 이 글에서는 MD5와 SHA 계열 해시에 대해서 다룬다.

What is Hash?

해시 함수는 임의의 입력을 받아, 이를 고정된 크기의 출력으로 매핑하는 함수이다. 해시 함수는 일반적으로 같은 입력에 대해서 항상 같은 출력을 내기 때문에 두 데이터가 같은지를 빠르게 비교하거나 데이터를 저장하여 검색하기 위해 색인할 때 유용하게 활용할 수 있다. 그러나 해시 함수의 값이 같다고 해서 실제 데이터가 같다고 간주할 수는 없다. 이는 비둘기집의 원리 때문으로, 입력의 크기는 무한하지만 출력의 크기는 유한하기 때문에 동일한 출력을 내는 서로 다른 입력이 존재하게 된다. 이를 해시 충돌이라고 한다. 검색이나 비교 시에는 해시 충돌이 일어났을 때 원문과 비교하는 과정을 거치면 해결되겠지만, 원문을 노출시키지 않아야 상황이거나 데이터 크기가 너무 커 효율성을 보장할 수 없는 상황에서는 원문 없이 해시 값만 가지고 인증을 해야 하는 상황이 벌어질 수 있다. 이러한 경우에는 암호학적으로 안전한 암호학적 해시 함수를 사용해야 한다. 우리가 크립토 문제풀이에서 다루어야 하는 함수들은 이 암호학적으로 안전한(이라고 생각되어 왔던) 해시 함수들이다.

암호학적 해시 함수는 다음과 같은 성질을 가져야 한다. 먼저 Preimage resistance로, 주어진 해시 값에 대해 그 해시 값을 생성하는 입력값을 찾는 것이 어려워야 한다. 그 다음으로 Second preimage resistance가 있는데, 입력 값에 대해 그 입력 값의 해시 값과 동일한 해시 값을 생성하는 또다른 입력값을 찾는 것이 어려워야 한다. 마지막으로 Collision Resistance가 있는데, 같은 해시 값을 가지는 두 입력 값을 찾는 것(해시 충돌을 찾는 것)이 어려워야 한다. 이 성질 중 하나라도 만족하지 못하면 해시 함수는 암호학적 해시 함수로서의 기능을 완전히 상실하게 되며, 실제로 사용하지 못하는 해시 함수가 되어버린다. 잘 설계된 해시 함수는 Avalanche effect에 의거하여 입력을 조금만 바꾸어도 해시 값의 거의 모든 부분이 바뀌어 엔트로피가 붕괴하기 때문에 preimage attack을 하는 것과 brute force attack을 하는 것에 큰 차이가 없다.

MD5

MD5는 위험하다.

MD5는 1991년에 개발되어 이제까지 굉장히 많이 쓰인 해시 함수 중 하나이지만, 2012년에 그 위험성이 발견되어 완전히 폐기되었다. MD5에는 낡은 노트북으로도 매우 손쉽게 여러가지 공격을 수행할 수 있으며, 그 공격들 하나하나가 굉장히 강력한 공격들이다. MD5의 출력은 128비트이며, 입력은 512비트 단위로 쪼개져서 따로따로 해시된다(만약 남은 입력이 512비트보다 작다면 패딩한다). 구체적으로는, 512비트 단위로 쪼개진 뒤 1번 블럭을 해시하고, 그 결과와 2번 블럭을 같이 해시하고, 그 결과와 3번 블럭을 같이 해시하고... 와 같은 과정을 거친다. 다시 말해 Merkle–Damgård construction 과정을 거치는 해시 함수이다.

MD5는 이미 많은 해시 충돌이 보고되었기 때문에, Collision Resistance를 가지지 않는다. 위키백과 등에 이러한 해시 충돌을 내는 입력값의 예시가 존재한다.

# First Input
d131dd02c5e6eec4 693d9a0698aff95c 2fcab58712467eab 4004583eb8fb7f89
55ad340609f4b302 83e488832571415a 085125e8f7cdc99f d91dbdf280373c5b
d8823e3156348f5b ae6dacd436c919c6 dd53e2b487da03fd 02396306d248cda0
e99f33420f577ee8 ce54b67080a80d1e c69821bcb6a88393 96f9652b6ff72a70

# Second Input
d131dd02c5e6eec4 693d9a0698aff95c 2fcab50712467eab 4004583eb8fb7f89
55ad340609f4b302 83e4888325f1415a 085125e8f7cdc99f d91dbd7280373c5b
d8823e3156348f5b ae6dacd436c919c6 dd53e23487da03fd 02396306d248cda0
e99f33420f577ee8 ce54b67080280d1e c69821bcb6a88393 96f965ab6ff72a70

# Hash Value
79054025255fb1a26e4bc422aef54eb4

단순히 해시 충돌을 찾는 것을 넘어, 특정한 해시 충돌을 찾는 문제는 약간 더 어렵다. 그러나 이미 많은 공격이 실전성 있게 사용되고 있기에 그 중 일부를 소개한다.

Identical Prefix Attack

특정한 prefix를 공통으로 가지는 두 입력에 대해 해시 충돌을 발생시켜야 하는 경우가 있다. 이러한 경우에 Identical prefix attack을 사용할 수 있다. 2009년에 발표된 FastColl을 사용하면, 단 몇 초의 계산으로 prefix가 같으면서 같은 해시 값을 가지는 2블럭의 값을 만들 수 있다. 후술할 방법을 이용하면 suffix까지 같게 만들 수 있다.

2012년에 발표되어 2017년에 구현된 UniColl을 사용하면, 조금 더 어려운 공격을 수행할 수 있다. Unicoll의 경우 단순히 Identical prefix를 가지는 두 입력을 찾아주는 것 외에 아무것도 보장되지 않는 FastColl과 비교해 볼 때 예측 가능한 변화를 줄 수 있다. Unicoll은 주어진 prefix를 그대로 가지는 입력 하나와, 그 입력과 완전히 동일하지만 시작 후 10번째 바이트가 정확히 1만큼 큰 입력의 해시 충돌을 찾아준다. 수행 시간은 일반적인 컴퓨터 기준으로 약 5분에서 10분 사이이다. 이는 굉장히 중요한 성질인데, 일반적으로 하나의 파일은 특정 prefix p를 가지고 다른 하나의 파일은 prefix q != p를 가지게 하는 것은 Chosen-prefix attack을 활용해야 가능하다. Chosen-prefix attack은 수행 시간이 Identical prefix attack에 비해 매우 오래 걸리기 때문에, 이런 경우에 제한적으로 Unicoll을 활용하여 대신 exploit할 수 있다(당연히, prefix p가 10바이트 이상이어야 한다는 등의 귀찮은 조건들이 따라붙기는 하나 몇 분만에 이런 충돌을 찾을 수 있다는 것은 매우 매력적인 점이다).

Identical Prefix Attack을 사용하는 대표적인 경우는 동일한 파일 형식을 가지는 경우(즉, 같은 헤더를 가지는 경우)에 해시 충돌을 찾아야 하는 상황이 있겠다.

Chosen Prefix Attack

Chosen prefix attack은 Idential prefix attack에 비해 훨씬 강력한 공격이다. 아예 두 파일 A와 B에 대해 원하는 prefix a와 b를 지정하고 해시 충돌을 찾아주기 때문이다. 2009년에 나온 공격 기법인 HashClash를 사용하면 수행할 수 있다. 그러나 HashClash 공격은 24코어 기준으로도 3시간이 걸리며 이는 수행하기에 꽤나 부담스러운 시간이다. 따라서 가능하면 다른 방법을 통해 exploit하고, 최후의 수단으로 남겨두는 것이 도움이 되리라 생각한다.

File Format Attack

유명한 파일 형식에 대해서는 파일 형식의 특수성을 이용해서 더 빠르고 효율적으로 exploit하는 많은 방법들이 개발되어 있다. 이는 흔히 사용되는 공격 방식은 아니나 알아두어서 나쁠 것은 없다. Polycolls에서 찾아볼 수 있다.

SHA

SHA의 경우에는 많은 알고리즘이 개발되어 있지만, 현재 사용되는 것은 SHA-1, SHA-2, SHA-3으로 구분된다. SHA-1의 경우 취약점이 발견되어 사용하는 것을 강력하게 권장하지 않는 수준까지 이르렀고, SHA-2의 경우 약한 취약점 또는 추측이 제안되기는 하였으나 현실적으로 CTF/실전 환경뿐만 아니라 이론적으로도 사용하기가 어려워 공격에 아무런 실전성이 존재하지 않는 것으로 알고 있다(혹시 아니라면 댓글로 알려주시길 바랍니다). SHA-3의 경우에는 2015년에 제안된 새로운 알고리즘이기 때문에 발견된 취약점이 사실상 아예 존재하지 않는다. 전반적으로 SHA의 경우에는 취약점이 발견된 SHA-1의 경우마저도 MD5에 비해 굉장히 안전한 편이다.

SHA-1의 경우 Chosen prefix attack은 존재하지 않지만, Shattered를 활용해 Identical prefix attack은 할 수 있다. 그러나 이마저도 GPU 1개 기준 110년정도가 걸리기 때문에 실제로 사용되는 중인 SHA의 경우에는 일반적인 공격을 수행할 수 없다고 간주하는 것이 옳다.

그러나 SHA2 중 SHA256의 경우는 해시 함수 외적인 굉장히 특이한 성질을 하나 보유하고 있는데, 바로 비트코인이다. 비트코인을 채굴하는 조건은 SHA256 해시값의 맨 마지막 비트가 특정 개수 이상 0이 되는 입력을 찾는 것이기 때문에 일반적으로 SHA 해시값에 대해서는 아무런 가정을 할 수 없지만 끝부분이 0으로 가득 찬 해시값만은 쉽게 찾을 수 있다.

More : Merkle–Damgård construction

해시 함수 중 입력을 특정 비트 단위로 블록으로 쪼개어 앞 부분의 해시 값을 뒤쪽 블록의 해시 값을 계산하는 데 활용하는 함수들을 Merkle–Damgård construction 과정을 따른다고 한다. 앞서 설명한 MD5와 SHA-3을 제외한 SHA 계열 해시 함수들이 모두 이 성질을 만족한다. 이런 과정을 따르는 함수들은 해시 함수 $H$에 대해 $H(A) = H(B)$를 만족시키면 $H(A||C) = H(B||C)$ 또한 만족한다. 따라서 하나의 해시 충돌을 찾았으면 그 뒤에 임의의 데이터를 마음대로 붙여 넣어 추가적인 해시 충돌을 얼마든지 만들 수 있다.

더 나아가, 이 성질을 만족하는 함수들은 Length-Extension attack에 취약하다. 어떤 메세지 $M$이 있고, $M$의 길이는 알지만 $M$이 구체적으로 무엇인지는 모른다고 가정해 보자. 이 때 $H(M)$을 알고 있다면 $M$에 적용된 패딩을 $p$라고 할 때 $M||p$로 시작하는 임의의 메세지의 해시 값을 바로 구하는 것이 가능하다. 생각해보면, 이 함수들은 블럭 사이즈와 맞아 떨어질 때까지 패딩을 추가하므로 $H(M) = H(M||p)$이다. 또 $p$는 정해진 padding scheme에 따라 적용되는 값이므로 $M$의 길이만 알면 $p$도 아는 값이 된다. 따라서 $H(M||p||M')$는 Merkle–Damgård construction의 성질에 의해 $H(M||p)$와 $M'$를 활용해 구할 수 있다. 만약 Merkle–Damgård construction인, 충분히 안전하지 못한 함수들을 인증에 사용한다면(다시 말해 HMAC에 사용하게 된다면) 공격자가 얼마던지 유효한 인증을 만들어낼 수 있다.