Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

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

このコミットは、Go言語の標準ライブラリcrypto/rsaパッケージにおいて、RSA公開鍵の公開指数Eの検証ロジックを強化するものです。具体的には、PublicKey.Eが32ビット符号付き整数に収まらない場合に拒否するチェックを追加し、さらに他の不正な値（モジュラスの欠如、Eが小さすぎる場合）も検証することで、RSA操作の堅牢性とセキュリティを向上させています。

コミット

commit ef87c0edae19d6437801cd74203f5a2c19ea6534
Author: Russ Cox <rsc@golang.org>
Date:   Thu Sep 13 10:47:01 2012 -0400

    crypto/rsa: reject PublicKey.E if it won't fit in a 32-bit int
    
    Right now we only have 32-bit ints so that's a no-op.
    Took the opportunity to check for some other invalid values too.
    Suggestions for additions or modifications welcome.
    
    R=agl
    CC=golang-dev
    https://golang.org/cl/6493112

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

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

元コミット内容

crypto/rsa: reject PublicKey.E if it won't fit in a 32-bit int

Right now we only have 32-bit ints so that's a no-op.
Took the opportunity to check for some other invalid values too.
Suggestions for additions or modifications welcome.

R=agl
CC=golang-dev
https://golang.org/cl/6493112

変更の背景

この変更の主な背景は、RSA公開鍵の公開指数Eの値が、異なるCPUアーキテクチャ（特に32ビットと64ビットシステム）間で一貫した動作を保証するためです。コミットメッセージにある「Right now we only have 32-bit ints so that's a no-op.」という記述は、当時のGoコンパイラがint型を32ビットとして扱っていたため、このチェックがすぐに影響を与えるわけではないことを示唆しています。しかし、将来的にint型が64ビットシステムで64ビットになる可能性を考慮し、Eの処理がアーキテクチャに依存しないようにするための予防的な措置です。

特に、Adam Langley氏のブログ記事「RSA public exponent validation」で指摘されているように、公開指数Eが非常に大きい値である場合、実装によっては異なる動作を引き起こす可能性があります。例えば、Eが32ビット整数に収まらないような大きな値であると、一部のシステムではオーバーフローが発生したり、計算が非常に遅くなったり、あるいは特定の最適化が適用できなくなったりする可能性があります。このような不整合は、潜在的なサイドチャネル攻撃（特にタイミング攻撃）のリスクを高めたり、サービス拒否攻撃につながる可能性も考えられます。

このコミットは、このような将来的な互換性の問題や潜在的なセキュリティリスクを未然に防ぐために、Eの値を明示的に制限し、さらにモジュラスNの存在チェックやEの最小値チェックといった基本的な健全性チェックも追加することで、crypto/rsaパッケージの堅牢性を高めることを目的としています。

前提知識の解説

RSA暗号の基本

RSA暗号は、公開鍵暗号方式の一つで、公開鍵と秘密鍵のペアを使用します。

  • 公開鍵 (Public Key): 誰もが知ることができ、データの暗号化や署名の検証に使用されます。RSA公開鍵は通常、以下の要素で構成されます。
    • モジュラス (Modulus, N): 2つの大きな素数pとqの積（N = p * q）です。
    • 公開指数 (Public Exponent, E): 通常は小さな正の整数で、最も一般的な値は3や65537（F4）です。
  • 秘密鍵 (Private Key): 所有者のみが知るべき鍵で、データの復号や署名の生成に使用されます。秘密鍵は通常、モジュラスN、秘密指数D、および素数p, qなどから構成されます。

RSAの暗号化・復号は、モジュラーべき乗（m^E mod N や c^D mod N）という数学的操作に基づいています。

公開指数 (E) の役割と一般的な値

