Huh, there were no write-ups from RDot for a long time. It's quite useful to write the solution of tasks, 'cause it makes you to systematize and remember the techniques.
We didn't participate in this RuCTF in normal way and solved only several tasks and all web tasks (mostly by BlackFan).
But i've learned a bit and would like to write it.
Two agents, Alex and Jane, have simultaneously known very secret message and transmitted it to Center. You know following:
1) They used RSA with this public key
2) They sent exactly the same messages except the signatures (name appended, eg. "[message]Alex")
3) They did encryption this way:
c, = pubKey.encrypt(str_to_num(message), 1) # using RSA from Crypto.PublicKey
c = num_to_str(c).encode('hex')
4) And here are cryptograms you have intercepted:
Now google for "rsa cryptograms attack" and see several articles on new related message attacks on RSA. See a Wikipedia article with the description of Franklin-Reiter theorem: http://en.wikipedia.org/wiki/Coppersmith's_Attack#Franklin-Reiter_Related_Message_Attack
Now everything is clear: we've got 2 plaintexts, which are linear dependent (M_1 = f(M_2)), and we've got their ciphertexts.
Now, since exponentiation of the plaintext modulo N gives us the ciphertext, we've got two polynomials:
A = f(x)^e - C_1
B = x^e - C_2
M_2 is the root of both of these polynomials, thus, we can obtain its value by computing GCD(A, B) and transforming it to the form x - M_2 modulo N.
Ok, let's do it with SageMath. We'll use PolynomialRing over the quotient of Z over the ideal N*Z, which gives us exactly Z_N[x].
s = hex(n)[2:-1]
if len(s) % 2 != 0:
s = '0' + s
n = int('00a35fe41555b06b23cd769a2aad77cad3a3daa6a76de7591c8b8f281afa5125297fb10541387f8b998d2fd1a76120dd147281ac5208ea52d3ecad1e3e7cab5c0db247ddf87cd8adc3ad13bfb571e26d2e17ffa2429a80b7e9dbdf4054845fd2242ae071fe1a195d28900eda405da3e937ca29dff284e0528c3db510dea9c733bf', 16)
s1 = int('Alex'.encode('hex'), 16)
s2 = int('Jane'.encode('hex'), 16)
c1 = int('61be5676e0f8311dce5d991e841d180c95b9fc15576f2ada0bc619cfb991cddfc51c4dcc5ecd150d7176c835449b5ad085abec38898be02d2749485b68378a8742544ebb8d6dc45b58fb9bac4950426e3383fa31a933718447decc5545a7105dcdd381e82db6acb72f4e335e244242a8e0fbbb940edde3b9e1c329880803931c', 16)
c2 = int('9d3c9fad495938176c7c4546e9ec0d4277344ac118dc21ba4205a3451e1a7e36ad3f8c2a566b940275cb630c66d95b1f97614c3b55af8609495fc7b2d732fb58a0efdf0756dc917d5eeefc7ca5b4806158ab87f4f447139d1daf4845e18c8c7120392817314fec0f0c1f248eb31af153107bd9823797153e35cb7044b99f26b0', 16)
e = 0x3001
x = PolynomialRing(ZZ.quo(n*ZZ), 'x').gen()
a = f
b = g
i = 0
r = a % b
if r == 0:
print 'FOUND %s' % rp
c = rp.coeffs()
print 'FLAG %s' % n2s(int(-pow(c, -1, n) * c))
rp = r
a, b = b, r
i += 1
Let's get the flag!
$ sagemath crypto500.sage
FOUND 86347048644041959766090057410640305461678868162177979421087317554210234110369955526791775847361535519143092394149068764498277643348795961082156089836642351621424445435902804588119216433665103505792218858888305714770868178378804365816297013813657963875724856245424023118807158540880143607254801768717070147804*x + 40836521644702680933657456433228492950202348193489549527400191298584941329596522282892128987400285318068118281466151919632036439194000125584502933334684046351809219092582554420924491543953943827409526936466307711980634548206697972041905742975718906307805649969647422605338208203046892961449351897728557420002
FLAG The key is RUCTF_StandBackImGonnaDoMath. Jane
Hi! We have unconfirmed information about our agent and developer of our site. His tasks includes processing requests from civilians. We think that he is double agent and works for irRational Security Agency. Help us to find evidence about that.
Flag format is "RUCTF_.*".
We've got the site with the form for sending some anonymous requests. Send it and get the page like /msg?id=8e22c45c65438e5108bd4e349da3a25b. There you see your unapproved request, and in HTML source code you see the comment with your IP address and user-agent string!
Looks like an administrator should approve the requests, and he'll see this page. So, we've got an XSS.
But we've also got a problem:
09.03.2014 13:20 MSK. Hint for task web:400 (irRSA). It seems that agent and system developer have disabled all outbound connections from agent's computer to the Internet ;-).
At this moment i suggested BlackFan to use DNS tunnel with my server, and it suddenly worked o_O
Moreover, the HTTPOnly flag for cookie id was not set, so, we got admin's cookie.
Payload by BlackFan: