Hackfest CTF 2017 Quals - Unsolved tasks writeup

Hello,

This page contains a quick and dirty instructions about how to solve the most unsolved tasks proposed during the online qualification round of Hackfest CTF 2017.

For10

Contestants were given a floppy image disk. It contains an RSA public key and 2 files containing encrypted data. The first idea which comes to mind. Is to attack RSA based on the provided public key. Let me tell you that this task is not about factoring N. 

This is basically a Forensics challenge. By analyzing the given disk image using Autopsy, you will figure out that there is a deleted pyc file. recover it then de-compile it using uncompyle2 for example. You get the python source code used to encrypt the flag. flag.back.enc and flag.enc are both ciphers of the same flag message. There is a polynomial relation between flag.enc and flag.enc.bak with degree delta = (modification time of flag.bak.enc - modification time of flag.enc). You can extract the last modification time on a file using the command stat -c %X. From the source code or the public key you get the value of the exponent e which is a low exponent (e=17). All those information are enough to perform a Franklin-Reiter related message attack.
https://www.cs.unc.edu/~reiter/papers/1996/Eurocrypt.pdf

Putting all together:

import binascii

def attack(c1, c2, delta, e, n):
    PRx. = PolynomialRing(Zmod(n))
    g1 = x^e - c1
    g2 = (x+delta)^e - c2

    def gcd(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic()

    return -gcd(g1, g2)[0]

c1=10880034844172469052981791827354127229154201440423217707536444121124275246552808247167392769811967751593735430970626304918553904951192398535677551360191392392281496970760292363413634300196045918122279859820711482997487437793689614968816882250170439210408797194012707019387733366266337138704878312925255380349018651556215097609065239577654468153363651645135452754680370314084422370351226585369601962995682769962753587392860582377819372826726033252701873280814818152331412339215243676390260412590225137607965050582900883048039187888344532026364624434988349989812174444666284536696245011538335356999710957542528135073762L

c2=39463595469616140341056106278714488721639802551556663492258223362811379884638910222210828207843122386187911897916522422885123110392549451346396276630934341730909294770535352243890213370011074494047289987055196276505397129219974271774997975494807052548024695212779779255245855816344174201857895717365452616172535273749132068060394195761018653420499439716635310637511445437333222723763558739215368936634293139134825229377563404156784659462606364062054161279301553482737277835985836238059169587065037432391166349986893454405408754904011582575049204307095437867550541219358723277938005278774313199760666216202954064525L

n=15929793877604817540005217755706422556240415451103581442897333688318448914859523609922869266570161946925318816229133148041811823473105336890660672558048216356825073555501217205384139536950378567155663409455849044752514801303559551039325925837885151304257575969300435144531715352163183011713024442397302405857519930659841583523130392362274727319399123369155079598742140714401273862189666598990310570111846290582020324588032118223474327870359374946268212744710908687857198555592446979871447865157913863660573414940450103192949126548027037286416891262206940627329931608106090547470907635794995575814659485634052786501803

e=17

diff = 1490369301 - 1489964508

m = attack(c1,c2, diff,e,n)

print binascii.unhexlify("%x" % int(m - 1489964508))

The flag was hackfest{r3l4t3d_m3ss4g3_4tta4k_0n_rsa_1s_th3_n3w_c00l}

Rev10

A binary without anti-debug tricks or obfuscation ... all what you have to do is reversing the algorithm
Here is my exploit

flag_enc = "sont!eslwha{eidssmrfrke}_ehs___cuoootscihmpcti_us_eeii_esf_ots"

flag = []
  
for i in range(len(flag_enc)):    
    s = flag_enc[i:i+1]
    flag.append(s)

while len(flag[0]) < len(flag_enc):
    new_str = sorted(flag);
    for i in range(len(flag)):
          flag[i] = flag[i] + new_str[i][len(new_str[i])-1:len(new_str[i])]
          if flag[i].startswith("hackfest{"):
              print flag[i]

The correct input is hackfest{compression_is_somehow_useful_to_hide_secrets!_it_is}

That's all :)