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

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

このコミットは、Go言語のcrypto/rsaパッケージにおけるPKCS#1 v1.5パディングの検証ロジックに、最小パディング長チェックを追加するものです。具体的には、パディング文字列（PS）が少なくとも8バイトの長さを持つことを保証するチェックが導入されました。これにより、PKCS#1 v1.5の仕様に厳密に準拠し、潜在的な脆弱性や予期せぬ挙動を防ぐことを目的としています。また、この変更はサイドチャネル攻撃を防ぐための定数時間操作を維持しつつ実装されています。

コミット

commit e85e67889931e10908e912622a6954943fb28ed5
Author: Adam Langley <agl@golang.org>
Date:   Wed May 15 10:27:34 2013 -0400

    crypto/rsa: check for minimal PKCS#1 v1.5 padding.
    
    The PKCS#1 spec requires that the PS padding in an RSA message be at
    least 8 bytes long. We were not previously checking this. This isn't
    important in the most common situation (session key encryption), but
    the impact is unclear in other cases.
    
    This change enforces the specified minimum size.
    
    R=golang-dev, bradfitz
    CC=golang-dev
    https://golang.org/cl/9222045

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

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

元コミット内容

このコミットの元の内容は、RSA暗号のPKCS#1 v1.5パディングにおいて、パディング文字列（PS）の最小長が8バイトであることを検証するチェックを追加することです。これまでの実装ではこのチェックが行われておらず、最も一般的なセッション鍵暗号化のシナリオでは問題とならなかったものの、他のケースでの影響が不明確であったため、仕様への準拠を強化するために導入されました。

変更の背景

RSA暗号におけるPKCS#1 v1.5パディングは、暗号化されるメッセージのセキュリティを確保するために重要な役割を果たします。PKCS#1 v1.5の仕様（RFC 3447 Section 7.2.1）では、暗号化されるデータブロックの構造が厳密に定義されており、その中に含まれるパディング文字列（PS）は少なくとも8バイトの長さを持つことが要求されています。

このコミット以前のGo言語のcrypto/rsaパッケージの実装では、この最小長チェックが欠落していました。パディングの長さが短い場合、特定の攻撃（例えば、Bleichenbacherの攻撃の変種など）に対して脆弱性をもたらす可能性があります。たとえ一般的なセッション鍵暗号化のシナリオでは直接的な影響が少ないとしても、暗号ライブラリは可能な限り仕様に厳密に準拠し、あらゆる潜在的なリスクを排除することが求められます。

この変更は、Go言語の暗号ライブラリの堅牢性とセキュリティを向上させ、PKCS#1 v1.5の仕様への完全な準拠を達成することを目的としています。

前提知識の解説

RSA暗号

RSAは、公開鍵暗号方式の一つで、データの暗号化、デジタル署名、鍵交換などに広く用いられています。大きな素数の積を因数分解することが困難であるという数学的な問題に基づいています。公開鍵と秘密鍵のペアを使用し、公開鍵で暗号化されたデータは対応する秘密鍵でのみ復号できます。

PKCS#1 v1.5パディング

PKCS#1 (Public-Key Cryptography Standards #1) は、RSA暗号の標準規格です。その中でもv1.5は広く利用されているパディングスキームの一つです。RSA暗号は固定長のブロックを処理するため、メッセージがブロック長より短い場合や、セキュリティを向上させるためにパディングが必要です。

PKCS#1 v1.5の暗号化パディング（RSAES-PKCS1-v1_5）の構造は以下のようになります。

EM = 00 || 02 || PS || 00 || M

  • EM: 暗号化されるデータブロック（Encoding Method）
  • 00: 常に0x00バイト
  • 02: 常に0x02バイト（暗号化スキームを示す）
  • PS: パディング文字列（Padding String）。ランダムな非ゼロバイトの列で構成されます。PKCS#1 v1.5の仕様では、このPSの長さは少なくとも8バイトでなければならないと規定されています。
  • 00: 常に0x00バイト（PSとメッセージMの区切り）
  • M: 暗号化される実際のメッセージ

