[インデックス 11514] ファイルの概要

このコミットは、Go言語の crypto/elliptic パッケージにおけるP-224楕円曲線実装のバグ修正に関するものです。具体的には、p224Contract 関数がフィールド要素の「最小表現」を生成できない場合があるという問題に対処しています。これにより、約0.02%の確率で不安定な（flakey）失敗が発生していました。

コミット

commit 2cc33511312a68299ced23428365c0fc86c89476
Author: Adam Langley <agl@golang.org>
Date:   Tue Jan 31 12:27:42 2012 -0500

    crypto/elliptic: p224Contract could produce a non-minimal representation.
    
    I missed an overflow in contract because I suspected that the prime
    elimination would take care of it. It didn't, and I forgot to get back
    to the overflow. Because of this, p224Contract may have produced a
    non-minimal representation, causing flakey failures ~0.02% of the
    time.
    
    R=golang-dev, rsc
    CC=golang-dev
    https://golang.org/cl/5592045

GitHub上でのコミットページへのリンク

https://github.com/golang/go/commit/2cc33511312a68299ced23428365c0fc86c89476

元コミット内容

crypto/elliptic: p224Contract could produce a non-minimal representation.

contract 関数でのオーバーフローを見落としていました。素数除去がそれを処理すると考えていましたが、そうではありませんでした。このため、p224Contract は非最小表現を生成する可能性があり、約0.02%の確率で不安定な失敗を引き起こしていました。

変更の背景

このコミットは、Go言語の暗号ライブラリ crypto/elliptic におけるP-224楕円曲線実装の重要なバグを修正するために行われました。P-224曲線は、NIST（米国国立標準技術研究所）によって定義された標準的な楕円曲線であり、TLS/SSL、デジタル署名、鍵交換などの様々な暗号プロトコルで広く利用されています。

問題は、p224Contract と呼ばれる内部関数にありました。この関数は、楕円曲線上の点座標を表現する際に使用される「フィールド要素」を、その「最小表現」（canonical form）に変換する役割を担っています。有限体上の演算では、同じ値を複数の異なる方法で表現できることがありますが、暗号演算の正確性とセキュリティを保証するためには、一意で最小な表現に正規化することが不可欠です。

コミットメッセージによると、開発者は p224Contract 関数内で発生する可能性のあるオーバーフローを見落としていました。当初、素数除去（prime elimination）のロジックがこのオーバーフローを適切に処理すると考えていたようですが、実際にはそうではありませんでした。この見落としにより、p224Contract は時折、フィールド要素の非最小表現を生成してしまい、その結果、楕円曲線上の点の検証（IsOnCurve 関数など）が失敗するという、不安定な（flakey）バグを引き起こしていました。この失敗は稀ではあったものの（約0.02%の確率）、暗号ライブラリにおいては許容できないレベルの信頼性の問題でした。

このバグは、特に楕円曲線上の点の加算や乗算といった演算の後に、結果が曲線上に存在するかどうかを検証する際に顕在化する可能性がありました。非最小表現の点が IsOnCurve 関数に渡されると、数学的には正しい点であるにもかかわらず、内部的な表現の不整合により検証が失敗し、アプリケーションレベルでエラーやクラッシュを引き起こす可能性がありました。

前提知識の解説

楕円曲線暗号 (ECC) の基本

楕円曲線暗号（Elliptic Curve Cryptography, ECC）は、公開鍵暗号の一種であり、有限体上の楕円曲線の数学的特性を利用しています。従来のRSAなどの公開鍵暗号と比較して、同等のセキュリティレベルをより短い鍵長で実現できるため、計算資源や帯域幅が限られた環境（モバイルデバイス、IoTデバイスなど）で広く利用されています。

ECCの基本的な操作は、楕円曲線上の点の加算と、点のスカラ倍（点を自分自身に繰り返し加算すること）です。これらの操作は、特定の有限体（通常は素数体 F_p または二元体 F_{2^m}）上で定義されます。

