20210911-CSAWCTF-CryptoSecPartWriteUp

Posted on Edited on In , Views: Symbols count in article: 7.9k Reading time ≈ 7 mins.

 

Gotta Decrypt Them All

nc crypto.chal.csaw.io 5001

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
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from pwn import *
from Morse import morse
from base64 import b64decode
from Crypto.Util.number import *
from gmpy2 import iroot
import codecs


context.log_level = 'debug'
sh = remote('crypto.chal.csaw.io', 5001)

letmesee = ''

while 1:
    try:
        sh.recvuntil(b'What does this mean?\r\n')
        c1 = sh.recvline().decode().strip()
        c1 = c1.split('/')
        plaintext = ''
        for i in c1:
            plaintext += chr(int(morse(i.strip(), ' ')))
        plaintext = b64decode(plaintext).decode()
        plaintext = plaintext.split('\n')
        c = int(plaintext[2][4:])
        plaintext = iroot(c, 3)[0]
        plaintext = long_to_bytes(plaintext).decode()
        plaintext = codecs.encode(plaintext, 'rot13')
        letmesee += plaintext
        letmesee += ' '
        sh.recvuntil(b'>> ')
        sh.sendline(plaintext)
    except:
        break
print(letmesee)

Pokemon Names Wormadam Stonjourner Cloyster Jynx Zorua

Forgery

nc crypto.chal.csaw.io 5006

Felicity and Cisco would like to hire you as an intern for a new security company that they are forming. They have given you a black box signature verification system to test out and see if you can forge a signature. Forge it and you will get a passphrase to be hired!

127 solves

伪造文书，先做RSA

1
2
3
4
5
def verify(answer: str, r: int, s: int, y: int):
    m = int(answer, 16) & MASK
    if any([x <= 0 or x >= p - 1 for x in [m, r, s]]):
        return False
    return pow(g, m, p) == (pow(y, r, p) * pow(r, s, p)) % p

复现的时候竟然发现做过，参考CTFSHOW月饼杯2021-ctfshow_login

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
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from Crypto.Util.number import *
from pwn import *
from re import *

MASK = 2 ** 1024 - 1

