crypto

saas

Every ctf has to have a chall called ‘saas’. Its just tradition.

Source

1
#!/usr/local/bin/python
2
from Crypto.Util.number import getPrime as gP
3
from random import choice, randint
4
p, q = gP(512), gP(512)
5
while p % 4 != 3:
6
    p = gP(512)
7

8
while q % 4 != 3:
9
    q = gP(512)
10

11
n = p * q
12
e = 0x10001
13

14
f = lambda x: ((choice([-1,1]) * pow(x, (p + 1) // 4, p)) * pow(q, -1, p) * q + (choice([-1,1]) * pow(x, (q + 1) // 4, q)) % q * pow(p, -1, q) * p) % n
15

16
while True:
17
    try:
18
        l = int(input(">>> ")) % n
19
        print(f(l))
20
    except:
21
        break
22

23
m = randint(0, n - 1)
24
print(f"{m = }")
25
s = int(input(">>> ")) % n
26
if pow(s,e,n) == m:
27
    print(open("flag.txt", "r").read())
28
else:
29
    print("Wrong signature!")
30
    exit(1)

The hint function f will let us factor n, which will allow us to easily forge RSA signatures.

1
f = lambda x: (
2
    (choice([-1,1]) * pow(x, (p + 1) // 4, p)) * pow(q, -1, p) * q +
3
    (choice([-1,1]) * pow(x, (q + 1) // 4, q)) % q * pow(p, -1, q) * p
4
) % n

Other inputs can be used as well, but the easiest way is to just enter 1 several times since it simplifies the pow(x, (p + 1) // 4, p) expressions. If x = 1, f simplifies to:

(\pm 1) * (q^{-1} \bmod p) * q + (\pm 1 \bmod q) * (p^{-1} \bmod q) * p \pmod n

Let’s consider the 4 cases based on the choice([-1, 1]) functions. If they’re both 1, then:

\begin{align*} (q^{-1} \bmod p) * q + (p^{-1} \bmod q) * p &= 1 \pmod p \\ (q^{-1} \bmod p) * q + (p^{-1} \bmod q) * p &= 1 \pmod q \\ &= 1 \pmod n \end{align*}

Well, that’s not very helpful. Let’s see what happens if they’re both -1.

\begin{align*} -(q^{-1} \bmod p) * q + (-1 \bmod q) * (p^{-1} \bmod q) * p &= -1 \pmod p \\ -(q^{-1} \bmod p) * q + (-1 \bmod q) * (p^{-1} \bmod q) * p &= -1 \pmod q \\ = -1 &= n - 1 \pmod n \end{align*}

Since we weren’t already given $n$ , this helps, but we still have to factor it. Let’s try -1 and then 1.

\begin{align*} -(q^{-1} \bmod p) * q + (p^{-1} \bmod q) * p &= -1 \pmod p \\ -(q^{-1} \bmod p) * q + (p^{-1} \bmod q) * p &= 1 \pmod q \\ &= x \pmod n \end{align*}

(Similarly, we can verify that 1 and then -1 gives $1 \bmod p$ and $-1 \bmod q$ ). If $x = -1 \bmod p$ then $\gcd(x+1, n) = p$ . Now that we know $n$ and $p$ , we can forge $s = m^d$ as usual. Connect to the server:

1
>>> 1
2
22584873973170387532631975715183528422437016681010618464581741882284345475758086005221539371683857475009200576502143088424522374562879237368635174156835283415890738492843061847279270354725129748353239745320933642792426188606836171676085221631281998525476933677154286648781607693710919190128678155081909268088
3
>>> 1
4
57515301216124622590566072376518371083992119569511667096809751291595343959859178121431978621164550685800822333376445699489444284601257225874255447364949171605200949316779305883182575252401100832245566541186202985973093581871838640842808631676969088876776493499364932189494081880465288341782241504351251269985
5
>>> 1
6
22584873973170387532631975715183528422437016681010618464581741882284345475758086005221539371683857475009200576502143088424522374562879237368635174156835283415890738492843061847279270354725129748353239745320933642792426188606836171676085221631281998525476933677154286648781607693710919190128678155081909268088
7
>>> 1
8
80100175189295010123198048091701899506429136250522285561391493173879689435617264126653517992848408160810022909878588787913966659164136463242890621521784455021091687809622367730461845607126230580598806286507136628765519770478674812518893853308251087402253427176519218838275689574176207531910919659433160538072
9
>>>
10
m = 53132934961200371180676162016341077654053922574943513666756222188084025661854865495927497737291401394349343056615078365876002760589653075983366529467611919986059455834413643048169959689387574237792950919554760828723038198835312635797931913782213768728290856702322316506344912730319204467752773777243157325701
11
>>> 20099041860533093891537787115551939590459747423543968198303933596565566658678985923271987920254172557043540713252140285247197236483427948785565652040279580299735124260366230344421118005522477491963228467520988599509254330856682864301571056119290774894214445107716375324246758240798939405391977606674070669038
12
.;,;.{squares_as_a_service_est_like_the_dawn_of_time}

(Since 801... is the largest, we know it must be $n - 1$ .)

Final script

1
from Crypto.Util.number import *
2
from math import gcd
3

4
out1 = 80100175189295010123198048091701899506429136250522285561391493173879689435617264126653517992848408160810022909878588787913966659164136463242890621521784455021091687809622367730461845607126230580598806286507136628765519770478674812518893853308251087402253427176519218838275689574176207531910919659433160538072
5
out2 = 57515301216124622590566072376518371083992119569511667096809751291595343959859178121431978621164550685800822333376445699489444284601257225874255447364949171605200949316779305883182575252401100832245566541186202985973093581871838640842808631676969088876776493499364932189494081880465288341782241504351251269985
6
m = 53132934961200371180676162016341077654053922574943513666756222188084025661854865495927497737291401394349343056615078365876002760589653075983366529467611919986059455834413643048169959689387574237792950919554760828723038198835312635797931913782213768728290856702322316506344912730319204467752773777243157325701
7

8
n = out1 + 1
9
p = gcd(n, out2 + 1)
10
q = n//p
11
e = 0x10001
12
phi = (p - 1) * (q - 1)
13
d = pow(e, -1, phi)
14
s = pow(m, d, n)
15

16
print(s)

Flag: .;,;.{squares_as_a_service_est_like_the_dawn_of_time}

never enough

Source

1
from random import getrandbits
2
from Crypto.Cipher import AES
3
from hashlib import sha256
4
danger = 624*32 # i hear you need this much.
5
given = []
6
key = ""
7
for _ in range(danger//20 - 16): # should be fine if im only giving u this much :3
8
    x = getrandbits(32)
9
    # we share <3
10
    key += str(x % 2**12)
11
    given.append(x >> 12)
12

13
key = key[:100]
14
key = sha256(key.encode()).digest()
15
flag = open("flag.txt", "rb").read().strip()
16
cipher = AES.new(key, AES.MODE_ECB)
17
print(given)
18
print(cipher.encrypt(flag + b"\x00" * (16 - len(flag) % 16)).hex())

This challenge clearly involves cracking python’s random, which is based on the mersenne twister algorithm. The script references the misconception that since the state of mersenne twister has 624 32-bit integers, you must need 624*32 bits of output in order to crack the generator, but it turns out you don’t need quite this many. Fortunately, we found a blog from rbtree (unfortunately in Korean, so we had to translate) covering a very similar challenge, so we won’t really have to understand the internals of the prng. As mentioned in rbtree’s post, for some reason it’s impossible to recover the lower bits of the first value of the state, so we had to bruteforce $2^{12}$ values to find the first part of the key. The vast majority of the solve script was taken directly from rbtree’s final code, and it takes about 2 minutes to run.

Final script

1
from tqdm import trange
2
from Crypto.Util.number import *
3
from hashlib import sha256
4
from Crypto.Cipher import AES
5
from Crypto.Util.Padding import unpad
6
import json
7
import random
8

9
class Twister:
10
    N = 624
11
    M = 397
12
    A = 0x9908b0df
13

14
    def __init__(self):
15
        self.state = [ [ (1 << (32 * i + (31 - j))) for j in range(32) ] for i in range(624)]
16
        self.index = 0
17

18
    @staticmethod
19
    def _xor(a, b):
20
        return [x ^ y for x, y in zip(a, b)]
21

22
    @staticmethod
23
    def _and(a, x):
24
        return [ v if (x >> (31 - i)) & 1 else 0 for i, v in enumerate(a) ]
25

26
    @staticmethod
27
    def _shiftr(a, x):
28
        return [0] * x + a[:-x]
29

30
    @staticmethod
31
    def _shiftl(a, x):
32
        return a[x:] + [0] * x
33

34
    def get32bits(self):
35
        if self.index >= self.N:
36
            for kk in range(self.N):
37
                y = self.state[kk][:1] + self.state[(kk + 1) % self.N][1:]
38
                z = [ y[-1] if (self.A >> (31 - i)) & 1 else 0 for i in range(32) ]
39
                self.state[kk] = self._xor(self.state[(kk + self.M) % self.N], self._shiftr(y, 1))
40
                self.state[kk] = self._xor(self.state[kk], z)
41
            self.index = 0
42

43
        y = self.state[self.index]
44
        y = self._xor(y, self._shiftr(y, 11))
45
        y = self._xor(y, self._and(self._shiftl(y, 7), 0x9d2c5680))
46
        y = self._xor(y, self._and(self._shiftl(y, 15), 0xefc60000))
47
        y = self._xor(y, self._shiftr(y, 18))
48
        self.index += 1
49

50
        return y
51

52
    def getrandbits(self, bit):
53
        return self.get32bits()[:bit]
54

55
class Solver:
56
    def __init__(self):
57
        self.equations = []
58
        self.outputs = []
59

60
    def insert(self, equation, output):
61
        for eq, o in zip(self.equations, self.outputs):
62
            lsb = eq & -eq
63
            if equation & lsb:
64
                equation ^= eq
65
                output ^= o
66

67
        if equation == 0:
68
            return
69

70
        lsb = equation & -equation
71
        for i in range(len(self.equations)):
72
            if self.equations[i] & lsb:
73
                self.equations[i] ^= equation
74
                self.outputs[i] ^= output
75

76
        self.equations.append(equation)
77
        self.outputs.append(output)
78

79
    def solve(self):
80
        num = 0
81
        for i, eq in enumerate(self.equations):
82
            if self.outputs[i]:
83
                # Assume every free variable is 0
84
                num |= eq & -eq
85

86
        state = [ (num >> (32 * i)) & 0xFFFFFFFF for i in range(624) ]
87
        return state
88

89
num = ((624 * 32)//20 - 16)
90
bit = 20
91
twister = Twister()
92

93
with open('out.txt') as f:
94
    lines = f.readlines()
95
    outputs = json.loads(lines[0])
96
    enc = bytes.fromhex(lines[1])
97

98
equations = [ twister.getrandbits(bit) for _ in range(num) ]
99

100
solver = Solver()
101
for i in trange(num):
102
    for j in range(bit):
103
        #print(i, j)
104
        solver.insert(equations[i][j], (outputs[i] >> (bit - 1 - j)) & 1)
105

106
state = solver.solve()
107
recovered_state = (3, tuple(state + [0]), None)
108
random.setstate(recovered_state)
109

110
for i in range(num):
111
    assert outputs[i] == (random.getrandbits(bit))
112

113
for i in range(2**12): # brute force the first output of the key
114
    random.setstate(recovered_state)
115
    random.getrandbits(32)
116
    key = ""
117
    for _ in range(30):
118
        x = random.getrandbits(32)
119
        key += str(x % 2**12)
120

121
    length = len(str(i))
122
    key = str(i) + key[0:100 - length]
123
    assert len(key) == 100
124
    key = sha256(key.encode()).digest()
125
    cipher = AES.new(key, AES.MODE_ECB)
126
    dec = cipher.decrypt(enc)
127
    if b'.;,;.' in dec:
128
        print(dec.rstrip(b'\x00').decode('ascii'))
129
        break

Flag: .;,;.{never_enough_but_you_gotta_just_make_more_or_something_idk_im_not_a_motivational_speaker_but_you_get_the_idea}

LCGs are SBGs

TODO (or is wjat doing this or something)

sums

I have a funny game, unfortunately the odds of you winning are basically 0, but I’m bored, so play with me and I’ll give you a flag if you win.

This challenge is a bit more complicated, but the main code is in sums.py. The Dockerfile has a reference to https://github.com/tsunrise/sumcheck_multilinear/, which has most of the other files along with the associated paper.

Source

1
#!/usr/local/bin/python
2
from IPVerifier import InteractiveVerifier
3
from IPProverLinear import InteractiveLinearProver
4
from polynomial import randomMVLinear
5
from random import randint
6
P = 2**256 - 189
7
NUM_VARS = 10
8
seed = randint(0, 2**64)
9
tries = 3
10
verifier = InteractiveVerifier(seed, randomMVLinear(10, P), 0)
11
def prime_verifier(poly, s_claim):
12
    global verifier
13
    verifier.poly = poly
14
    verifier.asserted_sum = s_claim % P
15
    verifier.active = True
16
    verifier.convinced = False
17
    verifier.round = 0
18
    verifier.expect = s_claim % P
19

20
def random_poly():
21
    poly = randomMVLinear(10, P)
22
    return poly
23

24

25
def do_run():
26
    global tries
27
    poly = random_poly()
28
    while (s_actual:=InteractiveLinearProver(poly).calculateTable()[1]) == 1337:
29
        poly = random_poly()
30
    print("Polynomial: ", poly.terms)
31
    s_claim = int(input("Enter the sum: "))
32
    prime_verifier(poly, s_claim)
33
    p0 = int(input("Enter P(0): ")) % P
34
    p1 = int(input("Enter P(1): ")) % P
35
    res = verifier.talk(p0, p1)
36
    if not res[0]:
37
        print("CHEATER!")
38
        return False
39
    print("Your odds: ", verifier.soundnessError())
40
    play = input("Do you want to play? (y/n): ")
41
    if play != "y":
42
        print("Bye")
43
        return False
44
    tries -= 1
45
    while verifier.active:
46
        print(f"challenge: {res}")
47
        p0 = int(input("Enter P(0): ")) % P
48
        p1 = int(input("Enter P(1): ")) % P
49
        res = verifier.talk(p0, p1)
50
        if not res[0]:
51
            print("CHEATER!")
52
            return False
53
    if not verifier.convinced:
54
        return False
55

56
    if s_claim != s_actual and s_claim == 1337:
57
        print("Wow...")
58
        return True
59
    return False # congrats, you played and lost...
60

61
def main():
62
    while tries:
63
        if do_run():
64
            print("Hmm, you won my game?")
65
            print("Flag: " + open("flag.txt", "r").read())
66
            break
67
        else:
68
            print("Skissue + get good")
69
            print("You have {} tries left".format(tries))
70

71

72

73
if __name__ == "__main__":
74
    main()

The challenge implements the SumCheck protocol, where we take the role of the prover and attempt to convince the verifier that the sum of a certain polynomial is 1337. Most of the paper isn’t that important, but it’s worth looking at the table in section 2.3 to get a general understanding of the protocol. asdf In each run, the code sends f, a randomly generated multilinear polynomial in 10 variables. A multilinear polynomial is a polynomial that’s linear in each of its variables separately, but not necessarily linear as a whole. For example, $f(x, y) = xy + 3x$ is multilinear but $f(x, y) = y^2 + 3x$ isn’t. When generating the polynomial, the script verifies that the sum $\sum_{b_1, \dots, b_{10} \in \{0,1\}} f(b_1, b_2, \ldots, b_{10}) \neq 1337$ in the while loop, but if we want to get the flag we have to claim that the sum is 1337. Then, just like in the protocol, we send $f_1(0)$ and $f_1(1)$ and in verifier.talk(p0, p1) the script verifies that our claimed s_claim is equal to p0 + p1. Then it asks if we want to play the game, and if so the protocol continues as in the paper. Note that one of our 3 tries is used up only if we decide to play.

The vuln

We already know from never enough that python’s random module is inherently weak, so it is interesting to see a seed given to the InteractiveVerifier. From the source code in IPVerifier.py below, we can verify that python’s random module is being used with the given seed.

1
"""
2
Interactive Verifier of Multilinear Polynomial Sum
3
Tom Shen
4
"""
5
import math
6
from random import Random
7
from typing import List, Tuple
8

9
from polynomial import MVLinear
10

11
DEFAULT_MAX_ALLOWED_SOUNDNESS_ERROR = 2 ** (-32)
12

13

14
class InteractiveVerifier:
15
    """
16
    An interactive verifier that verifies the sum of the multi-linear polynomial
17
    """
18

19
    def __init__(self, seed: int, polynomial: MVLinear, asserted_sum: int,
20
                 maxAllowedSoundnessError: float = DEFAULT_MAX_ALLOWED_SOUNDNESS_ERROR):
21
        """
22
        Initialize the protocol of the verifier.
23
        :param seed: the random source
24
        :param polynomial: The multilinear function
25
        :param asserted_sum: The proposed sum (0 and 1) of the multilinear function (which is to be verified)
26
        :param maxAllowedSoundnessError: the maximum soundness error allowed
27
        """
28
        self.p: int = polynomial.p
29
        """
30
        The field size
31
        """
32
        self.poly: MVLinear = polynomial
33
        self.asserted_sum: int = asserted_sum % self.p
34
        self.rand: Random = Random()
35
        self.rand.seed(seed)
36

37
        self.active: bool = True
38
        self.convinced: bool = False
39

40
        # check soundness
41
        if self.soundnessError() > maxAllowedSoundnessError:
42
            raise SoundnessErrorException(f"Soundness error {self.soundnessError()} exceeds maximum "
43
                                          f"allowed soundness error {maxAllowedSoundnessError}\n"
44
                                          f"Try to have a prime "
45
                                          f"with size "
46
                                          f">= {self.requiredFieldLengthBit(maxAllowedSoundnessError)} bits")
47

48
        # some edge case: if univariate or constant: no need to be interactive
49
        if polynomial.num_variables == 0:
50
            if (asserted_sum - polynomial.eval([])) % self.p == 0:
51
                self._convince_and_close()
52
                return
53
            else:
54
                self._reject_and_close()
55
                return
56
        if polynomial.num_variables == 1:
57
            result = (polynomial.eval([0]) + polynomial.eval([1])) % self.p
58
            if (asserted_sum - result) % self.p == 0:
59
                self._convince_and_close()
60
                return
61
            else:
62
                self._reject_and_close()
63
                return
64

65
        self.points: List[int] = [0] * self.poly.num_variables
66
        """
67
        the fixed points that are already decided by the verifier. At round i, [0, i-1] are decided
68
        """
69

70
        self.round: int = 0
71
        """
72
        which variable the verifier is summing (at round i, var 0 to var (i-1) is fixed, and the verifier is listening
73
        to the univariate function of variable i where var[i+1, n] is summed over.
74
        """
75

76
        self.expect: int = self.asserted_sum
77
        """
78
        The expected sum value at round i
79
        """
80

81
    def soundnessError(self) -> float:
82
        """
83
        Get the soundness error according to the MVLinear and field size.
84
        :return: The float representing the upper bound of probability of accepting when assertion is invalid.
85
        """
86

87
        n = self.poly.num_variables
88
        return (n * n) / self.p
89

90
    def requiredFieldLengthBit(self, e: float) -> int:
91
        """
92
        :param e: the maximum allowed soundness error
93
        :return: The minimum size of prime required to meet the soundness error constraint.
94
        """
95
        n = self.poly.num_variables
96
        minP = (n * n) / e
97
        return math.ceil(math.log(minP, 2)) + 1
98

99
    def randomR(self) -> int:
100
        return self.rand.randint(0, self.p)
101

102
    def talk(self, p0: int, p1: int) -> Tuple[bool, int]:
103
        """
104
        Send the verifier the univariate linear polynomial P(x).
105
        At round i, P(x) = sum over b: P(r_1, ..., r_i-1, x, b_i+1, b_i+2, ...)
106
        where r is fixed (as proposed by self.points)
107
        :param p0: P(0)
108
        :param p1: P(1)
109
        :return: a tuple (accept?, random r for x). If accept? is false, the returned integer is meaningless.
110
        """
111

112
        # if the protocol is not active, throw an error
113
        if not self.active:
114
            raise RuntimeError("Unable to prove: the protocol is not active. ")
115

116
        # check that P(0) + P(1) is in fact self.expect
117
        p0 %= self.p
118
        p1 %= self.p
119
        if (p0 + p1) % self.p != self.expect % self.p:
120
            self._reject_and_close()
121
            return False, 0
122

123
        # pick r at random
124
        r: int = self.randomR()
125
        pr: int = (p0 + r * (p1 - p0)) % self.p  # gradient formula
126
        self.expect = pr
127
        self.points[self.round] = r
128

129
        # if not final step, end here
130
        if not (self.round + 1 == self.poly.num_variables):
131
            self.round += 1
132
            return True, r
133

134
        # final step: check all
135
        final_sum = self.poly.eval(self.points)
136
        if pr != final_sum:
137
            self._reject_and_close()
138
            return False, 0
139
        self._convince_and_close()
140
        return True, 0
141

142
    def _convince_and_close(self):
143
        """
144
        Accept the sum. Close the protocol.
145
        """
146
        self.convinced = True
147
        self.active = False
148

149
    def _reject_and_close(self):
150
        """
151
        Reject the sum. Close the protocol
152
        """
153
        self.convinced = False
154
        self.active = False
155

156

157
class SoundnessErrorException(Exception):
158
    pass

In the code, the random function is only used in self.randomR(). If we are able to know future r values before they’re produced, it seems like we’d be able to falsely convince the verifier that the sum if 1337. So we now need to consider how many outputs of the rng we’re able to get. self.randomR() returns self.rand.randint(0, self.p), and since P = 2**256 - 189 it is essentially the same as getrandbits(256). Mersenne twister contains a state of 624 32-bit numbers, so for each r we’re given 8 outputs of the rng. Then, in each run the verifier sends us 9 r values (a 10th r is generated, but never sent), and there are 3 runs in total. So we’re given 9*8*3 = 216 outputs, which clearly isn’t enough to fully reconstruct the state of length 624. Fortunately, we don’t actually have to reconstruct the entire state to predict a few outputs. It turns out we only need to predict $r_{10}$ to be able to fool the verifier. Anyway, let’s take a look at the source code for python’s random.

1
/* Period parameters -- These are all magic.  Don't change. */
2
#define N 624
3
#define M 397
4
#define MATRIX_A 0x9908b0dfU    /* constant vector a */
5
#define UPPER_MASK 0x80000000U  /* most significant w-r bits */
6
#define LOWER_MASK 0x7fffffffU  /* least significant r bits */
7

8
static uint32_t
9
genrand_uint32(RandomObject *self)
10
{
11
    uint32_t y;
12
    static const uint32_t mag01[2] = {0x0U, MATRIX_A};
13
    /* mag01[x] = x * MATRIX_A  for x=0,1 */
14
    uint32_t *mt;
15

16
    mt = self->state;
17
    if (self->index >= N) { /* generate N words at one time */
18
        int kk;
19

20
        for (kk=0;kk<N-M;kk++) {
21
            y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
22
            mt[kk] = mt[kk+M] ^ (y >> 1) ^ mag01[y & 0x1U];
23
        }
24
        for (;kk<N-1;kk++) {
25
            y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
26
            mt[kk] = mt[kk+(M-N)] ^ (y >> 1) ^ mag01[y & 0x1U];
27
        }
28
        y = (mt[N-1]&UPPER_MASK)|(mt[0]&LOWER_MASK);
29
        mt[N-1] = mt[M-1] ^ (y >> 1) ^ mag01[y & 0x1U];
30

31
        self->index = 0;
32
    }
33

34
    y = mt[self->index++];
35
    y ^= (y >> 11);
36
    y ^= (y << 7) & 0x9d2c5680U;
37
    y ^= (y << 15) & 0xefc60000U;
38
    y ^= (y >> 18);
39
    return y;
40
}

As we can see, the mt state has length 624, and once 624 random numbers have been generated, it generates a new state within the for loops. Then whenever we generate a random number, it takes the number from the state and applies the xor operations called tempering. Thankfully, the process is invertible, so we can get a number in the state from the output y and vice versa. The untemper functions were taken from rbtree’s blog.

1
TemperingMaskB = 0x9d2c5680
2
TemperingMaskC = 0xefc60000
3

4
def temper(y):
5
    y ^= (y >> 11)
6
    y ^= (y << 7) & TemperingMaskB
7
    y ^= (y << 15) & TemperingMaskC
8
    y ^= (y >> 18)
9
    return y
10

11
def untemper(y):
12
    y = undoTemperShiftL(y)
13
    y = undoTemperShiftT(y)
14
    y = undoTemperShiftS(y)
15
    y = undoTemperShiftU(y)
16
    return y
17

18
def undoTemperShiftL(y):
19
    last14 = y >> 18
20
    final = y ^ last14
21
    return final
22

23
def undoTemperShiftT(y):
24
    first17 = y << 15
25
    final = y ^ (first17 & TemperingMaskC)
26
    return final
27

28
def undoTemperShiftS(y):
29
    a = y << 7
30
    b = y ^ (a & TemperingMaskB)
31
    c = b << 7
32
    d = y ^ (c & TemperingMaskB)
33
    e = d << 7
34
    f = y ^ (e & TemperingMaskB)
35
    g = f << 7
36
    h = y ^ (g & TemperingMaskB)
37
    i = h << 7
38
    final = y ^ (i & TemperingMaskB)
39
    return final
40

41
def undoTemperShiftU(y):
42
    a = y >> 11
43
    b = y ^ a
44
    c = b >> 11
45
    final = y ^ c
46
    return final

Here is the for loop in the source code that generates the first part of a new state.

1
        for (kk=0;kk<N-M;kk++) {
2
            y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
3
            mt[kk] = mt[kk+M] ^ (y >> 1) ^ mag01[y & 0x1U];
4
        }

Notice mt[i] only depends on the previous mt[i], mt[i+1], and mt[i+M] (where M = 397). Also notice that an r is generated in the verifier script even if we respond n when asked if we want to play the game. Though we can’t actually see the generated r, the fact that we can force the script to generate an r means we can progress through the state of the rng. Since we get 3 tries this means:

First try: we can submit whatever data to gather the r values based on mt[i]
Second try: we want to gather the r values generated around mt[M], so before our second try we should refuse to play the game about 39 times, since that means mersenne twister would have generated 49*8 = 392 values in total.
Third try: using the data from mt[0:72] and mt[392:464], we can compute at least mt[0:64] (and a little more) in the new state. Thus we will refuse to play the game around 15 more times, so that somewhere through our third try the new mersenne twister state will be generated. Then we will be able to predict $r_{10}$ and fool the verifier

Now there is only one more detail to figure out. How do we actually fool the verifier if we can predict $r_{10}$ ?

1
    def talk(self, p0: int, p1: int) -> Tuple[bool, int]:
2
        """
3
        Send the verifier the univariate linear polynomial P(x).
4
        At round i, P(x) = sum over b: P(r_1, ..., r_i-1, x, b_i+1, b_i+2, ...)
5
        where r is fixed (as proposed by self.points)
6
        :param p0: P(0)
7
        :param p1: P(1)
8
        :return: a tuple (accept?, random r for x). If accept? is false, the returned integer is meaningless.
9
        """
10

11
        # if the protocol is not active, throw an error
12
        if not self.active:
13
            raise RuntimeError("Unable to prove: the protocol is not active. ")
14

15
        # check that P(0) + P(1) is in fact self.expect
16
        p0 %= self.p
17
        p1 %= self.p
18
        if (p0 + p1) % self.p != self.expect % self.p:
19
            self._reject_and_close()
20
            return False, 0
21

22
        # pick r at random
23
        r: int = self.randomR()
24
        pr: int = (p0 + r * (p1 - p0)) % self.p  # gradient formula
25
        self.expect = pr
26
        self.points[self.round] = r
27

28
        # if not final step, end here
29
        if not (self.round + 1 == self.poly.num_variables):
30
            self.round += 1
31
            return True, r
32

33
        # final step: check all
34
        final_sum = self.poly.eval(self.points)
35
        if pr != final_sum:
36
            self._reject_and_close()
37
            return False, 0
38
        self._convince_and_close()
39
        return True, 0

The talk function is used to verify each of our inputs according to the protocol. When we make our third attempt, we clearly want to claim that the sum is 1337. For every round before the final round, all we need to do is supply p0 and p1 such that p0 + p1 == self.expect mod p. Personally, I just made p0 and p1 equal so that I wouldn’t have to deal with pr depending on r. For the last round, still we have that p0 + p1 == self.expect mod p, but now we also must make pr == final_sum == 1337. Notice that the final r is never sent to the prover, so there would be essentially no chance of coming up with the same final. But since we do have r, we can just solve the equations for p0 and p1.

\begin{align*} p_0 + p_1 &= \mathrm{self.expect} \pmod P \\ p_0 + r * (p_1 - p_0) &= \mathrm{actual\_sum} \pmod P \end{align*}

Final Script

The script takes almost 5 minutes because of the amount of time the server spends generating random polynomials that we don’t actually care about. Anyway this was a very fun chall.

1
from pwn import *
2
from tqdm import trange
3
from polynomial import MVLinear
4

5
P = 2**256 - 189
6
io = remote('smiley.cat', 44873, level='error')
7

8
TemperingMaskB = 0x9d2c5680
9
TemperingMaskC = 0xefc60000
10

11
def temper(y):
12
    y ^= (y >> 11)
13
    y ^= (y << 7) & TemperingMaskB
14
    y ^= (y << 15) & TemperingMaskC
15
    y ^= (y >> 18)
16
    return y
17

18
def untemper(y):
19
    y = undoTemperShiftL(y)
20
    y = undoTemperShiftT(y)
21
    y = undoTemperShiftS(y)
22
    y = undoTemperShiftU(y)
23
    return y
24

25
def undoTemperShiftL(y):
26
    last14 = y >> 18
27
    final = y ^ last14
28
    return final
29

30
def undoTemperShiftT(y):
31
    first17 = y << 15
32
    final = y ^ (first17 & TemperingMaskC)
33
    return final
34

35
def undoTemperShiftS(y):
36
    a = y << 7
37
    b = y ^ (a & TemperingMaskB)
38
    c = b << 7
39
    d = y ^ (c & TemperingMaskB)
40
    e = d << 7
41
    f = y ^ (e & TemperingMaskB)
42
    g = f << 7
43
    h = y ^ (g & TemperingMaskB)
44
    i = h << 7
45
    final = y ^ (i & TemperingMaskB)
46
    return final
47

48
def undoTemperShiftU(y):
49
    a = y >> 11
50
    b = y ^ a
51
    c = b >> 11
52
    final = y ^ c
53
    return final
54

55
def r_to_32(r):
56
    # converts the raw r values to 8 32-bit rng outputs
57
    binary = bin(r)[2:].zfill(256)
58
    return [int(binary[32*i:32*i+32], 2) for i in range(8)][::-1]
59

60
def flatten(xss):
61
    # flattens list
62
    return [x for xs in xss for x in xs]
63

64
N = 624
65
M = 397
66
MATRIX_A = 0x9908b0df
67
UPPER_MASK = 0x80000000
68
LOWER_MASK = 0x7fffffff
69

70
def gen_next_state(first_part, second_part):
71
    # first part of state is mt[0:length]
72
    # second part of state is mt[M:M+length]
73
    # this will generate new mt[0:length-1]
74

75
    assert len(first_part) == len(second_part)
76

77
    mag01 = [0x0, MATRIX_A]
78

79
    mt = []
80
    for i in range(len(first_part) - 1):
81
        y = (first_part[i]&UPPER_MASK) | (first_part[i+1]&LOWER_MASK)
82
        mt.append(second_part[i] ^ (y >> 1) ^ mag01[y & 0x1])
83

84
    return mt
85

86
def gen_next_random_values(state):
87
    # state is list of 64
88
    # this will generate next 8 r-values
89
    nums = [temper(i) for i in state]
90

91
    rs = []
92
    for i in range(len(state)//8):
93
        r_nums = nums[i*8:i*8+8]
94
        r = int(''.join([bin(i)[2:].zfill(32) for i in r_nums][::-1]), 2)
95
        rs.append(r)
96

97
    return rs
98

99
def send_values(p0, p1):
100
    io.sendlineafter(b"Enter P(0):", str(p0).encode())
101
    io.sendlineafter(b"Enter P(1):", str(p1).encode())
102

103
def gen_ps(expected_sum):
104
    # finds p0 and p1 such that p0 + p1 == expected_sum (and p0 == p1)
105
    if expected_sum % 2 == 0:
106
        return expected_sum // 2
107
    else:
108
        return (expected_sum + P) // 2
109

110
def parse_poly(line):
111
    return MVLinear(10, eval(line.strip("Polynomial: ")), P)
112

113
def round_loop(play, last_r=0):
114
    poly = parse_poly(io.recvline().decode('ascii'))
115

116
    expect = 1337
117
    io.sendlineafter(b"Enter the sum:", str(expect).encode())
118

119
    p = gen_ps(expect)
120
    send_values(p, p)
121
    expect = p
122

123
    line = io.recvuntil(b"Do you want to play? (y/n):")
124
    if play:
125
        io.sendline(b"y")
126
    else:
127
        io.sendline(b"n")
128
        io.recvline()
129
        io.recvline()
130
        io.recvline()
131
        return None
132

133
    rs = []
134

135
    for i in range(8):
136
        challenge = eval(io.recvline()[12:-1])
137
        assert challenge[0] == True
138
        r = challenge[1]
139
        rs.append(r)
140

141
        p = gen_ps(expect)
142
        send_values(p, p)
143
        expect = p
144

145
    challenge = eval(io.recvline()[12:-1])
146
    assert challenge[0] == True
147
    r = challenge[1]
148
    rs.append(r)
149
    assert len(rs) == 9
150

151
    if last_r == 0:
152
        p = gen_ps(expect)
153
        send_values(p, p)
154
        expect = p
155
    else:
156
        rs.append(last_r)
157
        actual_sum = poly.eval(rs)
158
        p0 = ((actual_sum - last_r*expect) * pow(1 - 2*last_r, -1, P)) % P
159
        p1 = (expect - p0) % P
160
        assert (p0 + last_r * (p1 - p0)) % P == actual_sum
161
        assert (p0 + p1) % P == expect
162
        send_values(p0, p1)
163

164
    print(io.recvline().decode('ascii'))
165
    print(io.recvline().decode('ascii'))
166
    print(io.recvline().decode('ascii'))
167
    return rs
168

169
first_part = round_loop(True)
170
first_part = flatten([r_to_32(i) for i in first_part])
171
first_part = [untemper(i) for i in first_part][:-5]
172

173
ignore = [round_loop(False) for _ in trange(39)]
174

175
second_part = round_loop(True)
176
second_part = flatten([r_to_32(i) for i in second_part])
177
second_part = [untemper(i) for i in second_part][5:]
178

179
ignore = [round_loop(False) for _ in trange(15)]
180
next_state = gen_next_state(first_part, second_part)[:64]
181
next_rs = gen_next_random_values(next_state)
182
next_last_r = next_rs[5]
183

184
final_play = round_loop(True, next_last_r)

Flag: .;,;.{sumcheck_needs_secure_random...}

smileyCTF 2025 crypto writeups

saas

Source

Final script

never enough

Source

Final script

LCGs are SBGs

sums

Source

The vuln

Final Script