好奇心の足跡

飽きっぽくすぐ他のことをしてしまうので、忘れないため・形にして頭に残すための備忘録。

ångstromCTF 2020 Crypto分野の復習 writeup

2020年 3/14(土)9:00 - 3/19(木)9:00 JST で開催された、ångstromCTFCrypto分野の復習です。CTF Timesはこちら
他の分野のwriteup, 戦績はこちら。

kusuwada.hatenablog.com

Crypto問最後の Lo-Kee はなんかヤバそうな匂いがしたのと、それまでのやつで力尽きたので手つかずです。

f:id:kusuwada:20200426164557p:plain

[Crypto] Keysar

Hey! My friend sent me a message... He said encrypted it with the key ANGSTROMCTF.

He mumbled what cipher he used, but I think I have a clue.

Gotta go though, I have history homework!!

agqr{yue_stdcgciup_padas}

これ、競技中に力技で解いたのですが、他の方のwriteup見ると "Keyed Caesar Cipher" というやつだったみたいです。

文字マップがアルファベット順ではなく、与えられたキーの文字列から始まる文字列+キーに含まれないアルファベットはその後に続く。例えば、keyがTESTKEYだとすると、マップはTESTKEYABCDFGHIJLMNOPQRUVWXZとなる。

下記のページで復号可能。

www.boxentriq.com

[Crypto] one time bad

My super secure service is available now!

Heck, even with the source, I bet you won't figure it out.

nc misc.2020.chall.actf.co 20301

server.pyが配布されます。

import random, time
import string
import base64
import os

def otp(a, b):
    r = ""
    for i, j in zip(a, b):
        r += chr(ord(i) ^ ord(j))
    return r


def genSample():
    p = ''.join([string.ascii_letters[random.randint(0, len(string.ascii_letters)-1)] for _ in range(random.randint(1, 30))])
    k = ''.join([string.ascii_letters[random.randint(0, len(string.ascii_letters)-1)] for _ in range(len(p))])

    x = otp(p, k)

    return x, p, k

random.seed(int(time.time()))

print("Welcome to my one time pad service!\nIt's so unbreakable that *if* you do manage to decrypt my text, I'll give you a flag!")
print("You will be given the ciphertext and key for samples, and the ciphertext for when you try to decrypt. All will be given in base 64, but when you enter your answer, give it in ASCII.")
print("Enter:")
print("\t1) Request sample")
print("\t2) Try your luck at decrypting something!")

while True:
    choice = int(input("> "))
    if choice == 1:
        x, p, k = genSample()
        print(base64.b64encode(x.encode()).decode(), "with key", base64.b64encode(k.encode()).decode())

    elif choice == 2:
        x, p, k = genSample()
        print(base64.b64encode(x.encode()).decode())
        a = input("Your answer: ").strip()
        if a == p:
            print(os.environ.get("FLAG"))
            break

        else:
            print("Wrong! The correct answer was", p, "with key", k)

指定されたホストにつなぐと、こんな感じ。

$ nc misc.2020.chall.actf.co 20301
Welcome to my one time pad service!
It's so unbreakable that *if* you do manage to decrypt my text, I'll give you a flag!
You will be given the ciphertext and key for samples, and the ciphertext for when you try to decrypt. All will be given in base 64, but when you enter your answer, give it in ASCII.
Enter:
    1) Request sample
    2) Try your luck at decrypting something!
> 1
LRoJBQcOIQs5CyUPEBEDGCMjLiEeCjcDMRMkLTo= with key eXF4S3NLWERRTVRGWUJQc2VKbHFNZEZUQXBDeGo=
> 1
OhIkHgocAAoDAw4VEjgeMAw/Ngo4JA== with key anBtd2ZxbWFZaktndHlRanptR011cQ==
> 1
LyoU with key anJx
> 2
Fg==
Your answer: test
Wrong! The correct answer was G with key Q

問題のタイトルとソースコードから、random.seed()が接続後に一度しか呼ばれていないことに起因する、random配列が予測できるところが脆弱っぽい…?
choice = 1を選択したときは、genSample()関数内でrandom.randintを3回呼んでいる。ここで生成したx,p,kは、x,kが出力として返され、px xor kで求めることができる。

choice = 2を選択したときは、与えられたxに対してpを予測し、答えを入れるとflagが表示されるみたい。間違えてもpkを教えてくれる。

  1. まずはrandom.randit()の配列を抽出する
  2. randit()配列を予想する

これで行けないかなー?pythonrandom()関数の予測は

Mersenne Twisterの出力を推測してみる - ももいろテクノロジー

こちらの記事を以前読んだことがありました。

これを参考に、624回rand関数が呼ばれたら、その後のrand関数で生成される関数は予測できそう…。
と思ったんだけど、getrandbits(32)以外の関数・引数だと一致しない。うーむ。

ここで競技終了。

ここから復習

いくつかwriteupを読んでみたところ、2つの解法を見つけました。難しく考えすぎていたか。

  1. randomseedtimeベースなので、ほぼ同時接続して通信させる
  2. kが特定の一文字になる確率が高いことを利用したbrute-force
  3. 比較的レンジが絞られているseedを、Sampleで得られたx,p,kから予測する

せっかくなので全部やってみることにしました。

1.randomのseedがtimeベースなので、ほぼ同時接続して通信させる

random関数のシードがrandom.seed(int(time.time()))と、intで丸めることによって秒単位になった時刻を使っているので、ほぼ同時に接続した通信では同じseedが使用されます。結果、random関数で生成される値も同じになるはずなので、失敗して送られてきた正解をそのまま投げつければ良さそう。

これは思いつきたかったなー!!!!!!

#!/usr/bin/env python3
# -*- coding:utf-8 -*-

from pwn import *

host = "misc.2020.chall.actf.co"
port = 20301

r1 = remote(host, port)
r2 = remote(host, port)

r1.recvuntil(b'> ')
r1.sendline(b'2')
cipher1 = r1.recvuntil(b': ').split(b'\n')[0]
r1.sendline(b'dummy')
res = r1.recv()
ans = res.split(b' ')[5]
key = res.split(b' ')[8]

r2.recvuntil(b'> ')
r2.sendline(b'2')
cipher2 = r2.recvuntil(b': ').split(b'\n')[0]
if cipher1 == cipher2:
    r2.sendline(ans)
    print(r2.recvall())
else:
    print('wrong cipher! c1: ' + cipher1 + ', c2: ' + cipher2)

実行結果

$ python solve.py 
[+] Opening connection to misc.2020.chall.actf.co on port 20301: Done
[+] Opening connection to misc.2020.chall.actf.co on port 20301: Done
[+] Recieving all data: Done (56B)
[*] Closed connection to misc.2020.chall.actf.co port 20301
b'actf{one_time_pad_more_like_i_dont_like_crypto-1982309}\n'
[*] Closed connection to misc.2020.chall.actf.co port 20301

2.kが特定の一文字になる確率が高いことを利用したbrute-force

一つは、genSample()関数内でランダムに生成しているp,kの長さが1~30であり、候補の文字列もlen(string.ascii_letters) = 52程度であることから、1/30 * 1/52 = 1/1560の確率でkが特定の一文字になります。なので一文字でbrute-forceをすれば試行回数が少なく結果が得られそう、というもの。

#!/usr/bin/env python3
# -*- coding:utf-8 -*-

