PCFG = 確率文脈自由文法 (Probabilistic Context Free Grammar)

PCFG = Pretty Cool Fuzzy Guesser

一言で言えば: 人間がパスワードを生成する方法についての研究を行うためのツールコレクションです。これらはパスワードハッシュをクラックするために使用できますが、合成パスワード（ハニーワード）を作成したり、より優れたパスワード強度アルゴリズムの開発を支援するためにも使用できます。

ツールのバージョン

Trainer: 4.4

Guesser: 4.6

PRINCE_LING: 4.3

Password_Scorer: 4.4

ドキュメント

Sphinx を使用して、コード内のドキュメント文字列に基づいて開発者ガイドを動的に生成しています。開発者ガイドをビルドするには、/doc/INSTRUCTIONS.rst の手順を参照してください。

プレビルドされた開発者ガイドの PDF は /doc/build/latex/pcfgdevelopersguide.pdf にもあります。なお、git 履歴をクリーンに保つため、メジャーリリース間でこのガイドを再ビルドする予定はありません。つまり、PDF をコミットするとすぐに非常に混乱するからです。そのため、プレビルドガイドは若干古くなっている可能性があります。コードの作成/修正に役立てるために使用する場合は、プレビルド版ではなく、自分でガイドをビルドすることをお勧めします。

概要

このプロジェクトは、機械学習を使用してユーザーのパスワード作成習慣を特定します。開示された平文/クラックされたパスワードのリストをトレーニングすることで、PCFG モデルが生成されます。このプロジェクトのコンテキストでは、モデルはルールセットと呼ばれ、トレーニング中に特定されたパスワードのさまざまな部分と、それらに関連する確率が多数含まれています。このステミングは、PRINCE などの他のクラッキングツールに役立ち、ルールセットの一部をより伝統的な辞書ベースの攻撃に直接組み込むこともできます。このプロジェクトには、このルールセットを利用して確率順にパスワードの推測を生成する PCFG 推測ジェネレータも含まれています。これは標準的な辞書攻撃よりもはるかに強力であり、テストでは、他の公開されている方法よりも平均して大幅に少ない推測数でパスワードをクラックできることが証明されています。欠点は、確率順に推測を生成するのが遅いことです。つまり、毎秒平均 50〜10 万の推測を生成するのに対し、GPU ベースのアルゴリズムは高速ハッシュアルゴリズムに対して毎秒数百万から数十億（以上）の推測を生成できます。したがって、PCFG 推測器は、多数のソルト付きハッシュやその他の低速ハッシュアルゴリズムに対して最も適しており、アルゴリズムのパフォーマンスコストは推測の精度によって補われます。

要件 + インストール

Python3 がこれらのツールの唯一のハード要件です
トレーニングには chardet Python3 ライブラリをインストールすることを強くお勧めします。必須ではありませんが、トレーニングパスワードの文字エンコーディングの自動検出を実行します。インストールするには:
ソースを https://pypi.python.org/pypi/chardet からダウンロード
または pip3 install chardet を使用してインストール

クイックスタートガイド

トレーニング

このリポジトリに含まれるデフォルトのルールセットは、RockYou データセットの 100 万パスワードのサブセットをトレーニングして作成されました。RockYou の 3200 万パスワードの完全なセットでトレーニングすると、より良いパフォーマンスが得られますが、ダウンロードサイズを小さくするために除外されました。新しいリストでトレーニングしなくても、デフォルトのルールセットを使用してパスワードの生成を開始できますが、ターゲットとするパスワードに近いと思われるターゲットセットでトレーニングすることをお勧めします。独自のルールセットを作成する場合のクイックガイドは次のとおりです:

トレーニングする平文パスワードのセットを特定します。

