Signature scheme is broken

[hddqsb]

The signature scheme (which is based on signing the Poly1305 tags) is broken: When a file has multiple recipients, one recipient can carefully edit the blocks in a way that leaves the Poly1305 tags unchanged. Other recipients will not be able to detect the modification.

This is because Poly1305 is not a cryptographic hash function. Knowledge of the key allows an attacker to construct almost-arbitrary plaintexts that have a desired Poly1305 tag.

I don't have a proof-of-concept, but I think this is apparent from the definition of Poly1305. I can probably construct an example if requested.

Suggestion: Compute a cryptographic hash of the plaintext data, then sign that hash (and encrypt the signature). Some suggestions for hash functions:

• SHA-512 (which is also used internally by Ed25519)
• BLAKE2 (which may be faster than SHA-512).

It will probably be a little slower than Poly1305, but that can't be helped.

---

Also, the scheme used to encrypt the signature is very suspect. It uses filehash[:32] as the encryption key and hash(filehash + recipient_public_key)[:12] as the nonce. But filehash is public (it is a SHA-512 hash of the Poly1305 tags, which are appended to the ciphertext and are therefore public). So if an attacker knows the recipient's public key, the attacker can decrypt the signature block. And if the attacker doesn't know who the recipient is, they can use the signature block to test known public keys and determine if they are the recipient.

Suggestion: Encrypt the signature using a secret key.

---

Finally, a minor comment (which may soon be irrelevant): The scheme for calculating filehash repeatedly calls sha512, but there is no apparent reason for doing so. It would be faster to just compute the SHA-512 of the concatenation of all the values to be hashed.

[covert-encryption]

The actual signature system is in for overhaul. How multiple signatures are handled, how the block of signatures is stored, etc. None of this was posted in public yet, so it is good that you opened the discussion. We may continue it on this issue.

The signature scheme (which is based on signing the Poly1305 tags) is broken: When a file has multiple recipients, one recipient can carefully edit the blocks in a way that leaves the Poly1305 tags unchanged. Other recipients will not be able to detect the modification.

A known problem, planning to replace with Blake2b over the entire ciphertext or of header data and data content. One possiblity considered is to sign each block rather than only the full file, to prevent ever releasing plaintext for which the signature was invalid (at most you could get a truncated output). Otherwise you have that protection via authentication, but not in terms of signatures. For this I estimate that the blocks need to be a few megabytes each to keep the computational overhead low.

It will probably be a little slower than Poly1305, but that can't be helped.

Quite a bit, especially if using per block signatures. However, probably there is not too much overlap between needing signatures and needing very large files (at several gigabytes per second). Technically one could also omit the Poly1305 when signatures are used, but the savings of that are negligible and probably not worth the added complexity. Rather, the signature should stay an optional part that adds to AEAD authentication without touching that process.

Also, the scheme used to encrypt the signature is very suspect. It uses filehash[:32] as the encryption key and hash(filehash + recipient_public_key)[:12] as the nonce. But filehash is public (it is a SHA-512 hash of the Poly1305 tags, which are appended to the ciphertext and are therefore public). So if an attacker knows the recipient's public key, the attacker can decrypt the signature block. And if the attacker doesn't know who the recipient is, they can use the signature block to test known public keys and determine if they are the recipient.

The current plan is to simply add the signature within the normal block stream, after all other data, or in a similar fashion, and avoid the separate signature block(s).

Finally, a minor comment (which may soon be irrelevant): The scheme for calculating filehash repeatedly calls sha512, but there is no apparent reason for doing so. It would be faster to just compute the SHA-512 of the concatenation of all the values to be hashed.

The choice was based on minimizing the number of cryptographic primaries needed. As you mentioned, SHA-512 was already used in Ed25519. Further, it was taken that an implementation might include only a simple sha512(data) function that didn't support incremental updates.

[covert-encryption]

As for multiple signatures on one file, there are two distinct use cases

1. A group of people want to sign with their id keys
2. One person wants to sign but also includes his prior keys which the recipient might trust if he didn't know the latest one.

Number 1 has it its uses but it would require coordination among signaturees, and hasn't been given much tought in Covert. Namely, first all going-to-be signaturees' public keys would be encrypted within the archive by whoever sends it, the sender adds his own signature but everyone else would have to just add theirs later, modifying the file (assuming they don't want to share their secret keys to the system where the message is originally sent).

Number 2 is more common in key updates (remember, Covert piggypacks messages for automatic key exchange and discovery). In this case it would suffice the only sign the file with the new id key (the primary one), and rather than signing the file, sign the new primary key with all the old keys (this can go in index header). As a result the client knows to update user's identity key, even if it keeps track of older keys (this could also contain a flag for whether the old key is believed to be compromised or if it can still be trusted).

The current implementation would add a separate AEAD block for each of the signatures, making them more independent, more equal. In the new system there could be design be only one key signing all of the data, with other using other means to prove that they back up the original signatures (e.g. as external signature files, signing the file hash). Not sure how much practical use there even is for something like this.

Let me know if you think of any specific use cases where some other mode of operation would be required.