😸

【論文紹介】statefulハッシュ、使うべきか、使わざるべきか

に公開
Security
Security
耐量子計算機暗号
pqc
tech

今回の論文

要約

  • OpenTitanのSHA2コアを使ってXMSSやSPHINCS+などのハッシュベース署名を実装。どちらがどういう場合に良いかを議論している
  • 特にディジタル署名の重要なアプリケーションである、セキュアブートに焦点を当てている。
  • LMS/SHPHINCS+-sを推奨。特にw=256パラメータ。（SHINCS+-sは標準落ちした）

所感

  • 知らないことが結構書いてあったので勉強になった。
  • 特にセキュアブートの文脈ではstatelessハッシュはあまり必要とされて無さそうであり、すでにいくつかのデバイスではLMS/XMSSがサポートされているためそれを使うんだろうなあという印象。
  • FIPS-205は使うとしたらデバイス側で署名生成を行う場合だろうと考えられる。

1. Introduction

  • statefulハッシュベース署名（HBS）であるLMSとXMSSが2019年にRFC標準化された。NISTも2020年にSP800-208を発行。
  • HBSの強みは、安全性がハッシュ関数の安全性のみに依存すること。ハッシュ関数はよく理解されているとみなされており、格子ベースよりもある意味保守的な手法と言える
  • よってANSSIやBSIのPQC移行文書[5,14]では、HBSに関してはハイブリッドモードの利用がoptinalとされている。
ANSSI文書補足

ANSSI文書では、３フェーズでPQC移行を進める。
2023年版捕捉文書

  • Phase 1: mandatory pre-quantum security, optional PQC, no claimed quantum resistance.
    PQCはオプションだが、2030年以降も使われるデバイスに対しては入れておくことを推奨
    ハッシュベース以外ハイブリッドモードは必須？
  • Phase 2. （少なくとも2025年以降）Mandatory pre-quantum security, optional PQC with claimed quantum resistance
    all post-quantum PKC algorithms shall continue to be systematically included inside hybrid mechanisms (except for hash-based signatures whose hybridation is optional as presented in phase 1)
  • Phase 3: （2030年以降）Optional standalone PQC with claimed quantum resistance.
    成熟したPQCならハイブリッドなしでもよい。
  • HBSはstatefulとstatelessの２種類があり、LMS/XMSSはstatefull HBS。
  • statefulハッシュの問題は、署名回数に上限がある（鍵生成の時点で決定する）ことと、stateの管理が必要なこと。ANSSI文書ではソフトウェアアップデートのようなstateが厳格に管理され、最大署名回数に上限があるようなアプリケーションでは利用に適するとされている。
  • 一方でstateless HBS SPHINCS+も標準化された。特徴は、statelessであること。つまり署名回数に（実質上の）制限がなく、stateの管理が不要というメリットがある。よりメタには従来のECDSAやRSAと同じ使い方ができるという点が強い。
  • しかしながら署名長や検証時間はstateful署名の方が良い。
  • Open TitanのSHA-2モジュールを、stateful/stateless HBSを高速化できるように改変して実装。評価する。

Hash-based signature schemes

  • HBSに必要なプリミティブが解説されてるがここでは解説しない

Secure boot with hash-based signatures

  • セキュアブートに焦点を当ててHBSの効率（特にstateful方式の状態管理）を議論している。
  • NSAによるCommercial National Security Algorithm Suite 2.0 日本語文書では、ファームウェア署名においては2025年までにXMSS/LMSへの移行を開始し、2030年までに完了することを求めている。
  • XMSS/LMSの推奨利用方法はSP800-208を参照しており、特に状態管理について次節で解説している。

