ENOWARS 2011 CTF Write-up: Diary

The challenge consists of the following description:

Hey! I am sure, Dark Viewer is writing down every little poop he did. Just trying to get the infos by searching for his diary. Shit. Its encrypted but what is the key…
Lets try break it!!

and this ciphertext: diary

Despite being only 100pts worth, no team was able to solve this challenge during the CTF, so a hint was added:

Tip: Two very simple encryptions on top of each other.

Using our tool charemap, we can perform a quick analysis of the ciphertext:

$ ./charemap -i diary.txt -a -s | head -n6
  Original Char |     Occurrences |     Mapped char |
-----------------------------------------------------
            ' ' |             352 |             ' ' |
              r |             179 |               e |
              g |             135 |               t |
              v |             121 |               a |
              b |             120 |               o |
              n |             110 |               n |
              u |              96 |               r |
              a |              89 |               i |
              e |              75 |               s |
              q |              67 |               h |
              f |              63 |               d |
              y |              54 |               l |
              z |              50 |               f |

We notice that the most frequent char is r followed by g. The distance (modulo 26) between r and e is 13; the same holds for g and t and so on:

>>> (ord('r')-ord('e')) % 26
13
>>> (ord('g')-ord('t')) % 26
13

We can safely assume that the first encryption used is ROT13.

Now, ROT13 is a basic form of a substitution cipher, so E = substitution(ROT13(M)) = substitution'(M). It would be just one substitution in the end. Concerning the encryption on top of rot13, we can exclude the vigenere cypher because the frequency of chars is very close to a typical English language text. So, what is a well known cipher that only scrambles the text? The columnar transposition cipher 🙂

Looking deeper at the ciphertext we notice a good degree of regularity. We focus on some sequences of numbers that look like pieces of the flag (remember that the flag format is eno[a-z0-9]{37}). Starting from the end, we calculate the distance between these 7 substrings:

>>> f = open('diary_rot13.txt', 'r')
>>> enc = f.read()
>>> f.close()
>>> enc.find('2598a2') - enc.find('0f860')
269
>>> enc.find('0f860') - enc.find('0be70')
269
>>> enc.find('0be70') - enc.find('72d4e5d')
269
>>> enc.find('72d4e5d') - enc.find('77399')
268
>>> enc.find('77399') - enc.find('3d70')
270
>>> enc.find('3d70') - enc.find('49bef')
270

At this point, we know that there are 7 subsets of flag chars at a distance of ~269 chars between each one of them.

We calculate the char number of diary_rot13.txt to see if it’s possible that the columnar transposition cipher is implemented with 7 columns and 269 rows:

0 $ wc -c diary_rot13.txt
1884 diary_rot13.txt
0 $ echo $((7*269))
1883

Yes! But it looks like there is one column with one char more than the others (the first column before scrambling). This leads to an irregularity in the transposition cipher.

Now it’s just a matter of finding the column with 270 rows and the correct permutation of columns. We can guess that the last char of the plaintext is a vertical tab. In this case it will be placed in the second column. At this point, finding the right permutation is trivial. We use the following code to decrypt the message:

#!/usr/bin/python

# Author:       Marco Squarcina 
# Description:  Script for solving "Challenge 1: Diary" of ENOWARS 2011,
#               there are two encryptions applied on this ciphertext: ROT13
#               and an irregular columnar transposition.


import sys, codecs
from numpy import array

# row length
R = 269
# standard column length excluding blanks
C = 7

def main():
        # read the ciphertext
        f = open(sys.argv[1], 'r')
        enc = f.read()
        f.close()

        # apply ROT13
        enc = codecs.encode(enc, "rot13")

        # create the matrix and fill it with ciphertext
        m = array([[ "" for i in range(C) ] for j in range(R+1)])
        j = 0
        for i in range(0,len(enc)):
                # the second column has 1 char more that leads to an irregularity in the
                # transposition cipher
                if i == 538:
                        m[269][1] = enc[i]
                else:
                        m[j%R][j/R] = enc[i]
                        j = j+1

        # remap columns using numpy advanced slicing
        m[:,[0, 1, 2, 3, 4, 5, 6]] = m[:,[1, 2, 3, 6, 0, 4, 5]]

        # print the decrypted message
        dec = ""
        for row in range(R+1):
                for col in range(C):
                        dec += str(m[row][col])
        sys.stdout.write(dec)

if __name__ == "__main__":
        main()

With this script, we get the deciphered text and the flag!