1
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ "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 $\endgroup$
    – poncho
    Jul 5 at 16:43
3
$\begingroup$

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$?

In the case of DES, then, yes it is known that the round function does generate the alternating group, as shown in this paper ("The One-Round Functions of the DES Generate the Alternating Group" by Ralph Wernsdorf).

I do not believe that any similar result is known for AES.

$\endgroup$
2
  • $\begingroup$ Ralph Wernsdorf wrote a similar paper for RIJNDAEL that shows that the round permutations also generate the alternating group there link.springer.com/chapter/10.1007/3-540-45661-9_11. $\endgroup$ Aug 7 at 20:10
  • $\begingroup$ @JosephVanName: thank you; I was unaware of that paper $\endgroup$
    – poncho
    Aug 7 at 20:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.