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

このコミットは、Go言語の標準ライブラリである crypto/dsa および crypto/ecdsa パッケージにおける、デジタル署名アルゴリズムのセキュリティ強化に関する変更です。具体的には、楕円曲線デジタル署名アルゴリズム (ECDSA) およびデジタル署名アルゴリズム (DSA) の署名生成プロセスにおいて、モジュラ逆元計算にフェルマーの小定理に基づく手法を導入することで、タイミング攻撃に対する耐性を向上させています。

コミット

commit f23d3ea85afce3c4940bcf55889625d2e2017128
Author: Adam Langley <agl@golang.org>
Date:   Tue Apr 8 16:32:48 2014 -0700

    crypto/(ec)dsa: use Fermat's inversion.
    
    Now that we have a constant-time P-256 implementation, it's worth
    paying more attention elsewhere.
    
    The inversion of k in (EC)DSA was using Euclid's algorithm which isn't
    constant-time. This change switches to Fermat's algorithm, which is
    much better. However, it's important to note that math/big itself isn't
    constant time and is using a 4-bit window for exponentiation with
    variable memory access patterns.
    
    (Since math/big depends quite deeply on its values being in minimal (as
    opposed to fixed-length) represetation, perhaps crypto/elliptic should
    grow a constant-time implementation of exponentiation in the scalar
    field.)
    
    R=bradfitz
    Fixes #7652.
    
    LGTM=rsc
    R=golang-codereviews, bradfitz, rsc
    CC=golang-codereviews
    https://golang.org/cl/82740043

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

https://github.com/golang/go/commit/f23d3ea85afce3c4940bcf55889625d2e2017128

元コミット内容

crypto/(ec)dsa: use Fermat's inversion.

Now that we have a constant-time P-256 implementation, it's worth
paying more attention elsewhere.

The inversion of k in (EC)DSA was using Euclid's algorithm which isn't
constant-time. This change switches to Fermat's algorithm, which is
much better. However, it's important to note that math/big itself isn't
constant time and is using a 4-bit window for exponentiation with
variable memory access patterns.

(Since math/big depends quite deeply on its values being in minimal (as
opposed to fixed-length) represetation, perhaps crypto/elliptic should
grow a constant-time implementation of exponentiation in the scalar
field.)

R=bradfitz
Fixes #7652.

LGTM=rsc
R=golang-codereviews, bradfitz, rsc
CC=golang-codereviews
https://golang.org/cl/82740043

変更の背景

この変更の主な背景は、暗号アルゴリズムにおけるサイドチャネル攻撃、特にタイミング攻撃への対策です。

Go言語の crypto/elliptic パッケージにおいて、P-256曲線（NIST P-256）の実装が定数時間で行われるようになったことが、このコミットの出発点となっています。定数時間実装とは、処理にかかる時間が入力データの内容に依存せず常に一定であることを意味します。これにより、攻撃者が処理時間のわずかな差を観測することで秘密情報を推測するタイミング攻撃を防ぐことができます。

P-256の実装が定数時間になったことで、次に注目すべきは、ECDSAおよびDSA署名生成プロセスにおける他の非定数時間操作でした。特に、署名生成の鍵となるステップの一つであるモジュラ逆元（kInv）の計算が、ユークリッドの互除法を用いて行われており、これが定数時間ではないことが問題視されました。ユークリッドの互除法は、入力値によって実行される演算回数や分岐回数が変動するため、タイミング攻撃の脆弱性となり得ます。

この脆弱性を解消するため、より定数時間特性に優れたフェルマーの小定理に基づくモジュラ逆元計算に切り替えることが決定されました。

前提知識の解説

DSA (Digital Signature Algorithm) と ECDSA (Elliptic Curve Digital Signature Algorithm)

• DSA: 公開鍵暗号方式の一つで、デジタル署名に特化したアルゴリズムです。メッセージの認証性、完全性、否認防止を提供します。離散対数問題の困難性に基づいています。
• ECDSA: DSAを楕円曲線暗号に適用したものです。DSAと比較して、同等のセキュリティレベルをより短い鍵長で実現できるため、計算コストやデータサイズを削減できます。楕円曲線上の離散対数問題の困難性に基づいています。