import string
from pwn import *

host = "misc.2020.chall.actf.co"
port = 20301

print(len(string.ascii_letters))

r = remote(host, port)
cnt = 0

while True:
    print('cnt: ' + str(cnt))
    r.recvuntil(b'> ')
    r.sendline(b'2')
    r.recvuntil(b': ').split(b'\n')[0]
    r.sendline(b'a')
    res = r.recvline()
    if b'actf{' in res:
        print(res)
        break
    else:
        cnt += 1
        continue

実行結果

$ python solve2.py 
52
[+] Opening connection to misc.2020.chall.actf.co on port 20301: Done
cnt: 0
~(中略)~
cnt: 109
cnt: 110
b'actf{one_time_pad_more_like_i_dont_like_crypto-1982309}\n'
[*] Closed connection to misc.2020.chall.actf.co port 20301

わーお!期待値を大幅に下回る110回目の思考でflagが手に入りました。ラッキー!

3.比較的レンジが絞られているseedを、Sampleで得られたx,p,kから予測する

x,p,kの生成アルゴリズムが公開されていること、randomとは言え時刻ベースのseedを使っているので、seedのレンジがある程度予測できることから(サーバーの時刻が大きくずれていなければ)、seedをlocalのbrute-forceで予測し、次のx,p,kを生成する解法。

#!/usr/bin/env python3
# -*- coding:utf-8 -*-

import string
import base64
from pwn import *

def otp(a, b):
    r = ""
    for i, j in zip(a, b):
        r += chr(ord(i) ^ ord(j))
    return r

def genSample():
    p = ''.join([string.ascii_letters[random.randint(0, len(string.ascii_letters)-1)] for _ in range(random.randint(1, 30))])
    k = ''.join([string.ascii_letters[random.randint(0, len(string.ascii_letters)-1)] for _ in range(len(p))])

    x = otp(p, k)

    return x, p, k

host = "misc.2020.chall.actf.co"
port = 20301

print(len(string.ascii_letters))

r = remote(host, port)
cnt = 0

r.recvuntil(b'> ')
r.sendline(b'1')
res = r.recvuntil(b'> ')
x = base64.b64decode(res.split(b' ')[0]).decode()
k = base64.b64decode(res.split(b' ')[3]).decode()
p = otp(x, k)

for t in range(int(time.time())-20, int(time.time())+20):
    random.seed(t)
    my_x, my_p, my_k = genSample()
    if my_k == k:
        print('seed: ' + str(t))
        break

next_x, next_p, next_k = genSample()

r.sendline(b'2')
r.recvuntil(b': ')
r.sendline(next_p)
print(r.recvline())

実行結果

$ python solve3.py 
52
[+] Opening connection to misc.2020.chall.actf.co on port 20301: Done
seed: 1586233716
b'actf{one_time_pad_more_like_i_dont_like_crypto-1982309}\n'
[*] Closed connection to misc.2020.chall.actf.co port 20301

わー!こんなに色んな解法があるのに一つも思いつかなかったとは!面白いなー。

[Crypto] Discrete Superlog

You've heard of discrete log...now get ready for the discrete superlog.

Server 1: nc crypto.2020.chall.actf.co 20603

Server 2: nc 3.234.224.95 20603

Server 3: nc 3.228.7.55 20603

Hint

just do it lmao

それぞれのサーバーに接続してみます。全部同じような文言が出てきました。Serverがたくさんあるのは予備かな?

$ nc crypto.2020.chall.actf.co 20603
We define a^^b to be such that a^^0 = 1 and a^^b = a^(a^^(b-1)), where x^y represents x to the power of y.
Given this, find a positive integer x such that a^^x = b mod p.
Generating challenge 1 of 10...
p = 723016406727943930447
a = 564447721002380463960
b = 642755755056058439913
Enter x: 

これも競技中に、当てずっぽうと力ずくで解いたのですが、writeupを見ておさらい。

この問題、自分のwriteupにも書いたとおり

a^(a^^(x-1))....と展開していって、x-1 -> 0 になるまで繰り返し、その結果が b mod p になるようなxを求める。

となります。この計算のことを"テトレーション"と呼ぶらしい。

テトレーション(英: tetration)とは、冪乗の次の 4 番目のハイパー演算である。つまり、自らの冪乗を指定された回数反復する二項演算である。超冪(ちょうべき)ともいうが、この語は n ≥ 4 番目の一般のハイパー演算を総称するために用いられることもある。

ほえー!知らなかった。
数学はちゃんと勉強したこと無いので、数式の中に ↑↑ とか出てきたら「アゲアゲ?」ってなっちゃうな…。

べき乗(冪乗)は

a^b = a↑b = a \times a \times \cdots \times a

それに対して、テトレーションは

^ba = a↑↑b = a↑a↑ \cdots ↑ a = {a^{a^{\cdots^a}}}

と展開できます。なので、今回の問題を数式にして表現すると、


^{x}a = b \bmod p

となるxを求めよ、という問題らしい。

普通にtetrationの値を求めようとすると、再帰を用いて

def tetration(a, x):
    if x == 0:
        return 1
    else:
        return pow(a, tetration(a, (x-1)))

のように実装できます。しかしこれでは計算量が爆発してしまい、x=2までくらいしか計算できない。
そこで、

フェルマーの小定理を拡張した、オイラーの定理を使うことで、計算量を抑えることを試みます。

フェルマーの小定理自体は、

p素数とし、ap の倍数でない整数(ap は互いに素)とする時に、

a^{p-1} ≡ 1\ \pmod{p}

すなわち、ap-1 乗を p で割った余りが1になる。

a^{p-1} \bmod p = 1

このフェルマーの小定理を拡張したオイラーの定理は、フェルマーp素数という条件だったのに対し、これを合成数に拡張したもの。

n を正の整数とし、an と互いに素な整数としたとき、

a^{φ(n)} ≡ 1\ \pmod{n}

すなわち、aφ(n) 乗を n で割った余りが1になる。

a^{φ(n)} \bmod n = 1

ここで、φ(n)オイラー関数(totient関数)と言い、正の整数 n に対して、 n と互いに素である 1 以上 n 以下の自然数の個数 φ(n) を与える数論的関数のこと。
例えば、1, 2, 3, 4, 5, 6 のうち 6 と互いに素なのは 1, 52 個であるから、定義によれば φ(6) = 2 である。また例えば 1, 2, 3, 4, 5, 6, 7 のうち 7 以外は全て 7 と互いに素だから、φ(7) = 6

totientについては、pythonだと下記のライブラリで高速に求めることができます。

Number Theory — SymPy 1.5.1 documentation

フェルマーの小定理オイラーの定理については、下記の記事がとてもわかり易かった。

フェルマーの小定理の証明と使い方 - Qiita

更に、オイラーの定理より a^φ(n) % n == 1 と、周期的に1になり、その周期がφ(n)なので

a^{x}\ \%\ n\ =\ a^{x\ \%\ φ(n)}\ \%\ n

が成り立ちます。

今回の問題に当てはめてみると、求めたい a↑↑x % p

^xa\ \%\ p\ =\ a^{T(a,x-1)}\ \%\ p

T(a,x)\ =\ ^xa\ \ \ (=\ a↑↑x)

と表すことが出来ます。※ \bmod%で表記しています。

