## dub-key (crypto, 120p)
> My friend set up a small signing scheme, however she won't let me sign stuff. Can you get it signed?>> Find it at dub-key-t8xd5pn6.9447.plumbing port 9447>> [dub-key.py](dub-key.py)
###PL[ENG](#eng-version)
Rozpoczeliśmy od analizy algorytmu podpisywania i jego własności(w skrócie - podpisywanie polega na tym że zmieniamy wiadomość w graf, i podpis toiloczyn długości wszystkich cykli w wiadomości). Niestety, nie udało nam się skończyć pisać pełnego atakuprzed końcem CTFa, ale w ostatnich godzinach zdecydowaliśmy się wykonać trywialny atak na algorytm podpisywania.
Otóż w tym zadaniu możemy podpisać dowolną wiadomość poza jedną - tą którą mamy podpisać żeby dostać flagę.Zauważyliśmy, że jeśli zmienimy tylko jeden bajt w wiadomości i podpiszemy go, to jest spora szansa że podpis się nie zmieniOszacowaliśmy tą szansę jako pesymistycznie 1/(256*e), ale prawdopodobnie znacznie większą - i rzeczywiście, w praktyce jużpo kilkudziesięciu sprawdzeniach udało się.
Pomysł sprowadza się do:
    msg = odbierz_wiadomość_do_podpisania()    msg1 = msg[-1] + '\x00'    sig1 = podpisz(msg1)    wyślij_podpis(sig1)
Tak więc nasz cały kod atakujący wyglądał tak:
```pythonimport hashlibimport socketimport stringimport itertoolsimport base64
def pow(init):    for c in itertools.product(string.lowercase, repeat=6):        dat = init + ''.join(c)        hash = hashlib.sha1(dat)        if hash.digest().endswith('\x00\x00\x00'):            return dat
def recv():    return s.recv(99999)    return r
def send(msg):    s.send(msg)
while True:    HOST, PORT = 'dub-key-t8xd5pn6.9447.plumbing', 9447    s = socket.socket()    s.connect((HOST, PORT))    inp = recv()    print inp    p = pow(inp)    send(p)    r = recv()    tosign = recv().split("\n")[0]    dat = base64.b64decode(tosign)    dat = dat[:-1] + '\x00'    send('1\n')    send(base64.b64encode(dat))    r = recv() # podpisane dane    t = recv() # sign something    send('2\n')    send(r)    print recv(), recv(), recv()```
I, co zaskakujące, zadziałał za pierwszym razem.
Flaga:
    9447{Th1s_ta5k_WAs_a_B1T_0F_A_DaG} 
### ENG version
We started with the analysis of the signature algorithm and its properties (in short - signing is done by changing the message into a graph and the signature is the number of all cycles in the message). Unfortunately, we didnt finish writing a full attack before the CTF ended, so in the last hours we decided to stick with a simple signature attack.
In this task we can sign any message apart from one - the one that gives us the flag. We noticed that if we change a single byte in the message and sign it, there is high chance that the signature will not change. We assumed that pessimistic probability is 1/(256*e), but apparently it's much higher - in practice we got it right after few dozens of attempts.
The idea is:
    msg = receive_message()    msg1 = msg[-1] + '\x00'    sig1 = sign(msg1)    send_signature(sig1)
So the code of entire attack was:
```pythonimport hashlibimport socketimport stringimport itertoolsimport base64
def pow(init):    for c in itertools.product(string.lowercase, repeat=6):        dat = init + ''.join(c)        hash = hashlib.sha1(dat)        if hash.digest().endswith('\x00\x00\x00'):            return dat
def recv():    return s.recv(99999)    return r
def send(msg):    s.send(msg)
while True:    HOST, PORT = 'dub-key-t8xd5pn6.9447.plumbing', 9447    s = socket.socket()    s.connect((HOST, PORT))    inp = recv()    print inp    p = pow(inp)    send(p)    r = recv()    tosign = recv().split("\n")[0]    dat = base64.b64decode(tosign)    dat = dat[:-1] + '\x00'    send('1\n')    send(base64.b64encode(dat))    r = recv() # signed data    t = recv() # sign something    send('2\n')    send(r)    print recv(), recv(), recv()```
And it actually worked on first attempt.
Flag:
    9447{Th1s_ta5k_WAs_a_B1T_0F_A_DaG} 