ポスト量子暗号のレイテンシー影響はデータ量の増加で軽減

本ブログは 2024 年 3 月 5 日に公開された Amazon Science Blog “Latency from post-quantum cryptography shrinks as data increases” を翻訳したものです。

ポスト量子暗号によりデータ量が増加した TLS 1.3 が実際の接続に与える影響を評価する際、最初のバイト到達時間 (TTFB: 最初のデータが届くまでの時間) ではなく最終バイト到達時間 (TTLB: データ転送が完了するまでの時間) を使用すると、より期待できる結果が得られます。

量子コンピュータが現在広く使用されている暗号標準を破る可能性があるというリスクは、ポスト量子暗号アルゴリズムの標準化と TLS 1.3 などのトランスポート暗号化プロトコルへの導入に向けた数多くの取り組みを促しています。ポスト量子アルゴリズムの選択は当然ながら TLS 1.3 のパフォーマンスに影響します。これまでの研究では、2 者間でポスト量子暗号接続を確立するために必要な「ハンドシェイク時間」、つまり最初のバイト到達時間 (TTFB) に焦点が当てられてきました。

これらの研究はハンドシェイク時間の増加を定量化する上で重要でしたが、実際の TLS 1.3 接続に対するポスト量子暗号の影響の全体像を示すものではありませんでした。実際の接続では、多くの場合かなりの量のデータが転送されます。2024 年の Workshop on Measurements, Attacks, and Defenses for the Web (MADweb) で、私たちは ML-KEM (ML 鍵カプセル化メカニズム) や ML-DSA (ML 電子署名アルゴリズム) などのデータ量の多いポスト量子暗号アルゴリズムが実際の TLS 1.3 接続に与える総合的な影響を評価する指標として最終バイト到達時間 (TTLB) を提唱する論文を発表しました。この論文では、新しいアルゴリズムがかなりの量のデータを転送する接続に与える実際の影響は、TLS 1.3 ハンドシェイク自体に与える影響よりもはるかに小さいことを示しています。

ポスト量子暗号

TLS 1.3 は、トランスポート層セキュリティプロトコルの最新バージョンであり、クライアントとサーバー間で転送されるデータを暗号化および認証するセキュアチャネルのネゴシエーションと確立に使用されます。TLS 1.3 は、オンラインバンクやストリーミングメディアなど、数多くの Web アプリケーションで使用されています。

TLS 1.3 で使用されているような非対称暗号アルゴリズムのセキュリティは、離散対数問題や素因数分解の困難さに依存していますが、暗号解読能力を持つ量子コンピュータが実現すれば、これらを効率的に解くことが可能になります。米国国立標準技術研究所 (NIST) はポスト量子暗号アルゴリズムの標準化に取り組んでおり、鍵交換用に ML-KEM を選定しました。また、署名 (暗号認証) 用に ML-DSA も選定しています。

これらのアルゴリズムが使用する公開鍵、暗号文、署名はキロバイト単位の大きさです。従来のアルゴリズムでは 50〜400 バイト程度だったため、TLS ハンドシェイクで交換されるデータ量が大幅に増加することになります。従来の TLS 1.3 鍵交換および認証とポスト量子鍵交換および認証を使用した場合のハンドシェイク時間を比較した研究が数多く行われてきました。

これらの比較は、各新アルゴリズムが最初のバイト到達時間 (TTFB)、つまりハンドシェイクプロトコルの完了に導入するオーバーヘッドを定量化するのに有用でした。しかし、ハンドシェイク時間とともにアプリケーションがデータ処理を開始するまでの総遅延を構成する、セキュア接続上のデータ転送時間は無視されていました。接続開始からデータ転送終了までの総時間が最終バイト到達時間 (TTLB) です。TTLB の遅延がどの程度許容されるかは、アプリケーションによって大きく異なります。

実験

私たちはさまざまなネットワーク条件をシミュレートする実験を設計し、クライアントが小さなリクエストを送信しサーバーが数百キロバイト (KB) のデータで応答する TLS 1.3 接続において、従来のアルゴリズムとポスト量子アルゴリズムの TTLB を測定しました。Ubuntu 22.04 仮想マシンインスタンスで Linux 名前空間を使用しました。名前空間は仮想イーサネットインターフェースを使用して相互接続されました。名前空間間の「ネットワーク」をエミュレートするために、Linux カーネルの netem ユーティリティを使用しました。これにより、クライアントとサーバー間にネットワーク遅延の変動、帯域幅の変動、パケット損失を発生させることができます。

実験では、以下のパラメータを変更することで、安定・不安定、高速・低速といったさまざまなネットワーク条件下でポスト量子アルゴリズムが TTLB に与える影響を比較しました。

• TLS 鍵交換メカニズム (従来の ECDH または ECDH+ML-KEM ポスト量子ハイブリッド)
• 従来の RSA または ML-DSA 証明書に対応する TLS 証明書チェーンサイズ
• TCP 初期輻輳ウィンドウ (initcwnd)
• クライアントとサーバー間のネットワーク遅延、またはラウンドトリップ時間 (RTT)
• クライアントとサーバー間の帯域幅
• パケットあたりの損失率
• サーバーからクライアントに転送されるデータ量

結果

実験結果は論文で詳細に分析されています。基本的に、ポスト量子の公開鍵、暗号文、署名による TLS 1.3 ハンドシェイクでの数 KB の追加データは、数百 KB 以上を転送する接続では気にならないことを示しています。10〜20 KB 未満のデータを転送する接続は、新しいデータ量の多いハンドシェイクの影響をより受ける可能性があります。