このパスワードセットには重複パスワードを含める必要があります。そうすることで、トレーナーは 123456 のような一般的なパスワードが一般的であることを識別できます。
パスワードは平文で、ハッシュやユーザー名などの関連情報は削除されている必要があります。生の .pot ファイルをトレーニングセットとして使用しようとしないでください。トレーニングプログラムはハッシュをパスワードの一部と見なすためです。
パスワードは、生成するパスワード推測と同じ方法でエンコードする必要があります。つまり、UTF-8 のパスワード推測を作成する場合、トレーニングセットも UTF-8 でエンコードする必要があります。長期的には、推測生成時にこれを変更できる機能が開発計画にありますが、現在はサポートされていません。
トレーニングパスワードリストのサイズは 10 万から 5000 万の間である必要があります。トレーニングパスワードリストのサイズが推測生成にどのように影響するかについてはまだテスト中ですが、パスワードリストが 1 万程度の小さなサイズでも良好な結果が得られています。理想的なサイズはおそらく 100 万程度であり、それ以降は収穫逓減が見られます。
このチュートリアルでは、入力パスワードリストを INPUT_PASSWORD_LIST と呼びます。

生成するルールセットの名前を選択します。このチュートリアルでは NEW_RULESET とします。
入力パスワードリストでトレーナーを実行します。

python3 trainer.py -t INPUT_PASSWORD_LIST -r NEW_RULESET
一般的なオプションフラグ: a. coverage: トレーニングセットがターゲットパスワードと一致すると信頼する度合い。値が高いほど、マルコフモデリングを使用したインテリジェントなブルートフォース生成（現在は OMEN アルゴリズムを使用）が少なくなります。coverage を 1 に設定すると、ブルートフォースは実行されません。coverage を 0 に設定すると、マルコフ攻撃のみを使用して推測が生成されます。この値は浮動小数点数で、デフォルトは 0.6 で、ターゲットパスワードの基本単語がトレーニングセットに見つかる確率が 60% であると想定します。例: python3 trainer.py -t INPUT_PASSWORD_LIST -r NEW_RULESET -c 0.6 b. --save_sensitive: 指定すると、トレーニング中に検出されたメールアドレスや完全な Web サイトなどの機密データがルールセットに保存されます。PCFG 推測ジェネレータは現在このデータを使用していませんが、実際のパスワードクラッキング攻撃では非常に価値があります。これはデフォルトではオフになっており、このツールを学術的な環境で使いやすくしています。オフの場合でも、ルールセット内にはほぼ確実に PII データが保存されることに注意し、生成されたルールセットを適切に保護してください。例: python3 trainer.py -t INPUT_PASSWORD_LIST -r NEW_RULESET --save_sensitive c. --comments: ルールセット設定ファイルにコメントを追加します。これは後で見返したときに、ルールセットをなぜどのように生成したかを知るのに役立ちます。追加したいコメントを引用符で囲んで指定します。

推測生成

以前にトレーニングされた PCFG ルールセットを使用して、推測を標準出力に生成します。これらの推測は、使用したい任意のプログラムにパイプで渡すことができます。ルールセットが指定されていない場合、デフォルトのルールセット DEFAULT が使用されます。このガイドでは、使用するルールセットが NEW_RULESET であると想定します。

注意: 推測生成プログラムはルールセット名を指定する際に大文字と小文字を区別します。

セッション名は必須ではありません（デフォルトでは default_run というセッションが作成されます）が、一時停止/停止したセッションを再開しやすくするために役立ちます。これらの例ではセッション名 SESSION_NAME を使用します。同じ名前のセッションを同時に複数実行する場合の組み込みの健全性チェックはありませんが、それを避けることをお勧めします。

新しい推測セッションを開始するには、以下を実行します:

python3 pcfg_guesser.py -r NEW_RULESET -s SESSION_NAME

以前の推測セッションを再開するには、以下を実行します（セッションを復元するときは同じルールセットを指定する必要があることに注意）:

python3 pcfg_guesser.py -r NEW_RULESET -s SESSION_NAME --load

パスワード強度スコアリング

以前にトレーニングされたルールセットによってパスワードが生成される確率を推定したい場合が多くあります。例えば、これはパスワード強度メトリックの一部として、または他の研究目的で使用できます。これを実行するサンプルプログラムが含まれています。

INPUT_LIST はスコアリングするパスワードのリストを表します。これらのパスワードは平文で、改行で区切られ、1 行に 1 つのパスワードである必要があります。