P-224 曲線とは

P-224は、NIST（National Institute of Standards and Technology）によって定義された標準的な楕円曲線の一つです。これは、素数体 F_p 上で定義されるWeierstrass形式の曲線であり、224ビットのセキュリティレベルを提供します。P-224のような標準曲線は、相互運用性とセキュリティの保証のために、多くの暗号ライブラリやプロトコルで採用されています。

有限体とモジュラ演算

ECCは有限体上で定義されます。有限体とは、要素の数が有限である数学的な集合であり、その上で加算、減算、乗算、除算（ゼロによる除算を除く）が定義されています。暗号学では、特に素数 p を法とする整数環 Z_p（または F_p とも表記）がよく用いられます。

モジュラ演算（剰余演算）は、有限体における基本的な演算です。例えば、「a mod p」は a を p で割った余りを意味します。この演算により、結果は常に 0 から p-1 の範囲に収まります。

「最小表現 (minimal representation)」の重要性

有限体における数値は、モジュラ演算の性質上、複数の表現を持つことができます。例えば、7 mod 5 は 2 ですが、7 や 12 も 5 を法としては 2 と等価です。しかし、暗号アルゴリズムの正確性、効率性、そしてセキュリティを保証するためには、各数値に対して一意の「最小表現」または「正規表現」（canonical representation）を定めることが不可欠です。通常、これは 0 から p-1 の範囲の数値です。

p224Contract のような関数は、計算結果がこの最小表現の範囲に収まるように調整する役割を担います。もし非最小表現の数値が後続の計算や検証に渡されると、数学的には正しい値であっても、比較や検証が失敗する可能性があります。これは、特に楕円曲線上の点が実際に曲線上に存在するかどうかを検証する IsOnCurve 関数のような場所で問題となります。

crypto/elliptic パッケージの役割

Go言語の crypto/elliptic パッケージは、楕円曲線暗号の基本的な操作（点の加算、スカラ倍、点の検証など）を提供する標準ライブラリです。このパッケージは、P-224、P-256、P-384、P-521といったNIST標準曲線を含む、様々な楕円曲線の実装を提供しています。暗号プリミティブとして、TLS、SSH、X.509証明書などの高レベルなプロトコルで利用されます。

技術的詳細

p224Contract 関数の役割と、なぜ「最小表現」が必要なのか

p224Contract 関数は、P-224曲線で使用される224ビットのフィールド要素を、その一意で最小な表現に変換する役割を担っています。P-224曲線は、p = 2^224 - 2^96 + 1 という大きな素数を法とする有限体上で定義されます。この素数は特殊な形式をしており、効率的なモジュラ演算を可能にします。

フィールド要素は、通常、複数の32ビットまたは64ビットの「肢（limb）」に分割して表現されます。P-224の場合、224ビットの数値は7つの32ビットの肢（p224FieldElement は [8]uint32 の配列として定義されていることが多い）で表現されます。p224Contract の目的は、これらの肢がそれぞれ特定の範囲（例えば 0 から 2^28-1）に収まるように、そして全体として 0 から p-1 の範囲の最小値になるように調整することです。

最小表現が必要な理由は以下の通りです。

1. 一意性: 同じ数学的な値が複数のビットパターンで表現されることを防ぎます。これにより、点の比較やハッシュ化が正しく行われます。
2. 正確性: 後続の演算が正しい入力値で実行されることを保証します。非最小表現の入力は、予期せぬオーバーフローやアンダーフローを引き起こし、計算結果を誤らせる可能性があります。
3. セキュリティ: 暗号アルゴリズムは、入力と出力が厳密に定義された形式に従うことを前提としています。非最小表現は、サイドチャネル攻撃の可能性を生み出したり、プロトコルの脆弱性につながる可能性があります。

オーバーフローがどのように発生し、なぜ問題だったのか

