[GCTF 2022] Cycling

Points: 201 (50 solves)

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. 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.

Exploring the challenge

Let’s have a brief look at the source code we’re provided with:

e = 65537
n = ... # snip
ct = ... # snip
# 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())

In short, we’re faced with an RSA encryption of the flag, and one additional “fact” that’s supposed to help us in some way. The fact is that when we repeat the encrypting exponentiation R=210253R = 2^{1025} - 3 times, we achieve the same as decrypting the ciphertext. Working through the math, this tells us that xeRxx^{e^{R}} \equiv x holds, at the very least when xx represents the flag.

A well-known fact when dealing with RSA, and modular exponentiation in general, is that the order of the multiplicative group mod nn is equal to the number of integers <n< n that are coprime to nn. This quantity is known as Euler’s totient φ(n)\varphi(n).

Furthermore, from Euler’s theorem (or Lagrange’s theorem if we frame it in a group-theoretic way), we know that any number xx taken to the φ(n)\varphi(n)th power (mod nn), results in the identity 11. This property is in fact vital for the correctness of RSA, as we rely on the fact that xφ(n)1(modn)x^{\varphi(n)} \equiv 1 \pmod n when we say that xed(xφ(n))kxxx^{ed} \equiv \left(x^{\varphi(n)}\right)^k x \equiv x.

From all this known theory underlying the RSA cryptosystem, we can now finally make a first deduction: eR+11(modφ(n))e^{R + 1} \equiv 1 \pmod{\varphi(n)}.

Background: Carmichael’s λ\lambda

Actually, that previous statement is what you would say with a basic understanding of the principles underlying RSA, but it’s in fact not entirely correct. It could very well be the case that x1(modn)x^\ell \equiv 1 \pmod n for <φ(n)\ell < \varphi(n). Moreover, this will for the case for every xx when n=pqn = pq is an RSA modulus. One thing that Lagrange’s theorem will still give us, even when φ(n)\ell \ne \varphi(n), is that φ(n)\ell \mid \varphi(n).1

The smallest exponent such that x1(modn)x^\ell \equiv 1 \pmod n for all xx is known as the Carmichael function λ(n)\lambda(n). We know that λ(n)φ(n)\lambda(n) \mid \varphi(n), but we can even write down a nicer formula:2

λ(p1r1p2r2pmrm)=lcm(p1r11(p11),,pmrm1(pm1)) \lambda(p_1^{r_1}p_2^{r_2}\ldots p_m^{r_m}) = \mathrm{lcm}(p_1^{r_1 - 1}(p_1 - 1), \ldots, p_m^{r_m - 1}(p_m - 1))

which, when we apply this to our RSA modulus nn, becomes

λ(pq)=lcm(p1,q1) \lambda(pq) = \mathrm{lcm}(p - 1, q - 1)

Returning to our wrong statement from before, we now know that eR+11(mod)e^{R + 1} \equiv 1 \pmod \ell where λ(n)\ell \mid \lambda(n), and furthermore, since ee doesn’t look too suspicious, nor can a readable flag be influenced all that much, we can in fact hope that eR+11(modλ(n))e^{R + 1} \equiv 1 \pmod{\lambda(n)}.

Factors of factors of factors; and some subtractions

Now that we understand the nuances of the formula x1x^\ell \equiv 1 a bit better, we can think further towards solving this challenge. Remember what we wrote down earlier?

eR+11(modλ(n)) e^{R + 1} \equiv 1 \pmod{\lambda(n)}

This tells us something more, since we have exactly the form of statement that lead us to introducing λ(n)\lambda(n) in the first place. We could now say that R+1λ(λ(n))R + 1 \mid \lambda(\lambda(n)), which gives us a somewhat nice relation between the value RR we’d been given, and our RSA modulus nn.

Let’s not worry about the possibility that R+1R + 1 is only a divisor, and instead assume that it holds with equality R+1=λ(λ(n))R + 1 = \lambda(\lambda(n)). Then we can try to write down what we expect R+1R + 1 to be:3

R+1=λ(λ(n))=λ(lcm(p1,q1))=λ(2s1s2sm)=lcm(s11,,sm1)\begin{aligned} R + 1 = \lambda(\lambda(n)) &= \lambda(\mathrm{lcm}(p - 1, q - 1)) \\ &= \lambda(2s_1s_2\ldots s_m) \\ &= \mathrm{lcm}(s_1 - 1, \ldots, s_m - 1) \end{aligned}

