QUICむけにAES-GCM実装を最適化した話 (1/2)

4月末に、会社のほうで「Can QUIC match TCP’s computational efficiency?」というブログエントリを書きました。我々が開発中のQUIC実装であるquiclyのチューニングを通して、QUICのCPU負荷はTLS over TCP並に低減可能であろうと推論した記事です。この記事を書く際には、Stay Homeという状況の中で、手元にあった安いハードウェアを使ったのですが、その後、10gbe NICを入手し、ハードウェアによるUDP GSOオフロード環境でのパフォーマンスを確認していくと、OpenSSLのAES-GCM実装がボトルネックになることがわかってきました。

TCP上で通信するTLSでは、一般に、データを16KB単位でAEADブロックに分割して、AES-GCMを用いてAEAD暗号化します^注。一方、UDPを用いるQUICでは、パケット毎にAES-GCMを適用することになります。インターネットを通過することができるパケットサイズは高々1.5KBなので、QUICのAEADブロックサイズはTLSと比較して1/10以下となります。

両条件について、OpenSSLのAES-GCM実装のスループットを比較したところ、4GHzの第9世代Intel Core CPUを使った場合、AEADブロックサイズ16KBにおいては約6.4GB/sなのに対し、AEADブロックサイズ1440バイトにおいては、4.4GB/s程度しか出ないことが分かりました。ハードウェアGSOオフロードが可能な環境ではCPU負荷の半分弱が暗号処理コストになるので、暗号処理で7割のスループットしか出ないのは、QUICの足かせになります。

それにしても、なぜ、これほど大きな速度差が発生するのでしょう。

その答えを理解するには、最適化されたAES-GCM実装が、一般に、どのようなものかを知っておく必要があります。

■AES-NIとパイプライン処理

まず、AES-GCMのうち、暗号処理であるAES実装の最適化手法を見てみましょう。

最近のx86 CPUは、たいてい、AES-NIというAES処理専用の命令に対応しています。128bitのAES暗号化においては、AES-NI命令を10回発行することで、16バイトの暗号化を行うことが可能です。第9世代のIntel Core CPUにおいては、AES-NI命令のレイテンシは4クロックなので、10*4=40クロックで16バイトの暗号化が可能になります。

4GHzでのスループットを計算してみると、4GHz / 40clock * 16byte = 1.6GB/sになります。

あれ、先ほどの6.4GB/sと比べると1/4の値です。なぜでしょう？

実は、x86 CPUはAES-NIをパイプライン処理します。そのため、依存関係のない（＝別のAESブロックを処理する）AES-NI命令を１クロックごとに１個発行することが可能なのです。

つまり、16バイトの基本ブロック単位で処理するのではなく、AES-NI(ブロック1用)、AES-NI(ブロック2用)、AES-NI(ブロック3用)、AES-NI(ブロック4用)、AES-NI(ブロック1用)、...のように、16バイトのブロック4つ分のAES-NI命令を並行に発行し続けることで、64バイト分の暗号化を4*10=40クロックで終えていくことができるのです。

4GHzでのスループットを再び計算すると、$GHz / 40clock * 16byte * 4 = 6.4GB/s。

毎クロック1命令発行、16バイトの暗号化に10命令必要ですから、これが理論上の上限値になります。

でも、ちょっと待ってください。6.4GB/sは、暗号処理であるAESのスループットであって、認証符号であるGCMの負荷を含んでいません。GCMの負荷は一体どこに行ってしまったのでしょう。

■AES-GCMのスティッチング

GCMはガロア体における乗算を用いる認証符号で、x86 CPUでは、PCLMULQDQというキャリーレス乗算命令を利用する最適化が知られています。さらに、式を変形することで、16バイトあたりのPCLMULQDQ命令発行回数を5回に減らせることが、また、事前計算を行えば、16*nバイトあたりのPCLMULQDQ命令発行回数を3*n+2回まで減らせることが知られています（参照: https://crypto.stanford.edu/RealWorldCrypto/slides/gueron.pdf）。

