flawed.net.nz

URL: https://flawed.net.nz/2018/02/21/attacking-merkle-trees-with-a-second-preimage-attack/

Title: flawed.net.nz

(@mah3mm 님이 호기심을 불러일으켜 주고, 이어서 저를 가르쳐 주신 덕분에 작성합니다)

이 글은 머클 트리(Merkle Tree) 구현에서 흔히 발생하는 결함 하나를 개괄하고, 가장 인기 있는 파이썬 라이브러리들을 대상으로 가능한 공격을 시연합니다.

하지만 그 전에, 머클 트리와 2차 프리이미지(Second Preimage) 공격이 무엇인지 간단히 살펴보겠습니다.

머클 트리

머클 트리는 비교적 단순한 자료구조로, 데이터 조각(원래부터 파일처럼 조각 단위이거나, 의도적으로 조각으로 나눈 데이터)에 대해 전체 데이터에 대한 해시를 독립적이며 분산된 방식으로 계산할 수 있게 해줍니다.

예를 들어, 1GB 파일 2000개가 있고 데이터 전체의 SHA256을 계산하고 싶다고 해봅시다. 일반적으로는 모든 파일을 하나로 이어 붙인 뒤 그 데이터에 대해 단 한 번 해시를 계산합니다. 하지만 이는 여러 이유로 문제가 됩니다. 그중 하나는, 단 하나의 파일에서 단 1바이트만 바뀌어도 2TB 전체 데이터를 다시 SHA256 해야 한다는 점입니다. 또 다른 문제는, 2000개 파일을 전부 확보하기 전에는 해시 계산을 시작할 수 없으며, 그 시점에서야 처음부터 다시 시작해야 한다는 점입니다.

머클 트리는 이를 각 데이터 조각(위 예시에서는 각 1GB 파일)을 개별적으로 해시한 뒤, 그 해시들을 이진 트리 형태로 계속 해시해 나가 최종적으로 단 하나의 해시 값(모든 데이터 조각 전체를 대표하는 값)만 남도록 구성함으로써 해결합니다. 따라서 단 하나의 파일이 바뀌면 그 파일만 다시 해시하고, 이후에는 ‘해시의 해시’를 계산하면 되는데 이는 매우 빠른 연산입니다.

그림과 위키피디아 페이지는 말 천 마디보다 낫습니다:

2차 프리이미지 공격

프리이미지(Preimage) 공격은 해시 지문(fingerprint) 하나가 주어졌을 때, 그 값으로 해시되는 어떤 데이터든 찾아내는 공격을 말합니다.

예를 들어 제가 MD5 값 5EB63BBBC01EEED093CB22BB8F5ACDC3를 주었는데, 여러분이 그 해시를 만들어내는 데이터를 찾아낸다면, 프리이미지 공격으로 MD5를 깨뜨린 것입니다.

참고: MD5는 128비트 해시 함수이며, 현재 알려진 최선의 프리이미지 공격도 그 강도를 123비트 수준으로만 낮춥니다. 이는 프리이미지 공격 관점에서는 여전히 매우 강합니다. MD5가 폐기(deprecate)된 진짜 약점은 충돌(Collision) 공격입니다. 이는 공격자가 서로 다른 두 입력을 같은 해시 값으로 만들 수 있게 해주지만, 그 결과가 통제 가능하거나 예측 가능한 방식은 아닙니다.

2차 프리이미지(Second Preimage) 공격은 어떤 데이터가 주어졌을 때, 그 첫 번째 데이터와 동일한 해시를 생성하는 두 번째 데이터를 찾는 공격입니다. 일반적인 프리이미지 공격과 매우 비슷하지만, 목표 해시 값으로 이어진다는 것이 이미 알려진 샘플 데이터가 주어진다는 점에서 미묘하게 다릅니다. 또한 2차 프리이미지는 항상 충돌보다 어렵습니다. 왜냐하면 한쪽 입력은 공격자가 통제할 수 없는 값이기 때문입니다.

머클 트리에 대한 2차 프리이미지 공격

머클 트리에 대한 공격은 한 번 이해하고 나면 꽤 단순합니다. 많은 구현은 “여러 입력을 머클 트리에 넣어서 루트 해시를 얻었다면, 그 해시 값을 만드는 다른 입력은 없다”라고 가정합니다. 하지만 많은 구현에서 이는 사소한 결함 때문에 틀린 가정입니다.

위 예시에서 입력은 L1, L2, L3, L4입니다. 이는 결국 도식 맨 위의 루트 해시 값을 출력합니다. 하지만 그림에서 보듯 중간 레이어의 입력은 이전 레이어의 해시들을 이어 붙인(concatenate) 값입니다. 그러므로 그 두 값을 그대로 머클 트리에 직접 입력으로 주면, 동일한 루트 해시 값을 다시 얻을 수 있습니다.

중요한 점은, 이 공격은 하위 해시 함수 자체에 알려진 보안 취약점이 전혀 없어도 발생할 수 있다는 것입니다. 이는 많은 머클 트리 구성 방식에 내재된 문제입니다.

이는 다음과 같은 예시를 통해 더 명확해집니다.

공격 예시

샘플 코드로 이 공격을 설명하는 대신, 저는 구글에서 “python merkle tree”를 검색하고, 머클 트리 구현이 있는 깃헙 저장소들을 훑어보며 결함을 시연하는 간단한 PoC 코드를 작성했습니다.

