Source code
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/python3
# Copyright 2022 Google LLC
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
# http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.
"""
It is well known that any RSA encryption can be undone by just encrypting the
ciphertext over and over again. If the RSA modulus has been chosen badly then
the number of encryptions necessary to undo an encryption is small.
If n = 0x112b00148621 then only 209 encryptions are necessary as the following
example demonstrates:
>>> e = 65537
>>> n = 0x112b00148621
>>> pt = 0xdeadbeef
>>> # Encryption
>>> ct = pow(pt, e, n)
>>> # Decryption via cycling:
>>> pt = ct
>>> for _ in range(209):
>>> pt = pow(pt, e, n)
>>> # Assert decryption worked:
>>> assert ct == pow(pt, e, n)
However, if the modulus is well chosen then a cycle attack can take much longer.
This property can be used for a timed release of a message. We have confirmed
that it takes a whopping 2^1025-3 encryptions to decrypt the flag. Pack out
your quantum computer and perform 2^1025-3 encryptions to solve this
challenge. Good luck doing this in 48h.
"""
e = 65537
n = 0x99efa9177387907eb3f74dc09a4d7a93abf6ceb7ee102c689ecd0998975cede29f3ca951feb5adfb9282879cc666e22dcafc07d7f89d762b9ad5532042c79060cdb022703d790421a7f6a76a50cceb635ad1b5d78510adf8c6ff9645a1b179e965358e10fe3dd5f82744773360270b6fa62d972d196a810e152f1285e0b8b26f5d54991d0539a13e655d752bd71963f822affc7a03e946cea2c4ef65bf94706f20b79d672e64e8faac45172c4130bfeca9bef71ed8c0c9e2aa0a1d6d47239960f90ef25b337255bac9c452cb019a44115b0437726a9adef10a028f1e1263c97c14a1d7cd58a8994832e764ffbfcc05ec8ed3269bb0569278eea0550548b552b1
ct = 0x339be515121dab503106cd190897382149e032a76a1ca0eec74f2c8c74560b00dffc0ad65ee4df4f47b2c9810d93e8579517692268c821c6724946438a9744a2a95510d529f0e0195a2660abd057d3f6a59df3a1c9a116f76d53900e2a715dfe5525228e832c02fd07b8dac0d488cca269e0dbb74047cf7a5e64a06a443f7d580ee28c5d41d5ede3604825eba31985e96575df2bcc2fefd0c77f2033c04008be9746a0935338434c16d5a68d1338eabdcf0170ac19a27ec832bf0a353934570abd48b1fe31bc9a4bb99428d1fbab726b284aec27522efb9527ddce1106ba6a480c65f9332c5b2a3c727a2cca6d6951b09c7c28ed0474fdc6a945076524877680
# Decryption via cycling:
pt = ct
for _ in range(2**1025 - 3):
pt = pow(pt, e, n)
# Assert decryption worked:
assert ct == pow(pt, e, n)
# Print flag:
print(pt.to_bytes((pt.bit_length() + 7)//8, 'big').decode())
Solutions
Attack 1: Factoring n
From the name and the description of the challenge, it is pretty clear that this is somehow related to the cycling attack on RSA.
The original attack
As described in this paper, the attack works as follows:
Given a seed and a boundary B on top of the public key parameters,
The first while loop only exists in case there exists an aperiodic part in the sequence and could be skipped. In the paper however, they do describe how to prevent such an attack and it seems like what we were given achieved exactly that.
The flaw
Now however, we are given another import information:
We have confirmed that it takes a whopping 2^1025-3 encryptions to decrypt the flag
With this we are given the order of the order of the modulus or in other words:
\[\lambda(\lambda(n))\]Where $\lambda$ is the Carmichael Function which is defined as [1]:
\[\lambda(2^k) = 2\lambda(2^{k-1})\] \[\lambda(p) = p-1, \lambda(p^k) = p\lambda(p^{k-1})\] \[\lambda(n) = lcm (\lambda(p_1^{e_1}), \lambda(p_2^{e_2}), ...., \lambda(p_j^{e_j}))\ where\ n = \prod_{i=1}^jp_i^{e_j}\]The attack
Now let’s set $\lambda(n) = x$ we are given $\lambda(x) = 2^{1025}-2$. Using factordb we can easily find the factors and realize that none of them have a power of 2 or more. With this list, we can now find another list of potential prime numbers $p_i$ that would be able to make such a $\lambda(x)$. This list has potential candidates of lambda factors and using these we can try and find the actual $\lambda(n)=\phi(n)$.
Reminder, euler’s theroem states that:
\[\alpha^{\phi(n)} = 1\ mod\ n\]as long as $\alpha$ and $n$ are relatively prime. Picking 2 in this case ensures that so now there is only to subtract 1 and if we find $\phi(n)$ then we will get a factor
Solve script
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
from math import gcd
import itertools
from operator import mul
from functools import reduce
e = 65537
n = 0x99efa9177387907eb3f74dc09a4d7a93abf6ceb7ee102c689ecd0998975cede29f3ca951feb5adfb9282879cc666e22dcafc07d7f89d762b9ad5532042c79060cdb022703d790421a7f6a76a50cceb635ad1b5d78510adf8c6ff9645a1b179e965358e10fe3dd5f82744773360270b6fa62d972d196a810e152f1285e0b8b26f5d54991d0539a13e655d752bd71963f822affc7a03e946cea2c4ef65bf94706f20b79d672e64e8faac45172c4130bfeca9bef71ed8c0c9e2aa0a1d6d47239960f90ef25b337255bac9c452cb019a44115b0437726a9adef10a028f1e1263c97c14a1d7cd58a8994832e764ffbfcc05ec8ed3269bb0569278eea0550548b552b1
ct = 0x339be515121dab503106cd190897382149e032a76a1ca0eec74f2c8c74560b00dffc0ad65ee4df4f47b2c9810d93e8579517692268c821c6724946438a9744a2a95510d529f0e0195a2660abd057d3f6a59df3a1c9a116f76d53900e2a715dfe5525228e832c02fd07b8dac0d488cca269e0dbb74047cf7a5e64a06a443f7d580ee28c5d41d5ede3604825eba31985e96575df2bcc2fefd0c77f2033c04008be9746a0935338434c16d5a68d1338eabdcf0170ac19a27ec832bf0a353934570abd48b1fe31bc9a4bb99428d1fbab726b284aec27522efb9527ddce1106ba6a480c65f9332c5b2a3c727a2cca6d6951b09c7c28ed0474fdc6a945076524877680
#factordb
primes = [2, 3, 5, 17, 257, 641, 65537, 274177, 2424833, 6700417, 67280421310721, 1238926361552897, 59649589127497217, 5704689200685129054721, 7455602825647884208337395736200454918783366342657, 93461639715357977769163558199606896584051237541638188580280321, 741640062627530801524787141901937474059940781097519023905821316144415759504705008092818711693940737]
#cycling attack with potential factors of lm(x)
huge = 2
huge = pow(huge, reduce(mul, primes)**4, n)
for i in itertools.chain.from_iterable([itertools.combinations(primes, j),print(j)][0] for j in range(1,len(primes))):
huge = pow(huge, reduce(mul, i)+1, n)
g = gcd(huge - 1, n)
if g > 1:
print("found factor",g)
break
if huge == 1:
print("you goofed")
break
p = g
assert n%p == 0
print(n//p)
# RSA decryption
q = n//p
phi = (p-1)*(q-1)
d = pow(e, -1, phi)
pt = pow(ct, d, n)
print(pt.to_bytes((pt.bit_length() + 7)//8, 'big'))
Attack 2: Using lambda to get to the private key
This second attack isn’t what the offical used but still interesting. While in the previous one, we picked between all the possible condidate factors of $\lambda(n)$ until we found the right ones to factorize, we also know that the list we have will contain all the factors. Thus there product will be by definition a multiple of $\lambda(n)$. This more than enough to reconstruct the private key and thus we can use this to attack:
Solve Script
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
from gmpy2 import mpz
from itertools import product as iter_product
from tqdm.auto import tqdm
e = 65537
n = 0x99efa9177387907eb3f74dc09a4d7a93abf6ceb7ee102c689ecd0998975cede29f3ca951feb5adfb9282879cc666e22dcafc07d7f89d762b9ad5532042c79060cdb022703d790421a7f6a76a50cceb635ad1b5d78510adf8c6ff9645a1b179e965358e10fe3dd5f82744773360270b6fa62d972d196a810e152f1285e0b8b26f5d54991d0539a13e655d752bd71963f822affc7a03e946cea2c4ef65bf94706f20b79d672e64e8faac45172c4130bfeca9bef71ed8c0c9e2aa0a1d6d47239960f90ef25b337255bac9c452cb019a44115b0437726a9adef10a028f1e1263c97c14a1d7cd58a8994832e764ffbfcc05ec8ed3269bb0569278eea0550548b552b1
ct = 0x339be515121dab503106cd190897382149e032a76a1ca0eec74f2c8c74560b00dffc0ad65ee4df4f47b2c9810d93e8579517692268c821c6724946438a9744a2a95510d529f0e0195a2660abd057d3f6a59df3a1c9a116f76d53900e2a715dfe5525228e832c02fd07b8dac0d488cca269e0dbb74047cf7a5e64a06a443f7d580ee28c5d41d5ede3604825eba31985e96575df2bcc2fefd0c77f2033c04008be9746a0935338434c16d5a68d1338eabdcf0170ac19a27ec832bf0a353934570abd48b1fe31bc9a4bb99428d1fbab726b284aec27522efb9527ddce1106ba6a480c65f9332c5b2a3c727a2cca6d6951b09c7c28ed0474fdc6a945076524877680
primes = [2, 3, 5, 17, 257, 641, 65537, 274177, 2424833, 6700417, 67280421310721, 1238926361552897, 59649589127497217, 5704689200685129054721, 7455602825647884208337395736200454918783366342657, 93461639715357977769163558199606896584051237541638188580280321, 741640062627530801524787141901937474059940781097519023905821316144415759504705008092818711693940737]
assert product(primes) == 2^1025 - 2
print("Number of q_i =", len(primes))
qi_choices = []
for qi in primes:
if qi == 2:
# qi_choice = [2]
qi_choice = [mpz(int(2))]
else:
# qi_choice = [1, qi]
qi_choice = [mpz(int(1)), mpz(int(qi))]
qi_choices.append(qi_choice)
total = product(len(i) for i in qi_choices)
possible_pis = [mpz(2), mpz(2), mpz(2)] # just to be safe
for qi_subset in tqdm(iter_product(*qi_choices), total=total):
possible_pi = product(qi_subset) + 1
if possible_pi.is_prime():
possible_pis.append(possible_pi)
many_multiple_of_lambda_n = product(possible_pis)
print("Lambda bit length =", many_multiple_of_lambda_n.bit_length())
d = pow(e, -1, int(many_multiple_of_lambda_n))
ct = 0x339be515121dab503106cd190897382149e032a76a1ca0eec74f2c8c74560b00dffc0ad65ee4df4f47b2c9810d93e8579517692268c821c6724946438a9744a2a95510d529f0e0195a2660abd057d3f6a59df3a1c9a116f76d53900e2a715dfe5525228e832c02fd07b8dac0d488cca269e0dbb74047cf7a5e64a06a443f7d580ee28c5d41d5ede3604825eba31985e96575df2bcc2fefd0c77f2033c04008be9746a0935338434c16d5a68d1338eabdcf0170ac19a27ec832bf0a353934570abd48b1fe31bc9a4bb99428d1fbab726b284aec27522efb9527ddce1106ba6a480c65f9332c5b2a3c727a2cca6d6951b09c7c28ed0474fdc6a945076524877680
pln = pow(ct, d, n)
print(pln)
print(bytes.fromhex(hex(int(pln))[2:]))
Flag
CTF{Recycling_Is_Great}