PCLMULQDQ命令は、7クロックのレイテンシがありますが、AES-NIとは同時に発行可能なので、AES命令とPCLMULQDQをほどよく織り交ぜるようなプログラムを書くことで、AESとGCMを並列に計算することが可能です。

IntelのCPUにおいては、若干GCMの方がAESよりも軽いので、ボトルネックはAESになり、AES-GCMでもAES同様のスループット6.4GB/sが期待できます。

■OpenSSLのaesni_ctr32_ghash_6x関数

以上を踏まえ、OpenSSLのAES-GCM実装であるaesni_ctr32_ghash_6x関数を見てみましょう。

この関数は、perlスクリプトを用いて生成されるアセンブリコードですが、以下のような、AES-NI命令とPCLMULQDQ命令が織り混ざる構成になっています。また、AES-NI命令について、同じラウンドキーを違う引数（$inout）に適用している、つまり、複数ブロックの暗号化を同時に行なっていることが分かります。命令の目的によってインデントを変えるなどの工夫も興味深いところです。

vpclmulqdq \$0x01,$Hkey,$Ii,$T2
    lea  ($in0,%r12),$in0
      vaesenc $rndkey,$inout0,$inout0
     vpxor 16+8(%rsp),$Xi,$Xi # modulo-scheduled [vpxor $Z3,$Xi,$Xi]
    vpclmulqdq \$0x11,$Hkey,$Ii,$Hkey
     vmovdqu 0x40+8(%rsp),$Ii # I[3]
      vaesenc $rndkey,$inout1,$inout1
    movbe 0x58($in0),%r13
      vaesenc $rndkey,$inout2,$inout2
    movbe 0x50($in0),%r12
      vaesenc $rndkey,$inout3,$inout3
    mov  %r13,0x20+8(%rsp)
      vaesenc $rndkey,$inout4,$inout4
    mov  %r12,0x28+8(%rsp)
    vmovdqu 0x30-0x20($Xip),$Z1 # borrow $Z1 for $Hkey^3
      vaesenc $rndkey,$inout5,$inout5

注意深い方は既にお気づきかもしれませんが、関数名の6xは、128bitのブロックを6ブロック単位で（つまり、96バイト単位で）AES-GCM符号化を行なっていることに由来します。

■なぜOpenSSLは短いAEADブロックの処理が苦手なのか

このように、丁寧に最適化されたコードであるにもかかわらず、なぜ、OpenSSLは短いAEADブロックの処理が苦手なのでしょうか。２つの要因が考えられます。

第一の要因は、関数呼び出しのオーバーヘッドです。OpenSSLのAEAD処理は、EVPと呼ばれるレイヤで抽象化されています。ひとつのAEADブロックを暗号化するには、EVP_EncryptInit_ex、EVP_EncryptUpdate、ENP_EncryptFinal、という３つの関数を介して、AES-GCM固有の処理を呼び出す必要があります。

第二の要因は、AES-GCMの事前処理と事後処理がパイプライン化されていない点です。先に紹介したaesni_ctr32_ghash_6x関数は、6.4GB/sという理論値を叩き出す、文句のつけどころのない関数です。しかし、AES-GCMにおいては、暗号化以外にも、AEADブロック毎に、AAD（認証つき平文）をGCMのコンテクストに入力したり、最終的なタグを計算するなどの処理が必要です。これらの付随する処理の負荷は、AEADブロックサイズが小さくのればなるほど、相対的に大きくなります。

これらの問題を指摘することは簡単です。

なるほど、AEAD処理をひとつの関数にまとめ、事前処理と事後処理を、パイプライン化されスティッチングされた暗号処理と並行に走らせることができれば、AEADブロックが短くても、理論値に近いスループットを発揮するような、AES-GCM実装を作ることができるでしょう。

しかし、上述したように、パイプライン化・スティッチングされたコードは、既に相当複雑です。ここにさらに、事前処理や事後処理を重畳することなどできるでしょうか。できたとして、保守可能なプログラムになるでしょうか。


次回に続きます。



注: スロースタート時には、より小さなブロックサイズを使って実効レイテンシを改善する場合もあります（参照: https://www.slideshare.net/kazuho/programming-tcp-for-responsiveness）