[Cryptography] Security of a permute-only system?

[John Denker]

On 11/25/2015 04:34 PM, Henry Baker wrote:

> Given a message source that's already "whitened", but otherwise
> unencrypted, how much security can be achieved strictly through an
> unknown, but random permutation?
> 
> I.e., if n=171, then a random permutation of size n would appear to
> require 1026 bits to specify it.
> 
> Suppose we simply applied our random permutation to each block of 171
> pre-whitened bits.
> 
> This random permutation is used essentially as (part of) a symmetric
> session key.
> 
> Let's assume neither CPA nor CCA: this scheme might be part of a
> larger system.
> 
> Q: does such a random permutation provide any additional security, or
> is it merely a waste of time?
> 
> (Let's assume that we can efficiently perform the permutation w/o any
> side channels -- e.g., perhaps an oblivious Batcher-type sorting
> network.)


The question is interesting ... but unanswerable.  It is ill-posed 
coming and going, i.e. simultaneously overspecified and underspecified.

To save time, I will offer some guesses as to what was intended.
If these guesses are close to correct, fine;  otherwise they will
serve to indicate what sort of clarification is needed to make
the question answerable.

*) The Subject line is contradicted by the body of the message.

The Subject line says "permute-only" but the body specifies
a whitener.  The whitener is doing a lot of the heavy lifting.
Depending on unspecified details of the whitener, the system 
could be reasonably secure with or without the permutation ... 
or it could be hopelessly insecure with or without the permutation.

Therefore assumption [A]: We should ignore the Subject line,
and assume some sort of whitener is present.

*) Similarly the body says the whitener and permutation "might
be part of a larger system".  Again depending on unspecified
details, the larger system might be reasonably secure with or
without the permutation ... or it might be hopelessly insecure
with or without the permutation.

Therefore assumption [B]:  We should ignore this part of the
body, and assume the larger system is absent, and focus on
the whitener and permutation.

*) A strong cipher is in some sense an ideal whitener.  Such
a thing makes the question trivial.  The answer is that the
permutation adds nothing;  the system is as secure as it's
going to get, with or without the permutation.

Therefore, to avoid triviality, assumption [C]:  We assume the 
whitener is an open code, perhaps like the famous mercantile
telegraph codes e.g.  https://books.google.com/books?id=4AoIAAAAQAAJ

If the whitener is keyed in any way, we assume the key is
known to the attacker (Eve).  If the whitener is context-
dependent (as any decent whitener must be), we assume the
context is known to Eve, or guessable with high confidence.

*) It is not specified whether the same permutation is used
for a single block or re-used for multiple blocks.  Since
re-use is a dumpster fire, assumption [D]:  All messages
(or all sessions) are one block long.

===================

Under assumptions A,B,C,D we can get an upper bound on how
well the system can perform.  After whitening we have a 171
bit block, and all 2^171 possible patterns are more-or-less
equally probable.

Now consider an implementation [E1] where those 171 bits are
re-encoded in 176 bit words, such that each word has 88
ones and 88 zeros.  That is, each word has a Hamming weight
of 88.  That is relevant, because Hamming weight is a
conserved quantity with respect to permutations.  There
are (176 choose 88) such words, which is more than 2^171.

The re-encoding scheme is known to Eve.

This is an interesting representation, because now a
permutation can change any codeword into any other.  It
takes log2(176!) = 1064 bits to specify such a permutation.
That's a lot ... but you should not imagine that it is
all-powerful;  to specify an arbitrary invertible function
would require log2((2^171)!) bits, which is a muuuuch 
bigger number.

Now consider a different implementation [E2].  To save 
money sending the bits over the wire, we encode the blocks 
using "only" 175 bits.  Half of the codes have a Hamming 
weight of 87, and half have 88.  We call these the "light" 
codes and the "heavy" codes respectively.  All together, 
there are (175 choose 87) plus (175 choose 88) such words,
which is more than 2^171.

The problem is, the set of light codes is closed under
permutations, and the set of heavy codes is also closed.
That means that by looking at the ciphertext, Eve instantly
gets one bit of information about the plaintext.

For many applications, this would be a disastrous amount
of leakage.

Now consider an implementation [E3] where we use the
raw 171-bit blocks, without re-encoding.  There are now
172 different Hamming weights, which Eve can observe and
exploit.  The leakage is an order of magnitude worse than
in scenario E2.

=======================

Summary:  A,B,C,D,E2 is insecure, and A,B,C,D,E3 is worse.

A,B,C,D,E1 "might" be better.  It is not quite as obviously
broken as the others, but I offer no guarantees, only an 
upper bound on the strength.  There could be innumerable 
less-obvious weaknesses.
h