ポリ1305

Poly1305は、暗号化に使用するためにDaniel J. Bernsteinによって設計されたユニバーサルハッシュファミリです。^[1]

他のユニバーサルハッシュファミリと同様に、Poly1305は、送信者と受信者が共有する秘密鍵を使用して単一のメッセージを認証するためのワンタイムメッセージ認証コードとして使用できます。 ^[2] これは、送信者と受信者が共有する秘密鍵を使用して単一のメッセージの内容を隠すためにワンタイムパッドを使用できる方法に似ています。

^{もともとPoly1305はPoly1305-AES [3]}の一部として提案されました。Poly1305-AESは Carter–Wegman認証子^{[4] [5] [1]} で、Poly1305ハッシュとAES-128を組み合わせて、単一の短いキーと個別のメッセージ番号を使用して多くのメッセージを認証します。Poly1305は後に、NaCl crypto_secretbox_xsalsa20poly1305認証暗号^[6]でXSalsa20を使用して各メッセージに生成された使い捨てキーとともに適用され 、その後、インターネット上のTLS に展開されたChaCha20-Poly1305認証暗号^{[7] [8] [1]}でChaChaを使用して適用されました。 ^[9]

Poly1305は16バイトの秘密鍵と16バイトのメッセージを受け取り、16バイトのハッシュを返します。これを行うために、Poly1305は次の処理を行います。^{[3] [1]}${\displaystyle r}$${\displaystyle L}$${\displaystyle m}$${\displaystyle \operatorname {Poly1305} _{r}(m)}$

1. リトルエンディアンの 16 バイト整数として解釈されます。${\displaystyle r}$
2. メッセージを連続する 16 バイトのチャンクに分割します。${\displaystyle m=(m[0],m[1],m[2],\dotsc ,m[L-1])}$
3. 16 バイトのチャンクごとに 1 バイトを追加して、16 バイトのチャンクを 17 バイトのリトルエンディアン整数として解釈し、多項式の係数として使用します。
4. 素数 を法として点における多項式を評価します。${\displaystyle r}$${\displaystyle 2^{130}-5}$
5. リトルエンディアン形式でエンコードされた結果を剰余して、 16 バイトのハッシュを返します。${\displaystyle 2^{128}}$

多項式 の係数（ ）は次のようになります。 ${\displaystyle c_{i}}$${\displaystyle c_{1}r^{q}+c_{2}r^{q-1}+\cdots +c_{q}r}$${\displaystyle q=\lceil L/16\rceil }$

$${\displaystyle c_{i}=m[16i-16]+2^{8}m[16i-15]+2^{16}m[16i-14]+\cdots +2^{120}m[16i-1]+2^{128},}$$

ただし、の場合は次のようになります。 ${\displaystyle L\not \equiv 0{\pmod {16}}}$

$${\displaystyle c_{q}=m[16q-16]+2^{8}m[16q-15]+\cdots +2^{8(L{\bmod {1}}6)-8}m[ L-1]+2^{8(L{\bmod {1}}6)}.}$$

秘密鍵は、バイト（つまり、上位 4 ビットがクリア）を持ち、バイト（つまり、下位 2 ビットがクリア）を持つように制限されています。したがって、には異なる値が考えられます。 ${\displaystyle r=(r[0],r[1],r[2],\dotsc ,r[15])}$${\displaystyle r[3],r[7],r[11],r[15]\in \{0,1,2,\dotsc ,15\}}$${\displaystyle r[4],r[8],r[12]\in \{0,4,8,\dotsc ,252\}}$${\displaystyle 2^{106}}$${\displaystyle r}$

がリトルエンディアンの整数として解釈される秘密の16バイト文字列である 場合、${\displaystyle s}$

$${\displaystyle a:={\bigl (}\operatorname {Poly1305} _{r}(m)+s{\bigr )}{\bmod {2}}^{128}}$$

はメッセージの認証子と呼ばれます。送信者と受信者が事前に一様にランダムに選ばれた32バイトの秘密鍵を共有していれば、送信者は認証されたメッセージを送信できます。受信者が認証されたとされるメッセージ（送信中に敵対者によって変更されている可能性があります）を受信すると、受信者は以下をテストすることでその真正性を検証できます。 ${\displaystyle m}$${\displaystyle (r,s)}$${\displaystyle (a,m)}$${\displaystyle (a',m')}$

$${\displaystyle a'\mathrel {\stackrel {?}{=}} {\bigl (}\operatorname {Poly1305} _{r}(m')+s{\bigr )}{\bmod {2}}^{128}.}$$ を知らなければ、攻撃者は検証に合格する を見つける可能性があります。 ${\displaystyle (r,s)}$${\displaystyle 8\lceil L/16\rceil /2^{106}}$${\displaystyle (a',m')\neq (a,m)}$

