Do the round maps of your block cipher generate the alternating or symmetric group?

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 $K$ and $X$ are finite sets, and $F:K\times X\rightarrow X$ is a mapping. Suppose also that for each $k\in K$ , we define a mapping $F_{k}:X\rightarrow X$ by letting $F_k(x)=F(k,x)$ , and each $F_k$ is a permutation. Then we say that $F$ 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 $\{F_k\mid k\in K\}$ 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 $\{F_k\mid k\in K\}$ 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 $F:K\times X\rightarrow X$ denote a block cipher round function and $G$ denote the group generated by $\{F_k\mid k\in K\}$ .

While it is necessary for $G$ to be the alternating or symmetric group of a secure block cipher, it may be very difficult to mathematically prove that $G$ is actually the alternating or symmetric group when $|X|$ is too large (when $|X|\leq 2^{32}$ it is not too hard to calculate when $G=A_{X}$ or $G=S_{X}$ using facts I will refer to later in this post). A proof that $G=A_X$ or $G=S_X$ demonstrates that $F$ can be studied mathematically, but all cryptographers already expect that $G$ is the symmetric group or alternating group regardless of whether someone has mathematically proven this fact already.

I consider the question of whether $G=A_X$ or $G=S_X$ to be a sanity test that can and should be used to eliminate bad block ciphers mainly when $|X|$ is small but which can only rule out the most serious deficiencies of a block cipher.

Markov ciphers

Suppose that the round permutations $\{F_{k}\mid k\in K\}$ generate the alternating group. Then as $n\rightarrow\infty$ , the distribution of permutations $F_{k_{1}}\circ\dots\circ F_{k_{n}}$ where $k_{1},\dots,k_{n}$ are selected from $K$ independently and uniformly at random approaches the uniform distribution on $A_{X}$ . 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 $G$ is perfect if and only if it does not have an abelian quotient group with more than one element.

Observation: Suppose that $G$ is a finite perfect group generated by elements $g_{1},\dots,g_{n}$ . Suppose that $p_{1}+\dots+p_{n}=1$ and $p_{i}>0$ for each $i$ . Consider the Markov chain $(\mathcal{X}_{n})_{n}$ where $\mathcal{X}_{0}$ is the uniform distribution on $G$ and where $P(\mathcal{X}_{r+1}=g_{i}\mathcal{X}_{r})=p_{i}$ . Then the Markov chain $(\mathcal{X}_{n})_{n}$ is irreducible and aperiodic, so the distribution $(\mathcal{X}_{0},\mathcal{X}_{n})$ converges to the uniform distribution on $G\times G$ as $n\rightarrow\infty.$

The alternating group $A_{X}$ is simple and hence perfect whenever $|X|\geq 5$ , so the above observation applies to $A_{X}.$ The group $S_{X}$ is not perfect, but the reader can make a similar observation for when $G=S_{X}$ .

Why generate $A_X$ instead of $S_X$ ?

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 $X=A\times B$ where $|A|$ is even. Let $g:B\rightarrow B$ be a permutation, and define a mapping $f:A\times B\rightarrow A\times B$ by letting $f(a,b)=(a,g(b)).$ Then $f$ is an even permutation.

By the above observation, it is significantly more computationally intensive to produce an odd permutation on the collection of all $n$ 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 $n$ -bits).

Observation: Suppose that $X,Y$ are sets where $Y$ is a finite vector space of characteristic $2$ with $|Y|>2$ . Let $f:X\rightarrow Y.$ Define a permutation $L:X\times Y\rightarrow X\times Y$ by letting $L(x,y)=(x,f(x)\oplus y)$ . Then $L$ 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 $X$ is a finite set and $n$ is a natural number. Let $f:X\rightarrow\mathbb{Z}_{n}.$ Define a permutation $L:X\times\mathbb{Z}_{n}\rightarrow X\times\mathbb{Z}_{n}$ by letting $L(x,z)=(x,f(x)+z)$ . Then $L$ is an odd permutation if and only if $n$ is even and $\sum_{x\in X}f(x)$ 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 $X=\mathbb{Z}_{3}^{n}$ and $f:X\rightarrow X$ is the permutation defined by $f(x_1,\dots,x_n)=(x_1+1,\dots,x_n)$ . Then $f$ 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 $A_{X}$ has index $2$ in $S_{X}$ , and since every element in $A_{X}$ differs from an element in $S_{X}$ by just a transposition, one should consider $A_{X}$ to be a very good approximation to $S_{X}$ , and the level security of the block cipher $F$ where $G=A_{X}$ should be similar to the level of the security if we had $G=S_{X}$ instead.

Transitive groups

