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

John Denker jsd at av8n.com
Wed Nov 25 12:18:28 EST 2015


On 11/24/2015 12:29 PM, Dennis E. Hamilton wrote:
> Surely there is a typo

Good catch.  Fixed in this version.

At a much deeper level, on 11/24/2015 09:16 AM, Sandy 
Harris wrote:

> Most stream
> ciphers just XOR to mix generator output with plaintext, so
> any enemy with known plaintext can recover generator
> output at trivial cost.

I should have explained this point earlier:
  When I am doing the encryption, I require that each 
  bit of generator output be used at most once.

Subject to that requirement, and assuming the generator
is cryptographically strong, the aforementioned known-
plaintext attack is non-issue.  The attacker already
has the plaintext, so he can't learn anything new about
that ... and learning about the generator output doesn't
do him any good.

In particular, I need to repair and explain the diagram
that I presented on 11/23/2015 06:04 PM.  I should have
said:

  i = block #

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

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

Of course you can replace AES by some other block cipher.
Similarly you can replace ChaCha.  In this case almost
any cryptologically strong hash function would suffice.

To be clear:  I am assuming that ChaCha is so strong
that it would be secure even if the AES step were
replaced by the identity transformation.  The need for
this assumption becomes clear when you consider chosen-
plaintext attacks (e.g. BEAST).

Let's talk about the nonce.  It is a standard feature of
ChaCha, for good reason.

*) By way of background:  For TCP-like traffic, each 
 block is encrypted only once, so the sequence number
 is unique, and the nonce doesn't add much.

*) More interestingly, UDP doesn't have block numbers,
 so one would have to introduce a concept of block #
 and/or a concept of nonce.  (A lot of UDP traffic has
 a sequence number at some higher level, but this is
 not something we can rely on in the general case.)

*) Yet more interestingly, for random-access disk sectors,
 the usual block # is not good enough, because blocks can
 be rewritten.  Here is where the role of the nonce can
 be seen clearly.  We need a block number /and/ a nonce.

Adding a nonce to a stored disk block is like adding salt
to a stored password.  It increases the storage requirement,
but is necessary for security.

  Tangential remark:  The idea of encrypting disk blocks
  with zero added storage requirement was a non-starter to 
  begin with, assuming you wanted some sort of authentication.

Also:  For maximum security, I would prefer to see the AES
key change every time (as a function of block # and nonce).
The construction given above drops this feature as an 
economy measure, to save the cost of rekeying.

Also note that in contrast to the proverbial whole enchilada,
this can take advantage of standard AES hardware.  You just
wrap the AES in XORs.

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

The general, conceptual points are:

  1) Using the same key more than once, block after block, 
   is a bad habit.  It causes all sorts of problems, some
   of which are alleviated by chaining modes such as CBC,
   but some of which are not.  We reeeeally need to kick 
   this habit.

  2) As a corollary:  We need ciphers for which rekeying
   is not expensive.

  3) On the other side of the same coin, we need ciphers
   with a strong key schedule, so that they are as strong
   against related-key attacks as against any other kind
   of attack.  (AES lacks this feature.)



More information about the cryptography mailing list