Ok so we have a string (with hex chars) and a mapping table between ASCII chars and hex values.
So I made a script to reverse the mapping.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
File.open('breiz', 'r') do |f| mapping = Hash.new answer = ''
data = f.read() encoded_data = data.match(/^#([0-9a-f]*)$/).captures[0] data.scan(/8====D::\^(.{1})::#HotLikeBreizh::([0-9a-f]{2})/).each do |char, hex| mapping.store(hex, char) end encoded_data = encoded_data.scan(/.{1,2}/) encoded_data.each do |chunck| if mapping.include?(chunck) puts "#{chunck}#{mapping[chunck]}" answer += mapping[chunck] end end puts answer end
That give me cust0m_e4svc_4u70_h07_k3ys, but bzhctf{cust0m_e4svc_4u70_h07_k3ys} is not the flag :(
What's wrong? Maybe I should take ^a and not a for chars?
Let's change the regex /8====D::\^(.{1})::#HotLikeBreizh::([0-9a-f]{2})/ into /8====D::(.{2})::#HotLikeBreizh::([0-9a-f]{2})/
bzhctf{^c^u^s^t^0^m^_^e^4^s^v^c^_^4^u^7^0^_^h^0^7^_^k^3^y^s} is not the flag either.
And then I saw that 4d could be b or e, it seems there is multiple chars possible for a single hex value.
Let's modify the ruby script to show the possibilities:
File.open('breiz', 'r') do |f| mapping = Hash.new answer = ''
data = f.read() encoded_data = data.match(/^#([0-9a-f]*)$/).captures[0] data.scan(/8====D::\^(.{1})::#HotLikeBreizh::([0-9a-f]{2})/).each do |char, hex| if mapping.include?(hex) mapping.store(hex, "[#{mapping[hex]}|#{char}]") else mapping.store(hex, char) end end encoded_data = encoded_data.scan(/.{1,2}/) encoded_data.each do |chunck| if mapping.include?(chunck) puts "#{chunck}#{mapping[chunck]}" answer += mapping[chunck] end end puts answer end
The output of my script is now cust0m_[b|e]4s[i|v]c_4u70_h07_k3ys, that let us 4 possibilities:
We need to bruteforce the authentication. User is admin, (one of) shuffled password is bicpemo and there is a random token that seems associated to the password.
So we neeed to parse the result and submit the password and the token until we get the flag. Each request use the previous result (password and token).
$ cat README Nous avons réussi à intercepter une conversation entre Alice et Bob sur un cannal non sécurisé. Malheureusement, le message contenant les informations sensibles dont nous souhaitons récupérer a été chiffré par le biais du chiffrement asymétrique RSA.
C'est pour cela que nous engageons les meilleurs cryptanaliste qui seront récompensés par des points s'ils parviennent à nous retrouver partiellement ou l'intégralité des données dont nous recherchons !
Pour vous faciliter la tâche nous vous avons extrait chacun de ces messages et les avons classés par ordre chronologique. (message1, puis message2 ...). Nous avons également interceptés deux clés publique en provenance d'Alice. (d'abord pubkey, ensuite pubkey2). Esperons que cela suffise pour que vous puissiez nous aider !
$ cat message1 | base64 -d De : Alice A : Bob Bonjour Bob, peux tu m'envoyer le flag du chall Crypto ? je ne le retrouve plus !
$ cat message2 | base64 -d De : Bob A : Alice Biensur, envois moi ta clé publique pour que je puisse te l'envoyer de façon sécurisée
$ cat message3 | base64 -d De : Bob A : Alice Attention je pense que ta clé publique est vulnérable à Wiener, je te conseille fortement de la changer ! bzhctf{B3g1N_0f_Fl4g
$ cat message4 | base64 -d De : Alice A : Bob Voilà, j'ai ajouté 15 bits de poids fort à ma nouvelle clé privée, maintenant je ne suis plus vulnérable à Wiener ;) Tu peux m'envoyer le flag sans soucis ;)
from sympy.solvers import solve from sympy import Symbol
defpartial_quotiens(x, y): pq = [] while x != 1: pq.append(x / y) a = y b = x % y x = a y = b #print pq return pq
defrational(pq): i = len(pq) - 1 num = pq[i] denom = 1 while i > 0: i -= 1 a = (pq[i] * num) + denom b = num num = a denom = b #print (num, denom) return (num, denom)
defconvergents(pq): c = [] for i inrange(1, len(pq)): c.append(rational(pq[0:i])) #print c return c
defphiN(e, d, k): return ((e * d) - 1) / k
# e = 17993 # n = 90581 # wiener_attack(e, n) --> p = 239, q = 379
e = 0x7f46ebfb41c86b905b769810a7e817f61520de40c36362fc8e943767ca0b9bd054f29d44589edaa8aaaae505ed86d5aaee2258dc49f6aa894a3480b5af0c3ee0cce6bd4974ca746ca05e2216b69232d019c1c3a7bb44220b471ecb1874ca442574505ba2a64d15a0db11f439ff494915b9d1110af52705739f454a8fd587a8155cd8eabac3551a4e1d122370e5e3c509eb5a3c195308ed57201b1fe5076337a4f155fef88c82a1309523ab7325328169b690f120d8c3bdc864a95296806961a1d49b2f5c0bebca97629d5ffc85f2564045e771d7f1b47c01a2114e1ce845d498da0dadaee1cfee4ce6efb1130cca81931e412e39eec05b396619def75fbe818d n = 0x9BCEC30ED18FDAB08E559BE429DC408ACCA727A0BDB22EDDAE297E0FB41911F0A924BF4B111CEF135A7766325639ED7B1DE13A25938B86A5B02E5B382D258D42BBC6EB5078ED4A5A84F77E35DE1F51D443E87870447770589F9E5D6F99846BBBD18A434D2954F4F36250C24BCAFAC21F63A183DDDE7DF3D9A8A715F790E965E0F25EC0052DC16F3164A4754B686F882A48F4400F6E5D9969344B3A62639DC00C2693288584248EC75BC7CA78EE80CB715C9BFC1A6BCF3DD876FEA62387D17B3CB299FCD85D36B476D0CE386CA9696AE6F8CFBA2E9D1080775BCA26F96C7BE917B6DD55CF94FA2BA806FD7EB8F8F64025DE135CE9118A75735740128CFA0C8181
pq = partial_quotiens(e, n) c = convergents(pq) x = Symbol('x') for (k, d) in c: if k != 0: y = n - phiN(e, d, k) + 1 roots = solve(x**2 - y*x + n, x) iflen(roots) == 2: p = roots[0] q = roots[1] if p * q == n: print'p = ', p print'q = ', q break
1 2 3
$ python2 wiener.py p = 114127149061357518627202132148209789945562612498171703248844728647183939205938400942088872182451798474402023118266246164952671542551602493983267902191445132286997707695929380412166491987698597139874971335692611445465113906908277696311843072283279564769241732213534852153586415575904428530982417501447741168433 q = 172341949716171339980378913772457904178742410614994375111157032750032422968724167844252874762188062144611147923283489705813391034056983943831521141317610640390137786177422229331666759756497246847667967198831406618086722957960048848045394212884717806630358540400300795625429172362504491641913435853590659323729
Now we have p and q let's use RSAtool to generate a PEM file: