2020 プロジェクト更新

Scallion は OpenCL と RSA を学ぶための趣味プロジェクトでした。現在、Scallion はメンテナンスしていません。以下の 2 点で問題が生じています。

1. Tor は v3 Onion アドレス に移行しており、Scallion は対応していません。古い v2 アドレスは 2021年10月 に使えなくなります。新しい仕様では異なる暗号プリミティブを使用し、全体的に複雑です。GPU 上で RSA 鍵のバッチを生成するための私たちのトリックは、必要な新しい ECDSA 鍵では同じようには機能しません。GPU 上で同様の（ただし互換性のない）ECDSA 鍵を生成することは可能で、Bitcoin アドレス生成に使われています。vanitygen-plus や古い oclvanitygen を参照してください。Tor v3 隠しサービスで動作する（CPU ベースの）バニティ生成ツールのリストについては、このブログ記事 を参照してください。
2. 私たちが依存している OpenSSL のバージョンは非推奨となっており、最近のほとんどの OS では利用できません。アップグレードは簡単ではありません。なぜなら、新しいバージョンの C# バインディングでは利用できない OpenSSL の低レベルの数学関数を使用しているからです。私は個人的に、Ubuntu 16.04 Xenial をベースにした nvidia dockerfile を使用して Scallion を実行しています。このバージョンにはまだ古い OpenSSL が含まれているためです。ただし、これは Nvidia GPU ユーザーにのみ有効なオプションです。古い OpenSSL ライブラリをビルドして直接リンクするか、Live USB や VM（PCI-e パススルーあり）で古い OS を実行することも試せます。

十分な注意と労力をかければ、上記の 2 つの課題を克服することは可能でしょう。GPU ECDSA 鍵生成アルゴリズムのサポートを実装して Tor v3 に対応し、OpenSSL を更新して数学関数を別のライブラリに置き換えるか、OpenSSL ライブラリ用の独自のマネージドコードラッパーを作ることができます。しかし、vanitygen-plus のようなメンテナンスされているプロジェクトに v3 オニオンアドレスのサポートを追加する方が良いでしょう。

Scallion

Scallion を使用すると、OpenCL を使ってバニティ GPG 鍵や .onion アドレス（Tor の 隠しサービス 用）を作成できます。

Scallion は Mono（Arch Linux でテスト済み）および .NET 3.5+（Windows 7 および Server 2008 でテスト済み）で動作します。

Scallion は現在ベータ版であり、活発に開発が進められています。それでも、使用可能な状態にあると考えています。改善は主にパフォーマンス、ユーザーインターフェース、インストールの容易さにおいて期待されており、鍵生成に使用される全体的なアルゴリズムの変更は予定されていません。

Scallion は MIT ライセンスで利用可能です。このプロジェクトのコードを自身のプロジェクトで使用する場合は、[email protected] までお知らせいただけると幸いです。

FAQ

よくある質問とその回答を以下に示します。

• なぜ GPG 鍵を生成するのですか？

  Scallion は、Web of Trust の strong set 内のすべての 32 ビット鍵 ID の衝突を見つけるために使用され、32 ビット鍵 ID がいかに安全でないかを実証しました。DEFCON での講演（動画）があり、追加情報は https://evil32.com/ で見つけることができます。

• 有効な文字は何ですか？

  Tor の .onion アドレスは Base32 を使用し、すべての英字と数字 2 から 7 まで（両端含む）で構成されます。大文字小文字は区別されません。

  GPG フィンガープリントは 16進数 を使用し、数字 0-9 と英字 A-F で構成されます。

• Bitcoin の ASIC（例：Jalapeno、KnC）を使ってこの処理を高速化できますか？

  残念ながら、できません。Scallion の処理は概念的には似ていますが（nonce を増やしてハッシュをチェック）、詳細は異なります（SHA-1 対 Bitcoin のダブル SHA-256）。さらに、Bitcoin ASIC は Bitcoin マイニング用途に極めて特化しているため高速です。例えば、こちらが CoinCraft A-1 のデータシート です。この ASIC は実際には発売されませんでしたが、一般的なアプローチを示しています。マイクロコントローラは、Bitcoin ブロックの最後の 128 ビット、前のビットのハッシュミッドステート、ターゲット難易度、試行する最大 nonce という形式で作業を送信します。ASIC は nonce を挿入する位置を選択し、どのブロックがハッシュ条件を満たすかを選択します。Scallion は nonce を異なる位置に挿入する必要があり、「XXXX より小さい」という単純な条件ではなく、パターンマッチをチェックします。

• 複数のデバイスを使用するにはどうすればよいですか？

  複数の Scallion インスタンスを実行してください。😄 Scallion の検索は確率的なので、2 台目のデバイスで作業が重複することはありません。真のマルチデバイスサポートはそれほど難しくありませんが、大きな利点もありません。私は tmux や screen で複数の Scallion インスタンスを実行して成功しています。必要なのは、いずれかのジョブがパターンを見つけたときに手動ですべてのジョブを中止するか（または出力ファイルを監視して結果が見つかったらすべてを強制終了するシェルスクリプトを書くこと）だけです。