Distributed state management compliant with NIST SP 800-208

  • stateful HBSを利用する際は、ハードウェア故障なども考慮したstate（つまり何番目の秘密鍵まで利用したか。単にカウンタ管理ともいえる）管理が必要である。
  • 単純なアプローチはデータを別リージョンにコピーしておき、地理的な単一故障点をなくすことであるが、NISTは秘密鍵のexportを禁止している。
  • NISTの推奨方法の一つは複数の鍵ペアを用意しておくこと。署名側は複数のデバイスでそれぞれの固有の秘密鍵を持ち、検証側にその全ての公開鍵を入れておく。通常は一つのデバイスの秘密鍵だけが使われるが、そのデバイスが故障した際には次のデバイスの鍵で署名し、検証側は全ての秘密鍵をアクセプトするようにしておけば良い
  • 第２の方法はハイパーツリーのサブツリーを複数デバイスに分散すること。例えばデバイスAでルートツリーとサブツリー1を生成、デバイスBでサブツリー2を生成する。これだけだとサブツリー2の認証パスにデバイスAのルートツリーが必要なのでデバイスAが単一故障点になる。これを防ぐため、全てのサブツリーのルートをルートツリーで署名しておく。（署名には認証パスが含まれる）

Distribution of sub-trees

論文ではさらに第２の案の効率化が提案されているが、以後でてこないので省略

To be, or not to be stateful

  • State管理のベストプラクティスとして[50]を引用
  • ３つの方法が提案されており、HSMに管理させるか、stateful/statelessのハイブリッドを使うか

Hardware/software co-design

  • ソフト実装のHBSのオーバーヘッドの８割程度はハッシュチェイン計算。ハードウェア化ででここを早くしたい。
  • OpenTitanのSHA-256モジュールは圧縮関数を65サイクルで実行可能。しかしデータ転送に1400サイクルかかる。ハッシュ長が長い時は問題にならないが、ハッシュチェイン内では圧縮関数が1回か２回しか使われないので、データ転送を減らすことが大きな課題
  • ハッシュチェインは要は圧縮関数の出力を入力に戻すパスを作ってやればいいということなので、そのようなデータパスを回路に挿入
  • その他LMS/XMSS/SPHINCS+を切り替える制御パスなどを追加し最適化した。
  • SHIPNCS+は、simple/robust variantを実装した。simple variantはLMSに近い構成で回路が簡略。robustはハッシュ入力にビットマスクを追加した形で、パスが複雑になる。XMSSと共通化もできない？ちなみにFIPS-205ではrobustのみが標準化された。

評価

実装したパラメータサイズ

  • 256ビットセキュリティを実装。HBSなので公開鍵サイズは小さい。
  • hはツリーの高さであり、stateful HBSの場合2^h回署名が可能。つまりh=16のとき65536回署名できる。これはデバイスが最大40年間利用されると想定し、1日に２回アップデートされたとしても足りるだけの量として設定。
  • wは秘密鍵を何ビットずつハッシュするか（w=256だと8ビットずつ）。wが大きいほど署名長が小さくなり、署名・検証時間が長くなる。wが大きいと攻撃に弱くなるみたいなことが書いてあるがほんとか？

wによる署名長・検証時間（HW実装時）への影響

  • wを大きくすると署名長が短くなる。しかしHW実装のおかげでサイクル数はそんなに増えない。これを見るとw=64くらいまでは伸ばして良さそうな感じがある。

合成結果

  • いろいろと機能を追加していったときの伸びを評価しているが、全部入りでもSHA2モジュールの元々の大きさの２倍に満たないオーバーヘッドで実装できている。OpenTitanコア全体の回路規模で見れば対して差ではないだろう。
  • OpenTitanは100MHzがターゲットであり、これらの回路は全てArtix-7で100MHzでタイミングメット。

Stateful HBSの署名検証速度

  • 提案する回路はソフト実装に対してLMSは80倍、XMSSは20倍早い。
  • wが大きいほどハッシュチェインが増えるのでHW化の効果が高い。
  • OpenTitanの元々のSHA2コアを使った場合と比較しても数倍以上速い。
  • XMSSとLMS（w=16）を比較すると、LMSのほうが4倍速い。XMSSは20ms程度。LMSは5ms程度