In order for $F$ to be secure, $G$ must be the symmetric group or the alternating group because if $G\not\in\{A_{X},S_{X}\}$ , then $G$ will lack the multiple transitivity that is necessary in order for the block cipher round function $F$ to be secure. This lack of security of $F$ is bad enough so that any block cipher with round function $F$ will be insecure regardless of the number of rounds used.

Suppose that $X$ is a finite set. Then a group $N\subseteq S_X$ is said to be $k$ -transitive if whenever $x_1,\dots,x_k,y_1,\dots,y_k\in X$ are elements where $x_1,\dots,x_k$ are distinct and $y_1,\dots,y_k$ are distinct, then there is some $g\in N$ with $g(x_i)=y_i$ for $1\leq i\leq k$ . A group $N$ is said to be transitive if it is $1$ -transitive.

The Mathieu groups are $5$ sporadic simple groups $M_{n}$ for $n\in\{11,12,22,23,24\}$ . The Mathieu groups are all $3$ -transitive subgroups of $S_{n}$ . The groups $M_{12},M_{24}$ are $5$ -transitive. The groups $M_{11},M_{23}$ are $4$ -transitive.

Theorem: The only finite $4$ -transitive groups are (up-to-a permutation of $X$ ) the groups $A_X,S_X$ and the Mathieu groups $M_{24},M_{23},M_{12},M_{11}$ .

If $G\not\in\{A_X,S_X\}$ , then $G$ is not $4$ -transitive, and if $F$ is used as the round function for a block cipher, then whenever $c=(c_{1},\dots,c_{4})$ is a ciphertext, $p=(p_{1},\dots,p_{4})$ is a plaintext, and $e_{k}(p_{i})=c_{i}$ for $i\in\{1,2,3,4\}$ where $e_{k}$ is the function for encrypting a block with key $k$ , then an adversary who only knows $c$ will know that $p$ is in the orbit of $c$ , and this information could possibly be used to gain information about $p$ . 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 $2$ -transitive groups have been classified (there are $8$ infinite families of $2$ -transitive groups together with $10$ sporadic $2$ -transitive groups). Unsurprisingly, by going through this collection of $2$ -transitive groups, one should conclude that if $G$ is any $2$ -transitive group other than the symmetric or alternating groups, then $F$ 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 $G$ is not $2$ -transitive, then $F$ should not be used as a block cipher round function. Therefore, a block cipher can only be secure if the group $G$ 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 $f,g$ are random elements of $S_n$ . Then there is a $1-n^{-1}+o(n^{-2})$ probability that $f,g$ generate either the alternating group or the symmetry group.

In most block ciphers, we would have $|K|>>2$ , so it will be very likely for $G$ to be the alternating group or symmetric group, and it will be even more likely for $G$ to generate the alternating group or symmetric group since the block cipher $F$ is designed for security, and in order to ensure security, one must have $G=A_{X}$ or $G=S_{X}$ .

Testing whether $G=A_X$ or $G=S_X$

When $|X|$ is small (for example, if $|X|\leq 2^{32}$ ), then one can use the following results to test whether $G=A_X$ or $G=S_X$ . One can also use the following test to determine whether $\{f_{h}\mid h\in H\}$ generates $A_{X}$ or $S_{X}$ for some subset $H\subseteq K$ .

Suppose that $(X,(u)_{u\in\mathcal{U}})$ is an algebraic structure where $u$ is a bijective unary operation on $X$ for each $u\in\mathcal{U}$ and where if $u\in\mathcal{U}$ , then $u^{-1}\in\mathcal{U}$ as well. Let $G$ be the group generated by $\mathcal{U}$ . Then we say that the group $G$ is primitive if the action of $G$ on $X$ is transitive and the algebra $(X,(u)_{u\in\mathcal{U}})$ is simple.

Theorem: (Camille Jordan) Let $G$ be a primitive permutation group on a finite set $X$ . Let $p$ be a prime with $p\leq |X|-3$ . If $G$ contains a $p$ -cycle, then $G$ is either the alternating group or the symmetric group.

Corollary: Let G be a transitive permutation group on a finite set $X$ . Let $p$ be a prime with $\frac{|X|}{2}<p$ and $p<|X|-2$ . If $G$ has a permutation that contains a cycle of length $p$ , then $G$ is either the symmetric group or alternating group on $X$ .

Let us now estimate the probability that a random permutation in $A_{n}$ or $S_{n}$ satisfies the above corollary to Jordan’s theorem.

Suppose $|X|=n$ and $1\leq k\leq n-2$ . Suppose that $a\in X$ is selected uniformly at random, and $f$ is selected from $S_{n}$ or $A_{n}$ uniformly at random. Then it is not too hard to show that there is a $\frac{1}{n}$ probability that the cycle in $f$ containing the point $a$ has length $k$ .

