1. はじめに

米NISTのポスト量子暗号標準化(Post-Quantum Cryptography Standardization)にむけたコンペティションは2021年のラウンド３では鍵カプセル化にはCRYSTALS-KYBER. デジタル署名としてCRYSTALS-Dilithium,　FALCON,　SPHINCS+が選択されました。また、それらをベースに標準化作業が行われています。一方、オープンソースプロジェクトのオープン量子安全(OQS: Open Quantum Safe)はそれらのアルゴリズムをライブラリーliboqsとして提供しています。

TLSプロトコルの中ではまだ扱いについてドラフト段階で標準が確定したわけではありませんが、基本的にはこれらのアルゴリズムは、プロトコルの構造を大きく変更することなしに、新たな鍵交換や署名アルゴリズムの追加として取り扱うことができます。つまり、TLSハンドシェークのClient Hello/Server HelloにおいてSupported GroupやSignature Algorithms拡張の中の曲線やアルゴリズムの種類の追加で対応することができます.wolfSSLでは下の図のようにliboqsと連携して、TLSサーバやクライアントアプリケーションを動作させることができるので、この記事ではそれらを使ってポスト量子暗号のうち特に鍵交換を試してみます。署名に関してはその２:署名を参照してください。

プロトコルの様子はWiresharkで見ることもできます。

なお、liboqsライブラリーにはQSアルゴリズム単体のものと、ECCとのハイブリッドアルゴリズムが提供されています。現段階ではこれらのポスト量子暗号のアルゴリズムが広範囲の条件で十分な堅牢さを持っていることが保証されているわけではありません。同プロジェクトでは従来型の楕円曲線暗号と組み合わせたいわゆるハイブリッド暗号を使用することを推奨しています。

2. liboqsの鍵交換

liboqsでは、鍵カプセル化と署名検証アルゴリズムの二つを提供していますが、今回は鍵カプセル化とそれのTLSでの鍵交換への適応について見ていくことにします。liboqsでは鍵カプセル化(KEM: Key encapsulation mechanisms)のために3つの主要なAPIを用意しています。

OQS_KEM_keypair

鍵カプセル化のための公開鍵、プライベート鍵のペアを生成します。
OQS_KEM_encaps

公開鍵を受け取り、相手側のための公開鍵と自分のための共有秘密値(Shared Secret)を生成します。
OQS_KEM_decaps

相手からの公開鍵と自分のプライベート鍵を使って共有秘密値を生成します。

これを、TLS1.3のハンドシェイクに当てはめると下の図のようになります。(EC)DHによる鍵交換の流れがほぼそのまま当てはまることがわかります。OQS_KEM_keypair, OQS_KEM_encapsで生成される公開鍵はClient Hello, Server Hello のKey Share拡張に格納されます。得られた共有秘密値はプリマスターシークレットとなります。

ここでは簡単のためOQS_KEMだけが使用される場合を示していますが、実際にはECC(ECDH)とのハイブリッドアルゴリズムも実現しています。ハイブリッドの場合は、ECDHの処理もこれと並行して行いCLient Hello, Server HelloのKey Shareには両方の鍵を結合して格納します。

以下にliboqsのサポートするKEMアルゴリズムをまとめます。

アルゴリズム	詳細種別	公開鍵サイズ	プライベイト鍵サイズ
Kyber	Kyber512	800	1632
	Kyber768	800	1632
	Kyber1024	1184	2400
	Kyber512-90s	1184	2400
	Kyber768-90s	1568	3168
	Kyber1024-90s	1568	3168

表: KEMアルゴリズム

3. ダウンロード、ビルド

それでは、実際にliboqsとwolfSSLを動かしてみることにします。

liboqsとwolfSSLをダウンロード、ビルドします。ここではUbuntuでの手順を説明します。

3.1 liboqs

liboqsソースコード一式をダウンロードし、cmake、makeでビルドします。

$ mkdir ~/oqs
$ cd ~/oqs
$ git clone --single-branch https://github.com/open-quantum-safe/liboqs.git
$ cd liboqs/
$ git checkout af76ca3b1f2fbc1f4f0967595f3bb07692fb3d82
$ mkdir build
$ cd build
$ cmake -DOQS_USE_OPENSSL=0 ..
$ make all
$ sudo make install

3.2 wolfSSL

wolfSSLをダウンロード、liboqsオプションを指定してビルドします。

$ git clone --depth 1 https://github.com/wolfssl/wolfssl
$ cd wolfssl
$ ./autogen.sh (Might not be necessary)
$ ./configure --with-liboqs
$ make all

これで、wolfSSLライブラリと一連のサンプルプログラムがビルドされました。

4. 実行させてみる

###4.1 ベンチマークプログラム

まずは、アルゴリズムごとの簡単なベンチマークプログラムを実行させてみます。
ベンチマークには、KEM: Kyber, 署名： DILITHIUM, FALCON, SPHINCSが含まれています。このベンチマークプログラムではこれらのアルゴリズムを約１秒間繰り返し、平均所要時間をミリ秒で、また１秒あたりの操作回数を表示します。

KYBER512    128  key gen     96600 ops took 1.001 sec, avg 0.010 ms, 96518.538 ops/sec
...
KYBER1024   256    decap     45400 ops took 1.001 sec, avg 0.022 ms, 45333.043 ops/sec
...
DILITHIUM     5     sign      5900 ops took 1.003 sec, avg 0.170 ms, 5881.262 ops/sec
DILITHIUM     5   verify     11800 ops took 1.002 sec, avg 0.085 ms, 11773.521 ops/sec
...
FALCON     5     sign      1700 ops took 1.008 sec, avg 0.593 ms, 1686.290 ops/sec
FALCON     5   verify      8800 ops took 1.007 sec, avg 0.114 ms, 8741.720 ops/sec
SPHINCS-FAST     5     sign       100 ops took 10.592 sec, avg 105.920 ms, 9.441 ops/sec
SPHINCS-FAST     5   verify       200 ops took 1.207 sec, avg 6.034 ms, 165.723 ops/sec 2.945 ms, 339.548 ops/sec
...

