7
$\begingroup$

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)?

Improve this question
$\endgroup$
4
  • $\begingroup$ Your question is not very clear, are you looking for some symmetric encryption scheme that provides non-repudiation ? symmetric or asymmetric are encryption algorithms, where as non repudiation, integrity, confidentiality are properties of security system. few encryption algorithms may give these properties out of box, like Encrypting with one's private key may give non-repudiation and encrypting with someones public key would give confidentiality $\endgroup$
    – sashank
    Nov 19, 2012 at 5:33
  • $\begingroup$ I'm looking for an asymmetric scheme which provides the combined benefits of authenticated encryption (presumably with a symmetric key and some block cipher), as well as digital signatures (using an asymmetric key). The symmetric key would be shared, and the public key would be well known. It may even be the case that the symmetric key is sent encrypted with the public key of the signer. I'm wondering if there is something more efficient than encrypting then signing (much like OCB is faster than doing encrypt then MAC). $\endgroup$
    – Robert I. Jr.
    Nov 19, 2012 at 6:07
  • $\begingroup$ I'm confused. You say you are looking for an asymmetric scheme but then say that the symmetric key would be shared. Is it asymmetric, symmetric, or are you looking for a combination? $\endgroup$
    – mikeazo
    Nov 19, 2012 at 14:12
  • $\begingroup$ Looking for a combination... you wouldn't usually want to encrypt a large piece of data using only asymmetric keys, anyway, since it would be incredibly slow. Which is why you would typically use a stream cipher and the block cipher key would be protected with the asymmetrical key, allowing you to transmit a long encrypted text to a recipient with only their public key without taking ages to encrypt/decrypt... $\endgroup$
    – Robert I. Jr.
    Nov 19, 2012 at 20:24

6 Answers 6

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I should have clarified... I only wanted non-repudiation for it's unspoofable identification properties (barring a stolen key), not for the claim that the signer cannot reneg on a promise contained in the payload. I realize that a fully-fledged non-repudiation system would really require physical witnesses and a trusted third party (much like a notary in real life). In a cryptography only approach, anyone could claim "Oh, my keys were stolen, but I didn't know about it at the time. I didn't sign that." $\endgroup$
    – Robert I. Jr.
    Nov 20, 2012 at 17:40
  • $\begingroup$ I was mostly asking the question because even though AE provides 'authentication', it only provides authentication that someone in the trusted group produced the message. Whereas digital signatures provide authentication that a particular key holder produced the message. $\endgroup$
    – Robert I. Jr.
    Nov 20, 2012 at 17:43
7
$\begingroup$

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.

Improve this answer
$\endgroup$
0
1
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Do the same issues with MAC-then-encrypt apply to sign-then-encrypt? (e.g. crypto.stackexchange.com/questions/202/…) Though I suppose it could be sign-then-Authenticated Encryption. $\endgroup$
    – Robert I. Jr.
    Nov 19, 2012 at 20:19
  • $\begingroup$ That's not the same. MAC is based on secret key and cannot compromise sigher's identity. $\endgroup$
    – Pavel Ognev
    Nov 19, 2012 at 23:14
  • $\begingroup$ That wasn't the question he asked. The issue with MAC-then-encrypt is chosen ciphertext attacks. $\endgroup$
    – Stephen Touset
    Nov 20, 2012 at 4:40
  • 2
    $\begingroup$ To answer the question in his comment: $\:$ Yes, that issue also applies to sign-then-encrypt. $\;\;$ $\endgroup$
    – user991
    Nov 20, 2012 at 6:40
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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.)

Improve this answer
$\endgroup$
5
  • $\begingroup$ Not enough why? If the signature encapsulates the ciphertext then if the signature is valid, then the ciphertext has not been modified, which means the signer must have used the same symmetric key. Unless I'm misunderstanding something... $\endgroup$
    – Robert I. Jr.
    Nov 19, 2012 at 20:17
  • $\begingroup$ "the same symmetric key" as what? $\:$ The receiver could present [signed ciphertext + $\hspace{1 in}$ associated data] along with any of $2^k$ possible keys. $\;\;$ $\endgroup$
    – user991
    Nov 19, 2012 at 22:51
  • $\begingroup$ The same symmetric key as the one used to encrypt the payload, which of course you can't verify until decryption, which is a flaw. I was assuming that the symmetric key is a shared secret. Though you're actually right about the commitment for another reason, too. Simply signing the ciphertext allows an existential forgery where the attacker can intercept the blob, strip the signature, and then resign with any other private key as anyone else in the system. $\endgroup$
    – Robert I. Jr.
    Nov 20, 2012 at 17:33
  • $\begingroup$ In that case, "the signer must have used the same symmetric key (as the one used to encrypt the payload)" to do what? $\:$ I don't see how your suggested attack would work at all, as the attacker can learn the message by just decrypting the ciphertext (since everyone in the system has the symmetric key), and then send the message as itself. $\;\;$ $\endgroup$
    – user991
    Nov 20, 2012 at 19:48
  • 1
    $\begingroup$ Because you "only wanted non-repudiation for it's unspoofable identification properties (barring a stolen key), not for the claim that the signer cannot reneg on a promise contained in the payload", you don't need a commitment to the key to be part of what was signed. $\:$ In that case, sign-then-AEAD (en.wikipedia.org/wiki/AEAD_block_cipher_modes_of_operation) would work better. $\hspace{.8 in}$ $\endgroup$
    – user991
    Nov 20, 2012 at 19:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.