依存関係

• OpenCL と適切なドライバがインストールされ、設定されていること。ディストリビューションのドキュメントを参照してください。
• OpenSSL。Windows の場合、プリビルドの x86 DLL が含まれています
• Windows の場合のみ、VC++ 再頒布可能パッケージ 2008

バイナリダウンロード

最新のバイナリバージョンだけ必要ですか？ こちらから入手してください：こちら。

Linux でのビルド

前提条件

• お使いの Linux ディストリビューション用の最新の mono を入手してください：

  http://www.mono-project.com/download/

• 共通の依存関係をインストール：

  root@kitploit:~

  sudo apt-get update
  sudo apt-get install libssl-dev mono-devel
  

• AMD/オープンソースビルド sudo apt-get install ocl-icd-opencl-dev

• Nvidia ビルド sudo apt-get install nvidia-opencl-dev nvidia-opencl-icd

• 最後に msbuild scallion.sln

Docker Linux（nvidia GPU のみ）

1. nvidia-docker コンテナ ランタイムを用意する

2. コンテナをビルド：

   root@kitploit:~

   docker build -t scallion -f Dockerfile.nvidia .
   

3. 実行：

   root@kitploit:~

   docker run --runtime=nvidia -ti --rm scallion -l
   

   期待される出力のスクリーンショット

Windows でのビルド

1. VS Express for Desktop 2012 で 'scallion.sln' を開く
2. ソリューションをビルド（デバッグモードで行いました）

使用方法

検索中に Scallion を再起動しても「進捗」は失われません。確率的な検索であり、Scallion は「進捗」しません

デバイス一覧表示

$ mono scallion/bin/Debug/scallion.exe -l

ハッシュの生成

$ mono scallion/bin/Debug/scallion.exe -d 0 prefix
Cooking up some delicious scallions...
Using kernel optimized from file kernel.cl (Optimized4)
Using work group size 128
Compiling kernel... done.
Testing SHA1 hash...
CPU SHA-1: d3486ae9136e7856bc42212385ea797094475802
GPU SHA-1: d3486ae9136e7856bc42212385ea797094475802
Looks good!
LoopIteration:40  HashCount:671.09MH  Speed:9.5MH/s  Runtime:00:01:10  Predicted:00:00:56  Found new key! Found 1 unique keys.
<XmlMatchOutput>
  <GeneratedDate>2014-08-05T07:14:50.329955Z</GeneratedDate>
  <Hash>prefix64kxpwmzdz.onion</Hash>
  <PrivateKey>-----BEGIN RSA PRIVATE KEY-----
MIICXAIBAAKBgQCmYmTnwGOCpsPOqvs5mZQbIM1TTqOHK1r6zGvpk61ZaT7z2BCE
FPvdTdkZ4tQ3/95ufjhPx7EVDjeJ/JUbT0QAW/YflzUfFJuBli0J2eUJzhhiHpC/
1d3rb6Uhnwvv3xSnfG8m7LeI/Ao3FLtyZFgGZPwsw3BZYyJn3sD1mJIJrQIEB/ZP
ZwKBgCTUQTR4zcz65zSOfo95l3YetVhfmApYcQQd8HTxgTqEsjr00XzW799ioIWt
vaKMCtJlkWLz4N1EqflOH3WnXsEkNA5AVFe1FTirijuaH7e46fuaPJWhaSq1qERT
eQT1jY2jytnsJT0VR7e2F83FKINjLeccnkkiVknsjrOPrzkXAkEA0Ky+vQdEj64e
iP4Rxc1NreB7oKor40+w7XSA0hyLA3JQjaHcseg/bqYxPZ5J4JkCNmjavGdM1v6E
OsVVaMWQ7QJBAMweWSWtLp6rVOvTcjZg+l5+D2NH+KbhHbNLBcSDIvHNmD9RzGM1
Xvt+rR0FA0wUDelcdJt0R29v2t19k2IBA8ECQFMDRoOQ+GBSoDUs7PUWdcXtM7Nt
QW350QEJ1hBJkG2SqyNJuepH4PIktjfytgcwQi9w7iFafyxcAAEYgj4HZw8CQAUI
3xXEA2yZf9/wYax6/Gm67cpKc3sgKVczFxsHhzEml6hi5u0FG7aNs7jQTRMW0aVF
P8Ecx3l7iZ6TeakqGhcCQGdhCaEb7bybAmwQ520omqfHWSte2Wyh+sWZXNy49EBg
d1mBig/w54sOBCUHjfkO9gyiANP/uBbR6k/bnmF4dMc=
-----END RSA PRIVATE KEY-----
</PrivateKey>
  <PublicModulusBytes>pmJk58BjgqbDzqr7OZmUGyDNU06jhyta+sxr6ZOtWWk+89gQhBT73U3ZGeLUN//ebn44T8exFQ43ifyVG09EAFv2H5c1HxSbgZYtCdnlCc4YYh6Qv9Xd62+lIZ8L798Up3xvJuy3iPwKNxS7cmRYBmT8LMNwWWMiZ97A9ZiSCa0=</PublicModulusBytes>
  <PublicExponentBytes>B/ZPZw==</PublicExponentBytes>
