Re: cryptanalyzing bitwise tramps?

Greg Rose wrote:
In article <fsba74$77j$1@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
HHaller <hhaller@xxxxxxxxxxxxxxxxxxxxxxxxxxxx> wrote:
[bit-permutation cipher]

I'd never spent much time thinking about bit-permutation
ciphers before. The chose-plaintext attack is the
obvious one and would work. (You would be
surprised how often it is possible to make the
target of an attack encrypt something that the
attacker gives to them.) But it's a bit more
challenging if you restrict yourself to the more
common known-plaintext scenario. That is, The
attacker knows both the inputs and outputs of
encryption under an unknown key.

Let there be N bits in the block. Then you can
think of the encryption as a simple matrix
multiplication:
C = M.P
(C is the ciphertext bit vector, P is the
plaintext bit vector, and M is a NxN binary
matrix.) THere are lots of constraints on the M
matrix, but we'll come back to that. For the
moment just assume the entries are arbitrary.

There are N^2 entries in M, which are unknown.
Each known plaintext-ciphertext pair yields N
binary linear equations relating up to N of these
unknowns. So with (somewhat more than) N such
pairs, you can simply run Gaussian elimination on
the N^2 unknowns, which would take time N^6
naively. If, for example, n = 256 = 2^8, you have
an O(2^48 attack.

But it gets worse. You can attack each of the
output bit positions separately, since they don't
interact with each other. So you really have N
independent systems of equations each in N
variables. These can be solved in O(N^4) (again
naively), or about 2^32 for N=256.

All that without assuming anything about the
contents of the matrix M... the attacks work on
any general linear system.

In this case we know that the matrix implements a
permutation, that is, there is exactly one '1' in
each row and column. If we assume that the
plaintexts are random (which is probably not true
in general), we can assume that for each output
bit, it will match a given bit of the input with
probability 1/2 if it's the wrong bit, but
probability 1 if it is the right bit. (Note that
this is a huge bias, cryptographically speaking.)
Given K known plaintext-ciphertext pairs, the
probability that a given output bit matches all of
the K input bits in a given position is 2^-k. So
long as K is somewhat greater than log_2(N), the
one that works right will be obvious. So with
about, say, 16 pairs for N=256, you can figure out
the permutation pretty quickly, O(NlogN).

For non-random plaintexts, the problem is that you
won't necessarily get enough information for a
unique solution. For example, encrypting ASCII
texts will show you where the 8th bits go, but
they'll always be zero so you won't know which are
which.

just some random thoughts,
Greg.

If he is going to look at bit permutations then perhaps the cipher by Moldovyan, i.e. Spectr-H64, Cobra, CIKS etc will be interesting
.

Relevant Pages

  • Re: Countering chosen-plaintext attacks
    ... >> attack on your cipher as proof that the cipher is safe from anyone ... > So we have a disagreement as you said. ... This is why it is called a chosen plaintext attack. ...
    (sci.crypt)
  • Re: Variable S-boxes
    ... "Tom St Denis" wrote in message ... I showed there was little computational cost of one valid morphing S-box. ... S-box denies that data how does an attack proceed? ... When finished and properly described my cipher (1-2 ...
    (sci.crypt)
  • Re: Countering chosen-plaintext attacks - heres those answers I sent you but I dont know if you got
    ... >> cryptanalysis of a block cipher in ECB mode can be done using just ... This c, this ciphertext, opens the door to a ciphertext-only attack ... >> I am open to any references or sources that back up your claim. ...
    (sci.crypt)
  • Re: Security of Secret Algorithm encruption
    ... > unknown algorithm? ... inner workings of the cipher, even though small portions might be missing. ... completely executed in the human mind. ... To attack this first I would look at n-gram distirbution to ...
    (sci.crypt)
  • Re: Polymorphic Ciphers
    ... stream cipher attacks as well as block cipher attacks. ... most or all commonly known symmetric encryption algorithm designs ... polymorphic ciphers can be made immune to Differential Power Attack." ...
    (sci.crypt)