あさっちの不定期日記

色々ごった煮。お勉強の話もあればテニスの話をするかもしれない。

zer0pts CTF writeup(3)

はじめに

その1はこちら。その2はこちら。

これが最終回です。

janken vs yoshiking (crypto, 143pts, 44solves)

Yoshiking knows the flag. He will give the flag to who has gold luck. Let's play the janken with Yoshiking and prove your luck!

import random
import signal
from flag import flag
from Crypto.Util.number import getStrongPrime, inverse

HANDNAMES = {
    1: "Rock",
    2: "Scissors",
    3: "Paper"
}

def commit(m, key):
    (g, p), (x, _) = key
    r = random.randint(2, p-1)
    c1 = pow(g, r, p)
    c2 = m * pow(g, r*x, p) % p
    return (c1, c2)


def decrypt(c, key):
    c1, c2 = c
    _, (x, p)= key

    m = c2 * inverse(pow(c1, x, p), p) % p
    return m


def keygen(size):
    p = getStrongPrime(size)
    g = random.randint(2, p-1)
    x = random.randint(2, p-1)

    return (g, p), (x, p)


signal.alarm(3600)
key = keygen(1024)
(g, p), _ = key
print("[yoshiking]: Hello! Let's play Janken(RPS)")
print("[yoshiking]: Here is g: {}, and p: {}".format(g, p))

round = 0
wins = 0
while True:
    round += 1
    print("[system]: ROUND {}".format(round))

    yoshiking_hand = random.randint(1, 3)
    c = commit(yoshiking_hand, key)
    print("[yoshiking]: my commitment is={}".format(c))

    hand = input("[system]: your hand(1-3): ")
    print("")
    try:
        hand = int(hand)
        if not (1 <= hand <= 3):
            raise ValueError()
    except ValueError:
        print("[yoshiking]: Ohhhhhhhhhhhhhhhh no! :(")
        exit()

    yoshiking_hand = decrypt(c, key)
    print("[yoshiking]: My hand is ... {}".format(HANDNAMES[yoshiking_hand]))
    print("[yoshiking]: Your hand is ... {}".format(HANDNAMES[hand]))
    result = (yoshiking_hand - hand + 3) % 3
    if result == 0:
        print("[yoshiking]: Draw, draw, draw!!!")
    elif result == 1:
        print("[yoshiking]: Yo! You win!!! Ho!")
        wins += 1
        print("[system]: wins: {}".format(wins))

        if wins >= 100:
            break
    elif result == 2:
        print("[yoshiking]: Ahahahaha! I'm the winnnnnnner!!!!")
        print("[yoshiking]: You, good loser!")
        print("[system]: you can check that yoshiking doesn't cheat")
        print("[system]: here's the private key: {}".format(key[1][0]))
        exit()

print("[yoshiking]: Wow! You are the king of roshambo!")
print("[yoshiking]: suge- flag ageru")
print(flag)

OT or NOT OTに続いてncで接続するタイプの問題です。ローカル再現は例によってfrom flag import flagを書き換えてsocatでどうぞ。

コードが長めですが、要約すると

  • P, Gは公開鍵、 xは秘密鍵

  • 以下の流れでユーザ(我々) vs Yoshikingのじゃんけんが行われる

    • Yoshikingがランダム値 rを設定。これはじゃんけんの度に毎回変化する

    • Yoshikingは C_1 = G^ r mod P, C_2 = mG^ {xr} mod Pを公開

    • mの値は、「Yoshikingがグーなら1、チョキなら2、パーなら3」

    • C_1, C_2を見た後で、ユーザ側は出す手を指定する

  • 1回でも負ければ終了。引き分けは特に影響なし。通算100勝でflag入手

いつものように大文字 G, P, C_1, C_2は既知で小文字 x, r, mは未知です。

この段階で先に告白しておきますが、CTFに久しく参加していないせいでセンスが鈍った決定的な1問です。

以下で色々試行錯誤していますが、cryptoのプロフェッショナルの方々は温かい目で見守ってください。

アプローチ1

くどいですが、乗法準同型性があります。グーに対する暗号文 C=G^ {xr}が分かれば、2倍や3倍することでチョキ、パーに対する暗号文 2G^ {xr}, 3G^ {gr}の計算は容易です。

もちろん、グーに限った話ではなく他の手にも言えます。なので、なんとか1回目は引き分けか勝利して

「 C_1 = G^ r, C_2 = G^ {xr}の情報、および2回目以降の情報 C_1' = G^ {r'}から