どちらのアルゴリズムも、署名生成プロセスにおいて、ある数値 k のモジュラ逆元 kInv を計算するステップを含みます。この k は署名ごとにランダムに生成される秘密の値であり、その計算過程が攻撃者に推測されると、秘密鍵が漏洩する可能性があります。

タイミング攻撃 (Timing Attacks)

タイミング攻撃は、暗号アルゴリズムの実行にかかる時間のわずかな変動を分析することで、秘密鍵などの秘密情報を推測するサイドチャネル攻撃の一種です。

多くの暗号アルゴリズムは、秘密情報（例: 秘密鍵のビット値）に基づいて異なる計算パスやメモリアクセスパターンを取ることがあります。例えば、あるビットが0の場合と1の場合で、条件分岐の有無やループの回数が変わると、実行時間に微細な差が生じます。攻撃者は、多数の暗号操作の実行時間を正確に測定し、統計的な分析を行うことで、これらの時間差から秘密情報を逆算しようとします。

タイミング攻撃を防ぐためには、暗号アルゴリズムのすべての操作が「定数時間」で実行されるように設計することが重要です。

定数時間 (Constant-Time) 処理

定数時間処理とは、アルゴリズムの実行時間が入力データの内容や秘密情報に依存せず、常に一定であるか、少なくとも予測可能な範囲で変動することを指します。これにより、タイミング攻撃によって秘密情報が漏洩するのを防ぎます。

定数時間処理を実現するためには、以下のような点に注意が必要です。

• 条件分岐の排除: 秘密情報に基づいて異なるコードパスを実行する条件分岐を避ける。
• ループ回数の固定: 秘密情報によってループの回数が変わらないようにする。
• メモリアクセスの固定: 秘密情報によってメモリのアクセスパターンが変わらないようにする。キャッシュ攻撃なども防ぐため、アクセスするアドレスも固定することが望ましい。
• テーブルルックアップの注意: 秘密情報に基づいてテーブルから値をルックアップする場合、アクセス時間が異なる可能性があるため注意が必要。

