[Cryptography] encryption + authentication - waiting - chaining (was: best practices)

[John Denker]

On 03/19/2017 03:04 PM, Kristian Gjøsteen wrote:

> With AEAD modes such as GCM, you can begin producing ciphertext the
> moment you get the first bytes of the message, which is convenient in
> some settings, I am told.

There's no need to rely on hearsay.  In telephony, very little
latency can be tolerated, and there is no relevant bound on the
length of a message.  The same idea in a slightly weaker form
applies to random-access storage devices:  You have to deal with
smallish blocks, not entire messages.

> What practical people appear to worry about is that you need to 
> process the entire message before you can begin producing 
> ciphertext.

Blocking until a first pass has been made over the entire message
would be even worse than the usual schemes for authenticating at
the "end" of the "message".

On 03/21/2017 08:28 PM, James A. Donald wrote:

> Every encrypted message needs a secret key, a unique IV at the 
> beginning, and an integrity check at the end.

For real-time interactive services and for random-access storage,
there is no such thing as the "end" of a message, and indeed no
such thing as a "message".  You have to encrypt and authenticate
on a block-by-block basis.

Also, in the real world there will be dropouts and there will
not be time for retransmissions.  Therefore chaining modes are
not usable.

On 03/20/2017 11:54 AM, Natanael wrote:
> This requires both linear encryption and then linear validation of
> every block from start to end as you decrypt, but proves at every
> stage that the full message is intact from the start to the block
> you're currently processing [....]

> This could be used for example to stream video over a network, where
> you first would continously transmit the signed partial Merkle tree
> roots, each substituting the prior one, until done streaming (this
> would however be fairly inefficient compared to the other options).

Inefficiency is an issue.  Authentication is always going to cost
"something", so the question is how much.


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

I offer no opinions about the strengths or weaknesses of the following
example, but at the very least it serves as a stake in the ground,
i.e. as the starting point for discussions and comparisons:

  "ChaCha20 and Poly1305 for IETF Protocols"
  https://tools.ietf.org/html/rfc7539

This uses a different key for each block.  Therefore  no chaining is
required, and random access is as easy as any other kind of access.
Poly1305 provides AEAD.

By way of contrast, AES is slower than ChaCha20 ... double-especially
if you include the cost of block-by-block rekeying, triple-especially
if you want to make it resistant to related-key attacks.

The ideal, almost always, is a new key per block.  A chaining mode is
just a kludge, just a fig leaf to conceal that fact that the underlying
block cipher cannot be rekeyed quickly enough and/or securely enough.

The services where encryption and authentication cannot wait until
the "end" of the "message" tend to be high-value services.  The
following story, albeit unverified, illustrates the sort of value
I'm talking about:
  http://thebulletin.org/okinawa-missiles-october8826

If you design a cryptosystem that works for real-time and/or random
access services, it will work OK for big static messages also.  However,
the converse is not true.

  I say "OK" rather than "perfectly" because I suspect that the
  real-time / interactive version may require ciphertext expansion
  beyond what would be required for a big static message.

  If so, then "acceptable authentication latency" ought to be treated
  as a dialable parameter.  Setting it to infinity at the start of the
  design process is a Bad Idea.

Encryption and authentication have different requirements.  For ordinary
telephony, the encryption blocks have to be quite small, to keep the
latency under control.  Stream ciphers, if carefully used, work fine.
The authentication blocks can be somewhat larger.  Millisecond-by-millisecond
authentication would be overkill.  Second-by-second authentication should
suffice.  Waiting until the end of the call is not acceptable.

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

As for making things resistant to misuse:  I am reminded of the following:

 ++ For every proverb, there is an equal and opposite proverb.

In this case, there is a proverb that says we should make it easy to
do the right thing, and hard to do the wrong thing.  However, there is
another proverb that says garbage in, garbage out.

For example, an ordinary lawnmower comes with a number of safety features.
Even so, it remains open to abuse in innumerable ways, and even if used
carefully there is some irreducible risk.  (Not to mention the urban legends
about the dangers of picking up a lawnmower and using it to trim hedges.)

There is a nontrivial issue here.  It is *much* more nuanced than saying:
 -- "it's unsafe to use a stream cipher",
 -- "it's safe to use AES, because only an idiot would use related keys", or
 -- "use XXX because it retains some modicum of security even if the IV is reused".

Instead I would say:
 ++ Sometimes there are good reasons for a stream cipher, but you have
  to be careful.
 ++ Sometimes there are good reasons for using a bunch of related keys,
  but you have to be careful.
 ++ Sometimes it's safe to use AES, but you have to be careful.
 ++ Sometimes it's OK to mow the lawn, but you have to be careful.
 ++ You can't make anything foolproof, because fools are so ingenious.

On 03/18/2017 03:58 AM, Jerry Leichter wrote:

>> We don't know how to compose secure modules into larger systems and maintain their security.

Indeed!

One can fantasize about a formal language that would specify what each
module requires and what it provides (in loose analogy to a package
management system like dpkg).

Right now I would settle for an informal language, perhaps a checklist.
For example, a certain mode:
 -- requires an IV that is unguessable
 -- requires a generic block cipher
     (which will bring in its own requirements)
 -- requires absence of transmission dropouts
     (this is because of chaining)
 -- provides message encryption
 -- does not provide authentication
 -- does not provide random access
 -- does not provide real-time service
 -- does not provide protection against traffic analysis