第３話： Open Quantum Safe (OQS) project と「ハイブリッド」証明書について

サイバートラスト研究開発ブログシリーズ耐量子計算機暗号 (PQC) の現状～ Open Quantum Safe project の PQC 実装はどこまで動くのか？～

Open Quantum Safe project / OpenSSL や Demo

OQS-OpenSSL

OQS project では Github 上に、PQC ライブラリ liboqs を組み込んだ OQS-OpenSSL（open-quantum-safe/openssl）も公開しています ^[1]。
この OpenSSL についても、Web 上の "Quickstart" の説明に従ってソースを get、build して、PQC 対応 openssl コマンドの実行を簡単に試せます。

 ・・・
$ git clone --branch OQS-OpenSSL_1_1_1-stable https://github.com/open-quantum-safe/openssl.git /home/ubuntu/openssl
$ git clone --branch main https://github.com/open-quantum-safe/liboqs.git
$ cd liboqs
$ mkdir build && cd build	
　・・・

$ ./openssl
OpenSSL>

OpenSSL の list コマンドでオプションとして -public-key-algorithms を指定して、公開鍵アルゴリズムのリストを表示すると、既存の RSA 暗号などに加え、例えば格子暗号の Dilithium2 や Dilithium3、また、" 耐量子暗号 + 楕円暗号 " の p256_dilithium2 や " 耐量子暗号＋RSA 暗号 " の rsa3072_dilithium2 などの既存暗号と PQC の組み合わせとなる、いわゆる「ハイブリッド」アルゴリズムもあるのが分かります。

OpenSSL> list -public-key-algorithms
Name: OpenSSL RSA method
        Type: Builtin Algorithm
        OID: rsaEncryption
        PEM string: RSA

　・・・（略）・・・

Name: OpenSSL Dilithium2 algorithm
        Type: Builtin Algorithm
        OID: dilithium2
        PEM string: dilithium2
Name: OpenSSL ECDSA p256 Dilithium2 algorithm
        Type: Builtin Algorithm
        OID: p256_dilithium2
        PEM string: p256_dilithium2
Name: OpenSSL RSA3072 Dilithium2 algorithm
        Type: Builtin Algorithm
        OID: rsa3072_dilithium2
        PEM string: rsa3072_dilithium2
Name: OpenSSL Dilithium3 algorithm
        Type: Builtin Algorithm
        OID: dilithium3
        PEM string: dilithium3
　・・・（略）・・・

ハイブリッド（hybrid）

ここで、ハイブリッドについて触れたいと思います。
NIST によって PQC が標準化されたとして、その後、実際の製品に組み込まれ、サービスにも適用され、PQC が世の中に普及するには、相当程度長い期間を要すると想像されています。前も記載しましたが、NIST も PQC 標準化の背景として『我々の最新の公開鍵暗号化インフラストラクチャを展開するのにほぼ 20 年という時間がかかりました』と記載しています。同じ RSA という暗号手法で、鍵長を 1024 bit から 2048 bit に変えるだけでも、「暗号の 2010 年問題」^[2] と呼ばれ、すったもんだがありました。

この PQC 普及までの間、既存の暗号技術（RSA 暗号や楕円暗号）を使い続けた場合に、量子コンピュータなどの技術の発展・飛躍によって既存暗号が弱体化するリスクも完全には否定できません。一方、PQC はまだ利用の実績が浅いことから、実際に本格利用され始めた後に、例えば前述の Rainbow 暗号のように、思わぬところで攻撃手法や脆弱性が見つかり、利用不可能にまでなる可能性も否定できません。PQC への移行を慎重にしてもリスクがあり、進めてもリスクがあります。

そこで、既存の暗号技術（RSA など）と PQC とを組み合わせて（ハイブリッド）、少なくとも既存暗号と PQC のいずれかが安全であればセキュリティが担保されると期待できる、というのが " ハイブリッド " の考え方です。

例えば、Web サーバの管理者は、RSA 暗号の鍵と PQC の鍵を持ち、これに対応する証明書を Web サーバにセットするイメージです。しかし、その具現化方法としては、異なる複数通りの方法が Internet-Draft として提案されています。当初は全般的に「ハイブリッド」と呼ばれていましたが、「コンポジット」証明書、「ハイブリッド」証明書、「マルチ」証明書といったように、呼び分けられ始めているようです。

コンポジット証明書（composite certificate）

方法は大きく、コンポジット (composite) か、非コンポジット（non-composite）かの２つに大別されます。ハイブリッドは後者に含まれます。
前者、コンポジットの特徴は、加入者（利用者）が持つ、例えば２つ（RSA と PQC）の公開鍵をひとまとめに組合せて（コンポジットして）証明書に入れるところにあります。証明書の中の構造は、大きくは右図のようになっていますが、この中の「加入者の公開鍵情報」にそれら加入者の公開鍵がまとまって入ります。

また、認証局側も例えば２つ（RSA と PQC）の鍵ペアを持っている場合、証明書にそれぞれの署名（認証局の電子署名）もまとめて入ることになります。
Internet-Draft が、IETF: draft-ounsworth-pq-composite-sigs "Composite Signatures For Use In Internet PKI" にまとめられています ^[3]（関連して以下も提案されています）。