The prime counting function $\pi$ is the function where $\pi(n)$ is the number of prime numbers less than or equal to $n$ .

The prime number theorem states that

$\lim_{n\rightarrow\infty}\frac{\pi(n)}{n/\ln(n)}=1$ .

Therefore, $\lim_{n\rightarrow\infty}\frac{\pi(2n)-\pi(n)}{n/\ln(n)}=1$ as well, so there are approximately $n/\ln(n)$ primes between $n$ and $2n$ .

In particular, if $|X|=n$ and $a$ is a randomly selected element in $X$ and $f$ is a randomly selected element of $A_n$ or $S_n$ , then there is approximately a $\frac{1}{2\ln(n)}$ probability that a belongs to a cycle of length $p$ where $p$ is a prime number with $n/2<p<n-2$ .

Therefore, if we have established that the group $G\subseteq S_{X}$ is transitive and we want to show that $G$ is the alternating group or the symmetric group, then there is approximately a $\frac{1}{2\ln(n)}$ probability that for a uniformly randomly selected $g\in G$ and uniformly randomly selected $a\in G$ , the cycle in $g$ containing $a$ will satisfy the premises of the corollary to Jordan’s theorem (unless of course, $G$ was never the alternating group or the symmetric group in the first place). This indicates that as long as $n$ is not too large, it is generally too difficult to show that $G$ 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 $F:K\times X\rightarrow X$ where $K=X=F_{256}^{16}$ is the function defined by letting $F(k,x)=k\oplus mc(rs(s(x)))$ where $mc,rs,s$ denote the MixColumns, ShiftRows, and ByteSub-transformations respectively. Here $mc,rs,s:F_{256}^{16}\rightarrow F_{256}^{16}$ are bijective mappings and $mc,rs$ are linear over $F_{2}$ . Furthermore, $s((x_{i})_{i=0}^{15})=(S(x_{i}))_{i=0}^{15}$ for all $(x_{i})_{i=0}^{15}\in F_{256}^{16}$ where $S:F_{256}\rightarrow F_{256}$ is the S-box permutation.

Observe that $G$ is transitive and only contains even permutations. To prove that $G$ is the alternating, we need to show that $G$ is $2$ -transitive, and then we need to apply the following theorem to establish that $G$ is alternating.

Definition and Theorem: The minimal degree of a finite group $G$ is the smallest order of an element $g\in G\setminus\{e\}$ . Suppose that $G\subseteq S_{X}$ is a $2$ -transitive group. Let $m$ be the minimal degree of $G$ . If $m<\frac{|X|}{3}-\frac{2\sqrt{|X|}}{3},$ then $G$ is either the alternating group or the symmetric group.

Lemma: Suppose that $P_{i}:F_{256}\rightarrow F_{256}$ is an even permutation whenever $0\leq i<16$ . Then the mapping $(x_{i})_{i=0}^{15}\mapsto(P_{i}(x_{i}))_{i=0}^{15}$ belongs to the group $G$ .

Proof outline: Observe that $F_{j}\circ F_{k}^{-1}(x)=j\oplus mc(rs(s(F_{k}^{-1}(x))))=j\oplus k\oplus x$ and $F_{j}^{-1}\circ F_{k}(x)=s^{-1}[(rs^{-1}\circ mc^{-1})(j\oplus k)\oplus s(x)]$ . Therefore, the operations of the form $F_{j}\circ F_{k}^{-1}$ are precisely the operations of the form $x\mapsto l\oplus x$ , and the operations of the form $F_{j}^{-1}\circ F_{k}$ are precisely the operations of the form $x\mapsto s^{-1}[l\oplus s(x)].$

Now, let $H$ be the group of permutations of $F_{256}$ generated the permutations $x\mapsto l\oplus x$ along with the mappings $x\mapsto S^{-1}[l\oplus S(x)].$ Then the group generated by the mappings of the form $F_{j}\circ F_{k}^{-1}$ together with the mappings of the form $F_{j}^{-1}\circ F_{k}$ is precisely the group of all permutations of the form $(x_{i})_{i=0}^{15}\mapsto(h_{i}(x_{i}))_{i=0}^{15}$ where $h_{i}\in H$ whenever $0\leq i<16$ . In particular, the group generated by $F_{j}\circ F_{k}^{-1}$ together with the mappings of the form $F_{j}^{-1}\circ F_{k}$ is isomorphic to $H^{16}$ . However, by applying the corollary to Jordan’s theorem, one can show that $H$ is actually the alternating group on the set $F_{256}$ . Q.E.D.

Lemma: The group $G$ is $2$ -transitive.

