一方、QUICにおいては、UDPパケット毎に独立した、短いAEADブロックを暗号化する必要があり、したがって、次のような速度向上の機会があることが分かります。
AEAD処理をひとつの関数にまとめ、事前処理と事後処理を、パイプライン化されスティッチングされた暗号処理と並行に走らせることができれば、AEADブロックが短くても、理論値に近いスループットを発揮するような、AES-GCM実装を作ることができる（前半より引用）
この条件を満たすような関数を実装し、ボトルネックをつぶしていって速度向上を図るというのは一案です。しかし、往々にして、そのような対症療法的なプログラミングスタイルでは、何回もの変更に伴う手戻りが発生したり、必ずしも最適でないコードが成果物の一部に残ったりしがちです。
より効率的な設計手法はないものでしょうか。
■QUIC向けAES-GCM実装「fusion」の設計方針
幸いなことに、AES-GCMについては、第9世代Core CPUにおけるボトルネックがAES-NIであり、そのスループットの理論上の上限が64バイト/40クロックであることが分かっています。スティッチングを用いたAES-GCM実装が、暗号化処理中、AES-NIを最高速度で回しつつ、他の演算ユニットを用いてGCMのハッシュ計算を行うという手法であることも、先に述べたとおりです。
ならば、AES-NIを常時実行しつつ、その合間をぬって、AEADの事前処理、事後処理を含む他のあらゆる処理を行うようにすれば、理論上の上限値に迫るようなAES-GCM実装が作れるのではないでしょうか。
このような考えに基づき、以下のような特徴をもつAES-GCM暗号ライブラリ「fusion」を作成することにしました：
- できるだけ長い間、6*16バイト単位でAES-NIを実行する
- その間に、AAD（＝事前処理）を含む、任意の長さのGCMハッシュ計算を行う
- 複雑な設計をメンテ可能とするために、アセンブリではなくCで記述する
- AEADブロック全体にわたって、GCMハッシュの事前計算を行う。それにより、reductionの負荷を下げる
- パケットヘッダ暗号化（パケット番号暗号化）に必要なAES演算を重畳する
AES-GCM暗号化の典型的なデータフローを可視化してみましょう。第一の図が、古典的な（OpenSSLのような）暗号化部分に注力したアプローチです。第二の図が、fusionのアプローチです。横軸が時間軸で、縦に並んでいる処理は同時実行（スティッチング）されています。fusionでは、より多くの処理がスティッチングされることがわかります。
以下が、fusion.cの暗号化のホットループです。gfmul_onestepは、1ブロック分のGCMハッシュの乗算演算を行うインライン関数です。6ブロック分（bits0〜bits5）のAES計算をする間に、gdata_cntで指定された回数だけgfmul_onestepを呼び出していることがわかります。
#define AESECB6_UPDATE(i) \
do { \
__m128i k = ctx->ecb.keys[i]; \
bits0 = _mm_aesenc_si128(bits0, k); \
bits1 = _mm_aesenc_si128(bits1, k); \
bits2 = _mm_aesenc_si128(bits2, k); \
bits3 = _mm_aesenc_si128(bits3, k); \
bits4 = _mm_aesenc_si128(bits4, bits4keys[i]); \
bits5 = _mm_aesenc_si128(bits5, k); \
} while (0)
#define AESECB6_FINAL(i) \
do { \
__m128i k = ctx->ecb.keys[i]; \
bits0 = _mm_aesenclast_si128(bits0, k); \
bits1 = _mm_aesenclast_si128(bits1, k); \
bits2 = _mm_aesenclast_si128(bits2, k); \
bits3 = _mm_aesenclast_si128(bits3, k); \
bits4 = _mm_aesenclast_si128(bits4, bits4keys[i]); \
bits5 = _mm_aesenclast_si128(bits5, k); \
} while (0)
/* run AES and multiplication in parallel */
size_t i;
for (i = 2; i < gdata_cnt + 2; ++i) {
AESECB6_UPDATE(i);
gfmul_onestep(&gstate, _mm_loadu_si128(gdata++),
--ghash_precompute);
}
for (; i < ctx->ecb.rounds; ++i)
AESECB6_UPDATE(i);
AESECB6_FINAL(i);
コードを注意深く読んだ方は、bits4の計算だけ、異なる鍵を使うようになっていることに気づいたかもしれません。これが、パケットヘッダ暗号化のためのAES計算を重畳するための工夫です。
■パケットヘッダ暗号化
パケットヘッダ（パケット番号）の暗号化は、QUICやDTLS 1.3といった新世代のトランスポートプロトコルに見られる機能です。パケットヘッダを暗号化することで、傍受者による通信内容の推測をより難しくしたり、中継装置（ルータ）が特定の通信パターンを前提にしてしまうことによりトランスポートプロトコルの改良が困難になること（ossification）を防ぐ効果が期待されています。
なぜ、パケットヘッダ暗号化のAES計算を重畳するのか。それは、6ブロック分のAES計算を一度に行う以上、パケット長を96で割った余りが65から80の間にならない限り、使われないスロットが発生するためです。その余ったスロットをパケットヘッダ暗号化のAES演算に使うことで、パケットヘッダ暗号化のコストを隠蔽するのが目的です。
パケットヘッダ暗号化を重畳した場合のデータフローを、以下に示します。
■ベンチマーク
では、ベンチマーク結果を見てみましょう。
青の棒は、OpenSSLのAES-GCM処理のうち、事前処理と事後処理を含まないスループットを、赤の棒は、両者を含んだトータルでのスループットを表しています。黄色はfusionのトータルスループット、緑は、パケットヘッダ暗号化に必要な演算を重畳した場合の値です。
まずは、最近のIntel製CPUである、Core i5 9400の値を見てみましょう。
AEADブロックサイズが16KBの場合、OpenSSLの事前事後処理を含まないスループットとfusionのスループットが、いずれも6.4GB/sという理論上の上限に達していることが分かります（微妙なズレは、CPUクロック制御の精度に起因するものです）。OpenSSLの事前事後処理を含むスループットは若干遅い6.2GB/sですが、TLSにおいて、事前事後処理を最適化しないオーバーヘッドは3%以下である、という風に読むこともできます。
一方で、AEADブロックサイズが1440バイトの場合、差は顕著です。OpenSSLのトータルスループットが4.4GB/sと、理論値の約70%にまで落ち込むのに対し、fusionは理論値の90%を超えるスループットを発揮します。また、パケットヘッダ暗号化によるオーバーヘッドが1%以下なのも見てとることができます。
AMD Ryzenに目を向けると、AEADブロックサイズ1440バイトの場合のみならず16KBの場合でも、fusionが勝っていることが読み取れます。これは、RyzenのAES-NIのスループットがPCLMULと比較して高いため、ボトルネックがPCLMULに代表されるGCMハッシュ計算の側に移動したものと考えられます。fusionは、想定されるAEADブロック全体にわたって事前計算を行うことで、GCMハッシュ演算のうちreductionの回数を削減しているので、ブロックサイズ16KBの場合にも差がついたと考えることができます。
■考察
カーネル・ネットワークカードのUDP処理が最適化された場合、暗号処理のコスト差が問題となって、TLSよりもQUICのほうがCPU負荷が高くなる、という問題がありました。この問題について、QUICを始めとする暗号化トランスポート向けに最適化したAES-GCM実装を準備することで、大幅な改善が可能であることを示しました。fusionをQUICの暗号ライブラリとして使った場合の詳細は本稿では紹介しませんが、TCPとUDPでGSOハードウェアオフロードがある環境において、パケットサイズ9KBならQUICが優位、パケットサイズ1.5KBでもQUICのオーバーヘッドはTLS+5%程度だという測定結果を得ています（参照: h2o/quicly PR #359)。
あわせて、
- パケットヘッダ暗号化のコストは（少なくとも送信側においては）特に問題視するレベルではないこと
- アセンブリを用いる場合と比較して、C言語を用いることで、最善ケースのスループットを保ったまま、より高度な設計による暗号ライブラリが開発可能であること
今回開発したAES-GCM実装「fusion」は、昨日、我々が管理するTLSスタックであるpicotlsにマージされ、使用可能になっています。fusion、あるいはそれに類する実装手法を用いることで、インターネット上の通信が、より低コストに、より安全になっていくことを期待します。
末筆ですが、fusionを開発するにあたり、光成(@herumi)さんにアドバイスを、吉田(@syohex)さんにベンチマークでご協力をいただきました。この場を借りて御礼申し上げます。
No comments:
Post a Comment
Note: Only a member of this blog may post a comment.