Rapidly verifiable signatures評価

  • [13,59]で、署名検証時間を削減する手法が提案されている。
  • 簡単にいうと署名生成時のメッセージにに乱数をつけて、検証が短くなるもの（ハッシュチェインの長い署名？）を探す。
  • 10^9まで探索した結果が以下。ソフト実装や元々のSHA-256コアの場合署名検証時間が３割程度改善されるが、提案手法のSHA-2+コアは１割程度しか改善しない。
  • 10^5程度の探索で効果はほぼ頭打ち
  • 署名生成時間が10^5倍になるのに対して効果が小さすぎる気はする？

SHIPNCS+の署名検証速度

  • SHA-2+コアはハッシュチエインだけ高速化？SHA-2++コアはマークルルート計算も高速化するようなコア
  • ソフトに対して14倍以上の高速化。元のSHA-256コアに対しても10倍弱早い。
  • 回路規模の増加が高々2倍弱なので、効果は大きいと言える。

先行研究との比較

  • いくつかのexcuseがついている。
    • SHA-2の元々の回路規模は含まず、増加分のみを評価？
    • 完全なFPGA実装はターゲット外なので比較から外す？
  • そんなもんだろうという結果

Secure boot

  • ここが割とこの論文の核みたいなところがある。
  • TockOSのカーネルサイズから、ファームウェアイメージのサイズを128KiBと想定。
  • 評価には、ファームウェアのハッシュ時間を含める（ファームウェアイメージが大きい場合は署名検証の時間は無視できるかもしれない）。
  • RSAとECCはオープンのRust実装を利用。OpenTitanのBigNumberコア（OTBN）による高速化も評価する。
  • 表の単位はメガサイクル。
  • ソフト実装の場合、stateless HBSはRSA/ECCよりやや速い。SPHINCS+-simpleはやや速いが、robustは3倍以上遅い。今100Mサイクルで1秒だとすると、検証時間が0.5秒だったのが1.7秒になるくらいのイメージ。
  • cc_{verif}/cc_{sw-hash}と書いてあるのはおそらく、署名検証時間におけるファームウェアダイジェストと署名検証時間の比のこと？つまり100%の時にダイジェストと署名検証時間が1:1になる？？？（自信なし）。
  • ハード実装の場合LMSはRSA/ECCよりも速いのでかなり有望。XMSSも使える範囲？1Mサイクルだと1msで起動できるイメージなので、この辺なら使えそうである。LMSは署名検証時間が37%なのでファームウェアハッシュの方がネック。
  • SPHINCS+は古典より10倍以上遅いため、要求が高いところでは使え無さそう。署名検証がファームウェアダイジェストの数倍かかっているのでまだまだ改善の余地あり。

Code size

  • 通常ブートROMのサイズは制限されている。OpenTitanの場合32KiB
  • そこに署名検証ルーチンが入るかどうか自体が大きな検討事項
  • Rustでコンパイルした各コードサイズが以下。これを見るとSPHINCS+はかなり厳しそうに見える。ハード実装の場合はもっと小さくなる？

Implementation security

  • 実はこの章がかなり長い。重要なのでそれはそう
  • バッファオーバーフローのような脆弱性はRust化で緩和できるブートローダー全体をRust化する動きもある。
  • しかしフォールト攻撃には脆弱。

fault injection

  • wolfSSLやOpenTitanの実装は、ソフトベースのフォールと攻撃対策を備えており、保護レベルを設定可能。
  • しかしながらこれらも完全ではない。
  • ARCHIEを使って、１名スキップをエミュレートしHBS（Rust実装版？）を評価
  • LMSに対しては２箇所の脆弱性が見つかった。
    • 一つはAUIPC命令：プログラムカウンタに対する測値加算命令で、認証パスの計算に使われる。5層のツリーで１回ずつ使われるので5回脆弱な命令が存在する。これがスキップされると、不正な認証パスでも検証をパスする可能性がある。
    • もう一つはmap_err：エラーハンドリング関数の分岐スキップ。これによりエラーがエラーじゃないものとして処理される。
  • XMSS/SHIPNCS+もいくつかの脆弱性が見つかっているが省略。

Conclusion

  • LMS/SPHINC+-sを推奨（SHIPNCS+-sは標準化から外れた）。
  • w=256パラメータがよさそう。

Discussion