IETF: draft-ounsworth-pq-composite-keys
"Composite Public and Private Keys For Use In Internet PKI" ^[4]
IETF: draft-ounsworth-pq-explicit-composite-keys
"Explicit Pairwise Composite Keys For Use In Internet PKI" ^[5]
IETF: draft-ounsworth-pq-composite-encryption
"Composite Encryption For Use In Internet PKI" ^[6]

なお、OQS project のプロトタイピングも、Web 上には "hybrid" という単語が散見されますが、実際はこのコンポジットの形です。署名アルゴリズムに rsa3072_picnicl1full（RSA 暗号 3072 bit と PQC として Picnic L1 full）を指定して、OQS-OpenSSL で認証局証明書やサーバ証明書を作成すると、例えば「加入者の公開鍵情報」は以下のように複数の公開鍵情報がまとまって入ります。

   ・・・
        Subject Public Key Info:
            Public Key Algorithm: rsa3072_picnicl1full
                RSA Public-Key: (3072 bit)
                Modulus:
                    00:c8:25:db:df:cf:cf:48:3c:81:a0:e2:c9:f3:44:
   　　　　　　　　　　・・・
                Exponent: 65537 (0x10001)
                picnicl1full Public-Key:
                pub:
                    0a:86:90:a8:15:4d:4b:8b:cd:e2:59:b9:55:36:22:
   　　　　　　　　　　・・・

この場合、既存のブラウザ（PQC およびコンポジット未対応）は、rsa3072_picnicl1full などの署名アルゴリズムを知らないので、当然のことながら接続できません。OQS project では、これら各種アルゴリズムを試せる interop テスト用の web サイトを公開していますが ^[7]、既存のブラウザで接続すると、「サポートされていないプロトコルが使用されている」などのエラーが表示されます。

出典：OQS project が公開している interop テスト用 Web サイト^[7]

既存のブラウザで接続した場合

なお、OQS project では、OQS ライブラリの各言語向けの wrapper として、liboqs-python（python 向け）や liboqs-go（Go 向け）を始め、C++、java、.NET 向けなどを公開しており ^[8]、利用のしやすさなどからこれが普及した時に、実質的にコンポジットの形態が主流を占めるようになるのかもしれません。

ハイブリッド証明書（hybrid certificate）

　ハイブリッドは、PQC 用の公開鍵情報などを証明書の中に含めるのはコンポ
ジットと同じですが、その情報を含める（登録する）証明書中の場所が異なります。
右図のように、PQC 関連の情報を登録する新たな拡張領域 (extension) を用意し、そこに加入者が別途保有する PQC 公開鍵情報 (subjectAltPublicKeyInfo) や、認証局の PQC 鍵による別の電子署名 (altSignatureValue）など、追加情報として登録する形になります。ここで、新たな拡張領域には、『重要ではない』（non-critical）というフラグが認証局によりセットされ、この新しい拡張領域を解釈できないブラウザなど（PQC 未対応アプリ）は、その拡張領域を無視してよいこととなり、あたかも従来と同じ証明書（無視してよい解釈不能の拡張領域が一部含まれているが）として処理が可能となります。つまり、ハイブリッド証明書を使った Web サーバには、PQC 未対応のブラウザなどでもエラーなく接続が可能になる、というものです。

同仕様については Cryptography ePrint^[9] や Internet-Draft（IETF: draft-truskovsky-lamps-pq-hybrid-x509 "Multiple Public-Key Algorithm X.509 Certificates"）^[10] に記載がありますが、後者については 2019 年 3 月に期限切れとなり以後更新されておらず、また、知的財産に関わるライセンスの宣言がなされているようで、今後これが、ブラウザやサーバ、ネットワーク機器などの各種製品・アプリケーションで広く対応できるのか先が見え難い所があります。

なお、同様の考え方によるハイブリッド証明書のプロトタイピングとしては、前述の OQS Project の OpenSSL からブランチして変更を加えた CROSSINGTUD/openssl-hybrid-certificates ^[11] があります。PQC 関連の情報を拡張領域に含めるところは同じですが、インプリメントの仕様は、前述の Internet-Draft とは若干異なっています。

下表の左列は前述の Internet-Draft の仕様で、PQC による署名アルゴリズムと署名自体とを個々の extension (AltSignatureAlgorithmExt と AltSignatureValueExt) として定めていますが、CROSSINGTUD/openssl-hybrid-certificates では、試しに TLS 証明書を作ってみると（右列）、PQC による署名は、利用アルゴリズムと署名自体を一つの extension（X509v3 Hybrid Signature(2.5.29.212)）として証明書中に含めています。

IETF: draft-truskovsky-lamps-pq-hybrid-x509

id-subjectAltPublicKeyInfo OBJECT IDENTIFIER ::= { TBD }
id-altSignatureAlgorithm OBJECT IDENTIFIER ::= { TBD }
id-altSignatureValue OBJECT IDENTIFIER ::= { TBD }

AltSignatureAlgorithmExt  ::=  AlgorithmIdentifier


AltSignatureValueExt  ::=  BIT STRING




SubjectAltPublicKeyInfoExt  ::=  SEQUENCE  {

     algorithm                  AlgorithmIdentifier,

     subjectAltPublicKey        BIT STRING 
}

CROSSINGTUD/openssl-hybrid-certificates

・・・
X509v3 extensions:
 X509v3 Basic Constraints(2.5.29.19 ):
・・・
X509v3 Hybrid Signature(2.5.29.212):
  Signature Algorithm: picnicL1FS
( 1.3.6.1.4.1.311.89.2.1.1)
    Signature dump:
 80:6a:05:　・・
　　　・・（略）・・
・・:3d:10

X509v3 Hybrid Key( 2.5.29.211):
Subject Public Key Info:
Public Key Algorithm: picnicL1FS
( 1.3.6.1.4.1.311.89.2.1.1)
    picnicL1FS Public-Key:
    pub:
01:69:ff: ・・
　　　・・（略）・・
・・:ff:79

また、Internet-Draft 側では、各 extention の OID(OBJECT IDENTIFIER) は未定義（TBD）となっていますが、別途、例えば 2.5.29.72（id-ce-subjectAltPublicKeyInfo OBJECT IDENTIFIER ::= { id-ce 72 }）などが定義されているようです。一方、CROSSINGTUD/openssl-hybrid-certificates 側では、2.5.29.212（id-ce-hybridSig OBJECT IDENTIFIER ::= { id-ce 212 }）といった値が使われています。

なお、右列の例では PQC としては、仮に picnicL1FS（Picnic-L1-FS）署名アルゴリズムを使用しています。同署名アルゴリズムの OID は、OQS の OID 一覧 ^[12] にもある通り 1.3.6.1.4.1.311.89.2.1.1 ですが、これはアルゴリズム開発者が Microsoft（マイクロソフトリサーチ）であることから、{iso(1) org(3) dod(6) internet(1) private(4) enterprise(1) microsoft(311)} の配下に Picnic の OID が定義されているようです。

補足ですが、上記 CROSSINGTUD/openssl-hybrid-certificates の方式によるハイブリッドについては、java 向け（ "CROSSINGTUD/bc-hybrid-certificates" ^[13]) も公開されていますが、ここ１年半ほどは更新はないようです。

