フォーマット保存暗号化

暗号化において、フォーマット保持暗号化( FPE ) とは、出力 (暗号文) が入力 (平文) と同じフォーマットになるように暗号化することを指します。「フォーマット」の意味はさまざまです。通常は、数字、アルファベット、英数字など、限られた文字セットのみが使用されます。例:

• 16 桁のクレジットカード番号を暗号化して、暗号文が別の 16 桁の数字になるようにします。
• 英語の単語を暗号化して、暗号文が別の英語の単語になるようにします。
• nビットの数値を暗号化して、暗号文が別のnビットの数値になるようにします(これがnビット ブロック暗号の定義です)。

このような有限領域の場合、および以下の説明の目的では、暗号はN個の整数{0, ... , N −1 } の順列と同等であり、Nは領域のサイズです。

FPE を使用する理由の 1 つは、明確に定義されたデータ モデルを持つ既存のアプリケーションに暗号化を統合する際に発生する問題です。典型的な例としては、(16 バイト長、数字のみ) などのクレジットカード番号1234567812345670が挙げられます。

データ モデルを変更する場合、このようなアプリケーションに暗号化を追加することは困難になる可能性があります。これは、通常、フィールドの長さの制限やデータ タイプの変更を伴うためです。たとえば、一般的なブロック暗号の出力では、クレジットカード番号が16 進数(例0x96a45cbcf9c2a9425cde9e274948cb67: 34 バイト、16 進数) またはBase64値 (例: 24 バイト、英数字と特殊文字)に変換されるためlqRcvPnCqUJc3p4nSUjLZw==、クレジットカード番号が 16 桁の数字であると想定している既存のアプリケーションは機能しなくなります。

単純なフォーマットの問題とは別に、AES-128-CBC を使用すると、このクレジットカード番号は 16 進数値に暗号化される可能性があります0xde015724b081ea7003de4593d792fd8b695b39e095c98f3a220ff43522a2df02。無効な文字の作成やデータ サイズの増加によって発生する問題に加えて、暗号化アルゴリズムの CBC モードを使用して暗号化されたデータは、復号化されて再度暗号化されたときに値も変わります。これは、暗号化アルゴリズムを初期化するために使用され、暗号化された値の一部として含まれるランダム シード値が、暗号化操作ごとに異なるために発生します。このため、CBC モードで暗号化されたデータを、データベース内の行を識別するための 一意のキーとして使用することはできません。

FPE は、元のデータのフォーマットと長さを保持することで移行プロセスを簡素化し、従来のアプリケーションでプレーンテキスト値を暗号テキストに簡単に置き換えることを可能にします。

真にランダムな順列は理想的な FPE 暗号ですが、大規模なドメインでは真にランダムな順列を事前に生成して記憶することは不可能です。したがって、FPE の問題は、単一の値の計算時間が短くなるように (理想的には一定ですが、最も重要なのはO(N)よりも短い) 秘密鍵から疑似ランダム順列を生成することです。

nビットのブロック暗号は、技術的にはセット{ 0, ..., 2 ⁿ -1 } 上の FPEです。これらの標準サイズのセットの 1 つで FPE が必要な場合は (たとえば、DESの場合はn = 64 、 AES の場合はn = 128)、適切なサイズのブロック暗号を使用できます。

ただし、一般的な使用法では、ブロック暗号は、任意の長さのメッセージを暗号化できる操作モードで使用され、前述の初期化ベクトルが使用されます。このモードでは、ブロック暗号は FPE ではありません。

暗号に関する文献 (以下の参考文献のほとんどを参照) では、「優れた」 FPE の基準は、攻撃者が FPE を真にランダムな順列と区別できるかどうかです。オラクルまたは既知の暗号文/平文のペアにアクセスできるかどうかに応じて、さまざまなタイプの攻撃者が想定されます。

ここで挙げたアプローチのほとんどでは、理想的なランダム関数の代わりに、よく知られたブロック暗号( AESなど) がプリミティブとして使用されています。これには、アルゴリズムに秘密鍵を簡単に組み込むことができるという利点があります。以下の説明で AES について言及していますが、他の優れたブロック暗号でも同様に機能します。

