[Cryptography] If diffusion is perfect how much confusion do you really need?

[Natanael]

Den 2 jun 2015 02:21 skrev "Ray Dillinger" <bear at sonic.net>:
>
> (warning: cipher design post)
>
> Let's say, in theory, that I have a "perfect" diffusion mechanism
> that can be defined for blocks of many different sizes.

[avalanche effect]

> But this mechanism which provides perfect diffusion, provides no
> confusion whatsoever.  Like P-boxes, it is trivially reversible,
> and anyone given the whole set of output bits can easily derive
> all the input bits. I'll denote the reversed D-box as a "Xob-d".

Makes me think of error correction coding with overhead set to 0 (Qr codes
is one example where that's an available option), using the key as the seed
for the randomness commonly employed in error correction algorithms.

> Now, I believe, but could be wrong here, that if you have such a
> "perfect" diffusion mechanism, you need very little confusion to
> create a secure cipher.
>
> in catenative notation, using no S-boxes whatsoever and xor as
> a trivial, reversible method of combining message with key, I
> can't think of a single attack that applies to this utterly
> simple, fast, three-and-a-half round construction:
>
> M > ^key | D-box | ^key | D-box | ^key | D-box | ^key = C
>
> And the decryption is in fact the very same operation using the
> reversed D-boxes:
>
> C > ^key | Xob-d | ^key | Xob-d | ^key | Xob-d | ^key = M

[...]

> But I think this is different.  This is a construction I'm
> actually confident in for mathematical reasons, and it's
> fast, and it requires very little state, and it's general,
> and it could be ridiculously fast (and small) in silicon,
> and it's so simple that it would be easy to get right.
>
> Am I hallucinating here?  Can anybody put this firmly in
> category B, or should I start writing a paper and some code
> to submit for the next design competition?  Surely this is
> too simple to've not been considered and debunked by someone
> smarter than me.

I'm no professional, so I might be missing something obvious to the
experts, but here's a reference to what this reminds me of:

XOR-encrypt-XOR mode (XEX): http://en.wikipedia.org/wiki/Xor-encrypt-xor

AFAICT I believe it should be secure IF the diffusion (computationally)
hides all statistical biases in the original plaintext and if the diffusion
is (computationally) uncorrelated from the application of XOR before and
after it, and if it is (computationally) indistinguishable from random and
thus effectively unpredictable (like a strong hash).

Attacks against XOR all relies on knowing statistics about the bits of
plaintext (diffusion output in this case). Repeated XOR of the same bit
string of terabytes of fully random data doesn't reveal anything about what
the string is because nobody knows what the original data was supposed to
be.

If your diffusion effectively makes it impossible to predict if any given
bit should be 1 or 0 without knowing the entire plaintext, and if known
plaintext + ciphertext don't reveal the key, I don't see a flaw here (for a
single block).

However, with biased diffusion outputs, you can perform an attack similar
to those against RC4 and XOR blocks against each other (if in ECB mode) and
try statistical attacks to uncover a possible raw diffusion output that you
try to reverse.

Say the worst case is ECB mode encryption of a counter (can you think of a
worse one?). You'll perform the diffusion on what's essentially a bunch of
iterations of your key. All those diffusion outputs must be computationally
uncorrelated and unpredictable. Even knowing it is a counter that has been
encrypted, you shouldn't be able to guess the effect on the diffusion.

If the diffusion output are statistically correlated, you can extract the
XOR'ed key given enough ciphertexts. The diffusion output simply needs to
be computationally indistinguishable from random even against chosen
plaintext attacks.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20150602/0446c7e4/attachment.html>