さらに、オイラーの定理より

a^{T(a,x-1)}\ \%\ p=\ a^{T(a,x-1)\ \%\ φ(p)}\ \%\ p

なので、

^xa\ \%\ p\ =\ a^{T(a,x-1)}\ \%\ p\\
\ \ \ \ \ \ \ \ \ \ \ =\ a^{T(a,x-1)\ \%\ φ(p)}\ \%\ p\\
\ \ \ \ \ \ \ \ \ \ \ =\ a^{a^{T(a,x-2)\%φ(φ(p))}}\ \%\ p\\
\ \ \ \ \ \ \ \ \ \ \ \cdots

と表すことができ、再帰で表現できそうです。
先程のテトレーションを純粋に求めるプログラムをちょっと変更して

from sympy.ntheory import totient

def tetoration_mod(a, x, p):
    if p == 1 or x == 0:
        return 1
    return pow(a, tetoration_mod(a, x-1, totient(p)), p)

これで計算できそう。

あとは、問題文から各値を読み込んで10回xを求めてみます。

#!/usr/bin/env python3
# -*- coding:utf-8 -*-

from pwn import *
from sympy.ntheory import totient

def tetoration_mod(a, x, p):
    if p == 1 or x == 0:
        return 1
    return pow(a, tetoration_mod(a, x-1, totient(p)), p)

host = "crypto.2020.chall.actf.co"
port = 20603

r = remote(host, port)

for i in range(10):
    r.recvuntil(b'of 10...\n')
    p = int(r.recvline().split(b' ')[2].strip())
    a = int(r.recvline().split(b' ')[2].strip())
    b = int(r.recvline().split(b' ')[2].strip())
    r.recvuntil(b'Enter x: ')
    
    x = 0
    while True:
        if tetoration_mod(a, x, p) == b:
            break
        x += 1
    print(str(i) + 'th x: ' + str(x))
    r.sendline(str(x).encode())
    ans = r.recvline()
    if ans == b'Correct!\n':
        continue
    else:
        print(ans)
print(r.recvall())

実行結果 

$ python solve.py 
[+] Opening connection to crypto.2020.chall.actf.co on port 20603: Done
0th x: 6
1th x: 7
2th x: 8
3th x: 4
4th x: 4
5th x: 3
6th x: 7
7th x: 2
8th x: 13
9th x: 3
[+] Recieving all data: Done (50B)
[*] Closed connection to crypto.2020.chall.actf.co port 20603
b'flag: actf{lets_stick_to_discrete_log_for_now...}\n'

(๑•̀ㅂ•́)و✧

ところで、なぜ力ずく解法が通ったのかは不明。大きな値を入れることで、サーバー側に付加をかけ、timeout = 正解!を狙った感じになっちゃったのかな?申し訳ない…。 参考にさせてもらったwriteup

[Crypto] Confused Streaming

I made a stream cipher!

nc crypto.2020.chall.actf.co 20601

chall.pyが配布されます。

from __future__ import print_function
import random,os,sys,binascii
from decimal import *
try:
    input = raw_input
except:
    pass