4.2 サンプルサーバ、クライアント

次に、サンプルサーバとクライアントでTLS通信を行わせて見ます。ローカルPCにサーバ用とクライアント用の二つのウィンドウを開いてそれぞれ次のようにサンプルサーバとクライアントを起動します。この時、Wiresharkも立ち上げておきます。鍵交換アルゴリズムとしてECC-P521とKyber Level 5のハイブリッドを指定してみます。

$ ./examples/server/server -v 4 --pqc P521_KYBER_LEVEL5

$ ./examples/client/client -v 4 --pqc P521_KYBER_LEVEL5

サーバ、クライアントはTLS接続と１往復のメッセージ通信を行います。それぞれのウィンドウには次のようなTLS1.3の接続情報とアプリケーションメッセージが表示されます。

$ ./examples/server/server -v 4 --pqc P521_KYBER_LEVEL5
Using Post-Quantum KEM: P521_KYBER_LEVEL5
Alternate cert chain used
 issuer : /C=US/ST=Montana/L=Bozeman/O=wolfSSL_2048/OU=Programming-2048/CN=www.wolfssl.com/emailAddress=info@wolfssl.com
 subject: /C=US/ST=Montana/L=Bozeman/O=wolfSSL_2048/OU=Programming-2048/CN=www.wolfssl.com/emailAddress=info@wolfssl.com
 altname = example.com
 serial number:53:16:7c:a0:56:50:46:27:82:ed:60:b4:da:33:d8:6a:c0:ea:dc:31 
SSL version is TLSv1.3
SSL cipher suite is TLS_AES_128_GCM_SHA256
SSL signature algorithm is (null)
SSL curve name is SECP521R1
Server Random : A840F6090DBD557AB550F853EAC1BC88D810598299F1BED1F0ECCB96E8C9FE68
Client message: hello wolfssl!

$ ./examples/client/client -v 4 --pqc P521_KYBER_LEVEL5
Using Post-Quantum KEM: P521_KYBER_LEVEL5
Alternate cert chain used
 issuer : /C=US/ST=Montana/L=Bozeman/O=Sawtooth/OU=Consulting/CN=www.wolfssl.com/emailAddress=info@wolfssl.com
 subject: /C=US/ST=Montana/L=Bozeman/O=wolfSSL/OU=Support/CN=www.wolfssl.com/emailAddress=info@wolfssl.com
 altname = example.com
 serial number:01 
SSL version is TLSv1.3
SSL cipher suite is TLS_AES_128_GCM_SHA256
SSL signature algorithm is (null)
SSL curve name is SECP521R1
Session timeout set to 500 seconds
Client Random : 218C741111D307A2841373F8872AE8F45F1D06EB7E7064F38D5FBFFEC6345B5E
I hear you fa shizzle!

Wiresharkには下のようなTLS1.3のパケットのやりとりがキャプチャーできます。TLS1.3なので "Cleint Hello", "Server Hello"の後のハンドシェークメッセージは暗号化されているのでキャプチャー情報としては "Application Data" と表示されます。

Server Helloの中を見てみると、"Cipher Suite: TLS_AES_128_GCM_SHA256" とあり、通常のTLS1.3の暗号スイートの一つとして合意していることがわかります。鍵交換アルゴリズムは、"Group: Unknown (12093)"　となっていて、WiresharkがまだQSアルゴリズムのIDに対応していないため、生のID値がそのまま表示されています。

    Handshake Protocol: Server Hello
        ...
        Cipher Suite: TLS_AES_128_GCM_SHA256 (0x1301)
        Compression Method: null (0)
        Extensions Length: 1715
        Extension: key_share (len=1705)
            Type: key_share (51)
            Length: 1705
            Key Share extension
               Key Share Entry: Group: p521_kyber1024, Key Exchange length: 1701
    Group: p521_kyber1024 (12093)

Supported Group拡張には現行の楕円曲線の種別、FFDHの鍵長に加えてPQのグループが生のID種別で表示されています。

Supported Groups (11 groups)
    ...
    Supported Group: kyber512 (0x023a)
    Supported Group: kyber768 (0x023c)
    Supported Group: kyber1024 (0x023d)
    Supported Group: p256_kyber512 (0x2f3a)
    Supported Group: p384_kyber768 (0x2f3c)
    Supported Group: p521_kyber1024 (0x2f3d)

サンプルサーバ(./examples/server/server)とクライアント(./examples/client/client)ではたくさんのコマンドアーギュメントが指定できるようになっています。ヘルプオプション("-?")を指定すると一番下にPQCオプションで指定できるアルゴリズムが表示されます。

$ ./examples/server/server -?
$ ./examples/client/client -?
...
--pqc <alg> Key Share with specified post-quantum algorithm only [KYBER_LEVEL1, KYBER_LEVEL3,
            KYBER_LEVEL5,  P256_KYBER_LEVEL1, P384_KYBER_LEVEL3, P521_KYBER_LEVEL5]

5. まとめ

ポスト量子暗号アルゴリズムを実際のTLSの中で試してみました。ベンチマークでわかるように、これらのアルゴリズムの処理時間は現行アルゴリズムと比べても遜色ない範囲に入りつつあることがわかります。次回は署名、検証について紹介する予定です。

TLSでポスト量子暗号を試してみる (その1: 鍵交換)