\トラーナのもぎたて情報/

PHPer チャレンジトークンの答え合わせ

みなさま、こんにちは!CTO のめもりーです。 本年開催された PHPer チャレンジトークンの答え合わせ、解き方を解説します。

toranabox.com

(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 までを探してください

答え

  • <1> … 0x29 (PHP エンジニア界隈といえば肉ですよね。)
  • トークンの答えは「#HelloPHPerKaigiWeAreTorana

解き方

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_splitpreg_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> … 適切な関数名を埋めてください

答え

  • <1> … HelloPHPerKaigiWeAreTorana-ehdf
  • <2> … nfc
  • <3> … explode
  • トークンの答えは「#11e7eb18b2

解き方

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 にダミーが含まれていることまで考慮すると 06 文字不足しているということがわかります。 したがって <2>0 <= 2n <= 6 文字だということから、 0x000xff の範囲のものが 0 <= 2n <= 6 個入ることも推測できます。

さらに 2 文字ずつ分解し $map[sprintf('%08x', crc32($split[$i]))] としている点から $map のキーは 0x000xff の範囲の分割された文字 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 で同様の取り組みがありましたら、その時を是非お楽しみに!