[exchange] Add "fingerprint"-like parameter

[cipriancraciun]

Add to the encryption a new mode that, besides the encrypted output, also outputs a kind of "fingerprint" for the encrypted message. Then to the decryption add a new parameter that allows one to specify this "fingerprint".

How does this work:

• it acts like a detached signature for the encrypted message;
• it binds not only the message, but also all the other parameters that went into the encryption (nonce, senders, recipients, secrets, pins, ballasts, oracles, etc.;)
• also it forces the one that decrypts the message be in the possession of the "fingerprint", else the message can't be decrypted;
• finally it serves as a way do verify that the message we actually expect was the one actually decrypted;

Properties:

• it doesn't need to be kept secret;
• if it's kept secret, it basically plays the same role as a normal "secret";
• if it's made public, it serves as a commitment that the output of the decryption is the one actually being decrypted; (i.e. make the fingerprint public, and at decryption time you can prove you've decrypted what you've promised to;)
• if during the encryption a fingerprint was requested, the decryption can't happen without also providing the fingerprint;

What use-cases can it serve:

• act as a "bearer token" for the message; knowing the "fingerprint" is mandatory for the decryption, and at the same time it can verify what was decrypted;
• one can save the encrypted file on a public store (like S3), and at decryption time we are sure we are decrypting what we are expecting (because someone, or even the original sender, can't replace the file without breaking the fingerprint;)

[hakavlad]

it acts like a detached signature for the encrypted message;
it binds not only the message, but also all the other parameters that went into the encryption (nonce, senders, recipients, secrets, pins, ballasts, oracles, etc.;)
also it forces the one that decrypts the message be in the possession of the "fingerprint", else the message can't be decrypted;
finally it serves as a way do verify that the message we actually expect was the one actually decrypted;

But it's just MAC tag!

[cipriancraciun]

But it's just MAC tag!

@hakavlad not quite.

Let's look at how encrypt-the-MAC works:

shared_key := PBKDF (...) # the user provided secrets
message := ... # the user provided plain-text

encryption_key = KDF (shared_key, domain : "encryption")
authentication_key = KDF (shared_key, domain : "authentication")

encrypted := encrypt (encryption_key, message)
mac := MAC (authentication_key, encrypted)

output := encrypted || mac

Now, technically, if one doesn't have the MAC, one can still decrypt the original message:

shared_key := PBKDF (...) # the user provided secrets
encrypted := ... # only the encrypted part of the output, removing the mac

encryption_key := KDF (shared_key, domain : "encryption")

message := decrypt (encryption_key, encrypted)

---

Then there is a second property I'm looking for: the fingerprint binds not only the cryptographic keys, but also the message. I.e. if one tries to decrypt with the wrong password, or one is given the wrong cipher text, the decryption results in nonsense.

If I'm not mistaken although Poly1305 is often used for computing the MAC in AE(AD) schemes, it lacks the extra property that it doesn't also bind the key to the MAC, thus the same cipher text can be decrypted under different keys, to different outputs, and still pass the MAC. (This article describes it best https://soatok.blog/2024/09/10/invisible-salamanders-are-not-what-you-think/). (This can be solved by using something like Blake3, or any other cryptographic hash.)

---

Thus, the "fingerprint" I'm looking for has this extra property that without it, one can't decrypt at all. (One can still ignore to verify that the input fingerprint is actually the fingerprint belonging to the output message, but they still must have it.)

For example this is the simplest form of "fingerprint" (I can think of):

shared_key := PBKDF (...) # the user provided secrets
message := ... # the user provided plain-text

fingerprint_key := KDF (shared_key, domain : "fingerprint")
fingerprint := HMAC (fingerprint_key, message)

packet_key := HMAC (shared_key, fingerprint)

encryption_key := KDF (packet_key, domain : "encryption")
authentication_key KDF (packet_key, domain : "authentication") # see note below

encrypted := encrypt (encryption_key, message) # see note below
mac := MAC (authentication_key, encrypted)

output := encrypted || mac

save (output)
print (fingerprint)

shared_key := PBKDF (...) # the user provided secrets
encrypted, mac_expected := ... # the output of the previous process
fingerprint_expected := ... # the output of the previous process

packet_key := HMAC (shared_key, fingerprint_expected)

encryption_key := KDF (packet_key, domain : "encryption")
authentication_key KDF (packet_key, domain : "authentication") # see note below

mac_computed := MAC (authentication_key, encrypted)
constant compare of mac_computed and mac_expected, fail if not equal

message := decrypt (encryption_key, encrypted)

# optional, see note below
fingerprint_key := KDF (shared_key, domain : "fingerprint")
fingerprint_computed := HMAC (fingerprint_key, message)

constant compare of fingerprint_computed and fingerprint_expected, fail if not equal

• the fingerprint is actually the MAC in MAC-then-encrypt;
• the fingerprint doesn't leak information about the message, provided the HMAC is secure;
• the MAC is completely optional in this case, because it plays the same role of the fingerprint, however
• in the case the message is passed through additional processing before being encrypted (like for example being compressed or padded), then the MAC protects the processed-and-encrypted data, while the fingerprint protects the original message;
• technically one can skip the extra fingerprint verification step, because unless HMAC is broken, if one touches either the provided secrets or the cipher-text, the decryption would fail;

---

What would be a valid use-case for such a "fingerprint" that can't be solved by a plain MAC:

• suppose you have an automated backup system that should run unattended, which just mirrors the content to an S3 bucket; the only required configuration is the S3 bucket and S3 credentials;
• you don't want to hard-code these two pieces of information in the backup script (or anywhere on the system); suppose it fits your threat model if you can store these parameters encrypted on a separate host in the same LAN, and store the encryption key on a USB thumb drive that is permanently connected to the system; (the idea is that if someone runs with your computer, they might have the decryption key, but they don't have access to get the encrypted parameters;)
• unfortunately, your key is compromised (say someone copies your USB thumb drive), and you are not aware of the compromise; the attacker could even read the encrypted parameters, and they could obtain the S3 bucket and S3 credentials, thus theoretically gain access to the existing backups;
• luckily, they weren't able to access the actual system that does the backup (thus no data can be leaked from the live system), and you've taken measures so that the S3 credentials in question can only be used for uploads, not downloads (thus no data can be leaked from the S3 bucket under the exposed credentials); (i.e. the S3 bucket is write-only;) (granted, the attacker could DoS your bank account by uploading random noise in your S3 bucket;)
• however, if the attacker can compromise the other remote system where your encrypted parameters are found, and knowing your encryption key, they can create a new S3 bucket and S3 credentials, on their own AWS account, and encrypt a new parameter file with the replaced S3 details;
• thus, the next time your backup runs, it happily uploads your data to a bucket the attacker controls;

Now, in the example above a MAC didn't help, because the attacker knew the encryption key, and thus it could swap the configuration by creating a new encrypted parameters file with a new correct MAC.

However, if you would have made a minor change to your backup system, you would have been protected: if you would have hard-coded a hash of the actual decrypted parameters file (domain separated preferably), even if the attacker gets your encryption key and tries to replace the parameters file, it would have failed the hash check and the backup system would have refused to upload your data to the attackers bucket.

(Alternatively one could have used a signature, hard-code the signer public-key, however now the attacker could try to steal your signature key and fool the backup system this way.)

(Alternatively one could have hard-coded the MAC, but then, if the MAC isn't key binding, the attacker could have also swapped your encryption key which lives on the USB stick.)

(Why does the encryption key live on the USB stick? Its easier for the plot, however you still need to store something somewhere ready for unattended use -- on the disk, wrapped via the TPM, etc. -- regardless it just makes the key harder to exfiltrate, not impossible.)

How would my "fingerprint" help in such a scenario:

• suppose you can hard-code the "fingerprint" of the parameters file in the backup script;
• this fingerprint gives nothing away about the plain-text message;
• it is assured that one and only one message can be decrypted for the given fingerprint; thus either you get your original S3 parameters, or you get nothing;
• plus, this fingerprint is a hard-requirement to actually decrypting the message; (you can think of it as a key if it's kept confidential;)