しかし、同じ鍵を2つのメッセージに再利用してはいけません。もし攻撃者が ${\displaystyle (r,s)}$

$${\displaystyle {\begin{aligned}a_{1}&={\bigl (}\operatorname {Poly1305} _{r}(m_{1})+s{\bigr )}{\bmod {2}}^{128},\\a_{2}&={\bigl (}\operatorname {Poly1305} _{r}(m_{2})+s{\bigr )}{\bmod {2}}^{128},\end{aligned}}}$$

の場合、減算できる ${\displaystyle m_{1}\neq m_{2}}$

$${\displaystyle a_{1}-a_{2}\equiv \operatorname {Poly1305} _{r}(m_{1})-\operatorname {Poly1305} _{r}(m_{2}){\pmod {2^{128}}}}$$

そして、結果として得られる多項式の根を見つけて、秘密の評価点 の候補の小さなリストを復元し、そこから秘密のパッド を復元します。敵対者はこれを使用して、高い確率で追加のメッセージを偽造できます。 ${\displaystyle r}$${\displaystyle s}$

オリジナルのPoly1305-AES提案^[3]では、 Carter–Wegman構造^{[4] [5]を使用して、 を}i番目のメッセージの認証子としてとることで、多くのメッセージを認証します。ここで、 はユニバーサルハッシュファミリであり、 はそれを隠すためのワンタイムパッドとして機能する独立した一様ランダムハッシュ値です。Poly1305-AESはAES-128を使用してを生成します。ここで、 は16バイトのリトルエンディアン整数としてエンコードされます。 ${\displaystyle a_{i}:=H_{r}(m_{i})+p_{i}}$${\displaystyle m_{i}}$${\displaystyle H_{r}}$${\displaystyle p_{i}}$${\displaystyle p_{i}:=\operatorname {AES} _{k}(i)}$${\displaystyle i}$

具体的には、Poly1305-AES鍵は、上記の16バイトの評価ポイントと16バイトのAES鍵の32バイトのペアです。メッセージのPoly1305-AES認証子は、 ${\displaystyle (r,k)}$${\displaystyle r}$${\displaystyle k}$${\displaystyle m_{i}}$

$${\displaystyle a_{i}:={\bigl (}\operatorname {Poly1305} _{r}(m_{i})+\operatorname {AES} _{k}(i){\bigr )}{\bmod {2}}^{128},}$$

16 バイトの文字列と整数は、リトルエンディアン エンコードによって識別されます。メッセージ間で再利用されることに注意してください。 ${\displaystyle r}$

を知らないと、攻撃者が受信者が本物として受け入れる認証済みメッセージを偽造する可能性は低くなります。攻撃者が認証済みメッセージを見て偽造を試み、最大で の利点で一様ランダム順列と区別できるとします。(AES が破られない限り、は非常に小さいです。) 攻撃者が 1 回の偽造に成功する可能性は最大で次のようになります。 ${\displaystyle (r,k)}$${\displaystyle C}$${\displaystyle D}$${\displaystyle \operatorname {AES} _{k}}$${\displaystyle \delta}$${\displaystyle \delta}$

$${\displaystyle \delta +{\frac {(1-C/2^{128})^{-(C+1)/2}\cdot 8D\lceil L/16\rceil }{2^{106}}}.}$$

メッセージ番号は、同じキー で決して繰り返されてはなりません。 繰り返されると、攻撃者は、ワンタイム認証子の場合と同様に、 と の候補の小さなリストを復元し、それを使用してメッセージを偽造することができます。${\displaystyle i}$${\displaystyle (r,k)}$${\displaystyle r}$${\displaystyle \operatorname {AES} _{k}(i)}$

NaCl crypto_secretbox_xsalsa20poly1305 認証暗号は、 XSalsa20ストリーム暗号でメッセージ番号を使用してメッセージごとのキー ストリームを生成します。最初の 32 バイトは 1 回限りの Poly1305 キーとして取得され、残りはメッセージの暗号化に使用されます。次に、メッセージの暗号文の 1 回限りの認証子として Poly1305 を使用します。^[6] ChaCha20-Poly1305も同様ですが、XSalsa20の代わりにChaChaを使用します。^[8]${\displaystyle i}$${\displaystyle (r_{i},s_{i})}$

Poly1305とその派生物の偽造に対する安全性は、その普遍的なハッシュ族としての境界差確率から導かれる。と がそれぞれ最大バイトのメッセージであり、 がリトルエンディアンの整数として解釈される任意の16バイトの文字列である場合、 ${\displaystyle m_{1}}$${\displaystyle m_{2}}$${\displaystyle L}$${\displaystyle d}$

$${\displaystyle \Pr[\operatorname {Poly1305} _{r}(m_{1})-\operatorname {Poly1305} _{r}(m_{2})\equiv d{\pmod {2^{128}}}]\leq {\frac {8\lceil L/16\rceil }{2^{106}}},}$$

