[Cryptography] basic cryptography ... was: key breaking

[John Denker]

On 11/23/2015 11:23 AM, Viktor Dukhovni wrote:

> The other key can simply be the same for every block, no need for
> RC4:
> 
> 	K_1 xor AES(K_2, data) xor K_1
> 
> Same K_1 for every block.  The DESX trick is not as cheesy as it
> might seem.  The DJB attack fails provided no single K_1 is shared
> by many K_2's.  (See the "Even Mansour" paper).

OK.

However, it is still true, as pointed out on Mon, Nov 23, 2015 
at 12:30:08PM -0500 by Phillip Hallam-Baker:

>> You have just invented
>> a new cipher with an extra round. 

Also with extra keying material required.

As with any cipher in this class, to have any semblance of security
for multi-block messages, you still need to do something like CBC.
So the parties need to agree on K_1, K_2, and IV.  Even then, we
still have all the nastiness associated with chaining modes:
 -- Doesn't work for datagrams.
 -- Doesn't work for random-access disk sectors.
 -- Doesn't parallelize.
 -- Doesn't solve all the security problems.

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

Contrast that with:

  i = block #

  (V_i, W_i) = ChaCha(K_1, i)

  ciphertext_i = V_i XOR AES(K_2, plaintext_i) XOR W_i

 ++ Works for datagrams.
 ++ Works for random-access disk sectors.
 ++ Parallelizes.
 ++ Does not require chaining.
 ++ Solves a bunch of problems that CBC doesn't.
 ++ Does not depend on encrypt-then-MAC.
 ++ Compatible with any imaginable authentication scheme
  (encrypt-then-MAC or otherwise) at this layer or higher or lower.
 ++ Does not require an IV.
 ++ The amount of keying material (K_1 and K_2) is not increased
  relative to vanilla AES/CBC.
 ++ Affordable.  Slightly more work than vanilla AES/CBC, but only
  very slightly.  Cheaper than AES/CBC/MAC.  Possibly slightly cheaper
  than enchilada.  Definitely cheaper than disk-encryption modes such
  as CMC and EME.
 ++ Hard to break.  Would require serious breakage of both AES and ChaCha.
 ++ Easy to analyze.  Even Mansour and all that.

This provides as much diffusion as AES/ECB (in contrast to ChaCha by
itself, which doesn't).  However, I don't want to emphasize diffusion.
It's overrated.  It asks the plaintext to do something it shouldn't
be asked to do, i.e. to provide randomness.  This can backfire bigtime
during chosen-plaintext attacks.  I would prefer to see the keys provide
sufficient randomness.  That's their job.

Did I mention that chaining modes are a nasty hack?

On 11/16/2015 01:51 PM, Perry E. Metzger wrote:

> CBC in particular has
> proven much more problematic than was assumed 25 years ago.

Indeed.  It's time to do something better.