context.log_level = 'debug'
while True:
    u = b'Felicity Cisco'.hex()
    sh = remote('47.96.253.167', 10001)
    content = sh.recvuntil(b'Answer:').decode()
    p, g, y = findall(r"\d+", content)
    p, y = int(p), int(y)
    u, r, s = u + hex((p - 1) // 2)[2:].rjust(1024, '0'), (p - 1) // 2, (p - 1) // 2
    sh.sendline(u)
    sh.recvuntil(b'r:')
    sh.sendline(str(r))
    sh.recvuntil(b's:')
    sh.sendline(str(s))
    flag = sh.recvall()
    if b'flag' in flag:
        print(flag)
        break

image-20210922205145757

另外一种解法，参考这篇论文On Forging ElGamal Signature and Other Attacks，后面有证明，里面先假设我们已经有一个对$(r,\ s)$符合等式

image-20210924083850936

为了使得
$$
g^u\equiv_py^rr^s\notag
$$

直接抄论文里的结论

image-20210924152637456

感觉论文有点小错，下面这样设置参数没问题
$$
r\equiv_pg^By^C\notag
$$
$$
s\equiv_{p-1}-rC^{-1}\notag
$$
$$
u\equiv_{p-1}-rC^{-1}B\notag
$$
随机选取$B, C\in[2, p-2]$

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
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from Crypto.Util.number import *
from pwn import *
from re import *
from gmpy2 import gcd, invert
from random import randint


MASK = 2 ** 1024 - 1
g = 3
context.log_level = 'debug'
while True:
    u = b'Felicity Cisco'.hex()
    sh = process(["python3", "./forgery.py"])
    content = sh.recvuntil(b'Answer:').decode()
    p, _, y = findall(r"\d+", content)
    p, y = int(p), int(y)
    B, C = randint(2, p - 2), randint(2, p - 2)
    if gcd(C, p - 1) != 1:
        continue
    r = pow(g, B, p) * pow(y, C, p) % p
    s = -r * invert(C, p - 1) % (p - 1)
    u = u + hex(-r * invert(C, p - 1) * B % (p - 1))[2:].rjust(1024, '0')
    sh.sendline(u)
    sh.recvuntil(b'r:')
    sh.sendline(str(r))
    sh.recvuntil(b's:')
    sh.sendline(str(s))
    flag = sh.recvall()
    if b'flag' in flag:
        print(flag)
        break

RSA Pop Quiz

考点

  • RSA-LSB

nc crypto.chal.csaw.io 5008

Wiener wiener chicken dinner

Who came up with this math term anyway?

Least Significant Bit Oracle Attack （LSB Oracle Attack / Parity Oracle）

该攻击使用的条件很简单，我们可以进行解密，并且会有oracle告诉我们明文的奇偶性，时间复杂度是$O(logN)$

假设已知的为enc，我们构造密文C
$$
C=(2^e\cdot c)\ mod\ n=(2^e\cdot m^e)\ mod\ n=(2\cdot m)^e\ mod\ n\notag
$$
我们将这个密文send过去，那么显然对应的明文就是$M=(2\cdot m)\ mod\ n$

oracle会告诉我们M的奇偶性，也就是最低位lsb是0还是1

由此我们可以进行推导，得出的结论如下

  • 如果lsb是0，说明$m<\frac{n}{2}$
  • 如果lsb是1，说明$m\geq \frac{n}{2}$；如果$2m$大于$n$，但注意$m$是不会超过$n$的，所以$2m$就不会超过$2n$，则$2m\ mod\ n=2m - n$，$n$是奇数，$2m$偶数，那么$M$是奇数，lsb是1

这样一次就可以将$m$限定在$\frac{n}{2}$的左边后者是右边，之后就是不断地二分，知道找到真正的m。因为运用二分的思想，所以时间复杂度才会是$log$

接下来就是继续构造
$$
C=(2^e\cdot C)\ mod\ n=(2^e\cdot (2\cdot M)^e)\ mod\ n=(4\cdot m)^e\ mod\ n\notag
$$
将$C$给send过去就可以在，获得oracle，就可以将$C$限定在$\frac{n}{4}$的空间里

自己从写了个源码搭建环境

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
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from Crypto.Util.number import getPrime, long_to_bytes, bytes_to_long
from gmpy2 import invert
from uuid import uuid4
import sys
import random
import hashlib
from string import ascii_letters, digits

space = ascii_letters + digits


def proof_of_work():
    pt = "".join([space[random.randint(0, len(space) - 1)] for _ in range(16)])
    ct = hashlib.sha256(pt.encode()).hexdigest()
    print("SHA-256(XXXX+{}) == {}".format(pt[4:], ct))
    guess = str(input("please give me XXXX: "))
    if hashlib.sha256((guess + pt[4:]).encode()).hexdigest() != ct:
        print("sorry, it seems you are not qualified")
        sys.exit(0)


banner = ''' ██       ██          ██                                          ██              ██        ████████ ██████
░██      ░██         ░██                                         ░██             ░██       ██░░░░░░ ░█░░░░██
░██   █  ░██  █████  ░██  █████   ██████  ██████████   █████    ██████  ██████   ░██      ░██       ░█   ░██
░██  ███ ░██ ██░░░██ ░██ ██░░░██ ██░░░░██░░██░░██░░██ ██░░░██  ░░░██░  ██░░░░██  ░██      ░█████████░██████
░██ ██░██░██░███████ ░██░██  ░░ ░██   ░██ ░██ ░██ ░██░███████    ░██  ░██   ░██  ░██      ░░░░░░░░██░█░░░░ ██
░████ ░░████░██░░░░  ░██░██   ██░██   ░██ ░██ ░██ ░██░██░░░░     ░██  ░██   ░██  ░██             ░██░█    ░██
░██░   ░░░██░░██████ ███░░█████ ░░██████  ███ ░██ ░██░░██████    ░░██ ░░██████   ░████████ ████████ ░███████
░░       ░░  ░░░░░░ ░░░  ░░░░░   ░░░░░░  ░░░  ░░  ░░  ░░░░░░      ░░   ░░░░░░    ░░░░░░░░ ░░░░░░░░  ░░░░░░░'''

proof_of_work()
flag = 'flag{' + str(uuid4()) + '}'
m = bytes_to_long(flag.encode())
p = getPrime(512)
q = getPrime(512)
n = p * q
phi = (p-1)*(q-1)
e = 0x10001
d = invert(e, phi)
c = pow(m, e, n)
print(banner)
print('n =', n)
print('e =', e)
print('c =', c)
choices = ['yes', 'no']
while 1:
    choice = input('do you wanna decrypt? (yes / no): ')
    if choice not in choices:
        print("sorry! i can't do this way ")
        sys.exit(0)
    elif choice == choices[0]:
        cx = eval(input('please give me your ciphertext: '))
        mx = pow(cx, d, n)
        print('this is what you want:', mx % 2)
    else:
        tempt = input('tell me your plaintext: ')
        if tempt == bytes_to_long(flag.encode()):
            print('congratulation! you are right: ')
        else:
            print('sorry! bye! ')
            sys.exit(0)

exp差不多这样吧，有点奇怪，后面收尾的时候不太对

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
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from pwn import *
from Crypto.Util.number import *
from itertools import product
from string import ascii_letters, digits
import hashlib
from re import findall

space = ascii_letters + digits

# context.log_level = 'debug'
sh = remote('47.96.253.167', 10001)


def proof_of_work1():
    # SHA-256(XXXX+8OeVCGS9zB8w) == c35d202a83694cfcace7a0cca784594ba3e984e3ced62714d08189d8bb03f6f0
    proof = sh.recvuntil(b'please give me XXXX:')
    tail = proof[13:25].decode()
    HASH = proof[30:94].decode()
    for i in product(space, repeat=4):
        head = ''.join(i)
        t = hashlib.sha256((head+tail).encode()).hexdigest()
        if t == HASH:
            sh.sendline(head.encode())
            break


def proof_of_work2():
    # SHA-256(XXXX+8OeVCGS9zB8w) == c35d202a83694cfcace7a0cca784594ba3e984e3ced62714d08189d8bb03f6f0
    proof = sh.recvline()
    tail = '35ec0130a578'
    HASH = '25da550b7b027fb3b802bf1c0234c30b59f17ff3a2a7f6f33e3428e6c0d162df'
    for i in product(space, repeat=4):
        head = ''.join(i)
        t = hashlib.sha256((head+tail).encode()).hexdigest()
        if t == HASH:
            print(head)
            break


proof_of_work1()
content = sh.recvuntil(b'do you wanna decrypt? (yes / no):').decode()
n, e, c = [int(_) for _ in findall(r'\d+', content)]
C = c
i = 0
j = n - 1
while True:
    m = (i + j) // 2
    if i >= j:
        sh.recvuntil(b'please give me your ciphertext:')
        sh.sendline(str(c))
        sh.recvuntil(b'this is what you want:')
        ans = sh.recvline()
        if b'1' in ans:
        	print(long_to_bytes(m))
        else:
            print(long_to_bytes(2*(m//2)))
        break
    sh.sendline(b'yes')
    C = 2 ** e * C % n
    sh.recvuntil(b'please give me your ciphertext:')
    sh.sendline(str(C))
    sh.recvuntil(b'this is what you want:')
    ans = sh.recvline()
    if b'0' in ans:
        j = m
    elif b'1' in ans:
        i = m

image-20210922223905766

最后一位显然不对，应该是左花括号，不知道为什么，应该问题不大

最后一层套娃是泄漏d低位，也是可以解的

Bits（not solve）

I wrote this oracle in rust so that it can’t sue companies over java stuff.

Author: CryptoHack (Robin_Jadoul and jack)

  • rust

run