ここで、は均一ランダムPoly1305キーである。^{[3] ：定理3.3、p.8}${\displaystyle r}$

この性質は、上で-ほぼΔ-普遍性、または-AΔUと呼ばれることもあります^[10]。この場合 、${\displaystyle \epsilon }$${\displaystyle \mathbb {Z} /2^{128}\mathbb {Z} }$${\displaystyle \epsilon }$${\displaystyle \epsilon =8\lceil L/16\rceil /2^{106}}$

ワンタイム認証子を使用すると、最大 バイトのメッセージに対する攻撃者の偽造試行の成功確率は次のようになります。 ${\displaystyle a={\bigl (}\operatorname {Poly1305} _{r}(m)+s{\bigr )}{\bmod {2}}^{128}}$${\displaystyle (a',m')}$${\displaystyle m'}$${\displaystyle L}$

$${\displaystyle {\begin{aligned}\Pr[&a'=\operatorname {Poly1305} _{r}(m')+s\mathrel {\mid } a=\operatorname {Poly1305} _{r}(m)+s]\\&=\Pr[a'=\operatorname {Poly1305} _{r}(m')+a-\operatorname {Poly1305} _{r}(m)]\\&=\Pr[\operatorname {Poly1305} _{r}(m')-\operatorname {Poly1305} _{r}(m)=a'-a]\\&\leq 8\lceil L/16\rceil /2^{106}.\end{aligned}}}$$

ここでは、簡単にするために、 内の算術はであるとみなされます。 ${\displaystyle \Pr[\cdots ]}$${\displaystyle \mathbb {Z} /2^{128}\mathbb {Z} }$

NaCl crypto_secretbox_xsalsa20poly1305 およびChaCha20-Poly1305の場合、偽造における敵対者の成功確率は、ワンタイム認証子の場合と同様に各メッセージごとに独立して同じであり、さらに、メッセージごとのキーを生成するために使用される疑似乱数関数としての XSalsa20 または ChaCha に対する敵対者の際立った利点があります。言い換えると、最大 バイトのメッセージの試行後に敵対者が単一の偽造に成功する確率は、最大で次のようになります。 ${\displaystyle \delta }$${\displaystyle D}$${\displaystyle L}$

$${\displaystyle \delta +{\frac {8D\lceil L/16\rceil }{2^{106}}}.}$$

Poly1305-AES の偽造に対する安全性は、Carter–Wegman–Shoup 構造から導かれます。この構造は、Carter–Wegman 認証子を順列でインスタンス化して、メッセージごとのパッドを生成します。^[11] 攻撃者が認証されたメッセージを見て、最大 バイトのメッセージの偽造を試み、攻撃者が疑似ランダム順列として AES-128 に対して最大で際立った優位性を持っている場合、攻撃者がいずれかの偽造に成功する確率は最大で次のようになります。^[3]${\displaystyle C}$${\displaystyle D}$${\displaystyle L}$${\displaystyle \delta }$${\displaystyle D}$

$${\displaystyle \delta +{\frac {(1-C/2^{128})^{-(C+1)/2}\cdot 8D\lceil L/16\rceil }{2^{106}}}.}$$

例えば、メッセージが1024バイトまでのパケットであると仮定すると、攻撃者はPoly1305-AESキーで認証された2 ^{64個のメッセージを確認し、攻撃者はなんと2 75}回の偽造を試み、攻撃者はδ以上の確率でAESを破ることができない。この場合、少なくとも0.999999 − δの確率で、2 ⁷⁵回すべてが拒否される。

— バーンスタイン、ダニエル・J.（2005）^[3]

Poly1305-AESは、さまざまなCPUで高速に計算できます。たとえば、nバイトのメッセージの場合、 3.1n + 780 Athlonサイクルしか必要ありません^{[3] 。著者は、} Athlon、Pentium Pro/II/III/M、PowerPC、UltraSPARC向けに最適化されたソースコードと、 CおよびC++による最適化されていないリファレンス実装をパブリックドメインソフトウェアとしてリリースしています。^[12]

以下は、Poly1305 をサポートする暗号化ライブラリのリストです。

• ぼたん
• バウンシーキャッスル
• 暗号++
• ライブラリgcrypt
• リブナトリウム
• イラクサ
• オープンSSL
• リブレSSL
• ウルフクリプト
• TLS の
• mbed TLS
• マトリックスSSL

• ChaCha20-Poly1305 – ストリーム暗号ChaCha20とPoly1305の変種を組み合わせたAEAD方式

• Poly1305-AES リファレンスと最適化された実装 (著者 DJ Bernstein)
• github.com の C での高速 Poly1305 実装
• NaClワンタイム認証子と Poly1305 を使用した認証暗号