HackingCrypto

왜 SHA-1 인증서 위조가 해시 충돌보다 어려울까?

SHA-1

SHA-1 (Secure Hash Algorithm 1)

SHA-1은 2005년부터 이론적 공격에 취약한 것으로 알려져 NIST에서 2013년 이후 보안 취약성 문제로 사용금지된 해시 알고리즘이다.
2017년, 이론적으로만 취약하다고 알려진 충돌 가능성에 대해 네덜란드 암스테르담의 CWI 연구소와 Google의 공동 프로젝트로 SHA-1 충돌쌍을 찾는 기술을 개발하는데 성공했다. (http://shattered.io 참조)
여러 웹 사이트에서 SHA-1을 이용한 인증서를 사용하고 있었기에 꽤나 큰 파장을 일으킬 수 있었을 것 같지만, 해시 충돌을 찾는 것과 디지털 인증서를 위조하는 것은 조금 달랐다. chosen-prefix collision attack이 의미있는 시간안에 가능한것 까지 찾은것이 아니였기 때문이였다.

Chosen-prefix collision attack

Mathematically stated, given two different prefixes p1, p2, the attack finds two appendages m1 and m2 such that hash(p1 ∥ m1) = hash(p2 ∥ m2) (where ∥ is the concatenation operation).
(Wikipedia)

기존의 악의적인 인증서를 만들기 위해 풀어야 했던 문제는 H(M1) = H(M2) 가 되도록 M1, M2 값을 찾는것이었지만, 이미 알려진 값인 P1과 P2를 이용해서 H(P1 | S1) = H(P2 | S2)인 S1, S2값을 찾는 것이라는 것으로 문제를 바꾼 것이다.
계산 복잡도가 획기적으로 줄게되는 이 방법을 통해 공격자는 동일한 해시값을 가진 두 개의 인증서를 만들 수 있게 되었다.

우선 X.509 인증서의 구조를 간략하게 살펴보자면 이렇다.

1
2
3
4
5
6
[   Serial number  ]
[  Validity period ]
[    Domain name   ]
[     Public key   ]
[ X.509 extensions ]
[     Signature    ]

위의 공격 방법을 적용하기 위해서 P1과 P2가 아래와 같다고 할 때, 이제는S1과 S2만 계산하면 된다.

1
2
P1 = Serial number | Validity period | real domain name
P2 = Serial number | Validity period | forged domain name

[그림 1] X.509 chosen-prefix attack

S1, S2값을 계산하는데 성공했다면, 공격자는 CA에게 정확한 Serial number를 가진 인증서를 정확한 시간에 검증 가능한 도메인과 Collision Bits에 해당하는 공개 키로 발급해야 한다.
발급에 성공한다면 해시값이 동일한 악의적인 인증서를 얻을 수 있다.

간단히 말해서, attacker.com 을 소유하고 있는 공격자가 공격타겟을 google.com 으로 정했다면,
적당히 Serial number와 Validity period를 예측하여 P1, P2를 정한다.

1
2
P1 = Serial number | Validity period | attacker.com
P2 = Serial number | Validity period | google.com

S1, S2값을 성공적으로 알아낸다면, 준비가 완료된 것이다. CA에게 공격자가 현재 소유하고 있는 attacker.com 의 인증서 P1 | S1를 서명해달라고 요청한다. 성공적으로 예측한 것과 동일한 Serial number, Validity period를 가진상태로 인증서가 발급 되었다면, 이 인증서의 Signature에 해당하는 부분을 제외한 윗부분을 위에서 생성한 google.com 인증서 P2 | S2로 바꿔치기 하면 악의적인 인증서가 만들어진다.

SHA-1 chosen-prefix attack에 관한 논문

글을 쓸겸 찾아보니 이미 chosen-prefix collision attack에 대해 논문이 나오고 있었다.

결론

  • 인증서 위조에 사용되는 chosen-prefix collision attack 이라는게 가능해야 했다.
  • chosen-prefix collision attack을 이용해야 계산 복잡도가 획기적으로 줄어들기 때문이다.
  • SHA-1은 수명을 다했다.

Reference

Share