フェルマーの小定理 (Fermat's Little Theorem)

フェルマーの小定理は、数論における基本的な定理の一つです。

定理: p が素数であり、a が p の倍数でない整数であるならば、 a^(p-1) ≡ 1 (mod p) が成り立つ。

この定理を変形すると、モジュラ逆元を計算するのに利用できます。 a^(p-1) ≡ a * a^(p-2) ≡ 1 (mod p) したがって、a の法 p における逆元 a^(-1) は、a^(p-2) mod p で計算できます。

この方法の利点は、べき乗演算が通常、入力値に依存しない定数時間（またはそれに近い）で実行されるように実装できる点です。

ユークリッドの互除法 (Euclidean Algorithm)

ユークリッドの互除法は、2つの整数の最大公約数 (GCD) を求めるための効率的なアルゴリズムです。拡張ユークリッドの互除法は、さらに ax + by = gcd(a, b) を満たす整数 x と y を求めることができ、これを利用してモジュラ逆元 a^(-1) mod m を計算できます（gcd(a, m) = 1 の場合）。

拡張ユークリッドの互除法は、繰り返し剰余を計算していく過程で、入力値によってループの回数や内部の演算回数が変動します。この変動がタイミング攻撃の脆弱性となり得ます。

math/big パッケージ

Go言語の math/big パッケージは、任意精度の整数、有理数、浮動小数点数を扱うための機能を提供します。暗号ライブラリでは、非常に大きな数を扱う必要があるため、このパッケージが広く利用されています。

math/big.Int 型は多倍長整数を表し、ModInverse や Exp といったメソッドを提供します。

• ModInverse(y, m): x * y ≡ 1 (mod m) となる x を計算します。内部的には拡張ユークリッドの互除法を使用しています。
• Exp(x, y, m): x^y mod m を計算します。

技術的詳細

このコミットの技術的な核心は、DSA/ECDSA署名生成における k のモジュラ逆元 kInv の計算方法を、ユークリッドの互除法に基づく math/big.Int.ModInverse から、フェルマーの小定理に基づく新しい関数 fermatInverse に変更した点です。

元の実装では、kInv := new(big.Int).ModInverse(k, priv.Q) (DSAの場合) または kInv = new(big.Int).ModInverse(k, N) (ECDSAの場合) が使用されていました。ModInverse は拡張ユークリッドの互除法を内部で利用しており、このアルゴリズムは入力値によって実行パスが変動するため、タイミング攻撃に対して脆弱でした。

新しい fermatInverse 関数は、フェルマーの小定理 a^(p-2) mod p を利用して逆元を計算します。具体的には、k^(P-2) mod P (DSA) または k^(N-2) mod N (ECDSA) を計算します。ここで P や N はそれぞれDSAの素数 Q やECDSAの曲線の位数 N を指します。この計算は math/big.Int.Exp メソッドを用いて行われます。

しかし、コミットメッセージにも明記されているように、この変更は完全な定数時間処理を保証するものではありません。math/big パッケージ自体が厳密には定数時間ではないためです。特に、math/big.Int.Exp メソッドは、べき乗計算に「4-bit window」という最適化手法を使用しており、これによりメモリアクセスパターンが可変になる可能性があります。また、math/big は値を最小限の表現（固定長ではない）で保持するため、これも定数時間特性を損なう要因となり得ます。

このコミットは、タイミング攻撃に対する防御を強化する一歩ではありますが、math/big の制約により、まだ改善の余地があることを示唆しています。コミットメッセージでは、将来的に crypto/elliptic パッケージがスカラーフィールドにおける定数時間べき乗実装を持つべきであるという提案もなされています。これは、より低レベルで、かつ定数時間特性を厳密に保証するべき乗アルゴリズムを実装する必要があることを意味します。

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

src/pkg/crypto/dsa/dsa.go

--- a/src/pkg/crypto/dsa/dsa.go
+++ b/src/pkg/crypto/dsa/dsa.go
@@ -173,6 +173,16 @@ func GenerateKey(priv *PrivateKey, rand io.Reader) error {
 	return nil
 }
 
+// fermatInverse calculates the inverse of k in GF(P) using Fermat's method.
+// This has better constant-time properties than Euclid's method (implemented
+// in math/big.Int.ModInverse) although math/big itself isn't strictly
+// constant-time so it's not perfect.
+func fermatInverse(k, P *big.Int) *big.Int {
+	two := big.NewInt(2)
+	pMinus2 := new(big.Int).Sub(P, two)
+	return new(big.Int).Exp(k, pMinus2, P)
+}
+
 // Sign signs an arbitrary length hash (which should be the result of hashing a
 // larger message) using the private key, priv. It returns the signature as a
 // pair of integers. The security of the private key depends on the entropy of
@@ -205,7 +215,7 @@ func Sign(rand io.Reader, priv *PrivateKey, hash []byte) (r, s *big.Int, err err
 			}
 		}
 
-		kInv := new(big.Int).ModInverse(k, priv.Q)
+		kInv := fermatInverse(k, priv.Q)
 
 		r = new(big.Int).Exp(priv.G, k, priv.P)
 		r.Mod(r, priv.Q)

src/pkg/crypto/ecdsa/ecdsa.go

--- a/src/pkg/crypto/ecdsa/ecdsa.go
+++ b/src/pkg/crypto/ecdsa/ecdsa.go
@@ -84,6 +84,16 @@ func hashToInt(hash []byte, c elliptic.Curve) *big.Int {
 	return ret
 }
 
+// fermatInverse calculates the inverse of k in GF(P) using Fermat's method.
+// This has better constant-time properties than Euclid's method (implemented
+// in math/big.Int.ModInverse) although math/big itself isn't strictly
+// constant-time so it's not perfect.
+func fermatInverse(k, N *big.Int) *big.Int {
+	two := big.NewInt(2)
+	nMinus2 := new(big.Int).Sub(N, two)
+	return new(big.Int).Exp(k, nMinus2, N)
+}
+
 // Sign signs an arbitrary length hash (which should be the result of hashing a
 // larger message) using the private key, priv. It returns the signature as a
 // pair of integers. The security of the private key depends on the entropy of
