Project Euphoria

移行しました -> https://project-euphoria.netlify.app/

一次合同方程式を解く

はじめに

CTFで暗号の問題をやっているとよく出くわす概念に合同式があるのですが方程式の形で与えられることは少ない上に、解こうとしても特殊な場合(解きやすい)が多く、一般化について考えたことがありませんでした。というわけで今回は一次合同方程式を考察し、そのソルバを実装して実際にCTFで出た問題を解くところまでやろうと思います。
高校レベルの整数論以外の前提知識として不定方程式 ax + by = \mathrm{GCD}(a, b)が可解であることとこれの解の導出(拡張Euclid互除法)がありますが、実装に関しては後者だけ知っていれば問題ありません。

一次合同方程式

今回扱うのは ax \equiv b \mod nの形の合同方程式になります。整数 a,b,nに対し、 ax nで割った余りがbとなるxを求めるというものです。まず最初に方程式が解けるかどうかを考察し、次にその解の個数と求め方を示します。

解の存在

次の2通りに分けて可解かどうかを調べます。なお、 \mathrm{GCD}(a, b) a,bの最大公約数を示します。

  1.  \mathrm{GCD}(a, n) = 1
  2.  \mathrm{GCD}(a, n) > 1

以下では g := \mathrm{GCD}(a,n)と定義します。

まず1. の場合ですが、 a, nが互いに素であることから ax + ny = 1に解が存在します(拡張Euclid互除法とその理論背景を参照)。これらを x_0, y_0とおきます。つまり、 ax_0 + ny_0 = 1です。これの両辺に bを乗じて変形すると a(bx_0) - b = (-by_0)nとなるため、 x := bx_0とおくことで ax \equiv b \mod nとなります。よって nを法としてこれと合同な数は全て解となります。

続いて2. の場合ですが、 b gの倍数である時とそうでない時を考えます。後者の場合に ax \equiv b \mod nとなる xの存在を仮定すると ax + ny = bとなる整数 x,yが存在します。しかし左辺が gの倍数であるのに対し、左辺 b gの倍数でないとしたので矛盾します。よって b gの倍数でない時は解は存在しません。
前者の場合は1. 同様に ax + ny = gの解が存在し x_0, y_0すると、 b = gb'とおくことで x_0b', y_0b' ax + ny = bを満たすことから解が存在することがわかります。

以上より b gの倍数であるなら解は存在することになります。

解の個数

では続いて nを法として解の数が幾つあるかを考えます。存在性と同様、2つの場合に分けて考えます。

  1. の場合、求められた解を nを法として x_0とおきます。ここでもう1つの解が存在するとして x_1とします。それぞれ ax_0 \equiv b \mod n, ax_1 \equiv b \mod nであることから2式の差をとると a(x_0 - x_1) \equiv 0 \mod nとなります。 a,nは互いに素であることから ax + ny = 1となる x,yが存在し、したがって ax \equiv 1 \mod nとなります。この x a^{-1}とおいて先程の2式の差をとった式の両辺にかけると x_0 - x_1 \equiv 0 \mod nとなることから x_0 \equiv x_1 \mod nであるため解は結局1つになります。

  2. の可解( b gの倍数)の場合、 ax \equiv b \mod nより、 ax - b = nyとなる整数 yが存在します。これの両辺を gで割ると \frac ag x - \frac bg = \frac ng yとなります。 a,b,nはいずれも gの倍数なのでこの式の分数部分は全て整数です。したがって \frac ag x \equiv \frac bg \mod \frac ngが成り立ちます。なお、 \frac ag x \equiv \frac bg \mod \frac ngが成り立つような xはこの手順を逆に辿ることで ax \equiv b \mod nが成り立つこともわかります。したがってこの2つの問題は法を無視して整数全体を見ると同一の解を持つことから \frac ag x \equiv \frac bg \mod \frac ngの解を nを法とするように拡張すれば ax \equiv b \mod nの解となります。
     \frac ag x \equiv \frac bg \mod \frac ngが解け、 \frac ngを法として解が1つになることは1. の場合をこの問題に適用できることから明らかです。この解を x_0とします。これを法が nの場合に拡張すると x = x_0 + \frac ng t \lt nとなる範囲で整数 tを用いて表すことができます。この tの範囲は 0 \leq t \leq g - 1であることから解の数は g個になります。

以上より ax \equiv b \mod nの解は存在する場合は g個になります。

実装

↑の2つをそのまま実装します。なお、外部でEuclid互除法と拡張Euclid互除法は実装済みとします(それぞれgcd(a, b)ext_gcd(a, b))

