So I've come up with an (admittedly impractical) encryption method using a lookup table. The table is a shuffled list of all unsigned 32-bit integers, effectively making it a 32-bit unkeyed PRP. I have this in a 16 round Feistel network, bringing the block size up to 128 bits and adding a 128-bit key.

Ignoring implementation issues like timing attacks, or the impracticality of carrying around a ~4 billion item lookup table, is the concept here sound? Are there any glaring issues I'm missing? Needless to say, this won't be going into anything important regardless.

Assume $E$ is an ideal unkeyed PRP (stored as a 16gb lookup table). The method starts with the simple key schedule. $Key_{n}$ is a list of 32-bit key blocks, and $RK_{n}$ is the resulting round keys for the Feistel network.

$$RK_{n} = \begin{cases} n\in[0,3] & E(Key_{n})\\ n\in[4,15] & E(RK_{n-4}) \end{cases}$$

The plaintext is given as the 32-bit blocks $A_0, B_0, C_0, D_0$. Encryption is as follows.

$$A_n = B_{n-1}\\ B_n = C_{n-1}\\ C_n = D_{n-1}\\ D_n = A_{n-1} \oplus E(RK_{n-1} \oplus E(B_{n-1}) \oplus E(C_{n-1}) \oplus E(D_{n-1}))$$

The values $A_{16}, B_{16}, C_{16}, D_{16}$ are the resulting ciphertext.

Decryption is a simple reversal of the above.

  • $\begingroup$ A 4-billion-item lookup table actually wouldn't be that bad on modern servers or high-end workstations; they could keep the entire table in a small fraction of their RAM. Heck, laptops can do it these days. $\endgroup$ – Nat Jul 2 '17 at 9:39
  • $\begingroup$ @Nat: it would be dreadfully slow; each $E$ table lookup would be a cache miss, and on a high-end CPU, a cache miss takes hundreds of CPU cycles. $\endgroup$ – poncho Jul 2 '17 at 11:29
  • $\begingroup$ +1: I'm very interested in algorithms that feature a large amount of hard coded entropy, such as the 4GB of program code you're suggesting. $\endgroup$ – Paul Uszak Jul 2 '17 at 11:49
  • 4
    $\begingroup$ A couple of things that give me a bad feeling: 1) The way B, C, D contribute to the new value of D is exactly the same 2) You use the same function for deriving the round keys and to transform the words in the round function, which suggests unfortunate interactions. $\endgroup$ – CodesInChaos Jul 2 '17 at 12:33
  • 2
    $\begingroup$ A brief cryptanalysis, key schedule appears to be vulnerable to slide attacks. Consider key ABCD and rotated key DABC, the schedule gives an 'off by one' schedule if E(D) = D thus a class of weak keys. The round function itself resisted simple differentials but seems vulnerable to truncated differentials and integral attacks. I wasn't able to get a full differential but there is a 5 round truncated differential starting with 00X0 from both ends. It seems likely that a 16 round differential exists. These types of questions are fun and instructive. The off topic rule should be changed. $\endgroup$ – Matthew Fisher Jul 3 '17 at 1:05