첫 번째 예시: https://github.com/JaeDukSeo/Simple-Merkle-Tree-in-Python

먼저 머클 트리 구현과 출력용 json 라이브러리를 임포트합니다. 그리고 MT 객체를 만들고, 일련의 ‘트랜잭션’(데이터 조각)을 할당한 뒤, 그 데이터로 트리를 구성하고 루트 노드를 출력합니다. 또한 트리의 값들을 덤프해 루트 노드에 도달하는 과정을 보여주는 간단한 함수를 작성합니다.

python
import json
from MerkleTrees import Jae_MerkTree

def do_merktree(transactions):
  Jae_Tree = Jae_MerkTree()
  Jae_Tree.listoftransaction = transactions
  Jae_Tree.create_tree()
  past_transaction = Jae_Tree.Get_past_transacion()
  print "final root: %s" % (Jae_Tree.Get_Root_leaf())
  print(json.dumps(past_transaction, indent=4))

이제 서로 다른 세 입력이 이 구현에서 완전히 동일한 해시 값을 출력함을 실제로 보여줍니다.

python
transaction1 = ['a','b','c','d']
transaction2 = ['ca978112ca1bbdcafac231b39a23dc4da786eff8147c4e72b9807785afee48bb3e23e8160039594a33894f6564e1b1348bbd7a0088d42c4acb73eeaed59c009d','2e7d2c03a9507ae265ecf5b5356885a53393a2029d241394997265a1a25aefc618ac3e7343f016890c510e93f935261169d9e3f565436429830faf0934f4f8e4']
transaction3 = ['62af5c3cb8da3e4f25061e829ebeea5c7513c54949115b1acc225930a90154dad3a0f1c792ccf7f1708d5422696263e35755a86917ea76ef9242bd4a8cf4891a']

do_merktree(transaction1)
do_merktree(transaction2)
do_merktree(transaction3)

• transaction1에서는 a, b, c, d 네 값을 입력합니다.
• transaction2에서는 두 값을 입력하는데, 각각이 이전 두 값의 해시를 이어 붙인(concatenate) 값입니다. 예를 들어 hash(a)+hash(b) 와 hash(c)+hash(d) 입니다(여기서 +는 연결을 의미).
• transaction3에서는 이전 레이어에서 출력된 해시들을 이어 붙인 값 하나를 입력합니다.

출력(트리 전체 덤프는 주석 처리한 상태)은 다음과 같습니다:

text
('final root: ', '58c89d709329eb37285837b042ab6ff72c7c8f74de0446b091b6a0131c102cfd')
('final root: ', '58c89d709329eb37285837b042ab6ff72c7c8f74de0446b091b6a0131c102cfd')
('final root: ', '58c89d709329eb37285837b042ab6ff72c7c8f74de0446b091b6a0131c102cfd')

두 번째 예시: https://github.com/Tierion/pymerkletools

이 라이브러리는 pip install merkletools로 설치할 수 있습니다. 아래 코드는 비슷한 흐름이며, 비교적 자명합니다.

python
import merkletools

mt = merkletools.MerkleTools(hash_type='md5')

mt.add_leaf(['a','b','c','d'],True)
mt.make_tree()
print("%s") % (mt.get_merkle_root())

mt.reset_tree()

mt.add_leaf('96e024ba2074fe77e8e965ba43a704be')
mt.add_leaf('c0a594722e66ed5e4dec538fdc1fc1ba')
mt.make_tree()
print("%s") % (mt.get_merkle_root())

이 코드는 다음과 같은 출력을 만듭니다:

text
$ python2 merkletools_demo.py 
ec3b15651156ce266ed7d267d8d43349
ec3b15651156ce266ed7d267d8d43349

서로 다른 두 입력을 트리에 제공했는데도, 동일한 해시 지문이 계산되었습니다.

이 공격의 한계

이 공격이 현실 세계(예: 비트코인)에서 실제로는 종종 큰 문제가 되지 않는 중요한 이유/한계는 다음과 같습니다. 입력 X와 동일한 해시 값을 생성하는 입력 Y를 찾을 수는 있지만, Y의 값이나 심지어 그 **형식(format)**에 대해 공격자는 아무런 통제권이 없습니다. 따라서 머클 트리를 데이터 무결성에 사용하고 있는 애플리케이션 입장에서는, 그 입력이 유용한 방식으로 해석되지 않을 가능성이 큽니다.

이로 인해 가능한 한 가지 공격은 서비스 거부(DoS)입니다. 해시 값이 같다는 이유로 무결성이 보장된다고 믿고 데이터를 덮어쓰거나 교체하는 상황이 발생할 수 있기 때문입니다.

수정 방법

다행히 수정은 꽤 단순합니다. 핵심은 트리에서 리프(leaf) 노드와 중간(intermediate) 노드를 구분하도록, 리프와 중간 노드 해시 입력 앞에 서로 다른 바이트 값을 접두(prefix)로 붙이는 것입니다(예: 인증서 투명성(Certificate Transparency) 구현처럼 0x00과 0x01 사용). 또는 트리 깊이/노드 깊이를 자료구조 일부로 기록해, 공격자가 중간 값을 직접 입력으로 공급할 수 없게 만들 수도 있습니다.