I have developed an interesting and peculiar cipher. I don’t believe that there’s any proper application for it because it is very slow, but it has at least one rather astonishing and potentially underhanded property, so I thought I would describe it and see if anyone here has any idea of a good (or evil) use for it.

This is now my entry for the “underhanded crypto” contest recently announced on the Metzdowd cryptography list, although I can’t immediately think of any terribly underhanded use for its astonishing property. I’m confident that it has an underhanded use, but I just can’t think of it. Perhaps that’s just because I am not sufficiently devious.

There was an earlier version that had security problems, but on polishing up the code, I found the mistake I had made (a mathematical proof which I had misinterpreted) and was able to fix it. The current version is now less “Fatally Flawed” than the original, but definitively has more potential for “Underhanded” use.

In construction it is a Feistel block cipher of four rounds. The S-boxes are constructed by (uniformly distributed) pseudorandom selection from among all possible sets of S-boxes. Each block encrypted uses a different set of S-boxes. The P-boxes are fixed and utterly generic: one bit from each S-box to the input of each S-box of the next round.

There is a version with 32-bit blocks using 4-bit S-boxes (permutations of 16 bitpatterns), and a version with 128-bit blocks using 8-bit S-boxes (permutations of 256 bitpatterns).

The selection of S-boxes is driven by a key stream, generated from a cryptographically secure pseudorandom generator initialized using a key, as for a stream cipher. In fact this whole thing began as an experiment in how to protect stream ciphers from bitflipping and repeated-keystream vulnerabilities.

The security of the cipher rests on the unpredictability of the key stream. If the keystream is unbiased and unrepeated, as with stream ciphers, I know of no conventional cryptanalytic technique that will make any inroads into it. In order for any conventional cryptanalytic technique to be meaningful, it is necessary to have a repeated keystream, giving the adversary more than one block encrypted using the same set of S-boxes. In that case I believe that it is at least *AS* difficult to make inroads against blocks having a single keystream location in common, as against any cipher having its block length, and that discovering the complete permutation (key) of any keystream location should give an attacker no insights against other blocks of the same keystream.

Feistel ciphers of four rounds have been proven capable of implementing literally every permutation of bit blocks depending on the S-boxes used, so this gives the peculiar effect, in common with stream ciphers, that if the pseudorandom generator used can be used to generate any sequence of the length required to construct the S-boxes for a given sequence of blocks, a given plaintext of that length or less can be encrypted as literally *ANY* ciphertext of the same number of blocks. Conversely, given a ciphertext, it can correspond to literally any possible plaintext, depending on the initialization of the PRNG.

Therefore if used with with a PRNG that permits one to find an appropriate initial state to “decrypt” to a selected message, you could find keys that permit you to decrypt any short ciphertext to a chosen plaintext message if someone with a court order, rubber hose, or $5 wrench requires you to give them a key. This is the (at least potentially) underhanded bit.

I have implemented it with a Completely Ridiculous CSPRNG that meets these requirements: it is provably capable of producing absolutely any sequence of bits up to 850Kbytes or thereabouts, *AND* you can find a key/initial state that permits any chosen initial sequence of that length or less to be output. So you can find a set of S-boxes required to encrypt/decrypt a given input to exactly match a desired output, one block at a time, and set the PRNG to produce the output, in sequence, that will produce exactly the desired S-boxes to transform a given input to your selected output.

The Completely Ridiculous CSPRNG is brutally simple in construction and requires just as much memory as you’d expect that it would. It takes a good known CSPRNG and masks its output with a massively large Linear Feedback Shift Register. The LFSR is in no way cryptographically secure, but using its output to mask with, provides a proof that the resulting PRNG can (and eventually will) produce every possible sequence of bytes up to the length of the LFSR state. The CSPRNG can be run, its output recorded, and the contents of the LFSR state selected to complement the CSPRNG output stream to produce any chosen output stream up to the length of its state. Because it is possible to find a set of S-boxes that will cause a given block to be transformed to any other block, it is possible to “gimmick” the PRNG state; one can find an initial PRNG state which will decrypt any input to some chosen output. Nevertheless, the PRNG output is otherwise just as secure as the output of the CSPRNG used to drive it. The current implementation uses a conservative (indeed, excessive) version of Rivest’s “Spritz” generator, with its state information widened to a permutation of 16-bit values, but retaining 8-bit output per state transition.

