This is the first post in a series of posts about block ciphers. From now on, I will try to produce more technical posts that involve more mathematics. This series of posts will be about symmetric encryption and related algorithms, but I do not have any plans in the immediate future of posting about public key encryption (I am preoccupied with block ciphers for the moment). Anyone who expects to understand this post should know the equivalent of a course in abstract algebra along with some basic knowledge about cryptography, but a group theory researcher who knows a little about symmetric cryptography would probably already know much of the content of this post.
Block ciphers are not only used to encrypt data, but they can also be used to produce cryptographic hash functions and cryptocurrency mining algorithms in different ways. In these posts, we will give special attention to using block ciphers as cryptocurrency mining algorithms similar to Circcash’s current mining algorithm Hashspin. Block ciphers like Hashspin’s block cipher with a 32 bit message space have different security requirements than block ciphers in general. For example, Hashspin’s block cipher requires a much lower level of computational security than a block cipher like AES. Furthermore, since Hashspin’s block cipher has a very small message space and round key space, there are ways to measure Hashspin’s level of cryptographic security that simply are too computationally costly to apply to block cipher’s like AES. On the other hand, Hashspin has a 1 bit long round key space, so block ciphers like Hashspin’s block cipher do not have too many round permutations to work with.
The only block ciphers that we will consider in this series of posts are the iterated round block ciphers where one encrypts a block of data by applying a round function with different round keys to that block of data.
Suppose that and are finite sets, and is a mapping. Suppose also that for each , we define a mapping by letting , and each is a permutation. Then we say that is the round map for some symmetric block cipher. It should be clear to anyone with a modest background in symmetric cryptography and group theory that the permutations need to generate either the symmetric group or the alternating group. This condition is necessary but not sufficient for security of a block cipher. The question of whether the permutations generate the symmetric group tell you that the block cipher can be made secure if you run it for enough rounds, but it may exponentially (in terms of the block size) many rounds to gain security.
For the rest of this post, we shall let denote a block cipher round function and denote the group generated by .
While it is necessary for to be the alternating or symmetric group of a secure block cipher, it may be very difficult to mathematically prove that is actually the alternating or symmetric group when is too large (when it is not too hard to calculate when or using facts I will refer to later in this post). A proof that or demonstrates that can be studied mathematically, but all cryptographers already expect that is the symmetric group or alternating group regardless of whether someone has mathematically proven this fact already.
I consider the question of whether or to be a sanity test that can and should be used to eliminate bad block ciphers mainly when is small but which can only rule out the most serious deficiencies of a block cipher.
Suppose that the round permutations generate the alternating group. Then as , the distribution of permutations where are selected from independently and uniformly at random approaches the uniform distribution on . More informally, if the round permutations generate the alternating group or symmetric group, then the block cipher is secure as long as it uses enough rounds of encryption and as long as the key scheduling algorithm is good enough.
Recall that a group is perfect if and only if it does not have an abelian quotient group with more than one element.
Observation: Suppose that is a finite perfect group generated by elements . Suppose that and for each . Consider the Markov chain where is the uniform distribution on and where . Then the Markov chain is irreducible and aperiodic, so the distribution converges to the uniform distribution on as
The alternating group is simple and hence perfect whenever , so the above observation applies to The group is not perfect, but the reader can make a similar observation for when .
Why generate instead of ?
Block ciphers must be quite efficient. It takes too much computation to compute an odd permutation, and constructing block ciphers using odd permutations does little to improve the security of the block cipher. Practical block ciphers are therefore constructed using only even round permutations. Let us go through some of the reasons why odd permutations are not efficient enough to use in block ciphers.
Observation: Suppose that where is even. Let be a permutation, and define a mapping by letting Then is an even permutation.
By the above observation, it is significantly more computationally intensive to produce an odd permutation on the collection of all bit long strings than it is to produce a corresponding even permutation (this is because any hardware that computes the procedure of performing the odd permutation may not ignore even one of the -bits).
Observation: Suppose that are sets where is a finite vector space of characteristic with . Let Define a permutation by letting . Then is always an even permutation.
The following observation is the closest way that I can think of for getting an odd permutation as a round permutation in a reasonable block cipher
Observation: Suppose that is a finite set and is a natural number. Let Define a permutation by letting . Then is an odd permutation if and only if is even and is odd.
If one were to design a block cipher based on ternary computation rather than binary computation or more generally based on arithmetic of odd prime characteristic, then such a block cipher will most likely contain odd permutations. The following observation shows that it is quite easy to produce odd permutations based on ternary computation.
Observation: Suppose that and is the permutation defined by . Then is an odd permutation.
In practice, since computation is binary, most block cipher encryption functions are always even permutations. Odd permutations are not only too slow to compute, but odd permutations do not do very much to add to the cryptographic security of a block cipher any more than even permutations do. Since has index in , and since every element in differs from an element in by just a transposition, one should consider to be a very good approximation to , and the level security of the block cipher where should be similar to the level of the security if we had instead.
In order for to be secure, must be the symmetric group or the alternating group because if , then will lack the multiple transitivity that is necessary in order for the block cipher round function to be secure. This lack of security of is bad enough so that any block cipher with round function will be insecure regardless of the number of rounds used.
Suppose that is a finite set. Then a group is said to be -transitive if whenever are elements where are distinct and are distinct, then there is some with for . A group is said to be transitive if it is -transitive.
The Mathieu groups are sporadic simple groups for . The Mathieu groups are all -transitive subgroups of . The groups are -transitive. The groups are -transitive.
Theorem: The only finite -transitive groups are (up-to-a permutation of ) the groups and the Mathieu groups .
If , then is not -transitive, and if is used as the round function for a block cipher, then whenever is a ciphertext, is a plaintext, and for where is the function for encrypting a block with key , then an adversary who only knows will know that is in the orbit of , and this information could possibly be used to gain information about . This cryptographic weakness persists regardless of how many rounds of encryption are used and regardless of the key scheduling algorithm that one uses.
All finite -transitive groups have been classified (there are infinite families of -transitive groups together with sporadic -transitive groups). Unsurprisingly, by going through this collection of -transitive groups, one should conclude that if is any -transitive group other than the symmetric or alternating groups, then is not suitable as a block cipher round function for any purpose other than perhaps an example of an insecure block cipher round function. One should also conclude that if is not -transitive, then should not be used as a block cipher round function. Therefore, a block cipher can only be secure if the group is the alternating or the symmetric group.
Most random permutations generate the alternating or symmetry group
It is quite easy to produce permutations that generate the alternating group or symmetric group. For example, suppose that are random elements of . Then there is a probability that generate either the alternating group or the symmetry group.
In most block ciphers, we would have , so it will be very likely for to be the alternating group or symmetric group, and it will be even more likely for to generate the alternating group or symmetric group since the block cipher is designed for security, and in order to ensure security, one must have or .
Testing whether or
When is small (for example, if ), then one can use the following results to test whether or . One can also use the following test to determine whether generates or for some subset .
Suppose that is an algebraic structure where is a bijective unary operation on for each and where if , then as well. Let be the group generated by . Then we say that the group is primitive if the action of on is transitive and the algebra is simple.
Theorem: (Camille Jordan) Let be a primitive permutation group on a finite set . Let be a prime with . If contains a -cycle, then is either the alternating group or the symmetric group.
Corollary: Let G be a transitive permutation group on a finite set . Let be a prime with and . If has a permutation that contains a cycle of length , then is either the symmetric group or alternating group on .
Let us now estimate the probability that a random permutation in or satisfies the above corollary to Jordan’s theorem.
Suppose and . Suppose that is selected uniformly at random, and is selected from or uniformly at random. Then it is not too hard to show that there is a probability that the cycle in containing the point has length .
The prime counting function is the function where is the number of prime numbers less than or equal to .
The prime number theorem states that
Therefore, as well, so there are approximately primes between and .
In particular, if and is a randomly selected element in and is a randomly selected element of or , then there is approximately a probability that a belongs to a cycle of length where is a prime number with .
Therefore, if we have established that the group is transitive and we want to show that is the alternating group or the symmetric group, then there is approximately a probability that for a uniformly randomly selected and uniformly randomly selected , the cycle in containing will satisfy the premises of the corollary to Jordan’s theorem (unless of course, was never the alternating group or the symmetric group in the first place). This indicates that as long as is not too large, it is generally too difficult to show that generates the alternating group or symmetric group. I was able to use this corollary to Jordan’s theorem to run a computer calculation to show that Hashspin’s round permutations do in fact generate the alternating group.
The round functions for DES and AES generate the alternating group.
Ralph Wernsdorf has written several papers in which he shows that the round permutations for DES and AES and other block ciphers like AES do in fact generate alternating groups; let me outline how Ralph Wernsdorf showed that the round permutations for AES generate the alternating group. More details of the proof can be found in the paper “The Round Functions of RIJNDAEL Generate the Alternating Group” by Wernsdorf.
The AES block cipher round function is the round function where is the function defined by letting where denote the MixColumns, ShiftRows, and ByteSub-transformations respectively. Here are bijective mappings and are linear over . Furthermore, for all where is the S-box permutation.
Observe that is transitive and only contains even permutations. To prove that is the alternating, we need to show that is -transitive, and then we need to apply the following theorem to establish that is alternating.
Definition and Theorem: The minimal degree of a finite group is the smallest order of an element . Suppose that is a -transitive group. Let be the minimal degree of . If then is either the alternating group or the symmetric group.
Lemma: Suppose that is an even permutation whenever . Then the mapping belongs to the group .
Proof outline: Observe that and . Therefore, the operations of the form are precisely the operations of the form , and the operations of the form are precisely the operations of the form
Now, let be the group of permutations of generated the permutations along with the mappings Then the group generated by the mappings of the form together with the mappings of the form is precisely the group of all permutations of the form where whenever . In particular, the group generated by together with the mappings of the form is isomorphic to . However, by applying the corollary to Jordan’s theorem, one can show that is actually the alternating group on the set . Q.E.D.
Lemma: The group is -transitive.
Proof outline: Since we already know that is transitive, to prove -transitivity, it suffices to show that the stablizer group is transitive on . By the above lemma, for all , there exists a permutation of the form such that where whenever and whenever . For , It is not to difficult to show using computer calculations that whenever , there is some such that these calculations apply the above lemma that gives one access to all functions of the form where each is an even permutation. This is enough to establish that is transitive on Q.E.D.
Theorem: The group is the alternating group on the set .
Proof outline: Since we have already established that every permutation in is even and is -transitive, it suffices to show that the minimal degree of is less than However, if is a 3-cycle, and is the identity permutation for , then by an above lemma, the mapping belongs to , but this mapping has order . Q.E.D.
I have been running computer experiments trying to obtain pairs of permutations that look like they can be round permutations from the same block cipher round function but where do not generate the alternating group or symmetric group and where or so. As you might expect, in most cases, would generate either the alternating group or the symmetric group or the reason that does not generate the alternating group would be immediately obvious. Here is an example of a function where do not generate the alternating group. I will let the reader attempt to find out why do not generate the alternating group.
Define an operation by letting . The operation is known as the ternary majority operation. Define an operation by letting precisely when
ii. , and
iii. for .
Let be the tuples where Let be the mapping defined by where addition is taken modulo . Define mappings where .
Then is neither the alternating group nor the symmetric group.
Cryptography problem: Why does the above pair of permutations not generate the alternating group or symmetric group? What is the group generated by the above pair of permutations? Feel free to use whatever software you would like to solve this cryptography problem.
In future posts, we shall develop some techniques that will help us solve this cryptography problem.