Making a SHA-256 Proof of Work solver from scratch

Problem

セキュリティ競技CTFの問題サーバーでは、接続者に計算問題を解かせることによって大量のリクエストを抑制する Proof of Work(PoW)というものが使われることがある。 解を探すには多くの計算が必要だが、サーバーは解を少ない計算で検証できる。

ここでは、与えられた文字列 prefix に非負整数 nonce の十進表記を連結し、SHA-256 ハッシュ値の先頭が bits ビット以上連続して 0 となる nonce を探す。 SHA-256 は入力から 256 ビットの値を計算するハッシュ関数であり、出力から入力を逆算する方法が知られていない。 例えば prefix が ctf-demo:、nonce が 123 なら、入力は ctf-demo:123。

ハッシュ値を一様なランダム値とみなすと、1 回の試行が成功する確率は約 2^(-bits)、解までの平均試行回数は約 2^bits になる。 ただし、指定した範囲内に解が存在する保証はない。

How the baseline code works

  1. 既知の SHA-256 テストベクトルと先頭ゼロビット数の判定を検査する。
  2. nonce を 0 から limit - 1 まで順に試す。
  3. 各候補で入力文字列を作り、SHA-256 を計算する。
  4. ハッシュ値の先頭ゼロビット数を数えて条件と比較する。
  5. 試行回数、発見数、計算時間、1 秒当たりのハッシュ数を表示する。 解があれば最初の nonce とハッシュ値を出力し、再計算で条件を確認する。

solve モードは最初の解で停止する。bench モードは解を見つけても全候補を調べ、発見数を数える。 性能比較では同じ prefix, bits, limit の bench を使い、早期終了による実行時間の違いを避ける。

bench の 10 億候補の時間が約5分、約325万hash/sec。

Where is parallelism