図 1 は、1Mbps 帯域幅、0%、1%、3%、10% の損失率、35 ミリ秒および 200 ミリ秒の RTT で収集された集計データセットの 50、75、90 パーセンタイルにおける TLS 1.3 ハンドシェイク時間の増加率を示しています。ML-DSA サイズ (16KB) の証明書チェーンは、8KB のチェーンのほぼ 2 倍の時間がかかることがわかります。つまり、ML-DSA 認証データの量を少なく抑えることができれば、低帯域幅接続でのポスト量子ハンドシェイクの速度が大幅に向上します。

図 2 は、損失率 0%、帯域幅 1Gbps の条件下で、すべてのパーセンタイルと異なるデータサイズにおける、従来のアルゴリズムに対するポスト量子ハンドシェイクの所要時間の増加率を示しています。サーバーからのデータが 0 KiB (キビバイト、1,024 バイト) の場合 (ハンドシェイクのみに相当)、速度低下は約 3% と小さく、サーバーからのデータ転送が増加するにつれて約 1% までさらに小さくなることがわかります。90 パーセンタイルでは速度低下がわずかに小さくなっています。

図 3 は、帯域幅 1Mbps、RTT 200ms、損失率 0% の条件下で、サーバーから 0〜200KiB のデータを転送する従来の TLS 1.3 接続とポスト量子 TLS 1.3 接続間の TTLB 増加率を各パーセンタイルで示しています。3 つのパーセンタイルの増加率はほぼ同じです。サーバーからのデータが 0KiB の場合は高い値 (約 33%) から始まりますが、サーバーからのデータサイズが増加するにつれて約 6% まで低下します。これは、ハンドシェイクのデータサイズが接続全体で分散されるためです。

図 4 は、帯域幅 1Mbps、RTT 200ms、損失率 10% の条件下で、サーバーから 0〜200 KiB のデータを転送する従来の TLS 1.3 接続とポスト量子 TLS 1.3 接続間の TTLB 増加率を各パーセンタイルで示しています。損失率 10% では、TTLB の増加率はすべてのパーセンタイルで 20〜30% の範囲に収まります。RTT 35ms での同じ実験でも同様の結果が得られました。20〜30% の増加は高いように見えるかもしれませんが、シナリオ全体のネットワーク不安定性により、実験を再実行すると増加率が小さくなったり大きくなったりすることがあります。また、サーバーからのデータ 200KiB、RTT 200ms、損失率 10% の条件下での従来のアルゴリズムの TTLB は 4,644ms、7,093ms、10,178ms であったのに対し、ポスト量子接続の同等値は 6,010ms、8,883ms、12,378ms でした。損失率 0% では 2,364ms、2,364ms、2,364ms でした。つまり、ポスト量子接続の TTLB は従来の接続に比べて 20〜30% 増加しましたが、従来の接続はすでにネットワーク損失により (97〜331%) 劣化しています。すでに大幅に劣化した接続時間に対して、追加の 20〜30% はそれほど大きな違いにはならないでしょう。

図 5 は、損失率 0%、サーバーから 0〜200KiB のデータを転送する条件下での、従来の TLS 1.3 接続とポスト量子 TLS 1.3 接続間の TTLB 増加率を示しています。非常に不安定な RTT をモデル化するために、平均 35ms、ジッター 35/4ms のパレート正規分布を使用しました。ポスト量子接続の TTLB 増加率は、サーバーデータ 0KiB で高い値から始まり、4〜5% まで低下します。以前の実験と同様に、損失率が高いほど増加率の変動は大きくなりましたが、全体として、「不安定なネットワーク条件」下でも転送データ量が増加するにつれて TTLB は許容可能なレベルまで低下することが結果から示されています。

不安定なネットワーク条件下での変動を確認するために、サーバーから 200KiB を転送するポスト量子 TLS 1.3 接続の TTLB 累積分布関数 (CDF) を使用しました (図 6)。あらゆる種類の不安定な条件 (1Gbps で損失率 5%、1Mbps で損失率 10%、パレート正規分布のネットワーク遅延) において、TTLB は実験測定サンプルの非常に早い段階で増加しており、総接続時間が非常に不安定であることを示しています。不安定なネットワーク条件下での TLS 1.3 ハンドシェイク時間でも同じ観察結果が得られました。

結論

この研究では、データ量の多いポスト量子アルゴリズムが TLS 1.3 接続に与える実際の影響は、ハンドシェイク自体に与える影響よりも小さいことを実証しました。損失率が低く、低帯域幅または高帯域幅の接続では、かなりの量のデータを転送する場合、ポスト量子ハンドシェイクの影響はほとんどありません。また、損失率が高い不安定な条件や遅延の変動が大きい条件下では、ポスト量子ハンドシェイクの影響は変動する可能性がありますが、一定の範囲内に収まり、転送データの総量が増加するにつれて低下することも示しました。さらに、不安定な接続ではそもそも接続完了までに長い時間がかかるため、ポスト量子ハンドシェイクによるわずかな遅延増加があっても、以前より使いにくくなることはありません。ただし、これはハンドシェイクデータ量の削減が不要という意味ではありません。アプリケーションデータの送信量がハンドシェイクメッセージのサイズに対して少ない場合は、ハンドシェイクデータの削減が特に重要になります。

詳細については、論文をご覧ください。