スコアリングセッションを実行するには: python3 password_scorer -r NEW_RULESET -i INPUT_LIST
デフォルトでは、結果は標準出力に出力され、各パスワードが 1 行ごとにスコアリングされます。

最初の値は生のパスワードです
2 番目の値は、入力値が 'password'、'website'、'e-mail address'、または 'other' のいずれとしてスコアリングされたかを表します。パスワードかその他の判定は、OMEN 推測制限と PCFG に関連する確率の両方に設定した制限に依存します。
3 番目の値は、ルールセットによるパスワードの確率です。0.0 と割り当てられた場合、そのパスワードはルールセットによって生成されないことを意味しますが、マルコフベースの攻撃によって生成される可能性があります。
4 番目の値は、パスワードを生成する OMEN レベルです。-1 は、パスワードが OMEN によって生成されないことを意味します。

Prince-Ling ワードリストジェネレータ

名前: PRINCE Language Indexed N-Grams (Prince-Ling)

概要: PRINCE スタイルのコンビネータ攻撃で使用するために、既にトレーニングされた PCFG ルールセット/文法に基づいてカスタマイズされたワードリストを構築します。この背後にある考え方は、PCFG トレーナーがトレーニングセットのパスワードを個々の解析に分割しているため、その情報を活用して他の攻撃用のターゲットワードリストを作成できるということです。

基本メカニズム: 内部的には、Prince-Ling ツールは基本的にミニ PCFG 推測ジェネレータです。マルコフ推測生成を除去し、通常の PCFG 攻撃で使用される基本構造を、PRINCE ワードリストを生成するために調整された大幅に削減された基本構造に置き換えます。これにより、PRINCE 攻撃でどの単語が有用であると期待されるかを考慮しながら、確率順に辞書単語を生成できます。

Prince-Ling の使用

trainer.py を使用して PCFG ルールセットをトレーニングします。Prince-Ling が利用するすべてのデータ構造を学習していないため、PCFG ツールセットのバージョン 4.1 以降を使用してルールセットを作成する必要があることに注意してください。
Prince-Ling を実行します: python3 prince-ling.py -r RULESET_NAME -s SIZE_OF_WORDLIST_TO_CREATE -o OUTPUT_FILENAME

--rule: PRINCE ワードリストを作成する PCFG ルールセットの名前
--size: PRINCE ワードリストに作成する単語の数。指定しない場合、Prince-Ling は大文字小文字のマングリングが有効になっているかどうかに応じて非常に大きくなる可能性のあるすべての可能な単語を生成します（大文字小文字のマングリングはキースペースを大幅に増加させます）
--output: エントリを書き込む出力ファイル名。指定しない場合、Prince-Ling は単語を標準出力に出力しますが、非 ASCII 文字を出力する場合、使用しているシェルによっては問題が発生する可能性があります。
--all_lower: PRINCE 辞書の単語を小文字のみで生成します。これは、大文字小文字を区別しないハッシュを攻撃する場合や、別の方法でターゲットを絞った大文字小文字のマングリングを適用する予定がある場合に便利です。

John the Ripper を使用したパスワードクラッキングの例

python3 pcfg_guesser -r NEW_RULESET -s SESSION_NAME | ./john --stdin --format=bcrypt PASSWORDS_TO_CRACK.txt

貢献

バグに気づいた場合、または追加してほしい機能がある場合は、この GitHub ページで Issue を開いてください。プルリクエストも受け付けていますが、理想的にはプルリクエストを Issue にリンクして、レビューや質問、変更内容の理解を容易にしてください。

PCFG を使用したパスワード作成戦略のモデリングには、多くの改善の余地があります。新しいアイデア、変更、提案は大歓迎です。コードが現在特定の方法で何かを行っているからといって、それが最良の選択であるとは限りません。例えば、アルファ文字列、数字、その他などのマスクが生成される現在のアプローチの基本構造は、「最も簡単な」実装オプションであったために選択されました。私のチームでは、基本単語から始めて、それに適用されるより伝統的なマングリングルールを PCFG の遷移としてモデル化する方が良い選択肢かもしれないという議論が多くありました。このコードを自由に活用してください！

pcfg_cracker

人気