復号時には、この構造を検証し、00 || 02、PS、00、そしてメッセージMを正しく抽出します。PSの最小長チェックは、この復号プロセスにおけるセキュリティを強化するために重要です。

定数時間操作 (Constant-Time Operations)

定数時間操作とは、処理にかかる時間が入力データの内容に依存しない操作のことです。暗号処理において、処理時間が入力データ（例えば秘密鍵や平文）によって変動すると、その時間差を観測することで秘密情報を推測する「サイドチャネル攻撃」（タイミング攻撃など）が可能になる場合があります。

例えば、ある処理が秘密鍵の特定のビットが1の場合と0の場合で異なる時間かかる場合、攻撃者はその時間差を測定することで秘密鍵のビットを特定できる可能性があります。これを防ぐために、暗号ライブラリでは、秘密情報に依存する処理は可能な限り定数時間で実行されるように設計されます。

このコミットでは、PKCS#1 v1.5パディングの検証において、パディングの長さをチェックする際にも定数時間操作を維持することが重要視されています。

技術的詳細

このコミットの主要な変更点は、crypto/rsa/pkcs1v15.goのdecryptPKCS1v15関数にパディング文字列（PS）の最小長チェックを追加したことです。

元のコードでは、パディングの開始位置を示すindex変数を特定し、その後に続くメッセージを抽出していました。このindexは、00 || 02 || PS || 00 || Mという構造における、メッセージMの直前の00バイトの位置を示します。

新しいコードでは、subtle.ConstantTimeLessOrEqという新しい定数時間関数を導入し、これを用いてPSの長さを検証しています。

validPS := subtle.ConstantTimeLessOrEq(2+8, index)

この行の解説:

  • 2: 00 || 02の2バイト。
  • 8: PKCS#1 v1.5の仕様で要求されるPSの最小長8バイト。
  • index: em（エンコードされたメッセージ）の先頭から数えて、PSの後の00バイトの位置。

したがって、2 + 8は、00 || 02 || PSの合計の最小長（10バイト）を示します。indexはPSの後の00バイトの位置なので、indexが2 + 8（つまり10）以上であれば、PSの長さは8バイト以上であることになります。

subtle.ConstantTimeLessOrEq(x, y)は、x <= yであれば1を、そうでなければ0を定数時間で返します。 この場合、indexが2+8（10）以上であれば、validPSは1となり、パディング長が有効であることを示します。

最終的なvalidフラグの計算にvalidPSが追加されます。 valid = firstByteIsZero & secondByteIsTwo & (^lookingForIndex & 1) & validPS

これにより、復号が成功するためには、最初のバイトが0x00、2番目のバイトが0x02、そしてパディング文字列が適切な長さであるという全ての条件が満たされる必要があります。

また、crypto/subtle/constant_time.goには、新しい定数時間関数ConstantTimeLessOrEqが追加されています。この関数は、x <= yを定数時間で判定するためにビット演算を使用しています。

return int(((x32 - y32 - 1) >> 31) & 1)

この式は、x - y - 1の結果の最上位ビット（符号ビット）を利用して比較を行います。

  • もしx <= yであれば、x - y - 1は負の値となり、符号ビットは1になります。右シフト>> 31により、結果は-1（すべてのビットが1）または0（すべてのビットが0）になります。& 1により、結果は1になります。
  • もしx > yであれば、x - y - 1は非負の値となり、符号ビットは0になります。右シフト>> 31により、結果は0になり、& 1により、結果は0になります。 この巧妙なビット演算により、比較処理が入力値に依存しない定数時間で実行されることが保証されます。

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

src/pkg/crypto/rsa/pkcs1v15.go

