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

John Denker jsd at av8n.com
Sun Nov 22 16:05:44 EST 2015


On 11/21/2015 08:05 PM, Phillip Hallam-Baker wrote:

>  Known plaintext is fairly rare but
> very guessable plaintext is much more common

Oh, it's muuuuuch worse than that.  Nowadays one needs to
worry about /chosen/ plaintext attacks.  BEAST is a recent
example.

> There are a couple of ways to defeat this type of attack. One would be to
> effectively randomize the plaintext by pre-encrypting with something like
> RC4.

Isn't the whole purpose of a cryptosystem to "randomize the 
plaintext"?

If the original system requires you to pre-randomize, it 
sounds to me like the original system wasn't worth much.
Specifically, the situation reminds me of stone soup.  If 
you pre-arrange enough yummy ingredients, the stone soup
recipe turns out great.  However, the stone per_se isn't 
doing what it claims to do.


In the context of cryptographic "modes", on 11/16/2015 
01:51 PM, Perry E. Metzger wrote:

> We didn't understand what they guaranteed. CBC in particular has
> proven much more problematic than was assumed 25 years ago.

One could argue that CBC is a nasty hack, and always has been.
Ditto for other chaining modes.

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:
 -- Less security, especially in the face of chosen-plaintext
  attacks.
 -- Increased cost, if you have to "pre-randomize" the data
  and/or encrypt-then-MAC in order to have a semblance of
  security.  Such increases are likely to nullify the alleged
  advantage that chaining was supposed to confer.
 -- Chaining doesn't work for datagrams, since it requires a
  well-defined notion of "previous" packet.
 -- Chaining doesn't work for random-access disk sectors.
 -- Chaining doesn't work if you want to encrypt a bunch of
  stuff using parallel hardware.

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:

     session key --\
                    \
     block # --->  XOR --\
                          \
                           \
                            \
     plaintext  -------->  block cipher -->  ciphertext

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.


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

     session key ----\
                      \
                    preliminary
     block #  --->    cipher  ----\
                     (or hash)     \
                                    \
                                   main
     plaintext  ------------>  block cipher -->  ciphertext


One way of looking at this is as a version of the main block
cipher, with a vastly fancier key schedule, making it more
resistant to related-key attacks.  That is, we parenthesize
the diagram as 
  (SK + block #) + (preliminary cipher + main cipher).

Another way of looking at this is as a stream cipher, which
is used to generate a stream of keys for the main cipher:
  (SK + block # + preliminary cipher) + (main cipher)

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.

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.


4) For completeness, we should mention using ChaCha directly as
a so-called stream cipher, in the usual way:

   session key ----\
                    \
   block # ------> ChaCha ------\ 
                                 \
                                  \
   plaintext -------------------> XOR --> ciphertext


Compared to scheme (4), scheme (3) has better diffusion.  Compared
to scheme (1), scheme (3) has more convincing confusion.

Of course in a known- or chosen-plaintext attack, diffusion doesn't
do all that much good.  So maybe scheme (4), primitive as it may
look, might not be completely crazy.

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

In the spirit of the recent thread about "other obvious issues being
ignored", I turn to the mother lode of things that are "generally
believed" but not actually true:

Quoting from https://en.wikipedia.org/wiki/Advanced_Encryption_Standard
>    However, related-key attacks are not of concern in any properly
>    designed cryptographic protocol, as properly designed software will
>    not use related-keys.

I say that's ludicrous.  As discussed above, there are exceedingly 
reasonable things one would like to do that involve related keys, 
which reportedly work with some ciphers (ChaCha) and not others 
(AES).  At a minimum, "concern" for related key attacks is a
prerequisite for "proper design".  If you tell me that "properly 
designed software" is obliged to pre-whiten the plaintext and/or 
pre-whiten the keys, I'm going to call it stone soup.

Quoting from https://en.wikipedia.org/wiki/Confusion_and_diffusion
>    The simplest way to achieve both diffusion and confusion is to use a
>    substitution-permutation network. In these systems, the plaintext and
>    the key often have a very similar role in producing the output, hence
>    the same mechanism ensures both diffusion and confusion.

Actually no.  If that were true, there would never be any such thing
as a related-key attack (since all cryptosystems are assumed secure 
with respect to related plaintexts).

In such a system, in a related-key + chosen-plaintext attack scenario,
you might end up with good security or no security whatsoever, depending
on how strong your key schedule is.  This is a big deal, because the 
AES key schedule is not very impressive.  I was astonished to hear that
related-key resistance was not a criterion and was not even evaluated 
during the AES competition.
     https://www.google.com/search?q=%22aes+competition%22+%22related-key%22



More information about the cryptography mailing list