ChaCha20-Poly1305 および Poly1305 の安全性調査・評価岩田

哲

名古屋大学大学院工学研究科

2017 年 10 月

エグゼクティブサマリー
メッセージ認証コード Poly1305 [Ber05b] および認証暗号化方式 ChaCha20-

Poly1305 [NL15] の安全性調査・評価を行った．
Poly1305 について，次の結果を得た．
• Bernstein による安全性証明 [Ber05b, Ber05a] に問題点は見受けられな
い．Poly1305 は証明可能安全性を有する MAC である．

• 関連鍵攻撃が可能である．しかし人工的な攻撃であり，現実的な脅威とはならないと考えられる．

• 複数ユーザ安全性について，ユーザ数への依存が限定的な安全性バウンドを導出できる．一般に，証明可能安全性の観点からはユーザ数が増加すると敵の攻撃確率の上界がそれに伴い増加するが，Poly1305 では
この増加が限定的である．
また文献調査により，次のことを確認した．

• 弱鍵が存在する．
• 再偽造可能性の意味で耐性がある．
• ナンスを再利用すると多項式ハッシュ関数の鍵を導出でき，偽造攻撃ができる．
また，ChaCha20-Poly1305 について次の結果を得た．

• Procter による [Pro14] の証明には一か所軽微な誤りがあるが簡単に修正可能であり，ChaCha20-Poly1305 は証明可能安全性を有する認証暗号化方式である．

• ChaCha20 ブロック関数が関連鍵攻撃に対して安全であるという仮定のもと，ChaCha20-Poly1305 は関連鍵攻撃に対する安全性を有する．

• 再偽造可能性の意味で耐性がある．
• ナンスを再利用すると偽造攻撃ができる．
• 弱鍵が存在する．
• 復号ミスユース耐性について，暗号化の意味での安全性は失われるが，認証の意味での安全性は保たれる．

• 複数ユーザ安全性について，ユーザ数に依存した自明な安全性バウン
ドを導出できる．また，ユーザ数への依存が限定的な安全性バウンドを導出できると予想される．

Poly1305 と ChaCha20-Poly1305 両方について，ナンスの再利用による安全性への影響は大きく，実装の際にはこれが起こらないよう注意が必要である．弱鍵の影響はどちらも少ないと考えられ，また Poly1305 の関連鍵攻撃が現実的に問題となることはないと考えられる．その他，懸念事項は見受けられない．
なお本報告書は Poly1305 と ChaCha20-Poly1305 のメッセージ認証コードと認証暗号化方式としての理論的な安全性調査・評価を行ったものであり，サイドチャネル攻撃等の実装に関する解析，あるい TLS のプロトコルとしての安全性解析等は扱っていない．

目次
1

はじめに

1

2

準備

1

3

Poly1305 の仕様

2

4

Poly1305 に関する文献調査

44.1

証明可能安全性 . . . . . . . . . . . . . . . . . . . . . . . . . .

4

4.2

安全性解析

. . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

4.2.1

関連鍵攻撃 . . . . . . . . . . . . . . . . . . . . . . . .

6

4.2.2

再偽造可能性 . . . . . . . . . . . . . . . . . . . . . . .

7

4.2.3

ナンス再利用 . . . . . . . . . . . . . . . . . . . . . . .

7

4.2.4

弱鍵 . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

4.3
5

改良版・修正版 . . . . . . . . . . . . . . . . . . . . . . . . . . 10

Poly1305 の安全性評価

11

5.1

証明可能安全性 . . . . . . . . . . . . . . . . . . . . . . . . . . 11

5.2

関連鍵攻撃

5.3

複数ユーザ安全性 . . . . . . . . . . . . . . . . . . . . . . . . . 15

. . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

6

ChaCha20-Poly1305 の仕様

20

7

ChaCha20-Poly1305 に関する文献調査

22

8

7.1

証明可能安全性 . . . . . . . . . . . . . . . . . . . . . . . . . . 22

7.2

その他の文献 . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

ChaCha20-Poly1305 の安全性評価
8.1

証明可能安全性 . . . . . . . . . . . . . . . . . . . . . . . . . . 25

8.2

関連鍵攻撃

8.3

再偽造可能性 . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

8.4

ナンス再利用 . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

8.5

弱鍵 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

8.6

8.7
9

25

. . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

復号ミスユース耐性. . . . . . . . . . . . . . . . . . . . . . . 32

8.6.1

PA 安全性 . . . . . . . . . . . . . . . . . . . . . . . . . 33

8.6.2

INT-RUP 安全性 . . . . . . . . . . . . . . . . . . . . . 34

複数ユーザ安全性 . . . . . . . . . . . . . . . . . . . . . . . . . 36

まとめ

参考文献

39
40

A ChaCha20 ブロック関数の仕様

46

図目次
1

T ← PolyR,K (N, M ) の定義 . . . . . . . . . . . . . . . . . . .
∗3

2⊤/⊥ ← VerR,K (N, M, T ) の定義 . . . . . . . . . . . . . . . .

3

3(C, T ) ← EncK (N, A, M ) と M/⊥ ← DecK (N, A, C, T ) の定義

224Z ← KGenK (N, ℓ) と T ← TagK (N, A, C) の定義 . . . . . . . 23

5

T ← PolyR (Y ) の定義 . . . . . . . . . . . . . . . . . . . . . . 23

6

ChaCha20-Poly1305 の暗号化アルゴリズムの全体像 . . . . . . 24

7

EncK ，DecK ，VerK の定義 . . . . . . . . . . . . . . . . . . . 33

8

ゲーム 0 とゲーム 1 の定義 . . . . . . . . . . . . . . . . . . . . 37

9

ゲーム 2 の定義 . . . . . . . . . . . . . . . . . . . . . . . . . . 38

10QuaterRound(a, b, c, d) の定義 . . . . . . . . . . . . . . . . . . 48

11

QuaterRound(a, b, c, d) の動作 . . . . . . . . . . . . . . . . . . 49

12Z ← CCK (ctr, N ) の定義 . . . . . . . . . . . . . . . . . . . . . 50

表目次
1

関連鍵攻撃に成功するパラメータの例 . . . . . . . . . . . . . . 15

1

はじめに
メッセージ認証コード Poly1305 は Bernstein によって FSE 2005 にて提案された [Ber05b]．また，認証暗号化方式 ChaCha20-Poly1305 は Nir と Langley
により RFC 7539 にて提案され [NL15]，TLS にて利用することが提案されている [LCM+ 16]．本報告書ではこれらのアルゴリズムの安全性調査・評価を報告する．
本書では下記項目を記載する．

• エグゼクティブサマリー• Poly1305 の仕様（3 章）• Poly1305 の安全性評価に関する文献調査（4 章）• Poly1305 に対する新たな安全性評価の検討（5 章）• ChaCha20-Poly1305 の仕様（6 章）• ChaCha20-Poly1305 の安全性評価に関する文献調査（7 章）• ChaCha20-Poly1305 に対する安全性評価の検討（8 章）
安全性評価を行うにあたり，一般的な暗号利用条件を想定したが，特に TLS
での利用が想定されることから，複数ユーザの設定における安全性の検討を行った．予備的な検討段階であるが，敵の攻撃成功確率の上界を導出できるという点で，Poly1305 と ChaCha20-Poly1305 はいずれも複数ユーザの設定
における証明可能安全性を有している．

2

準備
整数 ℓ ≥ 0 に対し，{0, 1}ℓ はすべての ℓ ビットのビット列の集合を表す．また，{0, 1}∗ はすべての有限ビット列の集合を表す．バイトは {0, 1, . . . , 255}の要素を指し，8 ビットのビット列に対応するとする．バイト列 X のバイト
長を len(X) と表記する．バイト列 X と Y の連結を X ∥ Y あるいは XY と表記する．整数 x と ℓ に対し，バイト列 X を ℓ バイトごとに分割する操作をℓ(X[0], . . . , X[x − 1]) ←− X と表記する．ただし X[0], . . . , X[x − 2] は ℓ バイト，1 ≤ len(X[x − 1]) ≤ ℓ であり，X[0], . . . , X[x − 1] の連結 X[0] ∥ · · · ∥ X[x − 1]
が X と一致する．また，空列の分割はこの限りではなく，X が空列の場合はℓX[0] ←− X とし，X[0] は空列であるとする．有限集合 S から一様ランダムに要素を選択し，それを S とすることを S ← S と表記する．16 進数は 0x を$つけて 0x03 などと表記する．

1

Poly1305 の仕様

3

本章ではメッセージ認証コード Poly1305 の仕様を記述する．ブロック暗号
として AES-128 を利用し，Poly1305-AES と表記する．Poly1305-AES はタグ生成関数 Poly とタグ検証関数 Ver からなる．タグ生成に素数 2130 − 5 を法とした多項式演算を用いる．タグ生成関数 Poly の入出力はPoly : KPoly × {0, 1}128 × {0, 1}∗ → {0, 1}128として表される．ただし，KPoly = {0, 1}128 × {0, 1}128 は鍵空間である．秘密鍵 (R, K) ∈ KPoly ，ナンス N ∈ {0, 1}128 ，任意長のメッセージ M を入力としてとり，128 ビット（16 バイト）のタグ T ∈ {0, 1}128 を出力する．

T ← PolyR,K (N, M ) と表記する．
タグ検証関数 Ver の入出力はVer : KPoly × {0, 1}128 × {0, 1}∗ × {0, 1}128 → {⊤, ⊥}である．秘密鍵 (R, K) ∈ KPoly ，ナンス N ∈ {0, 1}128 ，任意長のメッセージ

M ，タグ T ∗ ∈ {0, 1}128 を入力としてとり，T ← PolyR,K (N, M ) を計算し，
T = T ∗ であれば受理を示す ⊤ を返し，T ̸= T ∗ であれば拒否を示す ⊥ を返す．⊤ ← VerR,K (N, M, T ∗ ) や ⊥ ← VerR,K (N, M, T ∗ ) と表記する．

Poly1305-AES = (Poly, Ver) の擬似コードを図 1，図 2 に示す．
鍵

K は AES-128 の秘密鍵であり，R は法を 2130 − 5 とした多項式演算で用いる．R ∈ {0, 1}128 であり，次の制約を満たす．

• 下位バイトから数えて 4 バイト目，8 バイト目，12 バイト目，16 バイ
ト目の上位 4 ビットの値を 0 に固定する．

• 下位バイトから数えて 5 バイト目，9 バイト目，13 バイト目の下位 2ビットの値を 0 に固定する．
言い換えると，バイト列 (R[0], . . . , R[15]) を用いて

R = R[0] + 28 R[1] + · · · + 2120 R[15]として表現するとき，R[3], R[7], R[11], R[15] の上位 4 ビットが 0 であり，したがってこれらは {0, 1, . . . , 15} の値しかとらない．また，R[1], R[8], R[12] の下位 2 ビットが 0 であり，これらは {0, 4, 8, . . . , 252} の値しかとらない．Rは 16 バイトの長さであるが，取りうる値は 2106 通りになる．これにより，法2130 − 5 の多項式演算における計算コストを削減することができる．

2

Algorithm PolyR,K (N, M )16

1. (M [0], . . . , M [m − 1]) ←− M// m = ⌈len(M )/16⌉

2. for i = 1 to m − 1 do
C[i] ← M [i] + 0x01 · 28len(M [i])3.

4. T ← C[0]5. for i = 1 to m − 1 do
T ← R · C[i] mod (2130 − 5)

6.

7. T ← R · T mod (2130 − 1)
8. T ← T + AESK (N ) mod 2128
9. return T
図 1: T ← PolyR,K (N, M ) の定義

Algorithm VerR,K (N, M, T ∗ )1. T ← PolyR,K (N, M )2. if T = T ∗ then return ⊤3. else return ⊥図 2: ⊤/⊥ ← VerR,K (N, M, T ∗ ) の定義

メッセージ

16

メッセージ M を (M [0], . . . , M [m − 1]) ←− M と 16 バイトごとに分割する．ただし，m = ⌈len(M )/16⌉ である（len(M ) は M のバイト長である）．m は M のブロック長を表している．各メッセージブロック M [i]（i = 0, . . . , m − 1）に，それぞれ最上位にバイト 0x01 を付加し，C[i] とする．すなわち，C[i] =

M [i] + 0x01 · 2128

for i = 0, . . . , m − 2

M [i] + 0x01 · 28len(M [i])for i = m − 1とする．C[1], . . . , C[m − 2] は 17 バイトであり，各 C[i] は M [i] よりも 1 バ
イト長くなる．
多項式ハッシュ関数

R と C[1], . . . , C[m − 1] を用いて，ハッシュ値 HR (M )を次のように計算する．

HR (M ) = C[0] · Rm + C[1] · Rm−1 + · · · + C[m − 1] · R mod (2130 − 5)3

ただし，R と各 C[i] をリトルエンディアンで表現された符号なし整数とみなして演算を行う．
ハッシュ値 HR (M ) と，鍵 K ，ナンス N から次のようにタグ T ←PolyR,K (N, M ) を生成する．

タグ生成

T = HR (M ) + S mod 2128
だたし S = AESK (N ) である．最後に T を出力する．

Poly1305 に関する文献調査4

本章では Poly1305 に関する文献調査の報告をする．4.1 章で提案論文における証明可能安全性を扱い，安全性解析について，関連鍵攻撃，再偽造可能性，
ナンス再利用，弱鍵についてそれぞれ 4.2.1 章，4.2.2 章，4.2.3 章，4.2.4 章
で扱う．また，改良版，修正版を 4.3 章で扱う．

4.1

証明可能安全性

Poly1305 の証明可能安全性は提案論文 [Ber05b] にて示されている．Poly1305
はナンスを用いる MAC であり，敵はタグ生成オラクルとタグ検証オラクルにアクセスできる．

• タグ生成オラクルは鍵 (R, K) を保持しており，入力 (N, M ) に対し，タグ T ← PolyR,K (N, M ) を返す．

• タグ検証オラクルも同じ鍵 (R, K) を保持しており，入力 (N, M, T ∗ ) に対し，T ← PolyR,K (N, M ) を計算し，T = T ∗ であれば受理を示す ⊤を返し，T ̸= T ∗ であれば拒否を示す ⊥ を返す．⊤ は偽造成功に対応
し，⊥ は偽造失敗に対応する．
敵 A の目標は一度でも検証オラクルが ⊤ を返すことである．ただし，A はタグ生成オラクルに対して同じナンスを繰り返し使用してはならず，また鍵(R, K) は適切な空間から一様ランダムに選択されているとする．また一般性を失うことなく，タグ生成オラクルがクエリ (N, M ) に対して T を返したな
らば，それ以降 (N, M, T ) を検証オラクルにクエリせず，さらに，クエリは繰り返さないものとする．
次の定理が示されている．
定理 1 ([Ber05b]) 高々q 回タグ生成オラクルにアクセスし，高々q ′ 回タグ検証オラクルにアクセスする敵 A を考える．ただし，各クエリの M の長さ