</XmlMatchOutput>
init: 491ms / 1 (491ms, 2.04/s)
generate key: 1193ms / 6 (198.83ms, 5.03/s)
cpu precompute: 10ms / 6 (1.67ms, 600/s)
total without init: 70640ms / 1 (70640ms, 0.01/s)
set buffers: 0ms / 40 (0ms, 0/s)
write buffers: 3ms / 40 (0.08ms, 13333.33/s)
read results: 67442ms / 40 (1686.05ms, 0.59/s)
check results: 185ms / 40 (4.63ms, 216.22/s)

9.50 million hashes per second

Stopping the GPU and shutting down...

マルチパターンハッシュ

Scallion は、プリミティブな正規表現構文を使用して複数のパターンのうち 1 つ以上を見つけることをサポートしています。サポートされているのは文字クラス（例：[abcd]）のみです。. 文字は任意の文字を表します。Onion アドレスは常に 16 文字、GPG フィンガープリントは常に 40 文字です。マッチの末尾に $ を付けることで接尾辞を見つけることができます（例：DEAD$）。最後に、パイプ構文（例：pattern1|pattern2）を使用して複数のパターンを見つけることができます。複数のパターンを検索しても（妥当な範囲内で）、速度の大幅な低下は生じません。多くの正規表現は GPU 上で単一のパターンになり、速度低下は発生しません。

ユースケースの例：

• 読みやすくするために接頭辞の後に数字を付けて生成：

  root@kitploit:~

    mono scallion.exe prefix[234567]
  

• 複数のパターンを一度に検索（注意：-c を付けると、ヒットしても生成を継続します）

  root@kitploit:~

    mono scallion.exe -c prefix scallion hashes
    mono scallion.exe -c "prefix|scallion|hashes"
  

• 接尾辞 "badbeef" を検索

  root@kitploit:~

    mono scallion.exe .........badbeef
    mono scallion.exe --gpg badbeef$ # GPG 鍵を生成
  

• 複雑な自己説明的な例：

  root@kitploit:~

    mono scallion.exe "suffixa$|suffixb$|prefixa|prefixb|a.suffix$|a.test.$"
  

Scallion の仕組み

大まかには、Scallion は次のように動作します：

1. CPU 上で OpenSSL を使用して RSA 鍵を生成
2. 鍵を GPU に送信
3. 鍵の公開指数を増加
4. 鍵をハッシュ
5. ハッシュされた鍵が部分衝突でなければステップ 3 に戻る
6. 鍵が PKCS #1 v2.1 で推奨される健全性チェック（CPU でチェック）を通過しなければステップ 3 に戻る
7. 部分衝突のある新しい鍵が完成！

基本的なアルゴリズムは上記の通りです。速度/パフォーマンスは、GPU と CPU の両方での大規模な並列化の結果です。

速度 / パフォーマンス

Scallion は確率的な検索を行うことに注意してください。実際の時間は予測から大きく異なる可能性があります

初期の RSA 鍵生成は CPU で行われます。Ivy Bridge i7 は、シングルコアで毎秒 51 個の鍵を生成できます。各鍵はマイニングに 1 ギガハッシュ分の指数を提供でき、適切な CPU は現在の実装で複数の GPU に追いつくことができます。

SHA1 ハッシュは GPU で行われます。以下は、テストしたいくつかの GPU のハッシュレートです（メーカー別にグループ化し、電力でソート）：

MH/s = 100万ハッシュ/秒

Intel がプロセッサ向けの OpenCL ドライバをリリースしており、CPU でも短い衝突を見つけることができます。

特定の部分衝突にかかる秒数（平均）を計算するには、次の式を使用します：

例えば、私の nVidia Quadro K2000M では約 90 MH/s です。この速度で 8 文字の .onion 接頭辞を生成するには約 1 時間 41 分かかります。2^(5*8-1)/90 million = 101 分。

ワークグループサイズ

Scallion はデフォルトでデバイスが報告する推奨ワークグループサイズを使用します。これは適切なデフォルトですが、ワークグループを実験することでパフォーマンスが向上する可能性があります。

セキュリティ

Scallion によって生成される鍵は、shallot によって生成される鍵と非常に似ています。異常に大きな公開指数を持っていますが、OpenSSL の RSA_check_key 関数を介して PKCS #1 v2.1 で推奨されるすべての健全性チェックを受けています。Scallion は複数の RSA 鍵サイズをサポートしており、1024b、2048b、4096b 向けに最適化されたカーネルが用意されています。他の鍵サイズでも動作する可能性がありますが、テストは行われていません。

謝辞 / 参考文献

• Scallion は一部 shallot に基づいており、vanitygen に触発されています。
• OpenCL SHA-1 実装は NearSHA から改変されました。
• OpenTK および OpenSSL-net のコンポーネントが含まれています。

寄付

寄付は Bitcoin アドレス 1FxQcu6vhpwsqcTjPsjK43CZ9vjnuk4Hmo へお願いします。