Hash Collision

Hash Collision이란 무엇인가?

Hash Collision은 두 개의 다른 입력이 동일한 해시 출력 값을 만들어 내는 현상입니다. 같은 디지털 자물쇠를 열 수 있는 두 개의 서로 다른 열쇠를 상상해 보세요. 드문 일이지만 잘못된 알고리즘으로 발생하면 문제가 됩니다.

Hash Collision의 작동 원리

해시를 큰 데이터에 대한 작은 라벨로 생각해 보세요. 입력에서 결과로의 간단한 여정은 이렇습니다.

1. Input: 아무 메시지, 파일, 트랜잭션으로 시작합니다.
2. Hash: 암호학적 해시 함수의 계열에서 기능이 그 입력을 고정 길이 문자열로 바꿉니다.
3. Clash: 출력은 제한되어 있지만 입력은 무한하므로 두 개의 서로 다른 입력이 같은 출력으로 매핑될 수 있습니다.
4. Attack: 심각한 위협은 누군가 의도적으로 두 입력을 만들어 충돌하도록 한 뒤, 이를 서로 바꿔 치환하는 경우입니다.
5. Defense: 좋은 알고리즘은 그런 탐색을 천문학적으로 비싸게 만들어 무작위 추측에 시간과 비용이 들도록 합니다.

그런 아이디어입니다.

왜 Hash Collision이 중요한가

수학과 코드의 이 조용한 부분에 대해 왜 신경 써야 할까요?

• 혜택: 강한 저항은 데이터 라벨을 고유하게 유지해 주어, 교묘한 트릭의 여지를 줄여줍니다.
• 관점: 충돌은 블록체인 기술, 소프트웨어 업데이트, 파일 검증 등에서 무결성을 위협합니다.
• 관련성: 해시 동등성을 신뢰하는 지갑, 거래소, 증명 및 감사 도구에서 이를 만날 수 있습니다.

Hash Collision의 주요 특징

이 현상을 특별하고 정신적으로 기억해 둘 만한 이유는 무엇일까요:

• 필연적: 유한한 출력과 무한한 입력으로 인해 페이징 구두자 원리에 의해 어떤 쌍은 충돌합니다.
• 어려움: 현대 해시의 경우 의도적으로 충돌을 찾는 것은 계산적으로 가혹하게 설계되어 있습니다.
• 서명: 많은 디지털 서명이 해시에 서명하므로, 충돌 저항은 서명자에 대한 속임수 메시지를 방지합니다.

Hash Collision은 어떻게 계산되나요?

생일 이론으로 노력을 추정할 수 있습니다. k 비트 해시에 대해 약 50%의 확률로 충돌이 발생할 수 있는 무작위 시도 수는 대략 sqrt(2^k) 곱하기 약 1.1774 정도입니다.

n_fifty_percent ≈ 1.1774 * sqrt(2^k)

예: k가 256일 때 필요한 시도 수는 상상할 수 없을 만큼 커서, 충돌까지 브루트 포스하는 것은 주말 프로젝트가 아닙니다.

Variations

연구와 공격에서 다양한 변형이 나타납니다:

• Collision: 두 개의 서로 다른 입력이 같은 해시를 공유합니다.
• Second: 하나의 입력이 주어지면 그 해시와 일치하는 다른 입력을 찾습니다.
• Preimage: 해시가 주어지면 이를 매핑하는 임의의 입력을 찾습니다.
• Prefix: 선택된 접두사 충돌은 서로 다른 시작 값을 가진 두 메시지가 같은 해시로 끝나게 만듭니다.

예시

공격자가 동일한 txid를 가진 두 개의 서로 다른 트랜잭션을 만들어낼 수 있다면, 서명 후 쌍둥이를 서로 바꿔서 이중 지출 트릭을 시도할 수 있습니다.

재미있는 사실

MD5 충돌은 수십 년 전 이미 입증되었고, SHAttered 프로젝트는 두 개의 서로 다른 PDF로 공개 SHA-1 충돌을 만들어 업계가 이를 단종하도록 촉발했습니다.

Wrap-Up

한 줄로 요약하면, Hash Collision은 서로 다른 두 입력이 하나의 디지털 지문을 공유하는 드문 사례이며, 현대 암호 기술은 이를 그저 퀴즈 정도로만 남기지 않도록 열심히 작동합니다.