TU CTF – Secure Auth

This was a 150 point challenge with the description:

We have set up this fancy automatic signing server!
We also uses RSA authentication, so it’s super secure!

nc 104.196.116.248 54321

Connecting to the service, we get the following

screenshot 2016-05-14 01.39.35

Obviously, we cannot feed the message get_your_hands_off_my_RSA! to the oracle. So, we will only receive signatures, but no way to verify them; this means we don’t know either the public modulus, nor the public exponent. But, of course, we could guess the public exponent… there are a few standard ones: $3, 17, 65537...$

First, I obtained the signatures for $3$ and $4$ from the provided service. Denote these $s_3, s_4$ , respectively. We note that given a correct public exponent $e$ , we may compute $s_3^e = 3 + k \cdot N$ and $s_4^e = 4 + l \cdot N$ . Inevitably, $\textnormal{gcd}(s_3^e-3,s_4^e-4) = \textnormal{gcd}(k,l)\cdot N$ . Hoping for $\textnormal{gcd}(k,l)$ to be small, we can use serveral pairs until we find one that works.

Trying all the listed (guessed) public exponents, we find that $e = 65537$ (this was performed surprisingly fast in Sage with my Intel hexacore). Hence, we have now determined the modulus

$\begin{array}{rl} N = & 24690625680063774371747714092931245796723840632401231916590850908498671935961736 \\ &33219586206053668802164006738610883420227518982289859959446363584099676102569045 \\ &62633701460161141560106197695689059405723178428951147009495321340395974754631827 \\ &95837468991755433866386124620786221838783092089725622611582198259472856998222335 \\ &23640841676931602657793593386155635808207524548748082853989358074360679350816769 \\ &05321318936256004057148201070503597448648411260389296384266138763684110173009876\\ &82339192115588614533886473808385041303878518137898225847735216970008990188644891 \\ &634667174415391598670430735870182014445537116749235017327.\end{array}$

Now, note that

libnum.strings.s2n('get_your_hands_off_my_RSA!') % 3 == 0

OK, so we may split this message $m$ into a product of two message factors: $m_1 = 3$ and $m_2 = 166151459290300546021127823915547539196280244544484032717734177$ and sign them. Then, we compute the final signature $s = m^d = (m_1 \cdot m_2)^d = m_1^d \cdot m_2^d = s_1 \cdot s_2 \bmod N$ . Mhm, so what now?