chosen application attack

[dominictarr]

I recently realized that this construction has a chosen application attack

A chosen application attack means I can describe a reasonable application which when used over this protocol will have a security problem. If this application doesn't exist it's not a security problem, but we should set ourselves a very high bar for security design - so if our protocol requires applications to understand implementation details of the protocol then that is a security leak.

possible to replay a ciphertext

it's possible to repost someone elses ciphertext and it will be decryptable by the original recipients. If there was an application which automatically responded in some way to an encrypted message to it (which may include secret credentials, etc) then replaying the message could trigger some action to occur. (applications should be designed to be idempotent, but our protocol shouldn't not depend on the competence of developers in the application layer.

possible to alter a message and it still be valid (decryptable)

suppose there is a server running an application that performs an observable action when it decrypts a message, this provides an oracle that responds wether a message was valid. The adversary is able to observe this and guess that a particular message triggered that action (if messages are timed far apart, etc). The adversary is able to replay a message and trigger that action again. The adversary could modify the message to see how many recipients there are.

given:

let key = random(32)
let recipients = [curve25519_public,...] //up to MAX_RECIPIENTS=7
let one_time_key = curve25519()

The format of a private-box message is:

<24:nonce>
<32:one_time_key.public>
<49:box(key+recipients.length, recipient[i].public*one_time_key.secret, nonce)>*
<plaintext.length+16: box(plaintext, key, nonce)>

the adversary does not know one_time_key.secret, or any of the recipient[i].secret keys so cannot decrypt the message, however, they can guess the offset of the recipients, and construct messages where they replace a recipient with random bytes. This will leave the other recipients intact, so, by replacing one recipient at a time, and observing the oracle, the adversary detect which recipient slot the recipient is in, and then by reordering the recipient list, they can detect how many other recipients there are.

Since the recipient list is encrypted to each recipient, the adversary cannot change the recipient list length, but they can learn what the length is, thus decrypting 1 byte.

mitigations

protection from decryption oracle

To protect against the oracle attack, we encrypt the plaintext with box(plaintext, key, hmac(header, nonce)) where header is the nonce, one_time_key and encrypted recipient list. this would mean that altering one bit from the header (by changing a recipient or reordering them) would change the key to the message payload, so decryption would fail and the oracle would not be triggered.

protection from replay

To protect against the replay attack, we could use a nonce that is based on a random value, and also a deterministic value. In the context of secure-scuttlebutt, this could be the hash of the previous message and the author key.

recipients could be encrypted with box(key, recipient*one_time_key.private, hmac(previous+author, nonce)) this would mean that the attacker replayed the message, the recipients would fail to decrypt the message, because they would use the wrong key. The payload should also be encrypted with box(plaintext, key, hmac(previous+author, nonce))

use both mitigations?

that would be encrypting the plaintext with box(plaintext, key, hmac(header, hmac(previous+author, nonce))) this is probably not any advantage, but it would mean that not even the original author can create a valid message with a portion of the same ciphertext (partial replay).

[arj03]

Claiming no crypto-competence. The hash of the previous message sounds like a good idea.

[pfrazee]

Good catch