基礎となるブロック暗号のセキュリティと証明可能に関連するセキュリティを備えた FPE の実装は、暗号学者のJohn BlackとPhillip Rogawayによる論文^[1]で初めて試みられ、その 3 つの方法が説明されました。彼らは、これらの各手法が、それを構築するために使用されるブロック暗号と同じくらい安全であることを証明しました。つまり、AES アルゴリズムを使用して FPE アルゴリズムを作成すると、結果として得られる FPE アルゴリズムは AES と同じくらい安全です。これは、FPE アルゴリズムを破ることができる敵対者は AES アルゴリズムも破ることができるためです。したがって、AES が安全であれば、そこから構築された FPE アルゴリズムも安全です。以下のすべての文において、E はFPE アルゴリズムの構築に使用される AES 暗号化操作を示し、F はFPE 暗号化操作を示します。

{0, ..., N -1}で FPE アルゴリズムを作成する簡単な方法の 1 つは、各整数に疑似ランダムな重みを割り当て、重みで並べ替えることです。重みは、各整数に既存のブロック暗号を適用することによって定義されます。Black と Rogaway はこの手法を「プレフィックス暗号」と呼び、使用されるブロック暗号と同じくらい優れている可能性があることを示しました。

したがって、ドメイン{0,1,2,3}にFPEを作成するには、キーKが与えられた場合に各整数にAES( K )を適用し、たとえば次のようになります。

重み(0) = 0x56c644080098fc5570f2b329323dbf62
重み(1) = 0x08ee98c0d05e3dad3eb3d6236f23e7b7
重み(2) = 0x47d2e1bf72264fa01fb274465e56ba20
重み(3) = 0x077de40941c93774857961a8a772650d

[0,1,2,3]を重みでソートすると[3,1,2,0]となるので、暗号は

F (0) = 3
 F (1) = 1
 F (2) = 2
 F (3) = 0

この方法は、 Nの値が小さい場合にのみ有効です。値が大きい場合、ルックアップ テーブルのサイズとテーブルを初期化するために必要な暗号化の数が大きくなりすぎて実用的ではありません。

疑似乱数順列Pのドメイン内に許容値のセットMがある場合(たとえば、P はAES のようなブロック暗号である可能性があります)、結果が許容値のいずれか ( M内) になるまでブロック暗号を繰り返し適用することで、ブロック暗号から FPE アルゴリズムを作成できます。

CycleWalkingFPE(x) {
     P (x) がMの要素である場合 はP (x)
    を返し、そうでない場合はCycleWalkingFPE( P (x))を返します。 
         
        
}

再帰は必ず終了する。( Pは 1 対 1 であり、ドメインは有限であるため、Pを繰り返し適用するとサイクルが形成され、 M内の点から始めてサイクルは最終的にM内で終了する。)

これには、 Mの要素を整数の連続したシーケンス {0,..., N -1} にマッピングする必要がないという利点があります。MがPのドメインよりもはるかに小さい場合、各操作に非常に多くの反復が必要になる可能性があるという欠点があります。 P がAES などの固定サイズのブロック暗号である場合、これはこの方法が効率的な Mのサイズに対する厳しい制限となります。

たとえば、アプリケーションは、別の 100 ビット値を作成する方法で、AES を使用して 100 ビットの値を暗号化する場合があります。この手法では、AES-128-ECB 暗号化を、上位 28 ビットがすべて 0 に設定された値に達するまで適用できます。これには、平均 2 ²⁸回の反復が必要です。

Feistelネットワークを使用してFPEアルゴリズムを作成することも可能です。Feistelネットワークでは、各ラウンドのサブキーの疑似乱数ソースが必要であり、AESアルゴリズムの出力をこれらの疑似乱数として使用できます。これを行うと、十分なラウンドが使用される場合、結果として得られるFeistel構造は良好になります。^[2]

AES と Feistel ネットワークを使用して FPE アルゴリズムを実装する 1 つの方法は、Feistel ネットワークの左半分または右半分の長さに等しくなるのに必要な数の AES 出力ビットを使用することです。たとえば、サブキーとして 24 ビットの値が必要な場合は、この値に AES 出力の最下位 24 ビットを使用できます。

