みなさま、こんにちは!CTO のめもりーです。 本年開催された PHPer チャレンジトークンの答え合わせ、解き方を解説します。
(1) の答え合わせ
出題クイズ
<?php $bytes = [0x61, 0x4c, 0x45, 0x45, 0x46, 0x79, 0x61, 0x79, 0x4c, 0x5b, 0x62, 0x48, 0x40, 0x4e, 0x40, 0x7e, 0x4c, 0x68, 0x5b, 0x4c, 0x7d, 0x46, 0x5b, 0x48, 0x47, 0x48]; $string = ''; for ($i = 0; $i < count($bytes); $i++) { $string .= chr($bytes[$i] ^ <1>); } if (md5($string) !== 'a8f101dec277521c969386effb2c8397') { echo "ハズレです!"; return; } echo "#{$string}";
- <1> … ここに入る 0x00 〜 0xff までを探してください
答え
解き方
0x00
から 0xff
までと定められるので、計算量 O(n)
(n=255) からもブルートフォースで求められます。 以下のようにコードを書き直すとよいでしょう。
<?php $bytes = [0x61, 0x4c, 0x45, 0x45, 0x46, 0x79, 0x61, 0x79, 0x4c, 0x5b, 0x62, 0x48, 0x40, 0x4e, 0x40, 0x7e, 0x4c, 0x68, 0x5b, 0x4c, 0x7d, 0x46, 0x5b, 0x48, 0x47, 0x48]; for ($k = 0x00; $k <= 0xff; $k++) { $string = ''; for ($i = 0; $i < count($bytes); $i++) { $string .= chr($bytes[$i] ^ $k); } if (md5($string) === 'a8f101dec277521c969386effb2c8397') { echo "#{$string}"; return; } }
(2) の答え合わせ
出題クイズ
<?php $string = '<1>'; $sum = array_sum( array_map( static fn (string $char) => ord($char), <2>($string) ) ); $additional = implode( array_map( static fn (string $numberValue) => chr(0x63 + ((int) $numberValue)), <2>((string) $sum) ) ); $string = "{$string}-{$additional}"; if (md5($string) !== '2fa885e32bc24b26f9dff3a47efb0d08') { echo "ハズレです!"; return; } echo "#{$string}";
- <1> … シャープを除いた (1) のPHPer チャレンジトークン
- <2> … 適切な関数名を埋めてください
答え
- <1> … HelloPHPerKaigiWeAreTorana
- <2> … str_split
- トークンの答えは「#HelloPHPerKaigiWeAreTorana-ehdf」
解き方
文字列を array_map
にかけようとしている点から、文字列を分割する関数であることの予測が付くでしょう。 そうすると、自然に str_split
か preg_split
などがパッと思い浮かぶかなと思いますが、第 1 引数のみで対応していることから str_split
であることがわかります。
(3) の答え合わせ
出題クイズ
<?php $string = '<1>-<2>'; [$part1, $part2, $part3] = <3>('-', $string); $calculator = fn (string $stringValue) => array_sum( array_reverse( array_map( fn (string $numberValue) => crc32($numberValue), str_split($stringValue) ) ) ); $string = substr(md5($calculator($part1) + $calculator($part2) + $calculator($part3)), 0, 10); if (md5($string) !== '8037d28b5a754eeacd1ee90fb1246610') { echo "ハズレです!"; return; } echo "#{$string}";
- <1> … シャープを除いた (2) の PHPer チャレンジトークン
- <2> … 弊社 CTO が登壇するプロポーザルに出現する PHP 以外の小文字の英字 3 文字
- <3> … 適切な関数名を埋めてください
答え
解き方
HelloPHPerKaigiWeAreTorana-ehdf-nfc
としたときにこれらを [$part1, $part2, $part3]
のように配列から取り出しているという点から、指定した文字列で分割されているように予測できます。したがって explode
であることがわかります。
(4) の答え合わせ
出題クイズ
<?php $string = '<1>'; $string = substr(md5(str_replace(<3>('a', 'f'), '', $string)), 0, 10); if (md5($string) !== 'b310309130966447075369fb9d56b437') { echo "ハズレです!"; return; } echo "#{$string}";
- <1> … シャープを除いた (3) の PHPer チャレンジトークン
- <2> … 適切な関数名を埋めてください
答え
- <1> … 11e7eb18b2
- <2> … range
- トークンの答えは「#6458e00ac0」
解き方
str_replace
の第 2 引数が空を指定していることから、特定の文字列を削除するようなコードであることが推測できます。 また a
から f
までの値を削除しているであろうと考えられ、str_replace
の第 1 引数は配列を受け付けることから a
から f
までの配列を作成しているということも同様に推測できます。 したがって range
を使って生成することが可能であることがわかります。
(5) の答え合わせ
出題クイズ
<?php $string = '<1>'; $string .= implode(array_reverse(str_split($string))) . '<2>'; $map = [ 'e971773f' => 0x7d, 'cbea68d7' => 0x46, '7f8abdb1' => 0x5b, 'a42a75c2' => 0x48, '29d01a37' => 0x47, '4a2414ee' => 0x48, '1be678b5' => 0x61, 'a347b1db' => 0x40, '00f56a27' => 0x5b, '35497491' => 0x40, '23a0dee4' => 0x47, 'baa98f5e' => 0x4e, 'cdaebfc8' => 0x08, ]; $split = str_split($string, 2); $result = ''; for ($i = 0; $i < count($split); $i++) { $result .= chr($map[<3>(<4>, crc32($split[$i]))] ^ <5>); } if (md5($result) !== 'd5ff5cec18c54a4fdc90f8ce1462e6b4') { echo "ハズレです!"; return; } echo "#{$result}";
- <1> … シャープを除いた (4) の PHPer チャレンジトークン
- <2> … 適切な 0-9a-f で作成された文字列を埋めてください (ヒント:
$map
で生成されている値の規則性) - <3> … 適切な関数名を埋めてください
- <4> … 適切な関数のパラメータを埋めてください
- <5> … ここに入る 0x00 〜 0xff までを探してください
答え
- <1> … 6458e00ac0
- <2> … f1f2f3 または c0f2f3
- <3> … sprintf
- <4> … %08x
- <5> … 0x29
- トークンの答えは「#ToranaHiring!」
解き方
<2>
で苦戦している方が結構多かったのではないかなと思います。したがって、まず <2>
の解答を飛ばし <3>
, <4>
, <5>
から解いていきます。 $map
を見るとインデックスが 8 番目のものが 00
となっていること、16 進数になっていっること、そして全体的に 8
桁になっていることに着目をします。 crc32
の出力結果は必ずしも、8 桁目に値があるとは限らない中で、先頭がゼロフィルされているということは <3>
と <4>
はゼロフィル 16 進数の変換をするための関数とパラメータであることが推測できます。したがって sprintf
と %08x
であることがわかります。
次に <5>
ですが、これは (1) で解いたものを応用し、かつ、$split = str_split($string, 2)
のように分解されており、また count($split)
回繰り返すということから、以下のようにコードを書き換えられます。
<?php $string = '6458e00ac0'; $string .= implode(array_reverse(str_split($string))) . '<2>'; $map = [ 'e971773f' => 0x7d, 'cbea68d7' => 0x46, '7f8abdb1' => 0x5b, 'a42a75c2' => 0x48, '29d01a37' => 0x47, '4a2414ee' => 0x48, '1be678b5' => 0x61, 'a347b1db' => 0x40, '00f56a27' => 0x5b, '35497491' => 0x40, '23a0dee4' => 0x47, 'baa98f5e' => 0x4e, 'cdaebfc8' => 0x08, ]; $split = str_split($string, 2); for ($k = 0x00; $k <= 0xff; $k++) { $result = ''; for ($i = 0; $i < count($split); $i++) { $result .= chr($map[sprintf('%08x', crc32($split[$i]))] ^ $k); } if (md5($result) === 'd5ff5cec18c54a4fdc90f8ce1462e6b4') { echo "#{$result}"; return; } }
これだけだと <2>
が解けていないので、<2>
を解きます。$map[sprintf('%08x', crc32($split[$i]))]
となっており、 for
内において $map
に split の分割後の要素数の最大までをループしています。
仮に $map
にダミーの値が入っていると仮定したとしても $map
の要素数以下がトークンの長さの最大値が含まれている(0 < トークンの長さ <= $map の要素数
)ということが推測できますね。
また、 $map
の要素数は、13
であることがわかります。次に 6458e00ac0
とこれを逆にした 0ca00e8546
を合わせると 20 文字、 str_split($string, 2)
で 2 文字ずつ分解していることから $map
にダミーが含まれていることまで考慮すると 0
〜 6
文字不足しているということがわかります。 したがって <2>
は 0 <= 2n <= 6
文字だということから、 0x00
〜 0xff
の範囲のものが 0 <= 2n <= 6
個入ることも推測できます。
さらに 2 文字ずつ分解し $map[sprintf('%08x', crc32($split[$i]))]
としている点から $map
のキーは 0x00
〜 0xff
の範囲の分割された文字 2 つを crc32
しているということもわかります。そのため以下のように解くことができます。
さっそく以下のように $map
から使われている値を探索します。
<?php $map = [ 'e971773f' => 0x7d, 'cbea68d7' => 0x46, '7f8abdb1' => 0x5b, 'a42a75c2' => 0x48, '29d01a37' => 0x47, '4a2414ee' => 0x48, '1be678b5' => 0x61, 'a347b1db' => 0x40, '00f56a27' => 0x5b, '35497491' => 0x40, '23a0dee4' => 0x47, 'baa98f5e' => 0x4e, 'cdaebfc8' => 0x08, ]; $targets = []; for ($l = 0x00; $l <= 0xff; $l++) { for ($m = 0x00; $m <= 0xff; $m++) { $key = sprintf('%08x', crc32(chr($l) . chr($m))); if (!isset($map[$key])) { continue; } $targets[] = chr($l) . chr($m); } } print_r($targets);
以下のような値が表示されることがわかります。
Array ( [0] => 0a [1] => 0c [2] => 0e [3] => 46 [4] => 58 [5] => 64 [6] => 85 [7] => a0 [8] => c0 [9] => e0 [10] => f1 [11] => f2 [12] => f3 )
つまり <2>
に入る値はこれらのいずれかの組み合わせであるため、これをブルートフォースでトライしてみます。
<?php $map = [ 'e971773f' => 0x7d, 'cbea68d7' => 0x46, '7f8abdb1' => 0x5b, 'a42a75c2' => 0x48, '29d01a37' => 0x47, '4a2414ee' => 0x48, '1be678b5' => 0x61, 'a347b1db' => 0x40, '00f56a27' => 0x5b, '35497491' => 0x40, '23a0dee4' => 0x47, 'baa98f5e' => 0x4e, 'cdaebfc8' => 0x08, ]; $targets = [ // 空文字列で $map にダミーが含まれていても問題ないようにする '', ]; for ($l = 0x00; $l <= 0xff; $l++) { for ($m = 0x00; $m <= 0xff; $m++) { $key = sprintf('%08x', crc32(chr($l) . chr($m))); if (!isset($map[$key])) { continue; } $targets[] = chr($l) . chr($m); } } foreach ($targets as $a) { foreach ($targets as $b) { foreach ($targets as $c) { $string = '6458e00ac0'; $string .= implode(array_reverse(str_split($string))) . $a . $b . $c; $split = str_split($string, 2); for ($k = 0x00; $k <= 0xff; $k++) { $result = ''; for ($i = 0; $i < count($split); $i++) { $key = sprintf('%08x', crc32($split[$i])); if (!isset($map[$key])) { continue; } $result .= chr($map[$key] ^ $k); } if (md5($result) === 'd5ff5cec18c54a4fdc90f8ce1462e6b4') { echo "#{$result}"; return; } } } } }
これにより、出力結果が #ToranaHiring!
であることがわかります。計算量は O(n^3)
で n=14
です。(最大 2,744 回の探索) もしくは、愚直に 6 文字分全てのパターンを網羅するでも良いかなとは思いますが、出力にはおそらく時間がかかるであろうと思われます。 (計算量が純粋に O(n^6)
であり n=256
なので 最大 281,474,976,710,656 回の探索が必要になります)
いかがでしたでしょうか?
md5
でトークンの結果を検証しているので、結果が正しいか検証しやすかったのではないかなと思います。
出題後に、デジタルサーカスさんの PHPer チャレンジトークンを見て、もうちょっと捻れば良かったなぁと、思ったのは内緒です。 また次の PHPerKaigi で同様の取り組みがありましたら、その時を是非お楽しみに!