P-224のフィールド要素は、複数の uint32 の配列として扱われます。p224Contract 関数は、これらの肢に対してキャリー（繰り上がり）やボロー（借り入れ）を伝播させることで、値を正規化します。

元のコードでは、in[i] < 2**32 という前提で処理が行われていましたが、実際には in[i] < 2**29 というより厳しい制約が必要でした。これは、内部的な計算（特に out[i+1] += out[i] >> 28 のようなビットシフト操作）において、各肢が 2^28 を超える値を持つと、次の肢へのキャリーが適切に処理されず、結果としてオーバーフローが発生する可能性があったためです。

このオーバーフローは、最終的なフィールド要素が p を法とする最小表現の範囲外になることを意味しました。例えば、X mod p が Y であるべきなのに、Y + k*p のような形式で表現されてしまうことがありました。このような非最小表現の点が IsOnCurve 関数に渡されると、IsOnCurve は曲線の方程式 y^2 = x^3 + ax + b (mod p) に点を代入して検証しますが、非最小表現の x や y の値では、方程式が成立しないと判断されてしまうことがありました。これは、数学的には点が存在するにもかかわらず、実装上の問題で検証が失敗するという「不安定な失敗」につながりました。

in[i] < 2**32 から in[i] < 2**29 への変更の意味

p224Contract 関数のコメントが On entry, in[i] < 2**32 から On entry, in[i] < 2**29 に変更されました。これは、関数が期待する入力の各肢の最大値がより厳しくなったことを示しています。

元のコードでは、各肢が uint32 の最大値（2^32 - 1）まで取りうることを想定していましたが、実際には p224Contract の内部ロジック（特に >> 28 のシフト操作とそれに続く加算）が正しく機能するためには、各肢が 2^29 - 1 以下である必要がありました。この変更は、関数の事前条件を正確に反映し、オーバーフローを防ぐための重要なステップです。

追加されたキャリーチェーンのロジックの詳細な説明

修正の核心は、p224.go の p224Contract 関数に追加された新しいキャリーチェーンのロジックです。

	// We might have pushed out[3] over 2**28 so we perform another, partial,
	// carry chain.
	for i := 3; i < 7; i++ {
		out[i+1] += out[i] >> 28
		out[i] &= bottom28Bits
	}
	top = out[7] >> 28
	out[7] &= bottom28Bits

	// Eliminate top while maintaining the same value mod p.
	out[0] -= top
	out[3] += top << 12

	// There are two cases to consider for out[3]:
	//   1) The first time that we eliminated top, we didn't push out[3] over
	//      2**28. In this case, the partial carry chain didn't change any values
	//      and top is zero.
	//   2) We did push out[3] over 2**28 the first time that we eliminated top.
	//      The first value of top was in [0..16), therefore, prior to eliminating
	//      the first top, 0xfff1000 <= out[3] <= 0xfffffff. Therefore, after
	//      overflowing and being reduced by the second carry chain, out[3] <=\
	//      0xf000. Thus it cannot have overflowed when we eliminated top for the
	//      second time.

	// Again, we may just have made out[0] negative, so do the same carry down.
	// As before, if we made out[0] negative then we know that out[3] is
	// sufficiently positive.
	for i := 0; i < 3; i++ {
		mask := uint32(int32(out[i]) >> 31)
		out[i] += (1 << 28) & mask
		out[i+1] -= 1 & mask
	}

このコードブロックは、以前のキャリー伝播処理で発生した可能性のあるオーバーフローを修正するために追加されました。

1. 部分的なキャリーチェーンの再実行:

   • for i := 3; i < 7; i++ { ... } のループは、out[3] から out[7] までの肢に対して、再度キャリー伝播を行います。
   • out[i+1] += out[i] >> 28 は、現在の肢 out[i] の上位4ビット（2^28 を超える部分）を次の肢 out[i+1] に加算します。
   • out[i] &= bottom28Bits は、現在の肢 out[i] を下位28ビットにマスクし、2^28 未満に正規化します。
   • この処理は、特に out[3] が以前の処理で 2^28 を超えてしまった場合に、その影響を適切に伝播させることを目的としています。

