[Cryptography] Cipher having a universal polymorphic-decryption property

[Ray Dillinger]

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 here, 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.

So that's a very secure but ridiculously slow block cipher having a
potentially devious univeral polymorphic encryption property.  Can
anyone think of a single sane use (or a suitably underhanded use) for it?

				Bear

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20141211/71898beb/attachment.sig>