Feedback 'age and authentication': checking understanding and essentials

[cobratbq]

Hi, I read your blog post. I would like to check if my understanding of the core problem is correct, and possibly make a suggestion. In clarifying the problem(s), you mention a number of desirable properties. However, the core problem is that of authentication. As you mention, authentication is overloaded. So, I would like to check my understanding:

The principal issue is that you need a way of verifying whether the encrypted file originates from the original/expected sender", as opposed to someone else replacing the file as a whole, or figuring out the encryption key and making changes, or changing the recipients for the (otherwise unchanged) encrypted file. ("original" as-in: it got sent to you and you want to make sure it is the senders file. "expected" as-in: I created this file earlier, and now I want to be sure that my implicit assumption that this is "my file" is safe.)

The properties I figured out:

1. Ensure that the "sender" is indeed the producer.
2. Being able to work with large content (in small parts).
3. Being able to confirm that the whole file = all small parts = authentic content (from original sender).
4. Have the authentication mechanism "tied in with" the encrypted content s.t. you cannot simply strip or cut it off.

the idea

I'm no expert on this matter, but I was playing with the idea of "weaving the identity in" with the encrypted blocks as "Additional Data".

Let's say you create a hash digest x that is construct from the "critical parts of metadata (including sender public key to tie it in)" (I leave undefined for lack of knowledge.)
Let i be the index of a 64 KiB block of content.
Let dh_i be the hash derived from x, like dh_i = hash(i || x) (Notice that dh_i values are independent so random access to blocks is possible.)
Now, while encrypting each block of content, use dh_i as Additional Data for the 64KiB block of encrypted content.

Finally, encrypt x with the sender's private key (existing or some new one) and include that as part of the secret key.

Now, anyone can decrypt x with the sender's public key, derive the Additional Data for whatever encrypted content block is requested, and decrypt. In a way, the identity becomes a part of every block. IIUC then only x-encrypted-with-sender-private-key will be extra persisted data.

remarks

• Maybe an issue is that the sender public key now must be known?
• Maybe have some nonce for uniqueness. Again, I'll keep to the essense as I am no expert.
• Maybe you need to hash for more iterations, but (intuitively) I don't think that is relevant here.
• My first idea was playing with a hash-chain, but that seems pointlessly complicated.
• edit I may be missing the point completely as some other identity could encrypt the x value equally well, but I am still curious to any feedback.

[cobratbq]

Given The Cryptographic Doom Principle warnings regarding encrypt-and-authenticate, my suggestions to include select metadata is bad.
I am curious, though, if the general idea still stands: produce a hash (based on identity, as we want to ensure we know the sender/originator) and derive hashes for individual blocks. Then include the hashes in "Additional Data" of the AEAD.

[covert-encryption]

Only relying on AEAD for authentication, in particular by not using actual signatures, any recipient can forge the content. This property is called plausible deniability by Signal, although less confusingly it might be called repudiability as opposed to non-repudiation which is a property guaranteed by signatures. This is because plausible deniability is already overloaded to also mean not being able to prove that an encrypted container contains encrypted data if one doesn't have the right keys (e.g. VeraCrypt, Covert). I am using the latter meaning for deniability here.

Those who seek repudiability take this as an advantage but there are also uses where it is indeed necessary and useful to have non-repudiability, which more closely matches uses of hand-written signatures on documents. The recipient of the document wants to prove to others that the sender sent it, and this cannot be done with AEAD authentication alone.

In practice I would expect it not to be plausible that a recipient forged an authenticated message from the sender, say, if it went to a court. AFAIK there are no prior cases but I would think it to be almost certain that any court would disregard any claims by the sender to that he didn't send the message if it was discovered from the recipient as authenticated by the sender, unless the message content was clearly ridiculous or in conflict with other known facts. Courts routinely take as trusted emails and SMS with no authentication at all. This much weakens the main argument for repudiability.

The protection by repudiable authentication depends on 1-to-1 communication. The recipient knows that he didn't forge the message (although he could) so it must be from the sender. For messages with multiple recipients this becomes complicated because then recipients cannot know whether any of the other recipients forged it.

Thus, I argue that while there may be use for both modes, signatures are ultimately necessary. It appears to be established that nowadays one can use the same keys for signing and encryption (one of the design principles of Age, using SSH signing keys for Age encryption), making the process very convenient as long as the same program does both operations.

[cobratbq]

I was planning on a long explanation, but realized I might not comprehend all of what you're saying.

Only relying on AEAD for authentication ...

Are you saying that such a context -- a per-block hash derived from a single base hash -- added as 'additional data' is not sufficient protection of the ciphertext? Otherwise, my assumption is that: if we can sign (or encrypt-with-private-key) the single base hash and use that for individual blocks, that we are safe by: (and this is also where I am apparently missing something)

1. authenticating the single base hash
2. the derived hashes contribute to the protective ability of AEAD.

[covert-encryption]

I wasn't commenting on your scheme, but some notes on it:

• Why do you calculate dh_i instead of using the metadata directly as additional data? I gather this is only used to verify the file header, which contains the recipients? In that case it would suffice to directly use the header as additional data, on the first block only.
• Encryption with secret key and decryption with public key, as can be done with RSA keys, isn't possible with Elliptic Curves.
• The recipient could still decrypt any block and re-encrypt it with different content, keeping the header, x, AD, and the file key unchanged.

Looks like it doesn't provide non-repudiation property even if the second point was possible: the recipient can still forge the message and claim to a third party that the sender said something he didn't. Maybe I misunderstood something?

I don't know of any way to prevent a recipient from performing such alteration without actual signatures. At best you get repudiable schemes where the recipient knows that only him or the sender could've created the ciphertext, so it must be a genuine message.

[covert-encryption]

Covert uses the following principle for signatures, to avoid the PGP downfalls:

1. Create an AEAD encrypted and authenticated archive (think of Age)
2. Within a header inside that archive, list the public key(s) that the archive is going to be signed with
3. Sign the archive (or rather, sign a Blake2b hash of the archive, including its headers)
4. Write to file the archive followed by the signature (also encrypted for privacy, deniability and authentication)

Recipient decrypts the archive, finds inside a list of public keys (that he may or may not recognise) and verifies that the matching signatures are there after the archive itself and are valid for the corresponding public keys. The client then notifies the user of signatures and whether they are found in his address book. This also allows for key exchange, as the recipient can store the sender key on his address book (following TOFU principle). This follows the Doom principle in that everything is authenticated before other operations, although signature verification only comes after reading the archive.

Because the signature keys are listed inside the archive, which itself cannot be modified without breaking the signatures, there are no ways to tamper with the signatures (removal, replacement, alteration of data content). And without recipient secret keys the archive content cannot be read or altered in any way (plausible deniability too).

The recipient himself cannot reuse a signature in sending the message re-encrypted to someone else, fooling the new recipient to think the original sender signed a message intended for him (a known problem with sign then encrypt schemes such as PGP) because doing so would alter the headers, voiding the signature.

The recipient can however release the ciphertext and its file key to third parties who can then read the content and verify the signature.

[covert-encryption]

If the chunks AEAD encrypted were sufficiently large, something in the range of 16 megabytes, one could even have a separate signature per each block without too much overhead and even have signature verification during streaming, although streaming will always be vulnerable to cutoff attacks at block boundaries so it isn't pedantically 100 % correct either. I believe that full authentication plus signature verification error at the end is a reasonable compromise that gets the job done. Those who need to be maximally careful should not stream, but first verify the signature and then do a second pass to extract data, and others might rely on reverting the operations already done (e.g. deletion of files extracted).