2. top の除去:

   • ループ後、out[7] の上位4ビット（>> 28）が top 変数に格納されます。これは、最上位の肢から溢れた部分です。
   • out[7] &= bottom28Bits で out[7] も正規化されます。
   • top の値は、p = 2^224 - 2^96 + 1 の特殊な形式を利用して、モジュロ p の等価性を保ちながら下位の肢に「折り返されます」。
   • out[0] -= top と out[3] += top << 12 は、top を out[0] から減算し、out[3] に top を 2^12 倍して加算することで、top の値をモジュロ p で等価な形で下位の肢に分配します。これは、2^224 mod p が 2^96 - 1 に等しいというP-224の特性を利用した最適化です。top は 2^224 の係数に相当するため、top * 2^224 を top * (2^96 - 1) に置き換えることで、値を小さく保ちます。2^96 は out[3] の位置に相当するため、top << 12 (つまり top * 2^12) が out[3] に加算されます。

3. 負の out[0] の処理:

   • out[0] -= top の結果、out[0] が負になる可能性があります。
   • 最後の for i := 0; i < 3; i++ { ... } ループは、out[0] から out[2] までの肢に対して、負の値になった場合の「借り入れ（borrow）」を伝播させ、正の値に正規化します。
   • mask := uint32(int32(out[i]) >> 31) は、out[i] が負の場合に 0xFFFFFFFF、正の場合に 0x00000000 となるマスクを生成します。
   • out[i] += (1 << 28) & mask は、out[i] が負の場合に 2^28 を加算して正の範囲に戻します。
   • out[i+1] -= 1 & mask は、out[i] が負の場合に次の肢 out[i+1] から 1 を減算し、借り入れを伝播させます。

これらの追加されたロジックにより、p224Contract 関数は、入力されたフィールド要素がどのような状態であっても、確実にその最小表現に変換できるようになりました。

IsOnCurve が失敗する原因となったメカニズム

IsOnCurve(x, y) 関数は、与えられた点 (x, y) が楕円曲線の方程式 y^2 = x^3 + ax + b (mod p) を満たすかどうかを検証します。ここで x と y はフィールド要素です。

バグ修正前は、p224Contract が非最小表現の x や y を生成する可能性がありました。例えば、本来 X であるべきフィールド要素が X + k*p の形で表現されてしまうようなケースです。

IsOnCurve 関数は、内部でフィールド要素に対するモジュラ演算（乗算、加算など）を実行します。これらの演算は、入力が最小表現であることを前提として設計されていることが多く、非最小表現の入力に対しては、中間結果がオーバーフローしたり、最終的な比較が失敗したりする可能性があります。

具体的には、y^2 や x^3 + ax + b の計算結果が、p を法とする最小表現に正規化されないまま比較されると、数学的には等しい値であっても、ビットパターンが異なるために等しくないと判断されてしまうことがありました。これにより、有効な楕円曲線上の点であるにもかかわらず、IsOnCurve が false を返し、「P224 failed to validate a correct point」のようなエラーが発生していました。

コアとなるコードの変更箇所

src/pkg/crypto/elliptic/elliptic_test.go

新しいテストケース TestP224Overflow が追加されました。これは、特定の既知のバグのある点データ（非最小表現を引き起こす可能性があった点）をデコードし、それがP-224曲線上に存在するかどうかを IsOnCurve で検証するものです。このテストは、修正が正しく適用されたことを確認するための回帰テストとして機能します。

--- a/src/pkg/crypto/elliptic/elliptic_test.go
+++ b/src/pkg/crypto/elliptic/elliptic_test.go
@@ -6,6 +6,7 @@ package elliptic
 
  import (
  	"crypto/rand"
+	"encoding/hex"
  	"fmt"
  	"math/big"
  	"testing"
@@ -350,3 +351,13 @@ func TestMarshal(t *testing.T) {
  		return
  	}
  }
