[Cryptography] Encrypt then Authenticate, Why not have both?

Phillip Hallam-Baker phill at hallambaker.com
Fri Jul 6 14:11:50 EDT 2018

So I have been struggling with that perennial question of whether to
Encrypt then Authenticate or Authenticate then Encrypt. There are pros and
cons to both and there are equally vehement exhortations on both sides.

One factor that does play into this is that it is easier to create proofs
of security for one than the other. While that has to be considered as a
factor, I don't think it should be the only factor. I studied formal
methods for my doctorate, I know their strengths, I also know that they
have weaknesses. In particular there is a tendency to design to the
capabilities of our proofs rather than to what is secure and robust in

The problem with Encrypt then Authenticate is that there is no evidence
that the party authenticating saw the actual data. This purportedly creates
serious protocol level attacks. Though I don't quite see how they produce
practical issues unless there is another failure in the protocol.

The problem with Authenticate then Encrypt is that only parties that are
able to decrypt the data can authenticate it. I would like to be able to
check the signature on a message before I let it near any sort of private

So here is what I have come up with.

A DARE container is a sequence of records presented in an append only log
format. The log format provides Merkle Tree and Chain digest capabilities.

Individual records from a container may be extracted and presented as a
DARE message which is a self contained unit containing all the
cryptographic annotations (signatures, recipient blobs, etc) required for

Records and messages consist of a header, a body and an optional trailer.
Headers may contain multiple encrypted data sequences and even encrypted
headers. This allows a recursive approach to encrypting the body data for
Kimono protocols.

Encryption and Signature may be applied to individual records or to
non-contiguous records in the same container. The only constraint being
that the key exchange has to be written before the first record encrypted
under it and the signature has to be written on or after the last.

This provides a mechanism that is perfect for encrypting log files. A
single key exchange can be amortised over a sequence of log entries. It is
even possible for two different processes to write to the same log file
simultaneously, provided that the individual record writes are smaller than
the atomic write primitive of the O/S (believed to be 4096 bytes for
everything that matters).

The cryptographic processing pipeline for the body has four elements:

MAC -> Encrypt -> Package -> Digest

Keys and IVs are derived from a master secret by means of a KDF and salt.
Each record has a unique salt of at least 128 bits. Each encrypted data
item (other than the body) has a unique salt suffix. Thus erasing the salt
is sufficient to prevent decryption of the encrypted data and does not
disrupt validation of the container contents using the digest.

Since this construction means that a party cannot know the MAC Key unless
they know the Encryption key and vice versa, I suspect the order of MAC and
Encrypt no longer matter.

The Digest is only computed over the message body and nothing else. If an
application needs to sign something, it has to present it as a message body.

This requirement is important as it allows headers to be manipulated after
the fact. Signatures can be added or removed, A container can be redacted
so that it only contains a subset of authenticated records and the
cryptographic data moved to the position it is required. This could prove
useful in file archive formats, an application updating itself just syncs
the records that have been updated since it last synchronized, ignoring any
that were deleted before it could synchronize. If storage is scarce, the
archive may be periodically purged to eliminate deleted items.

Great care has been taken to ensure that DARE Messages can be written out
in a streaming mode without the need for unbounded buffering of data. This
is not true of containers which requires the final length of a record body
to be known before the record is written. So streaming of video data would
require streams to be split across multiple records.

Anyway, so to my question. The scheme described provides the cryptographic
capabilities I require but is subject to the semantic substitution attack
in which Mallet signs a message that was written by Alice and this allows
him to impersonate Alice 'somehow'. One possible approach to preventing
this attack would be as follows:

* Header of first signed record contains the list of signing keys that will
be used to sign the message.
* The digest of this value feeds into the message Salt in some verifiable
* The Salt feeds into the signature in some fashion.

If the protocol requires the signer to be authorized by the party that
performed the encryption, it checks to see that the key is listed.

I am also looking into ways of locking the Salt values into the payload
digest value so that it is possible to verify container structure
efficiently without calculating the payload digest.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20180706/edde2cb7/attachment.html>

More information about the cryptography mailing list