getcontext().prec = 1000
def keystream(key):
    random.seed(int(os.environ["seed"]))
    e = random.randint(100,1000)
    while 1:
        d = random.randint(1,100)
        ret = Decimal('0.'+str(key ** e).split('.')[-1])
        for i in range(d):
            ret*=2
        yield int((ret//1)%2)
        e+=1
try:
    a = int(input("a: "))
    b = int(input("b: "))
    c = int(input("c: "))
    # remove those pesky imaginary numbers, rationals, zeroes, integers, big numbers, etc
    if b*b < 4*a*c or a==0 or b==0 or c==0 or Decimal(b*b-4*a*c).sqrt().to_integral_value()**2==b*b-4*a*c or abs(a)>1000 or abs(b)>1000 or abs(c)>1000:
        raise Exception()
    key = (Decimal(b*b-4*a*c).sqrt() - Decimal(b))/Decimal(a*2)
except:
    print("bad key")
else:
    flag = binascii.hexlify(os.environ["flag"].encode())
    flag = bin(int(flag,16))[2:].zfill(len(flag)*4)
    ret = ""
    k = keystream(key)
    for i in flag:
        ret += str(next(k)^int(i))
    print(ret)

b*b - 4*a*cおや、この公式どこかで見たことがあるぞ…。なんだっけ…。2次方程式の解の公式だ!
コメントの部分に、"これらの厄介な虚数有理数、ゼロ、整数、大きな数などを削除します"とあるので、それ以外のa,b,cの組み合わせを探す。

abs(a)>1000 or abs(b)>1000 or abs(c)>1000

だと落ちるので、a,b,c の絶対値は 1000 以下。

Decimal(b*b-4*a*c).sqrt().to_integral_value()**2!=b*b-4*a*c

の条件に合うa,b,cを入力すると、flagをkeystream(key)関数で生成したkとxorを取ったflagが出力される。条件をまとめるとこんな感じ。

  • b*b > 4*a*c
  • a != 0, b != 0, c != 0
  • Decimal(b*b-4*a*c).sqrt().to_integral_value()**2 != b*b-4*a*c
  • a,b,c の絶対値は 1000 以下

  • 上記の条件に合うa,b,cを考える

  • keystream(key)関数からkを推測する(ただしrandom関数が使われている…!)
  • 出力とkをxorする

条件似合いそうなa,b,cを与えてみます。

$ nc crypto.2020.chall.actf.co 20601
a: -1
b: 2
c: 1
01100001011000110111010001100110011110110110010001101111011101110110111001011111011101000110111101011111011101000110100001100101010111110110010001100101011000110110100101101101011000010110110001111101

おお、なんか一個もらえた。んー、でもkを推測するのが難しそう。なんとかk=0にならんかな?

ここから復習

ここで競技時間は終了してしまいましたが、なんとこれflagだった…orz。

from Crypto.Util.number import *

stream = '01100001011000110111010001100110011110110110010001101111011101110110111001011111011101000110111101011111011101000110100001100101010111110110010001100101011000110110100101101101011000010110110001111101'

print(long_to_bytes(int(stream,2)))

実行結果

$ python solve.py 
b'actf{down_to_the_decimal}'

ただ、原理を理解して得られたわけではないのでちゃんと復習する。

ここから復習

これ、keystream()関数で生成されるkは常に0にできる条件を使っていたのでした。

keyに0.5以下の値が渡されると、

ret = Decimal('0.'+str(key ** e).split('.')[-1])

において、key ** eが非常に小さくなり、Decimal('0.'+str(key ** e).split('.')[-1])自体も、とても小さい値になります。(2.3E-340など)

for i in range(d):
            ret*=2

retに対して施されますが、deに比べて小さすぎるために

yield int((ret//1)%2)

は常に int(({1以下の値}//1)%2)となり、0が返ります。結果、flag xor 0の結果が表示されているので、これをint to byte decodeすればflagそのものだったというわけ。

なんとかk=0にならんかな?

なっとった!

原理がわからなくても、chall.pyをlocalで動かして挙動を確認し、key,kにどんな値が入ってくるかを観察すれば解けたかもしれない。(localで用意したflagのbinと出力が同じである、常にk=0になっている、などが確認できたため。)edの出力まではlocalで挙動を確認していたが、その結果kretがどうなっているかは確認していなかった。残念。

さらに、下の Dream Stream で別解、というか想定解を見たので記録。

[Crypto] Dream Stream

I made my stream cipher better.

nc crypto.2020.chall.actf.co 20602

chall.pyが配布されます。

from __future__ import print_function
import random,os,sys,binascii
from Crypto.Util.number import isPrime
from decimal import *
try:
    input = raw_input
except:
    pass
getcontext().prec = 3000
def keystream(key):
    random.seed(int(os.environ["seed"]))
    p = random.randint(3,30)
    while not isPrime(p):
        p = random.randint(3,30)
    e = random.randint(50,600)
    while 1:
        d = random.randint(10,100)
        ret = Decimal('0.'+str(key ** e).split('.')[-1])
        for i in range(d):
            ret*=2
        yield int((ret//1)%2)
        e+=p
try:
    a = int(input("a: "))
    b = int(input("b: "))
    c = int(input("c: "))
    # added some more weak key protections
    if b*b < 4*a*c or [a,b,c].count(0) or Decimal(b*b-4*a*c).sqrt().to_integral_value()**2==b*b-4*a*c or abs(a)>400 or abs(b)>500 or abs(c)>500:
        raise Exception()
    key = (Decimal(b*b-4*a*c).sqrt() - Decimal(b))/Decimal(a*2)
    if 4*key*key<5 or abs(key-key.to_integral_value())<0.05:
        raise Exception()
except:
    print("bad key")
else:
    flag = binascii.hexlify(os.environ["flag"].encode())
    flag = bin(int(flag,16))[2:].zfill(len(flag)*4)
    ret = ""
    k = keystream(key)
    for i in flag:
        ret += str(next(k)^int(i))
    print(ret)

Confused Streamingの続きっぽい。接続してみると

$ nc crypto.2020.chall.actf.co 20602
a: 1
b: 2
c: 3
bad key

出てくる文言も同じ様子。競技期間中は、「まずはConfused Streamingだな…」というメモを最後に終わっている…。

ここから復習

Confused Streamingからの変更点をソースから追ってみます。
まずは、a,b,cの入力値の評価について、Confusedの方では

remove those pesky imaginary numbers, rationals, zeroes, integers, big numbers, etc

との注意書きがありました。Dreamのほうは

added some more weak key protections

とあります。変更されている評価は、Exception発生の条件として

abs(a)>1000 or abs(b)>1000 or abs(c)>1000

から

abs(a)>400 or abs(b)>500 or abs(c)>500

に。その後、keyを生成してから

if 4*key*key<5 or abs(key-key.to_integral_value())<0.05:
        raise Exception()

の評価が追加になっています。

この

4k^{2} \geqq 5の条件が加わったので、key\frac{\sqrt{5}}{2}より大きい必要があり、先程 Confused Stream で使った手が使えません。

ここでwriteupを探してみましたが、CTF Timeにも載っていません…。問題自体Tasksにもなかったので、無かったことになっている??
唯一、Discordに公式writeupがあがっていました。

Confused Streaming/Dream Stream: Note that a, b, and c are being used as coefficients that are plugged into the quadratic formula to get the key. The bits of the keystream are taken from random bits in the fractional part of key^n, where n increases by an odd number. Plugging in a = 1, b = -2, c = -2 gives the key k = 1+sqrt(3). This has the nice property that k^n gets closer and closer to an integer as n increases. In fact, it flip-flops between being just over an integer and just under an integer (proof below). So, the bits of the keystream alternate between 1 and 0. Thus, we XOR the output with 01010101... or 10101010... to get the flag.

Proof of the nice property: Consider (1+sqrt(3))^n + (1-sqrt(3))^n. If we expand both of the binomials, the terms with sqrt(3) all cancel out. So, this expression approaches an integer. However, note that -1 < 1-sqrt(3) < 0, so (1-sqrt(3))^n approaches 0, alternating between just greater than 0 and just less than 0. Therefore, (1+sqrt(3))^n alternates between being just greater than an integer and just less than an integer.

edit: it has come to my attention that 1,-2,-2 may produce an error. In that case, any other key with the property described above works; you just need to find one that does (there are a lot that work).

Unintended solution for Confused Streaming: make the key between 0 and 1 so that it approaches 0

ぱっとこれを読んだだけではわからなかったので、読み解いていきました。
更に、この解法ではない組み合わせでもflagが取れたので、そちらも。多分こっちでflagが取れたチームのほうが多かったのでは。

  1. 想定解法k=010101...ork=101010...になる組み合わせを使う
  2. k=1になる組み合わせを使う

想定解法k=010101...ork=101010...

今回の制約を数式に表すと

  • b^{2} \geqq 4ac
  • a \neq 0, b \neq 0, c \neq 0
  • \sqrt{b^{2} - 4ac} を整数に丸めたものの2乗 \neq b^{2} - 4ac
  • |a|\leqq 400, |b|\leqq 500, |c|\leqq 500
  • 4key^{2} \geqq 5
  • |keyの小数部分| > 0.05

となっています。keystream関数で返却される値は0,1のどちらかとなっており、

  • eは範囲 50~600 のランダムな整数
  • dは範囲 10~100 のランダムな整数
  • pは 3~30 の範囲のランダムな素数

の時に

ret = \left\{ 0.(key^{e}の小数点以下) \right\} \times 2^{d}

を計算し、retを小数点以下で切り捨てて整数にした値(k)が

  • 奇数なら 1
  • 偶数なら 0

が返却されます。

Confused Streamingでは、|key|を小さくすることで、key^{e}を0に収束させ、dの値が比較的小さいことから \times 2^{d}の影響を小さくし、常にretが正の0に限りなく近い状態、kを0に固定することで解けました。

今回は先程も述べたとおり、4k^{2} \geqq 5の条件が加わったので、key\frac{\sqrt{5}}{2}より大きい必要があり、0に収束させることが出来ません。

ここで先程の公式解法より。唐突ですが、[1, -2, -2][a, b, c]の入力として与えることを考えます。このとき、

 key = \frac{\sqrt{4+8} + 2}{2}\\
\ \ \ \ \ = 1+\sqrt{3}

となります。無理数平方根有理数の加算になっていますが、このような数において以下のような性質があります。

\ \ \ (1+\sqrt{3}) + (1-\sqrt{3}) = 1 + \sqrt{3} + 1 - \sqrt{3} = 2 \\
(1+\sqrt{3})^{2} + (1-\sqrt{3})^{2} = 1 + 2\sqrt{3} + 3  + 1 - 2\sqrt{3} + 3 = 8 \\
(1+\sqrt{3})^{3} + (1-\sqrt{3})^{3} = 16 \\
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots \\
(1+\sqrt{3})^{n} + (1-\sqrt{3})^{n} = I\ (整数)

平方根の部分がキャンセルされるので、常に整数になります。
更に、-1 \lt 1 - \sqrt{3} \lt 0、すなわち | 1 - \sqrt{3} | \lt 1, 1-\sqrt{3} \lt 0であるため、

(1-\sqrt{3})^{n} \Rightarrow 0\ \ (n \to \infty)

nが増えるにつれて0に収束していきます。更に、後者の条件より

(1-\sqrt{3})^{n+1} = (1-\sqrt{3})^{n} \times (1-\sqrt{3})

で負の数 (1-\sqrt{3})(1-\sqrt{3})^{n} に掛けることになるので、±が逆転します。

以上の条件をまとめると

  • (1+\sqrt{3})^{n} + (1-\sqrt{3})^{n} = I\ (整数)
  • (1-\sqrt{3})^{n} \Rightarrow 0\ \ (n \to \infty)
  • (1-\sqrt{3})^{n+1} の符号は (1-\sqrt{3})^{n} の反対になる

以上のことより、

(1+\sqrt{3})^{n} \Rightarrow I\ (整数)\ \ (n \to \infty)

であり、さらに 整数Iの上下を行き来しながら収束する性質があることがわかります。(I + 0.000000..., I - 0.000000....)
よって、key1+\sqrt{3}の場合、

\left\{ 0.(key^{e}の小数点以下) \right\}

は、eが十分大きく、1ずつ増える時、0.0000000...(0に限りなく近い正の値)と0.9999999....(1に限りなく近い1以下の値)を交互に取りながら01に収束していくことがわかります。
今回、eは1ずつ増えるのではなくp、すなわちランダムな3~30の間の素数ずつ増えますが、pは奇数なため、eは奇数と偶数を交互に繰り返します。このため、やはり 0+ \Delta d1- \Delta d を交互に繰り返すことになります。

更にこのあと、\times 2^{d} が待っています。
0に収束する場合は、eよりdが十分小さい場合はこの 2d は無視できますが、1に収束する方はこの影響を大きく受けるはずです。ぱっと見、dがランダムなため、値が不定になってしまうように見えます。

ここで1に収束する値を、1-\Delta d と置いてみます。

(1-\Delta d) \times 2^{d} =2^{d} - \Delta d \times 2^{d} \\
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =2n - \Delta d \times 2^{d}

ここで、\Delta d \times 2^{d} (\to 0) で、0に限りなく近い正の値になるため、上記の式の値は 奇数.99999....となります。
これをint()で少数以下切り捨ての整数にするため、retは必ず奇数になり、1が返ることがわかります。

以上のことより、key有理数平方根で表現され、有理数 - 平方根 (key') が-1 \lt key \lt 0 の範囲に設定できれば、k01010...もしくは10101...の形になり、これと出力をxorすることでflagが求まります。

※残念ながら、2020/4/15現在、サーバーが正常に動いていないようなのでローカルでやることに。環境変数を設定するとlocalでも実行可。

$ export flag="kswd{this_is_local_flag!}"
$ export seed="10"
$ python chall.py 
a: 1
b: -2
c: -2
001111100010011000100010001100010010111000100001001111010011110000100110000010100011110000100110000010100011100100111010001101100011010000111001000010100011001100111001001101000011001000101000
from Crypto.Util.number import *

stream = '001111100010011000100010001100010010111000100001001111010011110000100110000010100011110000100110000010100011100100111010001101100011010000111001000010100011001100111001001101000011001000101000'

xor1 = ''
xor2 = ''
i = 0
for b in stream:
    xor1 += str(int(b) ^ (i%2))
    xor2 += str(int(b) ^ ((i+1)%2))
    i += 1

print(long_to_bytes(int(xor1,2)))
print(long_to_bytes(int(xor2,2)))

実行結果

$ python solve.py 
b'kswd{this_is_local_flag}'
b'\x94\x8c\x88\x9b\x84\x8b\x97\x96\x8c\xa0\x96\x8c\xa0\x93\x90\x9c\x9e\x93\xa0\x99\x93\x9e\x98\x82'

\(*ˊᗜˋ*)/
これをサーバーに対して実行できれば、flagが得られたはず。

k=1になる組み合わせを使う解法

今度は入力値[1, -3, 1]としてみます。このとき、

 key = \frac{\sqrt{9-4} + 3}{2} \\
\ \ \ \ \ = \frac{3}{2} + \frac{\sqrt{5}}{2} \\
\ \ \ \ \ \fallingdotseq 2.6

上記と同様、おもむろに (\frac{3}{2} + \frac{\sqrt{5}}{2})^{n} + (\frac{3}{2} - \frac{\sqrt{5}}{2})^{n} を考えてみます。

\frac{3}{2} - \frac{\sqrt{5}}{2} \fallingdotseq 0.38

のため、今度は 0 \lt \frac{3}{2} - \frac{\sqrt{5}}{2} \lt 1 です。

前項の想定解のとき見た性質より、

  • (\frac{3}{2} + \frac{\sqrt{5}}{2})^{n} + (\frac{3}{2} - \frac{\sqrt{5}}{2})^{n} = I\ (整数)
  • (\frac{3}{2} - \frac{\sqrt{5}}{2}) \Rightarrow 0\ \ (n \to \infty)
  • (\frac{3}{2} - \frac{\sqrt{5}}{2})^{n+1} の符号は (\frac{3}{2} - \frac{\sqrt{5}}{2})^{n} と同じ

以上より、

(\frac{3}{2} + \frac{\sqrt{5}}{2})^{n} = I - ([tex:(\frac{3}{2} - \frac{\sqrt{5}}{2})^{n} \\
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \Rightarrow I - 0.0000....\ \ (n \to \infty)

と、整数Iよりわずかに小さい値に収束します。
ここからは先程の想定解法のときと同じく、\times 2^{d} して小数部分を切り捨てて整数にすると、この結果は必ず奇数になるため、kは必ず1が返ります。

よって、key有理数平方根で表現され、有理数 - 平方根 (key') が 0 \lt key' \lt 1 の範囲のに設定できれば、k1に固定され、これと出力をxorすることでflagが求まります。

$ export flag="kswd{this_is_local_flag!}"
$ export seed="10"
$ python chall.py 
a: 1
b: -3
c: 1
100101001000110010001000100110111000010010001011100101111001011010001100101000001001011010001100101000001001001110010000100111001001111010010011101000001001100110010011100111101001100010000010
from Crypto.Util.number import *

stream = '100101001000110010001000100110111000010010001011100101111001011010001100101000001001011010001100101000001001001110010000100111001001111010010011101000001001100110010011100111101001100010000010'

xor = ''
for b in stream:
    xor += str(int(b) ^ 1)

print(xor)
print(long_to_bytes(int(xor,2)))

実行結果

$ python solve.py 
011010110111001101110111011001000111101101110100011010000110100101110011010111110110100101110011010111110110110001101111011000110110000101101100010111110110011001101100011000010110011101111101
b'kswd{this_is_local_flag}'

\(*ˊᗜˋ*)/
想定解法じゃないけど、こっちで解けたチームのほうが多そう。
競プロ勢は、日々こういう問題に取り組んでるのかな。この手の問題は常識レベル??

今回の問題は、別解に使える入力を弾きそびれたのかな?何れにせよ、普段数式見たり考えたりすることないので、とても面白かったです。
実際競技中に解こうと思うと、chall.pyがせっかく配布されているので、ローカルで動かしながら挙動を観察、kがどのような値をとっているかを確認すればよかったかなぁと思います。

[Crypto] RSA-OTP

RSA is kinda bad but I strengthened it with the unbreakable one time pad!

nc crypto.2020.chall.actf.co 20600

Hint

What information does the server tell you?

今回も chall.pyが配布されます。

from Crypto.Util.number import bytes_to_long
from Crypto.Random.random import getrandbits # cryptographically secure random get pranked
from Crypto.PublicKey import RSA
from secret import d, flag
# 1024-bit rsa is unbreakable good luck
n = 136018504103450744973226909842302068548152091075992057924542109508619184755376768234431340139221594830546350990111376831021784447802637892581966979028826938086172778174904402131356050027973054268478615792292786398076726225353285978936466029682788745325588134172850614459269636474769858467022326624710771957129
e = 0x10001
key = RSA.construct((n,e,d))

f = bytes_to_long(bytes(flag,'utf-8'))
print("Encrypted flag:")
print(key.encrypt(f,0)[0])

def otp(m):
    # perfect secrecy ahahahaha
    out = ""
    for i in bin(m)[2:]:
        out+=str(int(i)^getrandbits(1))
    return out

while 1:
    try:
        i = int(input("Enter message to sign: "))
        assert(0 < i < n)
        print("signed message (encrypted with unbreakable otp):")
        print(otp(key.decrypt(i)))
    except:
        print("bad input, exiting")
        break

とりあえず n素因数分解しようとしてみたが、msieveでは桁が大きすぎて扱えないエラーが。factordb.comでも全く分解できませんでした。

指定のホストに接続してみると、flagをencryptしたものを表示してくれます。

$ nc crypto.2020.chall.actf.co 20600
Encrypted flag:
17482644844951175640843255713372869422739097498066773957636359990466096121278949693816080016671592558403643716793132479255285512907247513385850323834210899918531077167485767118313722022095603863840851451191536627814100144146010392752308431038754246815068245448456643024387011488032896209253644172833489422733

そのあと、Enter message to sign: で整数を入力すると、これを key.decrypt() -> otp() の順で処理した値を表示してくれます。

perfect securityらしいotp(m)はただのxorなので、getrandbits(1)が何かわかれば再度xorしてあげるだけで逆算できるはず…なのですが、getrandbits(1)が文字通りランダムなのでわかりません。

とりあえず、教えてもらったEncrypted flagをそのまま突っ込んでみます。

$ nc crypto.2020.chall.actf.co 20600
Encrypted flag:
17482644844951175640843255713372869422739097498066773957636359990466096121278949693816080016671592558403643716793132479255285512907247513385850323834210899918531077167485767118313722022095603863840851451191536627814100144146010392752308431038754246815068245448456643024387011488032896209253644172833489422733
Enter message to sign: 17482644844951175640843255713372869422739097498066773957636359990466096121278949693816080016671592558403643716793132479255285512907247513385850323834210899918531077167485767118313722022095603863840851451191536627814100144146010392752308431038754246815068245448456643024387011488032896209253644172833489422733
signed message (encrypted with unbreakable otp):
0001000100011111100101000110111000011101010000001011000011110111100101111011110001000011111000011010101011010010001110100101010111110111110000100110101110010001001100100001010111111101110001010101011111101011011110001111100101110000011010011000110010110011001000111101011110101001100101000000110011010100100100111100010001110011010111111111100111010110010011101000111001101011001101000111000011100100010100001101110000011010011111000110111000110101101101111011011111000011000010100001010000000111010101110101010101111000010111100010101111011011001011101001001

flagをdecryptした結果…をランダムなbitsでxorした結果が得られました。でもやっぱりgetrandbits(1)がわからないので、これを復元できる気がしません…。もちろん、突っ込むたびに返ってくるbit列が変わってしまいます。

このあと、getrandbits(1)の出目予想が出来ないかなど色々試してみましたが、どれもうまく刺さりませんでした。

与えられている情報は、ソースよりne、そして暗号化されたflagcneがあれば公開鍵を構築できるので、公開鍵も与えられていることになります。あとは、好きな暗号文を与えると、復号して更にランダムなbit列でxorしたものも得られます。
一体これらの情報で、どうやったら平文が得られるんだろう🤔

ここから復習

他のwriteupを読んだところ、今回の問題ではOracle攻撃というのが使える様子。Oracle攻撃といえばPadding Oracleが有名です。Oracle攻撃の概要はこちらがわかりやすかったです。

用語解説:オラクル攻撃 - Qiita

writeupは、下記の4つが見つかりました。

実際のところ全部の解法を読んで理解を試みましたが、ソルバがあるけど解説がないもの、解説があるけどソルバがないもの、解説とソルバはあるけどflagが最後まで取得できなかったもの、という感じで結構厳しい。

最終的には、4つ目の解法がなんとか理解できそうだったので、この解法でやってみます。また、動くソルバを書いた&途中まで理解したので、公式解法についても中途半端ですが残しておきます。

  • LSB Oracle Attack っぽい解き方
  • 公式解法っぽい解き方(未完成)

LSB Oracle Attack っぽい解き方

ヒントの What information does the server tell you? というやつ。そりゃ当たり前だわ、サーバーが返す値を見ないことには始まらないわ、と思って無視してたんですけど、さすがヒント、これが大事だったようです。

結局、otpの処理を施して返却される値は、otp処理でランダムなビット配列とxorされてしまっており、元に戻すことは不可能です。他に得られる情報で、xorの結果、変わらない情報が「長さ」。突っ込んだmessageをdecryptした結果の長さがわかります。
先程試してみた、encryptoされたflagを突っ込んでdecrypt,otp処理をした結果の出力では、559bitsが返ってきています。otp処理では長さは変わらないはずなので、flagの平文mのbit長は559ビットということになります。

以下、まずは一般的な LSB Oracle Attack について考えてみます。
ほかの方のwriteup読んでも何故そうなるかさっぱりわからなかったのですが、こちらのサイトの解説のおかげで、まずは LSB Oracle Attack について理解することが出来ました。とても丁寧でわかりやすくてありがたい。

LSB Decryption Oracle Attack - ごちうさ民の覚え書き

以下、上記のブログの内容ほぼそのままなので、元の記事を見ていただくのが良いかと。途中から今回の問題に当てはめるために、こちらにも写経させていただきます。

RSA暗号の公式をおさらいすると、cが暗号文、mが平文の場合、

c=m^{e} \bmod n (c = pow(m, e, n)),

m=c^{d} \bmod n (m = pow(c, d, n)) (※dはinverse, eの逆元)

また、decryptした結果について得られる情報があることから、このEnter message to sign:に値を突っ込んで返してもらう機能をOracleと呼ぶことにします。

LSB Oracle Attack では、Oracleを関数f(x)とすると、

f(x)=dec(x) \bmod 2

と、復号した結果が偶数か奇数か、すなわち最終ビットが0か1かがわかる場合に有効です。ここで、

a=2^{e} \bmod n

とすると、

f(a^{i}c) = dec(a^{i}c) \bmod 2\\
\ \ \ \ \ \ \ \ \  = \left\{ \left ((a^{i}c) \bmod n \right)^{d} \bmod n \right\} \bmod 2 \\
\ \ \ \ \ \ \ \ \  = \left\{ \left ((a^{id} \bmod n)(c^{d} \bmod n) \right) \bmod n \right\} \bmod 2 \\
\ \ \ \ \ \ \ \ \  = ((a^{id}m) \bmod n) \bmod 2\\
\ \ \ \ \ \ \ \ \  = ((2^{ied}m) \bmod n) \bmod 2\ \ \ \ (a=2^{e} \bmod n より)\\
\ \ \ \ \ \ \ \ \  = \left\{ \left((2^{ed})^{i} \bmod n \right) \left( m \bmod n \right) \bmod n \right\} \bmod 2\\
\ \ \ \ \ \ \ \ \  = (2^{i}m \bmod n) \bmod 2

と展開できます。また、RSA暗号の性質より

  • nは奇数 (大きい素数(≠2)、p, qの積であるため)
  • 0 \leqq m \lt n\ \ \ (mはnより小さい正の数)
  • 0 \leqq m \lt 2(n-1)\ \ \ (n>2)

最後の条件は、n>2よりn \lt 2(n-1)が成り立つため、 m \lt n \lt 2(n-1) から説明できる。

ここで、i=1の時を考えてみます。

f(ac) = (2m \bmod n) \bmod 2

すなわち、2m % nが偶数か奇数か。ここで、先程のmのレンジの制約より、 2m \div nの商は01になります。また、2mは偶数、nは奇数のため、2m % n

  • 偶数の場合:
    • 商は0
    • 2m \leqq n
    • 2m \bmod n = 2m
  • 奇数の場合:
    • 商は1
    • 2m > n
    • 2m \bmod n = 2m - n

であることがわかります。

次に、i=2の時を考えてみます。

f(a^{i}c) = (2^{2}m \bmod n) \bmod 2\\
\ \ \ \ \ \ \ \ \ = (4m \bmod n) \bmod 2

i=1のときの結果を利用して、下記のように展開できます。

f(ac) = 1 かつ f(a^{2}c) = 1 のとき

f(a^{2}c) = (2(2m \bmod n) \bmod n) \bmod 2\\
\ \ \ \ \ \ \ \ \ \ = (2(2m-n) \bmod n) \bmod 2\ \ \ \ (i=1 のときの 2m /bmod n = 2m - n より)\\
\ \ \ \ \ \ \ \ \ \ = (4m - 2n - n) \bmod 2\ \ \ \ (今回も商が1になるため)\\
\ \ \ \ \ \ \ \ \ \ = (4m - 3n) \bmod 2\ \ \ \ (=1)

このように、他のケースについても展開して考えると

  • f(ac)=1, f(a2c)=1の場合:
    • 3/4 n \lt m \leq n
  • f(ac)=1, f(a2c)=0の場合:
    • 1/2 n \lt m \leq 3/4 n
  • f(ac)=0, f(a2c)=1の場合:
    • 1/4 n \lt m \leq 1/2 n
  • f(ac)=0, f(a2c)=0の場合:
    • 0 \lt m \leq 1/4 n

i=3以降も上記を繰り返すことにより、平文mの範囲を2文探索の要領で狭めていき、最終的に上限と下限の差分が1以下になったらmが求まります。

今回の問題では、Oraclef(x)f(x) = dec(x) % 2 ではなく f(x) = dec(x).bit_length です。このとき、

f(a^{i}c) = (2^{i}m \bmod n)\ の\ bit長

であり、mのレンジに関する性質は変わりません。

ここで、i=1の時を考えてみます。

f(ac) = (2m \bmod n)\ の\ bit長

今回もmのレンジの制約より、 2m \div nの商は01になります。また、2mは偶数、nは奇数のため、2m % nのbit長u

  • mのbit長より大きい(+1)場合:
    • 商は0
    • 2m \leqq n
    • 2m \bmod n = 2m
  • それ以外の場合:
    • 商は1
    • 2m > n
    • 2m \bmod n = 2m - n

であることがわかります。i=2以降は、先程の LSB Oracle Attack 同様の流れになるので、同じようにmのレンジを狭めていって特定することが出来ます。

from Crypto.Util.number import long_to_bytes
from pwn import *

n = 136018504103450744973226909842302068548152091075992057924542109508619184755376768234431340139221594830546350990111376831021784447802637892581966979028826938086172778174904402131356050027973054268478615792292786398076726225353285978936466029682788745325588134172850614459269636474769858467022326624710771957129
e = 0x10001

host = "crypto.2020.chall.actf.co"
port = 20600


def get_plain_bit_length(c):
    r.sendline(str(c).encode())
    res = r.recv().split(b'\n')[1]
    return len(res)


r = remote(host, port)
c = int(r.recv().split(b'\n')[1])
m_bit_len = get_plain_bit_length(c)

lower_m = 0
upper_m = n
u_prev = m_bit_len

while upper_m - lower_m >= 1:
    cK = (c * pow(2, e, n)) % n
    u = get_plain_bit_length(cK)

    if u == u_prev + 1:
        upper_m = (upper_m + lower_m) // 2
    else:
        lower_m = (upper_m + lower_m) // 2
    u_prev = u
    c = cK
    
    print('----------')
    print(long_to_bytes(lower_m))
    print(long_to_bytes(upper_m))

実行結果

$ python solve.py
[x] Opening connection to crypto.2020.chall.actf.co on port 20600
[x] Opening connection to crypto.2020.chall.actf.co on port 20600: Trying 52.207.14.64
[+] Opening connection to crypto.2020.chall.actf.co on port 20600: Done
----------
b'\x00'
b'`\xd90\x10\xef%5_\x9a\x1d $\x93d\x95\xd4\xe8F\x15(\\%nMn\xd1R\xb8\xc1\xd7b\xab\x9f\xc4\xeb\xd6\x1b\x82\x15\r\xc3s\x07\xcb\xfb\xc5\x85EA!0>\xeb\xf5\xb5\x98\xb7\xc9\xfdP\xa3\xafK+\x15$\xea\xb78\x059\xc8\xcbyNo\xc7\x0c\xc3\\\x11\xaa\x94\x91p!7\xbdk:vD\xdc\x19\x1b\x97\xafyZ\x90\xa39\x7fV\xb4\x11S\xf5+XM\x92\xd3\x17\xf4F.?\x1f\xe6\xeco\x95\x0e\x13r\xae\xc4'
----------
b'\x00'
b'0l\x98\x08w\x92\x9a\xaf\xcd\x0e\x90\x12I\xb2J\xeat#\n\x94.\x12\xb7&\xb7h\xa9\\`\xeb\xb1U\xcf\xe2u\xeb\r\xc1\n\x86\xe1\xb9\x83\xe5\xfd\xe2\xc2\xa2\xa0\x90\x98\x1fu\xfa\xda\xcc[\xe4\xfe\xa8Q\xd7\xa5\x95\x8a\x92u[\x9c\x02\x9c\xe4e\xbc\xa77\xe3\x86a\xae\x08\xd5JH\xb8\x10\x9b\xde\xb5\x9d;"n\x0c\x8d\xcb\xd7\xbc\xadHQ\x9c\xbf\xabZ\x08\xa9\xfa\x95\xac&\xc9i\x8b\xfa#\x17\x1f\x8f\xf3v7\xca\x87\t\xb9Wb'

...(中略)...

----------
b'actf{this_is_not_what_i_meant_when_i_told_you_to_use_rsa_with_padding9'
b'actf{this_is_not_what_i_meant_when_i_told_you_to_use_rsa_with_padding:'
----------
b'actf{this_is_not_what_i_meant_when_i_told_you_to_use_rsa_with_padding9'
b'actf{this_is_not_what_i_meant_when_i_told_you_to_use_rsa_with_padding9'
[*] Closed connection to crypto.2020.chall.actf.co port 20600

3~4分回すと、flagが出てきました٩(๑❛ᴗ❛๑)尸
最後閉じてないけど!実際は最後の9->}ですが、コレくらいの推測なら解けたと言っても良いはず…。
下記公式解法などの解き方より収束が遅く、ソルバがうまく動作しているのか不安になって諦めかけたりしましたが、自分で納得しながら書いたソルバでflagがゲットできて良かった!

公式解法っぽい解き方(未完成)

あるk

K=k^{e} \bmod n

とします。このとき、Kkの暗号文になります。このKとflagの暗号文cをかけると、

cK \equiv m^{e}k^{e} \equiv (mk)^{e} \bmod n

となり、mkの暗号文が得られることになります。
このとき、mkのbit長がnのbit長以下の場合、cKを突っ込んで得られる応答から、mkのbit長がわかることになります。

ここで、mkのbit長をuと置くと、

2^{u-1} \leqq mk \leqq 2^{u} - 1

mkのレンジを表すことが出来ます。
先程の試行より、mのbit長は559とわかっているので、

2^{558} \leqq m \leqq 2^{559} - 1

ということがわかります。

したがって、m

\frac{2^{u-1}}{k} \leqq m \leqq frac{2^{u} - 1}{k}

の範囲であることがわかります。

これを、

k=frac{2^{i} - 1}{m}

と仮定し、iを 559からnのbit長まで増やしていき、mの範囲を絞っていきます。

…が、この方法でmのレンジを絞っていくと、flagが途中まで判明します。が、まだ最後の数バイトが不明のまま残ってしまいます…。
公式ソルバでは、この後"step2"として、更にmの下位の方のバイトを求めています。

下記は、公式のソルバを上記の説明に合わせて書き換え、動くようにしたもの。残念ながら、step2についてはまだ理解が出来ていないです。多分巨大な数shiftを挟むことでmが収束するレンジを広げ、小さいbitまで絞り込めるようにしていると思うのだけど…。

from Crypto.Util.number import long_to_bytes
from Crypto.PublicKey import RSA
from pwn import *

# refer to https://pastebin.com/P8L7RTDu

n = 136018504103450744973226909842302068548152091075992057924542109508619184755376768234431340139221594830546350990111376831021784447802637892581966979028826938086172778174904402131356050027973054268478615792292786398076726225353285978936466029682788745325588134172850614459269636474769858467022326624710771957129
e = 0x10001
pubkey = RSA.construct((n,e))

host = "crypto.2020.chall.actf.co"
port = 20600


def get_plain_bit_length(c):
    r.sendline(str(c).encode())
    res = r.recv().split(b'\n')[1]
    return len(res)


r = remote(host, port)
c = int(r.recv().split(b'\n')[1])
c_bit_len = get_plain_bit_length(c)

u = c_bit_len
lower_m = 2**(u-1)
upper_m = 2**u - 1
dd = upper_m - lower_m

mid_m = (upper_m + lower_m) // 2

for num in range(u+1, n.bit_length()):
    k = (2**num - 1) // mid_m 
    cK = (c * pow(k, e, n)) % n
    u = get_plain_bit_length(cK)
    
    upper_m = min(upper_m, (2**u-1)//k)
    lower_m = max(lower_m, (2**(u-1)//k))
    
    if upper_m - lower_m < dd:
        dd = upper_m - lower_m
        mid_m = (upper_m + lower_m) // 2
        
    print('----------')
    print(long_to_bytes(lower_m))
    print(long_to_bytes(upper_m))

print('----------')
print('u: ' + str(u))
print('k: ' + str(k))
print('m: ' + str(mid_m))
print(long_to_bytes(lower_m))
print(long_to_bytes(upper_m))

# ここから更に正確な値を求めていく

i = 4*pow(10,40)  # 適当な大きな数
shift = n*i
for num in range(n.bit_length()):
    k = (2**num - 1 + shift) // mid_m
    cK = (c * pow(k, e, n)) % n
    u = get_plain_bit_length(cK)
    
    if u == n.bit_length():
        # we didn't wrap around
        upper_m = min(upper_m, (shift-1)//k)
        lower_m = max(lower_m, (2**(u-1) + shift - n)//k)
    else:
        upper_m = min(upper_m, (shift + 2**u - 1)//k)
        lower_m = max(lower_m, (2**(u-1)+shift)//k)
        
    if upper_m - lower_m < dd:
        dd = upper_m - lower_m
        mid_m = (upper_m + lower_m) // 2
    if dd <= 1:
        break
    print('----------')
    print(long_to_bytes(lower_m))
    print(long_to_bytes(upper_m))

print('----------')
print('u: ' + str(u))
print('k: ' + str(k))
print('m: ' + str(mid_m))
print(long_to_bytes(lower_m))
print(long_to_bytes(upper_m))

実行結果

$ python solve.py 
[+] Opening connection to crypto.2020.chall.actf.co on port 20600: Done
----------
b'@\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00'
b'\x7f\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff'
----------
b'@\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00'
b'ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff'
----------

...{中略1}...

----------
u: 1024
k: 62606626634666857169962576496954328573681192124427072668906299463448781600005761352512899051732400786172667561506921142654444651242031108630
m: 1435705157341034722972040166343948017765222376167759753619834511904754169570506546261909734839045859564975508867904779044318503483547332182165204288687845169555358931060
b'actf{this_is_not_what_i_meant_when_i_told_you_to_use_rsa_q\x1ab7\xb2\x08gO\x0fu\xcd#\xe1'
b'actf{this_is_not_what_i_meant_when_i_told_you_to_use_rsa_x\xa0\xed3\xc0\xb3%\x82w\xa94\x8d\x08'

...{中略2}...

----------
b'actf{this_is_not_what_i_meant_when_i_told_you_to_use_rsa_v\xe7\xc7\xcbx\xd8\x82y!\xd4\xa7\x8e\x99'
b'actf{this_is_not_what_i_meant_when_i_told_you_to_use_rsa_x\xa0\xed3\xc0\xb3%\x82w\xa94\x8d\x08'
----------
b'actf{this_is_not_what_i_meant_when_i_told_you_to_use_rsa_v\xe7\xc7\xcbx\xd8\x82y!\xd4\xa7\x8e\x99'
b'actf{this_is_not_what_i_meant_when_i_told_you_to_use_rsa_w\xc4Z\x7f\x9c\xc5\xd3\xfd\xcc\xbe\xee\r\xd0'
----------

...{中略3}...

----------
u: 567
k: 473699294761052263257453976608854380286151134994879613791162315212316412696124816295601503453088411612127948258634000745395634796195218589954600739259717757111055678091542
m: 1435705157341034722972040166343948017765222376167759753619834511904754169570506546261909734839045859564975508867904779044318503483547332182366926494593476321186830772092
b'actf{this_is_not_what_i_meant_when_i_told_you_to_use_rsa_with_padding|'
b'actf{this_is_not_what_i_meant_when_i_told_you_to_use_rsa_with_padding}'
[*] Closed connection to crypto.2020.chall.actf.co port 20600

中略1のあと、actf{this_is_not_what_i_meant_when_i_told_you_to_use_rsa_までmの範囲が絞れましたが、まだその先数byte残っています。
そこでstep2の処理に移行し、mを最終bitまで特定しているようです。

この解法の、私にもわかりそうな解説ありましたらぜひ教えて下さいませー!