# Do groups generated by round functions generate the alternating group?

Let $$K,X$$ be sets and let $$F:K\times X\rightarrow X$$ be a function. For each $$k\in K$$, let $$f_{k}:X\rightarrow X$$ be the function where $$f_{k}(x)=F(k,x)$$ whenever $$k\in K,x\in X$$. Assume that each $$f_{k}$$ is a bijection.

Suppose that $$F$$ is the round function for some cryptographic function such as AES-128 or some cryptographic function.

If $$F$$ is a cryptographic function, then I do not expect for $$\{f_{k}\mid k\in K\}$$ to generate the full symmetric group $$S_{X}$$, but I would expect for $$\{f_{k}\mid k\in K\}$$ to generate the alternating group $$A_{X}$$ (let me know if there are any real-world examples where $$f_{k}$$ is an odd permutation). Has there been cases in cryptography where it was rigorously proven that $$\{f_{k}\mid k\in K\}$$ generates or does not generate the alternating group $$A_{X}$$? For example, if $$F$$ is the round function for AES-128 or DES, then does $$\{f_{k}|k\in K\}$$ generate the alternating group $$A_{X}$$?

I am mainly interested in the case where the functions $$f_{k}$$ are the round functions because this case will probably be easier to analyze and because if the functions $$f_{k}$$ are the round functions, then it is more likely that $$\{f_{k}\mid k\in K\}$$ generates the alternating group.

This problem may be intractible in most cases, but there may be cases where one can show that $$\{f_{k}\mid k\in K\}$$ generates the alternating group $$A_{X}$$ such as outdated or insecure cryptography or when the cryptography has a special form that makes it easier to analyze (such as Feistel ciphers) or even cryptographic algorithms that are designed for testing.

We say that a subgroup $$G$$ of the permutation group $$S_{X}$$ is $$n$$-transitive if whenever $$x_{1},\dots,x_{n}$$ are distinct elements in $$X$$ and $$y_{1},\dots,y_{n}$$ are distinct elements in $$X$$, then there is some $$g\in G$$ with $$g(x_{i})=y_{i}$$ whenever $$1\leq i\leq n$$.

Theorem: Suppose that $$X$$ is finite and $$|X|>24$$. If $$G$$ is a $$4$$-transitive subgroup of $$S_{X}$$, then either $$G=S_{X}$$ or $$G=A_{X}$$.

The above theorem may make it easier to prove that $$G=A_{X}$$.

If $$\{f_{k}\mid k\in K\}$$ does not generate the alternating group $$A_{X}$$, then I would reject any block cipher with round function $$F$$ as being horribly insecure since either $$|X|\leq 24$$ which is too small for any block cipher or the group generated by $$\{f_{k}\mid k\in K\}$$ is not 4-transitive.

However, if it is easy or tractible to prove that $$\{f_{k}\mid k\in K\}$$ generates the alternating group $$A_{X}$$, then the function $$F$$ may be too well behaved for cryptographic purposes.

• "let me know if there are any real-world examples where $f_k$ is an odd permutation"; several Format Preserving Encryption algorithms (which often is used with very short messages) use a round functions that may be odd - one example would be FF1 Jul 5, 2021 at 16:43

For example, if $$F$$ is the round function for AES-128 or DES, then does $$\{f_k | k \in K \}$$ generate the alternating group $$A_X$$?