We now would like to relate these values si1s_i - 1 to RR somehow. By the above, it should be clear that any si1R+1s_i - 1 \mid R + 1, so when we list all divisors of R+1R + 1 in turn, and add 11 to them, we should end up with a set of candidates 𝒞\mathcal{C}, such that {si}i𝒞\{s_i\}_i \subseteq \mathcal{C}. The value R+1R + 1 itself is not particularly easy to factor in a short amount of time, but luckily it’s not an esoteric, unknown value, but a nicely structured one. And as it often happens to nicely structured values, they show up on factordb.

Who cares if it’s not the private key? It works

With the set 𝒞\mathcal{C}, what could we do? One option to consider is applying the same trick again, but using 𝒞\mathcal{C} rather than the factorization of R+1R + 1, to recover pp and qq. Annoyingly, 𝒞\mathcal{C} is a rather large set, and enumerating all subsets of it takes exponential time, so we’ll have to throw that idea out.

Instead, let’s look back at our initial, more naive, understanding of the RSA cryptosystem, where we used φ(n)\varphi(n) rather than λ(n)\lambda(n) to compute the decryption exponent d=e1(modφ(n))d = e^{-1} \pmod{\varphi(n)}. Even though we didn’t have the smallest modulus possible, we still had full correctness, since — as we know by now — λ(n)φ(n)\lambda(n) \mid \varphi(n). We can take that to the extreme: we know/assume that all factors of λ(n)\lambda(n) are among our values sis_i, so if we simply take Ξ=isi\Xi = \prod_i s_i, it should hold that λ(n)Ξ\lambda(n) \mid \Xi, and as such, we could use Ξ\Xi as a “replacement” for λ(n)\lambda(n) or φ(n)\varphi(n) when it comes to computing a decryption exponent.

With this, we have enough ideas and information to finally solve this challenge4.


All your factorbase are belong to us

The official intended solution relies on similar observations, but instead of finding some number kλ(n)k\lambda(n), it uses those potential factors of λ(n)\lambda(n) to directly factor the modulus nn.5 To understand how this factorization works, we look back at a well-known, simple special-purpose factoring algorithm: Pollard’s p - 1 algorithm.

Pollard’s algorithm allows finding a factor pp (say for n=pqn = pq) under the assumption that p1p - 1 is BB-powersmooth. That is, all prime power divisors srp1s^r \mid p - 1 are bounded by sr<Bs^r < B. This property enables us to find some product MM of prime powers less than BB, such that p1Mp - 1 \mid M but q1Mq - 1 \nmid M. In turn, looking at Fermat’s little theorem, we can see that for all aa, it holds that aM1(modp)a^M \equiv 1 \pmod p, but it will often be the case that aM1(modq)a^M \not\equiv 1 \pmod q, and so looking for gcd(aM1,n)\gcd(a^M - 1, n) should allow us to recover pp. Traditionally, Pollard’s method computes aM(modn)a^M \pmod n by repeatedly taking ssth powers of an accumulator and testing whether the gcd\gcd results in a factorization. The advantage of this is twofold: one doesn’t need to fully compute MM in its entirety6 and as long as the largest factor of p1p - 1 differs from the largest factor of q1q - 1,7 the method will still work, rather than yielding nn as the gcd\gcd.