公開指数Eは、RSA暗号化の際に使用される値です。Eは通常、計算効率とセキュリティのバランスを考慮して選ばれます。

  • 一般的な値: 3, 17, 65537などがよく使われます。これらの値はフェルマー数（F_n = 2^(2^n) + 1）であり、バイナリ表現で1のビットが少ないため、べき乗計算が高速に行えるという利点があります。
  • セキュリティ上の考慮: Eが小さすぎると、特定の攻撃に対して脆弱になる可能性があります（例: E=1は明らかに安全ではありません）。また、Eが大きすぎると、計算コストが増大するだけでなく、実装によっては予期せぬ動作を引き起こす可能性があります。

32ビット整数と64ビット整数

コンピュータのプログラミングにおいて、整数型は通常、その値を格納するために使用されるビット数によって定義されます。

  • 32ビット整数: 32ビット（4バイト）のメモリを使用して整数値を表現します。符号付きの場合、約 -20億から +20億までの範囲の値を格納できます。最大値は 2^31 - 1 です。
  • 64ビット整数: 64ビット（8バイト）のメモリを使用して整数値を表現します。符号付きの場合、非常に大きな範囲の値を格納できます。最大値は 2^63 - 1 です。

Go言語のint型は、コンパイルされるシステム（アーキテクチャ）によって32ビットまたは64ビットのいずれかになります。このコミットが作成された2012年当時、Goのint型は主に32ビットとして扱われていましたが、将来的に64ビットシステムで64ビットになる可能性がありました。このため、PublicKey.Eがint型で表現される際に、異なるアーキテクチャ間で動作の一貫性を保つことが重要になります。

サイドチャネル攻撃（特にタイミング攻撃）

サイドチャネル攻撃は、暗号システムの実装から漏洩する情報（実行時間、消費電力、電磁波など）を利用して、秘密鍵などの機密情報を推測する攻撃手法です。

  • タイミング攻撃: 暗号操作の実行時間のわずかな違いを分析することで、秘密鍵のビットを推測する攻撃です。例えば、特定の入力値に対する処理時間が他の入力値と異なる場合、その時間差が攻撃者に利用される可能性があります。 RSAの実装において、公開指数Eの処理方法がアーキテクチャによって異なると、計算時間の差が生じ、これがタイミング攻撃の足がかりとなるリスクがあります。このコミットは、Eの値を制限することで、このような実装依存の動作差をなくし、タイミング攻撃のリスクを低減することにも寄与します。

PKCS#1 v1.5とOAEPパディングスキーム

RSA暗号を使用する際には、平文を直接暗号化するのではなく、特定のパディングスキーム（詰め物方式）を適用するのが一般的です。これは、セキュリティを向上させ、特定の攻撃（例: 選択暗号文攻撃）を防ぐためです。

  • PKCS#1 v1.5: RSAの初期のパディングスキームの一つです。広く使用されていますが、既知の脆弱性（例: Bleichenbacherの攻撃）があるため、新しいプロトコルでは推奨されません。
  • OAEP (Optimal Asymmetric Encryption Padding): PKCS#1 v2.0で導入された、よりセキュアなパディングスキームです。ランダム性とハッシュ関数を組み合わせて、より強力なセキュリティを提供します。

このコミットでは、これらのパディングスキームを使用するRSA関数にcheckPub関数が追加され、RSA操作の前に公開鍵の健全性が検証されるようになります。

技術的詳細

このコミットは、Go言語のcrypto/rsaパッケージにおけるRSA公開鍵の検証ロジックを強化するものです。主な変更点は、PublicKey構造体に定義されている公開指数Eの値を厳密にチェックするcheckPub関数の導入と、その関数をRSAの主要な操作関数に組み込むことです。

PublicKey構造体

src/pkg/crypto/rsa/rsa.goファイルには、RSA公開鍵を表すPublicKey構造体が定義されています。

type PublicKey struct {
	N *big.Int // modulus
	E int      // public exponent
}

ここで注目すべきは、公開指数EがGoの組み込み型intで定義されている点です。前述の通り、int型はコンパイルされるアーキテクチャによって32ビットまたは64ビットになり得ます。

新しいエラー変数の定義

checkPub関数が返す可能性のあるエラーを表すために、以下の3つの新しいエラー変数が定義されました。

