指紋（コンピューティング）

コンピュータサイエンスにおいて、フィンガープリントアルゴリズムとは、任意の大きさのデータ項目（コンピュータファイルなど）をはるかに短いビット文字列（フィンガープリント）にマッピングする手順であり、人間の指紋が実際上人々を一意に識別するのと同じように、実際上は元のデータを一意に識別します。 ^{[1]このフィンガープリントは、}データの重複排除のために使用される場合があります。これは、ファイルフィンガープリント、データフィンガープリント、または構造化データフィンガープリントとも呼ばれます。

フィンガープリントは、通常、大きなデータの比較や転送を避けるために使用されます。たとえば、Webブラウザやプロキシサーバーは、リモートファイルのフィンガープリントのみを取得し、以前に取得したコピーのフィンガープリントと比較することで、そのファイルが変更されたかどうかを効率的に確認できます。^{[2] [3] [4] [5] [6]}

指紋関数は、暗号ハッシュ関数が不要な 大量のデータ ブロックを一意に識別するために使用される高性能ハッシュ関数と見なすことができます。

オーディオ フィンガープリントとビデオ フィンガープリントには特別なアルゴリズムが存在します。

フィンガープリント アルゴリズムが本来の目的を果たすには、ファイルの ID をほぼ確実に取得できなければなりません。言い換えると、衝突(2 つのファイルが同じフィンガープリントを生成すること) の確率は、他の避けられない致命的なエラーの原因 (戦争や隕石によるシステムの破壊など) の確率と比較して無視できるほど小さくなければなりません (たとえば、10 ⁻²⁰以下)。

この要件は、チェックサム機能の要件と多少似ていますが、はるかに厳格です。偶発的なデータ破損や転送エラーを検出するには、エラーの統計モデルが与えられれば、元のファイルと破損したバージョンのチェックサムがほぼ確実に異なるだけで十分です。一般的な状況では、この目標は 16 ビットまたは 32 ビットのチェックサムで簡単に達成できます。対照的に、大規模なファイル システムで仮想的な一意性を保証するには、ファイル フィンガープリントの長さが少なくとも64 ビットである必要があります(誕生日攻撃を参照)。

上記の要件を証明する場合、ファイルはファイル間に複雑な依存関係を生み出す、非常に非ランダムなプロセスによって生成されることを考慮する必要があります。たとえば、一般的なビジネス ネットワークでは、通常、わずかな編集やその他のわずかな変更のみが異なるドキュメントのペアまたはクラスターが多数見つかります。優れたフィンガープリント アルゴリズムでは、このような「自然な」プロセスによって、必要なレベルの確実性で明確なフィンガープリントが生成されるようにする必要があります。

コンピュータ ファイルは、連結 (アーカイブ ファイルなど) やシンボリック インクルード ( C プリプロセッサの#includeディレクティブなど) など、さまざまな方法で結合されることがよくあります。一部のフィンガープリント アルゴリズムでは、複合ファイルのフィンガープリントをその構成要素のフィンガープリントから計算できます。この「複合」プロパティは、プログラムの再コンパイルが必要な時期を検出するなど、一部のアプリケーションで役立つ場合があります。

ラビンのフィンガープリントアルゴリズムは、このクラスのプロトタイプです。^[7] このアルゴリズムは、実装が高速かつ簡単で、複合化が可能であり、衝突の確率を数学的に正確に分析します。つまり、2 つの文字列rとs が同じwビットのフィンガープリントを生成する確率は、max(| r |,| s |)/2 ^{w -1}を超えません。ここで、| r | はrのビット長を表します。このアルゴリズムでは、 wビットの内部「キー」を事前に選択する必要がありますが、この保証は、文字列rとs がキーを知らずに選択される 限り有効です。

ラビンの方法は悪意のある攻撃に対して安全ではありません。敵対的なエージェントは簡単にキーを発見し、それを使用して指紋を変更せずにファイルを変更できます。

主流の暗号グレードのハッシュ関数は、一般的に高品質のフィンガープリント関数として機能し、暗号解読者による厳しい精査を受けており、悪意のある攻撃に対して安全であると考えられているという利点があります。

MD5やSHAなどの暗号化ハッシュ アルゴリズムの欠点は、Rabin のフィンガープリント アルゴリズムよりも実行にかなり時間がかかることです。また、衝突確率の保証も証明されていません。これらのアルゴリズムの一部、特にMD5 は、安全なフィンガープリントには推奨されなくなりました。ただし、意図的なデータ改ざんが主な懸念事項ではないエラー チェックには依然として役立ちます。

NIST は、暗号化ハッシュ関数を使用してファイルのフィンガープリントを作成し、それらをソフトウェア製品にマッピングするソフトウェア リファレンス ライブラリである American National Software Reference Libraryを配布しています。 National Drug Intelligence Centerによって管理されているHashKeeperデータベースは、法執行機関のアプリケーション (押収されたディスク ドライブの内容を分析するなど) で使用するための、「安全であることがわかっている」コンピュータ ファイルと「安全であることがわかっている」コンピュータ ファイルのフィンガープリントのリポジトリです。