C_2'が G^ {xr'}に一致するかを求める(一致しなければ 2G^ {xr'}, 3G^ {xr'}で検証する)」

ことになります。いわゆるDDH仮定(Decisional Diffie-Hellman)を突破するのが目標です。

さて、ここで突然ですが楕円曲線の場合を考えます。つまり、楕円曲線上のPが与えられた場合に

「 C_1 = rP, C_2 = xrPの情報、および2回目以降の情報 C_1' = r'Pから

C_2'が xr'Pに一致するかを求める」

という問題を設定してみます。実は、これはペアリングという技術で解決可能です。

ペアリング eとは楕円曲線上の2点に対する演算のことで、任意の整数係数に対し、

e(aP, bP) = e(P, P)^ {ab}

が成立します。これを使えば、

e(C_2, C_1') = e(xrP, r'P) = e(P, P)^ {xrr'} = e(rP, xr'P) = e(C_1, xr'P)

となるので、 e(C_2, C_1') = e(C_1, C_2')が成立すれば C_2'と xr'Pは一致すると言えます。

これを何とか上記に適用できないでしょうか…？

結論から言うと、無理です。

上の方でDDH仮定という言葉を使いましたが、 G^ r mod Pのような乗法巡回群でこのDDH仮定は存在していて、 rPのような加法巡回群ではペアリングが存在している以上、DDH仮定は存在しません。

言い換えると、乗法巡回群でのペアリングが成立したら、DDH仮定(およびそれを安全性の根拠にしている暗号スキーム)が崩壊します。

アプローチ2

楕円曲線は忘れましょう。

改めてこのコードを見るとどうやらElGamal暗号に似た形をしています。

Wikipediaで何か有力な情報がないか見てみると、以下の文章がありました。

pを素数とするとき、 G = \mathbb{Z}_p^ \astとしてはいけない。このような群上ではDDH仮定が破れる。

あの、どう破れるかを見せてくださいWikipedia先生…

英語版Wikipediaも参照しましたが、めぼしい情報が得られません。こういう時は英語でググるとたいていヒットします。

"elgamal break ddh"で検索をかけて一番上に出てきたPDFにアクセスしてみます。

がっつり論文チックなやつですね。セクション名だけ読むくらいのめちゃくちゃ粗い粒度で目を通していくと…

4 BREAKING ELGAMAL

...

Example 4.1 (Breaking the DDH Assumption)

...

Example 4.2 (Breaking the ElGamal Scheme using a QR generator)

...

なる文字が。このセクションだけ熟読しました。どうやらQR、つまり平方剰余を絡めれば特殊なケースではDDHを破れる様子1。

論文はここでおしまいです。問題に戻りましょう。

以下では平方剰余を QR (Quadratic Residue), 平方非剰余を QNR (Quadratic Non-Residue)で表します。

これらの性質として押さえておくべきポイントは

  • a, bがともに QRなら abも QR

  • a, bの一方だけが QRなら abは QNR

  • a, bがともに QNRなら abは QR

だけです。 QR=1, QNR=-1に置き換えればわかりやすいかもしれません2。

なので、以下では QR, QNRをそれぞれ 1_Q, -1_Qで表記します3。

さて、問題設定は

「 C_1 = G^ r, C_2 = G^ {xr}, C_1' = G^ {r'}から C_2'が G^ {xr'}, 2G^ {xr'}, 3G^ {xr'}のどれなのかを当てる」

でした。ここで、 C_1が -1_Qのとき、 C_2 = C_1^ xなので

  • C_2が 1_Qなら xは偶数

  • C_2が -1_Qなら xは奇数

です。ここまでくるとほぼ解けたも同然です。ここで、わざと

「 2, 3, C_1がすべて -1_Qである」

状況を想定します。このとき、

C_2 C_1' = G^ {r'} C_2' → x G^ {xr'} 2G^ {xr'} 3G^ {xr'} → Yoshiking
-1_Q 1_Q 1_Q 奇数 1_Q -1_Q -1_Q グー
-1_Q 1_Q -1_Q 奇数 1_Q -1_Q -1_Q チョキ/パー
-1_Q -1_Q 1_Q 奇数 -1_Q 1_Q 1_Q チョキ/パー
-1_Q -1_Q -1_Q 奇数 -1_Q 1_Q 1_Q グー
1_Q 1_Q 1_Q 偶数 1_Q -1_Q -1_Q グー
1_Q 1_Q -1_Q 偶数 1_Q -1_Q -1_Q チョキ/パー
1_Q -1_Q 1_Q 偶数 1_Q -1_Q -1_Q グー
1_Q -1_Q -1_Q 偶数 1_Q -1_Q -1_Q チョキ/パー

