Is there an authenticated encryption scheme where the recipient can attribute the message to a single sender?

Question

With a standard authenticated encryption scheme (or MAC), Alice and Bob share a symmetric key. When Alice sends something to Bob, Bob can check that it is authentic. At that point, Bob can deduce that the message must have been sent by someone who knows the key, i.e., it must have been sent by Alice or Bob.

How can Bob verify that the message was sent by Alice? (not by Alice or Bob)

In particular, standard authenticated encryption only proves that the message come from someone in a trusted group (the group of people who know the symmetric key). I'd like a scheme where the recipient can verify which individual sent it.

In other words, I'd like to get all the current guarantees of AE, plus ability to authenticate which entity sent the message (only one particular entity must have been able to authenticate the document, unless their key is compromised). It's OK if it needs to use public-key technology. Ideally, such a mode would be single pass (like OCB), but hopefully not patent encumbered or GPL tainted (LGPL or weaker is ok). Getting authenticated associated data would be a bonus.

Or maybe I just need to encrypt (using a plain randomized mode, provides confidentiality only) then sign the ciphertext+associated data (which provides integrity, authentication and knowledge of the sender)?

Answer 1

The idea that cryptography alone can provide non-repudiation is a myth. I realize it is one that is taught in many crypto textbooks -- but the textbooks are wrong.

See, e.g., my answer here and here.

I could suggest some constructions (e.g., sign the message, append the signature to the message, then encrypt it using an authenticated encryption mode of operation): but it's pointless, as none of these constructions can provide non-repudiation on their own. In particular, the hardest parts of providing non-repudiation have nothing to do with cryptography or mathematics; they have to do with legal aspects, as well as endpoint security.

---

Edit (11/20): The question has been clarified to make clear that it is not seeking non-repudiation, but merely to know that the message has come from a single party. OK, then, here's one construction: sign the message, append the signature to the message, then encrypt it using an authenticated encryption mode of operation.