これにより、Feistel ネットワークの出力が入力の形式を維持するとは限りませんが、サイクル ウォーキング手法と同じ方法で Feistel ネットワークを反復処理して、形式が維持されるようにすることができます。 Feistel ネットワークへの入力のサイズを調整できるため、この反復処理が平均して非常に速く終了する可能性が非常に高くなります。 たとえば、クレジットカード番号の場合、16 桁のクレジットカード番号は 10 ^{15通りあり (冗長な}チェック ディジットを考慮)、 10 ¹⁵ ≈ 2 ^49.8であるため、50 ビット幅の Feistel ネットワークをサイクル ウォーキングとともに使用すると、平均してかなり速く暗号化する FPE アルゴリズムが作成されます。

ソープシャッフルは理想的なカードシャッフルのようなもので、片側が1ビットである最大限に不均衡なフェイステル暗号と同等である。不均衡なフェイステル暗号の方が、均衡なフェイステル暗号よりも安全性を証明するのが容易である。^[3]

ドメインサイズが2の累乗で、既存のブロック暗号のブロックサイズが小さい場合、Bellare、Rogawayによって説明されているVILモードを使用して新しい暗号を作成することができます。^[4]

Hasty Pudding Cipher は、カスタム構造 (プリミティブとして既存のブロック暗号に依存しない) を使用して、任意の有限の小さな領域を暗号化します。

NISTで検討対象として承認されたAESのFFSEMモード（仕様^[5]）は、前述のBlackとRogawayのFeistelネットワーク構造を使用し、ラウンド関数にはAESを使用していますが、1つのわずかな変更が加えられています。つまり、単一のキーが使用され、各ラウンドでわずかに調整されます。

2010年2月現在、FFSEMは、Mihir Bellare、Phillip Rogaway、Terence Spiesによって書かれたFFXモードに置き換えられました。（仕様、^{[6] [7]} NISTブロック暗号モード開発、2010）。

JPEG 2000標準では、マーカー コード (0xFF90 から 0xFFFF の範囲) はプレーンテキストと暗号文に出現してはなりません。単純なモジュラー 0xFF90 手法は、JPEG 2000 暗号化問題を解決するために適用できません。たとえば、暗号文のワード 0x23FF と 0x9832 は有効ですが、その組み合わせ 0x23FF9832 はマーカー コード 0xFF98 が導入されるため無効になります。同様に、単純なサイクル ウォーキング手法は、2 つの有効な暗号文ブロックが結合されると無効な暗号文になる可能性があるため、JPEG2000 暗号化問題を解決するために適用できません。たとえば、最初の暗号文ブロックがバイト "...30FF" で終了し、2 番目の暗号文ブロックがバイト "9832..." で始まる場合、マーカー コード "0xFF98" が暗号文に出現します。

Hongjun Wu と Di Ma による論文「JPEG2000 の効率的で安全な暗号化方式」^[8]では、JPEG 2000 のフォーマット保存暗号化の 2 つのメカニズムが紹介されています。JPEG 2000 のフォーマット保存暗号化を実行するには、暗号化と復号化でバイト「0xFF」を除外する手法を使用します。次に、JPEG 2000 暗号化メカニズムは、ストリーム暗号を使用してモジュロ n 加算を実行します。別の JPEG 2000 暗号化メカニズムは、ブロック暗号を使用してサイクル ウォーキング手法を実行します。

いくつかの FPE 構造は、標準暗号の出力を n を法として暗号化するデータに追加し、さまざまな方法で結果を偏りのないものにするというものです。多くの構造で共通する n を法とする加算は、FPE 問題に対する明らかな解決策であり (そのため、多くの場合に使用されます)、主な違いは使用される偏りのないメカニズムにあります。

FIPS 74、連邦情報処理標準出版物 1981 NBS データ暗号化標準の実装と使用に関するガイドラインのセクション 8 、^[9]では、モジュロ n 加算とそれに続くアンバイアス操作によってデータの形式を保持する方法で DES 暗号化アルゴリズムを使用する方法について説明しています。この標準は 2005 年 5 月 19 日に廃止されたため、この手法は正式な標準という点では時代遅れと見なす必要があります。

