I participated in AeroCTF as a member of Super Guesser. We reached 1st place :)

We were able to grab first bloods on all three cryptography challenges.

Phoenix was solved by rbtree, and I solved horcrux and boggart.

 

Phoenix

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
#!/usr/bin/env sage
 
= 2
= GF(p)
P.<x> = PolynomialRing(F)
 
 
class Cipher:
    def __init__(self, size, params):
        self.size = size
        self.params = params
 
    def sequence(self, key):
        while True:
            key = key * self.params[0]
            yield key + self.params[1]
 
    def encrypt(self, key, data, strength):
        for value, pbit in zip(self.sequence(key), data):
            xbit = sum(value[i] for i in range(0, strength, 2))
            ybit = mul(value[i] for i in range(1, strength, 2))
            
            yield int(pbit) ^^ int(xbit) ^^ int(ybit)
 
 
def main():
    size = 256
    length = 1024
    strength = 10
 
    q = P.irreducible_element(size, 'minimal_weight')
    R.<x> = P.quo(q)
 
    key, a, b = [R.random_element() for _ in range(3)]
 
    with open('flag.txt''rb'as file:
        flag = file.read().strip()
 
    message = int.from_bytes(flag, 'big')
    assert message.bit_length() < size
    plaintext = list(map(int, bin(message)[2:]))
    padding = [0* (length - len(plaintext))
 
    cipher = Cipher(size, [a, b])
    ciphertext = list(cipher.encrypt(key, padding + plaintext, strength))
    result = int(''.join(map(str, ciphertext)), 2)
 
    print(a)
    print(b)
    print(result)
 
 
if __name__ == '__main__':
    main()
 
cs

 

Solution (due to rbtree)

Let's look at the encryption scheme. 

 

We have a key $k \in GF(2^{256})$ and known parameters $a, b \in GF(2^{256})$.

To encrypt a plaintext $m$, it is first converted to binary then padded at the front with zeros to have length 1024. 

Then, we take the first 10 bits of the polynomial representation of $a^i k +b$ for each $i$, and calculate $$xbit_i = \sum \text{(even index bits)}$$ $$ybit_i = \prod \text{(odd index bits)}$$ where calculations are done in $GF(2)$. 

Finally, we encrypt our text with a stream cipher, i.e. XOR our plaintext with $\{xbit_i \oplus ybit_i\}_{i \ge 1}$. 

 

We now make some observations.

  • It's very likely that $ybit_i$ is $0$, since it is a product of 5 bits. Heuristically, it has a $31/32$ chance of being $0$. 
  • The message bit length is guaranteed to be less than 256. This means the length of the padding is at least 768.
  • If we write each 256 coefficients of $k$ as variables, then $xbit_i$ can be written as a linear combination of them (and $0, 1$)

 

Now we have our solution idea.

  • If we assume that $ybit_i = 0$ and know the ptxt/ctxt bits, we can recover $xbit_i$. This gives us a linear equation over our 256 variables.
  • Of course, we know 768 bits of the plaintext and all of the ciphertext, so we can do this for 768 different values of $i$.
  • We take 256 equations out of those 768 and hope that the system of equations have a unique solution.
  • If there is a unique solution, we can recover the key and perform the decryption process to get a candidate for our flag.
  • If our recovered flag has "Aero{" in it, we can finish the challenge. If not, we try another set of 256 equations.

 

We need to have $ybit = 0$ for all 256 bits/equations we selected. This has a probability of $$(31/32)^{256} \approx 0.0003$$ of succeeding, and we also need our system to be uniquely solvable. Thankfully, our algorithm terminates in about 2000 trials, and each trial doesn't take too long. It seems like SageMath is very efficient when it comes to matrices over $GF(2)$ :) 

 

Here's the solution script, by rbtree. It runs in a few minutes.

 

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
import random
from Crypto.Util.number import *
 
= 2
= GF(p)
P.<x> = PolynomialRing(F)
 
size = 256
length = 1024
strength = 10
 
= P.irreducible_element(size, 'minimal_weight')
R.<x> = P.quo(q)
 
class Cipher:
    def __init__(self, size, params):
        self.size = size
        self.params = params
 
    def sequence(self, key):
        while True:
            key = key * self.params[0]
            yield key + self.params[1]
 
    def encrypt(self, key, data, strength):
        for value, pbit in zip(self.sequence(key), data):
            xbit = sum(value[i] for i in range(0, strength, 2))
            ybit = mul(value[i] for i in range(1, strength, 2))
            
            yield int(pbit) ^^ int(xbit) ^^ int(ybit)
 
enc = 69824286833704501471834043923417254326103912707315595840737453739249974863266259092449058810542265536810346421685955365128856715192808287450464619418781355923155781710833586631897182535937891456025282049302526058466298304955387306232279075295308862156912873485647349272079984781574084434511227361370780842056
enc = list(map(int, bin(enc)[2:]))
enc = [0* (length - len(enc)) + enc
 
= x^255 + x^252 + x^246 + x^245 + x^240 + x^239 + x^236 + x^234 + x^233 + x^232 + x^231 + x^229 + x^228 + x^227 + x^224 + x^223 + x^218 + x^217 + x^216 + x^215 + x^210 + x^209 + x^204 + x^202 + x^200 + x^198 + x^197 + x^196 + x^192 + x^188 + x^187 + x^182 + x^181 + x^180 + x^178 + x^177 + x^176 + x^174 + x^173 + x^172 + x^167 + x^166 + x^161 + x^160 + x^157 + x^155 + x^154 + x^151 + x^150 + x^149 + x^148 + x^147 + x^146 + x^144 + x^140 + x^137 + x^135 + x^133 + x^132 + x^130 + x^129 + x^126 + x^122 + x^119 + x^118 + x^115 + x^112 + x^111 + x^109 + x^107 + x^106 + x^105 + x^104 + x^101 + x^100 + x^99 + x^97 + x^96 + x^94 + x^92 + x^87 + x^86 + x^84 + x^83 + x^81 + x^79 + x^75 + x^71 + x^69 + x^68 + x^67 + x^66 + x^65 + x^63 + x^62 + x^61 + x^56 + x^55 + x^53 + x^52 + x^50 + x^46 + x^44 + x^43 + x^41 + x^39 + x^38 + x^37 + x^36 + x^35 + x^34 + x^33 + x^32 + x^30 + x^29 + x^27 + x^24 + x^21 + x^17 + x^16 + x^14 + x^13 + x^12 + x^11 + x^10 + x^9 + x^5 + x^4 + x^3 + x + 1
= x^255 + x^254 + x^250 + x^247 + x^243 + x^242 + x^241 + x^238 + x^235 + x^232 + x^229 + x^227 + x^222 + x^221 + x^219 + x^218 + x^217 + x^216 + x^215 + x^211 + x^207 + x^206 + x^204 + x^202 + x^201 + x^197 + x^195 + x^193 + x^192 + x^190 + x^189 + x^188 + x^186 + x^184 + x^181 + x^180 + x^179 + x^178 + x^176 + x^173 + x^172 + x^169 + x^167 + x^165 + x^161 + x^160 + x^158 + x^149 + x^147 + x^146 + x^145 + x^140 + x^138 + x^137 + x^134 + x^133 + x^132 + x^130 + x^129 + x^128 + x^126 + x^125 + x^124 + x^121 + x^120 + x^118 + x^117 + x^114 + x^112 + x^111 + x^110 + x^109 + x^108 + x^107 + x^106 + x^105 + x^101 + x^96 + x^95 + x^94 + x^93 + x^92 + x^90 + x^89 + x^88 + x^86 + x^85 + x^84 + x^83 + x^81 + x^80 + x^79 + x^78 + x^77 + x^76 + x^71 + x^70 + x^69 + x^68 + x^67 + x^64 + x^63 + x^59 + x^56 + x^55 + x^53 + x^50 + x^46 + x^43 + x^42 + x^40 + x^38 + x^37 + x^35 + x^34 + x^33 + x^25 + x^23 + x^22 + x^21 + x^18 + x^16 + x^14 + x^13 + x^12 + x^11 + x^10 + x^8 + x^3 + x^2 + x
= sum(b[i] for i in range(0102))
 
vs = [ x^i for i in range(size) ]
vecs = []
for idx in range(length - size):
    for i in range(size):
        vs[i] = vs[i] * a
    
    arr = [int( sum(vs[j][i] for i in range(0102)) ) for j in range(size)]
    val = int(t) ^^ enc[idx]
 
    vecs.append( (arr, val) )
 
 
cipher = Cipher(size, [a, b])
cnt = 0
while True:
    cnt += 1
    random.shuffle(vecs)
 
    mat = Matrix(F, [vecs[i][0for i in range(size)])
    vec = Matrix(F, [vecs[i][1for i in range(size)]).transpose()
    try:
        vec = mat.inverse() * vec
 
        key = 0
        for i in range(size):
            if int(vec[i][0]):
                key += x^i
 
        plaintext = list(cipher.encrypt(key, enc, strength))
        plaintext = int(''.join(map(str, plaintext)), 2)
        plaintext = long_to_bytes(plaintext)
 
        if b'Aero{' in plaintext:
            while True:
                print(plaintext)
        else:
            print("FAIL2", cnt)
 
    except:
        print("FAIL", cnt)
        pass
cs

 

 

Horcrux

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
#!/usr/bin/env python3.8
 
from os import urandom
from gmpy2 import next_prime
from random import randrange, getrandbits
from Crypto.Cipher import AES
from fastecdsa.curve import Curve
 
 
def bytes_to_long(data):
    return int.from_bytes(data, 'big')
 
 
def generate_random_point(p):
    while True:
        a, x, y = (randrange(0, p) for _ in range(3))
        b = (pow(y, 2, p) - pow(x, 3, p) - a * x) % p
 
        if (4 * pow(a, 3, p) + 27 * pow(b, 2, p)) % p != 0:
            break
 
    return Curve(None, p, a, b, None, x, y).G
 
 
class DarkWizard:
    def __init__(self, age):
        self.power = int(next_prime(getrandbits(age)))
        self.magic = generate_random_point(self.power)
        self.soul = randrange(0self.power)
 
    def create_horcrux(self, location, weakness):
        # committing a murder
        murder = self.cast_spell(b'AVADA KEDAVRA')
 
        # splitting the soul in half
        self.soul = self.soul * pow(2-1self.power) % self.power
 
        # making a horcrux
        horcrux = (self.soul + murder) * self.magic
 
        # nobody should know location and weakness of the horcrux
        horcrux.x ^= location
        horcrux.y ^= weakness
 
        return horcrux
 
    def cast_spell(self, spell_name):
        spell = bytes_to_long(spell_name)
 
        return spell %~ spell
 
 
def encrypt(key, plaintext):
    cipher = AES.new(key=key, mode=AES.MODE_ECB)
    padding = b'\x00' * (AES.block_size - len(plaintext) % AES.block_size)
 
    return cipher.encrypt(plaintext + padding)
 
 
def main():
    wizard_age = 3000
    horcruxes_count = 2
 
    wizard = DarkWizard(wizard_age)
    print(f'Wizard\'s power:\n{hex(wizard.power)}\n')
    print(f'Wizard\'s magic:\n{wizard.magic}\n')
 
    key = urandom(AES.key_size[0])
    horcrux_length = len(key) // horcruxes_count
 
    for i in range(horcruxes_count):
        key_part = key[i * horcrux_length:(i + 1* horcrux_length]
 
        horcrux_location = bytes_to_long(key_part[:horcrux_length // 2])
        horcrux_weakness = bytes_to_long(key_part[horcrux_length // 2:])
 
        horcrux = wizard.create_horcrux(horcrux_location, horcrux_weakness)
        print(f'Horcrux #{i + 1}:\n{horcrux}\n')
 
    with open('flag.txt''rb'as file:
        flag = file.read().strip()
 
    ciphertext = encrypt(key, flag)
    print(f'Ciphertext:\n{ciphertext.hex()}')
 
 
if __name__ == '__main__':
    main()
 
cs

 

Solution

We first take a look at what's going on.

  • We have a 3000 bit prime $p$, which we know.
  • We have a point $G$ on some elliptic curve $ y^2 = x^3 + ax + b$ over $\mathbb{F}_p$ - we know $G$ but we don't know $a, b$.
  • We have a 128 bit AES key we have to recover : this is split into two "horcruxes" of 64 bits.
  • Each horcrux is split into two parts of 32 bits - they are XOR'ed to the coordinates of some point on the curve then given.

 

Writing this in mathematical equations, we have

  • We are given a 3000 bit prime $p$ and three coordinates $(x_0, y_0), (x_1, y_1), (x_2, y_2)$
  • 128 bit AES key is equal to $\alpha_1 || \beta_1 || \alpha_2 || \beta_2$ with each part being 32 bits, i.e. less than $2^{32}$.
  • $(x_0, y_0)$ lies on a elliptic curve $y^2 = x^3 + ax + b$ over $\mathbb{F}_p$, so $y_0^2 = x_0^3 + ax_0 + b$ in $\mathbb{F}_p$.
  • $(x_1 \oplus \alpha_1, y_1 \oplus \beta_1)$ lies on the curve, so $(y_1 \oplus \beta_1)^2 = (x_1 \oplus \alpha_1)^3 + a(x_1 \oplus \alpha_1) + b$
  • $(x_2 \oplus \alpha_2, y_1 \oplus \beta_2)$ lies on the curve, so $(y_2 \oplus \beta_2)^2 = (x_2 \oplus \alpha_2)^3 + a(x_2 \oplus \alpha_2) + b$

 

Since XOR is hard to deal with, we change it to normal addition - of course, it's clear that

  • $U, V \ge 0$, $V < 2^b$ implies $|(U \oplus V) - U| < 2^b$. 

Therefore, we can change each XOR to addition, by changing our constraints from $0 \le \alpha_i, \beta_i < 2^{32}$ to $|\alpha_i|, |\beta_i| < 2^{32}$.

 

Now we have to solve, given $p, x_0, y_0, x_1, y_1, x_2, y_2$, the system of equations $$\begin{equation*} \begin{aligned}  y_0^2 &= x_0^3 + ax_0 + b \\ (y_1 + \beta_1)^2 &= (x_1 + \alpha_1)^3 + a(x_1 + \alpha_1) + b \\ (y_2 + \beta_2)^2 &= (x_2 + \alpha_2)^3 + a(x_2 + \alpha_2) + b \end{aligned} \end{equation*}$$ over $\mathbb{F}_p$ and $|\alpha_i|, |\beta_i| < 2^{32}$. Now what do we do? There were a few ideas at this point...

 

Idea 1 : Lattices

Of course, "small solutions" imply that we have to use lattices. Maybe we can directly use them here?

For example, using github.com/rkm0959/Inequality_Solving_with_CVP we can solve a system of linear inequalities.

Turns out, it's quite difficult to do so, since our system has terms like $a \alpha_1$ and $a \alpha_2$. 

Because we don't know the value of $a$ and its size can be large, we can't deal with this term using this method.

 

To use the tool in the link, we need all terms of our equations to be either

  • linear in terms of our variables (i.e. variable multiplied by a known constant)
  • small (so that we can move this to the lower bound / upper bound vector for the CVP)

In this case, $a \alpha_1$ and $a \alpha_2$ term does not satisfy this requirement.

 

Idea 2 : Determinant

The failure of our Idea 1 leads to the key idea : removing $a$ in our system completely.

 

This can be done by realizing that $[1, -a, -b]^{T}$ is in the kernel of the matrix $$ \left[ \begin{matrix} y_0^2 - x_0^3 & x_0 & 1 \\ (y_1 + \beta_1)^2 - (x_1 + \alpha_1)^3 & (x_1 + \alpha_1) & 1 \\ (y_2 + \beta_2)^2 - (x_2 + \alpha_2)^3 & (x_2 + \alpha_2) & 1 \end{matrix} \right]$$ which means its determinant must be $0$ in $\mathbb{F}_p$. This gives us a polynomial equation in $\alpha_1, \alpha_2, \beta_1, \beta_2$. Now what?

 

The first idea was multivariable coppersmith - I tried to use defund's implementation, but the matrix size got way too large.

The second idea is, of course, lattices from Idea 1. If we expand our determinant, we will get a equation of the form $$\sum \text{(constant coefficient)} \cdot \text{(some monomial)} = 0$$ we can simply bound each monomials with $|\alpha_i|, |\beta_i| < 2^{32}$, then solve using the CVP toolkit above.

 

To be more precise : our equation will be in a form of $$\sum_{i=1}^k c_i m_i \equiv -c_{k+1} \pmod{p}$$ where $c_i$ is a known constant and $m_i$ is some non-constant monomial over $\alpha_i$, $\beta_i$. (Consider $m_{k+1}$ as $1$)

We solve this system by utilizing the following inequalities and plugging them into the CVP toolkit : 

$$-2^{32 \cdot \deg(m_i)} < m_i < 2^{32 \cdot \deg(m_i)}$$ $$ \sum_{i=1}^k c_i m_i+ pX = -c_{k+1}$$ where $\deg(m_i)$ is the degree of the monomial. Note that abuse of notation was used - $m_i$ is used both as a monomial, and as the actual value of the monomial with the true values of $\alpha_i$, $\beta_i$ plugged in. For further details, please take a look in the github repo and the solution.

 

UPD : Mystiz gives a good insight on entropy to explain why this line of thinking works. Link is here.

This is a very useful way to think about whether or not the above CVP toolkit will work, when it comes to the uniqueness of the solution.

 

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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
from sage.modules.free_module_integer import IntegerLattice
 
# https://github.com/rkm0959/Inequality_Solving_with_CVP
def Babai_CVP(mat, target):
    M = IntegerLattice(mat, lll_reduce=True).reduced_basis
    G = M.gram_schmidt()[0]
    diff = target
    for i in reversed(range(G.nrows())):
        diff -=  M[i] * ((diff * G[i]) / (G[i] * G[i])).round()
    return target - diff
 
 
def solve(mat, lb, ub, weight = None):
    num_var  = mat.nrows()
    num_ineq = mat.ncols()
 
    max_element = 0 
    for i in range(num_var):
        for j in range(num_ineq):
            max_element = max(max_element, abs(mat[i, j]))
 
    if weight == None:
        weight = num_ineq * max_element
 
    if len(lb) != num_ineq:
        print("Fail: len(lb) != num_ineq")
        return
 
    if len(ub) != num_ineq:
        print("Fail: len(ub) != num_ineq")
        return
 
    for i in range(num_ineq):
        if lb[i] > ub[i]:
            print("Fail: lb[i] > ub[i] at index", i)
            return
 
    # scaling process begins
    max_diff = max([ub[i] - lb[i] for i in range(num_ineq)])
    applied_weights = []
 
    for i in range(num_ineq):
        ineq_weight = weight if lb[i] == ub[i] else max_diff // (ub[i] - lb[i])
        applied_weights.append(ineq_weight)
        for j in range(num_var):
            mat[j, i] *= ineq_weight
        lb[i] *= ineq_weight
        ub[i] *= ineq_weight
 
    # Solve CVP
    target = vector([(lb[i] + ub[i]) // 2 for i in range(num_ineq)])
    result = Babai_CVP(mat, target)
 
    for i in range(num_ineq):
        if (lb[i] <= result[i] <= ub[i]) == False:
            print("Fail : inequality does not hold after solving")
            break
 
    ## recover your result
    return result, applied_weights
 
= 0x27266a1284b761f793a529b9664693a6b1db36864a8664898d98d8010ec51afffaef2d1c79ab2078c1e0b289a1719d34b0a081ca325ba2b367017ee8e0824aaa9488409e76e923d0f0fc917ddfc1b0534e93a74246405dadfd1683f0dc31682eed0fa6b95fc235c845e16d2ef40463b7e746668dad82981fc4e05933aca410c65b36f89738f7d97502f6626c38f595338f3864638d8613fb74c16b63f3969a49ebd103ef354ed756c3cd5e67f1d2dbe5acdbc088bd6c1d503acef4ec59e4a09efac4729ca796ad25217fe74e7a0c7ef5a3e1fcd9eb9288fb89e842ef0b16642f7e84e27df4bcb623726e2c44ef46be07f9b5a5f92fe2c77d0de79fa6d46193b064207125d8935c2ff04f63e2f858e98d2518077dc58e13307f01d65ae953efd70980f3aeed320b7a6b66eb0c578dc3f05d426f412c4e3c7a9bcc68f27fe236fde41400371a39f53828824f5de3d5902cd3e7dcaee58b89c1a234188e391d412e7bc598d4f10b2bcb26aab7cd09194e80be046022ee8471
 
x0 = 0x4f69c16e493693a9342b7b9bb0ae42d0e7425996151c631a5620ad4d7ed372d285f04df82975a379080af08322fd927cf8ea9702f4533b5981351dd12358ca61c6e34af3f902b13d2981cae7cd2416e910bfe2c90f3b64c02bf933b1d11ff8ee384f5b507d9a0b1be38b15e7db3ba700ed32122a0163ec66530911fe142e098187771f5a248627a1709800069d402c1a61a17bd053ff6541f981898df6670420b0f3ea6ebd6d01d24f6fe9e3091a7c36df0c1ad7596e8ae090c54528385422911ff8e1dc201ab56844bc92acabc495c442104de5c34a5fe6661b7213500f4ccef6e76b94c34d60772fcf0c1250e66812d85efcda4b323250f740d0d57d40697fedae0bdbaceb0582cd7c82a27610e7f9fba5ac8f84e006d034dcf481f2dc9338acabd51c28afc1b4fc1d0cd7c1cd5ad21109e8708e9458e5301868c68920ab1aefb1e9184383002e6c893f1793443f8388f3f1b6e1f4ecaecb4cf000f57f677156efdacb20d60a35b8337ee416957aadffdc889dce487
y0 = 0x2393c955e5f44ab3ac052dafd83554222728393b8fd20630f3c4f122d8c86d872a7b692b3782f12a6e57352c46328f85fad2d73eaccfcbf7beb47f97da2148c4f3fc7d6751bf66569c97a64f732e7cc71767ba11b1419732035c0285ff6973fba230a3d315fba7820855208e07e6fc5bc4b2cc3868aacde3b8e9b2075bfe861b2ebccd9b6c836d85dc319290263961344d348fe8faa0aa3ebca76fe514a7b7ba313a8200727b22a8714f8bba9e5ec2c549e5bfb5857c050d1ff0471d4b01426c2ee583a7d4b6c30df5ad2d9a6902f574416f8d55ed192b29d521e5d23a54e5062400b539468dca9aa3dc558feac63c88fc696d42434ad9a83551e6860aeb6a4d84ca80713387fa8c56a1e473a82af63ec03a71202aba0ae46fb9a97132f4c92d332327e2c11b79008586b22d92d60c3155e88b5e1f9c193b363ca28f0990400afb6e8148458708b89c6023c0d5ebb746bcd754fe37a84ee4dea6baa273b2ef31a864e9586f01bae855cc0d6f6055b2546b2a918664bdb6
 
 
x1 = 0x2700ff7abe81679c770d3171c993c55da4a47cda3360e33d2b763e65517f307a39d401a256ee0634f3f1c6c244aad34422dccfe9ebd1803339972095eb2b0a57c82ee0db9ba94365cfb5270c4924c5c1ec00db2aff529aa923b113d2ca8ad6a6774fb7c655cd101ea63bc5a6ea0261f8da82d455219c7584d7de0757b2fda627c4684d3bac8f899c24178c7e0ecef6c226892b86043d3853cdb777889ce2901d8496bf0232dd000208eb2ce77e953c478551b1112ebf4b02f0086726210a50dc20ac08eb15d846084f9324b4f1f5ec73e3ef7e4a5207e04ebb866f731201e5f626084d1b61c158cfd0fdbaae8b8dd23ba599689c74a790933a3e77daa1c95fbde63b74381aff2b98f41cfebb7f1b220a4f2e8c3361734d7bd6648c720efc0a5f978917d8b84b4764e416762884f00104981e62d876d460bd8c1095cd755d8f31c5377e5ef935da77ff82e823b49d817a1f91bd4d155306173eb07efa4567d362e1cddbf0483873d5efc9286c36a58e5b3d995f3d01ca60
y1 = 0x1bf9a696ef976644dd903fb148892044fe65dd16bf12966a6b6e43be4b3b52aaa348a76ed5a53bbb400a366c59c96cf88a9c6a713273a722c0c8cd6f42b7c6f5e1911d2d323780bce65be80eef4d375dd3425a9ff832e4166765c7687aaf3c6f3c1ae7c561c46c49f0075bb68d48b95be5fd2c94996a42ba255eb638ae5ce449064cc81831f2239dbb93f4944693ee42a507dc2878988928dc9ed5bb5cb3b3eba9ac414b4171e505d285edaf02d13c0748e47b17a498cb0c15883977a11cde98995a022999a555fb3f1a3b9226dc4122f3db6c86036b1b0e6ada10b23b8c89ddb590f2186191c0f1148a04a8e35c905d4053943554c58e8f0e2ccac42c2307532e2b8f55b74fccb8ab24a977c557d10bd7c8621bef3e7f326d00c3ff28a52ee85ec61bb8aef14f67ac80da5885a93f2840a5e44d9800b0352163667ba851bb15c4083955e1fba5cd9d6e7bf103a2bbb0fbc868136cf2871815762514c691e6352af18324d1ccdc21da3e1c4c6aa771aa9fccf343ad64b8
 
x2 = 0xa439486ae1dbd96ca0796947609757b9dc068d8ed8287f98261c0c77e0940d29e25d27e16b97bc6983be505b8295886a5e880664ecb2d9161036f5beb1dbdac08da0cc2797d574e0feac67bbcb43275ab9e9d936aa17fd9a0a13a2f95e111b5e0893c4d4c3afae3bfa4a60fc5d0673215dd876b8bc960fc765401135dc708562cbeb572fcefaef1fef51782f6e0b495c0799cf89a9f47ffec11b0e780fb41e80d75681f7c9dd5fbf5e93e1dcda8091ca6a84de5b82b3abc9194913119e429781c12c11ebc6b6e80c01683344319879dec8fe59dd2f9c5b7b6e5e211153ae3b5fd161edae59777f3e76ecdeaef518495e512119451c6a97a8f471c4349ba7df8c3e9c1ba67f7a4fef57551d58b8c87607dc830c8074eec50841a1e365be90b528e4f39b8e19e7617191ac5118bb1abc44739d65384d915cb72e226122965ebae1581f55ecb12e523b0e904b3c0a1b26cf506ca030a68fe40d34c0912272277cd0d605ab057dbb5423cca28629661ad163232e766e80949
y2 = 0x29cfc760529c48d68bc086a5b4403f1d4446db04abe243c99baf659b5e67cd6cdac9a658f273f4c682b9e13dda72aaa1ede42c69c98640f2fc58eabeef143a65334e4a236a6e72a157d92ab1a541c9bcf7d953b386a40d68880312ed1e900f6ba481bf134515f5a4c245a0d924db0e5105fc44fae71fc991df85219403ba5d48f68d5d91151f8411b4cbb6971bd63030b523989fa7ec94c14136ac712d4e91eca4c930d79caab7c328043c762917c4b3f868ce037cae9f19a579272c6b13ca8c19d349f5777bf6ac9c078d8472c92582daf96b30d4f7b8fdc004a36b792c133e2b6511956480892636ea91a3361afd8a3afbe3a5bf889feb5a5dc143f5a917347591634218066f2f71b36afd5257f6637152ac9a0965daa881ddc86ca8a8545b255cbb14e7738297a55c7428d9a0e79dee37f801fc1d49d205be809e0cd1b8a1b9d1d5b1b1a9ae98e7c564718cb17d10a3dd01c2914d7bb96c45a4fc942c2ed628354882464407c3208938282471aa2b8016e46c998e4
 
 
= Integers(p)
 
# determinant calculation
# a, b = alpha_1, beta_1
# c, d = alpha_2, beta_2
P.<a, b, c, d> = PolynomialRing(R)
= 0
+= (y0 ** 2 - x0 ** 3* (x1 + a) * 1
+= (x0) * 1 * ((y2 + d) ** 2 - (x2 + c) ** 3)
+= 1 * ((y1 + b) ** 2 - (x1 + a) ** 3* (x2 + c)
-= (y0 ** 2 - x0 ** 3* 1 * (x2 + c)
-= x0 * ((y1 + b) ** 2 - (x1 + a) ** 3* (1)
-= 1 * (x1 + a) * ((y2 + d) ** 2 - (x2 + c) ** 3)
 
# coefficient
= f.coefficients()
 
# degree
print(f.monomials())
# [a^3*c, a*c^3, a^3, a^2*c, b^2*c, a*c^2, c^3, a*d^2, a^2, b^2, a*c, b*c, c^2, a*d, d^2, a, b, c, d, 1]
= [poly.degree() for poly in f.monomials()]
print(D)
# [4, 4, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 0]
 
 
# CVP setup
print(len(C)) # 20
 
= Matrix(ZZ, 2020)
lb = [0* 20
ub = [0* 20
 
# monomial bounds
for i in range(019):
    M[i, i] = 1
    lb[i] = -(2 ** (32 * D[i]))
    ub[i] = (2 ** (32 * D[i]))
 
# the polynomial
for i in range(019):
    M[i, 19= C[i]
M[1919= p
lb[19= int((-C[19]) % p)
ub[19= int((-C[19]) % p)
 
# solve CVP
result, applied_weights = solve(M, lb, ub)
 
# recover variables
alpha_1 = result[15// applied_weights[15]
beta_1 = result[16// applied_weights[16]
alpha_2 = result[17// applied_weights[17]
beta_2 = result[18// applied_weights[18]
 
print(alpha_1, beta_1, alpha_2, beta_2)
 
# recover actual key
alpha_1 = x1 ^^ (x1 + alpha_1)
beta_1 = y1 ^^ (y1 + beta_1)
alpha_2 = x2 ^^ (x2 + alpha_2)
beta_2 = y2 ^^ (y2 + beta_2)
 
print(alpha_1, beta_1, alpha_2, beta_2)
# the rest is trivial decryption
cs

 

 

Boggart

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
#!/usr/bin/env python3.8
 
from gmpy import next_prime
from random import getrandbits
 
 
def bytes_to_long(data):
    return int.from_bytes(data, 'big')
 
 
class Wardrobe:
    @staticmethod
    def create_boggarts(fear, danger):
        # for each level of danger we're increasing fear
        while danger > 0:
            fear = next_prime(fear)
 
            if getrandbits(1):
                yield fear
                danger -= 1
 
 
class Wizard:
    def __init__(self, magic, year, experience):
        self.magic = magic
        self.knowledge = year - 1 # the wizard is currently studying the current year
        self.experience = experience
 
    def cast_riddikulus(self, boggart):
        # increasing the wizard's experience by casting the riddikulus charm
        knowledge, experience = self.knowledge, self.experience
 
        while boggart > 1:
            knowledge, experience = experience, (experience * self.experience - knowledge) % self.magic
            boggart -= 1
 
        self.experience = experience
 
 
def main():
    year = 3
    bits = 512
    boggart_fear = 31337
    boggart_danger = 16
 
    neutral_magic, light_magic, dark_magic = [getrandbits(bits) for _ in range(3)]
    magic = next_prime(neutral_magic | light_magic) * next_prime(neutral_magic | dark_magic)
 
    print('Hello. I am Professor Remus Lupin. Today I\'m going to show you how to deal with the boggart.')
 
    print(neutral_magic)
    print(magic)
 
    with open('flag.txt''rb'as file:
        flag = file.read().strip()
 
    # some young wizards without knowledge of the riddikulus charm
    harry_potter = Wizard(magic, year, bytes_to_long(b'the boy who lived'))
    you = Wizard(magic, year, bytes_to_long(flag))
 
    for boggart in Wardrobe.create_boggarts(boggart_fear, boggart_danger):
        # wizards should train to learn the riddikulus charm
        harry_potter.cast_riddikulus(boggart)
        you.cast_riddikulus(boggart)
 
    # wizard's experience should be increased
    print(harry_potter.experience)
    print(you.experience)
 
 
if __name__ == '__main__':
    main()
 
cs

 

Solution

There is a lot going on in this code, so let's take a look at it.

  • We have random 512 bit integer $M_N, M_L, M_D$ corresponding to neutral/light/dark magic
  • The value magic is created as $M = \text{next_prime}(M_N | M_L) \times \text{next_prime}(M_N | M_D)$.
  • We are given the values of $M_N$ and $M$ - so the factorization of $M$ is unknown.

Now, the text "the boy who lived" and the flag goes through some encryption process, and we know their ciphertexts.

  • The encryption process itself is quite random - it uses the cast_ridikkulus algorithm randomly.
  • To be more precise, it starts the parameter "fear" at 31337, and increases it to the next prime each time.
  • Then, with a 50% chance, the text gets encrypted with the said value of "fear" and the cast_ridikkulus algorithm.
  • If we have used the cast_ridikkulus algorithm 16 times, the encryption process terminates.

 

cast_riddikulus algorithm

 

Naturally, we have to look at the cast_riddikulus algorithm and how to reverse/decrypt it.

We note that the value of self.knowledge is fixed at $2$ at all times. Denote the self.experience as $x$, and the boggart as $n$.

 

The algorithm calculates a linear recurrence - it starts with $a_0=2$, $a_1 = x$, and moves up by $$a_{i} = xa_{i-1} - a_{i-2}$$ Let's forget about the modulos and solve this recurrence. Using standard techniques, we get $$a_n = \left( \frac{x - \sqrt{x^2 - 4}}{2} \right)^n + \left( \frac{x + \sqrt{x^2- 4}}{2} \right)^n $$ This looks kinda scary, but then we can see that this is just $$x = t + t^{-1} \implies a_n = t^n + t^{-n}$$ Note that this implication holds even when we consider the fact that we are working modulo $M$.

 

This has a lot of meaning - for example, the encryption function is commutative in a sense that encrypting a text (experience) with (boggart) $m$ then $n$ is equivalent to encrypting with $n$ then $m$, which is equivalent to encryption once with $mn=nm$. 

 

It also implies that under some "mild" conditions, we can reverse the encryption function as follows - 

  • Given $ctxt \equiv t^n +  t^{-n} \pmod{M}$, we solve for the value $t^n \pmod{M}$.
  • We solve for $t \pmod{M}$ using the value of $t^n \pmod{M}$.
  • We get our original value $ptxt = t + t^{-1} \pmod{M}$.

In the above algorithm, we needed

  • Factorization of $M$, and we need $t$ to be coprime to $M$
  • $t^n + t^{-n} \equiv ctxt \pmod{M}$ to be solvable, i.e. $ctxt^2 - 4$ being a quadratic residue
  • $n$ being coprime to $\phi(M)$, for the discrete root to be easy to solve 
  • (of course, we can use adlemann root extraction, but that's not very fast)

Let's review our requirements and how difficult they are

  • Factorization of $M$ : this is hard but must be done - and this is probably why we are given $M_N$.
  • $t$ being coprime to $M$ : this will probably hold even if we don't care about it
  • $ctxt^2 - 4$ being a quadratic residue : if not, we can just get our random values of $M_N, M_L, M_D, M$ again.
  • $n$ being coprime to $\phi(M)$ : in our context, we will use 16 primes larger than $30000$ as $n$, so it'll most likely be true.

Therefore, it's time to go back and try to factorize $M$ with our information of $M_N$.

 

factorization of $M$

 

The key idea is that the value of $M_N$ gives us known bits of each prime $p, q$ of $M$.

  • $M_N|M_L$ and $M_N|M_D$ obviously has all bits that $M_N$ has. 
  • Then, we apply the next_prime function. Due to the small prime gap, this is similar to adding a few thousand to each number.
  • Therefore, some lower bits will definitely change, and even higher bits can change due to carry

Consider $M'_N = M_N - (M_N \pmod{2^{16}})$, i.e. $M_N$ but changed the $16$ LSB to 0.

  • If no carry happens at the 16th bit, our primes will still have all the bits of $M'_N$.
  • If a carry happens at the 16th bit, we hope our primes will still have all the bits of $M'_N + 2^{16}$.

Therefore, we write $M''_N = M'_N \& (M'_N + 2^{16})$ and claim that $p, q$ all have the bits of $M''_N$.

 

It is known that with around 57% of the bits of $p, q$ known, we can factorize $N$ using the following algorithm -

  • At stage $k$, calculate all possible $(p \pmod{2^k}, q \pmod{2^k})$ such that $pq \equiv N \pmod{2^k}$.
  • Of course, we must respect the known bits of $p, q$ while calculating this.
  • We can change $p \pmod{2^k}$ to $p \pmod{2^{k+1}}$ or $p + 2^k \pmod{2^{k+1}}$ while moving to the next stage.
  • If we find a set of $(p, q)$ such that $pq = N$, the algorithm terminates. 
  • This can be written in a depth-first search style or a breadth-first search style. The latter works better on my machine.

We require that $M''_N$ has a lot of ones in its binary representation. We simply restart the connection until we get good parameters.

For the details of the factorization algorithm, please refer to the solution script below.

 

how did we encrypt this?

 

Now we know the factorization of $M$. We can now check if $ctxt^2 - 4$ is a quadratic residue modulo $M$.

We test this for the ciphertext of the "the boy who lived" and the ciphertext of the flag. If this check fails, we run our algorithm again with a new connection for a good set of parameters. We now assume $ctxt^2 - 4$ is a quadratic residue.

 

We reasonably guess that our encryption algorithm will have used 16 primes out of the 35 consecutive primes larger than 31337.

We also verify that $p-1$ and $q-1$ are all coprime to these 35 candidate primes. If not, we look for a good set of parameters.

 

Now we can encrypt and decrypt as we like. Let's find out which 16 primes were used for encryption.

 

To do this, we use meet-in-the-middle algorithm. Basically what we do is

  • Split the set of 35 primes into two pieces, and assume that 8 primes were used in each piece
  • Calculate the encryption of "the boy who lived" with each combination of 8 primes of the first piece
  • Calculate the decryption of the ciphertext with each combination of 8 primes of the second piece
  • Find a match, and if there is one, we have found our set of 16 primes.
  • If not, we can try a new split of the primes and continue on.

Now we know which primes were used for encryption. All we need to do is decrypt the ciphertext of the flag.

 

additional notes

 

Note 1 : speeding up cast_riddikulus algorithm

  • This is a linear recurrence, so we can speedup using matrix multiplication
  • However, this is also a Lucas sequence used in Williams's $p+1$ algorithm
  • Therefore, we can just copy the implementation from Wikipedia to achieve a speedup.

Note 2 : requirements relaxation

  • If we assume that the flag is small, we only need to work with mod $p$ or mod $q$, instead of mod $M$.
  • Therefore, we can relax our quadratic residue conditions to "QR modulo at least one of the primes"
  • Thankfully, I was very lucky with the parameters and got QR modulo $M$.

Note 3 : meet-in-the-middle, but not quite middle

  • If we try to run the code, we can see that encryption is faster than decryption.
  • Therefore, it's reasonable to give the encryption part more work than just "half" of the bunch.

The solution code is displayed in parts for reader's understanding. Feel free to comment and ask questions...

 

reading parameters

1
2
3
4
5
6
7
8
9
10
11
12
13
def recvint():
    T = r.recvline()
    return int(T[:-1].decode(), 10)
 
 
def get_vals():
    r.recvline()
    C = recvint()
    N = recvint()
    H = bytes_to_long(b'the boy who lived')
    H_AFTER = recvint()
    F_AFTER = recvint()
    return C, N, H_AFTER, F_AFTER
cs

 

factorization of $M$

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
def bsum(x):
    ret = 0
    while x > 0:
        ret += x % 2
        x //= 2
    return ret 
 
def factor(N, C, cand, k):
    if len(cand) == 0:
        return
    print(k, len(cand))
    # fix pq mod 2^{k+1} by adding 2^k or not
    ret = []
    if (C >> k) % 2 == 1# we know p, q has 2^k
        for p, q in cand:
            if p * q == N:
                print(p)
                print(q)
                return
            pp = p + (1 << k)
            qq = q + (1 << k)
            if (pp * qq - N) % (1 << (k + 1)) == 0 and pp * qq <= N:
                ret.append((pp, qq))
        factor(N, C, ret, k + 1)
    else:
        for p, q in cand:
            if p * q == N:
                print(p)
                print(q)
                return
            for i in range(02):
                for j in range(02):
                    pp = p + i * (1 << k)
                    qq = q + j * (1 << k)
                    if (pp * qq - N) % (1 << (k + 1)) == 0 and pp * qq <= N:
                        ret.append((pp, qq))
        factor(N, C, ret, k + 1)
 
# M_N to M''_N
-=  C % (1 << 16)
&= (C + (1 << 16))
# check number of 1s, if bsum(C) is small (<256), stop and rerun
print(C.bit_length(), bsum(C)) 
# factorize
factor(N, C, [(11)], 1)
cs

 

encryption and decryption

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def mlucas(v, a, n): # encryption fast, from Wikipedia
    v1, v2 = v, (v**2 - 2) % n
    for bit in bin(a)[3:]:
        if bit == "0":
            v1, v2 = ((v1**2 - 2) % n, (v1*v2 - v) % n)
        else:
            v1, v2 = ((v1*v2 - v) % n, (v2**2 - 2) % n)
    return v1
 
def REV(val, ex, pr): # decryption modulo a prime
    # t^n + 1/t^n = val
    if val == 0# if invalid
        return 0 # return invalid
    cc = tonelli((val * val - 4) % pr, pr) # modular sqrt
    if cc == -1# failure
        return 0 # return failure
    tn = ((val + cc) * inverse(2, pr)) % pr
    t = pow(tn, inverse(ex, pr-1), pr)
    return ((t + inverse(t, pr))) % pr
cs

 

meet-in-the-middle

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
primes = [31337313573137931387313913139331397314693147731481314893151131513315173153131541315433154731567315733158331601316073162731643316493165731663316673168731699317213172331727317293174131751317693177131793]
 
= primes[15:35]
= primes[:15]
 
LV = []
RV = []
 
# generally, encryption is faster than decryption
# therefore, we leave the "heavy" work for the encryption part...
 
for combo_L in tqdm(itertools.combinations(L, 8)):
    CC = list(combo_L)
    cur = H
    # you can also just multiply all primes and encrypt at once
    for pr in combo_L:
        cur = mlucas(cur, pr, p)
    CC.append(cur)
    LV.append(CC)
 
print("LEFT DONE")
 
for combo_R in tqdm(itertools.combinations(R, 8)):
    CC = list(combo_R)
    cur = HAFTER
    # you can also just multiply all primes and decrypt at once
    for pr in combo_R:
        cur = REV(cur, pr, p)
    CC.append(cur)
    RV.append(CC)
 
print("RIGHT DONE")
 
for i in tqdm(range(len(LV))):
    for j in range(len(RV)):
        if LV[i][8== RV[j][8]:
            print("FOUND!!")
            print(LV[i])
            print(RV[j])
cs

 

the finish, and the parameters I got

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
= bytes_to_long(b'the boy who lived')
sys.setrecursionlimit(10 ** 6)
 
= 12124756848659098434025945489515506912896022954145117746118560512007665385702760439414990812257455576297349156226093149988609289245714223348281989890389750
= 157597985389833012337654133040126048344064622845161536236706459270343905778002470548499258715513540516431526518690532156245280894778788692043941237295606686168037171464988128988463706375526180496632421973522548093894845498612792150825707672843107252573999144787226703076358545319417530365329436368718460943493
HAFTER = 66161881147822169408519540711422900962287264738494143175834051626001922954586728648835878096124744364195826536091510407493007528877139856387261499433277826944946254511824024047480941829026088269865298686453128715170657018128276813244425143986311708022950785583195028647859774987948632731985531259912781472862
FAFTER = 149186530719822614329126547638374064715014252925601014676661223009475822460330945440469384214084001910035138025738722725987466200681944900264994344927428683388976167111544750466576538413516454786176229441173029050647235653998791477157269246962955063391947778663841551982999293815571149539542758304215156142104
 
-=  C % (1 << 16)
&= (C + (1 << 16))
 
# factor(N, C, [(1, 1)], 1)
 
= 12558711464274427739528720572494472142909592647353129013838950445222814801805965383430302364628487022743397586481672449715551542652546057434522020868473011
= 12548897698474048380978452887676419841595083766206501465313606366388795637681128899285066184154566275021196792336453455837893284460576050862858626214885863
 
# recovered set of primes
pr = [31543315673157331607316493166731687316993135731379313973146931477315133151731531]
hp = FAFTER % p 
hq = FAFTER % q 
 
# reverse
for i in pr:
    hp = REV(hp, i, p)
    hq = REV(hq, i, q)
 
flag, tt = CRT(hp, p, hq, q) # CRT
print(long_to_bytes(flag))
cs

'CTF' 카테고리의 다른 글

LINE CTF Crypto Writeups  (0) 2021.03.22
zer0pts CTF 2021 Crypto Writeups  (1) 2021.03.07
UnionCTF Crypto Writeups  (2) 2021.02.21
CryptoHack All Solve, Again  (10) 2021.01.31
0x41 CTF SPN Writeup  (0) 2021.01.31