# 可解性
def is_solvable(a, b, n):
    g = gcd(a, n)
    
    return (b % g) == 0


# 解が1つの場合
def solve_one(a, b, n):
    x_0, _ = ext_gcd(a, n)
    return (x_0 * b) % n


# 全ての解をリストにして返す
def solve(a, b, n):
    a, b = a % n, b % n
    if not is_solvable(a, b, n):
        return []
    ret = []
    g = gcd(a, n)

    _a, _b, _n = a // g, b // g, n // g
    _x = solve_one(_a, _b, _n)

    for i in range(g):
        ret.append(_x + _n * i)

    return ret

if __name__ == "__main__":
    print(solve(4, 8, 12))  # [2, 5, 8, 11]

Contrail CTF document_rescueのWriteup

これが解けると何が嬉しいのかというとなんとCTFで使えます。実はこれは半分本当で先日のCTFで出た問題が解けなかったので復習のために勉強してこの記事が生えたという経緯があります。詳しくは↓のWriteup記事の反省欄に書いたのでそちらを参照して欲しいのですが、ここでは先日行われたContrail CTFで出てきたdocument_resuceというCryptoの問題を今回のソルバを利用して解こうと思います。

xornet.hatenablog.com

この問題ではPDFをCFBモードで暗号化しています。その際の暗号化関数は線形合同法を利用しており、具体的には事前に用意された未知の鍵 a,bを用いて暗号文ブロック c_iと平文ブロック p_iに対し c_i = ((a + bc_{i-1}) \mod {2^{32}}) \oplus p_iとしています。CFBモードなので最初のブロックのためのIVが与えられていますがこちらも鍵ファイル中に含まれているので不明です。以降この鍵を a,bと表し、IVを xとします。
ここでPDFはマジックナンバー%PDFであることからある程度平文を予測できると考えられます。ソースコードを見ると頭8文字は%PDF-9.9としていたため次のような関係式が成り立ちます。

  •  (ax + b) \equiv p_0 \oplus c_0 \mod{2^{32}}
  •  (ac_0 + b) \equiv p_1 \oplus c_1 \mod{2^{32}}

但し、 p_0%PDFの16進表記で p_1%-9.9のそれです、pythonを使うとint.from_bytes(b, "big")の結果になります。これだけの情報では a,b,xを特定するのは難しいのですがPDFのファイル終端が%EOFであることを利用できないか考えます。実際はパディングされているため平文の最終ブロックは確定しないのですが%EOF, EOF\x00, OF\x00\x00, F\x00\x00\x00の4つのうちいずれかになります。平文の最終ブロックを p _ {-1}とおき、暗号文の末尾2ブロックは c _ {-2}, c _ {-1}とすると合同方程式 (ac _ {-2} + b) \mod{2^{32}} = p _ {-1} \oplus c _ {-1}が追加で得られます。改めて3つの式を並べると次のようになります。この3つの式を利用して a,b,xを求めることを考えます。

  •  (ax + b) \equiv p_0 \oplus c_0 \mod{2^{32}}
  •  (ac_0 + b) \equiv p_1 \oplus c_1 \mod{2^{32}}
  •  (ac _ {-2} + b) \equiv p _ {-1} \oplus c _ {-1} \mod{2^{32}}

このうち2つ目と3つ目の式の差をとると a(c_0 - c _ {-2}) \equiv (p_1 \oplus c_1) - (p _ {-1} \oplus c _ {-1}) \mod{2^{32}}となります。これは aを求める合同方程式のため、上のソルバを使って解くことが出来ます。実際の解の数は \mathrm{GCD}(c_0 - c _ {-2}, 2^{32}) = 2であることから2つ存在し、 p _ {-1}の候補が4つあることから掛け合わせて8通り考えることになります。このようにして求まった各 aに対して2つ目の式、あるいは3つ目の式を利用すると bが求まります。よって各 a,bを1つ目の式に代入すると xを求める合同方程式になることから同じくソルバを使って解くことができます。

この実行結果は最終的に11通り存在することからこれら全てのパラメータで復号を試みます。どのPDFも手元のビュアーでは読めなかったのですが、バイナリエディタで中身を見ると1つだけGreat! You have awesome programming skill and knowledge of CFB-mode encryption! Then let's find and use a tool to fix this corrupted header and try to see this PDF file's content :)という文字が現れるPDFが現れたためオンラインの修復ツールに投げたところ無事にPDFが開けてフラグが出てきました。