xは C_2から決定できます。その右隣の3つはそれぞれグー、チョキ、パーに対応していて、 C_1' と xの偶奇から計算できます。

これと C_2'が一致するものがYoshikingの手の候補となります。

ここで、今までずっと完全に特定できなくても、2通りに絞れれば負けはないことを失念していました。

引き分けは影響しないですからね。

さて、ソルバの枠組みは以下のようになります。

  1. 与えられた数が 1_Q, -1_Qのどちらか、つまり平方剰余かどうかを判定する関数を作る

  2. 最初に Pが与えられるので、 2, 3が -1_Qになるよう祈る

  3. 1回目のじゃんけんの情報 C_1が -1_Qになるよう祈る

  4. 1回目のじゃんけんを引き分けか勝ちになるよう祈る

  5. ここまでくると、上の表に従ってコーディングすれば2回目以降で負けはない

…運の要素多くないですか？平方剰余と平方非剰余の割合はともに1/2なので、2.と3.の突破率は合計で約1/8です。

4.の突破率は言うまでもなく2/3で、トータルで1/12といったところでしょうか。

ですが、実際やってみるとわかりますが、なぜかほとんど突破しません4。

たぶん上の概算が甘いのでもう少し偏りがあるんだと思います。

なお、1.についてはLegendre記号を実装すればOKです。つまり、

a^ {\frac{p-1}{2}} = 1 mod p

なら aは平方剰余(ここでいう 1_Qに相当)、 -1なら平方非剰余( -1_Q)です。

アプローチ3

こちらは例によってrkm0959氏のwriteupです。

平方剰余に注目する点は一緒ですが、

「 2, 3が -1_Qで、 Gが 1_Qである」

状況を想定します。この時、 G^ {xr'}は常に 1_Qになり、 2G^ {xr'}と 3G^ {xr'}は常に -1_Qなので

C_2' → Yoshiking
-1_Q チョキ/パー
1_Q グー

確率もざっくり1/8で、場合分けも少ない。それに1回目から運ゲーに頼らなくていいのもエレガントすぎる。こういうセンスの良さは脱帽ですね。

自分が粉骨砕身して考えたシナリオが悲しくなってくるので、こちらをコーディングして終わろうと思います。

from pwn import *
import sys

# Legendre記号の実装
def legendre(a, p):
    assert(p % 2 == 1)
    val = pow(a, (p-1)//2, p)
    if val == 1:
        return 1
    elif val == p-1:
        return -1
    else:
        print('QR error')
        sys.exit()
        return 0

# 祈りパート。突破率約1/8
while True:
    # ローカル環境を想定
    io = remote('127.0.0.1', 4000)
    io.recvline()
    msg = io.recvline()[:-1].decode().split(': ')
    # G, Pの取得
    g, p = int(msg[2][:-7]), int(msg[3])
    # 2, 3が平方非剰余になるかどうか
    if legendre(2, p) == -1 and legendre(3, p) == -1:
        print('2 and 3 is QNR! Good!')
        # Gが平方剰余になるかどうか
        if legendre(g, p) == 1:
            print('G is QR! Attack start!')
            break 
    io.close()

win = 0
while win != 100:
    io.recvline()
    msg = io.recvline()[:-1].decode().split('=')[1].split(', ')
    # C_1, C_2の取得(C_1は使わない)
    c1, c2 = int(msg[0][1:]), int(msg[1][:-1])
    io.recv(100)
    # 上の表の部分を実装
    # C_2が平方非剰余ならチョキで引き分け以上確定
    if legendre(c2, p) == -1:
        io.sendline('2')
    # C_2が平方剰余ならパーで勝ち確定
    elif legendre(c2, p) == 1:
        io.sendline('3')
    else:
        print('coding error')
        sys.exit()
    
    io.recvline()
    io.recvline()
    io.recvline()
    msg = io.recvline()
    if b'win' in msg:
        # デバッグ用。勝利数表示
        print(io.recvline())
        win += 1
    
io.recvline()
io.recvline()
print(io.recvline())
io.close()

  1. 余談ですが、rkm0959氏は初手でQRと見抜いています。自分のセンスのなさよ…↩

  2. Legendre記号を考えれば明らかです。↩

  3. もちろん、数学的に正しい表記ではなくこの記事オリジナルの表記です。最初は QRなどで記事を書いていましたが、平方剰余がわからない人からすると見にくいと思ったので導入しました。↩

  4. 決して絶望的な確率ではないです。5分もかからないのでマシンパワーと運を信じましょう。↩