9
$\begingroup$

Consider a $k$-bit block cipher with $r$ rounds, and key composed of $r$ subkeys $K_i\in\{0,1\}^k-\{0^k\}$ (that is, non-zero $k$-bit bitstrings), for $i\in[0,r)$. Plaintext is $P=S_0\in\{0,1\}^k$, ciphertext is $C=S_r\in\{0,1\}^k$. At round $i$:

$$S_{i+1}=\begin{cases} S_i+K_i&\text{[addition in group }(\mathbb Z/2^k\mathbb Z,+)\ ]&\text{if }i\bmod 2=0\\S_i\otimes K_i&\text{[multiplication in field }(\mathbb F_{2^k},\oplus,\otimes)\ ]&\text{otherwise}\end{cases}$$

What must be $r$ to resist cryptanalysis? Possible declinations:

  • Up to what $r$ are we able to exhibit an explicit polynomial-time algorithm (w.r.t. security parameter $k$) that distinguishes the construction from a random permutation with non-vanishing probability, given access to an encryption and decryption oracle?
  • What should be $r$ for a given $k$ of practical interest (e.g. $k\ge64$ or larger) so that $2^n$ group/field operations are (conjecturally) needed to distinguishing the cipher from a random permutation, assuming say $2^{k/2}$ queries to an encryption and decryption oracle, and random key within the restriction that each subkey is non-zero?

We assimilate a bitstring $B\in\{0,1\}^k$, consisting of $k$ bits $b_i$, to integer $B=\displaystyle\sum_{0\le j<k}b_j\,2^j$ in $[0,2^k)$ of ring $\mathbb Z/2^k\mathbb Z$. We assimilate said $B$ to binary polynomial $B(x)$ of degree less than $k$, so that $B(x)=\displaystyle\sum_{0\le j<k}b_j\,x^j$. Multiplication $\otimes$ in field $\mathbb F_{2^k}$ is polynomial multiplication modulo the primitive (thus irreducible) binary polynomial $R(x)$ of degree $k$ minimizing $R(2)$ when evaluated in $\mathbb Z$ (see Joerg Arndt's list, OEIS A132448).


The initial motivation was this question, which can be solved by a fast 64-bit block cipher that we can build with CLMUL now on many CPUs. That evolved to the study of a minimalist block cipher.

$\endgroup$
4
  • $\begingroup$ While round function is minimalist, long key is not $\endgroup$ – Fractalice Jan 13 at 9:00
  • 1
    $\begingroup$ @Fractalic: right. To become a practical cipher, there would be need for a key schedule. I also suspect we should avoid that the $K_i$ contain long sequences of identical bits, which leads to weaker keys. The worst weak keys are those with $K_i=1$ for all odd $i$. One idea is to force all key bytes to have odd parity, as in DES, but for a very different reason! $\endgroup$ – fgrieu Jan 13 at 9:43
  • 1
    $\begingroup$ A mini question: what if $\otimes$ is changed to $\oplus$? Is there any simple attack? $\endgroup$ – Hhan Jan 16 at 2:30
  • 2
    $\begingroup$ @Hhan: if we change $\otimes$ to $\oplus$, the block cipher is unsafe, because there is no propagation from hi-order bit to low-order bit (the only propagation from a bit rank to another is thru the carries, and all are towards higher-rank bit). In particular, the low-order bit of $P\oplus C$ (equivalently, $S_0\oplus S_r$) is constant, and this is enough for a distinguisher. Conjecturally, if we replaced $\otimes$ by $\oplus$ followed by any constant (non-zero) rotation, I think we'd ultimately reach security. But that (again, conjecturally) would require much more rounds. $\endgroup$ – fgrieu Jan 16 at 11:43

Your Answer

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

Browse other questions tagged or ask your own question.