暗号計算機屋のブログ

なにか思いついたことを不定期に更新。

ICF3-Fの技術と今後について

2018年9月5日 補足1、補足2を追加

2018年9月4日 修正: ICF3-Fは鍵長が2倍になると処理時間が2倍強と書きましたが4倍強の間違いでした。すいません。それでも内容に大きな影響はないと思います。

背景

結論を先に言うとICF3をFPGASSLアクセラレータにしたICF3-Fは鍵長の長いRSA暗号が得意なのだが常時httpsのサーバー負荷増大は楕円暗号(ECDSA証明書)に移行しても対策できる。 ICF3-Fは、それほど売れないということ。しかし、その技術は楕円暗号が先に危殆化した場合など必要。ですので今後とも、よろしくお願いします。

事の発端。数か月前にFPGAを使い始めた。LSIの設計経験がありながら今頃になったのは暗号LSIでは秘密鍵が漏洩しないことが重要であるためFPGAでは困難だと考えていたから。 使い始めてみるとFPGAにはDSP(乗算器モジュール)が多数あることを知った。SSLの性能はDSPの占める割合が支配的であり、DSPはASICに近い性能がでるはずなので、FPGA全体として ASICを凌ぐコスパが実現されそうだという予感がした。 乗算器の数と性能では、はるかにGPUが上だが、1つのSSLを計算するにもGPU全体を動作させなければならないなど、GPUではあまりうまくないと思われた。

設計開始

SSLで使われるRSA暗号や楕円暗号などの公開鍵暗号はハードウェアが苦手な除算を乗算のような演算に変換するモンゴメリ乗算を利用する場合が多い。 モンゴメリ乗算のアルゴリズムは基数をパラメータとして持っているためFPGAの乗算器のサイズに最適な基数を選択できる。 ただし1024ビット以上のビット幅の大きい加算のキャリーが性能の足かせになる。 ASICではキャリーセーブアダーによる方法で回避するのだがDSPの乗算器は全加算をしてしまうため、気づけなかった人が多かったのかもしれない。 1024bitをDSPに合わせてブロックに分割する。 ブロック毎に全加算をする方法ではブロックの合計を保存するレジスタが加算を繰り返すうちに溢れてしまう問題を解決することが必要だった。 ブロックに、どういう冗長性を持たせれば加算を繰り返しても正しい答えになるのか考える必要があった。 (発明なのかな? そのときのブログ)

シミュレーションで正しい結果に

f:id:icf:20180903134157p:plain 2018年8月初旬、4サイクルピッチで正しい結果が出た直後、失明しかかる事故が発生し大騒ぎになった。 以前、左耳がほぼ完全に聴こえなくなった。このとき医者に3分の一くらい治らないこともあると言われたが、 6~7割程度回復した。日常の会話では、ほとんど問題ないが音楽鑑賞には全く耐えない。 失明の話に戻るが、治らないこともあるかと、数日、慌てふためいた。その後、ほとんど回復したが、 元々、既に動体視力が劣化していた。並みのエンジニア以下の思考力に低下したが3サイクルピッチに改善することに成功した。

XilinxFPGAに実装開始

設計の段階でディレイを最大限考慮しているが、シミュレーションではディレイは反映されないため、実際にインプリメントして、どの程度の周波数で動作するのか、XilinxのVivadoを使って確かめてみた。Vivadoは初めてなので保証できる値ではないのですが125MHzで動作することがわかった。これは演算器の性能なので、そこからRSA 2048bitの性能を計算するとDSP 90個で3.2ms程度になった。評価ボード ArtyのXC7A35T-L1CSG324Iにインプリメントしています。これはCPUに比べてかなり低消費電力なのでは?とも思った。 f:id:icf:20180903134217p:plain

鍵長が大きくなっても演算器の周波数が下がらない特長の発見

4サイクルピッチから3サイクルピッチに性能改善するときに1サイクル遅れたブロックと接続する技術を開発した。 この技術を使えば鍵長が大きくなっても周波数が下がらないことに気づいた。 モンゴメリ乗算のアルゴリズムは劇的に改造しないかぎり最下位ビットから演算器全体にブロッドキャストすることになり、 低基数ではハードウェア実装において鍵長の増加に伴い周波数を低下させる原因となっていた。 CPUでは鍵長が2倍になると、おおよそ7倍~9倍性能が低下する。 RSA 2048bitでは0.62msでも、RSA 16384bitでは400msになるため とてもSSLの実装として許容できる性能ではない。 この技術を使った場合の予想では、鍵長を2倍しても、演算器の幅を2倍にすることで性能低下は4倍強にとどまる。 仮に4.2倍とするとRSA 2048bitで3.2msだったのがRSA 16384bitでは237msとなるためぎりぎり現実的な性能といえる。

