[Cryptography] Security of a permute-only system?

[Miroslav Kratochvil]

I was considering similar scheme some time ago. Good idea is that key
expansion to permutation is actually computable in linear-time [1]. Bad
problem is the "whiteness". I only considered a scheme where you expand any
bit string to a string with exactly 1:1 amount of ones and zeroes (that is
achievable in decent time with colex ranking/unranking, e.g. my
implementation [2]), but that is fully breakable when an attacker has a
chance to see results of n*log(n) chosen encryptions with your key. Schema
is like this, for n=8:

you encrypt 00001111
then 00110011
then 01010101
get all the ciphertexts, AND them together, and you know the position of
permuted last bit. Repeat for all other bits.

If the inputs to the permutations were hard for attacker to modify, the
scheme would be secure. Similar scheme was (successfully) applied to
original McEliece scheme - secret permutation P was used to hide the
structure of the generator matrix.

Certainly some whitening could help the situation, but I'm not sure whether
there is some decent algorithm for reversible unranking of string to
whitened counterparts. One of the simplest methods is again found in
McEliece, namely the matrix S that is used for the exactly same purpose
(whitening the input). But that is a bit hardcore for our purpose (S can
"swallow" the permutation functionality anyway).

There is probably a simpler approach - you can pad the original input with
a simple hash of the plaintext, which (after colex unranking) effectively
prohibits any fixed ones/zeros in the permutation input:

encrypt(m,k) = rank_colex( permute( unrank_perm(k), unrank_colex(m |
hash(m)) ) )

It certainly needs some more research.

Hope this helped a bit.

-mk

[1] Mares - Linear-time ranking of permutations
[2] https://github.com/exaexa/codecrypt/blob/master/src/bvector.cpp#L355
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20151126/dff85623/attachment.html>