🦙

【CTF練習】Daily Alpaca Hack Writeup - crypto_666 (Crypto)

に公開
Security
CTF
crypto
素数
alpacahack
tech

はじめに

Daily Alpaca Hack 3月25日Cryptoの問題のWriteUpです。

問題概要

問題

悪魔の素数を作ることはできますか？

接続情報：nc 34.170.146.252 15827
添付ファイル：server.py

server.py
import os
from Crypto.Util.number import isPrime

flag = os.environ.get("FLAG", "Alpaca{*** REDACTED ***}")

p = input("p > ")
if ("6"*666 in p) and isPrime(int(p)):
    print(flag)
else:
    print("fail")

考察

コードを見ると、フラグを得るには以下の2つの条件を同時に満たす数pを入力する必要があることがわかります。
問題の条件：

  • 6が666個連続で含まれている("6"*666 in p)
  • 素数である(isPrime(int(p)))

この二つの条件を満たす入力をすればフラグを得ることができます。
6を666個作った前後に数字を付け足して総当たりで探します。
素数定理により大きな数の周辺には素数が高い密度で存在するため、現実的な時間で素数が見つかります。

解法

  1. "6"*666 を含む数を作る
  2. 後ろに奇数を付け足しながら素数判定を繰り返す
  3. 素数が見つかったらサーバーに送信する
  4. フラグを受け取る

今回はただ条件にあてはめて入力をする問題だったので6を666個ならべて素数になるように666個の6のあとに奇数を総当たりで付け足して素数を見つけていきます。

solve.py
from pwn import *
from Crypto.Util.number import isPrime

context.log_level = 'error'

def solve():
    r = remote("34.170.146.252", 15827)

    r.recvuntil(b"p > ")

    base = "6" * 666
    a = 1

    # 6*666を含む素数を見つける
    while True:
        p = base + str(a)
        if isPrime(int(p)):
            break
        a += 2  # 奇数だけを試す
    r.sendline(p.encode())
    flag = r.recvline().strip().decode()

    print("フラグ：" + flag)
solve()

実行結果：

フラグ：Alpaca{Prime numbers can be created freely}

まとめ

今回は脆弱性を見つけるというより、数学的な条件を満たす入力を作る問題でした。
素数は無限に存在するため、条件を満たす数を総当たりで探すというアプローチで解けました。
巨大な数の素数判定は時間がかかりますが、奇数だけに絞ることで効率よく探せることも学べましたね。

Discussion