補足1

RSA 16384bitの性能なら俺のほうが勝っている」と言う人もあるかもしれません。 5nmプロセスとか、Virtex UltraScale+みたいなハイエンドデバイスとか、デバイスの前提条件が考慮されているか確認してください。 こちらの前提はArtix-7で、比較的ローエンドなデバイスです。もちろん必要ならハイエンドデバイスも考えます。

補足2

理論的にはRSAの鍵長が2倍になると演算量は8倍です。ICF3-Fは鍵長が2倍になると演算器を2倍にできるアーキテクチャなので処理時間が4倍ですがCPUでは並列性を抽出できず8倍になると思います。もしできても無駄が多く消費電力が厳しくなる。鍵長がさらに大きくなればCPUとの差はもっとでると。

暗号プロセッサの開発開始

暗号プロセッサの周波数と演算器の周波数は普通2倍以上違うが、3倍になるのか、4倍になるのか。BRAMのタイミングと合わせて検討を始めた。 実際には、暗号プロセッサの開発と並行して、ICF3-Fが売れるのかも調べた。

ICF3-Fは、どれくらい売れるのか?

現時点でのSSL証明書RSAが大半で、まずはRSAのことだけを考えていた。 ICF3-Fは楕円にも対応可能であるため楕円に移行しても問題がないと考えていたからだ。 今後、普及していくと思われるTLS 1.3は当然、楕円に対応している。 RSAはサーバー側が非常に重く、クライアント側が軽いが、楕円はクライアント側よりもサーバー側のほうが軽く、サーバー側に負荷がかからないということを、さっき知った。 つまり楕円暗号に抵抗のないサーバー管理者はSSLアクセラレータを買うより、可能な限り楕円に切り替える。無料のSSL証明書 Let's Encryptも楕円に対応したものが発行できる。 「ICF3-Fは、買えば得をする商品になる」といったが、あまり正しくなかった。 ただSSL証明書の購入が、お客である場合も多いので、お客が楕円暗号に抵抗があったり、RSA証明書のほうが安価ということでRSAを選択する場合もある。 クライアント側が重い楕円はモバイルではバッテリーの消耗が大きい。そういうことを重視する場合は、やはりRSAの証明書を選択することもあるだろう。 ちなみに楕円P-256だけ、かなり最適化が進んでいる感じで楕円P-384の性能はかなり下がるということがあるようだ。なんと楕円P-521よりも性能が悪いのだ。 P-256よりも安全な証明書を選択したい場合、P-384かRSA 4096になるが、opensslの性能評価でクライアント側の処理は、RSA 4096のほうが約8倍くらい軽い。 RSA 4096を選択したくなるケースはあるかもと思った。

まとめ

背景の最初に書いた通りだが、楕円暗号の離散対数問題を効率的に解く方法が発見されたり、 量子コンピュータの進歩によって量子ゲート数が増えて鍵長の短い楕円暗号のほうが先に解読されるということになれば、 とても長い鍵長の専用演算器をハードウェア実装可能なICF3-Fの技術は、今とても役に立つということではないが、なくてははならないものではないかと思っています。 従来の専用演算器はモンゴメリアルゴリズム的に鍵長を長くすると低基数では性能劣化が大きくなる問題があった。高基数ではCPUと同じ状況になるだろう。 詳しく理解していないが改良型である冗長モンゴメリは、もしかすると鍵長が長くなっても性能劣化が小さいかもしれない。 しかし理論は美しいが、最初から重い実装なので、感覚的だがICF3-Fのほうがいいと思われる。 量子コンピュータについても勉強不足だが、現在、ざっと調べてもショアのアルゴリズム以外は検索で見つからない。 最悪のケースでは鍵長を長くしてもRSAや楕円暗号を延命することはできないということは考えていなければならない。 しかし量子コンピュータは量子ゲート型だけではなくて量子イジングモデル方式も多く開発が進んでいる。 解読されても鍵長を長くすることで延命できるケースも考えられるかもしれない。 鍵長が長くなるとCPUのコアを増やす方法ではSSLに必要な絶対性能を満たすことができず、ICF3-Fの専用演算器が必要となります。 IEEEなどの論文を調べても、学術的な価値も1999年に世界一のRSA性能だったICF3を含めて、とてもあるように思っています。 ICF3-FはFPGAを使って開発をするので、かつてASIC LSIの開発経験がある僕にとっては、ほとんどお金がかからず開発が進み、 Cmod A7などの評価ボートを、そのまま使って製品とするようなことをすれば、 ある程度、Xilinx様の協力があれば製品化は実現可能だと思います。