マルチ証明書（multi certificate）

マルチ証明書は、言葉の通り、複数の証明書を用いる方法です。例えば web サーバは、２つの鍵ペア（RSA などと PQC）とそれぞれに対応する２つの証明書を保持し、TLS などの接続の中で、例えばまずは RSA の証明書を使って認証を行い、続けて、PQC の証明書を使って同様に認証を行う、つまり２回、認証を行う（hybrid authentication）というものです。特に２つの鍵が１つにまとめられるなどはなく、個々に使われますので、非コンポジット側に分類されます。

TLS 接続では、接続しようとしている Web サーバが、正しくその Web サーバであるかを、証明書中の Common Name や SAN(Subject Alt Name) 中に記載されている FQDN（いわゆるサーバ名＋ドメイン名）で確認しますが、上記マルチ証明書として送られてきた２つの証明書のそれぞれで、つまり、既存暗号と PQC の両方で、この Common Name や SAN を確認して web サーバを認証することが１つのポイントとなります。

２つの証明書を１組のものとして使うことをより明確にするために（既存暗号側の証明書と PQC 側の証明書をより強く結びつけるために）、既存暗号側証明書情報を BoundCertificates という extension に記載して、PQC 側証明書の拡張領域に含める案が Internet-Draft（IETF: draft-becker-guthrie-cert-binding-for-multi-auth）^[14] で提案されており、これらを含めて、上記 hybrid authentication の案が Internet-Draft（IETF: draft-becker-guthrie-noncomposite-hybrid-auth）^[15] に記載されています。

TLS 接続中に、２つの証明書を使いたいと相手方に伝えるために Internet-Draft（IETF: draft-ietf-tls-tlsflags）で提案されている "tls_flags" という TLS 接続メッセージ中の extension を利用することを提案しており、これを解釈できない従来のブラウザやサーバなどは、単にこれを無視して、既存暗号（RSA など）側の証明書だけが使われるので、PQC 浸透途中、PQC 未対応のブラウザやサーバなどが混在している環境でも、特にエラーなく接続が可能になる案であると思われます。

ハイブリッド（hybrid）に関しては以上です。

次回 : OQS-demos：PQC 対応版 Chromium や Wireshark

次回は、「OQS-Demos」などについて解説します。

この記事の著者

サイバートラスト R&D センター

「R&D センター」は、2022 年 4 月 1 日に立ち上げられた研究開発部門です。
サイバートラストは、お客様のサービスの信頼性を支えるプラットフォーマーとして、先々のプラットフォームや社会制度、他がどのように変化するのかを考えています。
さまざまな IoT 機器が普及し、OSS や AI やブロックチェーンが活用され、量子コンピュータが発達する一方で、それらによる新たなセキュリティリスクも生じると想像される未来においても、引き続き、安心・安全な社会を実現するため、サイバートラストが果たす役割を含め、研究開発を進めていきます。