HackingWeek 2015 - Crypto 1

Introduction

The goal of the first cryptography challenge was to break the ADFGVX cipher and use the keyword to find the flag. It was rather difficult to complete this challenge with the ciphertext only so after a few hours the organizers added some hints.

ADFGVX était le chiffre utilisé par les Allemands pendant la première guerre mondiale. Essayez de vous y frotter en déchiffrant ce message dont le clair est en français:

Indice: Le md5sum du mot de passe est a50e38475041f76219748ee22c4377d4.
Et le Keysquare est: Keysquare: cey1l0zrjshpmof385axib4u92vqwt6gd7nk

DADVDFDDXDDAXGDFFDXDDDADAXAAGAFGGDAXGADAVAAADVFXFDFDVGFGAAAVFAFGFA
DADDVDGDVAXVDDVFFADGDGAXGFXXDFXDGGXFAADVGAXDVAVVAVAXDVADXADDDAXGXA
AVADFVAAFXAGVGAAAFDDGDAGFADFVDAFXDDDDDDADDXXAFFDAGXAVFGFDXFDXD

Context

We know the ciphertext, the key square and the md5 sum of the expected keyword used for the columnar transposition.
Another hint was added then removed the last word of the plain text is "EPREUVE".

ADFGVX is a fractionating transposition cipher which combine a modified Polybius square with a single columnar transposition.
After reading how it works, the next step was to develop a script to find a valid combination for the columnar transposition.

Finding the permutations

The permutation is defined by the alphabetical order of the letters in the keyword.
We will assume the length of the keyword is between 6 and 10 so we can use the full numeric charset.

Instead of implementing your own ADFGVX cipher you can use the pycipher python library.

Permutations script

#!/usr/bin/env python
import itertools
import string
from adfgvx import ADFGVX

CIPHERTEXT = "DADVDFDDXDDAXGDFFDXDDDADAXAAGAFGGDAXGADAVAAADVFXFDFDVGFGAAAVFAFGFADADDVDGDVAXVDDVFFADGDGAXGFXXDFXDGGXFAADVGAXDVAVVAVAXDVADXADDDAXGXAAVADFVAAFXAGVGAAAFDDGDAGFADFVDAFXDDDDDDADDXXAFFDAGXAVFGFDXFDXD"
KEYSQUARE = "CEY1L0ZRJSHPMOF385AXIB4U92VQWT6GD7NK"

def verify(keyword):
    plaintext = ADFGVX(KEYSQUARE, keyword).decipher(CIPHERTEXT)
    if plaintext[-7:] == "EPREUVE":
        print("Keyword found: {:s}\n{:s}\n".format(keyword, plaintext))

def generate(charset, minlength, maxlength):
    return ("".join(candidate)
        for candidate in itertools.chain.from_iterable(itertools.permutations(charset, i)
        for i in range(minlength, maxlength + 1)))

def sortind(word):
    t1 = [(word[i],i) for i in xrange(len(word))]
    t2 = [(k[1],i) for i,k in enumerate(sorted(t1))]
    return [q[1] for q in sorted(t2)]

if __name__ == "__main__":
    for attempt in generate(string.digits, 6, 10):
        verify(attempt)

Permutations results

Keyword found : 2610345978
TROUVEZLACLEFDECHIFFREMENTDECEMESSAGEETVOUSAUREZLEMOTDEPASSEQUIVOUSPERMETTRADEVALIDERCETTEEPREUVE

Keyword found : 2610395478
TR5XVEZC4CLEFDECHIFFREOCNTDCEEMESSAGE02VOUZBUREHCEMOVKEPASSEQUIVOUSR0RMETTRADY2ALIGYRCETTEEPREUVE

Keyword found : 2610435978
TRJUVEZ9ACLEFDECH3FFREYENTDZCEMEXSAGEZTVOUXAUREELEMONDEPAXSEQU3VOUSGERMENTRADZVALI5ERCENTEEPREUVE

Keyword found : 2610495378
TRPIVEZ9ACLEFDECHF3FREEYNTDZCEMEBRAGEP9VOUAXURELEEMODNEPABREQUFQOUSGERMEKWRADJ9ALIO0RCEKWEEPREUVE

Running the script will output a few suggestions like above. The first keyword "2610345978" has a valid permutation and output the text plain text.
Now we know the length of the keyword is 10 and we also know the order of the letters in this keyword.

Finding the expected keyword

We know the keyword length and the order of the letters there are quite a lot of possibilities.

Bruteforce script

#!/usr/bin/env python
import itertools
import hashlib
import string

CIPHERTEXT = "DADVDFDDXDDAXGDFFDXDDDADAXAAGAFGGDAXGADAVAAADVFXFDFDVGFGAAAVFAFGFADADDVDGDVAXVDDVFFADGDGAXGFXXDFXDGGXFAADVGAXDVAVVAVAXDVADXADDDAXGXAAVADFVAAFXAGVGAAAFDDGDAGFADFVDAFXDDDDDDADDXXAFFDAGXAVFGFDXFDXD"
KEY = "CEY1L0ZRJSHPMOF385AXIB4U92VQWT6GD7NK"
CHECKSUM = "a50e38475041f76219748ee22c4377d4"

MASK = [2, 6, 1, 0, 3, 4, 5, 9, 7, 8]

CHARSET = string.lowercase
ORDINAL = map(ord, CHARSET)

def generate(charset, minlength, maxlength):
    return ("".join(candidate)
        for candidate in itertools.chain.from_iterable(itertools.permutations(charset, i)
        for i in range(minlength, maxlength + 1)))

def bruteforce():
    cases = []
    for i in MASK:
        group =  "".join([CHARSET1 for c in range(i, len(ORDINAL) - (max(MASK) - i))])
        cases.append(group)

    for s3 in cases[3]:
        for s2 in cases[2]:
            if s2 < s3:
                continue
            for s0 in cases[0]:
                if s0 < s2:
                    continue
                for s4 in cases[4]:
                    if s4 < s0:
                        continue
                    for s5 in cases[5]:
                        if s5 < s4:
                            continue
                        for s6 in cases[6]:
                            if s6 < s5:
                                continue
                            for s1 in cases[1]:
                                if s1 < s6:
                                    continue
                                for s8 in cases[8]:
                                    if s8 < s1:
                                        continue
                                    for s9 in cases[9]:
                                        if s9 < s8:
                                            continue
                                        for s7 in cases[7]:
                                            if s7 < s9:
                                                continue

                                            attempt = s0 + s1 + s2 + s3 + s4 + s5 + s6 + s7 + s8 + s9

                                            h = hashlib.md5()
                                            h.update(attempt)
                                            if CHECKSUM == h.hexdigest():
                                                print attempt

if __name__ == "__main__":
    bruteforce()

Bruteforce result

Although the nested loops are dirty, this script above is very efficient. It found the expected passwords in a matter of seconds.
There was a little trick, the keyword was "docadeitoo" and as you can see the letter "o" repeats three times.