You could alternatively encrypt the message using authenticated encryption and then sign the ciphertext, but I don't recommend it. It could work, but it has some subtle pitfalls in some contexts, because the signature does not prove that the sender was aware of the context of the plaintext. For instance, suppose Alice's SSH client sends the message "Dear SSH server, please append my public key to /root/.ssh/authorized_keys -- and you can know that I am authorized because I know the root password is lk23jas0" (encrypted then signed with Alice's public key), and the SSH server acts on it if the root password is correct. Then Bob can eavesdrop, capture this message, strip off Alice's signature, sign the ciphertext with his own public key, and send it to the SSH server, obtaining root-level access even though Bob didn't know the root password.

Answer 2

To get non-repudiation, you must have a "proof" which can be used against the signer himself. Symmetric cryptography, by itself, will not help you there, because a cryptographic proof can only come from some "secret" which is under exclusive control of the signer, and the symmetric model assumes that there is a shared secret between two entities. The concept of non-repudiation makes sense if the signer wants to default on his signature, and the receiver of the signature sues him and wants to convince a third party (the judge) that the signature is genuine and binding. This is a scenario where both parties are adversaries with each other. In that context, there is very little provability that can be extracted from a secret value that they both know.

There are systems which provide non-repudiation and still use symmetric cryptography. That's what happens (happened ?) in payment smart cards: the cards "signs" the transaction by computing a MAC over it, with symmetric cryptography; the MAC key is user-specific, but known to both the card and the bank. Such transactions are binding in a legal way (so there is "non-repudiation") because the Law says so; but the system works in practice because it is not easy to circumvent. In particular, the bank is assumed to be honest and not to frame its customers; this assumption is not free, because it comes at the price of very heavy controls and auditing systems on the bank side.

One cornerstone of non-repudiation, as existing laws on digital signatures put it, is the notion of exclusive control. What the signer uses to sign must be proven to be usable by the signer only. In the banking smart card example, this is obtained through several mechanisms, including the inherent robustness of the card, the PIN code handling, and the expensive verifications and safeguards which are performed on the bank side of the transaction. These verifications can be made cheaper if the whole system uses asymmetric cryptography, because maintaining exclusive control of an asymmetric private key is easier than doing the same with a shared secret. For instance, in an asymmetric system, you can arrange for the private key never to leave the device on which it was generated, which makes device initialization easier, especially when already deployed in the field.

(Note that "easier" does not mean "easy".)

Anyway, non-repudiation is about people or at least legal entities; cryptography sees keys. Binding entities to key control is a complex business; one way to do it is PKI. People involved in PKI know that PKI is 5% asymmetric cryptography, 95% procedures. Getting the crypto right is the easy part. Asymmetric cryptography is not sufficient to achieve non-repudiation; and it is not strictly necessary either, but, in the current legal context, you will find that obtaining non-repudiation is even harder if your toolbox does not include asymmetric cryptography.

---

To say it differently, you can get non-repudiation out of an AE mode, under the same conditions that you would get non-repudiation out of a MAC. This is doable, in fact it has been done, but in a heavyweight framework of procedures, laws, controls, and a lot of money thrown at it. Banks did it with symmetric cryptography because when such systems began to be deployed (in the late 1980s in France), cards which could do asymmetric cryptography were very expensive.

Answer 3

There are no non-repudiation services without using of digital signature.

Or maybe I just need to encrypt (using a plain randomized mode, provides confidentiality only) then sign the ciphertext+associated data (which provides integrity, authentication and non-repudiation)?

Yes, it will be enough. Or you can sign, then encrypt to secure information about signer.

Answer 4

There are two approaches: either using symmetric-key cryptography, or public-key cryptography.

Symmetric-key cryptography. When Bob receives an authentic message that has been authenticated by a key known only to Alice or Bob, Bob can deduce that the message must have come from either Alice or Bob. Therefore, if Bob wants to verify that this message came from Alice, he only needs to verify that it didn't come from himself. There are many ways to achieve this goal.

For instance, one way is that Alice and Bob can agree to prefix each message with a "direction bit": when Alice sends a message, she'll prefix it with a 0 bit, and when Bob sends a message, he'll prefix it with a 1 bit. Bob can make sure that he always prefixes with a 1 bit (he never sends anything with a 0-bit prefix). Then, when Bob receives an authentic message, he can check that it is prefixed with a 0-bit. (If it is prefixed with a 1-bit, Bob knows that he is under attack and can drop the message.) This is enough for Bob to verify that the message came from Alice, or someone Alice shared her key with -- in particular, he knows it didn't come from himself, and he knows he didn't share the key with anyone other than Alice.

Another way is to prefix each message with a random 128-bit identifier. Bob can keep track of all of the identifiers he has ever used to send a message. When Bob receives an authentic message, he can verify that the identifier on that message does not match any identifier he is previously used. This is enough for him to verify that the message must have come from Alice (or someone she shared the key with), for the same reasons.

Cryptographic protocols typically treat it as an implicit to provide this kind of protection as part of the protocol, so if you are using an existing protocol, you usually won't need to add this mechanism on your own. This is basically known as providing security against reflection attacks. A reflection attack is where a message Bob sent is "reflected" back to him, i.e., the message is intercepted and replayed back to Bob. The schemes I outlined above are standard defenses against reflection attacks. And, if the key is shared among only 2 parties, then stopping reflection attacks is enough to achieve your desired goal.

This approach is only really viable if the symmetric key is shared among 2 parties (it is not workable if the key is shared among $n>2$ parties). However, the benefit is that it doesn't require use of public-key cryptography. Therefore, it doesn't impose any significant performance overhead.

Public-key cryptography. Alternatively, you can use public-key cryptography. Assume that every party has their own public/private keypair, and every party knows the authentic public key of every other party (perhaps through a PKI, or some other means). Then this problem is easy to solve: when Alice wants to send an authenticated message to Bob, she signs and encrypts the message. In particular, she prepends Bob's name to the message, signs this using her private key, appends her signature to the message, encrypts the whole thing under Bob's public key, and sends the resulting ciphertext to Bob. Bob can decrypt, verify the signature, and confirm that this indeed came from Alice (or someone she shared her private key with).

This is just the standard sign-then-encrypt scheme for point-to-point communication with public-key cryptography. Make sure you use an IND-CCA2-secure public-key encryption scheme and a UF-CMA-secure public-key signature scheme (i.e., one that is secure against existential forgery attack).

---

For some intricacies about whether to sign first or encrypt first, you might enjoy this: Defective Sign & Encrypt in S/MIME, PKCS#7, MOSS, PEM, PGP, and XML.

Answer 5

The type of scheme desired here would be Signcryption.

Signcryption fulfills the role of a digital signature while simultaneously encrypting the data. It appears that there are some primitives in Elliptical Curve Cryptograpy which will allow for this.

Answer 6

Or maybe I just need to encrypt (using a plain randomized mode, provides confidentiality only) then sign the ciphertext+associated data (which provides integrity, authentication and non-repudiation)?

That is not enough. You need to encrypt (confidentiality only) then sign
a commitment to the cipher key $\:$ + $\:$ ciphertext $\:$ + $\:$ associated data $\;\;$.
(The other parties need to have decommit strings for
that commitment, in addition to the cipher key itself.)