4

は高々ℓ バイトであるとする．また q + q ′ 回のクエリをする任意の敵 B に対し，AESK (·) と 128 ビット上のランダム置換 P (·) の識別成功確率が高々δ であると仮定する．このとき，タグ検証オラクルが A の高々q ′ 回のクエリをすべての拒否し，すべてに対して ⊥ を返す確率は少なくとも1−δ−(1 − q/2128 )−(q+1)/2 × 8q ′ ⌈ℓ/16⌉
2106

(1)

である．
式 (1) は q ≤ 264 のとき，敵が一度でも偽造攻撃に成功する確率が高々δ+

1.649 · 8q ′ ⌈ℓ/16⌉
14q ′ ⌈ℓ/16⌉
<δ+
106
2
2106

(2)

であることを示している．式 (2) の右辺が q に依存しないことは注目に値する．
定理 1は次の補題を用いて示される．
補題 1 ([Ber05b]) M と M ′ を，長さが高々ℓ バイトである互いに異なるメッセージとする．Z を任意の 16 バイト列とする．このとき，HR (M ) =HR (M ′ ) + Z を満たす R ∈ {0, 1, . . . , 2130 − 6} は高々8⌈ℓ/16⌉ 通りである．ただし，加算は法 2128 上で定義される．
補題 1は R が要素数 2106 の空間から一様ランダムに選択されるとき，[HR (M ) − HR (M ′ ) = Z] ≤Pr$

R←RPoly8⌈ℓ/16⌉2106ということを示しており（ただし，演算は mod 2128 で定義される），Poly1305
で使用される多項式ハッシュ関数の差分確率の上界を与えている．ここで，RPoly は Poly の鍵空間 KPoly のうち，R の取りうる集合に対応する．
この性質はユニバーサルハッシュ関数として定式化されている [CW79]．一
般に，F : KF × D → R を鍵付きハッシュ関数とする．KF は有限の鍵集合，

D は定義域，R は値域である．R が 2 項演算 + について可換群をなすとし，その逆演算を − と表記する．このとき，任意の異なる M, M ′ ∈ D と，任意の Z ∈ R に対し，差分確率について

Pr [FK (M ) − FR (M ′ ) = Z] ≤ ϵ
$

K ←KF

が成り立つとき，F は ϵ-A∆U（ϵ-almost-∆-ユニバーサル）ハッシュ関数という [Sti95]．とくに，R が {0, 1}n であり演算として排他的論理和 ⊕ を考えるとき，F を ϵ-AXU（ϵ-almost-XOR-ユニバーサル）ハッシュ関数という[Kra94]．
差分確率の小さなハッシュ関数 HR (·) とナンスを用いて T = HR (M ) +AESK (N ) としてタグを生成する方法は，安全な MAC の構成法として知られており [Sho96, Ber05a]，これと補題 1を組み合わせることにより，定理 1が
得られる．

5

4.2

安全性解析

4.2.1

関連鍵攻撃

一般に，F : KF × D → R を鍵付き関数とし，KF を有限の鍵集合，Dを定義域，R を値域とする．F に対する関連鍵攻撃では，関連鍵導出関数（RKD 関数，related-key derivation function）の集合 Φ = {φ} を考える．

φ : KF → KF であり，敵はこの集合内の関数を用いて鍵に変更を加えることができると仮定する．例として，KF = {0, 1}n のとき，Φ⊕ = {XOR∆ | K 7→ K ⊕ ∆, ∆ ∈ KF }あるいは

Φ+ = {Add∆ | K 7→ K + ∆ mod 2n , ∆ ∈ KF }が挙げられる．敵は任意に選択した ∆ ∈ KF に対して FK⊕∆ (·) や FK+∆ (·)にアクセスできることを意味する．
ユニバーサルハッシュ関数に基づく MAC に対する関連鍵攻撃は Wang ら
により解析されている [WLZZ16]．Poly1305 はこの枠組みの範疇である．
例として，n = 128 とし，鍵を (R, K) ∈ {0, 1}128 × {0, 1}128 ，2 ブロックのメッセージ M = (M [0], M [1]) に対し，

T = (M [0] · R2 ⊕ M [1] · R) ⊕ AESK (N )で定義される MAC を考える．ただし 1 ブロックは n = 128 ビットであり，演算は GF(2n ) で定義されるとする．M [0] = M [1] とし，RKD 関数の集合として Φ⊕ を考える．敵が関連鍵 (R′ , K ′ ) = (R ⊕ 0n−1 1, K) に対する (N, M )をタグ生成オラクルにクエリすると，オラクルはT = (M [0] · (R ⊕ 0n−1 )2 ⊕ M [1] · (R ⊕ 0n−1 )) ⊕ AESK (N )= (M [0] · R2 ⊕ M [1] · R) ⊕ AESK (N )を敵に返す．これは元の鍵 (R, K) に対する (N, M ) のタグと一致し，偽造攻撃に成功する．

Wang らはこれと同様の攻撃が Poly1305 に対して適用可能であると述べている [WLZZ16] が，法 2130 − 5 上で定義される多項式ハッシュ関数では上記にある (R + 1)2 = R2 + 1 のような等式は成り立たず，この例によって Poly1305が攻撃可能であるかどうかは定かではない．
一方で，5.2 章で示すように，入力メッセージを適切に選べば偽造攻撃が可能である．あるいはより複雑な RKD 関数の集合を許すことにより偽造攻撃が可能である．
一般に算術演算に基づく MAC では多くの場合関連鍵攻撃が可能である．一方，ブロック暗号のような要素技術のみに基づく MAC では，ブロック暗号

6

自体が関連鍵攻撃に対する安全性を有するという仮定により，方式全体の関連鍵攻撃に対する安全性を証明できる場合が多い．したがって，一般に算術演算に基づく MAC の方がブロック暗号のような要素技術のみに基づく MAC
よりも関連鍵攻撃に対する耐性が低いと考えられる．
ただし，ここで取り上げたような関連鍵攻撃のシナリオは制約が強く，現実に成立する可能性は低いと考えられ，このことが実際に問題となるようなことはないと考えられる．しかし，関連鍵攻撃のシナリオが成立しないよう
使用方法に注意すべきである．

4.2.2

再偽造可能性

MAC に対する再偽造不可能性は Black らにより提案された安全性概念である [BC09]．例として CBC MAC [BKR00] や PMAC [BR02] のような確定的な MAC を考える．仮に敵が偽造に成功，あるいは出力の衝突に成功したと仮定し，その後別の偽造に成功するのにどれだけの計算量が必要かにより安全性を評価する．理想的なランダム関数 F であれば，2 つのメッセージ Mと M ′ の衝突 F (M ) = F (M ′ ) はそれら以外の衝突ペアを入手するのには役に立たない．しかし CBC MAC では衝突ペア M と M ′ からさらなる衝突ペアを得るのは容易である．

Poly1305 の再偽造可能性は [BC09] にて解析されている．Poly1305 はナンスを用いる MAC であり，PolyR,K (N, M ) = PolyR,K (N ′ , M ′ )を満たすナンスとメッセージのペア ((N, M ), (N ′ , M ′ )) が得られたとしても（ただし N ̸= N ′ ），それ以外の衝突を得るのには役に立たない．したがって [BC09] の枠組みでは Poly1305 は再偽造可能性の意味で理想的な MAC と同等の安全性を有する．一方で，N = N ′ が満たされるような場合には次の4.2.3 章にあるようにハッシュ鍵を導出でき，偽造攻撃が可能となる．

4.2.3

ナンス再利用Poly1305 はナンスを用いる MAC であり，タグ生成オラクルに対して同じナンスを繰り返してはならない．このことは提案論文 [Ber05b] において強調して述べられており，実際ナンスが繰り返すような攻撃シナリオを考えると，容易にハッシュ鍵を導出できることが [BC09] にて述べられている．
敵が (N, M ) と (N, M ′ ) をタグ生成オラクルにクエリすると（ただし M ̸=

M ′ ），タグ生成オラクルはT = HR (M ) + AESK (N ) mod 2128

7

および

T ′ = HR (M ′ ) + AESK (N ) mod 2128
を敵に返す．したがってHR (M ) − HR (M ′ ) ≡ T − T ′(mod 2128 )(3)が成り立ち，これは R を未知変数とする高々max{m, m′ } 次の合同方程式とみなせる．ここで m = ⌈len(M )/16⌉，m′ = ⌈len(M ′ )/16⌉ である．式 (3) を直接解けば R（の候補）が求まる．
例えば M = 0x01，M ′ = 0x00 とし，ナンス N に対するそれぞれのタグを

T と T ′ とすると，⌈len(M )⌉ = ⌈len(M ′ )⌉ = 1 であるから m = m′ = 1 となり，
HR (M ) = (28 + 20 ) · R mod (2130 − 5) と HR (M ′ ) = 28 · R mod (2130 − 5)となる．これらから，((28 + 20 ) · R mod (2130 − 5)) − (28 · R mod (2130 − 5))≡ T − T′(mod 2128 )が得られる．高い確率で (28 + 20 ) · R < 2128 < 2130 − 5 が成り立ち，この場合

R = T − T ′ mod 2128
であるから R が求まる．

M や M ′ を敵が選択せず，より長い場合や，あるいは長さが異なる場合であっても一般に式 (3) を効率的に解くことが可能である．また，式 (3) が複数ある場合には，連立合同方程式を解く代わりに多項式の GCD を計算する
ことによって R を導出できる．
ナンスの再利用による安全性の低下は顕著であり，このことが起こらない
よう実装には注意が必要である．

4.2.4

弱鍵

多項式ハッシュ関数の弱鍵は Handschuh と Preneel により [HP08] にて議論されている．一般に，暗号方式に対して鍵空間全体の部分集合 S を考える．
未知の鍵がその集合 S に属するときに暗号方式が予期しない挙動を示し，なおかつ未知の鍵がその集合 S に属するかどうかを判定することが容易なとき，その S を弱鍵集合という．

MAC の場合は予期しない挙動は偽造成功確率が平均よりも大幅に高いことなどを意味する．また，その鍵の集合 S の要素数が s であるとき，未知の
鍵が S に属するかどうかを8• s 通りの鍵を試す全数探索よりも効率的に• かつ，s 回の検証オラクルのアクセスよりも効率的に判定できなければならない．

Poly1305 の場合，R = 0 のみからなる集合は弱鍵集合となる [HP08]．この場合任意の M に対してHR (M ) = 0
が成立する．したがって，タグ生成オラクルが生成した任意の (N, M, T ) に対し，(N, M ′ , T ) は検証オラクルに確率 1 で受理される．ここで，M ′ は Mとは異なる任意のメッセージである．ただし R = 0 の生起確率が低いため，
実際にこのことが問題となることはない [HP08]．
この解析は Saarinen [Saa12] と Procter と Cid [PC13, PC15] により一般化されている．また，[ABBT15] においても一般化されている．Procter とCid [PC13, PC15] の要点は，多項式ハッシュ関数を用いた MAC において
は，鍵空間のあらゆる部分集合が弱鍵集合になる，というものである．R をハッシュ関数 H の未知の鍵，Q = (Q[0], . . . , Q[ℓ − 1]) とし，多項式∑

Q(X) =

Q[i] · X ℓ−i0≤i≤ℓ−1を考える．Q(X) = 0 が R を根として持つとき，Q(X) を偽造多項式という．

Poly1305 の文脈では演算はすべて法 2130 − 5 上で定義される．
ここでHR (M ) = C[0] · Rm + C[1] · Rm−1 + · · · + C[m − 1] · R mod (2130 − 5)∑=C[i] · Rm−i mod (2130 − 5)0≤i≤m−1に対し m = ℓ とすると，

HR (M ) + Q(R) = HR (M )であり，HR (M ) + Q(R) =∑(C[i] + Q[i]) · Rm−i mod (2130 − 5)0≤i≤m−1= HR (M + Q)
であるから，(N, M ) に対する鍵 (R, K) のタグ T は，(N, M ′ ) に対する鍵(R, K) の MAC にもなっている．ただし，
M ′ = M + Q = (M [0] + Q[0], . . . , M [ℓ − 1] + Q[ℓ − 1])9である．この偽造は確率 1 でタグ検証オラクルに受理される．
また，未知の鍵 R が鍵集合 S に属するかどうかのテストは，偽造多項式

Q(X) = ΠS∈S (X − S) を用いて検証オラクルにクエリをすればよく，これはS のサイズによらない．Poly1305 におけるメッセージから多項式ハッシュ関数への変換のフォーマットに矛盾しないことが必要であるが，このことは限られた場合にしか問題とはならない．したがって，Poly1305 においては任意のサイズの弱鍵集合が存在する．また，Procter と Cid はこれを鍵回復攻撃に応用している [PC13, PC15]．
弱鍵集合のサイズが s のとき，その鍵が実際に使われる確率は s/2106 となる．また，これをテストするための偽造多項式の次数は s であるため，タグ検証オラクルへのクエリの長さも s となる．s/2106 が実際に問題となるような大きな確率となるためには s を大きくとる必要があり，この場合クエリの長さも s となる．たとえば鍵が使用される確率を 2−32 とする場合，s は 274となり，クエリするメッセージの長さが 274 ブロックになる．
したがって，Poly1305 においては任意のサイズの弱鍵集合が存在するものの，現実的には大きな問題とはならないと考えられる．
なお多項式ハッシュ関数を用いた MAC に対する弱鍵は，一般にブロック
暗号において議論される弱鍵，あるいは等価鍵とは位置づけが異なる．鍵長 k
ビット，ブロック長 n ビットのブロック暗号 E : {0, 1}k × {0, 1}n → {0, 1}nにおける等価鍵は，任意の M ∈ {0, 1}n に対して等号 EK (M ) = EK ′ (M ) が成立する鍵のペア (K, K ′ ) のことをいう．この場合全数探索にかかる計算量が 2k を下回るため，ブロック暗号における等価鍵の存在は，そのブロック暗号が鍵長相当の安全性を有していないことを直接意味する．
一方 MAC においては一つの鍵が鍵空間から一様ランダムに選択され，その鍵の下で偽造成功確率が低いことを目的に設計されるものであり，弱鍵集合の存在自体が MAC の直接的な安全性に影響するものではない．

4.3

改良版・修正版