var (
	errPublicModulus       = errors.New("crypto/rsa: missing public modulus")
	errPublicExponentSmall = errors.New("crypto/rsa: public exponent too small")
	errPublicExponentLarge = errors.New("crypto/rsa: public exponent too large")
)

checkPub関数の導入

このコミットの核心は、checkPub関数の導入です。この関数は、RSA公開鍵pubの健全性をチェックし、問題があればエラーを返します。

// checkPub sanity checks the public key before we use it.
// We require pub.E to fit into a 32-bit integer so that we
// do not have different behavior depending on whether
// int is 32 or 64 bits. See also
// http://www.imperialviolet.org/2012/03/16/rsae.html.
func checkPub(pub *PublicKey) error {
	if pub.N == nil {
		return errPublicModulus
	}
	if pub.E < 2 {
		return errPublicExponentSmall
	}
	if pub.E > 1<<31-1 {
		return errPublicExponentLarge
	}
	return nil
}

checkPub関数は以下の3つの条件をチェックします。

  1. pub.N == nil: 公開鍵のモジュラスNがnilでないことを確認します。モジュラスはRSA公開鍵の必須要素であるため、これが欠けている場合は不正な鍵と判断されます。
  2. pub.E < 2: 公開指数Eが2以上であることを確認します。Eが1以下であることはRSAの数学的特性上、適切ではありません。
  3. pub.E > 1<<31-1: 公開指数Eが2^31 - 1（符号付き32ビット整数の最大値）を超えないことを確認します。これがこのコミットの主要な目的であり、Eが32ビット整数に収まることを保証します。このチェックにより、int型が32ビットであるシステムと64ビットであるシステムで、Eの処理に関する動作の一貫性が保たれます。Adam Langley氏のブログ記事で言及されているように、Eが非常に大きい場合に発生しうる実装上の問題やセキュリティリスクを回避するための重要な制限です。

checkPub関数の適用

checkPub関数は、crypto/rsaパッケージ内の以下の主要なRSA操作関数に組み込まれました。これにより、RSAの暗号化、復号、鍵の検証といった操作が実行される前に、必ず公開鍵の健全性チェックが行われるようになります。

  • src/pkg/crypto/rsa/pkcs1v15.go:
    • EncryptPKCS1v15
    • DecryptPKCS1v15
    • DecryptPKCS1v15SessionKey
  • src/pkg/crypto/rsa/rsa.go:
    • PrivateKey.Validate() (秘密鍵の検証時にも、その内部に含まれる公開鍵の検証が行われます)
    • EncryptOAEP
    • DecryptOAEP

これらの変更により、不正な、あるいは潜在的に問題のある公開鍵がRSA操作に使用されることを防ぎ、ライブラリ全体の堅牢性とセキュリティが向上します。

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

src/pkg/crypto/rsa/pkcs1v15.go

