HITCON 2015 Quals: Poooooooow

Reading time ~1 minute

This challenge was solved by and the write up was written by one of my teammates, NGG.

p = 195589859419604305972182309315916027436941011486827038011731627454673222943892428912238183097741291556130905026403820602489277325267966860236965344971798765628107804393049178848883490619438682809554522593445569865108465536075671326806730534242861732627383004696136244305728794347161769919436748766859796527723

If we submitted x such that 0<x<p then the server replied with x^flag % p.

So if we could compute discrete logarithms over GF_p, then we would have been done.

However the best algorithms to compute discrete logarithm in a group requires more than O(sqrt(q)) time where q is the largest prime factor of the order of the base number, which would be too slow if we used a primitive root modulo p, because

p-1 = 2 * 3^336 * q
q = 4759647095086827597559114855685975263112106458932414012998147177848303887783492510354911068366203455488902018600593880874117783509946030773587965941

2 is a primitive root modulo p, so x = 2^q has order 2*3^336 which is long enough for the flag (which is 50 characters) and only has small prime factors, so we sent that number to the server.

We got that

x^flag % p = 76330748508434302948911811389582581821991628856573396875939665491436112259216518385549428479486803046688716209647162112374160557281493613562434598038831198998785672154884963029434409475216631801204644290518567711052531985788274092047888219286448792676928521370001329553409713430110222435245961441435742296538

The following Sage script gave the flag:

p = 195589859419604305972182309315916027436941011486827038011731627454673222943892428912238183097741291556130905026403820602489277325267966860236965344971798765628107804393049178848883490619438682809554522593445569865108465536075671326806730534242861732627383004696136244305728794347161769919436748766859796527723
x = 132585580939144436905911763231635617823178051459908250631824609219279037477801312198223424732856254163115776338354306272774475984396132199861419969731110371570526911820025198029198505641172369496514045117550502453451793346650024622608619967071106739007357005769870224699764282050497089845720561850966889205185
y = 76330748508434302948911811389582581821991628856573396875939665491436112259216518385549428479486803046688716209647162112374160557281493613562434598038831198998785672154884963029434409475216631801204644290518567711052531985788274092047888219286448792676928521370001329553409713430110222435245961441435742296538
f = discrete_log(Mod(y, p), Mod(x, p))
import binascii
print binascii.unhexlify('{0:x}'.format(f))

The flag was

hitcon{CBRT_cbrt_Cbrt_CbRt_cBrT_cBRT_RePeAt......}

GoogleCTF 2018 Quals: Web - BBS

Last weekend I played on the Google CTF 2018 Quals which was one of the best CTFs I played recently. They separated the easy challenges i...… Continue reading

0CTF 2017 Quals: Crypto challenges

Published on March 23, 2017

0CTF 2017 Quals: Choices (reverse, 297pts)

Published on March 23, 2017