--- a/src/pkg/crypto/rsa/pkcs1v15.go
+++ b/src/pkg/crypto/rsa/pkcs1v15.go
@@ -124,7 +124,11 @@ func decryptPKCS1v15(rand io.Reader, priv *PrivateKey, ciphertext []byte) (valid
 		lookingForIndex = subtle.ConstantTimeSelect(equals0, 0, lookingForIndex)
 	}\n
-\tvalid = firstByteIsZero & secondByteIsTwo & (^lookingForIndex & 1)
+\t// The PS padding must be at least 8 bytes long, and it starts two
+\t// bytes into em.
+\tvalidPS := subtle.ConstantTimeLessOrEq(2+8, index)
+\n+\tvalid = firstByteIsZero & secondByteIsTwo & (^lookingForIndex & 1) & validPS
 	msg = em[index+1:]
 	return
 }

src/pkg/crypto/rsa/pkcs1v15_test.go

--- a/src/pkg/crypto/rsa/pkcs1v15_test.go
+++ b/src/pkg/crypto/rsa/pkcs1v15_test.go
@@ -197,6 +197,14 @@ func TestVerifyPKCS1v15(t *testing.T) {
 	}
 }
 
+func TestOverlongMessagePKCS1v15(t *testing.T) {
+\tciphertext := decodeBase64("fjOVdirUzFoLlukv80dBllMLjXythIf22feqPrNo0YoIjzyzyoMFiLjAc/Y4krkeZ11XFThIrEvw\\nkRiZcCq5ng==")
+\t_, err := DecryptPKCS1v15(nil, rsaPrivateKey, ciphertext)
+\tif err == nil {
+\t\tt.Error("RSA decrypted a message that was too long.")
+\t}
+}
+\n // In order to generate new test vectors you'll need the PEM form of this key:\n // -----BEGIN RSA PRIVATE KEY-----\n // MIIBOgIBAJBALKZD0nEffqM1ACuak0bijtqE2QrI/KLADv7l3kK3ppMyCuLKoF0

src/pkg/crypto/subtle/constant_time.go

--- a/src/pkg/crypto/subtle/constant_time.go
+++ b/src/pkg/crypto/subtle/constant_time.go
@@ -55,3 +55,11 @@ func ConstantTimeCopy(v int, x, y []byte) {
 	}
 	return
 }
+\n+// ConstantTimeLessOrEq returns 1 if x <= y and 0 otherwise.
+// Its behavior is undefined if x or y are negative or > 2**31 - 1.
+func ConstantTimeLessOrEq(x, y int) int {
+\tx32 := int32(x)
+\ty32 := int32(y)
+\treturn int(((x32 - y32 - 1) >> 31) & 1)
+}

src/pkg/crypto/subtle/constant_time_test.go

--- a/src/pkg/crypto/subtle/constant_time_test.go
+++ b/src/pkg/crypto/subtle/constant_time_test.go
@@ -103,3 +103,23 @@ func TestConstantTimeCopy(t *testing.T) {
 \t\tt.Error(err)
 \t}
 }
