Every cipher I've encountered seems to be built from slight variations of only three basic operations: the S-box, the P-box, and the XOR. I’m just wondering, are there any others? And if there aren't (keep in mind I'm not counting XNOR here, since it's semantically the same as XOR), is there any way to prove that those three operations are the only ones that have the desired entropy properties needed for cryptography?

  • 3
    $\begingroup$ Subtract-and-branch-if-negative is all you need to make a Turing machine, but that knowledge doesn't help you much to design and engineer computer systems. What are you really trying to get at with this question? $\endgroup$ – Squeamish Ossifrage May 26 '18 at 23:42
  • 1
    $\begingroup$ Look into the general operations behind Feistel networks, Substitution Permutation networks, Add-Rotate-XOR, and the Lai-Massey scheme. Those will cover pretty much all the types of operations you're likely to see. But still, this is a very broad question. $\endgroup$ – forest May 27 '18 at 0:59
  • 1
    $\begingroup$ This is an open ended question. And that's especially bad because there are arguably infinitely many operations one could use in cryptography. And then it's not clear how many of those are useful, practical, or simple enough to give a name nor how one would draw distinctions between similar operations. Quick answer: There is no answer because no one has published a proof that puts bounds on the number of things cryptographers might decide to call a primitive. Best we can do is play a game of "list the names of however many things you can think of". $\endgroup$ – Future Security May 27 '18 at 6:48

Actually the list is large. You're only describing the old stalwarts that have been around for donkey's years in say DES. Substitution and permutation form what is termed confusion and diffusion. These aren't always required as there are alternatives. Your sentence regarding entropy as a function is inaccurate as in cryptography the entropy is external to the primitive, eg. in a key or password.

If you consider all primitives and not just ciphers, Keccak hash uses a quite elegant permutation of bits in it's $\pi$ permutation which isn't like a traditional P box as it does not distribute active bits between multiple S boxes. Whirlpool hash uses Galois field multiplication to achieve diffusion, as does Rijndael /AES.

Stream ciphers operate differently, and a stream of pseudo random numbers are used. ISAAC and RC4 are examples that use various array transpositions /indirections and bitwise rotations. I guess if you had a lot of time, Blum Blum Shub could be seeded to product a (slow) cipher stream of pseudo random numbers that is based upon prime multiplication and quadratic residues.

If you then expand the scope to asymmetric techniques, that are all manner of other mathematically hard trap door problems that can be used in things like lattice and elliptic curve cryptography, key exchange etc.

There are even alternatives to XOR, such as modular addition used in Speck. Speck also extensively features the bit rotate operator.

So you see that the list is longer than you thought, and I've only included a few of the operations that underpin cryptography. I hope that by listing these, it's proved by deduction that S and P boxes and XOR are not the only tools.

| improve this answer | |
  • $\begingroup$ The finite field arithmetic done in Whirlpool (and AES) is not intended for diffusion. Its purpose is to break linearity and provide confusion. Also, most implementations use a precomputed S-box. $\endgroup$ – forest Sep 8 '19 at 7:28

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