Saturday, 8 October 2016

CODZ cipher 13. kin_paper_torn straddle checkerboard?

I haven't actually played the game, I just like breaking codes.

Apparently there are some new CODZ ciphers, the transcripts can be seen here:

This post will look at the following cipher:



EDIT: I'm beginning to think that this is not the final decryption, that they have used a slightly modified method which results in some extra characters. There is too much decrypted for me to think that it is totally wrong, but I believe there is an extra step I'm missing somewhere in the middle. </EDIT>

The ciphertext is a straddle checkerboard. Converting the 10 symbols to digits, and reversing the string, we get (using @=0, C=1, B=2, ?=3, >=4, F=5, A=6, G=7, = is 8, <=9, Note that this mapping is arbitrary, and any other mapping would work just as well):

320143238736103135367632361414143975932181021439731321 83607321012710183138733341010341033711143635014343210

See the link for a description of the straddle checkerboard. Using this key:


The message decrypts to OCTOBERNSAREFORTTTHEYFOUNDTHESOURCEONVENUSBEGINNINGEXTRACTION. with spaces: OCTOBER NSA REPORT T THEY FOUND THE SOURCE ON VENUS BEGINNING EXTRACTION. There are likely a couple characters wrong still, or the slight mistakes are intentional.

My approach

There are 10 different characters, 107 in total. The counts for each character are as follows: A: 6, @: 11, C: 24, B: 9, G: 8, F: 3, =: 5, <: 3, ?: 28, >: 10. It so happens that 10 characters can be converted to digits, so we can look at existing ciphers that use digits e.g. the straddle checkerboard, GRANDPRE, MONOME-DINOME, MORBIT, NIHILIST SUBSTITUTION, POLLUX or TRIDIGITAL. There are probably also more.

Converted to digits it is: 0123434105363411173301430101433378313810172101237063812313 7934120181239579341414163236763531301637832341023. If you reverse it, you get 320143238736103135367632361414143975932181021439731321 83607321012710183138733341010341033711143635014343210. I'll be talking about the non reversed ciphertext, but I'll be applying all the steps to both just in case. Using the above ciphertext and this calculator, we can compute the most likely cipher algorithms, and it has concluded that it is most likely a nihilist substitution. Unfortunately, it can't be nihilist because it has an odd number of characters, and nihilist requires even. It can't be grandpre for the same reason. CryptoCrack (from here) can't break it as GRANDPRE, MORBIT, NIHILIST SUBSTITUTION, POLLUX or TRIDIGITAL.

That really only leaves straddle checkerboard as the last candidate from the ciphers I can think of. Assuming it is a straddle checkerboard, we first have to find to location of the blanks in the key. If we can find those locations, we can decrypt in with any letters and we will have a plain substitution cipher. There are 10 choose 2 = 45 ways of putting the first 2 blanks, and 20 choose 2 = 190 ways of putting the second. This means there are 45*190 = 8550 possible configurations of putting the blanks. Some of these will be invalid though, e.g. the key:

   0 1 2 3 4 5 6 7 8 9
   f k m   c p d   y e
3: h b i g q r o s a z
7: l u t j n w v x    

can't have 38, 39, 78 or 79 in the ciphertext. If these numbers do exist in the ciphertext, then this is not a possible set of blanks. After trying to decrypt our ciphertext with all 8550 keys, only 3340 are actually valid blank positions. In addition to this, most of the blank positions result in identical outputs to other blank positions, so we can discard all the duplicate outputs, leaving only 45 substitution ciphers that we have to try.

After trying to decrypt the resulting 45 substitution ciphers from the forward cipher and another 45 from the reversed cipher, one of the decrypts, namely SALSYFWIRVWFESWLLLZFDHSOIBLZFRSOWAFSIKFIORYFTUIIUITFJLWVALUSI, can be decrypted to OCTOBERNSAREFORTTTHEYWOUNDTHESOURCEONMENUSBEGINNINGEXTRACTION. There are likely a couple characters wrong still, or the slight mistakes are intentional.

This is a bit of python code that will spit out the possible substitution ciphers for a given straddle checkerboard ciphertext (Please excuse the rough code, I wrote everything pretty quick):

I have actually since discovered there is a much shorter way of getting to the final candidates, but I'll leave this code here. To rank the final candidates, use index of coincidence, the correct one is almost always the one with the IC closest to 0.07.

import random
import sys
from itertools import combinations

ctext = '6909746723099383772753870703607230943837727093872638757438333832743772974928387272384175943874720383270'

''' decrypt a straddle checkerboard cipher ctext given a key
 key should look like e.g. 'fkm.cpd.yehbigqrosazlutjnwvx..' 
 it should be 30 chars in length, and have 4 dots. 
 2 dots in the first 10 chars, and 2 in the last 20.
 - if it returns 0 in the first result, the key was invalid
def scdecrypt(ctext,key):
    dotpos = []
    for i,k in enumerate(key): 
        if k == '.': dotpos.append(i)
    output = ""        
    if dotpos[0] > 9: return 0,output
    if dotpos[1] > 9: return 0,output
    if dotpos[2] < 10: return 0,output
    if dotpos[3] < 10: return 0,output
    flag = 0
    for cc in ctext:
        c = int(cc)
        if key[c] != '.' and flag == 0: 
            output += key[c]
        elif flag == 1: 
            if key[10+c] == '.': return 0,""
            output += key[10+c]
            flag = 0
        elif flag == 2: 
            if key[20+c] == '.': return 0,""        
            output += key[20+c]
            flag = 0
        elif c == dotpos[0]: flag = 1     
        elif c == dotpos[1]: flag = 2
            return 0,output
    return 1,output

''' see if word and ct are possibly the same substitution cipher 
returns 0 in the first part of the result if they are not '''        
def canstart(ct,word):
    key = {}
    if len(word) > len(ct): return 0,key
    for i,char in enumerate(word):
        if ct[i] not in key: 
            if char not in key.values():           
                key[ct[i]] = char
            else: return 0,key
        elif key[ct[i]] == char: pass
        else: return 0,key
    return 1,key

# get a list of all the possible blank spot permutations
dp = []
a = combinations(range(10),2)
for i in a:
    b = combinations(range(20),2)
    for j in b:
        dotpos = list(i)

# we have all possible blank spot positions, try decrypting with each and see if we can discard any
count = 0
texts = []
for d in dp:
    for pos in d: key.insert(pos,'.')
    bool,ptext = scdecrypt(ctext,key)
    if bool == 0: continue
    count += 1

# now we have a heap of valid decrypts, discard duplicates
lst = []
for i in range(len(texts)):
    cs = False
    for j in range(len(lst)):
        if canstart(lst[j],texts[i])[0]: cs = True
    if not cs: lst.append(texts[i])

# print the unique possible decrypts, they must be solved as substitution ciphers
for i,j in enumerate(range(len(lst))):
    print lst[j]

No comments:

Post a Comment