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

[Natanael]

Den 22 nov 2015 23:04 skrev "John Denker" <jsd at av8n.com>:
[...]
> It seems obvious that if we wanted to do the Right Thing™ we
> would use a separate key for each block of the message.  Then
> some genius observed that keying was expensive, and one could
> optimize for speed by re-using a key, block after block.  It
> was argued that chaining was "almost" as good as rekeying.
> It was never really as good, so this optimization came at a
> price:

[...]

> It doesn't have to be that way.  For example ChaCha does not
> depend on chaining;  it can do a random-access "seek" to any
> block number whatsoever.  So, even though it is classed as a
> "stream cipher" it doesn't require an actual stream.
>
> One can achieve a similar result using a block cipher as your
> crypto primitive, as follows:
>
> 1) In some hypothetical ideal world, one could imagine the
> following, which I call "plain key ringlet" mode:

[AES-CTR like mode, except encryption comes after the last XOR]

> I don't trust the resistance of AES to related-key attacks, not nearly
> enough to use it in this mode, but hypothetically if we could trust
> it, there would be numerous advantages:
>  -- More resistance to guessable-plaintext attacks, known-plaintext
>   attacks, and chosen-plaintext attacks.
>  -- No "pre-randomization" required.  No encrypt-then-MAC required.
>  -- Decent efficiency.  For AES the cost of rekeying is only 40% of
>   the cost of encrypting a block, so this has more than 70% of the
>   throughput of any chaining mode such as CBC.  It is out-and-out
>   faster than disk-encryption modes such as CMC and EME.
>  -- Unlike chaining modes, this works for datagrams.
>  -- Also for random-access disk blocks.
>  -- Also for parallel crypto processing.

We still need MAC. Even scrambled plaintexts can be harmful, we need
authentication.

> 2) Consider the following, which is meant as an existence proof,
>  not as an optimized design.  I it call "turbo key ringlet" mode:

[what I call stream cipher keyed counter block mode, similar to your own
description below]

On a second thought I'm reminded of how XTS mode works, though still very
different;
https://en.wikipedia.org/wiki/Disk_encryption_theory#XTS

> You could use any old block cipher in CTR mode to generate the
> key stream.  AES is pretty fast.  Or you could use a so-called
> stream cipher directly.  ChaCha is very fast.

Even the lower margin version ChaCha8 instead of ChaCha20 could be used. In
this mode you'd need a massive statistical bias break in the output of
ChaCha8 to crack the key.

> 3) This isn't new;  a while back Sandy Harris proposed "enchilada"
> which can be seen as an optimized version of scheme (2):
>
>    session key ----\
>                     \
>                  preliminary
>    block # ------> ChaCha ------\ (round key array for AES)
>                                  \
>                                   \
>    plaintext -----------------> guts of AES --> ciphertext
>
> It bypasses all of the Rijndael key schedule, and instead relies
> on ChaCha to directly generate all 11 (or 15) of the AES round
> keys.

I've seen other suggestions like this on the crypto mailing lists (though
I'm not finding any right now, except for a previous mention of enchilada).
I've thought of this before myself and like the idea. You could potentially
use both an efficient small stream cipher to key a small efficient block
cipher in something like XEX mode. Something in the style of NSA's Speck
and Simon (though I wouldn't use something designed by them, see Dual EC
DBRG). It could easily be parallellized.

Problem is I'm not sure how to do authentication and keep efficiency. Use
Poly1305 the way it is typically combined with ChaCha20, and use the first
stream cipher output for block #0 (or the output after encrypting an empty
block with it) as the authentication key? Won't this kill performance?
What's the most efficient secure enough authentication mode? Any efficient
single-block authenticated ciphers (taking an encryption key and
authentication key separately)? Maybe Keccak who is supposed to be a very
flexible primitive and be able to provide authentication too.

Slightly off topic, but in order to not make things too simple for NSA
either, preventing ciphertext compression like with simple removal of
authentication tags, would be a nice feature:

https://moderncrypto.org/mail-archive/messaging/2014/000558.html

In the recent AEAD discussions I've seen links to AEAD modes where the auth
key is encrypted with the plaintext (with ciphertext longer than the
plaintext to match) and other such solutions where the tag/authentication
is mixed in with the ciphertext. Think it was in the nonce misuse resistant
AEAD conversations that it was linked. Also, if there were some
authentication tag algorithm that had an All-or-nothing-transform then that
would be nice too.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20151123/a4d6bfef/attachment.html>