SHA-256 충돌은 왜 발견되지 않았을까?

SHA-1 함수는 2005년에 단순 충돌 쌍이 발견되었다.
출처: SHA-1#Cryptanalysisandvalidation

2017년에는 구글 연구팀에 의해 실생활에서 활용될 여지가 있는 real world attack이 발견되었다. 아래 웹 페이지에서 제공하는 두 개의 PDF 파일은 전혀 다른 내용을 담고 있지만 동일한 SHA-1 다이제스트를 갖는다.
출처: https://shattered.io

구글 연구팀은 충돌을 찾기 위해 2년에 걸쳐 9.2 * 10^18 번의 SHA-1 계산을 수행했다고 한다. 이를 위해 shattered 공격법이 사용되었으며, 매우 오랜 시간과 컴퓨팅 자원이 필요한 작업이지만 이조차도 브루트 포스에 비하면 100,000배 빠른 수치라고 한다.
시간이 흐를수록 컴퓨팅 성능이 향상되어 공격 비용이 감소한다고는 하지만 여전히 매우 많은 비용과 시간이 필요한 것은 사실이다.
출처: https://security.googleblog.com

SHA-256도 단순 충돌 쌍 정도는 발견되지 않았을지 궁금하여 찾아보니 아직 충돌이 발견되지 않았다는 사실을 알게되었다.
구글 정도 되는 기업이 뚝딱뚝딱(?) 몇년쯤 고생하면 충돌을 발견할 수 있는거 아닌가 하는 의구심이 들어 이것저것 검색해보던 중 스택 익스체인지에서 재미난 글을 읽게 되었다.

256 비트는 얼마나 큰 숫자일까?

SHA-256은 256 비트 길이의 출력 값을 생성한다. 따라서 이론적으로는 (2^256 + 1)개의 서로 다른 숫자를 SHA-256에 대입하면 충돌 쌍이 발견될 것이다.
2021년 9월 기준, 비트코인 네트워크는 초당 대략 1.2 * 10^20번의 SHA-256 계산을 수행하고 있다. 이 속도라면 4.0 * 10^86 년 쯤 후에 2^256 번의 해시 계산을 하게 된다. 비트코인 네트워크를 동원할 수 있는 누군가가 존재한다면 4.0 ^ 10^86 년 후에 해시 충돌을 발견할 수 있다는 뜻이다.
출처 - 비트코인 해시 레이트: https://ycharts.com/indicators/bitcoinnetworkhash_rate
출처 - Why haven't any SHA-256 collisions been found yet?: https://crypto.stackexchange.com/a/47810

또 다른 스택 익스체인지 질문 글에 따르면 브루트 포스 공격을 위해서 2011년 전세계 총 생산(Gross World Product)의 10^44배에 달하는 전기세를 지불해야 한다고 한다. 전기세 뿐만 아니라 해시 값 비교를 위해 2^256 개의 문자열을 기록할 스토리지 와 컴퓨팅 자원도 필요하다.
출처: https://crypto.stackexchange.com/a/1147

열역학 관점에서 256 비트 키에 대한 브루트 포스 공격이 아예 불가능하다는 의견도 존재한다. 무슨 말인지 전혀 이해가 되지 않지만 그렇다고 한다(…)
출처: https://crypto.stackexchange.com/a/1160