HSCTF
Here’s a write up for the crypto challenges I was able to finish while paying hsctf. I’ve tried to be thorough with my writeup and include python implementation with a description of the solution. I hope that this is helpful.
| Challenge | Category |
|---|---|
| Super Secure System | OTP |
| Reverse Search Algorithm | RSA |
| Massive RSA | RSA |
| Really Secure Algorithm | RSA |
| Tux’s Kitchen | Reversing, XOR |
| Bomb | Enigma |
| Spooky ECC | ECC |
Crypto Challenges
Super Secure System
Keith made a SUPER SECURE SYSTEM!!! He claims it is so secure as long as he doesn’t reuse his key… nc crypto.hsctf.com 8111
When we connect to the server we’re greeted with the following:
* * * SUPER SECURE SYSTEM * * *
My encryption system is impossible to crack if used once!
You can use this system to encrypt any of your messages with my super special key!!!
Here is my super secret message: 1004684a4b05434356763f616d6955540d1d69341f4f35312d550c5b4d1e5448560547187323503915363e17593f5e463d08496545
Enter the message you want to encrypt:
The hint here is:
My encryption system is impossible to crack if used once!
My guess is that this is a OTP encryption, but the key is reused. Let’s double check by sending the same message twice
Enter the message you want to encrypt: you should never reuse your OTP key!!!!!
Encrypted: 4a410e413e0d5b3c184d1b12327f301679276f0b304f720c1310791d773a612b1537190a19775d68
Enter the message you want to encrypt: you should never reuse your OTP key!!!!!
Encrypted: 4a410e413e0d5b3c184d1b12327f301679276f0b304f720c1310791d773a612b1537190a19775d68
Looks like we were right. If we take the encrypted data, XOR it against our plain text we’ll have the OTP key which we can then just XOR against the supplied “super special key”.
Flag
hsctf{h0w_d3d_y3u_de3cryP4_th3_s1p3R_s3cuR3_m355a9e?}
Python Implementation
from pwn import *
context.log_level = 'critical'
s = remote("crypto.hsctf.com", 8111)
s.recvuntil("message: ")
c = s.recvline().strip().decode()
c = bytes.fromhex(c)
t = "a" * len(c)
s.recvuntil("encrypt: ")
s.sendline(t)
s.recvuntil("Encrypted: ")
ct = s.recvline().strip().decode()
ct = bytes.fromhex(ct)
flag = xor(t.encode(), xor(ct, c))
print(flag.decode())
s.close()
# >> hsctf{h0w_d3d_y3u_de3cryP4_th3_s1p3R_s3cuR3_m355a9e?}
Reverse Search Algorithm
Lets get started with some easy RSA.
Challenge Data
WWPHSN students, gotta get these points to boost your grade.
n = 561985565696052620466091856149686893774419565625295691069663316673425409620917583731032457879432617979438142137
e = 65537
c = 328055279212128616898203809983039708787490384650725890748576927208883055381430000756624369636820903704775835777
Nothing particularly stands out here, so I do my usual thing of stuffing n into factordb and hope for the best. We indeed find that n can be easily factorised:
p = 29
q = 19378812610208711050554891591368513578428260883630885898953907471497427917962675301070084754463193723428901453
Time to stick this into python and get the flag.
Flag
hsctf{y3s_rsa_1s_s0lved_10823704961253}
Python Implementation
from Crypto.Util.number import inverse
c = 328055279212128616898203809983039708787490384650725890748576927208883055381430000756624369636820903704775835777
n = 561985565696052620466091856149686893774419565625295691069663316673425409620917583731032457879432617979438142137
e = 65537
p = 29
q = 19378812610208711050554891591368513578428260883630885898953907471497427917962675301070084754463193723428901453
def get_RSA_flag(c,n,e,p,q):
phi = (p-1)*(q-1)
d = inverse(e,phi)
m = pow(c,d,n)
return bytes.fromhex(format(m,'x')).decode('utf-8')
print(get_RSA_flag(c,n,e,p,q))
# >> hsctf{y3s_rsa_1s_s0lved_10823704961253}
Massive RSA
Challenge Data
I was scared that my RSA would be broken, so I made sure that the numbers were massive.
c = 358031506752691557002311547479988375196982422041486602674622689505841503255891193495423484852537391230787811575487947331018616578066891850752360030033666964406349205662189685086812466246139857474435922486026421639388596443953295273675167564381889788905773472245885677132773617051291379731995063989611049809121305468803148551770792609803351375571069366930457307762595216806633327492195442616272627113423143562166655122764898972565860928147259322712805600875994388377208017608434714747741249858321487547543201109467214209112271771033615033493406609653861223917338109193262445432032609161395100024272041503554476490575517100959892951805088735483927048625195799936311280172779052715645263075391841840633949032397082918665057115947698884582406130793211266028238396814146117158924884049679536261009188784571232730683037831940224049822081316216826346444136538278601803972530054219050666898301540575647763640218206611889707353810593843233814867745903144987805142815936160730054575462147126944741419094810558325854901931279755547624294325463528887326262902481099025253153222985717157272371423956465138892784879439141174797253720403065191378958340033965895823856879711180993895832306970105743588207727415495184380531676665121800713201192348940665501790550763379781627493441276077597720109700408848080221149485596419299548121287851605588246207568970548444975309457244824469026820421430723018384050095117420646392648577894835705672984626936461419833136418809219064810002991383584690376016818146065548853387107821627387061145659169570667682815001659475702299150425968489723185023734605402721950322618778361500790860436305553373620345189103147000675410970964950319723908599010461359668359916257252524290941929329344189971893558606572573665758188839754783710992996790764297302297263058216442742649741478512564068171266181773137060969745593802381540073397960444915230200708170859754559500051431883110028690791716906470624666328560717322458030544811229295722551849062570074938188113143167107247887066194761639893865268761243061406701905009155852073538976526544132556878584303616835564050808296190660548444328286965504238451837563164333849009829715536534194161169283679744857703254399005457897171205489516009277290637116063165415762387507832317759826809621649619867791323227812339615334304473447955432417706078131565118376536807024099950882628684498106652639816295352225305807407640318163257501701063937626962730520365319344478183221104445194534512033852645130826246778909064441514943
n = 950687172821200540428729809153981241192606941085199889710006512529799315561656564788637203101376144614649190146776378362001933636271697777317137481911233025291081331157135314582760768668046936978951230131371278628451555794052066356238840168982528971519323334381994143826200392654688774136120844941887558297071490087973944885778003973836311019785751636542119444349041852180595146239058424861988708991060298944680661305392492285898022705075814390941667822309754536610263449507491311215196067928669134842614154655850281748314529232542980764185554607592605321212081871630106290126123668106453941684604069442637972979374182617204123679546880646955063471680804611387541602675808433185504968764805413712115090234016146947180827040328391684056285942239977920347896230959546196177226139807640271414022569186565510341302134143539867133746492544472279859740722443892721076576952182274117616122050429733446090321598356954337536610713395670667775788540830077914016236382546944507664840405622352934380411525395863579062612404875578114927946272686172750421522119335879522375883064090902859635110578120928185659759792150776022992518497479844711483878613494426215867980856381040745252296584054718251345106582780587533445417441424957999212662923937862802426711722066998062574441680275377501049078991123518677027512513302350533057609106549686502083785061647562269181863107725160293272971931807381453849850066056697913028167183570392948696346480930400320904644898839942228059188904225142187444604612121676565893284697317106343998167640380023972222033520190994951064491572372368101650142992876761420785551386138148283615194775971673577063363049929945959258097086463812469068598955485574579363616634109593903116561526921965491646400040600138481505369027344295330767163087489333402201631708610718911106905154471963379233672543874307197342217544783263700843246351822145605839955798639016346308363889766574606793652730311687899415585873892778899179927359964882217066947566799298173326850382334054179474389651499891117938361854701587568363867264590395711833275763832842002504433841816245069655064326325306033334336469743800464944131049874472540605264250854258280373869113420817955012823462838351481855289027030577957168468047751024562853260494808998446682723835213272609799649864902376137320638444968430858790173696935815430513690803796736064125183005539073920032869713201073105497655763097638587404309062750746064609677994654409535743453776560694719663801069746654445359756195253816544699551
e = 65537
New numbers, this time much much bigger than before. With n this large, we’re never going to be able to factorise it. The other reason we can’t factorise it is because it’s already prime!
To check this I used Alpertron.
As n is prime, the totient is simply n-1 and we can calculate d and hence the message m.
Flag
hsctf{forg0t_t0_mult1ply_prim3s}
Python Implementation
from Crypto.Util.number import inverse
c = 358031506752691557002311547479988375196982422041486602674622689505841503255891193495423484852537391230787811575487947331018616578066891850752360030033666964406349205662189685086812466246139857474435922486026421639388596443953295273675167564381889788905773472245885677132773617051291379731995063989611049809121305468803148551770792609803351375571069366930457307762595216806633327492195442616272627113423143562166655122764898972565860928147259322712805600875994388377208017608434714747741249858321487547543201109467214209112271771033615033493406609653861223917338109193262445432032609161395100024272041503554476490575517100959892951805088735483927048625195799936311280172779052715645263075391841840633949032397082918665057115947698884582406130793211266028238396814146117158924884049679536261009188784571232730683037831940224049822081316216826346444136538278601803972530054219050666898301540575647763640218206611889707353810593843233814867745903144987805142815936160730054575462147126944741419094810558325854901931279755547624294325463528887326262902481099025253153222985717157272371423956465138892784879439141174797253720403065191378958340033965895823856879711180993895832306970105743588207727415495184380531676665121800713201192348940665501790550763379781627493441276077597720109700408848080221149485596419299548121287851605588246207568970548444975309457244824469026820421430723018384050095117420646392648577894835705672984626936461419833136418809219064810002991383584690376016818146065548853387107821627387061145659169570667682815001659475702299150425968489723185023734605402721950322618778361500790860436305553373620345189103147000675410970964950319723908599010461359668359916257252524290941929329344189971893558606572573665758188839754783710992996790764297302297263058216442742649741478512564068171266181773137060969745593802381540073397960444915230200708170859754559500051431883110028690791716906470624666328560717322458030544811229295722551849062570074938188113143167107247887066194761639893865268761243061406701905009155852073538976526544132556878584303616835564050808296190660548444328286965504238451837563164333849009829715536534194161169283679744857703254399005457897171205489516009277290637116063165415762387507832317759826809621649619867791323227812339615334304473447955432417706078131565118376536807024099950882628684498106652639816295352225305807407640318163257501701063937626962730520365319344478183221104445194534512033852645130826246778909064441514943
n = 950687172821200540428729809153981241192606941085199889710006512529799315561656564788637203101376144614649190146776378362001933636271697777317137481911233025291081331157135314582760768668046936978951230131371278628451555794052066356238840168982528971519323334381994143826200392654688774136120844941887558297071490087973944885778003973836311019785751636542119444349041852180595146239058424861988708991060298944680661305392492285898022705075814390941667822309754536610263449507491311215196067928669134842614154655850281748314529232542980764185554607592605321212081871630106290126123668106453941684604069442637972979374182617204123679546880646955063471680804611387541602675808433185504968764805413712115090234016146947180827040328391684056285942239977920347896230959546196177226139807640271414022569186565510341302134143539867133746492544472279859740722443892721076576952182274117616122050429733446090321598356954337536610713395670667775788540830077914016236382546944507664840405622352934380411525395863579062612404875578114927946272686172750421522119335879522375883064090902859635110578120928185659759792150776022992518497479844711483878613494426215867980856381040745252296584054718251345106582780587533445417441424957999212662923937862802426711722066998062574441680275377501049078991123518677027512513302350533057609106549686502083785061647562269181863107725160293272971931807381453849850066056697913028167183570392948696346480930400320904644898839942228059188904225142187444604612121676565893284697317106343998167640380023972222033520190994951064491572372368101650142992876761420785551386138148283615194775971673577063363049929945959258097086463812469068598955485574579363616634109593903116561526921965491646400040600138481505369027344295330767163087489333402201631708610718911106905154471963379233672543874307197342217544783263700843246351822145605839955798639016346308363889766574606793652730311687899415585873892778899179927359964882217066947566799298173326850382334054179474389651499891117938361854701587568363867264590395711833275763832842002504433841816245069655064326325306033334336469743800464944131049874472540605264250854258280373869113420817955012823462838351481855289027030577957168468047751024562853260494808998446682723835213272609799649864902376137320638444968430858790173696935815430513690803796736064125183005539073920032869713201073105497655763097638587404309062750746064609677994654409535743453776560694719663801069746654445359756195253816544699551
e = 65537
def get_RSA_flag(c,n,e):
phi = (n-1)
d = inverse(e,phi)
m = pow(c,d,n)
return bytes.fromhex(format(m,'x')).decode('utf-8')
print(get_RSA_flag(c,n,e))
# >> hsctf{forg0t_t0_mult1ply_prim3s}
Really Secure Algorithm
Challenge Data
I heard about RSA, so I took a go at implementing it.
n = 263267198123727104271550205341958556303174876064032565857792727663848160746900434003334094378461840454433227578735680279553650400052510227283214433685655389241738968354222022240447121539162931116186488081274412377377863765060659624492965287622808692749117314129201849562443565726131685574812838404826685772784018356022327187718875291322282817197153362298286311745185044256353269081114504160345675620425507611498834298188117790948858958927324322729589237022927318641658527526339949064156992164883005731437748282518738478979873117409239854040895815331355928887403604759009882738848259473325879750260720986636810762489517585226347851473734040531823667025962249586099400648241100437388872231055432689235806576775408121773865595903729724074502829922897576209606754695074134609
e = 65537
c = 63730750663034420186054203696069279764587723426304400672168802689236894414173435574483861036285304923175308990970626739416195244195549995430401827434818046984872271300851807150225874311165602381589988405416304964847452307525883351225541615576599793984531868515708574409281711313769662949003103013799762173274319885217020434609677019589956037159254692138098542595148862209162217974360672409463898048108702225525424962923062427384889851578644031591358064552906800570492514371562100724091169894418230725012261656940082835040737854122792213175137748786146901908965502442703781479786905292956846018910885453170712237452652785768243138215686333746130607279614237568018186440315574405008206846139370637386144872550749882260458201528561992116159466686768832642982965722508678847
Another easy RSA. This one required you to go off an try to factorise n. It’s a bit of a weird one, because n is a 700 digit integer and for sensible primes you wouldn’t expect to find its factors. The challenge didn’t pick sensible factors though and what we find is n is a perfect square.
A lot of people in the hsctf discord complained about this puzzle, infering that there was something going wrong with the RSA implementation. I imagine this is because people were trying to decode c using $\phi(n) = (p-1)^2$. Seeing as this was a mistake a few people struggled with, I’ll quickly outline how the totient function for a perfect square is found.
For any integer k we find that the totient can be represented using its prime factors
For a perfect square $n = k^2$ we will have the same prime factorisation, except there will be twice as many of each. i.e we find that
\[\phi(n) = k^2 \left(1 - \frac{1}{p_1} \right) \left(1 - \frac{1}{p_2} \right) \ldots \left(1 - \frac{1}{p_k} \right)\]Or simply that $\phi(n) = k \phi(k)$. Lets stick this totient into python and grab the flag.
Flag
hsctf{square_number_time}
Python Implementation
from Crypto.Util.number import inverse
n = 263267198123727104271550205341958556303174876064032565857792727663848160746900434003334094378461840454433227578735680279553650400052510227283214433685655389241738968354222022240447121539162931116186488081274412377377863765060659624492965287622808692749117314129201849562443565726131685574812838404826685772784018356022327187718875291322282817197153362298286311745185044256353269081114504160345675620425507611498834298188117790948858958927324322729589237022927318641658527526339949064156992164883005731437748282518738478979873117409239854040895815331355928887403604759009882738848259473325879750260720986636810762489517585226347851473734040531823667025962249586099400648241100437388872231055432689235806576775408121773865595903729724074502829922897576209606754695074134609
e = 65537
c = 63730750663034420186054203696069279764587723426304400672168802689236894414173435574483861036285304923175308990970626739416195244195549995430401827434818046984872271300851807150225874311165602381589988405416304964847452307525883351225541615576599793984531868515708574409281711313769662949003103013799762173274319885217020434609677019589956037159254692138098542595148862209162217974360672409463898048108702225525424962923062427384889851578644031591358064552906800570492514371562100724091169894418230725012261656940082835040737854122792213175137748786146901908965502442703781479786905292956846018910885453170712237452652785768243138215686333746130607279614237568018186440315574405008206846139370637386144872550749882260458201528561992116159466686768832642982965722508678847
p = 16225510719965861964299051658340559066224635411075742500953901749924501886090804067406052688894869028683583501052917637552385089084807531319036985272636554557876754514524927502408114799014949174520357440885167280739363628642463479075654764698947461583766215118582826142179234382923872619079721726020446020581078274482268162477580369246821166693123724514271177264591824616458410293414647
def get_RSA_flag(c,n,e,p):
phi = p*(p-1)
d = inverse(e,phi)
m = pow(c,d,n)
return bytes.fromhex(format(m,'x')).decode('utf-8')
print(get_RSA_flag(c,n,e))
# >> hsctf{square_number_time}
Tux’s Kitchen
This challenge was 10% crypto and 90% reversing. I was stuck for ages on the challenge, banging my heada against the wall untill I spotted the “typo” that was stopping my code from working.
Challenge Data
I need to bake it! nc crypto.hsctf.com 8112
import random
good_image = """
TUX's KITCHEN
..- - .
' `.
'.- . .--. .
|: _ | : _ :|
|`(@)--`.(@) |
: .' `-, :
:(_____.-'.' `
: `-.__.-' :
` _. _. .
/ / `_ ' \\ .
. : \\ \\
. : _ __ .\\ .
. / : `. \\
: / ' : `. .
' ` : : : `.
.`_ : : / ' |
:' \\ . : '__ :
.--' \\`-._ . .' : `).
..| \\ ) : '._.' :
; \\-'. ..: /
'. \\ - ....- | '
-. : _____ | .'
` -. .'-- --`. .'
`-- --
"""
flag = open('flag.txt','r').read()
MY_LUCKY_NUMBER = 29486316
# I need to bake special stuff!
def bake_it():
s = 0
for i in range(random.randint(10000,99999)):
s = random.randint(100000000000,999999999999)
s -= random.randint(232,24895235)
return random.randint(100000000000,999999999999)
# Create my random mess
def rand0m_mess(food,key):
mess = []
mess.append(key)
art = key
bart = bake_it()
cart = bake_it()
dart = bake_it()
for i in range(len(food)-1):
art = (art*bart+cart)%dart
mess.append(art)
return mess
# Gotta prepare the food!!!
def prepare(food):
good_food = []
for i in range(len(food)):
good_food.append(food[i]^MY_LUCKY_NUMBER)
for k in range(len(good_food)):
good_food[i] += MY_LUCKY_NUMBER
return good_food
# Bake it!!!
def final_baking(food,key):
baked = rand0m_mess(food,key)
treasure = []
for i in range(len(baked)):
treasure.append(ord(food[i])*baked[i])
treasure = prepare(treasure)
return treasure
print(good_image)
key = bake_it()
print(final_baking(flag,key))
The first thing I did was go through each of the functions and try to clean up the junk. For example
def bake_it():
s = 0
for i in range(random.randint(10000,99999)):
s = random.randint(100000000000,999999999999)
s -= random.randint(232,24895235)
return random.randint(100000000000,999999999999)
should just be
def get_random():
return random.randint(100000000000,999999999999)
The function rand0m_mess(food,key) simply creates an array, the same length of the flag, filled with random numbers.
The encryption happens in two steps. First the flag is prepared(flag) where two operations are preformed on the bytes of the flag
def prepare(food):
good_food = []
for i in range(len(food)):
good_food.append(food[i]^MY_LUCKY_NUMBER)
for k in range(len(good_food)):
good_food[i] += MY_LUCKY_NUMBER
return good_food
The keen eyed will immedately see the typo in this function. What it looks like this function should do is the following:
def prepare(flag):
encrypted = []
for i in range(len(food)):
x = (food[i]^MY_LUCKY_NUMBER) + MY_LUCKY_NUMBER
encrypted.append(x)
return encrypted
Except that isn’t what’s happening. In the second loop over k, the index of the encryption is labelled with i, which is still valued at the end of the flag therefore the actual encryption is given by
def prepare(flag):
encrypted = []
for i in range(len(food)):
encrypted.append(food[i]^MY_LUCKY_NUMBER)
encrypted[-1] + MY_LUCKY_NUMBER * len(flag)
return encrypted
After this inital encryption, each byte is then multipled by the random data in mess
# Bake it!!!
def final_baking(food,key):
baked = rand0m_mess(food,key)
treasure = []
for i in range(len(baked)):
treasure.append(ord(food[i])*baked[i])
treasure = prepare(treasure)
return treasure
The random integers are way to big to try and start brute forcing, but lucky for us we dont need to. We can access the data via the server as many times as we like. Each time the data is multiplied by a new random number, but the bytes of the encrypted flag are always the same! This means we can call the server, over and over, and the look at the greatest common divisor for each element. For a suffienctly large data set the gcd will be the byte of the flag and we’ll be all sorted!
The first thing we do is write a small function to unprepare our food, then we call the server, take the data and unprepare it and store it in an array. We iterate over this a bunch of times and calculate the gcd.
Flag
hsctf{th1s_1s_0ne_v3ry_l0ng_fl@g_b3ca8s3_t5x_l0v3z_vveR9_LOn9_flaGs7!}
Note: This flag was leaked and replaced with a second flag:
hsctf{thiii111iiiss_isssss_yo0ur_b1rthd4y_s0ng_it_isnt_very_long_6621}
Python Implementation
from pwn import *
from math import gcd
from functools import reduce
context.log_level = 'critical'
MY_LUCKY_NUMBER = 29486316
def unprepare(good_food):
good_food[-1] -= MY_LUCKY_NUMBER*len(good_food)
unprepared = []
for i in range(len(good_food)):
unprepared.append(good_food[i]^MY_LUCKY_NUMBER)
return unprepared
def get_treasure(n):
bounty = []
for _ in range(n):
r = remote('crypto.hsctf.com', 8112)
r.recvuntil('[')
x = r.recvuntil(']').decode()
x_list = x[:-1].replace('L', '').split(', ')
x_list = [int(x) for x in x_list]
treasure = unprepare(x_list)
bounty.append(treasure)
return bounty
print("Collecting Treasure...")
treasure_count = 10
bounty = get_treasure(treasure_count)
print(bounty)
print("Finding Flag...")
flag = []
for j in range(70):
letter = []
for i in range(treasure_count):
letter.append(bounty[i][j])
flag.append(reduce(gcd,letter))
print("".join([chr(x) for x in flag]))
# >> hsctf{th1s_1s_0ne_v3ry_l0ng_fl@g_b3ca8s3_t5x_l0v3z_vveR9_LOn9_flaGs7!}
Bomb
When I first saw this, the idea of cracking enigma made me just not want to bother. It’s hard and annoying and generally a pain in the arse. I’m glad I went through it though, as GCHQ has recently developed a new tool “Bombe” which made the whole thing feel pretty fun.
Before I start, I 100% recommend reading and following the examples that GCHQ released with the deployment of this tool Enigma, the Bombe, and Typex
Challenge Data
Keith is very confused. Help Keith find out what the message means. nc crypto.hsctf.com 8100
JGYJZ NOXZX QZRUQ KNTDN UJWIA ISVIN PFKIR VWKWC UXEBH RFHDI NMOGQ BPRHW CXGAC ARBUN IHOWH QDDGL BBZYH HEJMV RBLJH CLHYP FSAAA KNRPX IKSNX QASGI XBMNP FLAFA KFEGV YWYUN JGBHH QDLZP UJWMO CCEUL YFIHR GTCOZ GEQML VFUAV URXUU BBGCI YZJQQ ROQFU SJDVR JILAJ XYCBC IGATK LQMAP UDPCG ONWFV MHBEC CLBLP JHZJN HMDNY YATIL FQSND AOCAM MGVRZ FEVKL CEDMG AIWXG QPCBI VTVZU HQGFD ZJICI EIWLP IFKAB LNVZI XRZTR SLGCA SZPFF HGBUK JAXNN JHUSV UFPIM ZZLAW SYOHB TOLRF KWANX FNEFD XXLNR LLGYS VTGXP NJQMC WAKRP JKWDP WVTNP WRYEJ RSODI QDYOQ DJDBI SLAVB UPDDR ATHYG ANJQR XPGFM FAMJR ZSJHC SYWQQ VBIHX XCQFW XZBUH ZRXWV TPESM EGVVY PBJSS
Reflector: B
Rotors: 3,2,4
Crib: the secret to life is
So lets start by firing up cyberchef and adding all this data into Bombe. We’re lucky! With an offset of 0 for the crib it looks like we’ve got something to work with:
Rotor Stops: ECG
Partial Plugboard: EK BC DQ II JJ LP MN OO RT SU XZ YY
Lets go to enigma now and see whether we can tweak this into giving us what we want. Lets add the rotor dials, reflector, inital positions ECG and the partial plugboard into the enigma tool: Enigma. This looks like garbage! Luckily for us, GCHQ tell us in the guide that this is to be expected.
To start getting something sensible we start rotating the right dial: AG, BH, CI, etc. By the time I was at EK I wasnt seeing much more improvement, so I started playing with the plug board. My crib still wasn’t perfect but after making the additons VF AG to the plugboard things were starting to get sensible.
My last step was to fiddle with the middle ring, stopping at RT for the middle ring setting I found
THESE CRETT OLIFE ISPTO MERSY CTFST ANDSF ORCAP TURET HEFLT ECTFS AREAT YPEOF COMPU TERSE OJRIT YCOMP ETITI ONBUT HSCTF EWOEN DSBEY ONDCO MPUTE RSECU RIBNT OINCL UDEOT HERAR EASOF COMQS TERSC IENCE CERTA INPIE CESON ONFOR MATIO NCALL EDFLA GSARE SUACE DONSE RVERS ENCRY PTEDH IACEN OROTH ERWIS ESTOR EDSOM EWYVR EDIFF ICULT TOACC ESSDU RINXY HSOIQ ITHID WYMOA NIFGP QUXVM RDQJS TWWTU TCTUJ JHALI FMMYJ YPFJG IMRID YPMXO LSLWM XACQW FOBWK GBFMY ZUVXA EQLAN DMJGX JNPBD OWHAT EVERI TTAKE STOCA PTULZ THATF LAGWH ENATE AMSUB MITSP ZISFL AGTOA SCORI NGPAG ETHEY XCLLG ETPOI NTSTH EPASS WORDI SVESE CUREK EITHW ASANE NIGMA
Look at that! The end is looking pretty good now. Lets format it a bit
THE PASSWORD IS VESECURE KEITH WAS AN ENIGMA
Okay… so VESECURE isn’t a word, but by this point it’s enough to guess
THE PASSWORD IS INSECURE KEITH WAS AN ENIGMA
Lets use our nc crypto.hsctf.com 8100 to submit out flag:
~$ nc crypto.hsctf.com 8100
Password:
KEITH WAS AN ENIGMA
No...
uh….
~$ nc crypto.hsctf.com 8100
Password:
INSECURE KEITH WAS AN ENIGMA
Here is your flag!
hsctf{d1d_y0ur_b0mbe_s4cc33d???-961451631955}
That’s better!
Flag
hsctf{d1d_y0ur_b0mbe_s4cc33d???-961451631955}
Spooky ECC
Challenge Data
Bigger curves means better right?
The data is encrypted with the following script
p = 0xb09700d3d1c7123f0b0336474c18c3f3f60002d480a4bce33f007c08b498197ed832687c47c2bc76b7eb199d3a420fcf77d3e5a32389fefb1032744bb473a4bd
A = 0x1b2a886d1cfcaecd03954657956cd03df56ec7709fbb0de738fb073ed20b92b6fa3d72f771618c5e2060a23c33b586a6046993894fd4950db2c12776e77fdbd1
B = 0x303bde5e945d46949b8c9986519a9a1f0301f61ff043b3bf2785fd85e365e4caa163c64ad307db8dbbac0087fd8562273ee61aac095815030cc73c7495b46ddb
g_x = 0x9f12acd5b74cc67e03506be8f904087863ce7fd8ed1de6404f26e8e96bea3761fca1f5b21def5298e7adbbf8787ea431a43d241fda6bc9fbaddeaff35ab4f7c3
g_y = 0x51f33f0e5c36e1bf91ac78b04c7e4f819bfad8db291fc2e20c10ee00e98525927719ecf0e8b96c5e62e3f48a38b94e72dddee1109bfdad9c7dfd3f566da69eb4
E = EllipticCurve(GF(p), [A, B])
g = E(g_x, g_y)
def generateKey():
private = randint(1, E.order() - 1)
public = g * private
return(public, private)
def computeSharedSecret(pubkey, privkey):
return pubkey * privkey
def secure_send_flag():
from secret import flag
myPubKey, myPrivKey = generateKey()
print myPubKey
bob_pub_x = 0x993cf91c25dd287e30cb8f6a0d4fa70e89e90ac0953e7ee876b1ef190a6a442235479162b5ac61beb1d1a5aca03313ff5c53c2e3c81df2fbedf3b0add0b20d18
bob_pub_y = 0x4e75b39de8d5daa3f5f489c02b8fa2cce6f2cfb406bb4a5a0d75d29a3021dcd61df697ef485743e7f8a1b9cc60879bc808e74f9c909b2f0cecb1df0a03c771f5
bobPubKey = E(bob_pub_x, bob_pub_y)
DH_secret = computeSharedSecret(bobPubKey, myPrivKey)
from hashlib import sha256
from Crypto.Cipher import AES
AES_secret = sha256(str(DH_secret.xy())).digest()
obj = AES.new(AES_secret, AES.MODE_ECB)
flag += " " * ((16 - len(flag)) % 16)
ciphertext = obj.encrypt(flag)
import binascii
print binascii.hexlify(ciphertext)
and the two print outs of the script are captured in the intercept
# public key
(1177058043549358413014554258002815119079001682731148396776662750875463733619059415667987598866208023692880799135159888362631239206873676420277546691755222 : 6042132606876152754155047441818131810928517366269481359146510190883638121779596002132009344517568983680414721512960291321687246617263491498797986759689315 : 1)
# ciphertext
d5cb4f93aa95af738bbcf5cbc1d4f1b66c9c9f84b4257035cf19e3ee41e2b79384fed7ef7d9fb58f6dfb86fefc95429b9f87b5b8a330aa082681fd140b8156bd
This was my first attempt at solving an ECC puzzle and really Robin solved it. After learning a bit more while trying I actually really like this challenge. The trick to solving this flag is to notice that the order of curve is equal to the modulus, this means we can perform an anomalous curve attack and obtain the private key (an integer) and solve the challenge.
I used sage online SageMath which doesnt have the Crypto package. This means the solution of this isn’t a single script but rather something I did in a few parts.
Obtaining the Private Key
I was a script kiddy for this stage of the puzzle and used this script, orginally by Shiho Midorikawa
To use the script we input the data points of the generator g and the public key v.
from sage.all import *
p = 0xb09700d3d1c7123f0b0336474c18c3f3f60002d480a4bce33f007c08b498197ed832687c47c2bc76b7eb199d3a420fcf77d3e5a32389fefb1032744bb473a4bd
A = 0x1b2a886d1cfcaecd03954657956cd03df56ec7709fbb0de738fb073ed20b92b6fa3d72f771618c5e2060a23c33b586a6046993894fd4950db2c12776e77fdbd1
B = 0x303bde5e945d46949b8c9986519a9a1f0301f61ff043b3bf2785fd85e365e4caa163c64ad307db8dbbac0087fd8562273ee61aac095815030cc73c7495b46ddb
E = EllipticCurve(GF(p), [A, B])
#verify attack
print E.order() == p
g_x = 0x9f12acd5b74cc67e03506be8f904087863ce7fd8ed1de6404f26e8e96bea3761fca1f5b21def5298e7adbbf8787ea431a43d241fda6bc9fbaddeaff35ab4f7c3
g_y = 0x51f33f0e5c36e1bf91ac78b04c7e4f819bfad8db291fc2e20c10ee00e98525927719ecf0e8b96c5e62e3f48a38b94e72dddee1109bfdad9c7dfd3f566da69eb4
v_x = 1177058043549358413014554258002815119079001682731148396776662750875463733619059415667987598866208023692880799135159888362631239206873676420277546691755222
v_y = 6042132606876152754155047441818131810928517366269481359146510190883638121779596002132009344517568983680414721512960291321687246617263491498797986759689315
g = E(g_x,g_y)
v = E(v_x, v_y)
def hensel_lift(curve, p, point):
A, B = map(long, (E.a4(), E.a6()))
x, y = map(long, point.xy())
fr = y**2 - (x**3 + A*x + B)
t = (- fr / p) % p
t *= inverse_mod(2 * y, p) # (y**2)' = 2 * y
t %= p
new_y = y + p * t
return x, new_y
# lift points
x1, y1 = hensel_lift(E, p, g)
x2, y2 = hensel_lift(E, p, v)
# calculate new A, B (actually, they will be the same here)
mod = p ** 2
A2 = y2**2 - y1**2 - (x2**3 - x1**3)
A2 = A2 * inverse_mod(x2 - x1, mod)
A2 %= mod
B2 = y1**2 - x1**3 - A2 * x1
B2 %= mod
# new curve
E2 = EllipticCurve(IntegerModRing(p**2), [A2, B2])
# calculate dlog
g2s = (p - 1) * E2(x1, y1)
v2s = (p - 1) * E2(x2, y2)
x1s, y1s = map(long, g2s.xy())
x2s, y2s = map(long, v2s.xy())
dx1 = (x1s - x1) / p % p
dx2 = (y1s - y1) / p
dy1 = (x2s - x2)
dy2 = (y2s - y2) % p
m = dy1 * inverse_mod(dx1, p) * dx2 * inverse_mod(dy2, p)
m %= p
print m
# >> True
# >> 6353581316382951116912435858210848523752542416244027116954494124651325903592581425048948314268166841134427987845368818998618690247223629041133055730941222
This gives us the public key and allows us to obtain our AES key. Lets go back to the orginal script, but now lets replace the random private key with the one from our intercepted message. We’ll also terminate the script early and make it dumb out the hexdigest so we can transfer it to my version of python which can do the last bit of work.
from hashlib import sha256
p = 0xb09700d3d1c7123f0b0336474c18c3f3f60002d480a4bce33f007c08b498197ed832687c47c2bc76b7eb199d3a420fcf77d3e5a32389fefb1032744bb473a4bd
A = 0x1b2a886d1cfcaecd03954657956cd03df56ec7709fbb0de738fb073ed20b92b6fa3d72f771618c5e2060a23c33b586a6046993894fd4950db2c12776e77fdbd1
B = 0x303bde5e945d46949b8c9986519a9a1f0301f61ff043b3bf2785fd85e365e4caa163c64ad307db8dbbac0087fd8562273ee61aac095815030cc73c7495b46ddb
g_x = 0x9f12acd5b74cc67e03506be8f904087863ce7fd8ed1de6404f26e8e96bea3761fca1f5b21def5298e7adbbf8787ea431a43d241fda6bc9fbaddeaff35ab4f7c3
g_y = 0x51f33f0e5c36e1bf91ac78b04c7e4f819bfad8db291fc2e20c10ee00e98525927719ecf0e8b96c5e62e3f48a38b94e72dddee1109bfdad9c7dfd3f566da69eb4
E = EllipticCurve(GF(p), [A, B])
g = E(g_x, g_y)
E_order = p
def generateKey():
private = 6353581316382951116912435858210848523752542416244027116954494124651325903592581425048948314268166841134427987845368818998618690247223629041133055730941222
public = g * private
return(public, private)
def computeSharedSecret(pubkey, privkey):
return pubkey * privkey
def secure_send_flag():
myPubKey, myPrivKey = generateKey()
bob_pub_x = 0x993cf91c25dd287e30cb8f6a0d4fa70e89e90ac0953e7ee876b1ef190a6a442235479162b5ac61beb1d1a5aca03313ff5c53c2e3c81df2fbedf3b0add0b20d18
bob_pub_y = 0x4e75b39de8d5daa3f5f489c02b8fa2cce6f2cfb406bb4a5a0d75d29a3021dcd61df697ef485743e7f8a1b9cc60879bc808e74f9c909b2f0cecb1df0a03c771f5
bobPubKey = E(bob_pub_x, bob_pub_y)
DH_secret = computeSharedSecret(bobPubKey, myPrivKey)
AES_secret = sha256(str(DH_secret.xy())).hexdigest()
return AES_secret
print(secure_send_flag())
# >> 0f7dd8b0d63bfaee2035ccbaf35c89428dc8aa129af5772aa4ae6e01c3956ddd
With this inplace we can now decrypt the ciphertext and grab our flag
from hashlib import sha256
from Crypto.Cipher import AES
import binascii
def solve():
DH_secret = '0f7dd8b0d63bfaee2035ccbaf35c89428dc8aa129af5772aa4ae6e01c3956ddd'
AES_secret = binascii.unhexlify(DH_secret)
obj = AES.new(AES_secret, AES.MODE_ECB)
ciphertext = 'd5cb4f93aa95af738bbcf5cbc1d4f1b66c9c9f84b4257035cf19e3ee41e2b79384fed7ef7d9fb58f6dfb86fefc95429b9f87b5b8a330aa082681fd140b8156bd'
plaintext = obj.decrypt(binascii.unhexlify(ciphertext))
return plaintext.decode()
print(solve())
# >> hsctf{Anomalous curves, m0ar like anom00se curves}
Flag
hsctf{Anomalous curves, m0ar like anom00se curves}