フラグはctrctf{f1l3_5truc7ur3_1nf0rm471on_4lw4ys_help_u}でした。

f:id:Xornet:20200106233826p:plain

使用したコードはこちらです↓

from math import ceil, floor


def gcd(a, b):
    if b == 0:
        return a

    return gcd(b, a % b)


def ext_gcd(a, b):
    if b == 1:
        return 0, 1

    q = a // b
    r = a % b

    next = ext_gcd(b, r)

    return next[1], next[0] - q * next[1]


def is_solvable(a, b, n):
    g = gcd(a, n)
    
    return (b % g) == 0


def solve_one(a, b, n):
    x_0, _ = ext_gcd(a, n)
    return (x_0 * b) % n


def solve(a, b, n):
    a, b = a % n, b % n
    if not is_solvable(a, b, n):
        return []
    ret = []
    g = gcd(a, n)

    _a, _b, _n = a // g, b // g, n // g
    _x = solve_one(_a, _b, _n)

    for i in range(g):
        ret.append(_x + _n * i)

    return ret


def to_num(b):
    return int.from_bytes(b, "big")


def decrypt(a, b, x):
    with open("flag.www", "rb") as f:
        cipher_raw = f.read()

    m = pow(2, 32)
    c = []
    index = 0
    while index + 4 <= len(cipher_raw):
        c.append(int.from_bytes(cipher_raw[index:index + 4], "big"))
        index += 4

    plain = []

    for i, _c in enumerate(c):
        if i != 0:
            plain.append(((c[i-1] * a + b) % m) ^ c[i])
        else:
            plain.append(((a * x + b) % m) ^ c[i])

    # print(plain[0].to_bytes(4, "big"))
    # print(plain[1].to_bytes(4, "big"))
    # print(plain[-1].to_bytes(4, "big"))

    f = open("flag-{}-{}-{}.pdf".format(a, b, x), "wb")
    for p in plain:
        f.write(p.to_bytes(4, "big"))

    f.close()


if __name__ == '__main__':
    with open("flag.www", "rb") as f:
        cipher_raw = f.read()

    c = []
    index = 0
    while index + 4 <= len(cipher_raw):
        c.append(int.from_bytes(cipher_raw[index:index + 4], "big"))
        index += 4

    plain = list(map(to_num, [b"%PDF", b"-9.9"]))
    hooter_candidates = list(
        map(to_num, [b"%EOF", b"EOF\x00", b"OF\x00\x00", b"F\x00\x00\x00"]))

    m = pow(2, 32)

    coef1 = (c[0] - c[-2]) % m
    g = gcd(coef1, m)

    print(g)

    abx_list = []

    for hooter in hooter_candidates:
        coef2 = ((plain[1] ^ c[1]) - (hooter ^ c[-1])) % m

        a_list = solve(coef1, coef2, m)

        for a in a_list:
            b = ((plain[1] ^ c[1]) - (c[0] * a)) % m

            x_list = solve(a, (plain[0]^c[0]) - b, m)

            for x in x_list:
                print("[+]: a, b, x -> %d %d %d" % (a, b, x))
                decrypt(a, b, x)

実行結果は次のようになります。ちなみにフラグが出てきた値はa, b, x = 2109834763, 3764688820, 268435455でした。

[+]: a, b, x -> 2134452074 854811907 92870375
[+]: a, b, x -> 2134452074 854811907 2240354023
[+]: a, b, x -> 4281935722 3002295555 92870375
[+]: a, b, x -> 4281935722 3002295555 2240354023
[+]: a, b, x -> 2109834763 3764688820 268435455
[+]: a, b, x -> 4257318411 1617205172 268435455
[+]: a, b, x -> 1049060107 1850361012 1270779903
[+]: a, b, x -> 3196543755 3997844660 1270779903
[+]: a, b, x -> 1202086667 2673427636 2381221887
[+]: a, b, x -> 3349570315 525943988 2381221887

あとがき

当日持っている整数論の知識で解けなくて物凄く悔しい思いをしたのでこのように解くことができて嬉しい一方で、z3のような優秀なソルバで解いてるWriteupが多く、そちらも習得しなくてはならないという気持ちにもなりました。弊チームに最近優秀な暗号担当が生えしばらく触れていませんでしたが、まだまだCrypto問題から学べることは多いので担当の低レイヤーを疎かにしない程度に頑張ろうと思います。
前回の復習記事ではあるものの、CTF関連の記事が続いているので次回も近いうちに真面目な記事が書けると嬉しいです。

参考文献