Explanation of Progress

There has been a long research effort to understand exactly what causes isomorphs in ciphers, and to classify what kinds of ciphers are capable of producing them. Starting with ciphertext-autokey (CTAK), since this was a known classical method that consistently produces isomorphs, we tried to expand on this to find what generalizations of it work.

We determined that when we extend CTAK by making the structure of the cipher states form a mathematical group instead of just a cyclic alphabet, isomorphs stay consistent, and this also gave us a direct explanation for classical chaining conflicts, since non-commutative groups deterministically cause them.

Knowing that group structures could preserve isomorphs, we needed to understand how group structures work, and what structures could be applicable to the eyes, so we needed to study group theory.

Group theory is all about groups, how they are made, their properties, and how they relate to each other. Groups are sets with a binary operation that lets you combine two elements to make an element from the same set, with the requirements that the operation is associative, every element has an inverse, and there is an identity or neutral element that doesn't change other elements it's applied to. These requirements are technically all you need, but they aren't that useful for understanding what groups are, because groups can have all kinds of different structures.

The best way to understand group theory is to look at examples of groups, to make it less abstract. There are plenty of videos on youtube giving good introductions. The main properties we are interested in are the order of the group (how many elements it has), whether or not it's commutative (since only non-commutative structures make the kinds of chaining conflicts we see), and what its subgroups are like.

The first group-based cipher we looked at was directly extending CTAK, since CTAK can be thought of as having each letter of the CT alphabet as an element of a cyclic group. Each PT letter acts on the group by rotating the cyclic alphabet by some amount cumulatively. Instead we just put the CT alphabet in correspondence with elements of some other finite group, and again have the PT letters act by elements of that group cumulatively. We call this group ciphertext-autokey (GCTAK). GCTAK makes for a good test example, since it produces isomorphs, can avoid doubles, and has chaining conflicts. However, it does not fit the eyes because the requirement that the number of group elements is equal to the size of the CT alphabet would require a group with 83 elements, and there is only one of those, and it is cyclic. The other thing is that GCTAK does not support hidden states.

The next step of the exploration was to extend GCTAK in a way that allowed for hidden states. The way we did this was essentially asking "what if some elements of the state group were indistinguishable from the CT output alone"? We found that one way to do this in a consistent way was to choose a group that is some multiple of the number of CT symbols we want to use, and choose some hidden subgroup such that the order of the group divided by the order of the subgroup is equal to the CT alphabet size. This corresponds to assigning a CT symbol to each coset of the hidden subgroup in the state group, and makes several states indistinguishable, giving us the hidden state behavior. The state update still happens cumulatively in the same way, but now the hidden states make it harder to tell what the exact state is unless we follow along with the state updates over the course of the message being encrypted. We call this cipher group autokey (GAK). It has been mathematically proven in general that GAK ciphers produce consistent (perfect) isomorphs, and that you can assign group elements to PT letters in a way that prevents doubles and is uniquely reversible (by not picking an element from the hidden subgroup, and by having at most one representative of each coset).

A small example of GAK that might make it make more sense is this: Imagine you have a cube with a letter on each face. Each plaintext letter causes the cube to rotate in some specific way, and then the CT output is the letter visible on the top face of the cube. In this example, the state group size is 24 since there are 24 different ways to orient a cube, the size of the CT alphabet is 6 (one letter for each face of the cube), and the hidden subgroup size is 4, because when a letter is output, it can have any of 4 different rotations which affect what the following outputs will be, even following the same rotation sequence. These rotations are not displayed in the output, so the rotation state of the letter is hidden, hence hidden state.

While GCTAK didn't end up being relevant to the eyes, GAK could be. This cipher fits the properties of the eyes very well. So the next question was "if the eyes were GAK, what groups are possible?"

We knew right away that the order of the group would need to be a multiple of 83, but there was a stronger restriction that applies to all GAK ciphers: The action of the group on the set of CT symbols has to be transitive. This means that every CT symbol is reachable from every other one, basically (not necessarily in one letter, but from some combination of letters combining into one group element). There's also some amount of evidence of this in the eyes, since the isomorphs in the eyes cover almost all CT symbols. Well, it turns out it's a known result how many transitive groups there are acting on relatively small numbers of objects, and for 83 there are exactly 6 groups possible for GAK. So we looked into these groups and attempted to narrow down which of them could fit the eyes.

These 6 groups are:

• $C_{83}$, a cyclic group, equivalent to standard CTAK with 83 CT symbols, which we already ruled out since it can't produce chaining conflicts
• $D_{166}$, a dihedral group, with 2 hidden states, directly ruled out using the main isomorphs in the first 3 messages, based on implied orders of non-commuting elements
• $C_{83}:C_{82}$ and $C_{83}:C_{41}$, an affine general linear group (AGL) and one of its subgroups, with 82 or 41 hidden states, tentatively ruled out based on isomorphs in the last 3 messages
• $S_{83}$ and $A_{83}$, all permutations of 83 symbols and its subgroup of even permutations, which haven't been ruled out and are kind of the worst case scenario here that we're left with if the other ones were ruled out

One way to think of a GAK cipher using S83 as the group is to have the state be an 83-card deck, where each PT letter causes a specific shuffle (permutation) of the cards, and the top card of the deck is output as the CT at each step. We call this a "deck cipher", not to be confused with other existing deck-based ciphers which aren't related and don't produce isomorphs.

Being an instance of GAK, this deck cipher produces consistent isomorphs, can avoid doubles as long as you choose shuffles which don't leave the top card unchanged, and naturally produces a CT with an even distribution of 83 symbols, assuming the shuffles are chosen in a way which mixes the deck well enough (and most choices do).

It was demonstrated experimentally that the differing message starts followed by shared sections are possible with deck ciphers because the unseen part of the deck can effectively act as a delayed hidden state. This wasn't possible with the other state groups unless the initial state differed for each message in a way that made them resync at the second character. It was also demonstrated that patterns matching the funny-looking obstacle and stutter section could be reproduced with carefully chosen plaintext.

The most recent development was showing that the shared sections after a differing first character are possible when all PT permutations differ from each other by a relatively small amount in terms of swaps applied to some chosen base permutation.

We have developed methods which extend chaining in a way that overcomes classical chaining conflict obstacles and have been able to successfully use this to fully solve GCTAK puzzles, and to partially solve simple GAK examples given enough isomorphs. However, we currently do not have any known algorithm for finding the PT -> group element mapping for GAK, and doing it with brute force is computationally infeasible due to the hidden states, even for small examples like ones with only two hidden states possible for each letter. Basically, we need a GAK attack, and any work on this would be much appreciated.

(The eyes are not guaranteed to be GAK, this is just a method that has been proven to fit all the required properties; the first method, really. It's possible that the eyes don't produce perfectly consistent isomorphs when plaintext is repeated. If that's the case, that would mean GAK doesn't fit. We can't prove that the isomorphs in the eyes are perfectly consistent without knowing the plaintext, we just know there are a lot of them that have the exact same repeat pattern, and the differences near the ends of them could be attributed to differences in plaintext indicating word boundaries, so it seems likely that they are consistent.)