# HackingWeek 2015 - Crypto 1

Decryption of an ADFGVX ciphertext, breaking a transposition cipher used by German Army during World War I.

## 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.

### Permutations script

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

KEYSQUARE = "CEY1L0ZRJSHPMOF385AXIB4U92VQWT6GD7NK"

def verify(keyword):
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,i) for i,k in enumerate(sorted(t1))]
return [q for q in sorted(t2)]

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

### Permutations results

``````Keyword found : 2610345978

Keyword found : 2610395478

Keyword found : 2610435978

Keyword found : 2610495378

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

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 = []
group =  "".join([CHARSET1 for c in range(i, len(ORDINAL) - (max(MASK) - i))])
cases.append(group)

for s3 in cases:
for s2 in cases:
if s2 < s3:
continue
for s0 in cases:
if s0 < s2:
continue
for s4 in cases:
if s4 < s0:
continue
for s5 in cases:
if s5 < s4:
continue
for s6 in cases:
if s6 < s5:
continue
for s1 in cases:
if s1 < s6:
continue
for s8 in cases:
if s8 < s1:
continue
for s9 in cases:
if s9 < s8:
continue
for s7 in cases:
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.