Goのcrypto/dsa脆弱性（CVE-2016-3959）の概要

Alex Mullins

2016年4月9日

---

はじめに

最近、Goプログラミング言語用のDigital Signature Algorithm（DSA）暗号ライブラリにバグが発見されました。この記事では、このバグの詳細と、攻撃者がこれを利用して、クライアント認証に基礎となる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関数の後半にあるステートメントの1つで無限ループが発生します。

少し寄り道してDSAを説明します。DSAは、非対称暗号を使用してメッセージに署名するデジタル署名アルゴリズムであり、署名は後でメッセージが実際に送信者/秘密鍵の保持者によって送信されたことを保証するために使用できます。簡単な例として、アリスがボブに昼食をどこでいつ会うかを伝えるメッセージを送信するとします。しかしボブは、メッセージを送信したのが本当にアリスであり、他の誰かではないことを確認したいと考えています。これを機能させるには、アリスは自分の秘密鍵でメッセージに署名し、ボブは知っているアリスの公開鍵でアリスの署名を検証できます。秘密鍵の保持者以外は、対応する公開鍵で検証できるメッセージに署名できません（少なくともこれが基本的な考え方です）。

動作には、DSAは5つの大きな数値を必要とします。最初の3つの数値はDSAパラメータP、Q、Gとして知られています。これらは基盤となるグループとグループジェネレータを定義します。これらの数値は、dsa.GenerateParameters()の呼び出しで適切に作成できます。

type Parameters struct {
        P, Q, G *big.Int
}

DSAに必要な残りの2つの数値は、秘密鍵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 またはWikipediaのページ：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の場合に剰余演算なしで累乗計算を行うことを指定していることがわかります。大きな数値をもう1つの大きな数値で累乗すると、結果も非常に大きな数値になります。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桁の10進数」があります。（注：Wolfram AlphaのWeb入力ボックスには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(&params, 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

この最後のテスト呼び出しはハングすることに注意してください。

悪用

これを誰かが悪用するにはどうすればよいでしょうか？攻撃者が何らかの方法でサーバーに不正なDSA鍵を受け入れさせ、署名のVerifyに使用させることができれば、サーバーを大きな累乗計算問題の処理に陥らせて、サービス拒否（DOS）を引き起こすことができます。SSHはクライアント認証プロトコルで署名方式としてDSAを使用するため、このエクスプロイトを試すのに最適なサーバー候補と思われます。これが発生し得るシナリオを想像してみましょう。