Proof outline: Since we already know that $G$ is transitive, to prove $2$ -transitivity, it suffices to show that the stablizer group $G_{0}=\{g\in G\mid g(0)=0\}$ is transitive on $F_{256}^{16}\setminus\{0\}$ . By the above lemma, for all $c\in F_{256}\setminus\{0\},x\in F_{256}^{16}\setminus\{\mathbf{0}\}$ , there exists a permutation $g\in G_{0}$ of $F_{256}^{16}$ the form $(x_{i})_{i=0}^{15}\mapsto(P_{i}(x_{i}))_{i=0}^{15}$ such that $g((x_{i})_{i=0}^{15})=(c_{i})_{i=0}^{15}$ where $c_{i}=0$ whenever $x_{i}=0$ and $c_{i}=c$ whenever $x_{i}\neq 0$ . For $c\in F_{256}\setminus\{0\}$ , It is not to difficult to show using computer calculations that whenever $(c_{i})_{i=0}^{15}\in\{0,c\}^{16}\setminus\{\mathbf{0}\}$ , there is some $g\in G_{0}$ such that $g((c_{i})_{i=0}^{15})=(c)_{i=0}^{15};$ these calculations apply the above lemma that gives one access to all functions of the form $(x_{i})_{i=0}^{15}\mapsto(P_{i}(x_{i}))_{i=0}^{15}$ where each $P_{i}$ is an even permutation. This is enough to establish that $G_{0}$ is transitive on $F_{256}^{16}\setminus\{\mathbf{0}\}.$ Q.E.D.

Theorem: The group $G$ is the alternating group on the set $F_{256}^{16}$ .

Proof outline: Since we have already established that every permutation in $G$ is even and $G$ is $2$ -transitive, it suffices to show that the minimal degree of $G$ is less than $\frac{2^{256}}{3}-\frac{2\cdot 2^{128}}{3}.$ However, if $P_{0}:F_{256}\rightarrow F_{256}$ is a 3-cycle, and $P_{i}:F_{256}\rightarrow F_{256}$ is the identity permutation for $0<i<16$ , then by an above lemma, the mapping $(x_{i})_{i=0}^{15}\mapsto(P_{i}(x_{i}))_{i=0}^{15}$ belongs to $G$ , but this mapping has order $3$ . Q.E.D.

Experimentation

I have been running computer experiments trying to obtain pairs of permutations $F_{0},F_{1}:X\rightarrow X$ that look like they can be round permutations from the same block cipher round function but where $F_{0},F_{1}:X\rightarrow X$ do not generate the alternating group or symmetric group and where $|X|=2^{16}$ or so. As you might expect, in most cases, $F_{0},F_{1}$ would generate either the alternating group or the symmetric group or the reason that $F_{0},F_{1}$ does not generate the alternating group would be immediately obvious. Here is an example of a function $F$ where $F_{0},F_{1}$ do not generate the alternating group. I will let the reader attempt to find out why $F_{0},F_{1}$ do not generate the alternating group.

Define an operation $m:\{0,1\}^{3}\rightarrow\{0,1\}$ by letting $m(x,y,z)=(x\wedge y)\vee(x\wedge z)\vee(y\wedge z)$ . The operation $m$ is known as the ternary majority operation. Define an operation $P:\{0,1\}^{16}\rightarrow\{0,1\}^{16}$ by letting $P((x_{i})_{i=1}^{16})=(y_{i})_{i=1}^{16}$ precisely when

i. $y_{12}=x_{12}\oplus x_{3}\oplus x_{7}\oplus x_{11}\oplus x_{15},$

ii. $y_{2}=x_{2}\oplus m(x_{6},x_{10},x_{14})$ , and

iii. $x_{i}=y_{i}$ for $i\not\in\{2,12\}$ .

Let $c_{0},c_{1}\in\{0,1\}^{16}$ be the tuples where $c_{0}=(0,\dots,0),c_{1}=(1,0,0,\dots,0).$ Let $S:\{0,1\}^{16}\rightarrow\{0,1\}^{16}$ be the mapping defined by $S((x_{i})_{i})=(x_{i+1})_{i}$ where addition $+$ is taken modulo $16$ . Define mappings $F_{0},F_{1}$ where $F_{i}(\mathbf{x})=c_{i}\oplus S(P(\mathbf{x}))$ .

Then $\langle F_{0},F_{1}\rangle$ 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.

Markov ciphers

Why generate instead of ?

Transitive groups

Most random permutations generate the alternating or symmetry group

Testing whether or

The round functions for DES and AES generate the alternating group.

Experimentation

Share this:

Like this:

Leave a Reply Cancel reply

Why generate $A_X$ instead of $S_X$ ?

Testing whether $G=A_X$ or $G=S_X$