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

Screenshot 2016-05-15 12.13.41

Phew 🙂

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s