Breaking the more complex ciphers
The Lighthouse Conspiracy › Forums › Bureau of Security and Signals Intelligence Forum › Breaking the more complex ciphers
 This topic has 6 replies, 3 voices, and was last updated 1 week, 2 days ago by madness.

AuthorPosts

13th November 2021 at 6:01 pm #68167Break_The_CipherParticipant
In trying to get a head start on the difficult ciphers before they come, I’ve reached a wall mostly in twostep encryption ciphers. I do think that I should also eventually make a script for the solitaire cipher because that could easily come up later, but it looked too confusing to make a decrypt script for.
I’m not really sure how to get past the substitution cipher encrypted with columnar transposition without waiting through an unreasonable amount of iterations. I’ve tried to create a substitution key through matching letter frequencies with the standard frequencies and then use tetragram fitness to decrypt the transposition, but the substitution key always seems to be greatly inaccurate. Does anyone know a way to break this? The ADFGVX cipher also has a similar problem, where I can use fitness for both keys, but it takes too many iterations to find a key for the Polybius square and the transposition.
13th November 2021 at 6:49 pm #68168madnessParticipant@Break_The_Cipher,
I dunno. I made a script to encipher and decipher in the solitaire cipher. The hard part is breaking it without knowing the key.For a substitution + transposition, it is easy to do the substitution part first, IF you know in advance that the substitution is a Caesar or affine cipher. For a general monoalphabetic substitution, you better hope that the transposition has few enough keys that you can try them all, then try to break the substitution for each one. Another approach is to try to match frequencies, then try to break the transposition, then go back and try to fix the substitution. I remember saying such a thing last year. But it’s very likely to fail.
I break ADFGX and ADFGVX by maximizing the index of coincidence in order to find the transposition key. If I find the correct key, then all that remains is a monoalphabetic substitution, which is easy to break. 6B from last year was one of these; it had only 6 possible transposition keys, so it was easy.
Here is an ADFGX ciphertext for you to practice with. Let’s call it “madness20215”.
XDAFGGDDAAFDADGADDFFAAAGFXAADDGDGDDDDDAFDFXFDXAFDDADAGFXADXDGADGAFDAFADGGFFXFAXD
DDDGDFDDFAAAGAFADXFFXADFGGFDDFAFXAAFXXAFXFFAGDAGADAADFXAGADGXXDAAFFDXXFXDFXDGFXA
GFGADXGDADDDAFAFXAFDXDDDAAFAAAFFXFAAAFAGGXDXXAAFFXXFDFXDAFFADXDFGXDFXFFFGFGFDXDA
FDDDAXXAXAFGFDDDGGFFXDDGFDDDDAXGFGADXFDGFXFXGDDFXDXGAFXXDAFFFXFGGDGAGGFAFFFAAFAX
DFDDXADDDDFFXGAFDAGFFXAAADDXGGXXAADADXGAGXDDAXGGDAGDFAAAAGXADGAXXAFFXFGDAFDFDXFD
FAAAAFXFDAAAXFAFAGDAXDADFAADGDFFXGFFDFGXAAXADAFFGXFXAFXXADAFADXXXGXXAFXDADGXXFDD
DAAFDGGAAAFAAXAGDXDAGDFADDFDXDFDFDADAFAAAAFFFXADGFXAAGAAAXFAFDXFFDGFXAGADXFDAAFD
DAXXGADAAFADAFFFXFADXDAXFFDXAFAXADDFXDFDADDDAAFAAGADGDAFDXAFDDAFDFDXFDGXFFAAGDXD
XXGXXAFADFXGADGGGGDDGAAFAADDDDDGFXFAADFFXAGXGAAFADDAXDDGFDXXAGAGDFDGADFAAXDDADDD
XDADDFADGAADGGXDDDDDFFXFDDADFFAFGAXFXFAAXGDGADAGDDXGXAXFDXDDFAAGDGGXGXXDDFGAFFAA
DDGFAFDFDAAXFFAAADGGFDFADGAFFDXDFFFADDGGDDADXDDDXXAGDDGDDAGAFFXAFFAGGFDAGADADDFX
DXDFGADGDAFDDAFDAAAADDGFFAXFFAXXADDFADDXFFDGAFAFGXGAGFGGGGFXDXDGGADFXFXXFXDADGAX
FDFXFFFADGDGGADAADDFFFDXADAGDDGFADAXFXADFADFGXGAADADDDGFFFDDAFDDXDDGXXDAAFFFXFFA
FGFGXDGFFDFFFDGFXXAGGDGDADGGGXXDDXGDDGAAXGFDFFXAFFGADADFFFXFFDXFAXFXFFADAFFDAFAF
DGGFGXGFGFFAGGDGFFFGAXDDXGDDADAXFFGFDAFDDFFFGAFAGGGDDDDFFGDDGFXDDFAGADAFDADFFAXX
GFXGFFDFDGFXGFGGXFDDFDXXXXADDFDFDGFGFXAFAFGADDAGDDDAAFXFGFGDFDGDADDXFDAGFFFDFFDG
GAFXGADXDDFGGFGFXFDADXGDDAFGDDAFDFFFFGXDDAFDDDGFAFFDGXDFXFADGXFFXDDFFFXAGGDADXGX
ADDXXDXFDDXADDDADGFGXAFFGFFGDAFAFFDDFDXGDXFAADXDFDDXGDDGDGGAAAGFFDGGAXXXAXDFFXFA
GGAXFGDDDAFXXDDDDXDGDADAGFDFDDFFDFAGGGFDADDAFDXDDFDFGGFFGGDGGGDGDDAFDAFFGGXGXDGX
GDFFFDFDDFXAGFDGDXXFXFDGGGFXDDGGFDXXFAXXDFFDFDDDGGFXADDGDGAGFDDFAXXFGXGDGDDAFADD
DGFDFDGFGF16th November 2021 at 10:11 am #68188Break_The_CipherParticipantI think I have an effective enough script which can find the text given the transposition keylength. It struggles to find the right keylength for this ciphertext though, is there an effective way to quickly check which keylengths are going to work? Also I’m not sure if it’s just my script but it seems the ioc gets higher and higher when the keylength is larger
18th November 2021 at 2:05 pm #68194Break_The_CipherParticipantOk it seems the script struggles to decrypt transposition with keylengths of around 20 or so, is there a way to make it more effective?
25th November 2021 at 5:04 pm #68330Break_The_CipherParticipantIt seems that the script gives different keys every time I run it, which means it runs into local maxima a lot. I’ve tried making it go through lots of iterations but it seems that hillclimbing is not enough to find an accurate transposition key. Is there a better way to find the key and get it out of the local maxima? I think simulated annealing would do a better job at finding the key, but I’m not sure.
26th November 2021 at 3:50 pm #68334sinkradParticipant@Break_The_Cipher, it is expected that hill climbing will find local maxima when the keylength you are looking for differs from the actual keylength. When you are trying transpositions of the correct keylength it is unlikely you will get stuck in a local maximum.
For testing whether the text might be encrypted with keylength n, I start by trying the following transpositions:
(1, 2, 3, .., n)
(2, 1, 3, .., n)
(2, 3, 1, .., n)
…
(2, 3, 4, .., 1)
That is, I try placing the first column in any other position of the matrix. When the keylength is correct at least one of these transpositions should put two columns that are adjacent in the actual key next to one another, which will result in a higher index of coincidence (ioc) for that transposition. For each possible keylength n I then compute the highest ioc over these n transpositions and the lowest ioc. Values of n for which the highest and lowest value differ strongly are likely candidates for the keylength.Applied to the example of madness and for (n = 1..14):
keylength: 3 – 0.00164
keylength: 4 – 0.00223
keylength: 5 – 0.00124
keylength: 6 – 0.00285
keylength: 7 – 0.00051
keylength: 8 – 0.00096
keylength: 9 – 0.00073
keylength: 10 – 0.00087
keylength: 11 – 0.00079
keylength: 12 – 0.0012
keylength: 13 – 0.00084
keylength: 14 – 0.00108The largest improvements are found with keylength 6, 4, 3, 12 (in that order). For this data set 6 is indeed the correct keylength. 12 probably gets a good score since it is a multiple of six.
The difficulty here is that 6 is not a multiple of the text length and therefore additional steps are required when placing the text in a matrix. Possibly something went wrong in that step. The easiest way to debug your code is to encrypt a known text with a known key and see whether your algorithm is capable of retrieving that key. Best to start simple with a keylength that divides the length of your text and then advance to the harder case of a keylength that is not a divider of the text length.
26th November 2021 at 3:50 pm #68344madnessParticipantThe professionals have trouble with permutations > 15, so I doubt you are able to do 20.
Anyway, you have to find a way to deal with multiple maxima.
BTW, simulated annealing is just another approach to hill climbing. I prefer to use a constant temperature, since the maxima are generally very steep.
26th November 2021 at 3:50 pm #68346madnessParticipantThe Vigenere cipher is so easy to break because it is highly constrained. Furthermore, a text that is doubly encrypted, where the second encryption is a Vigenere, can usually be broken. This is the fatal flaw of the Quagmire I cipher, which is equivalent to a monoalphabetic substitution followed by a Vigenere.

AuthorPosts
 You must be logged in to reply to this topic.