Index

2/8 Compressor

flag = os.environ.get("FLAG", "Alpaca{this_is_just_a_fake_flag_for_testing_goodluck}")
assert flag.startswith("Alpaca{") and flag.endswith("}")
assert len(flag) == 53

flag_charset = "abcdefghijklmnopqrstuvwxyz_A{}"
assert all(c in flag_charset for c in flag)

signal.alarm(600)

print(
    "I will compress (flag + your input) with zlib, but I will only give you the size of the compressed data."
)

while True:
    user_input = input("Your input: ").encode()
    data = flag.encode() + user_input
    compressed_data = zlib.compress(data)
    print(f"Size of compressed data: {len(compressed_data)} bytes")

サーバではflag+入力文字をzlib(Deflate)で圧縮し、圧縮後のバイト数を返してくれる。

細かい説明を省くとDeflateはブロック毎に構成され、 各ブロックは非圧縮のままか、LZ77で繰り返し部分の冗長性を消しその結果をハフマン符号(固定・可変)で詰めた形になる。

最短になる方法を計算するのは大変なので実際に動かして検証していく。

動作確認

Your input: Alpaca{
Size of compressed data: 64 bytes
Your input: aaaaaaa
Size of compressed data: 62 bytes
Your input: !"#$%&'
Size of compressed data: 68 bytes

既知のAlpacaで64, 同じ文字が続くaaaaaaaで62, 適当な記号列で68と圧縮の理解は概ね正しい。

flag_charset が決まっているのでAlpaca{の後ろにそれらを総当たりし、短くなるものが正解のはず。

これを繰り返せばフラグが求まる。

まずはシンプルにAlpaca{ + 1文字を試すと次のような結果が得られる。

[step 1] known='Alpaca{' MODE=none
 top 10 candidates
    64 'A'
    64 '_'
    64 'a'
    64 'c'
    64 'd'
    64 'e'
    64 'g'
    64 'h'
    64 'i'
    64 'l'
 TIE on min=64: ['A', '_', 'a', 'c', 'd', 'e', 'g', 'h', 'i', 'l', 'n', 'o', 'p', 'r', 's', 't', 'u', 'v', 'w', 'y'] ... (total 22)

byte長が短いものが22候補も出てしまった。正解した場合のみ単に1byte減るわけじゃないことが分かる。

そこで工夫が必要となる。

LZ77方式でフラグの次の文字を当てた場合には数bit分得をする。しかし、ここが切り上げられているため見分けがつかない。

そこで、末尾へフラグに出てこなそうなノイズを長さを変えながら付与することで、正解の見分けがつく。

例）正解が3bit分得してる場合