To abstract the bound BB away, we simply notice that all it gives us is some superset 𝒞\mathcal{C} of prime (power) factors of p1p - 1. This is exactly what we already found by enumerating primes sis_i such that si1R+1s_i - 1 \mid R + 1! If we call such a set 𝒞\mathcal{C} a factor base, and slightly generalize Pollard’s algorithm, we can apply it to our situation as well. And this is exactly the approach we see in the official solution script: we take some base aa (there called mm), repeatedly exponentiate it by potential prime factors, and check if gcd(a1,n){1,n}\gcd(a' - 1, n) \notin \{1, n\}.

Once a factorization of nn is found, it is of course only a matter of performing regular RSA decryption to obtain the flag.

Does this always work?

Until now, we’ve made several assumptions that turned out to be correct, in order to solve this challenge. Even the official solution turns out to rely on those assumptions,8 so we’d like to have a look at how much trouble we’d be in when the assumptions would be invalidated. To restate our assumptions more explicitly:

  1. R+1=λ(λ(n))R + 1 = \lambda(\lambda(n))
    • The inner λ\lambda corresponds to the multiplicative order of the flag, |m|(modn)|m| \pmod n
    • The outer λ\lambda corresponds to the multiplicative order of ee, modulo |m||m|
  2. p1p - 1 and q1q - 1 are square-free, that is, none of their prime factors occur with multiplicity >1> 1.
  3. All si1s_i - 1 are square-free, where siλ(n)s_i \mid \lambda(n), but this has been confirmed by the factorization of R+1R + 1

And let’s also introduce some counterexamples for all of these, where our assumption is invalidated, and our solution becomes broken:

  1. We explore the possibility for both λ\lambdas:
    • Let n=77n = 77, then λ(n)=lcm(6,10)=30\lambda(n) = \mathrm{lcm}(6, 10) = 30, but for the message m=15m = 15, it’s already true that m51(modn)m^5 \equiv 1 \pmod n, rather than the expected m30m^{30}. This in turn implies that we only need eR+11(mod5)e^{R + 1} \equiv 1 \pmod 5 to complete decrypt this message by cycling.
    • We now use n=989=23×43n = 989 = 23\times43, so λ(n)=2×3×7×11=462\lambda(n) = 2\times3\times7\times11 = 462 and λ(λ(n))=lcm(2,6,10)=30\lambda(\lambda(n)) = \mathrm{lcm}(2, 6, 10) = 30, but for instance e=379e = 379 only has multiplicative order 55 modulo λ(n)\lambda(n).
  2. Consider n=163×67=10921n = 163\times67 = 10921, then λ(n)=lcm(2×34,2×3×11)=2×34×11=1782\lambda(n) = \mathrm{lcm}(2\times3^4, 2\times3\times11) = 2\times3^4\times11 = 1782. λ(λ(n))\lambda(\lambda(n)) would then be 2×33×52\times3^3\times5, and we’d never pick up 343^4 as a potential factor out of any subset.
  3. Similar issues to the earlier point occur, except they are introduced slightly later in the process of computing λ(λ(n))\lambda(\lambda(n)).

Other than those assumptions, there’s some more things that can go wrong. We’ve relied on enumerating all subsets of factors of R+1R + 1, but — as we remarked with an initial failed idea of repeating such an enumeration on the result of that — that takes exponential time in the number of factors. If we end up with a large amount of these factors, we might in fact already get in trouble trying to enumerate all subsets, and spend a long time waiting for that.9 On the other side of that medallion, to obtain that initial list of factors, we need to be able to factor this value R+1R + 1. Now, if we consider for instance the worst case, where pp and qq are what we could call doubly-safe primes, i.e. p=2(2p+1)+1p = 2(2p' + 1) + 1, pp and p12\frac{p - 1}{2} are both safe primes, there’s only a minor difference in number of bits between nn and λ(λ(n))\lambda(\lambda(n)) and the latter is even a new RSA modulus. By assumed security of RSA (unless you get extra information like in this challenge), factoring that would not be feasible.

Can we fix it?

Yes we can!

Sort of, at least. Unless my very vague notion from the footnote in the previous section pans out, I don’t expect we could get around the exponential time enumeration, or the factoring problems. We can however try to fix up some of the problems our assumptions brought along, and get a slightly more generic solution.

Let’s first look at the case where |m|<λ(n)|m| < \lambda(n). Since for our original approach, we only care about mm itself, and not about factoring, we only need to find a multiple of |m||m|, which we still get from our powerset enumeration (under the assumption, for now, that we get λ(|m|)\lambda(|m|)). This means we can still compute an effective decryption exponent that works for mm itself, and any element with an order dividing |m||m|. Moreover, we can still use this to fully factor nn too. Once we decrypt mm, we know that mk|m|1(modn)m^{k|m|} \equiv 1 \pmod n, which means we can again apply our p - 1 approach with a factor base to find an exponent MM such that mM1(modp)m^M \equiv 1 \pmod p. Note that we require the use of mm as basis here, rather than an arbitrary number aa. The only condition under which this will still necessarily fail is when |m||m| divides gcd(p1,q1)\gcd(p - 1, q - 1), since then any exponent such that mM1(modp)m^M \equiv 1 \pmod p also satisfies mM1(modq)m^M \equiv 1 \pmod q.10

Next, we investigate the case where R+1λ(|m|)R + 1 \ne \lambda(|m|). Unfortunately, the solution here isn’t quite as clean. When the order of ee is too small, we simply lack the information to recover enough primes. When the order of ee is only slightly too small, we should be able to salvage it with only a constant cost to our computation time. Pick a fixed-size (multi)set of small primes 𝒫\mathcal{P}, and let 𝒞=𝒞𝒫\mathcal{C}' = \mathcal{C} \cup \mathcal{P}. This increases the computation time with a factor 2|𝒫|2^{|\mathcal{P}|}, but as long as the “lost” factor of λ(|m|)\lambda(|m|) is factorable over 𝒫\mathcal{P}, our algorithm works again. Optionally, if we would like to deal with more complex situations, we could also construct more complex ways to add extra factors. For example, an approach comparable to the “two-stage” variant of the p - 1 algorithm is possible, where we take e.g. at most 4 “small” primes and 1 “medium” sized extra prime.

Finally, how can we deal with the annoyance of prime powers? To deal with prime power divisors of λ(n)\lambda(n), it’s possible to apply a strategy similar to the p - 1 factoring algorithm, where every prime factor is simply included multiple times. Since exponents larger than 22 can be detected in the factorization of R+1R + 1, we recommend including each factor twice, unless evidence to the contrary is present from the factorization of R+1R + 1.11 The more conservative approach would be to include each prime ss a number of times proportional to log(n)log(s)\frac{\log(n)}{\log(s)}, which comes at an obvious computational cost. For the prime power divisors of λ(λ(n))\lambda(\lambda(n)), we’ll need to do just a bit more work. If we see a prime power srs^r when factoring R+1R + 1, it should be clear from how λ\lambda works that we expect to also see the factors of s1s - 1 appear. In that case, it’s obvious that sr+1s^{r + 1} should be in 𝒞\mathcal{C}. When however s2sis^2 \mid s_i, we only see ss and the factors of s1s - 1 appear when factoring R+1R + 1. Hence, when we add a prime to 𝒞\mathcal{C} that still divides R+1R + 1, we should add it with a higher multiplicity.

Talk is cheap, show me the code

We present here the code as we implemented it during the CTF. That is, making maximal assumptions such that it still gets the flag. The code for factorization based on Pollard’s p - 1 algorithm can be found in the official solution. Interested readers are encouraged to understand, implement and share the suggested improvements of this article :)

proof.all(False) # speed up primality checking a bit
import itertools
from Crypto.Util.number import long_to_bytes

# From the itertools documentation/example
def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return itertools.chain.from_iterable(itertools.combinations(s, r) for r in range(len(s)+1))

# From factordb
factors = [2, 3, 5, 17, 257, 641, 65537, 274177, 2424833, 6700417, 67280421310721, 1238926361552897, 59649589127497217, 5704689200685129054721, 7455602825647884208337395736200454918783366342657, (2^256+1)//1238926361552897, (2^512+1)//18078591766524236008555392315198157702078226558764001281]
assert 2**1025-2 == prod(factors)

C = []
for ps in powerset(factors):
    v = prod(ps) + 1
    if is_prime(v):
        C.append(prod(ps) + 1)
Ξ = prod(C)

e = 65537
n = 0x99efa9177387907eb3f74dc09a4d7a93abf6ceb7ee102c689ecd0998975cede29f3ca951feb5adfb9282879cc666e22dcafc07d7f89d762b9ad5532042c79060cdb022703d790421a7f6a76a50cceb635ad1b5d78510adf8c6ff9645a1b179e965358e10fe3dd5f82744773360270b6fa62d972d196a810e152f1285e0b8b26f5d54991d0539a13e655d752bd71963f822affc7a03e946cea2c4ef65bf94706f20b79d672e64e8faac45172c4130bfeca9bef71ed8c0c9e2aa0a1d6d47239960f90ef25b337255bac9c452cb019a44115b0437726a9adef10a028f1e1263c97c14a1d7cd58a8994832e764ffbfcc05ec8ed3269bb0569278eea0550548b552b1
ct = 0x339be515121dab503106cd190897382149e032a76a1ca0eec74f2c8c74560b00dffc0ad65ee4df4f47b2c9810d93e8579517692268c821c6724946438a9744a2a95510d529f0e0195a2660abd057d3f6a59df3a1c9a116f76d53900e2a715dfe5525228e832c02fd07b8dac0d488cca269e0dbb74047cf7a5e64a06a443f7d580ee28c5d41d5ede3604825eba31985e96575df2bcc2fefd0c77f2033c04008be9746a0935338434c16d5a68d1338eabdcf0170ac19a27ec832bf0a353934570abd48b1fe31bc9a4bb99428d1fbab726b284aec27522efb9527ddce1106ba6a480c65f9332c5b2a3c727a2cca6d6951b09c7c28ed0474fdc6a945076524877680

d = pow(e, -1, Ξ)
print(long_to_bytes(int(pow(ct, d, n))))