Internet Research Task Force (IRTF) A. Huelsing Request for Comments: 8391 TU Eindhoven Category: Informational D. Butin ISSN: 2070-1721 TU Darmstadt S. Gazdag genua GmbH J. Rijneveld Radboud University A. Mohaisen University of Central Florida May 2018 XMSS: eXtended Merkle Signature Scheme 概要 このノートは, 科学文献の既存の記述に基づくハッシュベースの電子署名システム eXtended Merkle Signature Scheme (XMSS) について記述する. このノートは, ワンタイム署名スキーム Winternitz One-Time Signature Plus (WOTS+)と single-tree のスキーム XMSS, XMSS の multi-tree の変種 XMSS^MT を指定する. XMSS と XMSS^MT は主要な構築ブロックで WOTS+ を用いる. XMSS は数学の問題によって推測される困難さに依存しない暗号学的電子署名を提供する. 代わりに, 暗号学的ハッシュ関数の性質にのみ依存することが証明されている. XMSS は, 基底のハッシュ関数の衝突耐性が壊れている場合でも, 強いセキュリティの保証, さらに安全さえ提供する. コンパクトな実装に適していて, 実装が相対的に楽で, サイドチャンネル攻撃に自然に耐性がある. 他の多くの署名システムと異なり, ハッシュベースの署名は, 量子コンピューターを用いた既知の攻撃に現在のところ耐えることができる. Huelsing, et al. Informational [Page 1] RFC 8391 XMSS May 2018 このメモの位置づけ この文書は, インターネット標準課程仕様ではない. 情報共有目的で発行される. この文書は, Internet Research Task Force (IRTF) の成果物だ. IRTF はインターネットに関する調査と開発の行動について出版する. これらの結果は配置には適していないかもしれない. この RFC は Internet Research Task Force (IRTF) のCrypto Forum Research Group の合意を表わしている. IRSG によって出版を許可された文書は, インターネット標準のいかなるレベルの候補ではない. RFC 7841 の 2節を参照. この文書の現在の状態についての情報, 訂正情報, フィードバックを提供する方法は, http://www.rfc-editor.org/info/rfc8391 で得られる. 著作権情報 Copyright (c) 2018 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Huelsing, et al. Informational [Page 2] RFC 8391 XMSS May 2018 目次 1イントロダクション ....................................................5 1.1. 量子後の暗号学での CFRG のノート .....................6 1.2. この文書で用いる表記 ..........................7 2. 表記法 ........................................................7 2.1. データタイプ .................................................7 2.2. 関数 ..................................................7 2.3. 演算子 ..................................................8 2.4. 整数からバイトへの変換 .................................9 2.5. ハッシュ関数アドレススキーム ...............................9 2.6. ベースの数 w の文字列 .................................12 2.7. メンバー関数 ..........................................13 3. プリミティブ .....................................................14 3.1. WOTS+: ワンタイム署名 ................................14 3.1.1. WOTS+ のパラメーター ...................................14 3.1.1.1. WOTS+ 関数 ...........................15 3.1.2. WOTS+ Chaining 関数 ............................15 3.1.3. WOTS+ 秘密鍵 ..................................16 3.1.4. WOTS+ 公開鍵 ...................................17 3.1.5. WOTS+ 署名の生成 .........................17 3.1.6. WOTS+ 署名の検証 .......................19 3.1.7. 疑似乱数鍵生成 ........................20 4. スキーム ........................................................20 4.1. XMSS: eXtended Merkle Signature Scheme ....................20 4.1.1. XMSS のパラメーター ....................................21 4.1.2. XMSS ハッシュ関数 ................................22 4.1.3. XMSS 秘密鍵 ...................................22 4.1.4. ランダム化された木のハッシュ化 ............................23 4.1.5. L-Trees ............................................23 4.1.6. TreeHash ...........................................24 4.1.7. XMSS 鍵生成 ................................25 4.1.8. XMSS 署名 .....................................27 4.1.9. XMSS 署名の生成 ..........................28 4.1.10. XMSS 署名の検証 .......................30 4.1.11. 疑似乱数鍵生成 .......................32 4.1.12. フリーインデックスの扱いと部分秘密鍵 ......33 4.2. XMSS^MT: Multi-Tree XMSS ..................................33 4.2.1. XMSS^MT のパラメーター .................................33 4.2.2. XMSS^MT 鍵生成 .............................33 4.2.3. XMSS^MT 署名 ..................................36 4.2.4. XMSS^MT 署名の生成 .......................37 4.2.5. XMSS^MT 署名の検証 .....................39 4.2.6. 疑似乱数鍵生成 ........................40 4.2.7. フリーインデックスの扱いと部分秘密鍵 .......40 Huelsing, et al. Informational [Page 3] RFC 8391 XMSS May 2018 5. パラメーターセット .................................................40 5.1. 関数の実装 ................................41 5.2. WOTS+ パラメーター ..........................................43 5.3. XMSS パラメーター ...........................................43 5.3.1. パラメーターのガイド ....................................44 5.4. XMSS^MT のパラメーター ........................................45 5.4.1. パラメーターのガイド ....................................47 6. 原理 ......................................................49 7. リファレンスコード .................................................50 8. IANA の考察 ............................................50 9. セキュリティの考察 ........................................54 9.1. セキュリティの証明 ...........................................55 9.2. 最小限のセキュリティの仮定 ..............................56 9.3. 量子後のセキュリティ .....................................56 10. References ....................................................57 10.1. Normative References .....................................57 10.2. Informative References ...................................58 Appendix A. WOTS+ XDR Formats ....................................60 A.1. WOTS+ Parameter Sets ......................................60 A.2. WOTS+ Signatures ..........................................60 A.3. WOTS+ Public Keys .........................................61 Appendix B. XMSS XDR Formats .....................................61 B.1. XMSS Parameter Sets .......................................61 B.2. XMSS Signatures ...........................................62 B.3. XMSS Public Keys ..........................................64 Appendix C. XMSS^MT XDR Formats ..................................65 C.1. XMSS^MT Parameter Sets ....................................65 C.2. XMSS^MT Signatures ........................................67 C.3. XMSS^MT Public Keys .......................................71 Acknowledgements ..................................................73 Authors' Addresses ................................................74 Huelsing, et al. Informational [Page 4] RFC 8391 XMSS May 2018 1イントロダクション (暗号学的) 電子署名スキームは, 非対称のメッセージ認証を提供する. 鍵生成アルゴリズムは, 秘密鍵と公開鍵から構成される鍵ペアを生成する. 署名を生成するのに秘密鍵を用いて, メッセージは署名される. メッセージ/署名のペアが, 公開鍵を用いて検証できる. ワンタイム署名 (OTS) スキームは, ただ 1 つのメッセージを安全に署名するために 1 つの鍵ペアを用いる. メニータイム署名 (MTS) システムは, 複数のメッセージの署名が可能だ. OTS スキームと MTS スキームは, 1979 に Merkle で提案されたように [Merkle83]. それぞれから構成される. これらは, 1990 年代によく研究され, 2000 年代半ば以降に再び注目されるようになった. 量子コンピューターの助けをえる攻撃に対する耐性があるからだ. これらの署名スキームの種類は, 暗号学的ハッシュ関数で構成されているので, ハッシュベース署名スキームと呼ばれる. ハッシュベース署名スキームは一般に小さな秘密鍵と公開鍵, 高速な署名生成と検証を特徴とする; 一方で大きな署名と相対的に遅い鍵生成を特徴とする. 加えて, 多種のアプリケーションの利益となるコンパクトな実装に適していて, 大くの種類のサイドチャンネル攻撃に自然と耐性がある. ハッシュベース署名の導入と標準化に向ってはいくつかの進歩が成されてきた. Buchmann と Dahmen, Huelsing は eXtended Merkle Signature Scheme (XMSS) [BDH11] を提案した. Merkle のもともとのスキームよりも優れた効率と標準のモデルでの現代的なセキュリティ耐性を提供する. McGrew と Curcio, Fluhrer は, Lamport と Diffie, Winternitz, Merkle の将来性のある仕事をベースにしたLeighton-Micali Signature (LMS) スキームを指定する Internet-Draft [MCF18] を執筆した. これは XMSS とは異なるアプローチを取りランダムオラクルモデルでのセキュリティ引数に完全に依存している. つい最近, ステートレスなハッシュベース署名スキーム SPHINCS が導入された[BHH15]. 現在へのアプリケーションにより簡単に配置しやすくする意図がある. ハッシュベースを導入するにあたっての合理的な次のステップは, 基本のアルゴリズム -- LMS かつ/ないし XMSS, SPHINCS, その他の変種 -- の仕様を完成させることだ. eXtended Merkle Signature Scheme (XMSS) [BDH11] は最新のステートフルハッシュベース署名スキームだ. これらのスキームの中で最初の署名で, 遅い鍵生成の問題を解決する multi-tree の変種が備わっている. さらに, 基底のハッシュ関数に弱い仮定をするだけで XMSS が安全だと示すことができる. 特に, XMSS のセキュリティに暗号学的ハッシュ関数の衝突耐性が要求されない. [HRS16] で記述された XMSS の改良もこのメモの一部だ. Huelsing, et al. Informational [Page 5] RFC 8391 XMSS May 2018 この文書は, XMSS の single-tree と multi-tree の変種について記述する. XMSS で利用されている [Huelsing13] で導入された Winternitz OTS スキームの変種である WOTS+ についても記述する. このスキームは, 実装間の相互運用性を保証するために十分な特異性を持って記述される. この文書は次のように構成されている. 表記方が 2 節で導入される. 3 節は WOTS+ 署名システムを記述する. 4 節で MTS スキームが定義される. 4.1 節が eXtended Merkle Signature Scheme (XMSS) で 4.2 節で その multi-tree 変種 (XMSS^MT) となる. 5 節でパラメーターについて記述される. 6 節はこのノートでの選択の根拠を記述する. 7 節はリファレンスコードについての情報を与える. 8節で, これらの署名システムについての IANA レジストリについて記述される. 最後に 9節で セキュリティの考察が示される. 1.1. 量子後の暗号学での CFRG のノート Crypto Forum Research Group (CFRG) によって文書化されたすべての量子後のアルゴリズムは, 現在実験とさらなる技術開発 (たとえば IETF プロトコルに対する性能とサイズの影響を確定するため) の準備ができていると考えられている. しかし, 執筆時に著者にはこのようなアルゴリズムを十分に配置した経験はない. これらのアルゴリズムの多くには, 特有の制限がある. たとえば, 確立したスキームに比べ古典的なインタフェイスの変更や提案されたパラメーターにいて暗号解析が弱い. CFRG は, 量子後の技術を記述するすべての文書で前段落を含むことと どのような特定の制限(特に特定のスキームの利用や配置に影響する可能性のある制限)について明確な追加の警告を含めることについて合意している. 文書の更新により時間とともにこのガイダンスは変更されるかもしれない. 加えて, XMSS について: 量子アルゴリズムについての調査コミュニティの知識の現在の状態において, 量子コンピューターに対してこの文書で記述する署名スキームの暗号学的セキュリティについて自信があることは CFRG の合意だ. 実際, インターネットの重要な部分のセキュリティが, 開発者が次の注意を払えば, この文書で定義された署名スキームに依存できることに自信がある. 伝統的な署名スキームと対照的に, この文書で記述される署名スキームはステートフルで, つまり秘密鍵が時間と共に変化する. 秘密鍵の状態が 2 度利用されると, 暗号学的なセキュリティの保証はない. Huelsing, et al. Informational [Page 6] RFC 8391 XMSS May 2018 結果として新しいメッセージの署名の偽造が可能となってしまう. これは多くの開発者にとって一般的ではない新しい特徴なので秘密鍵の注意深い扱いが必要となる. 秘密鍵の再利用を防ぐシステムなしでここに記述されるスキームを開発者は利用しないほうがよい. この文書で記述するスキームがステートフルである事実は, 電子署名の古典的な API を変更なしで利用できないことを示している. cannot be used without modification. API は秘密鍵の状態を取り扱えなければならない; とりわけ, これは API が 更新された秘密鍵の状態を返すことができなければならないことを意味している. 1.2. この文書で用いる表記 この文書でのキーワード "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", "OPTIONAL" は, ここで示しているようにすべて大文字で出現した場合のみ, BCP 16 [RFC2119] [RFC8174] で記述されているように解釈される. 2. 表記法 2.1. データタイプ バイトとバイト文字列が基本のデータタイプだ. バイトは 8 ビットの列だ. 単一のバイトは, 最初に "0x" が付く 16 進数字のペアとして表される. バイト文字列は, 0 以上のバイトの順序付き列で, 最初に "0x" が付く 16 進文字の順序付き列として表わされる. たとえば, 0xe534f0 は長さ 3 のバイト文字列だ. バイト文字列の配列は, すべてのバイト文字列が同じ長さを持つ インデックス 0 から始まる順序付きインデックス付き集合だ. すべてのデータタイプや構造にビッグエンディアン表現を仮定する. 2.2. 関数 x が 非負の実数として, 次の関数を定義する: ceil(x): x 以上の最小の整数を返す. floor(x): x 以下の最大の整数を返す. lg(x): x の 2 を底とする対数を返す. Huelsing, et al. Informational [Page 7] RFC 8391 XMSS May 2018 2.3. 演算子 a と b が整数の場合, 数学の演算子が次のように定義される. ^ : a ^ b は a の b 乗の結果を表す. * : a * b は a と b の席を表す. この演算子は, 通常の数学の表記法のように, 曖昧さがない場合に省略される場合がある. / : a / b は 非 0 の b による a の商を表わす. % : a % b は b による整数除算の非 0 の剰余を表す. + : a + b は a と b の和を表す. - : a - b は a と b の差を表す. ++ : a++ は 1 の加算を表す. つまり a = a + 1. << : a << b は 非負の b での a の論理左シフトを表す. つまり a * 2^b. >> : a >> b は 非負の b での a の論理右シフトを表す. floor(a / 2^b). 数式の評価で, 演算子の標準の順序が用いられる. 配列も一般的な方法で使われる. 配列 A の i 番目の要素は A[i] で表される. 必要に応じてバイト文字列はバイトの配列として扱われる. X がバイト文字列なら, X[i] は i 番目のバイトを表し, X[0] がもっとも左のバイトとなる. A と B が同じ長さのバイト文字列なら: o A AND B はビットワイズの論理積操作を表す. o A XOR B はビットワイズの論理排他和操作を表す. B がバイトで i が整数ならば, B >> i は論理右シフト操作を表す. Huelsing, et al. Informational [Page 8] RFC 8391 XMSS May 2018 X が x バイト文字列, Y が y バイト文字列ならば, X || Y は X と Y の連結を示し, X || Y = X[0] ... X[x-1] Y[0] ... Y[y-1]. 2.4. 整数からバイトへの変換 x と y が非負の整数ならば, X = toByte(x, y) をビッグエンディアンバイトオーダーの x の 2 進表現を含む y バイトの文字列として定義する. 2.5. ハッシュ関数アドレススキーム この文書で記述されるスキームは, それぞれのハッシュ関数呼び出しをランダム化する. 最初のメッセージダイジェストを除き, それぞれのハッシュ関数呼び出しで異なる鍵と異なるビットマスクが用いられることを意味する. これらの値は, 鍵 SEED と 32 バイトアドレス ADRS を入力, n バイトの値 (n はセキュリティパラメーター)を出力に取る疑似乱数関数により疑似乱数的に生成される. ここで, アドレス ADRS の構造を説明し, アドレスを操作するセッターメソッドを提案する. アドレスの生成は, 利用されている次の節で説明する. 次の 2 つの節でのスキームは, セキュリティパラメーター n でパラメーター化された 2 種のハッシュ関数を用いる. ハッシュ木の構築のため, n バイトの鍵と 2n バイトの入力を n バイトの出力に射影するハッシュ関数が用いられる. この関数をランダム化するために, 3n バイトが必要となる. n バイトの鍵と 2n バイトのビットマスクだ. OTS スキームの構築のために, n バイトの鍵と n バイトの入力を n バイトの出力に射影するハッシュ関数が用いられる. この関数をランダム化するために, 2n バイトが必要となる. n バイトの鍵と n バイトのビットマスクだ. 結果として, 最初の関数に 3 つのアドレスが, 2番目の関数に 2 つのアドレスが必要とされる. ユースケースごとに, 3 つの異なるタイプのアドレスがある. 1 つのタイプは, OTS スキームのハッシュで用いられる, 次は, メインの Merkle 木の構築でのハッシュに用いられる, さらに 1つは L-tree でのハッシュに用いられる. 最後のものはワンタイプ公開鍵の圧縮するために使われる. これらすべてのタイプは, 可能な限り形式を共有する. この節の残りで, これらのタイプについて詳述する. アドレスの構造はワードの境界でコンパイルされる. この文脈ではワードは 32 bit long だ. 木のアドレスだけは単一のワードにフィットさせるには長すぎるので, 2 つのワードにフィットできる. アドレスは次にように構造化される. 最上位ビットの 1 ワードの layer address に始まり, 2 ワードの tree address が続く. どちらのアドレスも multi-tree の変種 (4.2 節参照) のために必要とされ, multi-tree での tree の位置を記述する. そのため, single-tree のアプリケーションでは 0 に設定される. For Huelsing, et al. Informational [Page 9] RFC 8391 XMSS May 2018 multi-tree のハッシュベースの署名のため, layer address は multi-tree での, 最下層の木を高さ 0 から始まる, 木の高さを記述する. tree address は, もっとも左の木をインデックス 0 から始める multi-tree の層での木の位置を記述する. 次のワードでアドレスのタイプを定義する. OTS アドレスでは 0, L-tree アドレスでは 1, hash tree アドレスでは 2 が設定される. アドレスの type ワードが変更する時はいつでも, すべての後続のワードが 0 で初期化されて, 利用していないパディングのワードに非 0 の値が入らないようにする必要がある. まず, OTS アドレスの場合を記述する. この場合, type ワードに続いて木の中の OTS 鍵ペアのインデックスをエンコードした OTS address ワードがある. 次の word は chain address をエンコードしたもので, chain の中でハッシュ関数呼び出しのアドレスをエンコードした word だ. 最後の keyAndMask と呼ばれるワードは 1 つのハッシュ関数呼び出しのために 2 つの異なるアドレスを生成するのに使われる. 鍵を生成するためなら, この word は 0 に設定される. n バイトの bitmask を生成するなら, この word は 1 に設定される. +-------------------------+ | layer address (32 bits)| +-------------------------+ | tree address (64 bits)| +-------------------------+ | type = 0 (32 bits)| +-------------------------+ | OTS address (32 bits)| +-------------------------+ | chain address (32 bits)| +-------------------------+ | hash address (32 bits)| +-------------------------+ | keyAndMask (32 bits)| +-------------------------+ OTS Hash Address L-tree の場合の議論に移る. type ワード は 1に設定される. この場合は type ワードに続いて, この L-tree を使って計算された葉のインデックスをエンコードした L-tree address ワードがある. 次のワードは, L-tree 中の次の計算の入力になるノードの高さをエンコードする. 次のワードは, L-tree 中のその高さでのノードのインデックスをエンコードする. このとき, 最後のワードの keyAndMask は 1 つの関数呼び出しのために 3 つの異なるアドレスを生成するのに使われる. 鍵を生成するためなら, この word は 0 に設定される. 2n バイトの bitmask の最上位 n バイトを生成するなら, この word は 1 に設定される. 2n バイトの bitmask の最下位 (n) バイトを生成するなら, この word は 2 に設定される. Huelsing, et al. Informational [Page 10] RFC 8391 XMSS May 2018 +-------------------------+ | layer address (32 bits)| +-------------------------+ | tree address (64 bits)| +-------------------------+ | type = 1 (32 bits)| +-------------------------+ | L-tree address (32 bits)| +-------------------------+ | tree height (32 bits)| +-------------------------+ | tree index (32 bits)| +-------------------------+ | keyAndMask (32 bits)| +-------------------------+ L-tree Address 残りのタイプである main tree hash address を記述する. この場合, type ワードは 2 に設定される. 続いて 1ワードが 0 でパディングされる. 次のワードは, 次の計算の入力となるノードの高さをエンコードする. その高さでのノードのインデックスが次のワードとなる. L-tree addresses のように, 最後のワード keyAndMask は1 つの関数呼び出しのために 3 つの異なるアドレスを生成するのに使われる. 鍵を生成するためなら, この word は 0 に設定される. 2n バイトの bitmask の最上位 n バイトを生成するなら, この word は 1 に設定される. 2n バイトの bitmask の最下位 (n) バイトを生成するなら, この word は 2 に設定される. +-------------------------+ | layer address (32 bits)| +-------------------------+ | tree address (64 bits)| +-------------------------+ | type = 2 (32 bits)| +-------------------------+ | Padding = 0 (32 bits)| +-------------------------+ | tree height (32 bits)| +-------------------------+ | tree index (32 bits)| +-------------------------+ | keyAndMask (32 bits)| +-------------------------+ A Hash Tree Address Huelsing, et al. Informational [Page 11] RFC 8391 XMSS May 2018 これらのアドレス中のすべてのフィールドは, 符号無し整数でエンコードされる. アドレスの生成を記述する際, 正の整数を取り フィールドのビットをフィールドの長さの整数の 2 進表現に設定する setter メソッドを用いる. さらに, setType() メソッドは type ワードに続く 4 つ のワードを 0 に設定することを前提とする. 2.6. ベース w の数の文字列 バイト文字列は, ベース w の数の文字列として解釈されうる. つまり 集合 {0, ..., w - 1} の整数だ. 対応は, 次のように関数 base_w(X, w, out_len) (Algorithm 1) で定義される. X が len_X バイトの文字列で, w が 集合 {4, 16} のメンバーなら, base_w(X, w, out_len) は, 0 から w -1 の間の out_len 要素の整数配列を出力する. 長さ out_len は, 8 * len_X/lg(w) 以下が要求されている. Algorithm 1: base_w 入力: len_X バイトの文字列 X, 整数 w, 出力長 out_len 出力: out_len 要素の整数配列 basew int in = 0; int out = 0; unsigned int total = 0; int bits = 0; int consumed; for ( consumed = 0; consumed < out_len; consumed++ ) { if ( bits == 0 ) { total = X[in]; in++; bits += 8; } bits -= lg(w); basew[out] = (total >> bits) AND (w - 1); out++; } return basew; たとえば X が (ビッグエンディアンの) バイト文字列 0x1234 ならば, base_w(X, 16, 4) は 配列 a= {1, 2, 3, 4} を返す. Huelsing, et al. Informational [Page 12] RFC 8391 XMSS May 2018 X (represented as bits) +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | 0| 0| 0| 1| 0| 0| 1| 0| 0| 0| 1| 1| 0| 1| 0| 0| +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ X[0] | X[1] X (represented as base 16 numbers) +-----------+-----------+-----------+-----------+ | 1 | 2 | 3 | 4 | +-----------+-----------+-----------+-----------+ base_w(X, 16, 4) +-----------+-----------+-----------+-----------+ | 1 | 2 | 3 | 4 | +-----------+-----------+-----------+-----------+ a[0] a[1] a[2] a[3] base_w(X, 16, 3) +-----------+-----------+-----------+ | 1 | 2 | 3 | +-----------+-----------+-----------+ a[0] a[1] a[2] base_w(X, 16, 2) +-----------+-----------+ | 1 | 2 | +-----------+-----------+ a[0] a[1] 例 2.7. メンバー関数 アルゴリズムの記述を単純化するため, メンバー関数の存在を仮定する. 公開鍵 PK のような複雑なデータ構造が値 X を持つなら, getX(PK) はこの公開鍵の値 X を返す. それに対応して, setX(PK, X, Y) は PK の 値 X を Y が持つ値に設定する. メンバー関数の名前としてキャメルケースが用いられるので, 値 z は関数名の中では Z として参照され, たとえば getZ となる. Huelsing, et al. Informational [Page 13] RFC 8391 XMSS May 2018 3. プリミティブ 3.1. WOTS+: ワンタイム署名 この節は [Huelsing13] でのものに似たマナーで WOTS+ システムを記述する. WOTS+ は OTS スキームだ; 秘密鍵は任意のメッセージの署名に利用できる一方, それぞれの秘密鍵は単一のメッセージの署名に一度だけしか用いられなければならない. 特に , 秘密鍵が 2 つの異なるメッセージの署名に用いられると, スキームは安全ではなくなる. この節はパラメーターの説明で始める. その後で, WOTS+ スキームの主要な構築ブロックを形成するいわゆる chaining 関数について説明する. 次に, 鍵生成や署名, 検証のアルゴリズムを記述する. 最後に, 疑似乱数鍵生成について議論する. 3.1.1. WOTS+ のパラメーター WOTS+ はパラメーター n と w を用いる. どちらも正の整数の値を取る. これらのパラメーターは次のように要約される: n: バイトでのメッセージ長, かつ秘密鍵と公開鍵, 署名の要素の長さ. w: Winternitz パラメーター; 集合 {4, 16 } のメンバー. パラメーターは 値 len, len_1, len_2 を計算するのに用いられる. len: WOTS+ 秘密鍵と公開鍵, 署名での n バイト文字列要素の数len = len_1 + len_2, ここで len_1 = ceil(8n / lg(w)), len_2 = floor(lg(len_1 * (w - 1)) / lg(w)) + 1 で計算される. n の値は, WOTS+ で用いられる暗号学的ハッシュ関数によって決定される. ハッシュ関数は, 適切なセキュリティレベルを保証するように選ばれる. n の値は, 署名アルゴリジムで処理できる入力長だ. しばしばメッセージダイジェストの長さとなる. パラメーター w は 集合 {4, 16} から選ぶことができる. w のより大きな値は, 署名をより小さくするが, 全体の署名操作をより遅くする; セキュリティに対しての影響はほとんどない. w の選択は, 値 4 か 16 に限定されている. これらの値は最適なトレードオフと実装の用意さをもたらす. WOTS+ パラメーター は必要に応じてアルゴリズムの入力に暗黙的に含まれる. Huelsing, et al. Informational [Page 14] RFC 8391 XMSS May 2018 3.1.1.1. WOTS+ 関数 WOTS+ アルゴリズムは鍵付きの暗号学的ハッシュ関数 F を用いる. F は長さ n の鍵を用い, 長さ n のバイト文字列を受付け, また返す. 特定のインスタンス化における詳細は 5 節にある. F のセキュリティの考察は 9 節で議論する. 加えて, WOTS+ は 疑似乱数関数 PRF を用いる. PRF は n バイトの鍵と 32 ビットのインデックスを入力として取り, 長さ n の疑似乱数出力を生成する. 特定のインスタンス化における詳細は 5 節にある. PRF のセキュリティの考察は 9 節で議論する. 3.1.2. WOTS+ Chaining 関数 chaining 関数 (Algorithm 2) は PRF の出力を用いて n バイトの入力の F の繰り返しを計算する. 入力として OTS ハッシュアドレスを取る. このアドレスには, この chain のアドレスをエンコードするために最初の 6 つの 32 ビットワードが設定される. それぞれの繰り返しで, PRF は F のための鍵を生成するのに用いられ, F による処理の前に bitmask と中間結果が XOR される. ADRS は 2.5 節で指定された 32 バイト OTS ハッシュアドレスで, SEED は n バイトの文字列だ. 鍵と bitmask を生成するために PRF は SEED を鍵 ADRS を入力として呼ばれる. chaining 関数は n バイトの文字列 X と開始インデックス i, ステップ数 s, ADRS, SEED を入力として取る. chaining 関数は, PRF の出力を用いて, 入力 X に F を s 回繰り返して得られる値を出力とする. Huelsing, et al. Informational [Page 15] RFC 8391 XMSS May 2018 Algorithm 2: chain - Chaining 関数 Input: 入力文字列 X, 開始インデックス i, ステップ数 s, シード SEED, アドレス ADRS. 出力: X に F を s 回繰り返した値 if ( s == 0 ) { return X; } if ( (i + s) > (w - 1) ) { return NULL; } byte[n] tmp = chain(X, i, s - 1, SEED, ADRS); ADRS.setHashAddress(i + s - 1); ADRS.setKeyAndMask(0); KEY = PRF(SEED, ADRS); ADRS.setKeyAndMask(1); BM = PRF(SEED, ADRS); tmp = F(KEY, tmp XOR BM); return tmp; 3.1.3. WOTS+ 秘密鍵 WOTS+ の秘密鍵は sk (s は secret の s) と示され, n バイト文字列の長さ len の配列だ. この秘密鍵は, せいぜい 1 つのメッセージの署名にのみ使われなければならない. それぞれの n バイトの文字列は, 一様分布からランダムに選択されるか, 暗号学的に安全な疑似乱数手順を用いて選択されなければならない. 後者の場合, 用いる手順のセキュリティは, 少なくとも WOTS+ パラメーターで用いるもののそれと少なくとも一致しなければならない. 疑似乱数鍵生成についてのさらなる議論は 3.1.7 節を参照. 次の疑似コード (Algorithm 3) は sk の生成のアルゴリズムを記述する. Algorithm 3: WOTS_genSK - WOTS+ 秘密鍵の生成 入力: なし. 出力: WOTS+ 秘密鍵 sk for ( i = 0; i < len; i++ ) { initialize sk[i] with a uniformly random n-byte string; } return sk; Huelsing, et al. Informational [Page 16] RFC 8391 XMSS May 2018 3.1.4. WOTS+ 公開鍵 WOTS+ の鍵ペアは, 長さ w の len 個のハッシュ chain から構成される仮想の構造体を定義する. 秘密鍵中有の len 個の n バイト文字列はそれぞれ, 1 つのハッシュ chain の開始ノードを定義する. 公開鍵はそれぞれのハッシュ chain の終了ノードから構成される. それゆえ, 秘密鍵のように, 公開鍵も n バイト文字列の長さ len の配列だ. ハッシュ chain を計算するため, chaining 関数 (Algorithm 2) が用いられる. OTS ハッシュアドレス ADRS と シード SEED は呼び出されるアルゴリズムから供給される必要がある. このアドレスは, より大きな構造の中での WOTS+ 鍵ペアのアドレスをエンコードする. それゆえ, WOTS+ アルゴリムは, 最後の 3 つの 32 ビットワードを除いて ADRS のどの部分も操作してはならない. ここで用いる SEED は公開情報で検証者も利用可能なことに注意. 次の手順 (Algorithm 4) は pk を生成するアルゴリズムを記述する. sk は 秘密鍵だ. Algorithm 4: WOTS_genPK - 秘密鍵から WOTS+ 公開鍵を生成 入力: WOTS+ 秘密鍵 sk, アドレス ADRS, シード SEED. 出力: WOTS+ 公開鍵 pk for ( i = 0; i < len; i++ ) { ADRS.setChainAddress(i); pk[i] = chain(sk[i], 0, w - 1, SEED, ADRS); } return pk; 3.1.5. WOTS+ 署名の生成 WOTS+ 署名は, n バイト文字列の 長さ len の配列だ. WOTS+ 配列は, メッセージを len 個の 0 から w-1 の間の 整数に射影することで生成される. このために, メッセージは, 2.6 節で定義された base_w 関数を用いて, 長さ len-1 のベース w の数に変換される. 次に, チェックサムが計算され base_w 関数を用いて長さ len_2 のベース w の数 として変換されたメッセージに追加される. チェックサムは 最大の整数の値 len_1 * (w - 1) * 2^8 に到達する可能性があり, そのため パラメーター n と w に依存することに注意. 5 節で与えられたパラメーター集合では, 32 ビット符号無し整数はチェックサムを保持するのに十分だ. 他のパラメーターの設定を用いるなら, チェックサムの整数値を保持する変数のサイズは, 十分に大きくなければならない. ベース w 整数のそれぞれが, 異なるハッシュ chain からノードが選択するために用いられる. 署名は, 選択されたノードを連結して形成される. OTS ハッシュアドレス ADRS と シード SEED は呼び出されるアルゴリズムから供給される必要がある. このアドレスは, より大きな構造の中での WOTS+ 鍵ペアのアドレスをエンコードする. それゆえ, WOTS+ アルゴリムは, 最後の 3 つの 32 ビットワードを除いて ADRS のどの部分も操作してはならない. Huelsing, et al. Informational [Page 17] RFC 8391 XMSS May 2018 ここで用いる SEED は公開情報で検証者も利用可能なことに注意. 署名生成の疑似コードを次に示す (Algorithm 5), ここで, M はメッセージ で sig は結果の署名だ. Algorithm 5: WOTS_sign - 秘密鍵とメッセージから署名を生成 入力: メッセージ M, WOTS+ 秘密鍵 sk, アドレッス ADRS, シード SEED. 出力 WOTS+ 署名 sig csum = 0; // Convert message to base w msg = base_w(M, w, len_1); // Compute checksum for ( i = 0; i < len_1; i++ ) { csum = csum + w - 1 - msg[i]; } // Convert csum to base w csum = csum << ( 8 - ( ( len_2 * lg(w) ) % 8 )); len_2_bytes = ceil( ( len_2 * lg(w) ) / 8 ); msg = msg || base_w(toByte(csum, len_2_bytes), w, len_2); for ( i = 0; i < len; i++ ) { ADRS.setChainAddress(i); sig[i] = chain(sk[i], 0, msg[i], SEED, ADRS); } return sig; 署名のデータ形式は次で与えられる. +---------------------------------+ | | | sig_ots[0] | n bytes | | +---------------------------------+ | | ~ .... ~ | | +---------------------------------+ | | | sig_ots[len - 1] | n bytes | | +---------------------------------+ WOTS+ 署名 Huelsing, et al. Informational [Page 18] RFC 8391 XMSS May 2018 3.1.6. WOTS+ 署名の検証 メッセージ M の署名 sig を検証するため, 検証者は署名から WOTS+ の公開鍵の値を計算する. メッセージハッシュの base_w の値とメッセージのチェックサムを用いて, 署名の値から始めて chain 計算を "補完" することで, これができる. この段階は, WOTS_pkFromSig と呼ばれ, Algorithm 6 にて後で記述される:そして, WOTS_pkFromSig の結果は与えられた公開鍵と比較される. 値が等しければ 署名は受け入れられる. そうでなければ, 署名は拒否されなければならないOTS ハッシュアドレス ADRS と シード SEED は呼び出されるアルゴリズムから供給される必要がある. このアドレスは, より大きな構造の中での WOTS+ 鍵ペアのアドレスをエンコードする. それゆえ, WOTS+ アルゴリムは, 最後の 3 つの 32 ビットワードを除いて ADRS のどの部分も操作してはならない. ここで用いる SEED は公開情報で検証者も利用可能なことに注意. Algorithm 6: WOTS_pkFromSig - メッセージとその署名から WOTS+ 公開鍵を計算 入力: メッセージ M, WOTS+ 署名 sig, アドレス ADRS, シード SEED. 出力: '一時的' WOTS+ 公開鍵 tmp_pk csum = 0; // Convert message to base w msg = base_w(M, w, len_1); // Compute checksum for ( i = 0; i < len_1; i++ ) { csum = csum + w - 1 - msg[i]; } // Convert csum to base w csum = csum << ( 8 - ( ( len_2 * lg(w) ) % 8 )); len_2_bytes = ceil( ( len_2 * lg(w) ) / 8 ); msg = msg || base_w(toByte(csum, len_2_bytes), w, len_2); for ( i = 0; i < len; i++ ) { ADRS.setChainAddress(i); tmp_pk[i] = chain(sig[i], msg[i], w - 1 - msg[i], SEED, ADRS); } return tmp_pk; 注意: XMSS は WOTS_pkFromSig を公開鍵の値の計算に用い, 比較は後回しにする. Huelsing, et al. Informational [Page 19] RFC 8391 XMSS May 2018 3.1.7. 疑似乱数鍵生成 実装は, 単一の n バイトの値から秘密鍵を生成するのに暗号学的に安全な疑似乱数法を用いてもよい. たとえば, 方法として [BDH11] で提案され後述する方法を用いてもよい. 他の方法を用いてもよい. 疑似乱数法の選択は相互運用性に影響しないが, 暗号学的な強度は利用される WOTS+ パラメーターのそれと一致しなければならない. ランダムな n バイト文字列から秘密鍵の要素を生成する利点は, 完全な秘密鍵の代わりにこの n バイトの文字列のみを保存するだけでよいことだ. 鍵は必要な時に再生成できる. [BDH11] で提案された方法を PRF を用いて記述できる. 鍵生成の間, 一様な乱数な n バイト文字列 S は 安全な乱数源から抽出される. この文字列 S は秘密鍵として保存される. 秘密鍵要素は必要な時にいつでも sk[i] = PRF(S, toByte(i, 32)) として計算される. このシード S はハッシュ関数の呼び出しをランダム化するのに使われるシード SEED とは異ならなければらならないことに注意. さらに, このシード S は秘密を保たなければらならない. このシード S は 低いエントロピーで, 人間が記憶できる値 であってはならない. 秘密鍵要素は S から決定的に導出され, それらの秘密性はセキュリティに重大だからだ. 4. スキーム この節では, WOTS+ を用いる eXtended Merkle Signature Scheme (XMSS) が記述される. XMSS は 2 つのフレーバーがある: single-tree の変種 (XMSS) と multi-tree の変種 (XMSS^MT) だ. どちらも, 単一の小さい公開鍵で WOTS+ の鍵ベアをたくさんの数組合せることができる. 追加された主要な要素は, 2進 hash 木構築だ. XMSS は 1つのハッシュ木を用い, 一方 XMSS^MT は XMSS 鍵ペアの木を用いる. 4.1. XMSS: eXtended Merkle Signature Scheme XMSS は, 潜在的にはたくさんの, しかし固定の数のメッセージに署名するための方法だ. Merkle 署名スキームを基底にしている. XMSS は 4 つの暗号学的構成要素からなっている: OTS 法としての WOTS+, 2 つの追加の暗号学的ハッシュ関数 H と H_msg, 疑似乱数関数 PRF. WOTS+ を用いる XMSS の主要な利点の1つが, 用いるハッシュ関数の衝突耐性に依存せずより弱い性質に依存していることだ. XMSS 公開/秘密鍵ペアはそれぞれ, すべてのノードに n バイトの値を含む完全な2進木に紐づく. それぞれの木の葉は WOTS+ の公開鍵の値の特別な木のハッシュが含まれる. 葉でないノードはそれぞれ, まず子コードの値を連結し, bitmask で XOR を計算し, 鍵付きのハッシュ関数 H を適用して計算される. bitmask とハッシュ関数 H の鍵は, 疑似乱数関数 PRF を用いて公開鍵の部分である (公開の) シードから生成される. Huelsing, et al. Informational [Page 20] RFC 8391 XMSS May 2018 XMSS 木のルートに対応する値は, シードと共にXMSS 公開鍵を形成する. 2^h のメッセージを署名するのに用いることができる鍵ペアを生成するために, 木の高さ h が用いられる. XMSS はステートフルな署名スキームで, つまりすべての署名生成で秘密鍵が変更する. 一時的な秘密鍵を2回使われてしまうことを避けるため, WOTS+ 鍵ペアは, 関連する葉に従いもっとも左の葉が 0 から始まるインデックスで 0 から (2^h) - 1 まで番号付けされる. 秘密鍵は, すべての署名生成にて更新されるインデックスを含む . すなわち, 次の未使用の WOTS+ 鍵ペアのインデックスを含む. 署名は, 利用した WOTS+ 鍵ペアのインデックスと メッセージの WOTS+ 署名, いわゆる認証パスから構成される. 認証パスは, WOTS+ 署名から始まる木のルートの値が検証者が計算できるようにする木のノードのベクトルだ. 検証者はルートの値を計算し, XMSS 公開鍵のそれぞれの値を比較する. それらが一致したら, 署名は正当だと宣言される. XMSS 秘密鍵は, すべての WOTS+ 秘密鍵と現在のインデックスから構成される. ストレージを削減するために, [BDH11] で記述されているような疑似乱数鍵生成手続きが利用されてもよい. 利用される方法のセキュリティは少なくとも XMSS インスタンスのセキュリティと一致しなければならない. 4.1.1. XMSS のパラメーター XMSS は次のパラメーターを持つ: h: 木の高さ (レベル数 - 1) n: メッセージダイジェストとそれぞれのノードのバイトでの長さ w: 3.1 節で示した WOTS+ について定義された Winternitz パラメーター 木には 2^h の葉がある. XMSS と XMSS^MT で, 秘密鍵と公開鍵はそれぞれ SK (S は secret の S) と PK と表される. WOTS+ では, 秘密鍵と公開鍵はそれぞれ sk (s は secret の s) と PK と表される. XMSS と XMSS^MT の署名は Sig と表される. WOTS+ の署名は sig を表される. XMSS と XMSS^MT のパラメーターは, 必要に応じてアルゴリズムの入力に暗黙的に含まれる. Huelsing, et al. Informational [Page 21] RFC 8391 XMSS May 2018 4.1.2. XMSS ハッシュ関数 WOTS+ で要求される暗号学的ハッシュ関数 F と疑似乱数関数 PRF に加えて, XMSS はさらに 2 つの関数を用いる: o 暗号学的ハッシュ関数 H. H は n バイトの鍵と 2n の長さのバイト文字列を受け取り n バイトの文字列を返す. o 暗号学的ハッシュ関数 H_msg. H_msg は 3n バイトの鍵と任意の長さのバイト文字列を受け取り n バイトの文字列を返す. 特定のインスタンス化における詳細は 5 節にある. H と H_msg のセキュリティの考察は 9 節で議論する. 4.1.3. XMSS 秘密鍵 XMSS の秘密鍵 SK は, 2^h の WOTS+ 秘密鍵と まだ利用されていない次の WOTS+ 秘密鍵の葉のインデックス idx, SK_PRF (メッセージハッシュの乱数化のための疑似乱数値を生成する n バイトの鍵), n バイトの値 root (木と SEED のルートノード), bitmask と ハッシュ関数の鍵を疑似乱数で生成するのに用いられる n バイトの公開 SEED (訳注: 原文では seed だが SEED と思われる) を含む. root と SEED は形式的には公開鍵の一部だと考えられるが, これらは (たとえば 署名の生成に)必要とされ, 公開鍵を入力として取らない関数でも要求される. XMSS 秘密鍵が作成されたときに 葉のインデックス idx は 0 に初期化される. 鍵 SK_PRF は一様分布に従う安全な乱数源から抽出されなければならない. WOTS+ 秘密鍵は 3,1 節で記述したように生成されなければらならない. もしくは, 秘密鍵のサイズを削減するために, 4.1.11 節で議論するように暗号学的疑似乱数法が利用されなければならない. SEED は一様乱数な n バイト文字列として生成される. SEED は公開の値だが, よいエントロピー源から生成されるのがセキュリティにとって重要だ. root ノードは鍵生成の節 (4.1.7 節) で後述するように生成される. その節では, 組合された秘密鍵と公開鍵の生成のアルゴリズム例も含む. 次のアルゴリズムの記述のために, getWOTS_SK(SK, i) メソッドの存在が仮定される. このメソッドは, XMSS 秘密鍵 SK と整数 i を入力として取り, SK の i 番目の WOTS+ 秘密鍵を出力する. Huelsing, et al. Informational [Page 22] RFC 8391 XMSS May 2018 4.1.4. ランダム化された木のハッシュ化 読み易さを改善するため, 木でのランダム化されたハッシュ化を行なう関数 RAND_HASH(LEFT, RIGHT, SEED, ADRS) (Algorithm 7) を導入する. ハッシュ関数の左半分, 右半分を表す 2つの n バイトの値 LEFT と RIGHTと PRF の鍵として用いられるシード SEED, このハッシュ関数呼び出しのアドレス ADRS を取る. RAND_HASH はまず鍵 KEY と n バイトのビットマスク BM_0, BM_1 を生成するために SEED と ADRS に対して PRF を用いる. そして, 乱数化されたハッシュ H(KEY, (LEFT XOR BM_0) || (RIGHT XOR BM_1)) を返す. Algorithm 7: RAND_HASH 入力: n バイトの値 LEFT, n バイトの値 RIGHT, シード SEED, アドレス ADRS. 出力: n バイトの乱数化されたハッシュ ADRS.setKeyAndMask(0); KEY = PRF(SEED, ADRS); ADRS.setKeyAndMask(1); BM_0 = PRF(SEED, ADRS); ADRS.setKeyAndMask(2); BM_1 = PRF(SEED, ADRS); return H(KEY, (LEFT XOR BM_0) || (RIGHT XOR BM_1)); 4.1.5. L-Trees 2 進ハッシュ木の葉を計算するのに, いわゆる L-tree が利用される. L-tree はバランスしてない 2 進のハッシュ木で, メインの XMSS 2 進ハッシュ木と別のものだが似ている. アルゴリズム ltree (Algorithm 8) は, WOTS+ 公開鍵 pk を入力として取り, 単一の n バイトの値 pk[0] に圧縮する. L-tree のアドレスをエンコードする L-tree アドレス ADRS とシード SEEED も入力として取る. Huelsing, et al. Informational [Page 23] RFC 8391 XMSS May 2018 Algorithm 8: ltree 入力: WOTS+ 公開鍵pk, アドレス ADRS, シード SEED 出力: n バイトの圧縮された公開鍵の値 pk[0] unsigned int len' = len; ADRS.setTreeHeight(0); while ( len' > 1 ) { for ( i = 0; i < floor(len' / 2); i++ ) { ADRS.setTreeIndex(i); pk[i] = RAND_HASH(pk[2i], pk[2i + 1], SEED, ADRS); } if ( len' % 2 == 1 ) { pk[floor(len' / 2)] = pk[len' - 1]; } len' = ceil(len' / 2); ADRS.setTreeHeight(ADRS.getTreeHeight() + 1); } return pk[0]; 4.1.6. TreeHash Merkle 木の最初の n バイトのノードの計算のため, サブルーチン treeHash (Algorithm 9) は XMSS 秘密鍵 SK (シード SEED を含む)と符号無し整数 s (開始インデックス), 符号無し整数 t (ターゲットのノードの高さ), 含まれる木のアドレスをエンコードするアドレス ADRS を入力として取る. 木の中のノードの高さは, 葉の高さを 0 から始めて数える. treeHash アルゴリズムは, 左端の葉が インデックス s のWOTS+ pk のハッシュとなる, 高さ t の木のルートノードを返す. s % 2^t = 0 が要求される. すなわち, インデックス s の葉は, 高さ t のサブ木の左端の葉だ. そうでなければ, このハッシュ-アドレス化スキームは失敗する. ここで記述する treeHash アルゴリズムは, 通常のスタック関数 push() と pop() を用いて, (t -1 ) ノードまでスタックの保持を用いる. さらに, (符号なし整数の)ノードの高さは, スタック上にノードの値と一緒に (n バイト文字列として)保持される. Huelsing, et al. Informational [Page 24] RFC 8391 XMSS May 2018 Algorithm 9: treeHash Input: XMSS 秘密鍵 SK, 開始インデックス s, ターゲットのノードの高さ t, アドレス ADRS. 出力: n バイトのルートノード - スタックの一番上のノード if( s % (1 << t) != 0 ) return -1; for ( i = 0; i < 2^t; i++ ) { SEED = getSEED(SK); ADRS.setType(0); // Type = OTS hash address ADRS.setOTSAddress(s + i); pk = WOTS_genPK (getWOTS_SK(SK, s + i), SEED, ADRS); ADRS.setType(1); // Type = L-tree address ADRS.setLTreeAddress(s + i); node = ltree(pk, SEED, ADRS); ADRS.setType(2); // Type = hash tree address ADRS.setTreeHeight(0); ADRS.setTreeIndex(i + s); while ( Top node on Stack has same height t' as node ) { ADRS.setTreeIndex((ADRS.getTreeIndex() - 1) / 2); node = RAND_HASH(Stack.pop(), node, SEED, ADRS); ADRS.setTreeHeight(ADRS.getTreeHeight() + 1); } Stack.push(node); } return Stack.pop(); 4.1.7. XMSS 鍵生成 XMSS 鍵ペアは, XMSS_keyGen (Algorithm 10) で記述されているように計算される. XMSS 公開鍵 PK は, SK にも保持されている, 2進ハッシュ木の root とシード SEED から構成される. root は treeHash を用いて計算される. XMSS の場合は, 単一の主な木のみがある. それゆえ, 利用されるアドレスは最初はすべて 0 の文字列に設定される. このアルゴリズムを導入するのに XMSS 秘密鍵 SK についてどのような特定の形式や取り扱いも定義しないことに注意. 前述した要件に関係し, 秘密鍵を初期化するのに簡単だが非常に非効率な例を単に示す. Huelsing, et al. Informational [Page 25] RFC 8391 XMSS May 2018 Algorithm 10: XMSS_keyGen XMSS 鍵ペアの生成 入力: 入力なし. 出力: XMSS 秘密鍵 SK, XMSS 公開鍵 PK // Example initialization for SK-specific contents idx = 0; for ( i = 0; i < 2^h; i++ ) { wots_sk[i] = WOTS_genSK(); } initialize SK_PRF with a uniformly random n-byte string; setSK_PRF(SK, SK_PRF); // Initialization for common contents initialize SEED with a uniformly random n-byte string; setSEED(SK, SEED); setWOTS_SK(SK, wots_sk)); ADRS = toByte(0, 32); root = treeHash(SK, 0, h, ADRS); SK = idx || wots_sk || SK_PRF || root || SEED; PK = OID || root || SEED; return (SK || PK); 前述したものは単なる例のアルゴリズムだ. 秘密鍵のサイズを削減するため疑似乱数鍵生成を用いることが強く推奨される. 公開鍵と秘密鍵の生成は, 空間の削減のためにインターリーブしてもよい. 特に, 秘密鍵の生成に疑似乱数法を用いる場合, それぞれの WOTS+ 鍵ペアが treeHash によって必要となる際に生成が実施されてもよい. XMSS 公開鍵の形式は次だ. +---------------------------------+ | algorithm OID | +---------------------------------+ | | | root node | n bytes | | +---------------------------------+ | | | SEED | n bytes | | +---------------------------------+ XMSS 公開鍵 Huelsing, et al. Informational [Page 26] RFC 8391 XMSS May 2018 4.1.8. XMSS 署名 XMSS 署名は, 次の要素から構成される (4 + n + (len + h) * n) バイトの文字列だ: o 利用した WOTS+ 鍵ペアのインデックス idx_sig (4バイト), o 乱数化されたメッセージハッシュ化で用いたバイト文字列 r (nバイト), o WOTS+ 署名sig_ots (len * n バイト), o 利用した WOTS+ 鍵ペアに関連する葉のいわゆる認証パス 'auth' (h * n バイト). 認証パスは n バイトの文字列の配列だ. 利用したノードから root へのパス上のノードの兄弟を含んでいる. パス上のノードそのものは含まない. 検証者は WOTS+ 公開鍵から木の root ノードを計算するのにこれらのノードを必要とする. ノード Node は木の中のその位置で指定される. Node(x, y) は, レベル x の y 番目のノードを表わす. レベルでのもっとも左のノードが y = 0 となる. 葉はレベル 0 で, root がレベル h だ. 認証パスは, すべての層 0 <= x <= (h - 1) 上のノードをきっかり 1 つ含む. i 番目の WOTS+ 鍵ペアのための, 0 から数えて j 番目の認証パスは次だ: Node(j, floor(i / (2^j)) XOR 1) 認証パスの計算は 4.1.9 節で議論される. Huelsing, et al. Informational [Page 27] RFC 8391 XMSS May 2018 署名のデータ形式は次で与えられる. +---------------------------------+ | | | index idx_sig | 4 bytes | | +---------------------------------+ | | | randomness r | n bytes | | +---------------------------------+ | | | WOTS+ signature sig_ots | len * n bytes | | +---------------------------------+ | | | auth[0] | n bytes | | +---------------------------------+ | | ~ .... ~ | | +---------------------------------+ | | | auth[h - 1] | n bytes | | +---------------------------------+ XMSS 署名 4.1.9. XMSS 署名の生成 XMSS 秘密鍵を用いてメッセージ M の XMSS 署名を計算するため, 署名者は乱数 r , 利用される WOTS+ 鍵ペアのインデックス idx_sig, 公開鍵からの root 値を鍵として用いて乱数化されたメッセージダイジェストをまず計算する. そして, 次の利用していない WOTS+ 秘密鍵を用いて メッセージダイジェストの WOTS+ 署名が計算される. 次に, 認証パスが計算される. 最後に秘密鍵が更新される. つまり idx がインクリメントされる. 実装者は, 秘密鍵を更新する前に署名を出力してはならない. 認証パスのノードの値はどのように計算されてもよい. この計算では, 関数 XMSS_sign (Algorithm 12) のためのサブルーチン buildAuth によって実行されることが仮定されている. 最速の代替手法は, すべての木のノードを保持しそれぞれのノードをコピーして署名の中の配列を設定するものだ. もっともストレージを必要としない代替手法は, treeHash アルゴリズム (Algorithm 9) を用いてそれぞれの署名のすべてのノードをオンラインで計算しなおすものだ. Huelsing, et al. Informational [Page 28] RFC 8391 XMSS May 2018 この間に, 時間とストレージのトレードオフが異なる, いくつかのアルゴリズムがある. 概要については [BDS09] を参照. さらなるアプローチが [KMN14] で見られる. この手順の詳細は相互運用性には関係ないことに注意; 署名の検証操作をするために, これらの詳細を知る必要はない. buildAuth の後述のバージョンは 完全性のために与えられる. 理解のための簡単な例だが, 非常に非効率だ. 代替のアルゴリズムのうちの 1 つを用いることが強く推奨される. XMSS 秘密鍵 SK が与えられると, 木のすべてのノードが決定される. これらの値は treeHash (Algorithm 9) で定義される.. したばって, 次のように認証パスを計算できる. (例) buildAuth - i 番目の WOTS+ 鍵ペアの認証パスを計算 Input: XMSS 秘密鍵 SK, WOTS+ 鍵ペアインデックス i, ADRS. 出力: 認証パス auth for ( j = 0; j < h; j++ ) { k = floor(i / (2^j)) XOR 1; auth[j] = treeHash(SK, k * 2^j, j, ADRS); } 署名生成の記述を 2 つの主要なアルゴリズムに分割する. 最初の 1 つ treeSig (Algorithm 11) は XMSS 署名の主要部分を生成し, multi-tree の変種 XMSS^MT でも利用される. XMSS_sign (Algorithm 12) は treeSig を呼び出すが, 後で行なう秘密鍵の更新の前にメッセージの圧縮を扱う. 後述のアルゴリズム treeSig (Algorithm 11) は n バイトのメッセージへの WOTS+ 署名と対応する認証パスを計算する. treeSig は入力として n バイトのメッセージ M' とXMSS 秘密鍵 SK, 署名のインデックス idx_sig, アドレス ADRS を取る. WOTS+ 署名 sig_ots と認証パス auth を連結したものを返す. Huelsing, et al. Informational [Page 29] RFC 8391 XMSS May 2018 Algorithm 11: treeSig - メッセージに対する WOTS+ 署名と対応する認証パスの生成 入力: n バイトのメッセージ M', XMSS 秘密鍵 SK,署名のインデックス idx_sig, ADRS. 出力: WOTS+ 署名 sig_ots と認証パス auth の連結 auth = buildAuth(SK, idx_sig, ADRS); ADRS.setType(0); // Type = OTS hash address ADRS.setOTSAddress(idx_sig); sig_ots = WOTS_sign(getWOTS_SK(SK, idx_sig), M', getSEED(SK), ADRS); Sig = sig_ots || auth; return Sig; 後述のアルゴリズム XMSS_sign (Algorithm 12) は更新された秘密鍵 SK とメッセージ M の署名を計算する. XMSS_sign は入力として任意の長さのメッセージ M と XMSS 秘密鍵 SK を取る. 更新された秘密鍵 SK と 署名 Sig の連結によるバイト文字列を返す. Algorithm 12: XMSS_sign - XMSS 署名の生成と XMSS 秘密鍵の更新 入力: メッセージ M, XMSS 秘密鍵 SK. 出力: 更新された SK, XMSS 署名 Sig idx_sig = getIdx(SK); setIdx(SK, idx_sig + 1); ADRS = toByte(0, 32); byte[n] r = PRF(getSK_PRF(SK), toByte(idx_sig, 32)); byte[n] M' = H_msg(r || getRoot(SK) || (toByte(idx_sig, n)), M); Sig = idx_sig || r || treeSig(M', SK, idx_sig, ADRS); return (SK || Sig); 4.1.10. XMSS 署名の検証 XMSS 署名は次のように検証される. まず, 乱数 r, インデックス idx_sig, PK からの root, メッセージ M を用いてメッセージダイジェストを計算する. そして, 利用された WOTS+ 公開鍵 pk_ops が WOTS_pkFromSig を用いて WOTS+ 署名から計算される. 次に WOTS+ 公開鍵は L-tree を用いた対応する葉の計算に用いられる. インデックス idx_sig と認証パス auth と共に, 葉は木の別の root 値の計算に用いられる. 計算された root 値が XMSS 公開鍵のものと一致した場合にのみ, 検証は成功する. その他のいかなる場合も, 検証は失敗に終わらなければらならない. Huelsing, et al. Informational [Page 30] RFC 8391 XMSS May 2018 署名の生成のように, 検証を 2 つの部分にわけて, XMSS^MT の記述に再利用できるようにする. XMSS^MT でも必要な手順は, 関数 XMSS_rootFromSig (Algorithm 13) によって実行される. XMSS_verify (Algorithm 14) は XMSS_rootFromSig をサブルーチンとして呼び, XMSS 特有の手順を扱う. XMSS 署名検証の主要部分は, 後述の XMSS_rootFromSig (Algorithm 13) で実施される. XMSS_rootFromSig は インデックス idx_sig, a WOTS+ 署名 sig_ots, 認証パス auth, n バイトのメッセージ M', シード SEED, アドレス ADRS を入力として取る. XMSS_rootFromSig は, 入力データによって定義された木の root の値を持つ n バイト文字列を返す Algorithm 13: XMSS_rootFromSig - 木の署名から root ノードを計算 入力: インデックス idx_sig, WOTS+ 署名 sig_ots, 認証パス auth, n バイトのメッセージ M', シード SEED, アドレス ADRS. 出力: n バイトの root 値 node[0] ADRS.setType(0); // Type = OTS hash address ADRS.setOTSAddress(idx_sig); pk_ots = WOTS_pkFromSig(sig_ots, M', SEED, ADRS); ADRS.setType(1); // Type = L-tree address ADRS.setLTreeAddress(idx_sig); byte[n][2] node; node[0] = ltree(pk_ots, SEED, ADRS); ADRS.setType(2); // Type = hash tree address ADRS.setTreeIndex(idx_sig); for ( k = 0; k < h; k++ ) { ADRS.setTreeHeight(k); if ( (floor(idx_sig / (2^k)) % 2) == 0 ) { ADRS.setTreeIndex(ADRS.getTreeIndex() / 2); node[1] = RAND_HASH(node[0], auth[k], SEED, ADRS); } else { ADRS.setTreeIndex((ADRS.getTreeIndex() - 1) / 2); node[1] = RAND_HASH(auth[k], node[0], SEED, ADRS); } node[0] = node[1]; } return node[0]; 完全な XMSS 署名検証を後で (Algorithm 14) 示す. メッセージ圧縮を扱い, root の計算を XMSS_rootFromSig に移譲し, 結果を公開鍵の値と比較する. XMSS_verify は XMSS 署名 Sig, メッセージ M, XMSS 公開鍵 PK を入力として取る. Huelsing, et al. Informational [Page 31] RFC 8391 XMSS May 2018 XMSS_verify は, Sig が 公開鍵 PK のもとで M の有効な署名の場合にのみ true を返す. そうでなければ, false を返す. Algorithm 14: XMSS_verify - 対応する XMSS 公開鍵とメッセージを用いて XMSS 署名を検証 入力: XMSS 署名 Sig, メッセージ M, XMSS 公開鍵 PK. 出力: Boolean ADRS = toByte(0, 32); byte[n] M' = H_msg(r || getRoot(PK) || (toByte(idx_sig, n)), M); byte[n] node = XMSS_rootFromSig(idx_sig, sig_ots, auth, M', getSEED(PK), ADRS); if ( node == getRoot(PK) ) { return true; } else { return false; } 4.1.11. 疑似乱数鍵生成 実装は, 単一の n バイトの値から XMSS 秘密鍵を生成するのに暗号学的に安全な疑似乱数法を用いてもよい. たとえば, [BDH11] で提案された方法や後述する方法が利用されてもよい. [HRS16] のうちの 1 つのような他の方法が利用されてもよい. 疑似乱数法の選択は相互運用性に影響しないが, 暗号学的な強度は利用される XMSS パラメーターのそれと一致しなければならない. XMSS では, WOTS+ でのものと似た方法が利用できる. [BDH11] で提案された方法は, PRF を用いて記述できる. 鍵生成の間に, 一様乱数な n バイト文字列 S が安全な乱数源から抽出される. このシード S は公開のシード SEED と混同してはならない. シード S は SEED 独立でなければらならない. これは主要な秘密で, 秘密を保たなければならないからだ. このシード S は それぞれの WOTS+ 鍵ペアのための n バイト値 S_ots を生成するのに利用される. そして n バイト値 S_opts は, 3.1.7 節で記述された方法を用いて それぞれの WOTS+ 秘密鍵を計算するのに使われる. WOTS+ 鍵ペアのシードは, S_ots[i] = PRF(S, toByte(i, 32)) のように計算される. ここで, i は WOTS+ 鍵ペアのインデックス. この方法の利点は, S が与えられた場合に PRF の len + 1 の評価のみを用いち WOTS+ 鍵が計算できることだ. Huelsing, et al. Informational [Page 32] RFC 8391 XMSS May 2018 4.1.12. フリーインデックスの扱いと部分秘密鍵 いくつかのアプリケーションは, 部分秘密鍵や秘密鍵のコピーと共に動作する必要があるかもしれない. 例として, ロードバランシングや, 署名権の移譲, 署名のプロキシがある. これらのアプリケーションは, それら自身の鍵形式を用いてもよいし, 前述したものとは異なる署名アルゴリズムを用いてもよい. 部分秘密鍵や秘密鍵のコピーのインデックスは, アプリケーションの必要に応じて操作されてよい. しかし, アプリケーションは, それぞれのインデックス, つまりそれぞれの WOTS+ 鍵ペアが, 単一のメッセージのみの署名に用いられることを保証する手順を確立しなければならない. 4.2. XMSS^MT: Multi-Tree XMSS XMSS^MT はたくさんのしかし固定された数のメッセージに署名するための方法だ. 最初に [HRB13] で記述された. XMSS を元にしている. XMSS^MT は XMSS 木のいくつかの層の木, いわゆる hypertree を用いる. 一番上と中間の層にある木は, それぞれの下の層の木の root ノードを署名するのに用いられる. 最下層の木は実際のメッセージの署名に用いられる. すべての XMSS 木は等しい高さを持つ. 木の高さが h / d の d 層の XMSS 木を持つ全体の高さが h である XMSS^MT 木を考える. そして, d - 1 層は 1 つの XMSS 木を含み, d - 2 層は 2^(h / d) の XMSS 木を含む. 最後に layer 0 は 2^(h - h / d) の XMSS 木を含む. 4.2.1. XMSS^MT のパラメーター すべての XMSS パラメーターに加えて, XMSS^MT システムは, h を割り切れる整数である木の層の数 d を必要とする. 同じ木の高さ h / d と同じ Winternitz パラメーター w がすべての木の層に用いられる. より高い層のすべての木は, 他の木の root ノードの署名をする. root ノードは n バイトの文字列だ. それゆえ, メッセージの圧縮は必要ではなく, WOTS+ はハッシュ値ではなく root ノード自身を署名するのに用いられる. 4.2.2. XMSS^MT 鍵生成 XMSS^MT の秘密鍵 SK_MT (S は secret の S) は, それぞれの XMSS 木ごとに 1 つの切りつめた XMSS 秘密鍵から構成される. これらの切りつめた XMSS 秘密鍵は, その XMSS 鍵ペアに関連する WOTS+ 秘密鍵のみを含む. 疑似乱数関数鍵やインデックス公開のシードや root ノードを含まない. 代わりに, SK_MT は 単一の n バイト疑似乱数関数鍵 SK_PRF, 単一の (ceil(h / 8))バイトインデックス idx_MT, 単一の n バイトシード SEED, 単一の root 値 root (一番上の層の単一の木の root) を含む. Huelsing, et al. Informational [Page 33] RFC 8391 XMSS May 2018 インデックスは, 0 層のすべての XMSS 木のすべての WOTS+ 鍵ペアに対する包括的なインデックスだ. 0 から開始される. 最下層にある最後に利用した WOTS+ 鍵ペアのインデックスを保持する. 0 から 2^h -1 の間の数となる. 切り詰められた XMSS 鍵は, 4.1.3 節で記述されたように生成されるか 4.2.5 節で議論する暗号学的疑似乱数法を用いて生成されなければならない. XMSS のように, PRF 鍵 SK_PRF は 一様分布に従う安全な乱数源から抽出されなければならない. SEED は一様乱数な n バイト文字列として生成される. SEED は公開の値だが, よいエントロピー源から生成されるのがセキュリティにとって重要だ. root は最上層の単一の XMSS 木の root ノードだ. その計算法は後で説明する. XMSSのように, root と SEED は公開情報で, 古典的には公開鍵の一部とみなされる. しかし, 両者は署名に必要で, 署名操作は秘密鍵のみを取るので, SK_MT の一部でもある. この文書は XMSS^MT 秘密鍵 SK_MT の特定の形式を定義しない. 相互運用性にとって必要ないからだ. アルゴリズム 15 と 16 は getXMSS_SK(SK, x, y) を用いる. これは, y 番目の層の x 番目の XMSS 木の切りつめた秘密鍵を出力する. XMSS^MT 公開鍵 PK_MT は, d -1 層の単一の XMSS 木の root とシード SEED を含む. これらは 秘密鍵 SK_MT の中にあるものと同じ値だ. SEED を鍵とする疑似乱数関数 PRF はすべての XMSS 木の bitmask と鍵を生成するのに利用される. XMSSMT_keyGen (Algorithm 15) は, SK_MT と PK_MT を生成する疑似コードの例を示す. 最上層の木の n バイトの root ノードは, treeHash を用いて計算される. アルゴリズム XMSSMT_keyGen は XMSS^MT 秘密鍵 SK_MT と XMSS^MT 公開鍵 PK_MT を出力する. 後出のアルゴリズムはどのように切りつめた XMSS 秘密鍵が生成されるかを示す例を与える. しかし, 利用する方法の暗号学的強度が利用する XMSS^MT パラメーターセットと一致するか上まわる限り, 前述した方法のうちのどれでも許容される. Huelsing, et al. Informational [Page 34] RFC 8391 XMSS May 2018 Algorithm 15: XMSSMT_keyGen - XMSS^MT 鍵ペアの生成 入力: 入力なし. 出力: XMSS^MT 秘密鍵 SK_MT, XMSS^MT 公開鍵 PK_MT // Example initialization idx_MT = 0; setIdx(SK_MT, idx_MT); initialize SK_PRF with a uniformly random n-byte string; setSK_PRF(SK_MT, SK_PRF); initialize SEED with a uniformly random n-byte string; setSEED(SK_MT, SEED); // Generate reduced XMSS private keys ADRS = toByte(0, 32); for ( layer = 0; layer < d; layer++ ) { ADRS.setLayerAddress(layer); for ( tree = 0; tree < (1 << ((d - 1 - layer) * (h / d))); tree++ ) { ADRS.setTreeAddress(tree); for ( i = 0; i < 2^(h / d); i++ ) { wots_sk[i] = WOTS_genSK(); } setXMSS_SK(SK_MT, wots_sk, tree, layer); } } SK = getXMSS_SK(SK_MT, 0, d - 1); setSEED(SK, SEED); root = treeHash(SK, 0, h / d, ADRS); setRoot(SK_MT, root); PK_MT = OID || root || SEED; return (SK_MT || PK_MT); 前述したものは単なる例のアルゴリズムだ. 秘密鍵のサイズを削減するため疑似乱数鍵生成を用いることが強く推奨される. 公開鍵と秘密鍵の生成は, 空間の削減のためにインターリーブしてもよい. 特に, 秘密鍵の生成に疑似乱数法を用いる場合, それぞれの WOTS+ 鍵ペアが別のアルゴリズムによって必要となる時まで生成が遅らされてもよい.I Huelsing, et al. Informational [Page 35] RFC 8391 XMSS May 2018 XMSS^MT 公開鍵の形式は次のように与えられる. +---------------------------------+ | algorithm OID | +---------------------------------+ | | | root node | n bytes | | +---------------------------------+ | | | SEED | n bytes | | +---------------------------------+ XMSS^MT 公開鍵 4.2.3. XMSS^MT 署名 XMSS^MT 署名 Sig_MT は 長さ (ceil(h / 8) + n + (h + d * len) * n) のバイト文字列だ. 次の要素で構成される: o 最下層の利用した WOTS+ 鍵ペアのインデックス idx_sig (ceil(h / 8) バイト), o 乱数化されたメッセージハッシュ化のために利用したバイト文字列 r (n バイト), o 切りつめた XMSS 署名 ( それぞれ (h / d + len) * n バイト). 切りつめた XMSS 署名は, WOTS+ 署名 sig_ots と認証パス auth のみを含む. インデックス idx とバイト文字列 r は含まない. Huelsing, et al. Informational [Page 36] RFC 8391 XMSS May 2018 署名のデータ形式は次で与えられる. +---------------------------------+ | | | index idx_sig | ceil(h / 8) bytes | | +---------------------------------+ | | | randomness r | n bytes | | +---------------------------------+ | | | (reduced) XMSS signature Sig | (h / d + len) * n bytes | (bottom layer 0) | | | +---------------------------------+ | | | (reduced) XMSS signature Sig | (h / d + len) * n bytes | (layer 1) | | | +---------------------------------+ | | ~ .... ~ | | +---------------------------------+ | | | (reduced) XMSS signature Sig | (h / d + len) * n bytes | (layer d - 1) | | | +---------------------------------+ XMSS^MT 署名 4.2.4. XMSS^MT 署名の生成 XMSS^MT 秘密鍵 SK_MT を用いてメッセージ M に対する XMSS^MT 署名 Sig_MT の計算するために, 後述の XMSSMT_sign (Algorithm 16) は 4.1.9 節で定義した treeSig を用いる. まず, 署名のインデックスが idx_sig に設定される. 次に 疑似乱数 n バイト文字列 r の計算に PRF が用いられる. この n バイトの文字列と idx_sig, PK_MT の root ノードが乱数化された長さ n のメッセージダイジェストの計算に用いられる. 最下層の絶対インデックス idx の WOTS+ 鍵ペアを用いて, メッセージダイジェストが署名される. WOTS+ 鍵ペアの認証パスと XMSS 木の root が計算される. root は親の XMSS 木によって署名される. 最上層の木に届くまで, これが繰替えされる. Huelsing, et al. Informational [Page 37] RFC 8391 XMSS May 2018 Algorithm 16: XMSSMT_sign - XMSS^MT 署名の生成と XMSS^MT 秘密鍵の更新 入力: メッセージ M, XMSS^MT 秘密鍵 SK_MT. 出力: 更新された SK_MT, 署名 Sig_MT // Init ADRS = toByte(0, 32); SEED = getSEED(SK_MT); SK_PRF = getSK_PRF(SK_MT); idx_sig = getIdx(SK_MT); // Update SK_MT setIdx(SK_MT, idx_sig + 1); // Message compression byte[n] r = PRF(SK_PRF, toByte(idx_sig, 32)); byte[n] M' = H_msg(r || getRoot(SK_MT) || (toByte(idx_sig, n)), M); // Sign Sig_MT = idx_sig; unsigned int idx_tree = (h - h / d) most significant bits of idx_sig; unsigned int idx_leaf = (h / d) least significant bits of idx_sig; SK = idx_leaf || getXMSS_SK(SK_MT, idx_tree, 0) || SK_PRF || toByte(0, n) || SEED; ADRS.setLayerAddress(0); ADRS.setTreeAddress(idx_tree); Sig_tmp = treeSig(M', SK, idx_leaf, ADRS); Sig_MT = Sig_MT || r || Sig_tmp; for ( j = 1; j < d; j++ ) { root = treeHash(SK, 0, h / d, ADRS); idx_leaf = (h / d) least significant bits of idx_tree; idx_tree = (h - j * (h / d)) most significant bits of idx_tree; SK = idx_leaf || getXMSS_SK(SK_MT, idx_tree, j) || SK_PRF || toByte(0, n) || SEED; ADRS.setLayerAddress(j); ADRS.setTreeAddress(idx_tree); Sig_tmp = treeSig(root, SK, idx_leaf, ADRS); Sig_MT = Sig_MT || Sig_tmp; } return SK_MT || Sig_MT; Huelsing, et al. Informational [Page 38] RFC 8391 XMSS May 2018 Algorithm 16 は XMSS^MT 署名を計算する唯一の方法だ. 木の高さ h /d の XMSS スキームの署名の時間よりも署名の時間を短かくできる, 時間-メモリのトレードオフが存在する. これらのトレードオフは, 1) 状態を保持することで特定の値が何度も再計算されるのを防ぎ 2) すべての署名生成に対してすべての計算を分散する. 詳細は [Huelsing13a] に見られる. 4.2.5. XMSS^MT 署名の検証 XMSS^MT 署名の検証 (Algorithm 17) は, 小さな変更がある XMSS 署名検証としてまとめることができる. まず, メッセージがハッシュ化される. 複数のXMSS 署名はすべて n バイトの値だ. 次に, 与えられた値の計算された root ノードを比較するのではなく, この root ノードの署名が検証される. 最上位の木の root ノードのみが XMSS^MT の公開鍵の値と比較される. XMSSMT_verify は XMSS_rootFromSig を用いる. 関数 getXMSSSignature(Sig_MT, i) は, XMSS^MT 署名 Sig_MT から i 番目の切りつめた XMSS 署名を返す. XMSSMT_verify は入力として XMSS^MT 署名 Sig_MT とメッセージ M, 公開鍵 PK_MT を取る. XMSSMT_verify は, Sig_MT が 公開鍵 PK_MT の下で M の正当な署名の場合にのみ true を返す. そうでなければ, false を返す. Algorithm 17: XMSSMT_verify - XMSS^MT 公開鍵 PK_MT を用いて メッセージ M の XMSS^MT 署名 Sig_MT を検証 入力: XMSS^MT 署名 Sig_MT, メッセージ M, XMSS^MT 公開鍵 PK_MT. 出力: Boolean idx_sig = getIdx(Sig_MT); SEED = getSEED(PK_MT); ADRS = toByte(0, 32); byte[n] M' = H_msg(getR(Sig_MT) || getRoot(PK_MT) || (toByte(idx_sig, n)), M); unsigned int idx_leaf = (h / d) least significant bits of idx_sig; unsigned int idx_tree = (h - h / d) most significant bits of idx_sig; Sig' = getXMSSSignature(Sig_MT, 0); ADRS.setLayerAddress(0); ADRS.setTreeAddress(idx_tree); byte[n] node = XMSS_rootFromSig(idx_leaf, getSig_ots(Sig'), getAuth(Sig'), M', SEED, ADRS); Huelsing, et al. Informational [Page 39] RFC 8391 XMSS May 2018 for ( j = 1; j < d; j++ ) { idx_leaf = (h / d) least significant bits of idx_tree; idx_tree = (h - j * h / d) most significant bits of idx_tree; Sig' = getXMSSSignature(Sig_MT, j); ADRS.setLayerAddress(j); ADRS.setTreeAddress(idx_tree); node = XMSS_rootFromSig(idx_leaf, getSig_ots(Sig'), getAuth(Sig'), node, SEED, ADRS); } if ( node == getRoot(PK_MT) ) { return true; } else { return false; } 4.2.6. 疑似乱数鍵生成 XMSS のように, 実装は, 単一の n バイトの値から XMSS^MT 秘密鍵を生成するのに暗号学的に安全な疑似乱数法を用いてもよい. たとえば, 後述する方法が利用されてもよい. [HRS16] のうちの 1 つのような他の方法が利用されてもよい. 疑似乱数法の選択は相互運用性に影響しないが, 暗号学的な強度は利用される XMSS^MT パラメーターのそれと一致しなければならない. XMSS^MT では, XMSS や WOTS+ でのものと似た方法が利用できる. この方法は PRF を用いる. 鍵生成の間, 一様な乱数な n バイト文字列 S_MT は 安全な乱数源から抽出される. このシード S_MT は それぞれの XMSS 鍵ペアのための n バイト値 S を生成するのに利用される. そしてこの n バイト値は, 4.1.11 節で記述された方法を用いて それぞれの XMSS 秘密鍵を計算するのに使われる. S[x][y] は層 y の x 番目の XMSS 秘密鍵のシードとする. シードは次のように計算される: S[x][y] = PRF(PRF(S, toByte(y, 32)), toByte(x, 32)). 4.2.7. フリーインデックスの扱いと部分秘密鍵 4.1.12 節の内容が XMSS^MT にも適用される. 5. パラメーターセット この節は多くの関連するアプリケーションをカバーするであろう基本のパラメーターセットを提供する. 2 つの古典的なセキュリティレベルに対するパラメーターセットが定義される. n = 32 のパラメーターは, 256 ビットの古典的なセキュリティレベルを提供する. n = 64 のパラメーターは, 512 ビットの古典的なセキュリティレベルを提供する. 量子コンピュータの補助付きの攻撃を考慮すると, これらの出力のサイズはそれぞれ 128 ビットと 256 ビットの ポスト量子のセキュリティを実現する. Huelsing, et al. Informational [Page 40] RFC 8391 XMSS May 2018 この文書はいくつかのパラメーターセットを指定するが, 実装はすべての要求されているパラメーターセットの検証のサポートを提供することだけが要求されている. 要求されているパラメーターセットはすべて, すべての関数のインスタンス化に SHA2-256 を利用する. 要求されているパラメーターセットは, 木の高さのパラメーター h (単一の鍵ペアで可能な署名の数を決定する) と 層の数 d (速度と署名のサイズのトレードオフを定義する) によってのみ区別される. 実装は, 提案されたパラメーターセットのいずれかを用いる署名の生成のサポートを提供してもよい. 簡便のため, この文書は XMSS (XMSS_SHA2_20_256) と XMSS^MT (XMSSMT-SHA2_60/3_256) を デフォルトの選択肢として定義する. これらは多くの一般的な要求に一致するだろう. 5.1. 関数の実装 n = 32 の設定に対して, [FIPS180] で定義された SHA2-256 を用いるパラメーターと [FIPS202] で定義された SHA3/Keccak ベースの拡張可能な出力関数 SHAKE-128 を用いるパラメーターを与える. n = 64 の設定に対して, [FIPS180] で定義された SHA2-512 を用いるパラメーターと [FIPS202] で定義された SHA3/Keccak ベースの拡張可能な出力関数 SHAKE-256 を用いるパラメーターを与える. SHA2-256 を用いるパラメーターセットは, 配置を義務づけられていて, あらゆる実装で提供されなければならない. この文書で指定される残りのパラメーターセットは選択できる. SHA2 はそれ自身では鍵付きのモードを提供しない. 鍵付きのハッシュ関数を実装するため, n =32 での SHA2 のために次が用いられる. F: SHA2-256(toByte(0, 32) || KEY || M), H: SHA2-256(toByte(1, 32) || KEY || M), H_msg: SHA2-256(toByte(2, 32) || KEY || M), PRF: SHA2-256(toByte(3, 32) || KEY || M). これに応じて, n = 64 での SHA2 に対して次を用いる: F: SHA2-512(toByte(0, 64) || KEY || M), H: SHA2-512(toByte(1, 64) || KEY || M), H_msg: SHA2-512(toByte(2, 64) || KEY || M), PRF: SHA2-512(toByte(3, 64) || KEY || M). Huelsing, et al. Informational [Page 41] RFC 8391 XMSS May 2018 n バイトのパディングが 2 つの理由で利用される. 1 つ目は, 内部の圧縮関数が 2n バイトのブロックを取るが, 鍵は n と 3n のバイト長なので必要となる.First, it is necessary that the internal compression function takes 2n-byte blocks, but keys are n and 3n bytes long. 2つ目は, 異なる関数ファミリーの独立を達成するためにパディングが用いられる. 最後に, PRF に対して, メッセージ長が固定されていて, 標準的な length extension 攻撃はここでは考慮しなくてよいので, 本格的な Hash-Based Message Authentication Code (HMAC) は必要とされない. これらの理由から, 前述のより簡単な構成で十分だ. SHA3 に対しても同様の構成が用いられる. 鍵付きのハッシュ関数の実装のため, n= 32 の SHA3 に対して次が用いられる. F: SHAKE128(toByte(0, 32) || KEY || M, 256), H: SHAKE128(toByte(1, 32) || KEY || M, 256), H_msg: SHAKE128(toByte(2, 32) || KEY || M, 256), PRF: SHAKE128(toByte(3, 32) || KEY || M, 256). これに応じて, n = 64 での SHA3 に対して次を用いる: F: SHAKE256(toByte(0, 64) || KEY || M, 512), H: SHAKE256(toByte(1, 64) || KEY || M, 512), H_msg: SHAKE256(toByte(2, 64) || KEY || M, 512), PRF: SHAKE256(toByte(3, 64) || KEY || M, 512). SHA 2 のように, 最初の n バイトの識別子が, 異なる関数ファミリーの独立を達成するために用いられる. SHA3 の場合より短い識別子を利用できるが, SHA2 での実装との一貫性のため n バイトを用いる. Huelsing, et al. Informational [Page 42] RFC 8391 XMSS May 2018 5.2. WOTS+ のパラメーター WOTS+ 署名法を完全に記述するために, 関数 F と PRF, パラメーター n とw が指定されなければならない. 次のテーブルでいくつかの WOTS+ 署名システムを定義する. それぞれは名前で識別される. 命名は次の規則に従う: WOTSP-[Hashfamily]_[n in bits]. この文書のすべてのパラメーターセットは w=16 を用いるので, 命名には w を含んでいない. len の値を便利のために提供する. +-----------------+----------+----+----+-----+ | Name | F / PRF | n | w | len | +-----------------+----------+----+----+-----+ | REQUIRED: | | | | | | | | | | | | WOTSP-SHA2_256 | SHA2-256 | 32 | 16 | 67 | | | | | | | | OPTIONAL: | | | | | | | | | | | | WOTSP-SHA2_512 | SHA2-512 | 64 | 16 | 131 | | | | | | | | WOTSP-SHAKE_256 | SHAKE128 | 32 | 16 | 67 | | | | | | | | WOTSP-SHAKE_512 | SHAKE256 | 64 | 16 | 131 | +-----------------+----------+----+----+-----+ Table 1 単一の関数の実装は前述されているように行なわれる. WOTS+ の External Data Representation (XDR) 形式は Appendix A に列挙されている. 5.3. XMSS のパラメーター XMSS 署名法を完全に記述するために, 関数 F, H, H_msg, PRF とパラメー=タ n, w, h が指定されなければならない. 次のテーブルで異なる XMSS 署名システムを定義する. それぞれは名前で識別される. 命名は次の規則に従う: XMSS-[Hashfamily]_[h]_[n in bits]. この文書のすべてのパラメーターセットは w=16 を用いるので, 命名には w を含んでいない. Huelsing, et al. Informational [Page 43] RFC 8391 XMSS May 2018 +-------------------+-----------+----+----+-----+----+ | Name | Functions | n | w | len | h | +-------------------+-----------+----+----+-----+----+ | REQUIRED: | | | | | | | | | | | | | | XMSS-SHA2_10_256 | SHA2-256 | 32 | 16 | 67 | 10 | | | | | | | | | XMSS-SHA2_16_256 | SHA2-256 | 32 | 16 | 67 | 16 | | | | | | | | | XMSS-SHA2_20_256 | SHA2-256 | 32 | 16 | 67 | 20 | | | | | | | | | OPTIONAL: | | | | | | | | | | | | | | XMSS-SHA2_10_512 | SHA2-512 | 64 | 16 | 131 | 10 | | | | | | | | | XMSS-SHA2_16_512 | SHA2-512 | 64 | 16 | 131 | 16 | | | | | | | | | XMSS-SHA2_20_512 | SHA2-512 | 64 | 16 | 131 | 20 | | | | | | | | | XMSS-SHAKE_10_256 | SHAKE128 | 32 | 16 | 67 | 10 | | | | | | | | | XMSS-SHAKE_16_256 | SHAKE128 | 32 | 16 | 67 | 16 | | | | | | | | | XMSS-SHAKE_20_256 | SHAKE128 | 32 | 16 | 67 | 20 | | | | | | | | | XMSS-SHAKE_10_512 | SHAKE256 | 64 | 16 | 131 | 10 | | | | | | | | | XMSS-SHAKE_16_512 | SHAKE256 | 64 | 16 | 131 | 16 | | | | | | | | | XMSS-SHAKE_20_512 | SHAKE256 | 64 | 16 | 131 | 20 | +-------------------+-----------+----+----+-----+----+ Table 2 XMSS の XDR 形式は Appendix B に列挙されている. 5.3.1. パラメーターのガイド RSA や Digital Signature Algorithm (DSA) のような伝統的な署名スキームとは対照的に, XMSS は 1 つの鍵ペアで署名が可能なメッセージ数を決定する木の高さのパラメーター h を持つ. 高さを増すことで 1 つの鍵ペアをより多くの署名に利用できるが, 署名のサイズが増し, 鍵の生成や署名, 検証の速度が遅くなる. h の異なる値の影響を説明するため, 次のテーブルで署名のサイズと実行時間を示す. 最悪の場合に認証パスを計算するために BDS アルゴリズムが使われた場合の F と H の呼び出し回数で, 実行時間は与えられる. Huelsing, et al. Informational [Page 44] RFC 8391 XMSS May 2018 the worst case. 最後の列は, 1 つの鍵ペアで署名可能なメッセージ数を示す. 同じパラメーター h と n での XMSS-SHAKE インスタンヅでも同じ値となる. +------------------+-------+------------+--------+--------+-------+ | Name | |Sig| | KeyGen | Sign | Verify | #Sigs | +------------------+-------+------------+--------+--------+-------+ | REQUIRED: | | | | | | | | | | | | | | XMSS-SHA2_10_256 | 2,500 | 1,238,016 | 5,725 | 1,149 | 2^10 | | | | | | | | | XMSS-SHA2_16_256 | 2,692 | 79*10^6 | 9,163 | 1,155 | 2^16 | | | | | | | | | XMSS-SHA2_20_256 | 2,820 | 1,268*10^6 | 11,455 | 1,159 | 2^20 | | | | | | | | | OPTIONAL: | | | | | | | | | | | | | | XMSS-SHA2_10_512 | 9,092 | 2,417,664 | 11,165 | 2,237 | 2^10 | | | | | | | | | XMSS-SHA2_16_512 | 9,476 | 155*10^6 | 17,867 | 2,243 | 2^16 | | | | | | | | | XMSS-SHA2_20_512 | 9,732 | 2,476*10^6 | 22,335 | 2,247 | 2^20 | +------------------+-------+------------+--------+--------+-------+ Table 3 デフォルトでは, 特別な要件がないユーザは XMSS-SHA2_20_256 を用いるべきだ. 1 つの鍵ペアで 2^20 のメッセージの署名が可能で, 手頃な速度と署名のサイズを提供する. 鍵ペアごとによりたくさんの署名を必要としたりより高速な鍵生成が必要なユーザは, XMSS^MT を考慮すべきだ. 5.4. XMSS^MT のパラメーター XMSS^MT 署名法を完全に記述するために, 関数 F, H, H_msg, PRF とパラメーター n, w, h, d が指定されなければならない. 次のテーブルで異なる XMSS^MT 署名システムを定義する. それぞれは名前で識別される. 命名は次の規則に従う: XMSSMT-[Hashfamily]_[h]/[d]_[n in bits]. この文書のすべてのパラメーターセットは w=16 を用いるので, 命名には w を含んでいない. Huelsing, et al. Informational [Page 45] RFC 8391 XMSS May 2018 +------------------------+-----------+----+----+-----+----+----+ | Name | Functions | n | w | len | h | d | +------------------------+-----------+----+----+-----+----+----+ | REQUIRED: | | | | | | | | | | | | | | | | XMSSMT-SHA2_20/2_256 | SHA2-256 | 32 | 16 | 67 | 20 | 2 | | | | | | | | | | XMSSMT-SHA2_20/4_256 | SHA2-256 | 32 | 16 | 67 | 20 | 4 | | | | | | | | | | XMSSMT-SHA2_40/2_256 | SHA2-256 | 32 | 16 | 67 | 40 | 2 | | | | | | | | | | XMSSMT-SHA2_40/4_256 | SHA2-256 | 32 | 16 | 67 | 40 | 4 | | | | | | | | | | XMSSMT-SHA2_40/8_256 | SHA2-256 | 32 | 16 | 67 | 40 | 8 | | | | | | | | | | XMSSMT-SHA2_60/3_256 | SHA2-256 | 32 | 16 | 67 | 60 | 3 | | | | | | | | | | XMSSMT-SHA2_60/6_256 | SHA2-256 | 32 | 16 | 67 | 60 | 6 | | | | | | | | | | XMSSMT-SHA2_60/12_256 | SHA2-256 | 32 | 16 | 67 | 60 | 12 | | | | | | | | | | OPTIONAL: | | | | | | | | | | | | | | | | XMSSMT-SHA2_20/2_512 | SHA2-512 | 64 | 16 | 131 | 20 | 2 | | | | | | | | | | XMSSMT-SHA2_20/4_512 | SHA2-512 | 64 | 16 | 131 | 20 | 4 | | | | | | | | | | XMSSMT-SHA2_40/2_512 | SHA2-512 | 64 | 16 | 131 | 40 | 2 | | | | | | | | | | XMSSMT-SHA2_40/4_512 | SHA2-512 | 64 | 16 | 131 | 40 | 4 | | | | | | | | | | XMSSMT-SHA2_40/8_512 | SHA2-512 | 64 | 16 | 131 | 40 | 8 | | | | | | | | | | XMSSMT-SHA2_60/3_512 | SHA2-512 | 64 | 16 | 131 | 60 | 3 | | | | | | | | | | XMSSMT-SHA2_60/6_512 | SHA2-512 | 64 | 16 | 131 | 60 | 6 | | | | | | | | | | XMSSMT-SHA2_60/12_512 | SHA2-512 | 64 | 16 | 131 | 60 | 12 | | | | | | | | | | XMSSMT-SHAKE_20/2_256 | SHAKE128 | 32 | 16 | 67 | 20 | 2 | | | | | | | | | | XMSSMT-SHAKE_20/4_256 | SHAKE128 | 32 | 16 | 67 | 20 | 4 | | | | | | | | | | XMSSMT-SHAKE_40/2_256 | SHAKE128 | 32 | 16 | 67 | 40 | 2 | | | | | | | | | | XMSSMT-SHAKE_40/4_256 | SHAKE128 | 32 | 16 | 67 | 40 | 4 | | | | | | | | | | XMSSMT-SHAKE_40/8_256 | SHAKE128 | 32 | 16 | 67 | 40 | 8 | Huelsing, et al. Informational [Page 46] RFC 8391 XMSS May 2018 | | | | | | | | | XMSSMT-SHAKE_60/3_256 | SHAKE128 | 32 | 16 | 67 | 60 | 3 | | | | | | | | | | XMSSMT-SHAKE_60/6_256 | SHAKE128 | 32 | 16 | 67 | 60 | 6 | | | | | | | | | | XMSSMT-SHAKE_60/12_256 | SHAKE128 | 32 | 16 | 67 | 60 | 12 | | | | | | | | | | XMSSMT-SHAKE_20/2_512 | SHAKE256 | 64 | 16 | 131 | 20 | 2 | | | | | | | | | | XMSSMT-SHAKE_20/4_512 | SHAKE256 | 64 | 16 | 131 | 20 | 4 | | | | | | | | | | XMSSMT-SHAKE_40/2_512 | SHAKE256 | 64 | 16 | 131 | 40 | 2 | | | | | | | | | | XMSSMT-SHAKE_40/4_512 | SHAKE256 | 64 | 16 | 131 | 40 | 4 | | | | | | | | | | XMSSMT-SHAKE_40/8_512 | SHAKE256 | 64 | 16 | 131 | 40 | 8 | | | | | | | | | | XMSSMT-SHAKE_60/3_512 | SHAKE256 | 64 | 16 | 131 | 60 | 3 | | | | | | | | | | XMSSMT-SHAKE_60/6_512 | SHAKE256 | 64 | 16 | 131 | 60 | 6 | | | | | | | | | | XMSSMT-SHAKE_60/12_512 | SHAKE256 | 64 | 16 | 131 | 60 | 12 | +------------------------+-----------+----+----+-----+----+----+ Table 4 XMSS^MT の XDR 形式は Appendix C に列挙されている. 5.4.1. パラメーターのガイド XMSS ですでに用いられた木の高さのパラメーターに加えて, XMSS^MT は木の層の数を決定するパラメーター d を持つ. XMSS は単一の層 すなわち d=1 の XMSS^MT と解釈できる. それゆえ, h の選択は XMSS と同様の影響がある. 木の層の数は, 一方では署名のサイズ, 他方では鍵の生成と署名のスピードの間のトレードオフを提供する. 層の数を増すと, 署名のサイズが線形に増すのと引き換えに, 鍵の生成の時間は指数関数的に減り署名の時間は線形に減る. 本質的に, XMSS^MT 署名は 層ごとに 1 つの WOTSP 署名を含む. 速度は, 木の高さ h/d のXMSS の速度のおよそ d 倍に相当する. h と d の異なる値の影響を説明するために, 次の表で署名のサイズと実行時間を示す. BDS アルゴリズムと分散した署名の生成が用いられた場合の F と H の呼び出し回数で, 実行時間は与えられる. タイミングは最悪の場合の時間だ. 最後の列は, 1 つの鍵ペアで署名可能なメッセージ数を示す. 同じパラメーター h と n での XMSS-SHAKE インスタンスでも同じ値となる. Huelsing, et al. Informational [Page 47] RFC 8391 XMSS May 2018 SHAKE instances with same parameters h and n. 整形の制限のために, "XMSSMT" を省いてパラメーターセットの名前のパラメーター部分のみを与える. +----------------+---------+------------+--------+--------+-------+ | Name | |Sig| | KeyGen | Sign | Verify | #Sigs | +----------------+---------+------------+--------+--------+-------+ | REQUIRED: | | | | | | | | | | | | | | SHA2_20/2_256 | 4,963 | 2,476,032 | 7,227 | 2,298 | 2^20 | | | | | | | | | SHA2_20/4_256 | 9,251 | 154,752 | 4,170 | 4,576 | 2^20 | | | | | | | | | SHA2_40/2_256 | 5,605 | 2,535*10^6 | 13,417 | 2,318 | 2^40 | | | | | | | | | SHA2_40/4_256 | 9,893 | 4,952,064 | 7,227 | 4,596 | 2^40 | | | | | | | | | SHA2_40/8_256 | 18,469 | 309,504 | 4,170 | 9,152 | 2^40 | | | | | | | | | SHA2_60/3_256 | 8,392 | 3,803*10^6 | 13,417 | 3,477 | 2^60 | | | | | | | | | SHA2_60/6_256 | 14,824 | 7,428,096 | 7,227 | 6,894 | 2^60 | | | | | | | | | SHA2_60/12_256 | 27,688 | 464,256 | 4,170 | 13,728 | 2^60 | | | | | | | | | OPTIONAL: | | | | | | | | | | | | | | SHA2_20/2_512 | 18,115 | 4,835,328 | 14,075 | 4,474 | 2^20 | | | | | | | | | SHA2_20/4_512 | 34,883 | 302,208 | 8,138 | 8,928 | 2^20 | | | | | | | | | SHA2_40/2_512 | 19,397 | 4,951*10^6 | 26,025 | 4,494 | 2^40 | | | | | | | | | SHA2_40/4_512 | 36,165 | 9,670,656 | 14,075 | 8,948 | 2^40 | | | | | | | | | SHA2_40/8_512 | 69,701 | 604,416 | 8,138 | 17,856 | 2^40 | | | | | | | | | SHA2_60/3_512 | 29,064 | 7,427*10^6 | 26,025 | 6,741 | 2^60 | | | | | | | | | SHA2_60/6_512 | 54,216 | 14,505,984 | 14,075 | 13,422 | 2^60 | | | | | | | | | SHA2_60/12_512 | 104,520 | 906,624 | 8,138 | 26,784 | 2^60 | +----------------+---------+------------+--------+--------+-------+ Table 5 Huelsing, et al. Informational [Page 48] RFC 8391 XMSS May 2018 デフォルトでは, 特別な要件がないユーザは XMSSMT-SHA2_60/3_256 を用いるべきだ. 1 つの鍵ペアで 2^60 のメッセージの署名が可能だ (実質的に署名の数の制限はない). 同時に, 署名のサイズと速度がよくバランスされている. 6. 原理 このノートの目的は, 科学文献に基づいて WOTS+ と XMSS, XMSS^MT アルゴリズムを記述することだ. この記述は, SPHINCS [BHH15] のような状態なしハッシュベース署名アルゴリズムの記述に基づけるようにモジュール化されている. このノートは, H_msg に対するマルチユーザとマルチターゲットの攻撃を防ぐ調整を用いている点で科学文献からすこし逸脱している. この目的のために, 利用した一時鍵ペアのインデックスと公開鍵は, ハッシュ関数の鍵の一部となっている. これにより, 攻撃者にどのハッシュ値を攻撃させるかのドメイン分離を達成する. 乱数化されたメッセージハッシュに用いる乱数の生成のため, メッセージの代わりに利用された一時鍵ペアのインデックスに対して, 秘密の値で鍵付きとなる, PRF を適用する. 2 回ではなく 1 度だけメッセージを処理する必要があるのがこの理由です. 長いメッセージに対して, これは速度を改善し, ストレージに全メッセージを保持できないリソースに制限のあるデバイスでの実装を単純化する. SHA2-256 を用いる必須のパラメーターセットを1つ与える. 理由は 2 つある. 1 つは, SHA2-256 は主要な暗号ライブラリの一部だ. もう 1 つは, 256 ビットのハッシュ関数は, 量子コンピュータの助けをえる攻撃に対してさえ 128 ビットのセキュリティを影響するパラメーターを導く. 256 ビットの量子後のセキュリティレベルは, 保守的すぎるように思える. しかし, 暗号分析の進歩の可能性に備えて, より広くはサポートされていない SHA2-512 と SHAKE-246, SHAKE-512 関数を用いる選択できるパラメーターセットも提供する. Winternitz のパラメーターとして w = 16 の値を推奨する. 署名のサイズの減少度が減っていくので, より大きな値は含んでいない. さらに, w = 16 は, アルゴリズムのいくつかの実装をかなり単純化する. w = 4 を許容しているが, 効率の理由で指定されたパラメーターセットを w = 16 に限定しているのに注意してほしい. Huelsing, et al. Informational [Page 49] RFC 8391 XMSS May 2018 署名と公開鍵の形式は, パースしやすいように設計されている. どちらの形式も, 署名アルゴリズムの詳細のすべてを示す 32 ビットの列挙値で始まり, よって, 形式をパースするのに必要なすべての情報が定義されている. 7. リファレンスコード テストのために, C によるリファレンス実装が利用できる. コードには, この文書の疑似コードに忠実に従う基本的な実装と XMSS^MT のための [HRB13] に記述されているような認証パスと分散化された署名生成を計算するために BDS アルゴリズム [BDS08] を用いる最適化された実装が含まれている. コードは, でいつまでも利用できる. 8. IANA の考慮 Internet Assigned Numbers Authority (IANA) は 3 つのレジストリを作成した: 1 つは (3 節で定義された) WOTS+ 署名のため, 1つは (4 節で定義された) XMSS 署名のため, もう1つは (4 節で定義された) XMSS^MT 署名のためのものだ. 明確さと簡便さのため, WOTS+ と XMSS, XMSS^MT のパラメーターセットの最初の集合は 5 節で定義されている. これらのレジストリへの追加は, 独立した実装間での相互運用性を可能とするために, [RFC8126] で記述された "Specification Required" ポリシーで定義されているような十分に詳細な, RFC ないし永続的かつ容易に利用可能なリファレンスで仕様が文書化されている必要がある. これらのレジストリのそれぞれのエントリは次の要素を含む. o "XMSS_SHA2_20_256" のような短縮名, o 正の番号, o 署名のテストケースを完全に定義する, ないし, 実装の正確さを検証するのに用いられるリファレンス実装 (もしくはそのような実装へのリファレンス) を提供する仕様へのリファレンス. これらのレジストリへのエントリの追加の要求は, 名前とリファレンスを含まなければならない. 番号は IANA によって割り当てられる. これらの番号の割り当ては, 利用可能な最小の正の番号が使われる必要がある. 投稿者はその要求をレビューし承認してもらわなければならない. Internet Engineering Steering Group (IESG) によって, このタスクのために指定された専門家が [RFC8126] で定義された "Specification Required" ポリシーにより要求される. Huelsing, et al. Informational [Page 50] RFC 8391 XMSS May 2018 Internet Engineering Steering Group (IESG). IESG は iesg@ietf.org で接触できる. IANA のプロセスに慣れていない興味がある応募者は, を訪問するべきだ. 番号 0x00000000 (10 進で 0) は予約されている. 0xDDDDDDDD (10 進で 3,722,304,989) と 0xFFFFFFFF (10 進で 4,294,967,295) の間 (境界を含む) の番号は, IANA によって割り当てられず, 私的な利用のために予約されている. 複数のサイトが同じ値を異なる(非互換な)方法によって用いるのを防ぐ試みは行なわれない [RFC8126]. "WOTS+ Signatures" レジストリは次の通り. +--------------------+-----------------+-------------+ | Numeric Identifier | Name | Reference | +--------------------+-----------------+-------------+ | 0x00000000 | Reserved | this RFC | | | | | | 0x00000001 | WOTSP-SHA2_256 | Section 5.2 | | | | | | 0x00000002 | WOTSP-SHA2_512 | Section 5.2 | | | | | | 0x00000003 | WOTSP-SHAKE_256 | Section 5.2 | | | | | | 0x00000004 | WOTSP-SHAKE_512 | Section 5.2 | +--------------------+-----------------+-------------+ Table 6 Huelsing, et al. Informational [Page 51] RFC 8391 XMSS May 2018 "XMSS Signatures" レジストリは次の通り. +--------------------+-------------------+-------------+ | Numeric Identifier | Name | Reference | +--------------------+-------------------+-------------+ | 0x00000000 | Reserved | this RFC | | | | | | 0x00000001 | XMSS-SHA2_10_256 | Section 5.3 | | | | | | 0x00000002 | XMSS-SHA2_16_256 | Section 5.3 | | | | | | 0x00000003 | XMSS-SHA2_20_256 | Section 5.3 | | | | | | 0x00000004 | XMSS-SHA2_10_512 | Section 5.3 | | | | | | 0x00000005 | XMSS-SHA2_16_512 | Section 5.3 | | | | | | 0x00000006 | XMSS-SHA2_20_512 | Section 5.3 | | | | | | 0x00000007 | XMSS-SHAKE_10_256 | Section 5.3 | | | | | | 0x00000008 | XMSS-SHAKE_16_256 | Section 5.3 | | | | | | 0x00000009 | XMSS-SHAKE_20_256 | Section 5.3 | | | | | | 0x0000000A | XMSS-SHAKE_10_512 | Section 5.3 | | | | | | 0x0000000B | XMSS-SHAKE_16_512 | Section 5.3 | | | | | | 0x0000000C | XMSS-SHAKE_20_512 | Section 5.3 | +--------------------+-------------------+-------------+ Table 7 Huelsing, et al. Informational [Page 52] RFC 8391 XMSS May 201 "XMSS^MT Signatures" レジストリは次の通り. +--------------------+------------------------+-------------+ | Numeric Identifier | Name | Reference | +--------------------+------------------------+-------------+ | 0x00000000 | Reserved | this RFC | | | | | | 0x00000001 | XMSSMT-SHA2_20/2_256 | Section 5.4 | | | | | | 0x00000002 | XMSSMT-SHA2_20/4_256 | Section 5.4 | | | | | | 0x00000003 | XMSSMT-SHA2_40/2_256 | Section 5.4 | | | | | | 0x00000004 | XMSSMT-SHA2_40/4_256 | Section 5.4 | | | | | | 0x00000005 | XMSSMT-SHA2_40/8_256 | Section 5.4 | | | | | | 0x00000006 | XMSSMT-SHA2_60/3_256 | Section 5.4 | | | | | | 0x00000007 | XMSSMT-SHA2_60/6_256 | Section 5.4 | | | | | | 0x00000008 | XMSSMT-SHA2_60/12_256 | Section 5.4 | | | | | | 0x00000009 | XMSSMT-SHA2_20/2_512 | Section 5.4 | | | | | | 0x0000000A | XMSSMT-SHA2_20/4_512 | Section 5.4 | | | | | | 0x0000000B | XMSSMT-SHA2_40/2_512 | Section 5.4 | | | | | | 0x0000000C | XMSSMT-SHA2_40/4_512 | Section 5.4 | | | | | | 0x0000000D | XMSSMT-SHA2_40/8_512 | Section 5.4 | | | | | | 0x0000000E | XMSSMT-SHA2_60/3_512 | Section 5.4 | | | | | | 0x0000000F | XMSSMT-SHA2_60/6_512 | Section 5.4 | | | | | | 0x00000010 | XMSSMT-SHA2_60/12_512 | Section 5.4 | | | | | | 0x00000011 | XMSSMT-SHAKE_20/2_256 | Section 5.4 | | | | | | 0x00000012 | XMSSMT-SHAKE_20/4_256 | Section 5.4 | | | | | | 0x00000013 | XMSSMT-SHAKE_40/2_256 | Section 5.4 | | | | | | 0x00000014 | XMSSMT-SHAKE_40/4_256 | Section 5.4 | | | | | | 0x00000015 | XMSSMT-SHAKE_40/8_256 | Section 5.4 | Huelsing, et al. Informational [Page 53] RFC 8391 XMSS May 2018 | | | | | 0x00000016 | XMSSMT-SHAKE_60/3_256 | Section 5.4 | | | | | | 0x00000017 | XMSSMT-SHAKE_60/6_256 | Section 5.4 | | | | | | 0x00000018 | XMSSMT-SHAKE_60/12_256 | Section 5.4 | | | | | | 0x00000019 | XMSSMT-SHAKE_20/2_512 | Section 5.4 | | | | | | 0x0000001A | XMSSMT-SHAKE_20/4_512 | Section 5.4 | | | | | | 0x0000001B | XMSSMT-SHAKE_40/2_512 | Section 5.4 | | | | | | 0x0000001C | XMSSMT-SHAKE_40/4_512 | Section 5.4 | | | | | | 0x0000001D | XMSSMT-SHAKE_40/8_512 | Section 5.4 | | | | | | 0x0000001E | XMSSMT-SHAKE_60/3_512 | Section 5.4 | | | | | | 0x0000001F | XMSSMT-SHAKE_60/6_512 | Section 5.4 | | | | | | 0x00000020 | XMSSMT-SHAKE_60/12_512 | Section 5.4 | +--------------------+------------------------+-------------+ Table 8 署名システムの IANA 登録は, そのシステム自体やそのセキュリティの保証を構成しない. 9. セキュリティの考察 正当な署名を攻撃者が偽造するのを防止できれば, 署名システムは安全だと考えられる. より具体的に, 攻撃者が公開鍵を得て選択した任意のメッセージに対する署名を学習できる場合を考える. この設定であっても, 検証アルゴリズムが受付けるような攻撃者が選択した新しいメッセージ/署名のペアを生成できなければ, 署名システムは安全だ. 攻撃者が攻撃するのを防ぐというのは, 攻撃するのが計算的に高価すぎるという意味だ. 計算が高価かの見積りにはいろいろある. このため, このノートでは, 攻撃者が偽造するのがどれくらい高価かのみを示す. パラメーターにはビットセキュリティ値が付く. ビットセキュリティの意味は次の通り. 裁量の攻撃が 1/2 の確立で成功するのに少なくとも 2^(b -1) ビットの操作がかかる場合, パラメーターセットは b ビットのセキュリティを保証する. Huelsing, et al. Informational [Page 54] RFC 8391 XMSS May 2018 1/2. すなわち, 攻撃を成功させるには攻撃者は平均で 2^b ビットの操作が必要となる. ビットセキュリティの与えられた値は, [HRS16] に従い推定された. 9.1. セキュリティの証明 この文書で記述されたすべてのスキームの完全なセキュリティの証明は [HRS16] にある. この証明は, 記述されたスキームのいずれにおいても署名を偽造するのに, 利用されているハッシュ関数とPRFの特定のセキュリティの特性のうちの少なくとも 1 つを破らなければいけないことを示す. [HRS16] での証明は, ここで用いているランダム化されたハッシュとは異なる最初のメッセージ圧縮を考慮している. この点については後述する. 元々のスキームでは, これらの証明は, 攻撃者が特定の最小限のセキュリティ特性を破らなければいけないことを示す. 特に, ハッシュ関数の衝突耐性を破っても偽造するのに充分ではない. より具体的には, 利用される関数に対する要件は, F と H はポスト量子でマルチ関数マルチターゲットで第 2 原像耐性のある鍵付き関数で, F はおおまかにいってほとんどの像が少なくとも 2 つの原像を持つ追加の統計的要件を満し, PRF はポスト量子疑似乱数関数で, H_msg はポスト量子マルチターゲット拡張ターゲット衝突耐性鍵付きハッシュ関数であるそれぞれの特性の詳細な定義は [HRS16] を参照してほしい. いくつかの直観を与えるために: マルチ関数マルチターゲットで第 2 原像耐性とは, 鍵付きハッシュ関数の第 2 原像耐性の拡張で, 多くの値のうちの 1 つの値に対して 2 番目の原像を攻撃者が見つけるのに成功する場合をカバーしている. マルチターゲット拡張ターゲット衝突耐性も同様で, ターゲット衝突耐性はすでに鍵付きハッシュ関数を考慮しているので, マルチ関数識別子を欠いている. [HRS16] の証明は PRF を 2 つの関数に分割する. PRF は 疑似乱数鍵生成やランダム化されたメッセージのハッシュのための乱数の生成に使われた場合でも, 疑似乱数関数とみなされる. PRF がビッドマスクやハッシュ関数の鍵を生成するのに使われる場合はいつでも, ランダムオラクルとしてモデル化される. これは証明での技術的な理 由のためで, 疑似乱数関数を用いる実装は安全だ. [HRS16] の証明は最初のメッセージ圧縮のための古典的なランダム化されたハッシュ化を考慮している. すなわち, H(r || getRoot(PK) || index, M) の代わりに H(r, M), . この古典的なランダム化されたハッシュは, 衝突抵抗よりも厳密により弱いと推測される性質である拡張ターゲット衝突耐性からセキュリティの低下を招く [HRS16]. しかし, この場合攻撃者は同時に複数のユーザに対してマルチターゲット攻撃を行なうことができるのが判明している. この理由は, u ユーザを同時に攻撃する攻撃者は, u * 2^h のランダム化されたハッシュ H(r_i_j || M_i_j) を学習するからだ. ここで 署名のインデックス i は [0, 2^h-1] の範囲でユーザのインデックス j は [0, u] だ. Huelsing, et al. Informational [Page 55] RFC 8391 XMSS May 2018 randomized hashes H(r_i_j || M_i_j) with signature index i in [0, 2^h - 1] and user index j in [0, u]. 学習した u * 2^h のハッシュに対してH(r* || M*) = H(r_i_u || M_i_u) となるような 1 組を見つければ十分だ. したがって, 攻撃者は 2^n ではなく 2^n / u * 2^h の時間でブルートフォース検索を行なえる. この作業で利用されるインデックス化ランダム化されたハッシュ H(r || getRoot(PK) || toByte(idx, n), M) はハッシュの関数の呼び出しを位置とユーザ依存とする. これは前述の攻撃を妨害する. 攻撃の間のそれぞれのハッシュ関数の評価は, 学習した乱数化されたハッシュ値の 1つのみを対象とするからだ. より具体的には, 攻撃者はそれぞれのクエリに対して用いるインデックス idx と root 値を決定しなければらならなくなる. 利用するハッシュ関数がランダムな関数だと仮定すると, このメッセージ圧縮を対象とするマルチユーザの存在による偽造攻撃は, 2^n のハッシュ関数呼び出しの複雑性を持つ. 与えられたビットセキュリティの値は, 伝統的な攻撃者と量子攻撃者を仮定して, 利用されているハッシュ関数の要求されるセキュリティの性質に対してもっともよく知られている一般的な攻撃の複雑さを元に推定された. 執筆時点で, 古典的な設定で提案されているパラメーターに対するもっとももよく知られている攻撃は一般的な攻撃だ. さらに, 量子の設定では, 一般的な攻撃よりも優れた専用の攻撃は知られていない. それでも, ハッシュ関数の量子暗号解析のトピックは, 古典的な設定ほどよく理解されていない. 9.2. 最低限のセキュリティの仮定 記述されたスキームのセキュリティを証明するために必要な仮定は, 次の意味で最低限だ. 任意のサイズのメッセージを許す署名アルゴリズムはすべて, 暗号学的ハッシュ関数のセキュリティ, 衝突耐性ないしランダム化されたハッシュがメッセージの圧縮に利用されるならば拡張ターゲット衝突耐性のどちらかに依存する. ここで記述されたスキームに対しては, これはすでに十分に安全だ. これに対して, RSA や DSA, 楕円曲線DSA (ECDSA) のような一般的な署名スキームは, 特定の数学的問題の推測される困難さに依存する. 9.3. 量子後のセキュリティ 量子後の暗号システムは, 合理的なサイズの量子コンピュータにアクセスできる攻撃者に対して安全なシステムだ. このノートの執筆時点では, このようなマシンを作成可能かどうかは未解決の問題だ. しかし, この領域で最近数年で重大な進歩がなされた. それゆえ, この場合に準備をすることはリスク評価の問題と考える. Huelsing, et al. Informational [Page 56] RFC 8391 XMSS May 2018 RSA や DSA, ECDSA とは違い, 記述された署名システムは, 適切な暗号学的ハッシュ関数を用いているなら, 量子後も安全だ. 特に, 量子後のセキュリティに対して, n のサイズは古典的なセキュリティに必要なサイズの倍でなければならない. これは, Grover のアルゴリズムによる量子平方根攻撃から保護するためだ. [HRS16] は, Grover のアルゴリズムの変種が, 記述されたスキームに対して必要とされるハッシュ関数のセキュリティの特性に対する最適な一般的な攻撃であることを示している. 前述したように, ここでは一般的な攻撃のみを考慮している. 暗号学的ハッシュ関数は, かなり良い性能の専用の攻撃が存在するようになったらすぐ廃止する必要がある. これは, 量子の設定でも適用される. 利用するハッシュ関数に対する記述した一般的な攻撃よりもかなり良い性能の専用の攻撃が存在するようになったらすぐ, これらのハッシュ関数は記述されたスキームでこれ以上利用されなくなるか, セキュリティレベルの計算のやり直しが必要となる. 10. References 10.1. Normative References [FIPS180] National Institute of Standards and Technology, "Secure Hash Standard (SHS)", FIPS PUB 180-4, DOI 10.6028/NIST.FIPS.180-4, August 2015. [FIPS202] National Institute of Standards and Technology, "SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions", FIPS PUB 202, DOI 10.6028/NIST.FIPS.202, August 2015. [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, . [RFC4506] Eisler, M., Ed., "XDR: External Data Representation Standard", STD 67, RFC 4506, DOI 10.17487/RFC4506, May 2006, . [RFC8126] Cotton, M., Leiba, B., and T. Narten, "Guidelines for Writing an IANA Considerations Section in RFCs", BCP 26, RFC 8126, DOI 10.17487/RFC8126, June 2017, . Huelsing, et al. Informational [Page 57] RFC 8391 XMSS May 2018 [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, May 2017, . 10.2. Informative References [BDH11] Buchmann, J., Dahmen, E., and A. Huelsing, "XMSS - A Practical Forward Secure Signature Scheme Based on Minimal Security Assumptions", Lecture Notes in Computer Science, Volume 7071, Post-Quantum Cryptography, DOI 10.1007/978-3-642-25405-5_8, 2011. [BDS08] Buchmann, J., Dahmen, E., and M. Schneider, "Merkle Tree Traversal Revisited", Lecture Notes in Computer Science, Volume 5299, Post-Quantum Cryptography, DOI 10.1007/978-3-540-88403-3_5, 2008. [BDS09] Buchmann, J., Dahmen, E., and M. Szydlo, "Hash-based Digital Signature Schemes", Book chapter, Post-Quantum Cryptography, DOI 10.1007/978-3-540-88702-7_3, 2009. [BHH15] Bernstein, D., Hopwood, D., Huelsing, A., Lange, T., Niederhagen, R., Papachristodoulou, L., Schneider, M., Schwabe, P., and Z. Wilcox-O'Hearn, "SPHINCS: Practical Stateless Hash-Based Signatures", Lecture Notes in Computer Science, Volume 9056, Advances in Cryptology - EUROCRYPT, DOI 10.1007/978-3-662-46800-5_15, 2015. [HRB13] Huelsing, A., Rausch, L., and J. Buchmann, "Optimal Parameters for XMSS^MT", Lecture Notes in Computer Science, Volume 8128, CD-ARES, DOI 10.1007/978-3-642-40588-4_14, 2013. [HRS16] Huelsing, A., Rijneveld, J., and F. Song, "Mitigating Multi-Target Attacks in Hash-based Signatures", Lecture Notes in Computer Science, Volume 9614, Public-Key Cryptography - PKC, DOI 10.1007/978-3-662-49384-7_15, 2016. [Huelsing13] Huelsing, A., "W-OTS+ - Shorter Signatures for Hash-Based Signature Schemes", Lecture Notes in Computer Science, Volume 7918, Progress in Cryptology - AFRICACRYPT, DOI 10.1007/978-3-642-38553-7_10, 2013. Huelsing, et al. Informational [Page 58] RFC 8391 XMSS May 2018 [Huelsing13a] Huelsing, A., "Practical Forward Secure Signatures using Minimal Security Assumptions", PhD thesis TU Darmstadt, 2013, . [KMN14] Knecht, M., Meier, W., and C. Nicola, "A space- and time- efficient Implementation of the Merkle Tree Traversal Algorithm", Computing Research Repository (CoRR), arXiv:1409.4081, 2014. [MCF18] McGrew, D., Curcio, M., and S. Fluhrer, "Hash-Based Signatures", Work in Progress, draft-mcgrew-hash-sigs-11, April 2018. [Merkle83] Merkle, R., "Secrecy, Authentication, and Public Key Systems", Computer Science Series, UMI Research Press, ISBN: 9780835713849, 1983. Huelsing, et al. Informational [Page 59] RFC 8391 XMSS May 2018 Appendix A. WOTS+ XDR Formats The WOTS+ signature and public key formats are formally defined using XDR [RFC4506] in order to provide an unambiguous, machine readable definition. Though XDR is used, these formats are simple and easy to parse without any special tools. Note that this representation includes all optional parameter sets. The same applies for the XMSS and XMSS^MT formats below. A.1. WOTS+ Parameter Sets WOTS+ parameter sets are defined using XDR syntax as follows: /* ots_algorithm_type identifies a particular signature algorithm */ enum ots_algorithm_type { wotsp_reserved = 0x00000000, wotsp-sha2_256 = 0x00000001, wotsp-sha2_512 = 0x00000002, wotsp-shake_256 = 0x00000003, wotsp-shake_512 = 0x00000004, }; A.2. WOTS+ Signatures WOTS+ signatures are defined using XDR syntax as follows: /* Byte strings */ typedef opaque bytestring32[32]; typedef opaque bytestring64[64]; union ots_signature switch (ots_algorithm_type type) { case wotsp-sha2_256: case wotsp-shake_256: bytestring32 ots_sig_n32_len67[67]; case wotsp-sha2_512: case wotsp-shake_512: bytestring64 ots_sig_n64_len18[131]; default: void; /* error condition */ }; Huelsing, et al. Informational [Page 60] RFC 8391 XMSS May 2018 A.3. WOTS+ Public Keys WOTS+ public keys are defined using XDR syntax as follows: union ots_pubkey switch (ots_algorithm_type type) { case wotsp-sha2_256: case wotsp-shake_256: bytestring32 ots_pubk_n32_len67[67]; case wotsp-sha2_512: case wotsp-shake_512: bytestring64 ots_pubk_n64_len18[131]; default: void; /* error condition */ }; Appendix B. XMSS XDR Formats B.1. XMSS Parameter Sets XMSS parameter sets are defined using XDR syntax as follows: /* Byte strings */ typedef opaque bytestring4[4]; /* Definition of parameter sets */ enum xmss_algorithm_type { xmss_reserved = 0x00000000, /* 256 bit classical security, 128 bit post-quantum security */ xmss-sha2_10_256 = 0x00000001, xmss-sha2_16_256 = 0x00000002, xmss-sha2_20_256 = 0x00000003, /* 512 bit classical security, 256 bit post-quantum security */ xmss-sha2_10_512 = 0x00000004, xmss-sha2_16_512 = 0x00000005, xmss-sha2_20_512 = 0x00000006, Huelsing, et al. Informational [Page 61] RFC 8391 XMSS May 2018 /* 256 bit classical security, 128 bit post-quantum security */ xmss-shake_10_256 = 0x00000007, xmss-shake_16_256 = 0x00000008, xmss-shake_20_256 = 0x00000009, /* 512 bit classical security, 256 bit post-quantum security */ xmss-shake_10_512 = 0x0000000A, xmss-shake_16_512 = 0x0000000B, xmss-shake_20_512 = 0x0000000C, }; B.2. XMSS Signatures XMSS signatures are defined using XDR syntax as follows: /* Authentication path types */ union xmss_path switch (xmss_algorithm_type type) { case xmss-sha2_10_256: case xmss-shake_10_256: bytestring32 path_n32_t10[10]; case xmss-sha2_16_256: case xmss-shake_16_256: bytestring32 path_n32_t16[16]; case xmss-sha2_20_256: case xmss-shake_20_256: bytestring32 path_n32_t20[20]; case xmss-sha2_10_512: case xmss-shake_10_512: bytestring64 path_n64_t10[10]; case xmss-sha2_16_512: case xmss-shake_16_512: bytestring64 path_n64_t16[16]; case xmss-sha2_20_512: case xmss-shake_20_512: bytestring64 path_n64_t20[20]; default: void; /* error condition */ }; Huelsing, et al. Informational [Page 62] RFC 8391 XMSS May 2018 /* Types for XMSS random strings */ union random_string_xmss switch (xmss_algorithm_type type) { case xmss-sha2_10_256: case xmss-sha2_16_256: case xmss-sha2_20_256: case xmss-shake_10_256: case xmss-shake_16_256: case xmss-shake_20_256: bytestring32 rand_n32; case xmss-sha2_10_512: case xmss-sha2_16_512: case xmss-sha2_20_512: case xmss-shake_10_512: case xmss-shake_16_512: case xmss-shake_20_512: bytestring64 rand_n64; default: void; /* error condition */ }; /* Corresponding WOTS+ type for given XMSS type */ union xmss_ots_signature switch (xmss_algorithm_type type) { case xmss-sha2_10_256: case xmss-sha2_16_256: case xmss-sha2_20_256: wotsp-sha2_256; case xmss-sha2_10_512: case xmss-sha2_16_512: case xmss-sha2_20_512: wotsp-sha2_512; case xmss-shake_10_256: case xmss-shake_16_256: case xmss-shake_20_256: wotsp-shake_256; case xmss-shake_10_512: case xmss-shake_16_512: case xmss-shake_20_512: wotsp-shake_512; Huelsing, et al. Informational [Page 63] RFC 8391 XMSS May 2018 default: void; /* error condition */ }; /* XMSS signature structure */ struct xmss_signature { /* WOTS+ key pair index */ bytestring4 idx_sig; /* Random string for randomized hashing */ random_string_xmss rand_string; /* WOTS+ signature */ xmss_ots_signature sig_ots; /* authentication path */ xmss_path nodes; }; B.3. XMSS Public Keys XMSS public keys are defined using XDR syntax as follows: /* Types for bitmask seed */ union seed switch (xmss_algorithm_type type) { case xmss-sha2_10_256: case xmss-sha2_16_256: case xmss-sha2_20_256: case xmss-shake_10_256: case xmss-shake_16_256: case xmss-shake_20_256: bytestring32 seed_n32; case xmss-sha2_10_512: case xmss-sha2_16_512: case xmss-sha2_20_512: case xmss-shake_10_512: case xmss-shake_16_512: case xmss-shake_20_512: bytestring64 seed_n64; default: void; /* error condition */ }; Huelsing, et al. Informational [Page 64] RFC 8391 XMSS May 2018 /* Types for XMSS root node */ union xmss_root switch (xmss_algorithm_type type) { case xmss-sha2_10_256: case xmss-sha2_16_256: case xmss-sha2_20_256: case xmss-shake_10_256: case xmss-shake_16_256: case xmss-shake_20_256: bytestring32 root_n32; case xmss-sha2_10_512: case xmss-sha2_16_512: case xmss-sha2_20_512: case xmss-shake_10_512: case xmss-shake_16_512: case xmss-shake_20_512: bytestring64 root_n64; default: void; /* error condition */ }; /* XMSS public key structure */ struct xmss_public_key { xmss_root root; /* Root node */ seed SEED; /* Seed for bitmasks */ }; Appendix C. XMSS^MT XDR Formats C.1. XMSS^MT Parameter Sets XMSS^MT parameter sets are defined using XDR syntax as follows: /* Byte strings */ typedef opaque bytestring3[3]; typedef opaque bytestring5[5]; typedef opaque bytestring8[8]; /* Definition of parameter sets */ enum xmssmt_algorithm_type { xmssmt_reserved = 0x00000000, Huelsing, et al. Informational [Page 65] RFC 8391 XMSS May 2018 /* 256 bit classical security, 128 bit post-quantum security */ xmssmt-sha2_20/2_256 = 0x00000001, xmssmt-sha2_20/4_256 = 0x00000002, xmssmt-sha2_40/2_256 = 0x00000003, xmssmt-sha2_40/4_256 = 0x00000004, xmssmt-sha2_40/8_256 = 0x00000005, xmssmt-sha2_60/3_256 = 0x00000006, xmssmt-sha2_60/6_256 = 0x00000007, xmssmt-sha2_60/12_256 = 0x00000008, /* 512 bit classical security, 256 bit post-quantum security */ xmssmt-sha2_20/2_512 = 0x00000009, xmssmt-sha2_20/4_512 = 0x0000000A, xmssmt-sha2_40/2_512 = 0x0000000B, xmssmt-sha2_40/4_512 = 0x0000000C, xmssmt-sha2_40/8_512 = 0x0000000D, xmssmt-sha2_60/3_512 = 0x0000000E, xmssmt-sha2_60/6_512 = 0x0000000F, xmssmt-sha2_60/12_512 = 0x00000010, /* 256 bit classical security, 128 bit post-quantum security */ xmssmt-shake_20/2_256 = 0x00000011, xmssmt-shake_20/4_256 = 0x00000012, xmssmt-shake_40/2_256 = 0x00000013, xmssmt-shake_40/4_256 = 0x00000014, xmssmt-shake_40/8_256 = 0x00000015, xmssmt-shake_60/3_256 = 0x00000016, xmssmt-shake_60/6_256 = 0x00000017, xmssmt-shake_60/12_256 = 0x00000018, /* 512 bit classical security, 256 bit post-quantum security */ xmssmt-shake_20/2_512 = 0x00000019, xmssmt-shake_20/4_512 = 0x0000001A, xmssmt-shake_40/2_512 = 0x0000001B, xmssmt-shake_40/4_512 = 0x0000001C, xmssmt-shake_40/8_512 = 0x0000001D, xmssmt-shake_60/3_512 = 0x0000001E, xmssmt-shake_60/6_512 = 0x0000001F, xmssmt-shake_60/12_512 = 0x00000020, }; Huelsing, et al. Informational [Page 66] RFC 8391 XMSS May 2018 C.2. XMSS^MT Signatures XMSS^MT signatures are defined using XDR syntax as follows: /* Type for XMSS^MT key pair index */ /* Depends solely on h */ union idx_sig_xmssmt switch (xmss_algorithm_type type) { case xmssmt-sha2_20/2_256: case xmssmt-sha2_20/4_256: case xmssmt-sha2_20/2_512: case xmssmt-sha2_20/4_512: case xmssmt-shake_20/2_256: case xmssmt-shake_20/4_256: case xmssmt-shake_20/2_512: case xmssmt-shake_20/4_512: bytestring3 idx3; case xmssmt-sha2_40/2_256: case xmssmt-sha2_40/4_256: case xmssmt-sha2_40/8_256: case xmssmt-sha2_40/2_512: case xmssmt-sha2_40/4_512: case xmssmt-sha2_40/8_512: case xmssmt-shake_40/2_256: case xmssmt-shake_40/4_256: case xmssmt-shake_40/8_256: case xmssmt-shake_40/2_512: case xmssmt-shake_40/4_512: case xmssmt-shake_40/8_512: bytestring5 idx5; case xmssmt-sha2_60/3_256: case xmssmt-sha2_60/6_256: case xmssmt-sha2_60/12_256: case xmssmt-sha2_60/3_512: case xmssmt-sha2_60/6_512: case xmssmt-sha2_60/12_512: case xmssmt-shake_60/3_256: case xmssmt-shake_60/6_256: case xmssmt-shake_60/12_256: case xmssmt-shake_60/3_512: case xmssmt-shake_60/6_512: case xmssmt-shake_60/12_512: bytestring8 idx8; Huelsing, et al. Informational [Page 67] RFC 8391 XMSS May 2018 default: void; /* error condition */ }; union random_string_xmssmt switch (xmssmt_algorithm_type type) { case xmssmt-sha2_20/2_256: case xmssmt-sha2_20/4_256: case xmssmt-sha2_40/2_256: case xmssmt-sha2_40/4_256: case xmssmt-sha2_40/8_256: case xmssmt-sha2_60/3_256: case xmssmt-sha2_60/6_256: case xmssmt-sha2_60/12_256: case xmssmt-shake_20/2_256: case xmssmt-shake_20/4_256: case xmssmt-shake_40/2_256: case xmssmt-shake_40/4_256: case xmssmt-shake_40/8_256: case xmssmt-shake_60/3_256: case xmssmt-shake_60/6_256: case xmssmt-shake_60/12_256: bytestring32 rand_n32; case xmssmt-sha2_20/2_512: case xmssmt-sha2_20/4_512: case xmssmt-sha2_40/2_512: case xmssmt-sha2_40/4_512: case xmssmt-sha2_40/8_512: case xmssmt-sha2_60/3_512: case xmssmt-sha2_60/6_512: case xmssmt-sha2_60/12_512: case xmssmt-shake_20/2_512: case xmssmt-shake_20/4_512: case xmssmt-shake_40/2_512: case xmssmt-shake_40/4_512: case xmssmt-shake_40/8_512: case xmssmt-shake_60/3_512: case xmssmt-shake_60/6_512: case xmssmt-shake_60/12_512: bytestring64 rand_n64; default: void; /* error condition */ }; /* Type for reduced XMSS signatures */ Huelsing, et al. Informational [Page 68] RFC 8391 XMSS May 2018 union xmss_reduced (xmss_algorithm_type type) { case xmssmt-sha2_20/2_256: case xmssmt-sha2_40/4_256: case xmssmt-sha2_60/6_256: case xmssmt-shake_20/2_256: case xmssmt-shake_40/4_256: case xmssmt-shake_60/6_256: bytestring32 xmss_reduced_n32_t77[77]; case xmssmt-sha2_20/4_256: case xmssmt-sha2_40/8_256: case xmssmt-sha2_60/12_256: case xmssmt-shake_20/4_256: case xmssmt-shake_40/8_256: case xmssmt-shake_60/12_256: bytestring32 xmss_reduced_n32_t72[72]; case xmssmt-sha2_40/2_256: case xmssmt-sha2_60/3_256: case xmssmt-shake_40/2_256: case xmssmt-shake_60/3_256: bytestring32 xmss_reduced_n32_t87[87]; case xmssmt-sha2_20/2_512: case xmssmt-sha2_40/4_512: case xmssmt-sha2_60/6_512: case xmssmt-shake_20/2_512: case xmssmt-shake_40/4_512: case xmssmt-shake_60/6_512: bytestring64 xmss_reduced_n32_t141[141]; case xmssmt-sha2_20/4_512: case xmssmt-sha2_40/8_512: case xmssmt-sha2_60/12_512: case xmssmt-shake_20/4_512: case xmssmt-shake_40/8_512: case xmssmt-shake_60/12_512: bytestring64 xmss_reduced_n32_t136[136]; case xmssmt-sha2_40/2_512: case xmssmt-sha2_60/3_512: case xmssmt-shake_40/2_512: case xmssmt-shake_60/3_512: bytestring64 xmss_reduced_n32_t151[151]; Huelsing, et al. Informational [Page 69] RFC 8391 XMSS May 2018 default: void; /* error condition */ }; /* xmss_reduced_array depends on d */ union xmss_reduced_array (xmss_algorithm_type type) { case xmssmt-sha2_20/2_256: case xmssmt-sha2_20/2_512: case xmssmt-sha2_40/2_256: case xmssmt-sha2_40/2_512: case xmssmt-shake_20/2_256: case xmssmt-shake_20/2_512: case xmssmt-shake_40/2_256: case xmssmt-shake_40/2_512: xmss_reduced xmss_red_arr_d2[2]; case xmssmt-sha2_60/3_256: case xmssmt-sha2_60/3_512: case xmssmt-shake_60/3_256: case xmssmt-shake_60/3_512: xmss_reduced xmss_red_arr_d3[3]; case xmssmt-sha2_20/4_256: case xmssmt-sha2_20/4_512: case xmssmt-sha2_40/4_256: case xmssmt-sha2_40/4_512: case xmssmt-shake_20/4_256: case xmssmt-shake_20/4_512: case xmssmt-shake_40/4_256: case xmssmt-shake_40/4_512: xmss_reduced xmss_red_arr_d4[4]; case xmssmt-sha2_60/6_256: case xmssmt-sha2_60/6_512: case xmssmt-shake_60/6_256: case xmssmt-shake_60/6_512: xmss_reduced xmss_red_arr_d6[6]; case xmssmt-sha2_40/8_256: case xmssmt-sha2_40/8_512: case xmssmt-shake_40/8_256: case xmssmt-shake_40/8_512: xmss_reduced xmss_red_arr_d8[8]; Huelsing, et al. Informational [Page 70] RFC 8391 XMSS May 2018 case xmssmt-sha2_60/12_256: case xmssmt-sha2_60/12_512: case xmssmt-shake_60/12_256: case xmssmt-shake_60/12_512: xmss_reduced xmss_red_arr_d12[12]; default: void; /* error condition */ }; /* XMSS^MT signature structure */ struct xmssmt_signature { /* WOTS+ key pair index */ idx_sig_xmssmt idx_sig; /* Random string for randomized hashing */ random_string_xmssmt randomness; /* Array of d reduced XMSS signatures */ xmss_reduced_array; }; C.3. XMSS^MT Public Keys XMSS^MT public keys are defined using XDR syntax as follows: /* Types for bitmask seed */ union seed switch (xmssmt_algorithm_type type) { case xmssmt-sha2_20/2_256: case xmssmt-sha2_40/4_256: case xmssmt-sha2_60/6_256: case xmssmt-sha2_20/4_256: case xmssmt-sha2_40/8_256: case xmssmt-sha2_60/12_256: case xmssmt-sha2_40/2_256: case xmssmt-sha2_60/3_256: case xmssmt-shake_20/2_256: case xmssmt-shake_40/4_256: case xmssmt-shake_60/6_256: case xmssmt-shake_20/4_256: case xmssmt-shake_40/8_256: case xmssmt-shake_60/12_256: case xmssmt-shake_40/2_256: case xmssmt-shake_60/3_256: bytestring32 seed_n32; Huelsing, et al. Informational [Page 71] RFC 8391 XMSS May 2018 case xmssmt-sha2_20/2_512: case xmssmt-sha2_40/4_512: case xmssmt-sha2_60/6_512: case xmssmt-sha2_20/4_512: case xmssmt-sha2_40/8_512: case xmssmt-sha2_60/12_512: case xmssmt-sha2_40/2_512: case xmssmt-sha2_60/3_512: case xmssmt-shake_20/2_512: case xmssmt-shake_40/4_512: case xmssmt-shake_60/6_512: case xmssmt-shake_20/4_512: case xmssmt-shake_40/8_512: case xmssmt-shake_60/12_512: case xmssmt-shake_40/2_512: case xmssmt-shake_60/3_512: bytestring64 seed_n64; default: void; /* error condition */ }; /* Types for XMSS^MT root node */ union xmssmt_root switch (xmssmt_algorithm_type type) { case xmssmt-sha2_20/2_256: case xmssmt-sha2_20/4_256: case xmssmt-sha2_40/2_256: case xmssmt-sha2_40/4_256: case xmssmt-sha2_40/8_256: case xmssmt-sha2_60/3_256: case xmssmt-sha2_60/6_256: case xmssmt-sha2_60/12_256: case xmssmt-shake_20/2_256: case xmssmt-shake_20/4_256: case xmssmt-shake_40/2_256: case xmssmt-shake_40/4_256: case xmssmt-shake_40/8_256: case xmssmt-shake_60/3_256: case xmssmt-shake_60/6_256: case xmssmt-shake_60/12_256: bytestring32 root_n32; case xmssmt-sha2_20/2_512: case xmssmt-sha2_20/4_512: case xmssmt-sha2_40/2_512: case xmssmt-sha2_40/4_512: case xmssmt-sha2_40/8_512: Huelsing, et al. Informational [Page 72] RFC 8391 XMSS May 2018 case xmssmt-sha2_60/3_512: case xmssmt-sha2_60/6_512: case xmssmt-sha2_60/12_512: case xmssmt-shake_20/2_512: case xmssmt-shake_20/4_512: case xmssmt-shake_40/2_512: case xmssmt-shake_40/4_512: case xmssmt-shake_40/8_512: case xmssmt-shake_60/3_512: case xmssmt-shake_60/6_512: case xmssmt-shake_60/12_512: bytestring64 root_n64; default: void; /* error condition */ }; /* XMSS^MT public key structure */ struct xmssmt_public_key { xmssmt_root root; /* Root node */ seed SEED; /* Seed for bitmasks */ }; 謝辞 We would like to thank Johannes Braun, Peter Campbell, Florian Caullery, Stephen Farrell, Scott Fluhrer, Burt Kaliski, Adam Langley, Marcos Manzano, David McGrew, Rafael Misoczki, Sean Parkinson, Sebastian Roland, and the Keccak team for their help and comments. Huelsing, et al. Informational [Page 73] RFC 8391 XMSS May 2018 Authors' Addresses Andreas Huelsing TU Eindhoven P.O. Box 513 Eindhoven 5600 MB The Netherlands Email: ietf@huelsing.net Denis Butin TU Darmstadt Hochschulstrasse 10 Darmstadt 64289 Germany Email: dbutin@cdc.informatik.tu-darmstadt.de Stefan-Lukas Gazdag genua GmbH Domagkstrasse 7 Kirchheim bei Muenchen 85551 Germany Email: ietf@gazdag.de Joost Rijneveld Radboud University Toernooiveld 212 Nijmegen 6525 EC The Netherlands Email: ietf@joostrijneveld.nl Aziz Mohaisen University of Central Florida 4000 Central Florida Blvd Orlando, FL 32816 United States of America Phone: +1 407 823-1294 Email: mohaisen@ieee.org Huelsing, et al. Informational [Page 74]