비트코인 머클 트리 알고리즘의 취약점과 우회방안

비트코인 마이너는 블록에 포함될 트랜잭션들의 머클 루트를 계산하여 블록 헤더에 넣고 블록을 생성합니다. 다른 비트코인 풀 노드들은 블록 헤더의 머클 루트가 스스로 계산한 머클 루트와 같은지 비교하여 해당 블록의 유효성을 검사합니다.

머클 루트는 세부적인 구현에서 약간씩 차이가 나는데, 비트코인은 각 라운드의 해시가 홀수 개이면 마지막 해시를 한 번 중복해서 넣는 방식으로 짝수로 만들고 계산을 합니다. 일례로 1 2 3 해시의 머클 루트를 계산하기 위해서는 1 2 해시를 합쳐서 A를 만들고 남은 해시가 홀수 개니 3을 하나 더 추가해서 3 3 해시를 합쳐서 B를 만드는 방식입니다. 그런 다음 A B를 합쳐서 해시를 계산하면 머클 루트가 나옵니다.

그런데 이런 방식으로 머클 루트를 만들면 트랜잭션을 중복해서 넣는 방식으로 머클 루트가 같은 블록을 쉽게 만들어 낼 수 있는 문제가 있습니다. 예를 들어, 아래 그림처럼 1 2 3 4 5 6 해시의 머클 루트가 A라고 하면 5 6해시를 중복해서 한 번 더 넣은 1 2 3 4 5 6 5 6의 머클 루트도 A가 됩니다. 다음 라운드에서 F가 하나인 것과 F가 두 개인 것이 해시 값이 C로 동일하기 때문입니다.

누군가가 고의로 머클 루트는 같지만 validation이 실패하는 블록을 고의로 보내게 되면, 이 블록을 받은 노드는 이후 정상적인 블록을을 invalid하다고 판단하게 되므로 심각한 DoS 공격이 가능해집니다.

비트코인 이 문제를 인지하고 해시 목록의 마지막에 두 개의 동일한 해시가 나오는 경우를 머클 루트가 invalid한 것과 동일하게 취급하는 방법으로 우회하고 있습니다. (호환성 때문에 머클 트리 알고리즘을 바꿀 수는 없었습니다.) 1 2 3 4 5 6 5 6의 경우 해시를 계산하고 나면 D E F F가 나오는데 마지막에 F가 2번 나오므로 invalid하다고 판단하는 방식입니다.

이는 머클 트리 구현 편의를 위해 선택한 간단한 구현 세부사항이 어떤 식으로 보안 문제를 일으킬 수 있는지를 보여주는 아주 좋은 예입니다. 참고로 이 문제는 CVE-2012-2459로 리포트되어 있습니다.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s