Now, as to the reason why it is slow. It requires 54 bits of pseudorandom keystream per bit encrypted (when implemented in 128-bit blocks) or 40 bits of pseudorandom keystream per bit encrypted (when implemented in 32-bit blocks). In addition to the time spent generating pseudorandom numbers, time is spent using that pseudoentropy for constructing the S-boxes for each block and then actually performing the encryption and decryption. And the PRNG is enormous defeating on-chip cache. So in terms of speed, it is a snail among racehorses.

As you may have guessed, the length of a “key” that can decrypt a given ciphertext to any chosen plaintext is therefore 40 or 54 times the length of the ciphertext/plaintext pair, and therefore use of such a “key” would be rather obvious unless it is the case that *ALL* keys used with the system are that length. Predictably, the size of keys indicated is a bit over 850K, enabling messages of up to 14Kbytes or so to be encrypted (or decrypted) to any chosen ciphertext (or plaintext) by selection of a particular key.

This makes key distribution and management, if this particular capability is desired, just as large (in fact 54 times larger) a problem as it is for one-time pads. On the other hand, if initialized from a key of 128 bits, it is as secure as any other cipher of 128-bit security.

Obviously, the Completely Ridiculous PRNG can be used to create a stream cipher having the same universal polymorphic decryption property applicable to much longer messages, but in this application you would have the usual problems of stream ciphers, in messages becoming entirely insecure in the case of repeated keystreams and in vulnerability to bitflipping attacks – necessitating MACs, initialization vectors, etc.

But that isn’t the half of it. Because a complete permutation is being chosen for each block of the cipher, you can do more than choose a single output for a single input. You can choose different outputs for different inputs at the same time, because those would be different elements of the permutation at that block. In other words, you can make a key which will reliably encrypt A to B at a given block location, and which will also encrypt C to D, encrypt E to F, and so on. In fact you can create a key that will give you up to 30 different chosen encryptions (where you take a previously chosen known plaintext and “encrypt” it to get a previously chosen known ciphertext) before the math to pick out the right S-boxes starts to get really hard. With work, you can get more than 30 chosen encryptions but the math does start to get really hard.

So you could create a key with 30, or possibly more, chosen encryptions, and use it as a “normal” key for purposes of encrypting other messages, for as long as you like – but then on a few special occasions when the circumstances warrant, you could send ciphertexts indistinguishable from innocuous plaintexts which that particular key would decrypt into one of your 30 chosen messages.

You could also create a key that reveals a long secret message when used iteratively. In other words, Alice can create a key and share it with Bob, then send an innocuous looking message A to Bob, who could encrypt it and get chosen ciphertext B, then encrypt B and get chosen ciphertext C, then encrypt C and get chosen ciphertext D, and so on. In this case the usual roles of ciphertext and key are reversed. The effect is not much different from giving Bob an encrypted message (up to 30 times longer than the “chosen encryption” length of the cipher) and then sending him the key at a chosen moment.

One problem with this is that if you use chosen encryptions that transform “innocuous looking” plaintext to a meaningful message, an adversary can attack the cipher based on guessing block-sized bits of plaintext as ciphertexts and finding collisions with your chosen encryption of that ciphertext. This could result in revealing your chosen encryptions early, and could be leveraged for knowledge about your S-boxes which an adversary could use to attack other messages encrypted with that key. Therefore using this property directly would be harmful to security.

To use the polymorphic-decryption property without sacrificing security, it should be used only with at least one end of each chosen encryption being apparently-random gobbledegook. That way an opponent either can’t guess the plaintext because it’s binary gobbledegook, or can’t tell that the encryption is chosen, because it’s encrypted form looks like binary gobbledegook. What this means is that with security, you can actually encode fifteen, not thirty, chosen encryptions in the key. Bob would use it by decrypting a (potentially innocuous-looking) ciphertext to get a message that looks like random noise, then re-encrypting the random-looking noise using the same key to get a different chosen plaintext.

Anyway, that’s a very secure but ridiculously slow block cipher having a potentially devious univeral polymorphic encryption property. It is a particularly amazing example of “deniable encryption” in fact. Can anyone think of a single sane use (or a suitably underhanded use) for it?