--- a/src/pkg/crypto/rsa/pkcs1v15.go
+++ b/src/pkg/crypto/rsa/pkcs1v15.go
@@ -19,6 +19,9 @@ import (
 // WARNING: use of this function to encrypt plaintexts other than session keys
 // is dangerous. Use RSA OAEP in new protocols.
 func EncryptPKCS1v15(rand io.Reader, pub *PublicKey, msg []byte) (out []byte, err error) {
+	if err := checkPub(pub); err != nil {
+		return nil, err
+	}
 	k := (pub.N.BitLen() + 7) / 8
 	if len(msg) > k-11 {
 		err = ErrMessageTooLong
@@ -47,6 +50,9 @@ func EncryptPKCS1v15(rand io.Reader, pub *PublicKey, msg []byte) (out []byte, er
 // DecryptPKCS1v15 decrypts a plaintext using RSA and the padding scheme from PKCS#1 v1.5.
 // If rand != nil, it uses RSA blinding to avoid timing side-channel attacks.
 func DecryptPKCS1v15(rand io.Reader, priv *PrivateKey, ciphertext []byte) (out []byte, err error) {
+	if err := checkPub(&priv.PublicKey); err != nil {
+		return nil, err
+	}
 	valid, out, err := decryptPKCS1v15(rand, priv, ciphertext)
 	if err == nil && valid == 0 {
 		err = ErrDecryption
@@ -69,6 +75,9 @@ func DecryptPKCS1v15(rand io.Reader, priv *PrivateKey, ciphertext []byte) (out [
 // Encryption Standard PKCS #1'', Daniel Bleichenbacher, Advances in Cryptology
 // (Crypto '98).
 func DecryptPKCS1v15SessionKey(rand io.Reader, priv *PrivateKey, ciphertext []byte, key []byte) (err error) {
+	if err := checkPub(&priv.PublicKey); err != nil {
+		return err
+	}
 	k := (priv.N.BitLen() + 7) / 8
 	if k-(len(key)+3+8) < 0 {
 		err = ErrDecryption

src/pkg/crypto/rsa/rsa.go

--- a/src/pkg/crypto/rsa/rsa.go
+++ b/src/pkg/crypto/rsa/rsa.go
@@ -25,6 +25,30 @@ type PublicKey struct {
 	E int      // public exponent
 }
 
+var (
+	errPublicModulus       = errors.New("crypto/rsa: missing public modulus")
+	errPublicExponentSmall = errors.New("crypto/rsa: public exponent too small")
+	errPublicExponentLarge = errors.New("crypto/rsa: public exponent too large")
+)
+
+// checkPub sanity checks the public key before we use it.
+// We require pub.E to fit into a 32-bit integer so that we
+// do not have different behavior depending on whether
+// int is 32 or 64 bits. See also
+// http://www.imperialviolet.org/2012/03/16/rsae.html.
+func checkPub(pub *PublicKey) error {
+	if pub.N == nil {
+		return errPublicModulus
+	}
+	if pub.E < 2 {
+		return errPublicExponentSmall
+	}
+	if pub.E > 1<<31-1 {
+		return errPublicExponentLarge
+	}
+	return nil
+}
+
 // A PrivateKey represents an RSA key
 type PrivateKey struct {
 	PublicKey            // public part.
@@ -57,6 +81,10 @@ type CRTValue struct {
 // Validate performs basic sanity checks on the key.
 // It returns nil if the key is valid, or else an error describing a problem.
 func (priv *PrivateKey) Validate() error {
+	if err := checkPub(&priv.PublicKey); err != nil {
+		return err
+	}
+
 	// Check that the prime factors are actually prime. Note that this is
 	// just a sanity check. Since the random witnesses chosen by
 	// ProbablyPrime are deterministic, given the candidate number, it's
@@ -216,6 +244,9 @@ func encrypt(c *big.Int, pub *PublicKey, m *big.Int) *big.Int {
 // The message must be no longer than the length of the public modulus less
 // twice the hash length plus 2.
 func EncryptOAEP(hash hash.Hash, random io.Reader, pub *PublicKey, msg []byte, label []byte) (out []byte, err error) {
+	if err := checkPub(pub); err != nil {
+		return nil, err
+	}
 	hash.Reset()
 	k := (pub.N.BitLen() + 7) / 8
 	if len(msg) > k-2*hash.Size()-2 {
@@ -402,6 +433,9 @@ func decrypt(random io.Reader, priv *PrivateKey, c *big.Int) (m *big.Int, err er
 // DecryptOAEP decrypts ciphertext using RSA-OAEP.
 // If random != nil, DecryptOAEP uses RSA blinding to avoid timing side-channel attacks.
 func DecryptOAEP(hash hash.Hash, random io.Reader, priv *PrivateKey, ciphertext []byte, label []byte) (msg []byte, err error) {
+	if err := checkPub(&priv.PublicKey); err != nil {
+		return nil, err
+	}
 	k := (priv.N.BitLen() + 7) / 8
 	if len(ciphertext) > k ||
 		k < hash.Size()*2+2 {

コアとなるコードの解説

src/pkg/crypto/rsa/rsa.go の変更点

  1. エラー変数の追加: errPublicModulus, errPublicExponentSmall, errPublicExponentLarge の3つのerror変数が追加されました。これらは、checkPub関数が公開鍵の検証に失敗した場合に返す具体的なエラーメッセージを提供します。これにより、エラーの原因をより明確に特定できるようになります。

  2. checkPub関数の定義: この関数は、PublicKeyポインタを受け取り、その公開鍵がRSA操作に使用するのに適切であるかを検証します。

    • if pub.N == nil: RSA公開鍵のモジュラスNがnilである場合、errPublicModulusを返します。モジュラスはRSA鍵の根幹をなす要素であり、これが存在しない鍵は無効です。
    • if pub.E < 2: 公開指数Eが2未満である場合、errPublicExponentSmallを返します。RSAの数学的定義上、Eは2以上の整数である必要があります。E=1のような値はセキュリティ上の問題を引き起こす可能性があります。
    • if pub.E > 1<<31-1: 公開指数Eが2^31 - 1（符号付き32ビット整数の最大値）より大きい場合、errPublicExponentLargeを返します。このチェックは、PublicKey.EがGoのint型（当時32ビット）に収まることを保証するためのものです。これにより、32ビットシステムと64ビットシステムでEの処理が異なることによる潜在的な問題（例: オーバーフロー、性能低下、タイミング攻撃の可能性）を防ぎ、実装の一貫性と堅牢性を高めます。コメントにもあるように、Adam Langley氏のブログ記事でこの問題が指摘されています。

  3. PrivateKey.Validate()へのcheckPubの追加: PrivateKeyのValidateメソッドは、秘密鍵の健全性をチェックするものです。このメソッドの冒頭にcheckPub(&priv.PublicKey)が追加されました。これにより、秘密鍵の検証を行う際に、その秘密鍵に対応する公開鍵の健全性も同時にチェックされるようになります。これは、秘密鍵が有効であっても、関連する公開鍵が不正な値を含んでいる場合に備えるための重要な追加です。

  4. EncryptOAEPおよびDecryptOAEPへのcheckPubの追加: OAEPパディングスキームを使用するRSA暗号化関数EncryptOAEPと復号関数DecryptOAEPの冒頭にもcheckPubが追加されました。これにより、OAEPを使用したRSA操作を行う前に、渡された公開鍵（または秘密鍵に含まれる公開鍵）が有効であるかどうかが検証され、不正な鍵による操作が防止されます。

src/pkg/crypto/rsa/pkcs1v15.go の変更点

  1. EncryptPKCS1v15、DecryptPKCS1v15、DecryptPKCS1v15SessionKeyへのcheckPubの追加: PKCS#1 v1.5パディングスキームを使用するRSA暗号化関数EncryptPKCS1v15と復号関数DecryptPKCS1v15、およびセッション鍵復号関数DecryptPKCS1v15SessionKeyの冒頭にもcheckPubが追加されました。これらの関数もRSA操作を行うため、同様に公開鍵の健全性チェックが必須となります。これにより、古いパディングスキームを使用する場合でも、公開鍵の検証が確実に行われるようになります。

これらの変更は、crypto/rsaパッケージが扱うRSA公開鍵の入力値をより厳密に検証することで、ライブラリの堅牢性を高め、異なるシステム環境下での一貫した動作を保証し、潜在的なセキュリティリスクを軽減することを目的としています。特に、Eの値を32ビット整数に制限するチェックは、Go言語のint型の特性と、RSA実装における微妙な挙動の違いに起因する問題を解決するための重要な措置です。

関連リンク

参考にした情報源リンク

  • Adam Langley - RSA public exponent validation: https://www.imperialviolet.org/2012/03/16/rsae.html
  • Go言語のcrypto/rsaパッケージのソースコード (コミット時点のバージョンに基づく)
  • RSA暗号に関する一般的な知識 (公開鍵暗号、モジュラス、公開指数、パディングスキームなど)
  • 32ビット/64ビットシステムにおける整数型の挙動に関する知識
  • サイドチャネル攻撃、特にタイミング攻撃に関する知識