0x00 Happy!

We are given an archive of challenge files: a Ruby script implementing RSA, a marshalled public key and an encrypted flag. The task, of course, is to decrypt the flag.

Auditing the script reveals that besides the usual parameters \(\{p,q,e,N\}\), it stores a bunch of derived values \(\{d_1, d_2, c_f\}\) in the Key object. These are later used during decryption. There is also something strange going on – keygen takes an extra argument \(k\), which is the power to which \(q\) will be raised in the public modulus:

def self.generate_key(bits, k)
  while true
    p = OpenSSL::BN::generate_prime(bits, true).to_i
    q = OpenSSL::BN::generate_prime(bits, true).to_i
    e = 65537
    next if e.gcd((p - 1) * (q - 1) * q ** (k - 1)) > 1
    d1 = e.pow((p - 1) / 2 - 2, (p - 1))
    fail unless d1 * e % (p - 1) == 1
    d2 = e.pow(((q - 1) / 2 - 1) * (q - 1) * (k > 1 ? q ** (k - 2) : 1) - 1, q ** (k - 1) * (q - 1))
    fail unless d2 * e % (q ** (k - 1) * (q - 1)) == 1
    cf = p.pow(q ** (k - 1) * (q - 1) - 1, q ** k)
    return Key.new({
      n: p * q ** k,
      e: e,
      p: p,
      q: q ** k,
      d1: d1,
      d2: d2,
      cf: cf,
    })
    break
  end
end

Generally speaking, this is a bad idea. While factoring a product of two primes of roughly the same size (e.g. 512 bits) is infeasible, Boneh et al. show that factoring a number of the form \(pq^k\) becomes significantly easier as \(k\) increases. But let’s keep looking, maybe there are more issues.

While the padding scheme used looks legit¹, there is a typo in the sanitization from private to public key:

def public_key
  Key.new(@attr.reject{|k, v| [:p, :q, :d1, :d2, :ce].include?(k)})
end

The primes and some of the derived values are stripped, but \(c_f\) sneaks through. Loading the public key file confirms this and we have three values to work with:

N = 5452318773620154613572502669913080727339917760196646730652258556145398937256752632887555812737783373177353194432136071770417979324393263857781686277601413222025718171529583036919918011865659343346014570936822522629937049429335236497295742667600448744568785484756006127827416640477334307947919462834229613581880109765730148235236895292544500644206990455843770003104212381715712438639535055758354549980537386992998458659247267900481624843632733660905364361623292713318244751154245275273626636275353542053068704371642619745495065026372136566314951936609049754720223393857083115230045986813313700617859091898623345607326632849260775745046701800076472162843326078037832455202509171395600120638911
e = 65537
cf = 25895436290109491245101531425889639027975222438101136560069483392652360882638128551753089068088836092997653443539010850513513345731351755050869585867372758989503310550889044437562615852831901962404615732967948739458458871809980240507942550191679140865230350818204637158480970417486015745968144497190368319745738055768539323638032585508830680271618024843807412695197298088154193030964621282487334463994562290990124211491040392961841681386221639304429670174693151

At this point in the CTF, we noted that the size of \(N\) is \(\log_2{N}\approx 2295=765*3\). Knowing that \(N=pq^k\) and that both primes are roughly the same size (but at least 700 bits), we can conclude that \(k=2\). This is sadly too small to enable direct factorization (ch. 6 in Boneh et al.), but maybe we can somehow use the information from \(c_f\). The expression by which it is given can be simplified using Euler’s theorem:

\[ \begin{aligned} c_f & \equiv p^{q^{k-1}(q-1)-1} \equiv p^{\varphi(q^k)-1} \equiv p^{-1}\ (mod\ q^k) \\ & \equiv p^{-1}\ (mod\ q^2) \end{aligned} \]

What we have, then, is simply the inverse of one factor of \(N\) modulo the other two. This reveals the meaning behind the challenge description: “No, we’Re not SAd. We are Happy!”. It’s a reference to “R U Sad”, a challenge from this year’s Plaid CTF. In that one, we were given both inverses and could solve it by calculational reasoning with Bézout’s identity. Here, the situation is not so clear, which is reason enough to be sad.

0x01 Lenstra, Lenstra, Lovász

As a wise man once said, “If it’s not LLL, it’s LLL”. LLL is a lattice basis reduction algorithm which, given a basis for an integer lattice, is able to find a small basis for the same lattice with a precise bound on the coefficients. The details of how it works are not terribly important as we can just use an existing implementation.

As originally realised by Coppersmith and then refined by Howgrave-Graham, this algorithm is extremely useful for cryptanalysis. A. May’s survey provides a comprehensive overview of the area and was indispensable in solving this challenge. It contains a proof of the following:

Theorem 1. Let \(N\) be an integer of unknown factorization, which has a divisor \(b \geq N^\beta\), \(0 \lt \beta \leq 1\). Let \(f(x)\) be a univariate monic polynomial of degree \(\delta\). Then we can find all solutions \(x_0\) for the equation \(f(x) \equiv 0\ (mod\ b)\) with \(\lvert x_0 \rvert \leq cN^\frac{\beta^2}{\delta}\) in time \(\mathcal{O}(c\delta^5\log^9N)\).

In other words, we can find some roots of a polynomial modulo \(b\) in sorta-logarithmic time as long as they are small enough – asymptotically below \(N^{\frac{\beta^2}{\delta}}\). The survey also lays out Coppersmith’s algorithm which finds such solutions² (see “Coppersmith’s method in the univariate case”).

While the algorithm itself has strikingly low time complexity, I found one thing in its statement even more surprising – the fact that at no point do we need to know the value of \(b\) to find the roots of \(f(x)\) modulo \(b\). It suffices to know that \(b\) factors \(N\) and that it’s at least \(N^\beta\). To me, this reads like black magic. It also happens to be the case in our task, so let’s use it.

The crucial condition Coppersmith’s method needs to work are small-enough roots. We have the polynomial \(f(x)=c_fx-1\), with \(f(p) \equiv 0\ (mod\ q^2)\) and degree \(\delta = 1\). To compute the smallness requirement, note that \(b = q^2 \approx N^\frac{2}{3}\), so that \(\beta = \frac{2}{3}\). Hence, we need \(\lvert p \rvert \leq cN^\frac{4}{9}\), which is true, but not by much – \(p \approx N^\frac{1}{3}\).

At this point it becomes clear why the modulus is so weird – this wouldn’t be possible to solve if \(N\) were simply \(pq\), because then \(\beta=\frac{1}{2}\) and \(p\) would be too large. Unless there is a completely different solution – I’d be interested in hearing about that!

One small issue remains - our polynomial is not monic. This can be solved by multiplying it by the inverse of \(c_f\) modulo \(N\) (remember, no need to know \(b\)) in the polynomial ring over integers modulo \(N\).

Knowing all this, decrypting the flag amounts to typing the parameters into an off-the-shelf implementation of Coppersmith’s algorithm.

TWCTF{I_m_not_sad__I_m_happy_always}

Thanks goes to my teammates hyperreality and Retr0id for helping out, as well as to the organizers for prompting me to finally learn LLL-based attacks.