PHPerKaigi 2023 トークン問題解説 (1/5)

From d30dfc89bf1b673b2fdc0638766b930adaec228c Mon Sep 17 00:00:00 2001 From: nsfisis Date: Sat, 29 Mar 2025 00:47:55 +0900 Subject: feat(blog/nuldoc): migrate syntax highlighter from highlight.js to shiki.js --- .../phperkaigi-2023-tokens-q1/index.html | 265 +++++++++++---------- 1 file changed, 140 insertions(+), 125 deletions(-) (limited to 'vhosts/blog/public/posts/2025-01-08') diff --git a/vhosts/blog/public/posts/2025-01-08/phperkaigi-2023-tokens-q1/index.html b/vhosts/blog/public/posts/2025-01-08/phperkaigi-2023-tokens-q1/index.html index 16bf6730..892c7f34 100644 --- a/vhosts/blog/public/posts/2025-01-08/phperkaigi-2023-tokens-q1/index.html +++ b/vhosts/blog/public/posts/2025-01-08/phperkaigi-2023-tokens-q1/index.html @@ -14,8 +14,7 @@ PHPerKaigi 2023 トークン問題解説 (1/5)｜REPL: Rest-Eat-Program Loop - - +

@@ -136,7 +135,9 @@ まずはトークンを得る方法を解説抜きで説明する。次のように実行する。

$ echo "#iwillblog" | php Q1.png >/dev/null

$ echo "#iwillblog" | php Q1.png >/dev/null

無事に実行できていれば「#ModernPHPisStaticallyTypedLanguage」というトークンが得られる。 @@ -151,7 +152,9 @@ まずは素直に画像として見てみよう。全体は QR コードになっている。適当な QR コードリーダで読み込むと、次のようなテキストが表示されるはずだ。

Guess password. $ echo "password" | php Q1.png >/dev/null

Guess password. $ echo "password" | php Q1.png >/dev/null

メッセージは、この画像の実行方法とこの問題でやるべきこと (パスワードの推測) を示している。 @@ -168,8 +171,10 @@ 不正なパスワードを使って実行してみると、次のようなエラーメッセージが表示される。

$ echo "foo" | php Q1.png >/dev/null
-401 Unauthorized

$ echo "foo" | php Q1.png >/dev/null
+401 Unauthorized

すでに「解き方」の節で示したように、パスワードである PHPer トークンは「#iwillblog」である。これを与えて実行すると正解のトークンが得られる。 @@ -258,23 +263,27 @@ strings コマンドを使うと、隠されたデータを簡単に閲覧できる。

IHDR
--HHc
-<PLTE
-IDATx
-IEND
-<?php
-error_reporting(-1);
-$b = unpack('C*', file_get_contents(__FILE__));
-$w = $b[20]+2;
-$h = $b[24]+2;
-// (以下略)

IHDR
+-HHc
+<PLTE
+IDATx
+IEND
+<?php
+error_reporting(-1);
+$b = unpack('C*', file_get_contents(__FILE__));
+$w = $b[20]+2;
+$h = $b[24]+2;
+// (以下略)

IHDR や IEND が PNG 画像の一部で、<?php からが実際のプログラムになっている。もちろんこれを PHP プログラムとして動かすと、PHP タグより前にある PNG 画像としてのデータはそのまま標準出力へと出力されてしまう。それを防ぐため、QR コードを読み込んだときの実行方法

Guess password. $ echo "password" | php Q1.png >/dev/null

Guess password. $ echo "password" | php Q1.png >/dev/null

には標準出力を捨てるよう >/dev/null と指定されている。 @@ -291,107 +300,109 @@ $h = $b[24]+2; 画像の正体がわかったところで、画像に隠されていた PHP プログラムについて見ていこう。先ほどは一部しか記載しなかったので、全体を載せる。なお、ある程度ゴルフしながら書いたので、空白こそ残しているものの可読性は非常に低いことと思う。

<?php
-error_reporting(-1);
-$b = unpack('C*', file_get_contents(__FILE__));
-$w = $b[20]+2;
-$h = $b[24]+2;
-$cs = [];
-for ($y = 0; $y < $h; $y++)
-  for ($x = 0; $x < $w; $x++)
-    $cs[$y*$w + $x] = ($x*$y === 0 || $x === $w-1 || $y === $h-1)
-                        ? 0
-                        : $b[122+($y-1)*($w-1)+$x-1];
-$i = stream_isatty(STDIN)
-    ? []
-    : array_map(ord(...), str_split(trim((string) fgets(STDIN))));
-$m = [];
-$pc = 1*$w+1;
-$dp = 0;
-$cc = 1;
-$c0 = 1;
-$b = 0;
-$ns = 0;
-$o = '';
-while (true) {
-  $ns++;
-  if ($ns > 1e5) {
-    echo "infinite loop detected\n";
-    break;
-  $c1 = $cs[$pc];
-  $y = (6 + intdiv($c1-2, 3) - intdiv($c0-2, 3)) % 6;
-  $x = (3 + $c1%3 - $c0%3) % 3;
-  match (($c0 !== 1) * ($c1 !== 1) * ($y*3 + $x)) {
-    1 => $m[] = $b,
-    2 => array_pop($m),
-    3 => $m[] = array_pop($m) + array_pop($m),
-    4 => $m[] = (fn($x, $y) => $y - $x)(array_pop($m), array_pop($m)),
-    5 => $m[] = array_pop($m) * array_pop($m),
-    8 => $m[] = array_pop($m) === 0 ? 1 : 0,
-    11 => $cc *= pow(-1, array_pop($m)),
-    12 => $m[] = $m[count($m)-1],
-    13 => $m = (fn($n, $d, $m, $l) => [
-            ...array_slice($m, 0, $l-$d),
-            ...array_reverse([
-              ...array_reverse(array_slice($m, $l-$d, $d-$n)),
-              ...array_reverse(array_slice($m, $l-$n)),
-            ]),
-          ])(array_pop($m), array_pop($m), $m, count($m)),
-    15 => !empty($i) and $m[] = array_shift($i),
-    16 => $o .= sprintf('%d', array_pop($m)),
-    17 => $o .= sprintf('%c', array_pop($m)),
-    default => 'nop',
-  };
-  $c0 = $c1;
-  for ($j = 0; $j < 8; $j++) {
-    $v = [];
-    if ($c1 === 1) {
-      $x = $pc % $w;
-      $y = intdiv($pc, $w);
-      $e = [($y+1)*$w-1, ($h-1)*$w+$x, $y*$w, $x][$dp];
-      $z = [1, $w, -1, -$w][$dp];
-      for ($ep = $pc; $ep !== $e; $ep += $z)
-        if ($cs[$ep] !== 1) break;
-      $ep -= $z;
-      $pc = $ep;
-    } else {
-      $q = [$pc];
-      $ep = $pc;
-      while (!empty($q)) {
-        $qq = array_pop($q);
-        $v[$qq] = true;
-        foreach ([$qq+1, $qq+$w, $qq-1, $qq-$w] as $qp) {
-          if ($cs[$qp] !== $c1) continue;
-          if (isset($v[$qp])) continue;
-          $q[] = $qp;
-          $qx = $qp % $w;
-          $qy = intdiv($qp, $w);
-          $x = $ep % $w;
-          $y = intdiv($ep, $w);
-          if (
-            ($dp === 0 && ($x < $qx || ($x === $qx && ($y<=>$qy) === $cc)))
-            || ($dp === 1 && ($y < $qy || ($y === $qy && ($qx<=>$x) === $cc)))
-            || ($dp === 2 && ($qx < $x || ($qx === $x && ($qy<=>$y) === $cc)))
-            || ($dp === 3 && ($qy < $y || ($qy === $y && ($x<=>$qx) === $cc)))
-          )
-            $ep = $qp;
-        }
-      }
-    }
-    $np = $ep + [1, $w, -1, -$w][$dp];
-    if ($cs[$np] !== 0) {
-      $b = count(array_keys($v));
-      $pc = $np;
-      break;
-    }
-    if ($j === 7) break 2;
-    if ($j % 2 === 0) $cc = -$cc;
-    if ($j % 2 === 1) $dp = ($dp+1) % 4;
-// The original Piet image is wrong: it outputs 403 error for invalid passwords.
-// Failure of authentication should be notified by 401, not 403.
-// I noticed that one month before PHPerKaigi, but I could not read or write (paint)
-// Piet any longer at that time.
-fwrite(STDERR, str_replace('403 Forbidden', '401 Unauthorized', $o));

<?php
+error_reporting(-1);
+$b = unpack('C*', file_get_contents(__FILE__));
+$w = $b[20]+2;
+$h = $b[24]+2;
+$cs = [];
+for ($y = 0; $y < $h; $y++)
+  for ($x = 0; $x < $w; $x++)
+    $cs[$y*$w + $x] = ($x*$y === 0 || $x === $w-1 || $y === $h-1)
+                        ? 0
+                        : $b[122+($y-1)*($w-1)+$x-1];
+$i = stream_isatty(STDIN)
+    ? []
+    : array_map(ord(...), str_split(trim((string) fgets(STDIN))));
+$m = [];
+$pc = 1*$w+1;
+$dp = 0;
+$cc = 1;
+$c0 = 1;
+$b = 0;
+$ns = 0;
+$o = '';
+while (true) {
+  $ns++;
+  if ($ns > 1e5) {
+    echo "infinite loop detected\n";
+    break;
+  $c1 = $cs[$pc];
+  $y = (6 + intdiv($c1-2, 3) - intdiv($c0-2, 3)) % 6;
+  $x = (3 + $c1%3 - $c0%3) % 3;
+  match (($c0 !== 1) * ($c1 !== 1) * ($y*3 + $x)) {
+    1 => $m[] = $b,
+    2 => array_pop($m),
+    3 => $m[] = array_pop($m) + array_pop($m),
+    4 => $m[] = (fn($x, $y) => $y - $x)(array_pop($m), array_pop($m)),
+    5 => $m[] = array_pop($m) * array_pop($m),
+    8 => $m[] = array_pop($m) === 0 ? 1 : 0,
+    11 => $cc *= pow(-1, array_pop($m)),
+    12 => $m[] = $m[count($m)-1],
+    13 => $m = (fn($n, $d, $m, $l) => [
+            ...array_slice($m, 0, $l-$d),
+            ...array_reverse([
+              ...array_reverse(array_slice($m, $l-$d, $d-$n)),
+              ...array_reverse(array_slice($m, $l-$n)),
+            ]),
+          ])(array_pop($m), array_pop($m), $m, count($m)),
+    15 => !empty($i) and $m[] = array_shift($i),
+    16 => $o .= sprintf('%d', array_pop($m)),
+    17 => $o .= sprintf('%c', array_pop($m)),
+    default => 'nop',
+  };
+  $c0 = $c1;
+  for ($j = 0; $j < 8; $j++) {
+    $v = [];
+    if ($c1 === 1) {
+      $x = $pc % $w;
+      $y = intdiv($pc, $w);
+      $e = [($y+1)*$w-1, ($h-1)*$w+$x, $y*$w, $x][$dp];
+      $z = [1, $w, -1, -$w][$dp];
+      for ($ep = $pc; $ep !== $e; $ep += $z)
+        if ($cs[$ep] !== 1) break;
+      $ep -= $z;
+      $pc = $ep;
+    } else {
+      $q = [$pc];
+      $ep = $pc;
+      while (!empty($q)) {
+        $qq = array_pop($q);
+        $v[$qq] = true;
+        foreach ([$qq+1, $qq+$w, $qq-1, $qq-$w] as $qp) {
+          if ($cs[$qp] !== $c1) continue;
+          if (isset($v[$qp])) continue;
+          $q[] = $qp;
+          $qx = $qp % $w;
+          $qy = intdiv($qp, $w);
+          $x = $ep % $w;
+          $y = intdiv($ep, $w);
+          if (
+            ($dp === 0 && ($x < $qx || ($x === $qx && ($y<=>$qy) === $cc)))
+            || ($dp === 1 && ($y < $qy || ($y === $qy && ($qx<=>$x) === $cc)))
+            || ($dp === 2 && ($qx < $x || ($qx === $x && ($qy<=>$y) === $cc)))
+            || ($dp === 3 && ($qy < $y || ($qy === $y && ($x<=>$qx) === $cc)))
+          )
+            $ep = $qp;
+        }
+      }
+    }
+    $np = $ep + [1, $w, -1, -$w][$dp];
+    if ($cs[$np] !== 0) {
+      $b = count(array_keys($v));
+      $pc = $np;
+      break;
+    }
+    if ($j === 7) break 2;
+    if ($j % 2 === 0) $cc = -$cc;
+    if ($j % 2 === 1) $dp = ($dp+1) % 4;
+// The original Piet image is wrong: it outputs 403 error for invalid passwords.
+// Failure of authentication should be notified by 401, not 403.
+// I noticed that one month before PHPerKaigi, but I could not read or write (paint)
+// Piet any longer at that time.
+fwrite(STDERR, str_replace('403 Forbidden', '401 Unauthorized', $o));

これは一体なんなのか。ずばり、難解プログラミング言語の一つ Piet のインタプリタである。Piet はピエト・モンドリアン (『赤・青・黄のコンポジション』などで知られる抽象画家) の作品にインスピレーションを受けて作られた、画像をソースコードとするプログラミング言語である。インタプリタは画像の各ピクセルの上を進みながら、色等に応じて特定の処理をおこなっていく。ここでは詳しい言語仕様については解説しないので、気になる方は Wikipedia の記事「Piet」などを参照してほしい。 @@ -401,7 +412,9 @@ $h = $b[24]+2; プログラムの冒頭にあるこの箇所

$b = unpack('C*', file_get_contents(__FILE__));

$b = unpack('C*', file_get_contents(__FILE__));

で __FILE__ つまりこの画像ファイルを読み込んでいる。先ほど Piet は画像をソースコードにしていると説明した。そう、今回の問題の画像ファイル Q1.png は、PHP 製 Piet インタプリタであると同時に、Piet のソースコード画像でもあるのだ。QR コード中央のカラフルな部分が Piet の命令になっている。 @@ -460,11 +473,13 @@ $h = $b[24]+2; ところで、先ほど掲載した Piet のインタプリタのソースコード末尾には次のような箇所がある。

// The original Piet image is wrong: it outputs 403 error for invalid passwords.
-// Failure of authentication should be notified by 401, not 403.
-// I noticed that one month before PHPerKaigi, but I could not read or write (paint)
-// Piet any longer at that time.
-fwrite(STDERR, str_replace('403 Forbidden', '401 Unauthorized', $o));

// The original Piet image is wrong: it outputs 403 error for invalid passwords.
+// Failure of authentication should be notified by 401, not 403.
+// I noticed that one month before PHPerKaigi, but I could not read or write (paint)
+// Piet any longer at that time.
+fwrite(STDERR, str_replace('403 Forbidden', '401 Unauthorized', $o));

コメントにも書かれているが、この Piet のソースコード画像には誤りがあった。本来 HTTP のステータスコードを真似るのなら、認証の失敗には 401 を返さなければならない。しかし、Piet のソースは 403 を返すように書いてしまっていた。そのことに私が気付いたのは PHPerKaigi 2023 が開催されるひと月前で、その時点で私はこの Piet のソースコードを (ちょうどこの記事でそうなっているのと同じように) 読解できなくなっていた。さらに悪いことに、正しいメッセージ「401 Unauthorized」は元の「403 Forbidden」よりも3文字長い。3文字出力が長くなるということは、それだけ Piet で塗るべきピクセルが増えることを意味する。もはや3文字追加で出力するだけの余白はこの画像に残されていなかった (と思う。腕ききの Piet プログラマならできるかもしれないので挑戦してみてほしい)。 -- cgit v1.2.3-70-g09d2