-
Notifications
You must be signed in to change notification settings - Fork 0
Alphabet Chaining
Alphabet chaining is a process that lets you use isomorphs to deduce the structure and ordering of the ciphertext alphabet. For each pair of isomorphs, there is some transformation between their underlying states, and if the states form a group, this group can be determined (at least partially) by looking at what kinds of transformations occur between isomorphs. Some information about the transformation which maps between the two states can be found by looking at how ciphertext symbols transform, for each pair of symbols in the isomorph pair.
The general steps involved in alphabet chaining are:
- Identify isomorphs in the ciphertext, making the assumption that those isomorphs represent repeated plaintext
- Create chains for pairs of isomorphs, each link in the chain giving the transformation from a letter of one isomorph to a letter of the other in the same place
- Use the chains to place letters in the ciphertext alphabet (this is the part which is the hardest to explain because there are many ways to do it)
- Once the ciphertext alphabet is complete, take deltas in it to convert the puzzle into a substitution cipher which can be more easily solved
I'll explain the process by showing how it can be used to solve a simple ciphertext-autokey (CTAK) cipher. Consider the following ciphertext:
RATNXKGJOTBWULWWVORAIHBRLXPCHWKIVKKJMRWCAKXWEMCSGDRGGFUFLOENRRLQOYSLRKQTYGXZFXBT
The first step of alphabet chaining is to identify isomorphs in the ciphertext. Higher confidence isomorphs which are clearly visible are the best choice for this, because any incorrect assumptions about sequences of text being isomorphic while the underlying plaintext is different will lead to contradictions (chaining conflicts). In a pinch, lower confidence ones with fewer repeats can be used if there is good reason to believe the plaintext will be the same (like known plaintext, or maybe matching word lengths if spaces are available, but you could guess wrong). In this example text, you can find a pattern A......A.B..BB which is repeated 3 times, with the following isomorphs:
A......A.B..BB
TNXKGJOTBWULWW
HBRLXPCHWKIVKK
CAKXWEMCSGDRGG
Given a pair of isomorphs, the next step is to build chains. When the isomorphs are aligned so that the repeat pattern is in the same columns (as shown above), each link of the chain is built by looking at the pair of letters in a column, ignoring duplicates. Each pair of isomorphs can be used to create a different set of chains. For the three above, we have three pairs. I'll label the transformations between the pairs of rows here as a = 1
a (1 -> 2): TH, NB, XR, KL, GX, JP, OC, BW, WK, UI, LV
b (1 -> 3): TC, NA, XK, KX, GW, JE, OM, BS, WG, UD, LR
c (2 -> 3): HC, BA, RK, LX, XW, PE, CM, WS, KG, ID, VR
Then within each isomorph pair, we can combine these links into longer chains if the starting letter of one chain is the ending letter of the other, or vice versa. For example, NB and BW combine to make NBW, and XR and GX combine to make GXR. After doing this as much as we can, we get the following chains:
a (1 -> 2): TH, NBWKLV, GXR, JP, OC, UI
b (1 -> 3): TC, NA, XKX, GWG, JE, OM, BS, UD, LR
c (2 -> 3): HCM, BA, VRKG, LXWS, PE, ID
One of the most important things to look for when building chains is cycles. In CTAK and GCTAK, the presence of a single cycle means that all of the chains for that isomorph pair will form cycles of the same length. In b above, we have two 2-cycles, XKX and GWG, so all of the other letters could be assumed to be in 2-cycles as well in this case. For a and c, we don't see any cycles yet, so we don't know how long those chains will get before forming cycles.
Classically, for solving a CTAK cipher with CT alphabet size n, this is done by assuming that each transformation between isomorphs corresponds to some linear shift amount mod n, and attempting to place the letters in the alphabet according to that shift amount in a way that is consistent. Since any offset and decimation of the alphabet will give a decryption equivalent up to substitution, the shift amount for the first pair of isomorphs can usually be assumed to be 1 for convenience, and that will work unless the shift is actually a factor of the CT alphabet size.
So for the example, we can assume we have a = 1 and try to determine where the letters will be placed. We know that these chains have letters which are adjacent in the alphabet, but we don't know where they are placed relative to each other. If we look at the b chains, we can place them vertically to indicate an unknown shift between the two (even though the shift might be obvious with the 2-cycles, since it's just half the alphabet size). So with how I'm writing this, empty space means unknown placement of fragments of the alphabet, adjacent means offset by a in the alphabet, and vertically adjacent means offset by b in the alphabet. (This is an example of vector chaining.)
I'll just show what happens with the first large chain first. We have NBWKLV horizontally and NA, BS, WG, KX, LR vertically. GXR is already a chain for a, so it's a good sign that we see that it's still consistent with the letters that were placed using b (specifically, as transformations, a and b commute). Since we see ASGXR, this means we've extended the chains for a to include this.
NBWKLV
ASGXR
We can do the same thing with other chains from a and b to fill out as much of the alphabet structure as we can, keeping in mind the vertical offset is the shift from b, which cycles between the two rows since it makes 2-cycles. The disconnected sections here have unknown offset and placement from each other, they are not necessarily in the order shown.
NBWKLV MTH JP UI
ASGXR OC E D
Next we could consider the chains from c, but in this case they don't actually add any new information. The shift from c corresponds to -a + b, which makes sense when you think about it in terms of changes between isomorphs (if we apply -a, we change isomorph 2 into isomorph 1, then if we apply change b, we change isomorph 1 into isomorph 3, so overall this changes isomorph 2 to isomorph 3). The transformations for b happened to be more useful because they formed 2-cycles.
Anyway, we have not filled out the full alphabet here or connected all the pieces together, which is an issue with using very short ciphertext like this as an example.
There's also another isomorph which partially fits this pattern, without the double at the end. Let's create chains between the 3rd isomorph and this one, and call the shift between them d. Do not include the non-isomorphic part after the end of the pattern, because that will cause a direct conflict. The text no longer being isomorphic at that point is direct evidence that the underlying plaintext changes.
A......A.B..B
CAKXWEMCSGDRGG
YSLRKQTYGXZFX
d (3 -> 4*): CY ASGXRF KL WK EQ MT DZ
Since d contains the ASGXR chain we already found for a, the transformations for a and d are the same and the chains can be merged. After merging them, we get these chains for a/d:
a = d: MTH, NBWKLV, ASGXRF, JP, OCY, UI, EQ, DZ
NBWKLV MTH JP UI
ASGXRF OCY EQ DZ
This fills out all the letters A-Z, but we actually still don't know where these fragments should be placed. When more text is available, this isn't as likely to be an issue, but that's what I get for using such a short example. If the ciphertext alphabet is not chosen randomly but uses a keyed alphabet, you can attempt to find the keyed alphabet by choosing pairs of uncommon letters and decimating the alphabet to make them have the right distance. For example, JK, PQ, VWXYZ, these are rare letters, so if you see a pair of them in a chain, you can try placing the disconnected chains in a place that makes them continue the pattern, possibly with missing letters that are in the key.
We see VW in a chain, so we can try -3 decimation. This also corresponds to FG and RS in the other long chain, so it looks correct. The expected letter after W would be X before N, but it doesn't fit here since it's not at the end of a chain, but we can place Y here and Z after another -3 steps, to combine most of the chains together. JK is also at a distance of -3 if placed here, so we can attach it and close the gap, completing 2 13-letter chains:
DZOCYNBWKLVJP
UIMTHASGXRFEQ
The vertical shift here corresponds to an offset of 13, based on the 2-cycles in the 26 letter alphabet. You can also see UV, IJ, and MP when looking in steps of -3 between the two strings. So this is the full 26-letter alphabet:
DZOCYNBWKLVJPUIMTHASGXRFEQ
Then apply the decimation by -3:
DFGHIJKNOQRSTUVWYZEXAMPLBC
So we can see the keyword here was "example". However, the starting position of the alphabet may not be here or at the start of the keyword. Now that the ciphertext alphabet has been obtained by this alphabet chaining process, we can take deltas using this alphabet to convert the cipher into a substitution cipher. We did not even need to apply the decimation to be able to do this, and would get a substitution using any decimation and shift of the ciphertext alphabet obtained by this process.
By "deltas", consider the first two letters of the ciphertext, RA. The index of R in the alphabet above is 10, and the index of A is 20, so the delta is 20 - 10 = 10. Note that the deltas are taken mod alphabet size. Since the first letter has no previous letter, it uses the initial state of the cipher. A cipher like this could also use an initial key, but I prefer to just use an initial state of the identity (or a value of 0 here). The sequence of deltas will become a substitution of the plaintext, but if you use the correct starting point for the alphabet, you can take deltas and index the same alphabet with them to get the plaintext directly. You can also index into a different plaintext alphabet and get a substitution in the same way.
If you use the alphabet starting with the key at the beginning, and index the deltas into the same alphabet, you get this sequence, which is a substitution of the plaintext:
EXAMPLBCDFGHIJKNOQRSTUVWYZ
RGRUIJVMMPIQYGREZTAGGZUIJVMMPIQYGREZONLGUIJVMMPIQYGREZIKVHGNMEJIZDUIJVMMPIQYGRLK
With the right choice of offset though, this alphabet causes deltas to directly decrypt to the plaintext:
OQRSTUVWYZEXAMPLBCDFGHIJKN
REDHAMISSTACKEDONGREENHAMISSTACKEDONBLUEHAMISSTACKEDONAPIXELSOMANYHAMISSTACKEDUP
Hopefully this example helps with understanding the general idea of alphabet chaining, though some parts of the process can vary. The key parts that will be the same are the main steps: Finding isomorphs, creating chains for pairs of them, combining those chains to place letters in the alphabet, and using the alphabet to take deltas, converting the cipher into a substitution.
The process of finding isomorphs and creating chains generally stays the same even in more complicated ciphers than CTAK, but the parts like combining chains and taking deltas can be very different.
For group ciphertext-autokey (GCTAK) ciphers, which use a more general state group than just the cyclic one used for CTAK, most of the chaining process is the same. The first difference is that in commutative groups, the alphabet structure may not be possible to express as a single line/cycle, which means you may have to expand it to multiple dimensions, e.g. a 5x5 grid for an alphabet of 25 rather than a line of 25. Each direction still acts like values mod n for some n, but you can have intersecting cycles with the same "distance" between letters with those distances going along different axes. Commutative groups can be chained using higher dimensional chaining like this consistently, and the deltas become vector deltas, again using the modulus in each dimension.
For non-commutative GCTAK ciphers, chaining still works, but if a pair of elements doesn't commute, then you won't be able to place the letters in a grid and treat them like vectors anymore. However, you can still treat the group structure as a whole as a graph, and this works, and is called graph chaining. This generalization of chaining still has the same general idea though, you place the letters in a way that makes the graph consistent and then use paths on the graph to take deltas to convert the puzzle into a substitution.
For the more general group autokey (GAK) ciphers, a generalization of chaining can still work for determining the structure of the group, but some of the things that we take for granted with chaining start to break down. For example, an element is not guaranteed to have all cycles formed be the same length anymore (the hidden state causes some cycles to repeat letters and end up appearing smaller), and overlap of an edge is not necessarily enough to say for sure that two elements are equal (the number of edges overlapping required to say for sure depends on the group). The generalization of chaining that appears to be working for GAK is geometric graph chaining, but it's still a work in progress, and it might actually be unrealistic to expect chaining to ever work for the eyes with how large the group appears to be relative to how little text we have available.