+
+func TestP224Overflow(t *testing.T) {
+	// This tests for a specific bug in the P224 implementation.
+	p224 := P224()
+	pointData, _ := hex.DecodeString("049B535B45FB0A2072398A6831834624C7E32CCFD5A4B933BCEAF77F1DD945E08BBE5178F5EDF5E733388F196D2A631D2E075BB16CBFEEA15B")
+	x, y := Unmarshal(p224, pointData)
+	if !p224.IsOnCurve(x, y) {
+		t.Error("P224 failed to validate a correct point")
+	}
+}

src/pkg/crypto/elliptic/p224.go

p224Contract 関数のコメントが更新され、入力の各肢の制約が in[i] < 2**32 から in[i] < 2**29 に変更されました。 そして、オーバーフローを適切に処理し、フィールド要素を確実に最小表現に正規化するための新しいキャリー伝播ロジックが追加されました。

--- a/src/pkg/crypto/elliptic/p224.go
+++ b/src/pkg/crypto/elliptic/p224.go
@@ -341,7 +341,7 @@ func p224Invert(out, in *p224FieldElement) {
 
  // p224Contract converts a FieldElement to its unique, minimal form.
  //
-// On entry, in[i] < 2**32
+// On entry, in[i] < 2**29
  // On exit, in[i] < 2**28
  func p224Contract(out, in *p224FieldElement) {
  	copy(out[:], in[:])
@@ -365,6 +365,39 @@ func p224Contract(out, in *p224FieldElement) {
  		out[i+1] -= 1 & mask
  	}\n
+	// We might have pushed out[3] over 2**28 so we perform another, partial,
+	// carry chain.
+	for i := 3; i < 7; i++ {
+		out[i+1] += out[i] >> 28
+		out[i] &= bottom28Bits
+	}
+	top = out[7] >> 28
+	out[7] &= bottom28Bits
+
+	// Eliminate top while maintaining the same value mod p.
+	out[0] -= top
+	out[3] += top << 12
+
+	// There are two cases to consider for out[3]:
+	//   1) The first time that we eliminated top, we didn't push out[3] over
+	//      2**28. In this case, the partial carry chain didn't change any values
+	//      and top is zero.
+	//   2) We did push out[3] over 2**28 the first time that we eliminated top.
+	//      The first value of top was in [0..16), therefore, prior to eliminating
+	//      the first top, 0xfff1000 <= out[3] <= 0xfffffff. Therefore, after
+	//      overflowing and being reduced by the second carry chain, out[3] <=\
+	//      0xf000. Thus it cannot have overflowed when we eliminated top for the
+	//      second time.
+
+	// Again, we may just have made out[0] negative, so do the same carry down.
+	// As before, if we made out[0] negative then we know that out[3] is
+	// sufficiently positive.
+	for i := 0; i < 3; i++ {
+		mask := uint32(int32(out[i]) >> 31)
+		out[i] += (1 << 28) & mask
+		out[i+1] -= 1 & mask
+	}
+
  	// Now we see if the value is >= p and, if so, subtract p.
  
  	// First we build a mask from the top four limbs, which must all be

コアとなるコードの解説

src/pkg/crypto/elliptic/elliptic_test.go の変更

func TestP224Overflow(t *testing.T) {
	// This tests for a specific bug in the P224 implementation.
	p224 := P224() // P-224曲線オブジェクトを取得
	// 特定の点データを16進数文字列からバイトスライスにデコード
	pointData, _ := hex.DecodeString("049B535B45FB0A2072398A6831834624C7E32CCFD5A4B933BCEAF77F1DD945E08BBE5178F5EDF5E733388F196D2A631D2E075BB16CBFEEA15B")
	// バイトスライスから楕円曲線上の点(x, y)をアンマーシャル（デコード）
	x, y := Unmarshal(p224, pointData)
	// アンマーシャルされた点(x, y)がP-224曲線上に存在するかどうかを検証
	if !p224.IsOnCurve(x, y) {
		// 存在しない場合、テストを失敗させる
		t.Error("P224 failed to validate a correct point")
	}
}

このテストは、以前のバグによって IsOnCurve が誤って false を返す可能性があった特定の点に対して、修正後に正しく true を返すことを確認します。Unmarshal 関数は、圧縮または非圧縮形式の点データを (x, y) 座標に変換します。このテストが成功することは、p224Contract が正しく機能し、Unmarshal が生成する点が IsOnCurve によって正しく検証されることを意味します。

src/pkg/crypto/elliptic/p224.go の p224Contract 関数の変更

// On entry, in[i] < 2**29
// On exit, in[i] < 2**28
func p224Contract(out, in *p224FieldElement) {
	copy(out[:], in[:]) // 入力 'in' を 'out' にコピーして作業を開始

	// ... (既存のキャリー伝播ロジック) ...

	// We might have pushed out[3] over 2**28 so we perform another, partial,
	// carry chain.
	for i := 3; i < 7; i++ {
		out[i+1] += out[i] >> 28 // out[i]の上位4ビットをout[i+1]に加算（キャリー）
		out[i] &= bottom28Bits   // out[i]を下位28ビットにマスク（正規化）
	}
	top = out[7] >> 28       // out[7]から溢れた最上位のキャリーを取得
	out[7] &= bottom28Bits   // out[7]を正規化

	// Eliminate top while maintaining the same value mod p.
	// topの値をモジュロpで等価な形で下位の肢に分配
	out[0] -= top        // out[0]からtopを減算
	out[3] += top << 12  // out[3]にtopを2^12倍して加算 (P-224の特殊な素数形式を利用)

	// There are two cases to consider for out[3]:
	// ... (コメントによる詳細な説明) ...

	// Again, we may just have made out[0] negative, so do the same carry down.
	// As before, if we made out[0] negative then we know that out[3] is
	// sufficiently positive.
	for i := 0; i < 3; i++ {
		mask := uint32(int32(out[i]) >> 31) // out[i]が負の場合にマスクを生成
		out[i] += (1 << 28) & mask          // out[i]が負の場合、2^28を加算して正の範囲に戻す
		out[i+1] -= 1 & mask                 // out[i]が負の場合、out[i+1]から1を減算（借り入れ）
	}

	// ... (既存の最終的なpとの比較と減算ロジック) ...
}

この追加されたコードブロックは、以前のキャリー伝播処理で発生した可能性のあるオーバーフローを修正し、フィールド要素が確実に最小表現に正規化されるようにします。特に、out[3] のオーバーフローの可能性に対処し、最上位のキャリー top をP-224の素数の特性を利用して下位の肢に適切に分配します。また、out[0] が負になった場合の借り入れ処理も行い、全ての肢が正しい範囲に収まるようにします。これにより、p224Contract は常に正確な最小表現を生成し、IsOnCurve などの後続の検証関数が正しく機能するようになります。

関連リンク

• Go言語 crypto/elliptic パッケージのドキュメント: https://pkg.go.dev/crypto/elliptic
• NIST FIPS 186-4 (Digital Signature Standard): https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf (P-224曲線を含むNIST標準曲線が定義されています)
• 楕円曲線暗号の基礎 (Wikipedia): https://ja.wikipedia.org/wiki/%E6%A5%95%E5%86%86%E6%9B%B2%E7%B7%9A%E6%9A%97%E5%8F%B7

参考にした情報源リンク

• Go言語のコミット履歴 (GitHub): https://github.com/golang/go/commits/master
• Go言語のコードレビューシステム (Gerrit): https://go.dev/cl/5592045 (コミットメッセージに記載されているCLリンク)
• 楕円曲線暗号に関する一般的な情報源 (例: Wikipedia, Cryptography Stack Exchangeなど)
• 有限体とモジュラ演算に関する数学的資料