フォーマットを保持する暗号化のもう一つの初期のメカニズムは、ピーター・ガットマンの「制限された範囲の値を持つデータの暗号化」^[10]でした。これは、結果を均一にするためにいくつかの調整を加えた任意の暗号に対してモジュロn加算を実行し、結果として得られる暗号化は、それが基づいている基礎となる暗号化アルゴリズムと同じくらい強力になります。

Michael Brightwell と Harry Smith による論文「データ型保存暗号化を使用したデータ ウェアハウスのセキュリティ強化」^{[11]では、プレーンテキストの形式を保存する方法で}DES暗号化アルゴリズムを使用する方法について説明しています。この手法では、ここで参照されている他のモジュロ n 手法のように、バイアスのない手順が適用されないようです。

Mihir BellareとThomas Ristenpartによる論文「Format-Preserving Encryption」^[12]では、「ほぼバランスの取れた」Feistelネットワークを使用して安全なFPEアルゴリズムを作成する方法について説明しています。

Ulf Mattssonによる 論文「データ型保存暗号化を使用したフォーマット制御暗号化」^{[13]では、FPEアルゴリズムを作成する他の方法について説明しています。}

FPEアルゴリズムの一例としてはFNR（Flexible Naor and Reingold）がある。^[14]

NIST特別刊行物800-38G「ブロック暗号モードの動作に関する推奨事項：フォーマット保存暗号化の方法」^{[15]では、FF1とFF3の2つの方法が指定されています。それぞれについて提出された提案の詳細は、特許およびテストベクトル情報を含むNISTブロック暗号モード開発サイト[16]}で確認できます。FF1とFF3の両方のサンプル値が用意されています。^[17]

• FF1 は FFX[Radix]「フォーマット保持 Feistel ベース暗号化モード」であり、ANSI X9 の標準プロセスでも X9.119 および X9.124 として使用されています。これは、カリフォルニア大学サンディエゴ校の Mihir Bellare、カリフォルニア大学デービス校の Phillip Rogaway、および Voltage Security Inc. の Terence Spies によって NIST に提出されました。テスト ベクトルが提供され、その一部は特許を取得しています。(DRAFT SP 800-38G Rev 1) ^{[18] では、}暗号化されるデータの最小ドメイン サイズが 100 万 (以前は 100) である必要があります。

• FF3は、著者にちなんで名付けられたBPSです。フランスのIngenicoのÉric Brier、Thomas Peyrin、Jacques SternによってNISTに提出されました。著者は、NISTに対して、アルゴリズムは特許を取得していないと宣言しました。 ^[19] Cyber​​Res Voltage製品は、BPSモードの特許も所有していると主張しています。^{[20] [21]} 2017年4月12日、NISTは、研究者が脆弱性を発見したため、FF3は「汎用FPE方法としてはもはや適していない」と結論付けました。^[22]
• FF3-1（DRAFT SP 800-38G Rev 1）^[18]はFF3に代わるもので、暗号化されるデータの最小ドメインサイズを100万（以前は100）にすることを要求している。

別のモードが NIST ガイダンスの草案に含まれていましたが、最終公開前に削除されました。

• FF2 は、FFX 用の VAES3 スキームです。「暗号化を維持するための FFX モードの動作」の補遺です。サブキー操作を使用して任意の基数の文字列を暗号化し、暗号化キーの寿命を延ばすためのパラメータ コレクションです。これは、VeriFone Systems Inc. の Joachim Vance によって NIST に提出されました。テスト ベクトルは FF1 とは別に提供されておらず、その一部は特許を取得しています。著者は、NIST で現在検討中のDFF ^{[23]として修正アルゴリズムを提出しました。}

韓国も FPE 規格である FEA-1 と FEA-2 を開発しました。

FF1とFF3のオープンソース実装は、C言語、Go言語、Java、Node.js、Python、C#/.Net、Rustで公開されています。