@@ -102,7 +112,7 @@ func Sign(rand io.Reader, priv *PrivateKey, hash []byte) (r, s *big.Int, err err
 				return
 			}
 
-			kInv = new(big.Int).ModInverse(k, N)
+			kInv = fermatInverse(k, N)
 			r, _ = priv.Curve.ScalarBaseMult(k.Bytes())
 			r.Mod(r, N)
 			if r.Sign() != 0 {

コアとなるコードの解説

このコミットの主要な変更は、fermatInverse という新しいヘルパー関数の導入と、既存の Sign 関数内でのモジュラ逆元計算の呼び出し箇所の変更です。

fermatInverse 関数の追加

crypto/dsa/dsa.go と crypto/ecdsa/ecdsa.go の両方に、ほぼ同じ実装の fermatInverse 関数が追加されました。

func fermatInverse(k, P *big.Int) *big.Int { // PはDSAではpriv.Q、ECDSAではN
	two := big.NewInt(2)
	pMinus2 := new(big.Int).Sub(P, two) // P-2 を計算
	return new(big.Int).Exp(k, pMinus2, P) // k^(P-2) mod P を計算
}

この関数は、フェルマーの小定理 a^(p-2) ≡ a^(-1) (mod p) を直接実装しています。

• k: 逆元を計算したい数値。
• P (または N): 法となる素数（DSAでは priv.Q、ECDSAでは曲線の位数 N）。
• two := big.NewInt(2): 定数2を表す big.Int を作成。
• pMinus2 := new(big.Int).Sub(P, two): 法から2を引いた値 (P-2) を計算。これはフェルマーの小定理における指数部となります。
• return new(big.Int).Exp(k, pMinus2, P): k を P-2 乗し、その結果を P で割った余り（モジュロ）を計算します。これが k のモジュラ逆元となります。

この fermatInverse 関数は、math/big.Int.Exp を使用してべき乗剰余を計算します。べき乗剰余アルゴリズムは、通常、入力値のビット長に依存するものの、個々のビット値には依存しないように実装されることが多いため、ユークリッドの互除法よりも定数時間特性に優れているとされています。ただし、コミットメッセージにあるように、math/big.Int.Exp 自体が完全に定数時間ではない（4-bit windowや可変メモリアクセスパターンがある）という注意点があります。

Sign 関数内の変更

crypto/dsa/dsa.go の Sign 関数と crypto/ecdsa/ecdsa.go の Sign 関数において、kInv の計算方法が変更されました。

変更前:

kInv := new(big.Int).ModInverse(k, priv.Q) // DSAの場合
kInv = new(big.Int).ModInverse(k, N)       // ECDSAの場合

変更後:

kInv := fermatInverse(k, priv.Q) // DSAの場合
kInv = fermatInverse(k, N)       // ECDSAの場合

これにより、モジュラ逆元計算がユークリッドの互除法からフェルマーの小定理に基づく方法に切り替わり、タイミング攻撃に対する耐性が向上しました。

関連リンク

• Go Issue: crypto/ecdsa: constant time ModInverse for scalar field · Issue #7652 · golang/go
• Go Code Review: https://golang.org/cl/82740043

参考にした情報源リンク

• Fermat's Little Theorem - Wikipedia
• Modular multiplicative inverse - Wikipedia
• Timing attack - Wikipedia
• math/big package - math/big - Go Packages
• crypto/dsa package - crypto/dsa - Go Packages
• crypto/ecdsa package - crypto/ecdsa - Go Packages
• crypto/elliptic package - crypto/elliptic - Go Packages
• Constant-time programming - Wikipedia
• Exponentiation by squaring - Wikipedia (べき乗アルゴリズムの一般的な説明)
• Windowed exponentiation - Wikipedia (4-bit windowの説明に関連)