alexmullins/dsaCVE-2016-3959 분석 및 Go SSH 서버에 대한 개념 증명 공격
Alex Mullins
2016년 4월 9일
최근 Go 프로그래밍 언어용 DSA(Digital Signature Algorithm) 암호 라이브러리에서 버그가 발견되었습니다. 이 글에서는 버그의 세부 내용과 공격자가 이를 이용하여 기본 DSA 라이브러리를 사용해 클라이언트를 인증하는 표준 Go SSH 서버에 대해 서비스 거부 공격을 시작할 수 있는 방법을 살펴보겠습니다.
이 취약점에 대한 첫 번째 언급은 Open Source Security(oss-sec) 메일링 리스트의 http://seclists.org/oss-sec/2016/q2/11 게시물에 나타났습니다.
Go는 여러 큰 정수 루틴에 무한 루프가 있어 Go 프로그램이 원격 서비스 거부 공격에 취약합니다. HTTPS 클라이언트 인증 또는 Go ssh 서버 라이브러리를 사용하는 프로그램은 모두 이 취약점에 노출됩니다. 이 문제는 다음 CL에서 해결되고 있습니다: https://golang.org/cl/21533
-- Jason Buberel
요약하자면, 이 취약점이 악용되면 기본 BigNum 라이브러리 코드에서 무한 루프가 발생할 수 있습니다. 이는 CPU와 메모리 측면에서 시스템 리소스를 소모하여 결국 프로그램이나 시스템 자체가 응답하지 않게 만들 수 있습니다.
위 진술은 SSH와 HTTPS 클라이언트 인증이 모두 영향을 받는다고 말하지만, Go의 crypto/tls 및 net/http 패키지를 살펴본 후에는 이는 부정확해 보입니다. HTTPS 클라이언트 인증은 RSA 또는 ECDSA 서명 체계를 사용할 수 있지만 DSA는 사용할 수 없습니다. 아래를 참조하십시오. 이 부분이 틀렸다면 알려주시기 바랍니다.
https://golang.org/pkg/crypto/tls/#Certificate
type Certificate struct {
Certificate [][]byte
// PrivateKey contains the private key corresponding to the public key
// in Leaf. For a server, this must implement crypto.Signer and/or
// crypto.Decrypter, with an RSA or ECDSA PublicKey. For a client
// (performing client authentication), this must be a crypto.Signer
// with an RSA or ECDSA PublicKey.
PrivateKey crypto.PrivateKey
... other fields
}
oss-sec 메일링 리스트에 해당 게시물이 올라온 지 얼마 지나지 않아 CVE 번호 CVE-2016-3959가 발급되었습니다. Go 관리자들은 이에 대한 수정 사항을 준비했으며, 2016년 4월 13일 수요일에 출시될 버전 1.5.4 및 1.6.1에 포함될 예정입니다. https://groups.google.com/forum/#!topic/golang-nuts/MmSbFHLPo8g
이 글의 코드 샘플을 따라하려면 Go 버전 1.6이 설치되어 있어야 합니다. https://golang.org/doc/install의 지침을 따르십시오. 이 문서와 코드 샘플을 다운로드하려면 Git도 설치되어 있어야 합니다. https://git-scm.com/book/en/v2/Getting-Started-Installing-Git의 지침을 따르십시오. 저장소를 클론하려면 터미널에서 다음 명령을 실행하십시오:
$ go get github.com/alexmullins/dsa
이 명령은 저장소를 Go 작업 공간에 클론합니다.
다음 섹션에서는 취약점의 세부 사항을 다룹니다.
그렇다면 정확히 무엇이 잘못되었을까요? 이에 답하려면 oss-sec 메일링 리스트의 원래 발표로 돌아가야 합니다. 문제에 대한 일반적인 설명과 https://golang.org/cl/21533의 코드 수정 링크 외에는 많은 정보가 없습니다. 해당 변경 사항의 커밋 메시지에는 다음이 포함되어 있습니다:
crypto/dsa: 유효하지 않은 PublicKey를 조기에 제거
PublicKey.P == 0인 경우 Verify가 실패합니다. 시도조차 하지 마십시오.
--- Robert Griesemer
그리고 수정된 코드:
https://github.com/golang/go/blob/master/src/crypto/dsa/dsa.go#L247
// Verify verifies the signature in r, s of hash using the public key, pub. It
// reports whether the signature is valid.
//
// Note that FIPS 186-3 section 4.6 specifies that the hash should be truncated
// to the byte-length of the subgroup. This function does not perform that
// truncation itself.
func Verify(pub *PublicKey, hash []byte, r, s *big.Int) bool {
// FIPS 186-3, section 4.7
// Code fix added to check if the key parameters are sensible.
if pub.P.Sign() == 0 {
return false
}
if r.Sign() < 1 || r.Cmp(pub.Q) >= 0 {
return false
}
if s.Sign() < 1 || s.Cmp(pub.Q) >= 0 {
return false
}
w := new(big.Int).ModInverse(s, pub.Q)
n := pub.Q.BitLen()
if n&7 != 0 {
return false
}
z := new(big.Int).SetBytes(hash)
u1 := new(big.Int).Mul(z, w)
u1.Mod(u1, pub.Q)
u2 := w.Mul(r, w)
u2.Mod(u2, pub.Q)
v := u1.Exp(pub.G, u1, pub.P)
u2.Exp(pub.Y, u2, pub.P)
v.Mul(v, u2)
v.Mod(v, pub.P)
v.Mod(v, pub.Q)
return v.Cmp(r) == 0
}
위의 커밋 메시지와 코드 수정을 요약하면 다음과 같습니다: Go 1.6 및 이전 버전에서 crypto/dsa 패키지의 Verify 함수에 버그가 있습니다. 누군가 공개 키 매개변수 P를 0으로 설정하여 Verify를 호출하면 Verify 함수의 더 아래에 있는 명령문 중 하나에서 무한 루프가 발생합니다.
잠시 DSA를 설명하겠습니다. DSA는 비대칭 암호화를 사용하여 메시지에 서명하고, 나중에 메시지가 실제로 송신자/개인 키 소유자에 의해 전송되었음을 보장하는 데 사용할 수 있는 디지털 서명 알고리즘입니다. 간단한 예로, Alice가 Bob에게 점심을 어디서 언제 만날지 알려주는 메시지를 보냅니다. Bob은 메시지가 Alice가 보낸 것이 확실하기를 원하며 다른 사람이 보낸 것이 아님을 확인하려 합니다. 이를 위해 Alice는 자신의 개인 키로 메시지에 서명하고, Bob은 Bob이 알고 있는 Alice의 공개 키로 Alice의 서명을 확인할 수 있습니다. 개인 키 소유자 외에는 누구도 해당 공개 키로 확인할 수 있는 메시지에 서명할 수 없습니다(적어도 그런 개념입니다).
DSA가 작동하려면 5개의 큰 숫자가 필요합니다. 처음 3개의 숫자는 DSA 매개변수 P, Q, G로 알려져 있습니다. 이들은 기본 그룹과 그룹 생성기를 정의합니다. 이 숫자들은 dsa.GenerateParameters()를 호출하여 올바르게 생성할 수 있습니다.
type Parameters struct {
P, Q, G *big.Int
}
DSA에 필요한 마지막 두 숫자는 개인 키 X와 이에 해당하는 공개 키 Y입니다. 이 숫자들도 dsa.GenerateKey()를 호출하여 생성할 수 있습니다.
type PrivateKey struct {
PublicKey
X *big.Int
}
type PublicKey struct {
Parameters
Y *big.Int
}
이것이 DSA에 대해 알아야 할 전부입니다. 자세한 내용은 NIST 표준(http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf) 또는 위키피디아 페이지(https://en.wikipedia.org/wiki/Digital_Signature_Algorithm)를 참조하십시오.
다시 주제로 돌아와서, Verify 함수의 무한 루프는 어디에 있을까요? 조금 더 파고들면 코드가 다음에서 멈추는 것을 발견할 수 있습니다:
v := u1.Exp(pub.G, u1, pub.P)
Exp() 메서드의 주석입니다:
// Exp sets z = x**y mod |m| (i.e. the sign of m is ignored), and returns z.
// If y <= 0, the result is 1 mod |m|; if m == nil or m == 0, z = x**y.
// See Knuth, volume 2, section 4.6.3.
func (z *Int) Exp(x, y, m *Int) *Int {
위에서 m == 0일 때 모듈러 축소 없이 지수 연산을 수행한다는 주석을 볼 수 있습니다. 큰 숫자를 가져와 다른 큰 숫자로 지수 연산을 하면 결과도 정말 큰 숫자가 됩니다. math/big이 어떻게 작동하는지 잘 알지는 못하지만, 여기서 일어나는 일이라고 생각합니다. Exp()는 완료하는 데 매우 오랜 시간이 걸리는(사실상 무한대나 마찬가지인) 이 지수 연산을 열심히 처리하고 있습니다.
아래 테스트 코드에서 수집한 dsa.Verify() 호출에서 Exp()에 사용되는 샘플 숫자는 다음과 같습니다:
x = 87134495734400160760614045850064869082246125869475484226357302998590334523718907040547736115253396811403341841812955872027275698952059512800196447089300992352859585665865224989740
07948775031938554271780506269767106717359222697821209685947889925442133804051298762702245652821695254167558015585995918548052076 (307 digits)
y = 751336012463178371212581620103057049388105279629 (48 digits)
z = x ^ y
Wolfram Alpha를 사용하면 이 숫자 z가 얼마나 큰지 가늠할 수 있습니다. 결과 숫자 z에는 "113406800566837208055789635448879116719378036793444 자릿수(1.13407x10^50 자릿수)"가 있습니다. (참고: Wolfram Alpha 웹 입력 상자에서 x의 처음 150자리만 y의 거듭제곱으로 사용할 수 있었으므로 실제 자릿수는 더 많습니다!) 규모를 감 잡기 위해: 과학자들은 우주의 원자 수를 10^78에서 10^82 사이로 추정합니다http://www.universetoday.com/36302/atoms-in-the-universe/.
DSA 서명/검증 예제 테스트:
func generatePrivKey(t *testing.T) *dsa.PrivateKey {
// Create the DSA parameters
params := dsa.Parameters{}
err := dsa.GenerateParameters(¶ms, rand.Reader, dsa.L1024N160)
if err != nil {
t.Fatalf("failed to generate dsa parameters: %v", err)
}
// Create the DSA private/public keys
priv := new(dsa.PrivateKey)
priv.Parameters = params
err = dsa.GenerateKey(priv, rand.Reader)
if err != nil {
t.Fatalf("failed to generate dsa keys: %v", err)
}
return priv
}
func TestDSASignature(t *testing.T) {
var message = "Hello brave new world!"
var hash = sha1.Sum([]byte(message))
var err error
priv := generatePrivKey(t)
// Sign a message
r, s, err := dsa.Sign(rand.Reader, priv, hash[:])
if err != nil {
t.Fatalf("failed to sign message: %v", err)
}
if !dsa.Verify(&priv.PublicKey, hash[:], r, s) {
t.Fatalf("failed to verify message: %v", err)
}
}
$ go test
PASS
ok github.com/alexmullins/dsa 0.224s
P를 0으로 설정하는 예제 테스트:
func TestDSAPanic(t *testing.T) {
flag.Parse()
if !*fail {
t.Skip()
}
var message = "Hello brave new world!"
var hash = sha1.Sum([]byte(message))
var err error
priv := generatePrivKey(t)
// Sign a message
r, s, err := dsa.Sign(rand.Reader, priv, hash[:])
if err != nil {
t.Fatalf("failed to sign message: %v", err)
}
// Set P = 0
priv.P = new(big.Int).SetInt64(0)
if !dsa.Verify(&priv.PublicKey, hash[:], r, s) {
t.Fatalf("failed to verify message: %v", err)
}
}
$ go test -fail
이 마지막 테스트 호출이 멈추는 것을 확인하십시오.