Wang らは Poly1305 の鍵を 16 バイトまで削減した IPMAC を提案している [WLW06a]．IPMAC は Poly1305 同様ナンスベースの MAC であり，多項式ハッシュ関数用の鍵 R を R = EK (0n ) とすることで，Poly1305 から得られる．ただし，ナンス空間から 0n が除外されなければならない．AES が擬似ランダム置換との仮定のもと，IPMAC が証明可能安全であることが示されており，敵の偽造成功確率の上界が次の式で与えられることが証明されている [WLW06a]．

q(q + 1) 8⌈ℓ/16⌉
+
(4)
2129
2128
ただし，q はタグ生成オラクルへのアクセス回数，ℓ はタグ生成オラクルへのδ+

クエリにおける M の最大バイト長を表し，敵は 1 度だけタグ検証オラクル

10

にアクセスする．また，δ は高々q + 1 回のクエリをする任意の敵 B に対し，

AESK (·) と 128 ビット上のランダム置換 P (·) の識別成功確率の上界を表す．
式 (4) の導出においては R の特定のビットを 0 にすることは考慮されておらず，このため成功確率の分母が 2128 となっている．
また，Wang らは Poly1305 の鍵を 16 バイトまで削減し，なおかつナンスを必要としない OPMAC（One-Key Poly1305）を提案している [WLW06b]．
これは T ← HR (M ) + AESK (N ) mod 2128 とするかわりにT ← AESK (HR (M ) mod 2128 )とし，R = EK (0n ) とすることで Poly1305 から得られる．OPMAC は確定
的 MAC であり，AES が擬似ランダム置換との仮定のもと，証明可能安全であることが示されている [WLW06b]．敵の偽造成功確率の上界は次の式で与
えられる．

δ+

(q + 2)2 (1 + 8⌈ℓ/16⌉)
1
+ 128
2129
2

(5)

記号は式 (4) と同一であり，R の特定ビットを 0 にすることを考慮していない．
一般に式 (5) で与えられる上界は式 (1) や式 (4) よりも劣っている．しかし，Poly1305 と IPMAC はナンスが繰り返さないことに安全性の根拠を置いており，OPMAC はナンスの管理が不要であるという長所がある．

Poly1305 の安全性評価

5

本章では Poly1305 の安全性評価を報告する．5.1 章で証明可能安全について考え，5.2 章では関連鍵攻撃を扱う．5.3 章では複数ユーザ安全性を考える．

5.1

証明可能安全性

Bernstein による一連の証明 [Ber05b, Ber05a] に問題点は見受けられず，
Poly1305 は証明可能安全性を有する MAC である．

5.2

関連鍵攻撃

本章では，4.2.1 章で紹介した Wang らの関連鍵攻撃について，適切に入力
メッセージを選択すれば Poly1305 に対する偽造攻撃が可能であることを示す．RKD 関数（関連鍵導出関数）の集合として

Φ = {(a, b) | R 7→ aR + b mod (2130 − 5)}を考える．敵は定数 a, b に対して R 7→ aR + b mod (2130 − 5) という操作が可能である．

11安全性定義安全性の定義について，敵はタグ生成オラクルと，タグ検証オ

ラクルにアクセスできる．

• タグ生成オラクルは ((a, b), N, M ) を入力として受け取り，タグ T ←PolyaR+b,K (N, M ) を敵に返す．
• タグ検証オラクルは ((a, b), N, M, T ∗ ) を入力として受け取り，タグ T ←PolyaR+b,K (N, M ) を計算し，T = T ∗ であれば受理を示す ⊤ を返し，T ̸= T ∗ であれば拒否を示す ⊥ を返す．
敵の攻撃目標はタグ検証オラクルが ⊤ を一度でも出力することである．ただし，敵はタグ生成オラクルに対して同じ (a, b) を用いる場合はナンスを繰り返してはならず，タグ生成オラクルがクエリ ((a, b), N, M ) に対して T を返したならばそれ以降 ((a, b), N, M, T ) を検証オラクルにクエリせず，また，ク
エリは繰り返さないものとする．
まず (a, b) = (1, 1) のときの攻撃が可能であることを示す．
関連鍵攻撃（(a, b) = (1, 1) の場合） メッセージ M = (M [0], M [1]) と M ′ =(M ′ [0], M ′ [1]) を次のように定める．
• M [0] = 2128 − 3• M [1] = 2128 − 3• M ′ [0] = 2128 − 3• M ′ [1] = 2128 − 2
このとき，先頭に 1 バイトの 0x01 を付加した値をそれぞれ C = (C[0], C[1])と C ′ = (C ′ [0], C ′ [1]) とすれば，• C[0] = 2 × 2128 − 3• C[1] = 2 × 2128 − 3• C ′ [0] = 2 × 2128 − 3• C ′ [1] = 2 × 2128 − 2となる．M のハッシュ値は HR (M ) = C[0] · R2 + C[1] · R mod (2130 − 5) であり，M のハッシュ値は HR (M ′ ) = C ′ [0] · R2 + C ′ [1] · R mod (2130 − 5) である．
このとき，HR (M ) = HR+1 (M ′ )，すなわち

C[0] · R2 + C[1] · R ≡ C ′ [0] · (R + 1)2 + C ′ [1] · (R + 1)

12

(mod 2130 − 5)

が成り立つ．実際，右辺はC[0] · R2 + C[1] · R≡ (2 × 2128 − 3) · R2 + (2 × 2128 − 3) · R(mod 2130 − 5)であり，左辺はC ′ [0] · (R + 1)2 + C ′ [1] · (R + 1)
≡ (2 × 2128 − 3) · (R + 1)2 + (2 × 2128 − 2) · (R + 1)

(mod 2130 − 5)

≡ 右辺 + (2 × 2128 − 3)(2R + 1) + (2 × 2128 + R − 2) (mod 2130 − 5)
≡ 右辺 + (4 × 2128 − 5)R + (2 × 4128 − 5) (mod 2130 − 5)
≡ 右辺である．したがって HR (M ) = HR+1 (M ′ ) が成り立つ．

(N, M ) の鍵 (R, K) に対するタグ T が，(N, M ′ ) の鍵 (R + 1, K) に対するタグと一致するので，敵は ((1, 1), N, M ′ ) をタグ生成オラクルにクエリし Tを得たのち，((1, 0), N, M, T ) をタグ検証オラクルにクエリすることで偽造攻撃に成功することができる．
次に一般の場合を考える．
関連鍵攻撃（一般の場合） (a, b) = (1, 1) の場合と同様に，メッセージ M =(M [0], M [1]) と M ′ = (M ′ [0], M ′ [1]) に対し，先頭に 1 バイトの 0x01 を付加した値をそれぞれ C = (C[0], C[1]) と C ′ = (C ′ [0], C ′ [1]) とする．M のハッ
シュ値は HR (M ) = C[0] · R2 + C[1] · R mod (2130 − 5) であり，M のハッ
シュ値は HR (M ′ ) = C[0] · R2 + C[1] · R mod (2130 − 5) である．
ここで，次の条件を満たす a, b, C = (C[0], C[1]), M = (M [0], M [1]), C ′ =(C ′ [0], C ′ [1]), M ′ = (M ′ [0], M ′ [1]) を考える．
条件 1 C[0] = 0x01 ∥ M [0]
条件 2 C[1] = 0x01 ∥ M [1]
条件 3 C ′ [0] = 0x01 ∥ M ′ [0]
条件 4 C ′ [1] = 0x01 ∥ M ′ [1]
条件 5 C[0] ≡ a2 C ′ [0] (mod 2130 − 5)
条件 6 C[1] ≡ 2abC ′ [0] + aC ′ [1] (mod 2130 − 5)
条件 7 bC ′ [0] + C ′ [1] ≡ 0 (mod 2130 − 5)
このとき，HR (M ) = HaR+b (M ′ )，すなわち

C[0] · R2 + C[1] · R ≡ C ′ [0] · (aR + b)2 + C ′ [1] · (aR + b)
13

(mod 2130 − 5)

が成り立つ．条件 1 から 4 は M と M ′ から C と C ′ の変換に関するフォー
マットの規則を表しており，条件 5 から 7 はこの式が R に関する恒等式になることを意味している．
実際に，右辺 − 左辺 を整理すると(a2 C ′ [0] − C[0])R2 + (2abC ′ [0] + aC ′ [1] − C[1])R + (b2 C ′ [0] + bC ′ [1]) ≡ 0となる．各条件は係数が 0 であることを保証しており，恒等式になっていることが確かめられる．したがって HR (M ) = HaR+b (M ′ ) が成り立つ．
これは (N, M ) の鍵 (R, K) に対するタグ T が，(N, M ′ ) の鍵 (aR + b, K)に対するタグと一致することを意味する．敵は ((a, b), N, M ′ ) をタグ生成オラクルにクエリし T を得たのち，((1, 0), N, M, T ) をタグ検証オラクルにク
エリすることで偽造攻撃に成功することができる．
上記の条件を満たす a, b, M [0], M [1], M ′ [0], M ′ [1] の導出方法について， mod(2130 − 5) 上で定義される連立合同方程式
 128

2 + M [0] ≡ a2 (2128 + M ′ [0])






2

128

+ M [1] ≡ 2ab(2128′+ M [0]) + a(2

(6)
128

′

+ M [1])b(2128 + M ′ [0]) + (2128 + M ′ [1]) ≡ 0

(7)
(8)

を考える．

1. a と M ′ [0] を適当に与えると，式 (6) から M [0] が一意に定まる．
2. この M ′ [0] に対し b を適当に定めると式 (8) から M ′ [1] が得られる．
3. これまでに定めた a, b, M ′ [0], M ′ [1] から式 (7) より M [1] が定まる．これらの値が mod 2128 の要素となっていれば攻撃成功である．
これはいつでも成功するわけではないが，実際に多くのパラメータを導出することができる．
たとえば a = 55 と M ′ [0] = 2128 − 3 とすると，式 (6) からM [0] = 340282366920938463463374607431768209941= 2128 − 1515となる．ただし，10 進数で表記している．b = 3 としてこれらを式 (8) に代入すると

M ′ [1] = 340282366920938463463374607431768211455= 2128 − 1を得る．最後に式 (7) から

M [1] = 340282366920938463463374607431768211371= 2128 − 8514

表 1: 関連鍵攻撃に成功するパラメータの例

a

55

b

1
− 15152 − 30

128

M [0]
M [1]

2

128

M ′ [0]2128 − 3

M ′ [1]2128 − 2

a

61

b

1
128

M [0]

2

M [1]

2

− 5584128− 94

M ′ [0]2128 − 4

M ′ [1]2128 − 1

a

99

b
M [0]

1
2

128

− 14704

M [1]2128 − 151

M ′ [0]2128 − 4

M ′ [1]2128 − 1を得る．いずれも 2128 未満であり，攻撃に成功する．その他の攻撃に成功す
るパラメータの例を表 1 に示す．
したがって定数 a, b に対して R 7→ aR + b mod (2130 − 5) といった操作を行うことができる敵は Poly1305 の偽造が可能である．一方で，関連鍵攻撃の成立可能性については鍵にどのような操作を行うことができるか，すなわ
ち RKD 関数の集合の定義が重要であり，ここで挙げたような算術演算を用いる例は人工的であり，現実的な脅威とはならないと考えられる．

5.3

複数ユーザ安全性

複数ユーザが存在するときの共通鍵暗号の安全性は近年になって盛んに研究されている [BBT16, CMS11, HT16, HT17, FJM14, LMP17, ML15, ST16]．
まず Chatterjee ら [CMS11] による MAC の複数ユーザ安全性を定義する．

H : KH × D → {0, 1}n を MAC とする．KH は鍵空間，D は定義域，タグは T ∈ {0, 1}n であり，確定的な MAC を考えている．シングルユーザの設定においては，敵 A はタグ生成オラクルに M をクエリしタグ T = HK (M ) を受け取る．敵は偽造文 (M ′ , T ′ ) を出力する．A の目的は検証に受理されるよ15うな，すなわち T ′ = HK (M ′ ) であるような (M ′ , T ′ ) を出力することである．
この安全性を MAC1 安全性という．敵 A は，実行時間 t，確率 ϵ で偽造に成功するとき，H を MAC1 の意味で (t, ϵ)-break するという．H を (t, ϵ)-break
するような敵が存在しないとき，H は MAC1 の意味で (t, ϵ)-安全であるという．
複数ユーザ設定においては，まず U 個の独立な鍵 K1 , . . . , KU が選ばれ，これらはユーザ 1 から U に対応する．敵 A は次のようにオラクルにアクセスする．すなわち，クエリ (i, M ) に対し（ただし i ∈ {1, . . . , U } であり，M ∈ Dである），タグ生成オラクルは T = HKi (M ) を返す．さらに敵はオラクルを

corrupt することができ，任意の i ∈ {1, . . . , U } に対してその鍵 Ki を得ることができる．敵の目標は次を満たす (i, M, T ) を出力することである．

• i ∈ {1, . . . , U } であり，M ∈ D である• オラクル i は corrupt されていない• HKi に対して M をクエリしていない• T = HKi (M )この安全性を MAC*安全性という．敵 A は，実行時間 t，確率 ϵ で偽造に成功するとき，H を MAC*の意味で (t, ϵ)-break するという．H を (t, ϵ)-break す
るような敵が存在しないとき，H は MAC*の意味で (t, ϵ)-安全であるという．

Chatterjee らは MAC が MAC1 の意味で (t, ϵ)-安全であれば，MAC*の意
味で (t, ϵU )-安全であることを示している [CMS11]．
ナンスを用いる MAC についても同様に安全性定義，安全性証明が可能である．この場合，各ユーザについてナンスを再利用することはできないが，異なるユーザ間で同じナンスを利用することは許される．H : KH ×N ×D → {0, 1}nをナンスを用いる MAC とする．KH は鍵空間，N はナンス空間，D は定義
域，タグは T ∈ {0, 1}n である．
シングルユーザの設定においては，敵 A はタグ生成オラクルに (N, M ) をクエリしタグ T = HK (N, M ) を受け取る．A の目的は T ′ = HK (N ′ , M ′ ) であるような (N ′ , M ′ , T ′ ) を出力することである（MAC1 安全性）．敵 A は，
実行時間 t，確率 ϵ で偽造に成功するとき，H を MAC1 の意味で (t, ϵ)-break
するという．H を (t, ϵ)-break するような敵が存在しないとき，H は MAC1の意味で (t, ϵ)-安全であるという．
複数ユーザ設定において，U 個の独立な鍵 K1 , . . . , KU が選ばれる．敵 A
は，クエリ (i, N, M ) に対し（ただし i ∈ {1, . . . , U }，N ∈ N ，M ∈ D である），タグ生成オラクルは T = HKi (N, M ) を返す．ただし，同じオラクル iに N を繰り返し用いてはならない．さらに敵はオラクルを corrupt することができ，任意の i ∈ {1, . . . , U } に対してその鍵 Ki を得ることができる．敵の目標は次を満たす (i, N, M, T ) を出力することである．

16

• i ∈ {1, . . . , U }，N ∈ N ，M ∈ D である• オラクル i は corrupt されていない• HKi に対して (N, M ) をクエリして T を得ていない• T = HKi (N, M )この安全性を MAC*安全性という．敵 A は，実行時間 t，確率 ϵ で偽造に成功するとき，H を MAC*の意味で (t, ϵ)-break するという．H を (t, ϵ)-break す
るような敵が存在しないとき，H は MAC*の意味で (t, ϵ)-安全であるという．

[CMS11] と同じ議論により，敵の攻撃成功確率は上界はシングルユーザにおける成功確率の上界の U 倍となる．実際，次にように帰着できる．A を H
を MAC*の意味で (t, ϵ)-break する敵とする．この A を用いて，H に対してMAC1 の意味で偽造攻撃をする B を構成する．
• B は A が偽造を行うインデックス j ∈ {1, . . . , U } を一様ランダムに選択する．

• B は i ∈ {1, . . . , U }, i ̸= j に対応するユーザの鍵 Ki を一様ランダムに選択する．ユーザ j の鍵は B のタグ生成オラクルが保持している鍵 K
である．

• B は A を実行する．ユーザ i ̸= j に対する corrupt クエリとタグ生成ク
エリ (i, N, M ) に対しては自身が保持する Ki を用いる．

• ユーザ j に対するタグ生成クエリは自身のタグ生成オラクルに問い合わせをする．ユーザ j に対する corrupt クエリは攻撃失敗である．

• A が (j, N, M, T ) を出力したら，B は (N, M, T ) を出力して終了する．
そうでなければ B は攻撃失敗である．

A の動作は B がユーザ j を corrupt しない限り j の値とは独立である．したがって，A が攻撃に成功し，なおかつ B が j を正しく推測する確率は ϵ/U であるから，B は H を MAC1 の意味で (t, ϵ/U )-break する．したがって，Hが MAC1 の意味で (t, ϵ)-安全であれば，MAC*の意味で (t, ϵU )-安全である．

Poly1305 においては，式 (2) より，ユーザ数が U であれば敵の攻撃成功確
率は高々

(
U

14⌈ℓ/16⌉
δ+
2106

)
(9)

となる．ただし q ≤ 264 と仮定した．また，q はタグ生成オラクルへのアクセス∑総数の最大値（ユーザ i に qi 回アクセスするようであれば， 1≤i≤U qi ≤ q ），タグ検証オラクルへは [CMS11] の安全定義に従い 1 度だけアクセスすることとし，ℓ はクエリのメッセージの最大バイト長を表す．

17

式 (9) は Poly1305 の複数ユーザが存在する場合の敵の攻撃成功確率の上界を与えており，この意味で Poly1305 は複数ユーザの設定においても証明可能
安全性を有している．
一方で，いくつかの暗号方式においては複数ユーザの安全性がシングルユー
ザの安全性から低下しない，あるいは限定的な影響しかない場合があることが知られている [BBT16, HT16, HT17, LMP17, ML15, ST16]．
例えば，Luykx らは複数ユーザにおける PRP-PRF switching lemma の解析を示している [LMP17]．シングルユーザにおける PRP-PRF switchinglemma は，
P
F
AdvprfPerm(n) (A) = Pr[A ⇒ 1] − Pr[A ⇒ 1]として，

AdvprfPerm(n) (A) ≤0.5q 22nを示している [BR06]．ここで，P ← Perm(n) は {0, 1}n 上のランダム置換，$F ← Func(n) は {0, 1}n から {0, 1}n へのランダム関数，q は A のクエリ回数$を表す．Perm(n) は {0, 1}n 上のすべての置換の集合，Func(n) は {0, 1}n から{0, 1}n へのすべての関数の集合である．複数ユーザの PRP-PRF switchinglemma は，ユーザ数を U として
P1 ,...,PU
Advmu-prf⇒ 1] − Pr[AF1 ,...,FU ⇒ 1]
Perm(n) (A) = Pr[Aを考える（上記のように利得関数に mu-をつけて複数ユーザを考えていることを表す）．
自明な証明手法に従えばAdvmu-prf
Perm(n) (A) ≤ U

0.5q 22nが上界として得られるが，0.5q 2(10)2nとなることが示せる [LMP17]．ただし，q は A のクエリの総数の最大値であAdvmu-prf
Perm(n) (A) ≤る．また Luykx らは [LMP17] において Wegman-Carter 認証コードを解析しており，Poly1305 はこの枠組みにあてはまる．

H : KH × D → R を鍵付きハッシュ関数，KH は有限の鍵集合，D は定義
域，R は値域であり，2 項演算 + について群であるとし，その逆演算を − とする．また，F : R → R をランダム関数とする．
このとき，Wegman-Carter 認証コード WC = (Tag, Ver) は次のように定義される．タグ生成関数 Tag はナンス N ∈ R とメッセージ M ∈ D，鍵K ∈ KH , F に対し，
T = HK (M ) + F (N )18

を出力する．T ← TagK,F (N, M ) と表記する．検証アルゴリズム Ver は鍵 Kと F を保持しており，入力 (N, M, T ∗ ) に対し T ← TagK,F (N, M ) を計算し，

T = T ∗ であれば ⊤ を，そうでなければ ⊥ を返す．
このシングルユーザ安全性は
TagK,F ,VerK,FAdvauthforges]WC (A) = Pr[Aと定義される．A forges はタグ検証オラクルが一度でも ⊤ を返すイベントである．複数ユーザの安全性はAdvmu-auth(B) = Pr[B TagK1 ,F1 ,VerK1 ,F1 ,...,TagKU ,FU ,VerKU ,FU forges]WCと定義される．この場合の B forges はいずれかのタグ検証オラクルが一度でも ⊤ を返すイベントである．

Luykx らの結論は，H が多項式ハッシュ関数であれば，Advmu-auth(B) はWC
mu-auth(B) の上界になる，というU に依存せず，最良の Advauth
WC (A) が AdvWCものである [LMP17]．
これを Poly1305 に当てはめる．AES-128 の代わりに {0, 1}n 上のランダ
ム置換を用いた Poly1305 を Poly1305p = (Polyp , Verp ) とし，{0, 1}n から{0, 1}n へのランダム関数を用いた Poly1305 を Poly1305f = (Polyf , Verf ) とする．
式 (2) は，
prp
authAdvauthPoly1305 (A) ≤ AdvE (B) + AdvPoly1305p (A)およびAdvauthPoly1305p (A) ≤14q ′ ⌈ℓ/16⌉
2106

(11)

を示している．Advprp
E (B) は E = AES-128 の擬似ランダム置換としての安全性を表す．
ここで Advmu-authPoly1305 (A) について考える．まずmu-prp
Advmu-auth(C)
Poly1305 (A) ≤ AdvE

(12)+ Advmu-prf
Perm(n) (B)(13)+ Advmu-authPoly1305f (A)(14)となる．式 (12) は E = AES-128 の複数ユーザにおける擬似ランダム置換としての安全性を表している．式 (13) は複数ユーザにおける PRP-PRF switch
であり，式 (10) より 0.5(q + q ′ )2 /2128 が上界となる（q は A のタグ生成オラ
クルへのアクセス総数の最大値，q ′ はタグ検証オラクルへのアクセス総数の最大値である）．式 (14) は，[LMP17] の結果から，シングルユーザの安全性

19

AdvauthPoly1305f (A) が上界となる．式 (11) より0.5(q + q ′ )2
+ AdvauthPoly1305p (A)
2128
′
′ 2
0.5(q + q )14q ⌈ℓ/16⌉
+
≤
128
2
2106

AdvauthPoly1305f (A) ≤であるから，最終的に，
mu-prp
Advmu-auth(C) +Poly1305 (A) ≤ AdvE

(q + q ′ )2
14q ′ ⌈ℓ/16⌉
+
2128
2106

(15)

を得る．ただし，q はタグ生成オラクルへのアクセス総数の最大値，q ′ はタ
グ検証オラクルへのアクセス総数の最大値，ℓ はクエリの M の最大バイト長である．Advmu-prp(C) は高々q + q ′ 回のクエリにより，U 個のブロック暗号
Eのオラクル (EK1 , . . . , EKU ) と U 個のランダム置換のオラクル (P1 , . . . , PU )を識別する利得である．
式 (15) で与えられる上界の第一項の Advmu-prp(C) はユーザ数に依存する
E[Bih02, BMS05] ものの，第二項，第三項がユーザ数 U と独立である．したがって，式 (15) はユーザ数の影響が限定的な安全性バウンドを与えている．

ChaCha20-Poly1305 の仕様

6

本章では ChaCha20-Poly1305 の仕様を示す [NL15]．構成要素としてストリーム暗号 ChaCha20 で利用されているブロック関数 [Ber08] と，Poly1305に基づく多項式ハッシュ関数を用いる．ナンスごとに Poly1305 の鍵が変わる
ことに大きな特徴がある．

ChaCha20-Poly1305 を CC-Poly と略記する．CC-Poly は 2 つのアルゴリズ
ム (Enc, Dec) からなる．

• 鍵は 256 ビット（32 バイト）の鍵 K であり，暗号化アルゴリズム EncK は入力として 96 ビット（12 バイト）のナンス N ，任意長の AD（associateddata）A，および任意長の平文 M をとり，平文と同じ長さの暗号文 Cと 128 ビット（16 バイト）のタグ T を出力する．

• 復号アルゴリズム DecK は入力として 96 ビット（12 バイト）のナンス
N ，任意長の AD A，任意長の暗号文 C ，および 128 ビット（16 バイト）のタグ T をとり，暗号文と同じ長さの平文 M か，あるいは拒否を示す ⊥ を返す．

CC-Poly はその内部で ChaCha20 のブロック関数 CC を用いる．CC の入出
力は

CC : KCC × {0, 1}32 × {0, 1}96 → {0, 1}51220で与えられる．ここで KCC = {0, 1}256 は鍵空間である．入力として 256 ビット（32 バイト）の秘密鍵 K ，32 ビット（4 バイト）のカウンタ ctr，および96 ビット（12 バイト）のナンス N をとり，512 ビット（64 バイト）の鍵ス
トリーム Z を出力する．Z ← CCK (ctr, N ) と表記する．

CC-Poly では，Poly1305 の多項式ハッシュ関数の部分のみを考える．すな
わち，Poly の入出力をPoly : KPoly × {0, 1}∗ → {0, 1}128とする．ここで KPoly = {0, 1}128 は鍵空間である．入力として 128 ビット（16 バイト）の秘密鍵 R と任意長のメッセージ Y をとり，ハッシュ値 T ←PolyK (Y ) を出力する．ただし，R は特定のビットが 0 になるようにマスクされる．
暗号化アルゴリズム EncK は次のように動作する．

• CCK (0 ∥ N ) を計算し，その上位 128 ビットを R，次の 128 ビットを Sとして，Poly のワンタイム鍵 R と擬似ワンタイムパッド S を生成する．
• 鍵ストリーム Z = CCK (1, N ) ∥ CCK (2, N ) ∥ · · · を生成し，これと平文
M との排他的論理和から暗号文 C = Z ⊕ M を生成する．
• まず AD A と暗号文 C からメッセージ Y を次のように構成する．
Y ← A ∥ pad(A) ∥ C ∥ pad(C) ∥ pad(A, C)
ここで pad(A) は A ∥ pad(A) の長さが 16 バイトの整数倍になるような
最も短いゼロバイト列 0x0 . . . 0 であり，pad(C) は C ∥ pad(C) の長さが 16 バイトの整数倍になるような最も短いゼロバイト列 0x0 . . . 0 である．pad(A) と pad(C) は A ないしは C が初めから 16 バイトの整数倍であれば空列となる．pad(A, C) は len(A) と len(C) をそれぞれ 8 バイ
トで表現したバイト列の連結である．メッセージ Y の長さはつねに 16
バイトの整数倍となる．
最後に，T ← PolyR (Y ) + S mod 2128 としてタグ T を生成する．ただし，R の特定ビットは 0 とする．
復号アルゴリズム DecK は次のように動作する．

• CCK (0 ∥ N ) を計算し，その上位 128 ビットを R，次の 128 ビットを Sとして，Poly のワンタイム鍵 R と擬似ワンタイムパッド S を生成する．

• 暗号化アルゴリズムと同様の手順で AD A と暗号文 C からメッセージ
Y を構成する．次に T ← PolyR (Y ) + S mod 2128 としてタグ T を生成する．ただし，R の特定ビットは 0 とする．入力されたタグとこれが一致すれば次に進み，そうでなければ拒否する．

21

Algorithm EncK (N, A, M )1. Z ← KGenK (N, len(M ))2. C ← M ⊕ Z
3. T ← TagK (N, A, C)
4. return (C, T )Algorithm DecK (N, A, C, T ∗ )1. T ← TagK (N, A, C)
2. if T ̸= T ∗ then return ⊥3. Z ← KGenK (N, len(C))
4. M ← C ⊕ Z
5. return M
図 3: (C, T ) ← EncK (N, A, M ) と M/⊥ ← DecK (N, A, C, T ) の定義• 鍵ストリーム Z = CCK (1, N ) ∥ CCK (2, N ) ∥ · · · を生成し，これと暗号
文 C との排他的論理和から平文 M = Z ⊕ C を生成する．

CC-Poly = (Enc, Dec) の擬似コードを図 3 に示す．また，内部で用いるサブルーチンの定義を図 4，図 5 に示す．参考として，ChaCha20 ブロック関
数 CC の仕様を付録 Aに示す．図 6 に暗号化アルゴリズムの流れを示す．

ChaCha20-Poly1305 に関する文献調査7

本章では ChaCha20-Poly1305 に関する文献調査の報告をする．7.1 章でProcter による証明可能安全性を扱い，その他を 7.2 章で扱う．

7.1

証明可能安全性

CC-Poly の安全性は Procter により示されている [Pro14]．安全性定義は[BN08, RBB03] によるものを考えており，暗号化オラクルと復号オラクルにアクセスする敵を考える．暗号化オラクルはクエリ (N, A, M ) に対し (C, T ) ←EncK (N, A, M ) を返す．復号オラクルはクエリ (N, A, C, T ) に対し M か ⊥を返す．このとき，CC-Poly の AE 安全性を次のように定義する．
EncK ,DecK⇒ 1] − Pr[A$,⊥ ⇒ 1]
AdvAE
CC-Poly (A) = Pr[A22

Algorithm KGenK (N, ℓ)
1. m ← ⌈ℓ/64⌉
2. for i = 1 to m do
3.

Z[i] ← CCK (i, N )4. Z ← first ℓ bytes of Z[1] ∥ · · · ∥ Z[m]5. return Z
Algorithm TagK (N, A, C)
16

1. (R, S) ←− first 32 bytes of CCK (0, N )2. R ← R ∧ 0x0ffffffc0ffffffc0ffffffc0fffffff
3. Y ← A ∥ pad(A) ∥ C ∥ pad(C) ∥ pad(A, C)
4. T ← PolyR (Y ) + S mod 2128
5. return T
図 4: Z ← KGenK (N, ℓ) と T ← TagK (N, A, C) の定義

Algorithm PolyR (Y )16

1. (Y [0], . . . , Y [y − 1]) ←− Y// y = ⌈len(Y )/16⌉

2. for i = 1 to y − 1 do
3.

C[i] ← Y [i] + 0x01 · 28len(Y [i])4. T ← C[0]5. for i = 1 to y − 1 do
6.

T ← R · C[i] mod (2130 − 5)

7. T ← R · T mod (2130 − 5)
8. T ← T mod 2128
9. return T
図 5: T ← PolyR (Y ) の定義

だたし，$ は EncK と同じ長さの乱数を返し，⊥ はつねに ⊥ を返すオラクルである．また，敵は暗号化オラクルに同じナンスを用いてクエリしてはならず，暗号化クエリ (N, A, M ) に対し (C, T ) を得たのちに (N, A, C, T ) を復号
オラクルにクエリしてはならず，クエリは繰り返さないとする．

23

N

A

0
96

32

CCK

32
CCK

512

CCK

512

512
concatenate

trunc
128

m

1

32

M

Z

128

C
R

Poly1305
S

128
T

図 6: ChaCha20-Poly1305 の暗号化アルゴリズムの全体像

このとき Procter は次の式を示した [Pro14]．
prf
′′
AdvAE
CC-Poly (A) ≤ AdvCC (B) + q

8⌈ℓmax /16⌉
2106

(16)

ただし q ′′ は復号オラクルへのアクセス回数を表し，ℓmax は暗号化クエリと復号クエリに対する Poly への入力 Y の最大バイト長を表す．また，Advprf
CC (B)は CC の擬似ランダム関数として安全性を表し，これは小さいと考えられて
いる．

7.2

その他の文献Bhargavan らは TLS 1.3 record layer の安全性を解析しており [DFK+ 17]，
その中で AES-GCM と ChaCha20-Poly1305 を含む認証暗号化方式の一般的構成法を示し，TLS 1.3 での使用に特化した証明可能安全性を示している．それに基づき，TLS 1.3 record layer 全体の安全性を議論している．

Nir と Langley による RFC 7539 においても ChaCha20-Poly1305 の安全性が議論されている [NL15]．使用にあたってはナンスが繰り返さないことが重要である点，繰り返した場合は平文の排他的論理和が漏えいすることが述べられている．またサイドチャネル攻撃ついての言及があり，タイミングによるサイドチャネル攻撃を避けるために実行時間が一定となるよう実装するべきである，ということが述べられている．

24

Ashur らはナンスの再利用についての解析を行っている [ADL17]．通常ナ
ンスを再利用すると，平文の排他的論理和が漏えいし暗号化としての安全性が失われる．あるいはハッシュ関数の鍵が漏えいし，偽造攻撃が可能となる．

Ashur らは，いくつかのナンスが再利用されたとしても，ある時点以降ナンスの再利用がなければ，CC-Poly は暗号化についても認証についてもその時点以降は安全であることを証明した．これは再利用されたナンスに対する安
全性は失われるが，それ以外のナンスについては影響が波及しないことを示している．

ChaCha20-Poly1305 の安全性評価

8

本章では ChaCha20-Poly1305 の安全性評価を報告する．8.1 章で証明可能
安全について考える．8.2 章では関連鍵攻撃，8.3 章では再偽造可能性，8.4 章
ではナンス再利用，8.5 章では弱鍵，8.6 章では復号ミスユース耐性，8.7 章
では複数ユーザ安全性について考える．

8.1

証明可能安全性

Procter による [Pro14] の証明には一か所軽微な誤りがあるが簡単に修正可能であり，最終的に得られるバウンドに影響しない．CC-Poly は証明可能安
全性を有する認証暗号化方式である．

[Pro14] の証明では，鍵ストリームを真のランダム関数の出力から構成する
ゲーム (E 1 , D1 ) と，鍵ストリームを真のランダムビット列として生成する
ゲーム (E 2 , D2 ) を考え，これらのゲームが等価であるとされている．暗号化
クエリにおいては等価であるが，復号クエリにおいては以前に暗号化クエリで使用したナンスを再利用することができ，この場合，鍵ストリームはすでに決まっている．したがって，ナンスの再利用をチェックするルーチンを加えるといった修正が必要であるが，これは容易であり，最終的な安全性のバ
ウンドに影響しない．

8.2

関連鍵攻撃

CC-Poly では多項式ハッシュ関数を利用しているものの，その鍵はナンス
ごとに更新される．CC が関連鍵攻撃に対しても安全な擬似ランダム関数であれば，鍵に操作が加えられたとしてもすべての鍵が更新されるため，多項式
ハッシュ関数にあったような関連鍵攻撃を行うことはできない．
実際に CC が関連鍵攻撃に対して安全な擬似ランダム関数であるとの仮定の下で CC-Poly 全体が関連鍵攻撃に対して安全な認証暗号化方式であることの証明が可能である．

25

たとえば，鍵導出関数の集合として

Φ⊕ = {XOR∆ | K 7→ K ⊕ ∆, ∆ ∈ KF }を考える．敵が ∆1 , ∆2 , . . . を使用した場合，EncK⊕∆1 , DecK⊕∆1 , EncK⊕∆2 , DecK⊕∆2 , . . .
をオラクルとして有することになる．CC が関連鍵攻撃に対して安全な擬似ランダム関数であれば，これらの内部で使用されている

CCK⊕∆1 , CCK⊕∆2 , . . .
はそれぞれ独立なランダム関数

Fi : {0, 1}32 × {0, 1}96 → {0, 1}512に置き換わる．(EncK⊕∆i , DecK⊕∆i ) をそれぞれ (EncFi , DecFi ) と書くことにすれば，敵の観点からは独立な鍵 Fi を有する複数の ChaCha20-Poly1305を攻撃することになる．これ以降は情報理論的な安全性証明となり，8.7 章にある複数ユーザ安全性と同じ議論から，敵の攻撃成功確率の上界を導出で
きる．

8.3

再偽造可能性

認証暗号化方式に対する再偽造不可能性は Forler らにより解析されている[FLLW17]．仮に敵が偽造に成功，あるいは出力の衝突に成功したと仮定し，その後別の偽造に成功するのにどれだけの計算量が必要かにより安全性を評価する．理想的な認証暗号化方式であれば，たとえば 2 つの入力 (N, A, M )と (N ′ , A′ , M ′ ) のタグが衝突したとして（ただし N ̸= N ′ ），これら以外の衝突ペアを入手するのには役に立たない．

CC-Poly でも同様に，繰り返さないナンスを用いている限り，タグが衝突する 2 つの入力 (N, A, M ) と (N ′ , A′ , M ′ ) が得られたとしてもこれら以外の衝突を得るのには役に立たず，CC-Poly は再偽造可能性の意味で理想的な認証
暗号化方式と同等の安全性を有する．一方で Poly1305 と同様に，N = N ′ が満たされるような場合にはハッシュ鍵を導出でき，汎用的偽造が可能となる．

8.4

ナンス再利用CC-Poly で使用する Poly では特定のフォーマットに従って入力メッセージ
Y を生成するため，これに対処する必要があるが，ナンスを再利用すると Rと S を復元することができる．また，得られた R と S を用いることにより，

26

ナンス N に対する偽造を行うことができる [II16]．ただし Ashur らにより示されているように，他のナンスについては影響がない [ADL17]．
本章では [II16, Ima17] に従い，偽造ができることを確認する．任意のナン
ス N を固定し，AD A = 0x00，A′ = 0x0000 を考える．平文 M を空列とする．以下，整数 a ≤ b に対して
[a, b] = {x | a ≤ x ≤ b}[a, b) = {x | a ≤ x < b}(a, b] = {x | a < x ≤ b}(a, b) = {x | a < x < b}とする．
敵は暗号化オラクル EncK に (N, A, M ) と (N, A′ , M ) をクエリし，(C, T )と (C ′ , T ′ ) を得る．C と C ′ は空列である．len(A) = 1 と len(A′ ) = 2 より，それぞれの Poly への入力メッセージ Y と Y ′ はY = A + len(A) · 2128⌈len(A)/16⌉ = 1 · 2128
Y ′ = A′ + len(A′ ) · 2128⌈len(A′ )/16⌉ = 2 · 2128
16

16となる．それぞれ 16 バイトごとに分割し (Y [0], Y [1]) ←− Y と (Y ′ [0], Y ′ [1]) ←−Y ′ とすれば，Y [0] = 0，Y [1] = 1，Y ′ [0] = 0，Y ′ [1] = 2 となる．特定のビットを 0 に固定したあとの R に対して，{
Y(R) = 2128 R + (1 + 2128 )R′Y (R) = 2
とおくと，

{

128

R + (2 + 2

128

(17)

)R

(18)

T = (Y(R) mod (2130 − 5) + S) mod 2128′′

T = (Y (R) mod (2130− 5) + S) mod 2

(19)

128

となる．ある整数 κ，κ′ に対して{
T + 2128 κ = Y(R) mod (2130 − 5) + S
′

T +2

128 ′

′

κ = Y (R) mod (2

130

(21)

− 5) + S(22)が成り立つ．T と T ′ を移項すれば，{ 128
2 κ = (Y(R) mod (2130 − 5) + S) − T
128 ′

2

′

κ = (Y (R) mod (2130− 5) + S) − T

(20)

(23)
′

(24)

を得る．S ∈ [0, 2128 ) であり T ∈ [0, 2128 ) であるから S − T ∈ (−2128 , 2128 )となり，式 (23) の右辺の範囲は(Y(R) mod (2130 − 5) + S) − T ∈ (−2128 , 2130 + 2128 − 5)
⊆ (−2128 , 5 · 2128 )27

となる．κ ∈ (−2128 , 5·2128 ) であり，κ が整数であることより κ ∈ {0, 1, 2, 3, 4}である．同様にして式 (24) より κ′ ∈ {0, 1, 2, 3, 4} が成り立つ．
次に，ある整数 λ，λ′ に対して式 (21) と式 (22) は{T − S + 2128 κ + (2130 − 5)λ = Y(R)T ′ − S + 2128 κ′ + (2130 − 5)λ′ = Y′ (R)

(25)
(26)

と書き直せる．式 (26) から式 (25) を引き，式 (17) と式 (18) を用いるとT ′ − T + 2128 (κ′ − κ) + (2130 − 5)(λ′ − λ) = Y′ (R) − Y(R)=Rが成り立つ．κ∗ = κ′ − κ とし，λ∗ = λ′ − λ とすると

T ′ − T + 2128 κ∗ + (2130 − 5)λ∗ = Rを得る．これより(2130 − 5)λ∗ = R − (T ′ − T ) − 2128 κ∗(27)が成り立つ．κ∗ ∈ {0, ±1, ±2, ±3, ±4} である．
次に，式 (27) の T ′ − T の符号により，次のように場合分けして考える．

• T′ − T ≥ 0• T′ − T < 0
T ′ − T ≥ 0 のとき R ∈ [0, 2124 ) であり，T ′ − T + 2128 κ∗ ∈ [2128 κ∗ , 2128 (1 +κ∗ )) なので，式 (27) の範囲は
R − (T ′ − T ) − 2128 κ∗ ∈ (−2128 (1 + κ∗ ), 2124 − 2128 κ∗ )となる．次に，9 通りの κ∗ の値に対し，これに対応する λ∗ が存在するかを確かめる．

κ∗ = −4 のとき

R − (T ′ − T ) − 2128 κ∗ = R − (T ′ − T ) + 4 · 2128 ∈(3 · 2

128

128

124

,2

+4·2

) より，(2130 − 5)λ∗ ∈ (3 · 2128 , 2124 + 4 · 2128 ) を満たす λ∗ は λ∗ = 1 である．

κ∗ = −3 のとき

R − (T ′ − T ) − 2128 κ∗ = R − (T ′ − T ) + 3 · 2128 ∈(2 · 2128 , 2124 + 3 · 2128 ) より，(2130 − 5)λ∗ ∈ (2 · 2128 , 2124 + 3 · 2128 ) を満たす λ∗ は存在しない．

κ∗ = −2 のとき

R − (T ′ − T ) − 2128 κ∗ = R − (T ′ − T ) + 2 · 2128 ∈(2128 , 2124 + 2 · 2128 ) より，(2130 − 5)λ∗ ∈ (2128 , 2124 + 2 · 2128 ) を満たす λ∗は存在しない．

28κ∗ = −1 のとき R−(T ′ −T )−2128 κ∗ = R−(T ′ −T )+2128 ∈ (0, 2124 +2128 )より，(2130 − 5)λ∗ ∈ (0, 2124 + 2128 ) を満たす λ∗ は存在しない．

κ∗ = 0 のとき R − (T ′ − T ) − 2128 κ∗ = R − (T ′ − T ) ∈ (−2128 , 2124 ) より，(2130 − 5)λ∗ ∈ (−2128 , 2124 ) を満たす λ∗ は λ∗ = 0 である．
κ∗ = 1 のとき R−(T ′ −T )−2128 κ∗ = R−(T ′ −T )−2128 ∈ (−2·2128 , 2124 −2128 ) より，(2130 − 5)λ∗ ∈ (−2 · 2128 , 2124 − 2128 ) を満たす λ∗ は存在しない．
κ∗ = 2 のとき
2

128

,2

124

−2·2

R − (T ′ − T ) − 2128 κ∗ = R − (T ′ − T ) − 2 · 2128 ∈ (−3 ·128) より，(2130 − 5)λ∗ ∈ (−3 · 2128 , 2124 − 2 · 2128 ) を満たす

λ∗ は存在しない．
κ∗ = 3 のとき

R − (T ′ − T ) − 2128 κ∗ = R − (T ′ − T ) − 3 · 2128 ∈ (−4 ·2128 , 2124 − 3 · 2128 ) より，(2130 − 5)λ∗ ∈ (−4 · 2128 , 2124 − 3 · 2128 ) を満たす
λ∗ は λ∗ = −1 である．
κ∗ = 4 のとき

R − (T ′ − T ) − 2128 κ∗ = R − (T ′ − T ) − 4 · 2128 ∈ (−5 ·2128 , 2124 − 4 · 2128 ) より，(2130 − 5)λ∗ ∈ (−5 · 2128 , 2124 − 4 · 2128 ) を満たす
λ∗ は λ∗ = −1 である．
以上より，T ′ − T ≥ 0 の場合に (κ∗ , λ∗ ) に対応する R の値の候補は
T ′ − T − 5
if (κ∗ , λ∗ ) = (−4, 1)T ′ − T
if (κ∗ , λ∗ ) = (0, 0)R=
T ′ − T − 2128 + 5 if (κ∗ , λ∗ ) = (3, −1)T ′ − T + 5
if (κ∗ , λ∗ ) = (4, −1)となる．

T ′ − T < 0 のとき R ∈ [0, 2124 ) と T ′ − T ∈ (−2128 , 0) より R − (T ′ − T ) ∈(0, 2124 + 2128 ) なので，R − (T ′ − T ) − 2128 κ∗ ∈ (−2128 κ∗ , 2124 + 2128 (1 − κ∗ ))である．T ′ − T ≥ 0 の場合と同様に，9 通りの κ∗ の値に対し，対応する λ∗が存在するかを確かめる．

κ∗ = −4 のとき

R − (T ′ − T ) − 2128 κ∗ = R − (T ′ − T ) + 4 · 2128 ∈(4 · 2

128

128

124

,2

+5·2

) より，(2130 − 5)λ∗ ∈ (4 · 2128 , 2124 + 5 · 2130 ) を満たす λ∗ は存在しない．

29

κ∗ = −3 のとき

R − (T ′ − T ) − 2128 κ∗ = R − (T ′ − T ) + 3 · 2128 ∈(3 · 2128 , 2124 + 4 · 2128 ) より，(2130 − 5)λ∗ ∈ (3 · 2128 , 2124 + 4 · 2128 ) を満たす λ∗ は λ∗ = 1 である．

κ∗ = −2 のとき

R − (T ′ − T ) − 2128 κ∗ = R − (T ′ − T ) + 2 · 2128 ∈(2 · 2

128

128

124

,2

+3·2

) より，(2130 − 5)λ∗ ∈ (2 · 2128 , 2124 + 3 · 2128 ) を満たす λ∗ は存在しない．

κ∗ = −1 のとき R − (T ′ − T ) − 2128 κ∗ = R − (T ′ − T ) + 2128 ∈ (2128 , 2124 +2 · 2128 ) より，(2130 − 5)λ∗ ∈ (2128 , 2124 + 2 · 2128 ) を満たす λ∗ は存在しない．
κ∗ = 0 のとき R − (T ′ − T ) − 2128 κ∗ = R − (T ′ − T ) ∈ (0, 2124 + 2128 ) より，(2130 − 5)λ∗ ∈ (0, 2124 + 2128 ) を満たす λ∗ は存在しない．
κ∗ = 1 のとき R − (T ′ − T ) − 2128 κ∗ = R − (T ′ − T ) − 2128 ∈ (−2128 , 2124 )より，(2130 − 5)λ∗ ∈ (−2128 , 2124 ) を満たす λ∗ は λ∗ = 0 である．

κ∗ = 2 のとき

R − (T ′ − T ) − 2128 κ∗ = R − (T ′ − T ) − 2 · 2128 ∈ (−2 ·2128 , 2124 − 2128 ) より，(2130 − 5)λ∗ ∈ (−2 · 2128 , 2124 − 2128 ) を満たす λ∗ は存在しない．

κ∗ = 3 のとき

R − (T ′ − T ) − 2128 κ∗ = R − (T ′ − T ) − 3 · 2128 ∈ (−3 ·2128 , 2124 − 2 · 2128 ) より，(2130 − 5)λ∗ ∈ (−3 · 2128 , 2124 − 2 · 2128 ) を満たす
λ∗ は存在しない．
κ∗ = 4 のとき

R − (T ′ − T ) − 2128 κ∗ = R − (T ′ − T ) − 4 · 2128 ∈ (−4 ·2128 , 2124 − 3 · 2128 ) より，(2130 − 5)λ∗ ∈ (−4 · 2128 , 2124 − 3 · 2128 ) を満たす
λ∗ は λ∗ = −1 である．
対応する R の値の候補は
T ′ − T + 2128 − 5
R = T ′ − T + 2128

T ′ − T + 5

if (κ∗ , λ∗ ) = (−3, 1)
if (κ∗ , λ∗ ) = (1, 0)
if (κ∗ , λ∗ ) = (4, −1)となる．
したがって T ′ − T ≥ 0 のときに R の候補を 4 通り，T ′ − T < 0 のとき 3通りに絞ることができる．これらを式 (19) あるいは (20) に代入すればこれらに対応する S の値を導出できる．
上記の手順を利用して次のようにして偽造攻撃を行うことができる．

30

1. 任意のナンス N を固定し，AD A = 0x00，A′ = 0x0000 とする．平文
M を空列とする．
2. 敵は暗号化オラクル EncK に (N, A, M ) と (N, A′ , M ) をクエリし，(C, T )と (C ′ , T ′ ) を得る（C と C ′ は空列である）．

3. 上記の手順に従い，(R, S) の候補を得てから，ランダムに (R, S) を決める．

4. 任意の (A′′ , C ′′ ) を選び（ただし (A′′ , C ′′ ) ̸= (A, C), (A′ , C ′ )），それに対応するタグ T ′′ を R と S を用いて計算する．

5. (N, A′′ , C ′′ , T ′′ ) を検証オラクルにクエリする．
正しく (R, S) が選ばれればこの偽造攻撃は成功し，T ′ − T ≥ 0 であれば確率

1/4，そうでなければ 1/3 で成功する．

8.5

弱鍵

CC-Poly の秘密鍵は ChaCha20 ブロック関数で用いる鍵 K であり，Poly で使用する R はナンスと K に依存する．

Poly1305 にあったような弱鍵は R を鍵として考えているものであり，その意
味では CC-Poly の直接的な弱鍵とはなっていない．たとえば S = {R1 , . . . , Rs }として偽造多項式を R1 , . . . , Rs から Q(X) = Π1≤i≤s (X − Ri ) と生成したとして，未知の鍵 R がこの中に含まれていれば Q(X) を用いて確率 1 で偽造に成功する．また，未知の鍵が集合 S に属しているかのテストは，Q(X) を用いて復号オラクルにクエリをすることにより行うことができる．
したがってこの S は弱鍵の定義を満たすように考えられるが，これらに対応する CC の鍵の集合を列挙することは容易ではない．すなわち，trunc16 を入力の先頭 16 バイトを返す関数として，

R1 = trunc16 (CCK1 (0, N )), . . . , Rs = trunc16 (CCKs (0, N ))(28)を満たす鍵 K1 , . . . , Ks が存在する（各 Ki は一意とは限らない）．弱鍵集合
としては {K1 , . . . , Ks } となるが，N と R1 , . . . , Rs からこれらを求めるのは困難である．
一方で，固定された N と K に対して R が一意に定まる．したがって，

K1 , . . . , Ks を任意に固定し，S = {K1 , . . . , Ks } として，式 (28) に従って
R1 , . . . , Rs を定めると，この S は弱鍵集合としての要件を満たす．未知の鍵
K が S に含まれていれば R1 , . . . , Rs から生成される偽造多項式 Q(X) を用いれば偽造攻撃に成功する．また，Q(X) を用いて復号オラクルにクエリをすることにより，未知の鍵 K が集合 S に属しているかのテストを行うこと
ができる．

31

したがって ChaCha20-Poly1305 には弱鍵が存在する．しかし，Poly1305と同様に弱鍵の存在が現実的な問題とはならないと考えられるとともに，全体の鍵空間のサイズは 2256 であるからその影響は Poly1305 よりも小さいものと考えられる．

8.6

復号ミスユース耐性

復号ミスユース耐性は Andreeva らにより提案された安全性定義であり，
検証で受理されないような暗号文に対する平文を入手できる状況を考える[ABL+ 14]．暗号化に関する安全性 PA（plaintext awareness）と認証に関する安全性 INT-RUP（integrity under releasing unverified plaintext）がある．

CC-Poly は暗号化に関する安全性を満たさないが，認証に関する安全性を満たすことが証明できる．本章では [II16, IMI16, Ima17, IMI17] に基づき，これらの概要を示す．
まずこの設定では，ChaCha20-Poly1305 を暗号化アルゴリズム，復号アルゴリズムだけではなく，暗号化，復号，検証の 3 つのアルゴリズムからなると捉える．それぞれ次のように定義される．

• 暗号化アルゴリズム EncK は 6 章と同様に定義され，鍵 K を用いて入力 (N, A, M ) から暗号文とタグのペア (C, T ) を出力する．

• 復号アルゴリズム VerK は (N, A, C, T ∗ ) を入力とし，鍵ストリーム Z =CCK (1, N ) ∥ CCK (2, N ) ∥ · · · を生成し，これと暗号文 C との排他的論
理和から平文 M = Z ⊕ C を生成する．検証に相当するチェックは行わず，T ∗ は用いない．また，つねに平文を返す．

• 検証アルゴリズム VerK は (N, A, C, T ∗ ) を入力とし，次のように動作する．

– CCK (0 ∥ N ) を計算し，その上位 128 ビットを R，次の 128 ビット
を S として，Poly のワンタイム鍵 R と擬似ワンタイムパッド S を生成する．

– 暗号化アルゴリズムと同様の手順で AD A と暗号文 C からメッ
セージ Y を構成する．次に T ← PolyR (Y ) + S mod 2128 として
タグ T を生成する．ただし，R の特定ビットは 0 とする．入力されたタグとこれが一致すれば ⊤ を出力し，そうでなければ ⊥ を出力する．
検証アルゴリズムはチェックのみを行い，平文の計算は行わない．

CC-Poly = (Enc, Dec, Ver) の擬似コードを図 7 に示す．また，内部で用いるサブルーチンのは図 4，図 5 にある．ChaCha20 ブロック関数 CC の仕様
は付録 Aにある．

32

Algorithm EncK (N, A, M )1. Z ← KGenK (N, len(M ))2. C ← M ⊕ Z
3. T ← TagK (N, A, C)
4. return (C, T )Algorithm DecK (N, A, C, T ∗ )1. Z ← KGenK (N, len(C))
2. M ← C ⊕ Z
3. return M
Algorithm VerK (N, A, C, T ∗ )1. T ← TagK (N, A, C)
2. if T ̸= T ∗ then return ⊥3. return ⊤図 7: EncK ，DecK ，VerK の定義

8.6.1

PA 安全性まず ChaCha20-Poly1305 に対する PA を定義する．PA は直感的には平文を知らずに暗号文を作成できないという性質であり，復号クエリを使っても暗号化クエリで得られる以上の平文の情報を手に入れることができないことを指す．

Ext を extractor とする．これは状態を保持できるアルゴリズムであり，鍵K を入力とせず，暗号化オラクル EncK や復号オラクル DecK にも直接アクセスしない．A を 2 つのオラクル O1 と O2 にアクセスする敵とする．PA1
においては，Ext は A が O1 にクエリした履歴にアクセスできるが，PA2 ではアクセスできない．また PA2 においは，A が O1 に対して (N, A, M ) をク
エリし (C, T ) を受け取ったならば，その後 (N, A, C, T ) を O2 にクエリしてはならない．このとき，上記の制限を満たして Ext が効率よく復号オラクル

DecK をシミュレートできるとき，それぞれ PA1 安全，PA2 安全といい，利得をAdvpa1,Ext (A) = Pr[AEncK ,DecK ⇒ 1] − Pr[AEncK ,Ext ⇒ 1]
CC-PolyAdvpa2,Ext (A) = Pr[AEncK ,DecK ⇒ 1] − Pr[AEncK ,Ext ⇒ 1]
CC-Polyと定義する．ただし，K ← KCC である．また，O1 に対してナンスを再利用$してはならないが，O2 に対しては再利用してもよく，O1 と O2 の間でナン

33

スを繰り返し利用しても構わない．

Andreeva らはナンスを用いたカウンタモードが PA1 安全ではないことを示しており [ABL+ 14]，同じ議論で ChaCha20-Poly1305 が PA1 を満たさないことを示せる．
敵は A はナンス N と AD A と A′ ，タグ T を任意に選び，1 ブロックの任意の暗号文 C に対し，復号オラクルに対して (N, A, C, T ) をクエリす
る．復号オラクルが DecK のとき，復号の式は M = CCK (1, N ) ⊕ C と表され，M ⊕ C から鍵ストリーム Z （= CCK (1, N )）の値を得る．1 ブロックのM ′ ̸= M に対し，暗号化オラクルに対して (N, A′ , M ) をクエリすると，暗号文が C ′ = CCK (1, N ) ⊕ M ′ = Z ⊕ M ′ ということがわかる．しかし，復号
オラクルが extractor のとき，extractor は鍵 K を知らず，暗号化クエリや復号クエリを行うことはできない．1 回目の復号クエリにおいてナンス N に対する暗号化クエリの履歴がないので，どの extractor も鍵ストリーム Z を計算することができない．したがって，ChaCha20-Poly1305 は PA1 安全ではない．
以上から，次の定理が成り立つ．
定理 2 ChaCha20-Poly1305 は PA1 安全ではない．

PA1 安全でなければ PA2 安全でもないので，次の系を得る．
系 1 ChaCha20-Poly1305 は PA2 安全ではない．

8.6.2

INT-RUP 安全性

ChaCha20-Poly1305 に対する INT-RUP 安全性は次のように定義される．
敵 A は，ChaCha20-Poly1305 の暗号化オラクル EncK ，復号オラクル DecK ，および検証オラクル VerK が与えられる．このとき，A の利得を
EncK ,DecK ,VerK
forges]Advint-rup
CC-Poly (A) = Pr[Aと定義する．ただし，K ← KCC であり，A forges は VerK が A の検証クエ$

リに対して一度でも ⊤ を返すイベントである．また，A が暗号化オラクルに(N, A, M ) をクエリし (C, T ) を受け取った後で，VerK に対して (N, A, C, T )をクエリしてはならない．さらに，A は暗号化オラクルに対してナンスを繰り返してはならない．DecK と VerK に対してはナンスを再利用してもよく，それぞれのオラクルの間でナンスを再利用してもよい．

A を ChaCha20-Poly1305 に対する敵であるとする．A は暗号化クエリを
q 回，復号クエリを q ′ 回，検証クエリを q ′′ 回行うとする．暗号化クエリが(N1 , A1 , M1 ), . . . , (Nq , Aq , Mq )34

であり，復号クエリが(N1′ , A′1 , C1′ , T1′ ), . . . , (Nq′ ′ , A′q′ , Cq′ ′ , Tq′′ )であり，検証クエリが(N1′′ , A′′1 , C1′′ , T1′′ ), . . . , (Nq′′′′ , A′′q′′ , Cq′′′′ , Tq′′′′ )であったとする．このときの暗号化クエリにおける入力の総バイト長を∑(len(Ni ) + len(Ai ) + len(Mi ))1≤i≤qとし，復号クエリにおける入力の総バイト長を∑(len(Ni′′ ) + len(A′i′ ) + len(Ci′′ ) + len(Ti′′ ))1≤i′ ≤q ′とする．検証クエリにおける入力の総バイト長を∑(len(Ni′′′′ ) + len(A′′i′′ ) + len(Ci′′′′ ) + len(Ti′′′′ ))1≤i′′ ≤q ′′と定義する．

∑
また，暗号化クエリにおける平文の総ブロック数を 1≤i≤q ⌈len(Mi )/64⌉，∑
復号クエリにおける暗号文の総ブロック数を 1≤i′ ≤q′ ⌈len(Ci′′ )/64⌉ と定義する．さらに，暗号化クエリと検証クエリに対するメッセージの最大バイト長を max{len(Y1 ), . . . , len(Yq ), len(Y1′′ ), . . . , len(Yq′′′′ )} と定義する．ただし，Yi
は暗号化クエリにおける Poly1305 への入力メッセージを表し，Yi′′′′ は検証ク
エリにおける Poly1305 への入力メッセージを表す．
このとき，以下の定理が成り立つ．

定理 3 A を暗号化オラクルに高々q 回，復号オラクルに高々q ′ 回，検証オ
ラクルに高々q ′′ 回アクセスする敵とする．それぞれのクエリの入力の総バイト長が高々σ バイト，高々σ ′ バイト，高々σ ′′ バイトであり，暗号化クエリの平文の総ブロック数が高々µM ブロック，復号クエリの暗号文の総ブロッ
ク数が高々µ′C ′ ブロックであり，さらに暗号化クエリと検証クエリに対するメッセージの最大バイト長が高々ℓmax バイトであるとする．このとき，高々µM + q + µ′C ′ + q ′′ 回オラクルにクエリする CC に対する敵 B が存在し，
prf′′
Advint-rup
CC-Poly (A) ≤ AdvCC (B) + q

8⌈ℓmax /16⌉
2106

(29)

が成り立つ．また，B の実行時間は A の実行時間と O(σ + σ ′ + σ ′′ ) である．
以下，証明の概略を示す．一般性を失うことなく，A は確定的アルゴリズ
ムであり，それぞれのオラクルに q 回，q ′ 回，q ′′ 回アクセスするとする．証35

明は game-playing technique [BR06] に従う．図 8 にゲーム 0 とゲーム 1 の定義を示す．ゲーム 0 は枠内の処理を含み，ゲーム 1 は含まない．ゲーム 0 とゲーム 1 はフラグ forge が true にならない限り同一であるから，fundamental

lemma of game playing [BR06] より，
ゲーム 1
Advint-rup
sets forge]
CC-Poly (A) ≤ Pr[A(30)が成り立つ．
次に，CCK をランダム関数 F ← {f | f : {0, 1}32 × {0, 1}96 → {0, 1}512 }$に置き換えたゲームをゲーム 2 とする．ゲーム 2 を図 9 に示す．このとき，定理にある CC に対する敵 B が存在し，

Pr[Aゲーム 1 sets forge] − Pr[Aゲーム 2 sets forge] ≤ Advprf
CC (B)(31)が成り立つ．
ここでゲーム 2 において，F の入力 (0, N ) はタグ生成のみに用いられ KGenF
では使用されないため，EncF が暗号文 C の生成に利用する乱数と DecF が使用する乱数は，EncF がタグ T の生成に使用する乱数と VerF が使用する乱数とは独立である．とくに，DecF はフラグ forge を true とすることと独立である．

KGenF を A がシミュレートすると捉えれば，forge を true することは(N, A, C) 7→ T
によって定まるメッセージ認証コードに対して，q 回のタグ生成オラクルと

q ′′ 回のタグ検証オラクルへのアクセスにより偽造をすることに他ならない．
このときの偽装成功確率の上界は Procter の結果 [Pro14] より

Pr[Aゲーム 2 sets forge] ≤ q ′′8⌈ℓmax /16⌉
2106

(32)

となる．
式 (30)，式 (31)，式 (32) より，式 (29) を得る．

8.7

複数ユーザ安全性

CC-Poly の複数ユーザ安全性を解析した文献はないが，GCM についての解析が知られている [LMP17]．

ChaCha20-Poly1305 ではユーザ数が U であるとき，式 (16) より敵の攻撃
成功確率に関する自明な安全性バウンド
mu-prfAdvmu-AE(B) + U q ′′CC-Poly (A) ≤ AdvCC

368⌈ℓmax /16⌉
2106

(33)

Algorithm Initialize
1. K ← {0, 1}256$

2. forge ← false
Algorithm EncK (N, A, M )1. Z ← KGenK (N, len(M ))2. C ← M ⊕ Z
3. T ← TagK (N, A, C)
4. return (C, T )Algorithm DecK (N, A, C, T ∗ )1. Z ← KGenK (N, len(C))
2. M ← C ⊕ Z
3. return M
Algorithm VerK (N, A, C, T ∗ )1. T ← TagK (N, A, C)
2. if T = T ∗ then forge ← true; return ⊤3. return ⊥Algorithm KGenK (N, ℓ)
1. m ← ⌈ℓ/64⌉
2. for i = 1 to m do
3.

Z[i] ← CCK (i, N )4. Z ← first ℓ bytes of Z[1] ∥ · · · ∥ Z[m]5. return Z
Algorithm TagK (N, A, C)
16

1. (R, S) ←− first 32 bytes of CCK (0, N )2. R ← R ∧ 0x0ffffffc0ffffffc0ffffffc0fffffff
3. Y ← A ∥ pad(A) ∥ C ∥ pad(C) ∥ pad(A, C)
4. T ← PolyR (Y ) + S mod 2128
5. return T
Algorithm Finalize
1. return forge
図 8: ゲーム 0 とゲーム 1 の定義

37

Algorithm Initialize
1. F ← {f | f : {0, 1}32 × {0, 1}96 → {0, 1}512 }$2. forge ← false
Algorithm EncF (N, A, M )1. Z ← KGenF (N, len(M ))2. C ← M ⊕ Z
3. T ← TagF (N, A, C)
4. return (C, T )Algorithm DecF (N, A, C, T ∗ )1. Z ← KGenF (N, len(C))
2. M ← C ⊕ Z
3. return M
Algorithm VerF (N, A, C, T ∗ )1. T ← TagF (N, A, C)
2. if T = T ∗ then forge ← true
3. return ⊥Algorithm KGenF (N, ℓ)
1. m ← ⌈ℓ/64⌉
2. for i = 1 to m do
3.

Z[i] ← F (i, N )4. Z ← first ℓ bytes of Z[1] ∥ · · · ∥ Z[m]5. return Z
Algorithm TagF (N, A, C)
16

1. (R, S) ←− first 32 bytes of F (0, N )2. R ← R ∧ 0x0ffffffc0ffffffc0ffffffc0fffffff
3. Y ← A ∥ pad(A) ∥ C ∥ pad(C) ∥ pad(A, C)
4. T ← PolyR (Y ) + S mod 2128
5. return T
Algorithm Finalize
1. return forge
図 9: ゲーム 2 の定義

38

を得る．式 (33) は CC-Poly の複数ユーザにおける安全性を示しており，敵の攻撃成功確率の上界を導出できるという点で，ChaCha20-Poly1305 は複数
ユーザ安全性の意味で証明可能安全性を有している．
式 (33) において第一項の Advmu-prf(B) は計算量的な安全性を示しており，
CC[Bih02, BMS05] にある結果からこの項はこれ以上改善できず厳密である．一方で，情報理論的な項

U q ′′

8⌈ℓmax /16⌉
2106

は，[LMP17] と同様の解析を行うことにより，ユーザ数に依存せず，

q ′′8⌈ℓmax /16⌉
2106まで改善できると予想される．全体の安全性バウントとしては Advprf
CC (B) のみにユーザ数 U がかかり，それ以外への影響がなく，′′
U Advprf
CC (B) + q

8⌈ℓmax /16⌉
2106

を安全性バウンドとして示せるものと予想される．

9

まとめ
認証暗号化方式 ChaCha20-Poly1305 およびメッセージ認証コード Poly1305の安全性調査・評価を報告した．

Poly1305 について，Bernstein による安全性証明 [Ber05b, Ber05a] に問題点がないことを確認した．また文献調査により，弱鍵が存在すること，再偽造可能性の意味で耐性があること，ナンスを再利用すると多項式ハッシュ関数の鍵を導出でき，偽造攻撃ができることを確認した．
安全性評価として，関連鍵攻撃が可能であることと，複数ユーザ安全性についてユーザ数への依存が限定的な安全性バウンドを導出できることを示した．
また ChaCha20-Poly1305 について，Procter による証明 [Pro14] を修正することにより，ChaCha20-Poly1305 の証明可能安全性バウンドを導出できることを確認した．
安全性評価として，ChaCha20 ブロック関数が関連鍵攻撃に対して安全であれば ChaCha20-Poly1305 が関連鍵攻撃に対する安全性を有すること，再偽造可能性の意味で耐性があること，ナンスを再利用すると偽造攻撃ができること，弱鍵が存在することを示した．また，復号ミスユース耐性について，
暗号化の意味での安全性は失われるものの，認証の意味での安全性は保たれること，複数ユーザ安全性について，ユーザ数に依存した自明な安全性バウンドを導出できることを示した．
上記のうち，ナンスの再利用による安全性への影響は大きいことは懸念事項であり，注意して実装されなくてはならない．弱鍵の影響は少ないと考え39

られ，また Poly1305 の関連鍵攻撃が現実的に問題となることはないと考えられる．その他，懸念事項は見受けられない．

謝辞
本報告書は名古屋大学大学院工学研究科計算理工学専攻，今村和弥君の協力を得て作成した．

参考文献[ABBT15] Mohamed Ahmed Abdelraheem, Peter Beelen, Andrey Bogdanov, and Elmar Tischhauser.

Twisted Polynomials andForgery Attacks on GCM. In Elisabeth Oswald and Marc Fischlin, editors, Advances in Cryptology - EUROCRYPT 2015 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, April
26-30, 2015, Proceedings, Part I, volume 9056 of Lecture Notes
in Computer Science, pages 762–786. Springer, 2015.
[ABL+ 14] Elena Andreeva, Andrey Bogdanov, Atul Luykx, Bart Mennink, Nicky Mouha, and Kan Yasuda. How to Securely Release
Unverified Plaintext in Authenticated Encryption. In Palash
Sarkar and Tetsu Iwata, editors, Advances in Cryptology - ASIACRYPT 2014 - 20th International Conference on the Theory and Application of Cryptology and Information Security,
Kaoshiung, Taiwan, R.O.C., December 7-11, 2014. Proceedings, Part I, volume 8873 of Lecture Notes in Computer Science,
pages 105–125. Springer, 2014.
[ADL17]

Tomer Ashur, Orr Dunkelman, and Atul Luykx.

Boosting

Authenticated Encryption Robustness with Minimal Modifications. In Jonathan Katz and Hovav Shacham, editors, Advancesin Cryptology - CRYPTO 2017 - 37th Annual International
Cryptology Conference, Santa Barbara, CA, USA, August 2024, 2017, Proceedings, Part III, volume 10403 of Lecture Notes
in Computer Science, pages 3–33. Springer, 2017.
[BBT16]

Mihir Bellare, Daniel J. Bernstein, and Stefano Tessaro. HashFunction Based PRFs: AMAC and Its Multi-User Security.
In Marc Fischlin and Jean-Sébastien Coron, editors, Advances40

in Cryptology - EUROCRYPT 2016 - 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part I, volume 9665 of Lecture Notes in Computer Science,
pages 566–595. Springer, 2016.
[BC09]

John Black and Martin Cochran. MAC Reforgeability. In Orr
Dunkelman, editor, Fast Software Encryption, 16th International Workshop, FSE 2009, Leuven, Belgium, February 22-25,
2009, Revised Selected Papers, volume 5665 of Lecture Notes in
Computer Science, pages 345–362. Springer, 2009.

[Ber05a]Daniel J. Bernstein. Stronger Security Bounds for WegmanCarter-Shoup Authenticators. In Ronald Cramer, editor, Advances in Cryptology - EUROCRYPT 2005, 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Aarhus, Denmark, May 22-26, 2005, Proceedings, volume 3494 of Lecture Notes in Computer Science,
pages 164–180. Springer, 2005.

[Ber05b]Daniel J. Bernstein.
The Poly1305-AES MessageAuthentication Code. In Henri Gilbert and Helena Handschuh,
editors, Fast Software Encryption: 12th International Workshop, FSE 2005, Paris, France, February 21-23, 2005, Revised
Selected Papers, volume 3557 of Lecture Notes in Computer
Science, pages 32–49. Springer, 2005.

[Ber08]Daniel. J. Bernstein. ChaCha, a variant of Salsa20. Workshop
Record of SASC 2008: The State of the Art of Stream Ciphers,
2008. http://cr.yp.to/papers.html#chacha.

[Bih02]Eli Biham. How to decrypt or even substitute DES-encrypted
messages in 228 steps. Inf. Process. Lett., 84(3):117–124, 2002.

[BKR00]Mihir Bellare, Joe Kilian, and Phillip Rogaway. The Securityof the Cipher Block Chaining Message Authentication Code. J.
Comput. Syst. Sci., 61(3):362–399, 2000.

[BMS05]

Alex Biryukov, Sourav Mukhopadhyay, and Palash Sarkar. Improved Time-Memory Trade-Oﬀs with Multiple Data. In Bart
Preneel and Staﬀord E. Tavares, editors, Selected Areas in Cryptography, 12th International Workshop, SAC 2005, Kingston,41

ON, Canada, August 11-12, 2005, Revised Selected Papers, volume 3897 of Lecture Notes in Computer Science, pages 110–127.
Springer, 2005.
[BN08]

Mihir Bellare and Chanathip Namprempre. Authenticated Encryption: Relations among Notions and Analysis of the GenericComposition Paradigm. J. Cryptology, 21(4):469–491, 2008.

[BR02]

John Black and Phillip Rogaway. A Block-Cipher Mode of Operation for Parallelizable Message Authentication. In Lars R.
Knudsen, editor, Advances in Cryptology - EUROCRYPT 2002,
International Conference on the Theory and Applications of
Cryptographic Techniques, Amsterdam, The Netherlands, April
28 - May 2, 2002, Proceedings, volume 2332 of Lecture Notes in
Computer Science, pages 384–397. Springer, 2002.

[BR06]

Mihir Bellare and Phillip Rogaway.

The Security of Triple

Encryption and a Framework for Code-Based Game-Playing
Proofs. In Serge Vaudenay, editor, Advances in Cryptology EUROCRYPT 2006, 25th Annual International Conference on
the Theory and Applications of Cryptographic Techniques, St.
Petersburg, Russia, May 28 - June 1, 2006, Proceedings, volume 4004 of Lecture Notes in Computer Science, pages 409–426.
Springer, 2006.
[CMS11]Sanjit Chatterjee, Alfred Menezes, and Palash Sarkar. Another
Look at Tightness. In Ali Miri and Serge Vaudenay, editors,
Selected Areas in Cryptography - 18th International Workshop,
SAC 2011, Toronto, ON, Canada, August 11-12, 2011, Revised
Selected Papers, volume 7118 of Lecture Notes in Computer Science, pages 293–319. Springer, 2011.

[CW79]

Larry Carter and Mark N. Wegman. Universal Classes of Hash
Functions. J. Comput. Syst. Sci., 18(2):143–154, 1979.

[DFK+ 17] Antoine Delignat-Lavaud, Cédric Fournet, Markulf Kohlweiss,
Jonathan Protzenko, Aseem Rastogi, Nikhil Swamy, Santiago Zanella Béguelin, Karthikeyan Bhargavan, Jianyang Pan,and Jean Karim Zinzindohoue. Implementing and Proving the
TLS 1.3 Record Layer. In 2017 IEEE Symposium on Security
and Privacy, SP 2017, San Jose, CA, USA, May 22-26, 2017,
pages 463–482. IEEE Computer Society, 2017.

42

[FJM14]

Pierre-Alain Fouque, Antoine Joux, and Chrysanthi Mavromati. Multi-user Collisions: Applications to Discrete Logarithm, Even-Mansour and PRINCE. In Palash Sarkar and Tetsu
Iwata, editors, Advances in Cryptology - ASIACRYPT 2014 20th International Conference on the Theory and Applicationof Cryptology and Information Security, Kaoshiung, Taiwan,
R.O.C., December 7-11, 2014. Proceedings, Part I, volume 8873
of Lecture Notes in Computer Science, pages 420–438. Springer,
2014.

[FLLW17] Christian Forler, Eik List, Stefan Lucks, and Jakob Wenzel.
Reforgeability of Authenticated Encryption Schemes. In Josef
Pieprzyk and Suriadi Suriadi, editors, Information Security andPrivacy - 22nd Australasian Conference, ACISP 2017, Auckland, New Zealand, July 3-5, 2017, Proceedings, Part II, volume 10343 of Lecture Notes in Computer Science, pages 19–37.
Springer, 2017.
[HP08]

Helena Handschuh and Bart Preneel. Key-Recovery Attacks on
Universal Hash Function Based MAC Algorithms. In David A.
Wagner, editor, Advances in Cryptology - CRYPTO 2008, 28th
Annual International Cryptology Conference, Santa Barbara,
CA, USA, August 17-21, 2008. Proceedings, volume 5157 ofLecture Notes in Computer Science, pages 144–161. Springer,
2008.

[HT16]

Viet Tung Hoang and Stefano Tessaro. Key-Alternating Ciphersand Key-Length Extension: Exact Bounds and Multi-user Security. In Matthew Robshaw and Jonathan Katz, editors, Advances in Cryptology - CRYPTO 2016 - 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August
14-18, 2016, Proceedings, Part I, volume 9814 of Lecture Notes
in Computer Science, pages 3–32. Springer, 2016.

[HT17]

Viet Tung Hoang and Stefano Tessaro. The Multi-user Security of Double Encryption. In Jean-Sébastien Coron and Jesper Buus Nielsen, editors, Advances in Cryptology - EUROCRYPT 2017 - 36th Annual International Conference on the
Theory and Applications of Cryptographic Techniques, Paris,
France, April 30 - May 4, 2017, Proceedings, Part II, volume10211 of Lecture Notes in Computer Science, pages 381–411,
2017.
43

[II16]

今村 和弥, 岩田 哲. ChaCha20-Poly1305 の Nonce-Misuse および Decryption-Misuse 耐性. 2016 年暗号と情報セキュリティシン
ポジウム，SCIS 2016, 2016.

[Ima17]

今村 和弥. ストリーム暗号とユニバーサルハッシュ関数に基づく認証暗号化方式の安全性に関する研究. 名古屋大学工学研究科計算理工学専攻修士論文, 2017.

[IMI16]

Kazuya Imamura, Kazuhiko Minematsu, and Tetsu Iwata. Integrity Analysis of Authenticated Encryption Based on Stream
Ciphers. In Liqun Chen and Jinguang Han, editors, Provable
Security - 10th International Conference, ProvSec 2016, Nanjing, China, November 10-11, 2016, Proceedings, volume 10005
of Lecture Notes in Computer Science, pages 257–276, 2016.

[IMI17]

Kazuya Imamura, Kazuhiko Minematsu, and Tetsu Iwata. Integrity analysis of authenticated encryption based on stream ciphers. International Journal of Information Security, Jun 2017.

[Kra94]

Hugo Krawczyk. LFSR-based Hashing and Authentication. In
Yvo Desmedt, editor, Advances in Cryptology - CRYPTO ’94,
14th Annual International Cryptology Conference, Santa Barbara, California, USA, August 21-25, 1994, Proceedings, volume 839 of Lecture Notes in Computer Science, pages 129–139.
Springer, 1994.

[LCM+ 16] Adam Langley, Wan-Teh Chang, Nikos Mavrogiannopoulos,
Joachim Strombergson, and Simon Josefsson.

ChaCha20-

Poly1305 Cipher Suites for Transport Layer Security (TLS).
RFC 7905, 2016. https://tools.ietf.org/html/rfc7905.
[LMP17]Atul Luykx, Bart Mennink, and Kenneth G. Paterson. Analyzing Multi-key Security Degradation. In Tsuyoshi Takagi andThomas Peyrin, editors, Advances in Cryptology - ASIACRYPT
2017 - 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong,
China, December 3-7, 2017, Proceedings, Part II, volume 10625
of Lecture Notes in Computer Science, pages 575–605. Springer,
2017.

[ML15]

Nicky Mouha and Atul Luykx. Multi-key Security: The EvenMansour Construction Revisited.

In Rosario Gennaro andMatthew Robshaw, editors, Advances in Cryptology - CRYPTO
44

2015 - 35th Annual Cryptology Conference, Santa Barbara, CA,
USA, August 16-20, 2015, Proceedings, Part I, volume 9215 ofLecture Notes in Computer Science, pages 209–223. Springer,
2015.
[NL15]

Yoav

Nir

Poly1305

and
for

Adam

IETF

Langley.

Protocols.

ChaCha20
RFC

7539,

and
2015.

https://tools.ietf.org/html/rfc7539.
[PC13]

Gordon Procter and Carlos Cid. On Weak Keys and Forgery
Attacks Against Polynomial-Based MAC Schemes. In Shiho
Moriai, editor, Fast Software Encryption - 20th International
Workshop, FSE 2013, Singapore, March 11-13, 2013. Revised
Selected Papers, volume 8424 of Lecture Notes in Computer Science, pages 287–304. Springer, 2013.

[PC15]

Gordon Procter and Carlos Cid. On Weak Keys and Forgery Attacks Against Polynomial-Based MAC Schemes. J. Cryptology,
28(4):769–795, 2015.

[Pro14]

Gordon Procter. A Security Analysis of the Composition of
ChaCha20 and Poly1305. IACR Cryptology ePrint Archive,
2014:613, 2014.

[RBB03]

Phillip Rogaway, Mihir Bellare, and John Black. OCB: A blockcipher mode of operation for eﬃcient authenticated encryption.
ACM Trans. Inf. Syst. Secur., 6(3):365–403, 2003.

[Saa12]

Markku-Juhani Olavi Saarinen.

Cycling Attacks on GCM,

GHASH and Other Polynomial MACs and Hashes. In Anne
Canteaut, editor, Fast Software Encryption - 19th International
Workshop, FSE 2012, Washington, DC, USA, March 19-21,
2012. Revised Selected Papers, volume 7549 of Lecture Notes in
Computer Science, pages 216–225. Springer, 2012.
[Sho96]

Victor Shoup. On Fast and Provably Secure Message Authentication Based on Universal Hashing. In Neal Koblitz, editor,
Advances in Cryptology - CRYPTO ’96, 16th Annual International Cryptology Conference, Santa Barbara, California, USA,
August 18-22, 1996, Proceedings, volume 1109 of Lecture Notes
in Computer Science, pages 313–328. Springer, 1996.

[ST16]

Thomas Shrimpton and R. Seth Terashima. Salvaging Weak
Security Bounds for Blockcipher-Based Constructions.
45

InJung Hee Cheon and Tsuyoshi Takagi, editors, Advances in
Cryptology - ASIACRYPT 2016 - 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, December 4-8, 2016, Proceedings, Part I, volume 10031 of Lecture Notes in Computer
Science, pages 429–454, 2016.
[Sti95]

Douglas R. Stinson. On the Connections Between Universal
Hashing, Combinatorial Designs and Error-Correcting Codes.
Electronic Colloquium on Computational Complexity (ECCC),
2(52), 1995.

[WLW06a] Dayin Wang, Dongdai Lin, and Wenling Wu. An Improved
Poly1305 MAC. In Jianying Zhou, Moti Yung, and Feng Bao,
editors, Applied Cryptography and Network Security, 4th International Conference, ACNS 2006, Singapore, June 6-9, 2006,
Proceedings, volume 3989 of Lecture Notes in Computer Science, pages 284–292, 2006.
[WLW06b] Dayin Wang, Dongdai Lin, and Wenling Wu. OPMAC: OneKey Poly1305 MAC. In Helger Lipmaa, Moti Yung, and Dongdai Lin, editors, Information Security and Cryptology, Second
SKLOIS Conference, Inscrypt 2006, Beijing, China, November
29 - December 1, 2006, Proceedings, volume 4318 of Lecture
Notes in Computer Science, pages 78–87. Springer, 2006.
[WLZZ16] Peng Wang, Yuling Li, Liting Zhang, and Kaiyan Zheng.
Related-Key Almost Universal Hash Functions: Definitions,
Constructions and Applications.

In Thomas Peyrin, editor,

Fast Software Encryption - 23rd International Conference, FSE
2016, Bochum, Germany, March 20-23, 2016, Revised Selected
Papers, volume 9783 of Lecture Notes in Computer Science,
pages 514–532. Springer, 2016.

A

ChaCha20 ブロック関数の仕様

CC-Poly では内部で ChaCha20 のブロック関数 CC を用いる [Ber08]．CCの入出力は

CC : KCC × {0, 1}32 × {0, 1}96 → {0, 1}512で与えられる．KCC = {0, 1}256 は鍵空間である．入力として 256 ビット（32バイト）の秘密鍵 K ，32 ビット（4 バイト）のカウンタ ctr，および 96 ビッ

46

ト（12 バイト）のナンス N をとり，512 ビット（64 バイト）の鍵ストリー
ム Z を出力する．
状態配列

状態配列は 512 ビット（64 バイト）からなり，これを 32 ビット（4 バイト）ごとに区切り，行列
X[0] X[1] X[4] X[5]X=
 X[8] X[9]
X[12] X[13]

X[2]

X[3]




X[7] 

X[10] X[11]
X[14] X[15]X[6]4として表現する．入力である鍵 K とナンス N を (K[0], . . . , K[7]) ←− K およ4び (N [0], N [1], N [2]) ←− N と 4 バイトごとに分割し，状態配列を
Con[0] Con[0] Con[2] Con[3] K[0]
K[1]K[2]
K[3] 


X=

K[4]
K[5]
K[6]
K[7]


ctr
N [0]
N [1]
N [2]

(34)

と初期化する．ただし，Con[i] は定数であり，Con[0] = 0x61707865，Con[1] =0x3320646e，Con[2] = 0x79622d32，Con[3] = 0x6b206574 である．
ラウンド処理ラウンド処理は 1/4 ラウンド関数 QuaterRound を基本とす

る，全部で 20 ラウンドからなる処理である．QuaterRound の定義を図 10 に示す．また，図 11 に動作の流れを示す．ただし，X ≪ n はバイト列 X を

n ビット左に巡回シフトしたバイト列を表す．
各ラウンドでは，奇数ラウンドにおいて列成分に QuaterRound を適用し，
偶数ラウンドでは対角成分に QuaterRound を適用する．CCK (ctr, N ) の定義を図 12 に示す．

47

Algorithm QuaterRound(a, b, c, d)
1. a ← a + b mod 232
2. d ← d ⊕ a
3. d ← d ≪ 16
4. c ← c + d mod 232
5. b ← b ⊕ c
6. b ← b ≪ 12
7. a ← a + b mod 232
8. d ← d ⊕ a
9. d ← d ≪ 8
10. c ← c + d mod 232
11. b ← b ⊕ c
12. b ← b ≪ 7
図 10: QuaterRound(a, b, c, d) の定義

48

a

b

c

d

≪ 16

≪ 12

≪8

≪7
a

b

c

d

図 11: QuaterRound(a, b, c, d) の動作

49

Algorithm CCK (ctr, N )1. Xinit ← 式 (34) の行列
2. X ← Xinit
3. for i = 1 to 10 do
4.

QuaterRound(X[0], X[4], X[8], X[12])5.

QuaterRound(X[1], X[5], X[9], X[13]))

6.

QuaterRound(X[2], X[6], X[10], X[14]))

7.

QuaterRound(X[3], X[7], X[11], X[15])8.

QuaterRound(X[0], X[5], X[10], X[15])9.

QuaterRound(X[1], X[6], X[11], X[12])10.

QuaterRound(X[2], X[7], X[8], X[13])11.

QuaterRound(X[3], X[4], X[9], X[14])12. X ← X + Xinit mod 232// 行列の成分ごとの和13. Z ← X[0] ∥ · · · ∥ X[15]14. return Z
図 12: Z ← CCK (ctr, N ) の定義

50