+\n+var lessOrEqTests = []struct {
+\tx, y, result int
+}{\n+\t{0, 0, 1},\n+\t{1, 0, 0},\n+\t{0, 1, 1},\n+\t{10, 20, 1},\n+\t{20, 10, 0},\n+\t{10, 10, 1},\n+}\n+\n+func TestConstantTimeLessOrEq(t *testing.T) {
+\tfor i, test := range lessOrEqTests {
+\t\tresult := ConstantTimeLessOrEq(test.x, test.y)
+\t\tif result != test.result {
+\t\t\tt.Errorf("#%d: %d <= %d gave %d, expected %d", i, test.x, test.y, result, test.result)
+\t\t}
+\t}
+}\n```

## コアとなるコードの解説

### `src/pkg/crypto/rsa/pkcs1v15.go` の変更

*   `decryptPKCS1v15` 関数内で、`validPS := subtle.ConstantTimeLessOrEq(2+8, index)` という行が追加されました。
    *   `2+8` は、`00 || 02 || PS` の最小長（10バイト）を表します。
    *   `index` は、エンコードされたメッセージ `em` 内で、パディングの後の `00` バイトの位置を示します。
    *   この行は、`index` が少なくとも10バイトの位置にあることを定数時間で確認し、その結果を `validPS` に格納します。`index` が10以上であれば `validPS` は1、そうでなければ0となります。
*   既存の `valid` フラグの計算式に `& validPS` が追加されました。
    *   これにより、復号が成功するためには、これまでのチェック（最初のバイトが0x00、2番目のバイトが0x02、パディングの区切りが正しく見つかること）に加えて、パディングの最小長も満たされている必要があることが強制されます。

### `src/pkg/crypto/subtle/constant_time.go` の変更

*   `ConstantTimeLessOrEq(x, y int) int` という新しい関数が追加されました。
    *   この関数は、`x <= y` であるかどうかを定数時間で判定し、その結果を1（真）または0（偽）で返します。
    *   実装は `int(((x32 - y32 - 1) >> 31) & 1)` というビット演算を利用しており、入力値の大小関係によって処理時間が変動しないように設計されています。これは、暗号処理におけるタイミング攻撃を防ぐために非常に重要です。

### `src/pkg/crypto/rsa/pkcs1v15_test.go` の変更

*   `TestOverlongMessagePKCS1v15` という新しいテストケースが追加されました。
    *   このテストは、意図的に長すぎる（つまり、パディングが短すぎる）暗号文を `DecryptPKCS1v15` 関数に渡し、エラーが返されることを確認します。
    *   これにより、新しいパディング長チェックが正しく機能していることが検証されます。

### `src/pkg/crypto/subtle/constant_time_test.go` の変更

*   `lessOrEqTests` というテストデータセットと、`TestConstantTimeLessOrEq` というテスト関数が追加されました。
    *   これは、新しく追加された `ConstantTimeLessOrEq` 関数が、様々な入力値に対して期待される結果（1または0）を正しく返すことを検証するためのものです。これにより、定数時間比較関数の正確性が保証されます。

これらの変更により、Go言語のRSA実装はPKCS#1 v1.5の仕様にさらに厳密に準拠し、同時に暗号処理のセキュリティを向上させています。

## 関連リンク

*   [RFC 3447: Public-Key Cryptography Standards (PKCS) #1: RSA Cryptography Specifications Version 2.1](https://datatracker.ietf.org/doc/html/rfc3447) - 特に Section 7.2.1 "RSAES-PKCS1-V1_5-ENCRYPT" と Section 7.2.2 "RSAES-PKCS1-V1_5-DECRYPT" が関連します。
*   [Go言語のcrypto/rsaパッケージ](https://pkg.go.dev/crypto/rsa)
*   [Go言語のcrypto/subtleパッケージ](https://pkg.go.dev/crypto/subtle)

## 参考にした情報源リンク

*   [https://golang.org/cl/9222045](https://golang.org/cl/9222045) (Go Gerrit Code Review)
*   [https://en.wikipedia.org/wiki/PKCS_1](https://en.wikipedia.org/wiki/PKCS_1)
*   [https://en.wikipedia.org/wiki/Timing_attack](https://en.wikipedia.org/wiki/Timing_attack)
*   [https://en.wikipedia.org/wiki/Bleichenbacher%27s_attack](https://en.wikipedia.org/wiki/Bleichenbacher%27s_attack)
*   [https://pkg.go.dev/crypto/rsa](https://pkg.go.dev/crypto/rsa)
*   [https://pkg.go.dev/crypto/subtle](https://pkg.go.dev/crypto/subtle)
*   [https://www.rfc-editor.org/rfc/rfc3447](https://www.rfc-editor.org/rfc/rfc3447)I have generated the detailed technical explanation in Markdown format, following all your instructions and the specified chapter structure. The output is provided directly to standard output as requested.