Subject: weak authentication issue with rfc5083

From: Trevor Freeman <[email-masked]>
Date: Mon, 5 May 2008 19:52:08 +0000

We have identified a potential for spoofing when using rfc5083.

Rfc5083 computes a message HMAC over the content using the authenticated encryption algorithms. The message HMAC is calculated based on the content and the content encryption key (CEK).

A number of allowed key management techniques derive a key encryption key (KEK) which can be used to authenticate the sender e.g. Static-Static Diffie Hellman, Kerberos shared secret, shared password. The KEK is used to encrypt the CEK per recipient.

However when the integrity of the message is validated via the message HMAC, the sender only demonstrates knowledge of the CEK to the recipient.

Any other recipient knows the CEK so can construct another message using the same CEK and compute the new HMAC and reuse the encrypted KEK data from the original message. For example:

Alice sends a message to Bob and Mallet. Alice uses  different KEK's  for both Bob and Mallet to encrypt the CEK. Bob decrypts the CEK using  his KEK. The message decrypts and the HMAC checks out so Bob think the message is from Alice because only Bob and Alice know the KEK.

Mallet is the recipient of the original message so he can use his KEK to learn the message CEK. Mallet then  constructs a new message and encrypts it using the same CEK as the original message. Mallet copies Bobs  KEK recipient Info from Alice's message which contains the same encrypted CEK. Because Mallet knows the CEK he can also compute the correct HMAC for the new message. Mallet sends the new message to Bob. Bob again uses his KEK to discover the CEK and successfully decrypts the message and the HMAC check out so Bob thinks this new message is also from Alice.

This issue only applies when there are multiple recipients. The motivation to use the new authenticated encryption is to improve performance so solutions like bifurcating messages to use different CEK or signing the message are counterproductive.

We need an additional structure to allow the sender to demonstrate knowledge of both the KEK and CEK per recipient when sending to multiple recipients.
What is the consensus to resolve this?

We can version 5083 to document the new structure or we can do document the new structure via a standalone document.

---

From: "Jim Schaad" <[email-masked]>
Date: Mon, 5 May 2008 13:23:22 -0700

Trevor,

The same issue also occurs for AuthenticatedData in RFC 3852.  This has been
known for a long time.

I am not sure how a demonstration of the KEK would solve this issue however.
The only way that I know to actually deal with this problem is to place the
computed MAC under encryption for each recipient.

Jim

From: [email-masked] [mailto:[email-masked]]
On Behalf Of Trevor Freeman
Sent: Monday, May 05, 2008 12:52 PM
To: [email-masked]
Subject: weak authentication issue with rfc5083

Rfc5083 computes a message HMAC over the content using the authenticated
encryption algorithms. The message HMAC is calculated based on the content
and the content encryption key (CEK). 

A number of allowed key management techniques derive a key encryption key
(KEK) which can be used to authenticate the sender e.g. Static-Static Diffie
Hellman, Kerberos shared secret, shared password. The KEK is used to encrypt
the CEK per recipient.

However when the integrity of the message is validated via the message HMAC,
the sender only demonstrates knowledge of the CEK to the recipient.

Any other recipient knows the CEK so can construct another message using the
same CEK and compute the new HMAC and reuse the encrypted KEK data from the
original message. For example:

Alice sends a message to Bob and Mallet. Alice uses  different KEK's  for
both Bob and Mallet to encrypt the CEK. Bob decrypts the CEK using  his KEK.
The message decrypts and the HMAC checks out so Bob think the message is
from Alice because only Bob and Alice know the KEK.

Mallet is the recipient of the original message so he can use his KEK to
learn the message CEK. Mallet then  constructs a new message and encrypts it
using the same CEK as the original message. Mallet copies Bobs  KEK
recipient Info from Alice's message which contains the same encrypted CEK.
Because Mallet knows the CEK he can also compute the correct HMAC for the
new message. Mallet sends the new message to Bob. Bob again uses his KEK to
discover the CEK and successfully decrypts the message and the HMAC check
out so Bob thinks this new message is also from Alice.

This issue only applies when there are multiple recipients. The motivation
to use the new authenticated encryption is to improve performance so
solutions like bifurcating messages to use different CEK or signing the
message are counterproductive.

We need an additional structure to allow the sender to demonstrate knowledge
of both the KEK and CEK per recipient when sending to multiple recipients.

We can version 5083 to document the new structure or we can do document the
new structure via a standalone document.

---

From: Trevor Freeman <[email-masked]>
Date: Mon, 5 May 2008 20:40:19 +0000

Hi Jim,
You can demonstrate knowledge of both HMAC and KEK fairly simply per recipient e.g. by concatenating the KEK with the message HMAC and hashing the result. Since Mallet does not know the KEK they cannot compute the new hash. This fix works for both 3852 and 5083.

Trevor

From: Jim Schaad [mailto:[email-masked]]
Sent: Monday, May 05, 2008 1:23 PM
To: Trevor Freeman; [email-masked]
Subject: RE: weak authentication issue with rfc5083

Trevor,

The same issue also occurs for AuthenticatedData in RFC 3852.  This has been known for a long time.

I am not sure how a demonstration of the KEK would solve this issue however.  The only way that I know to actually deal with this problem is to place the computed MAC under encryption for each recipient.

Jim

From: [email-masked] [mailto:[email-masked]] On Behalf Of Trevor Freeman
Sent: Monday, May 05, 2008 12:52 PM
To: [email-masked]
Subject: weak authentication issue with rfc5083

---

From: Trevor Freeman <[email-masked]>
Date: Mon, 5 May 2008 21:03:23 +0000

Another suggestion is to use the kek to wrap the hmac just like you wrapped the CEK.

From: [email-masked] [mailto:[email-masked]] On Behalf Of Trevor Freeman
Sent: Monday, May 05, 2008 1:40 PM
To: Jim Schaad; [email-masked]
Subject: RE: weak authentication issue with rfc5083

Hi Jim,

Trevor

Trevor,

Jim

---

From: Daniel Brown <[email-masked]>
Date: Mon, 5 May 2008 18:09:29 -0400

Trevor,

Essentially the same problem was commented upon in RFC 3278:

http://tools.ietf.org/html/rfc3278#section-4.1.2

but no solution was provided other than to use separate AuthenticatedData per recipient. There are some other possible solutions, however.

For example, in the case of Diffie-Hellman, the input into the KDF used to compute the KEK from the raw DH secret can be include the MAC tag, which prevents message substitution.  See Section 5 of http://eprint.iacr.org/2005/056 for more discussion.

Best regards,

                Dan

From: [email-masked] [mailto:[email-masked]] On Behalf Of Trevor Freeman
Sent: Monday, May 05, 2008 3:52 PM
To: [email-masked]
Subject: weak authentication issue with rfc5083

---

From: "Jim Schaad" <[email-masked]>
Date: Mon, 5 May 2008 15:38:14 -0700

The downside of this would be that you could no longer do one pass encoding.
You would need to compute the HMAC prior to computing the recipient infos.

Jim

From: Trevor Freeman [mailto:[email-masked]] 
Sent: Monday, May 05, 2008 2:03 PM
To: Trevor Freeman; Jim Schaad; [email-masked]
Subject: RE: weak authentication issue with rfc5083

Another suggestion is to use the kek to wrap the hmac just like you wrapped
the CEK.

Hi Jim,

You can demonstrate knowledge of both HMAC and KEK fairly simply per
recipient e.g. by concatenating the KEK with the message HMAC and hashing
the result. Since Mallet does not know the KEK they cannot compute the new
hash. This fix works for both 3852 and 5083.

Trevor

Trevor,

Jim

---

From: Trevor Freeman <[email-masked]>
Date: Mon, 5 May 2008 22:41:31 +0000

Not if you send the recipient info's with the encrypted hmac as an unauthenticated attribute.

Trevor

From: Jim Schaad [mailto:[email-masked]]
Sent: Monday, May 05, 2008 3:38 PM
To: Trevor Freeman; [email-masked]
Subject: RE: weak authentication issue with rfc5083

The downside of this would be that you could no longer do one pass encoding.  You would need to compute the HMAC prior to computing the recipient infos.

Jim

Hi Jim,

Trevor

Trevor,

Jim

---

From: [email-masked] (Peter Gutmann)
Date: Tue, 06 May 2008 18:47:00 +1200

>original message. For example:

Uhh, AuthEnv doesn't specify any use of HMAC, it can be used with HMAC if
required (the other use is with a combined MAC+encrypt mode), but in the HMAC
usage the HMAC and CEK keys are derived from a single key using a PRF, so
knowledge of the CEK doesn't give you the HMAC key, and vice versa.  It was
specifically designed that way to prevent rollbacks where you strip off the
MAC and rewrite it as plain encrypted data.  Or have I misunderstood your
point?

Peter.

---

From: "Jim Schaad" <[email-masked]>
Date: Tue, 6 May 2008 12:29:43 -0700

Peter,

I believe you have misunderstood the issue that Trevor raised.

His problem is:

1.  I send you and him a single Authenticated Message.
2.  He takes the common CEK in the original message, uses it to create a MAC
on an new message and then sends it on to you.

As is always true with Authenticated messages, there is no proof of origin.
He worries that you might be confused and believe the second messages was
from me rather than from him.  Since they both use the same CEK that is not
a factor that could be used to distinguish them.

Jim

> -----Original Message-----
> From: [email-masked] [mailto:owner-ietf-
> [email-masked]] On Behalf Of Peter Gutmann
> Sent: Monday, May 05, 2008 11:47 PM
> To: [email-masked]; [email-masked]
> Subject: Re: weak authentication issue with rfc5083
> 
>

---

From: "Jim Schaad" <[email-masked]>
Date: Tue, 6 May 2008 12:30:47 -0700

I would have an issue with this since could be silently stripped without the
recipients or senders knowledge.  Thus I don't see it as solving your
problem.

Jim

Sent: Monday, May 05, 2008 3:42 PM

Not if you send the recipient info's with the encrypted hmac as an
unauthenticated attribute.

Trevor

Jim

Hi Jim,

Trevor

Trevor,

Jim

---

From: Trevor Freeman <[email-masked]>
Date: Tue, 6 May 2008 19:25:05 +0000

I should have use MAC to be more accurate.

5083 generates a MAC using the message contents and the CEK.

If there are multiple recipients - all know the CEK so any can generate new messages with the same CEK. So you only can presume the message is from one of the group who know the CEK but you don't know which one.

You could have used a pair wise shared secret to protect the CEK but 5083 does not define how to use the pair wise shared secret to also authenticate the sender. If the sender encrypted the MAC using the KEK and attached that to the message as an unauthenticated attribute the receiver can authenticate the sender.

-----Original Message-----
From: pgut001 [mailto:[email-masked]]
Sent: Monday, May 05, 2008 11:47 PM
To: [email-masked]; Trevor Freeman
Subject: Re: weak authentication issue with rfc5083

Peter.

---

From: Trevor Freeman <[email-masked]>
Date: Tue, 6 May 2008 21:29:34 +0000

The same is true of the MAC because that is sent as unauthenticated data. The recipients computes the MAC then compares it to the unprotected value sent with the message. The computed value and the transmitted value have to match otherwise it's an authentication failure.  If you strip or alter the MAC the recipient detects problem.
This proposal has exactly the same characteristics.

Trevor

From: Jim Schaad [mailto:[email-masked]]
Sent: Tuesday, May 06, 2008 12:31 PM
To: Trevor Freeman; [email-masked]
Subject: RE: weak authentication issue with rfc5083

I would have an issue with this since could be silently stripped without the recipients or senders knowledge.  Thus I don't see it as solving your problem.

Jim

Trevor

Jim

Hi Jim,

Trevor

Trevor,

Jim

---

From: [email-masked] (Peter Gutmann)
Date: Sat, 10 May 2008 01:25:46 +1200

"Jim Schaad" <[email-masked]> writes:

>from me rather than from him.  Since they both use the same CEK that is not a
>factor that could be used to distinguish them.

Ah, OK, thanks.  How serious a threat is this in practice though?  Wouldn't
people just use asymmetric auth if they're worried about proof of origin?  I
realise it's kind of an interesting problem to solve, but does it need solving
beyond a security considerations note "If you're seriously worried about proof
of origin use a signature"?

Peter.

---

From: Daniel Brown <[email-masked]>
Date: Fri, 9 May 2008 10:21:43 -0400

Peter, Jim,

This is a serious problem, imo.  If Bob receives an AuthenticatedData from Alice but it is not really from Alice, then there really is no authentication, despite the promise that AuthenticatedData provides authentication.  What security service is AuthenticatedData providing in this case?  If the Charles is the attacker, then cannot Charles strip off his RecipientInfo from the AuthenticatedData, in which case, Bob has no way of knowing that Alice originallly sent the AuthenticatedData to two parties?

A difference between SignedData and AuthenticatedData is that with the latter Bob cannot prove (cryptographically) to others that Alice authenticated anything.  That's the motivation to use AuthenticatedData instead of SignedData.

***

Maybe AuthEnvData is a little different from AuthData, though.  For example, if the key management mechanism is key transport, so Alice provides no certificate, then effectively Alice is anonymous.  In that case, the MAC only protects integrity of the message from modification in transit, it does not provide authentication.  (Cf. TLS with unauthenticated clients, where records are MAC for a similar purpose.)  If AuthEnvData is used for that lesser purpose, then the substitutuion attack by Charles is not as significant, because Alice is essentially anonymous.

From reading 5083, I interpret its intent only to be add integrity to EnvData, since CBC mode does not provide full integrity.  However, for some choices of key management, it has the further capability of authenticating the sender (i.e. if the key management authenticates the sender, which in does in all cases except key transport).  This is a useful capability and should be noted.  Regardless, it should be emphasized that, at least in the case of key transport, that no actual authentication is provided (just integrity).  Otherwise, evidently there is a risk of misinterpretation.

Best regards,

        Dan

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Peter Gutmann
Sent: Friday, May 09, 2008 9:26 AM
To: [email-masked]; [email-masked]; [email-masked]; [email-masked]
Subject: RE: weak authentication issue with rfc5083

Peter.

---

From: Trevor Freeman <[email-masked]>
Date: Fri, 9 May 2008 19:53:02 +0000

Hi Peter,
The push back to why doesn't everyone just use signatures is when I have an existing security mechanism like Kerberos which builds secure pair wise keys. Kerberos shared secrets can establish mutual authentication providing both parties demonstrate knowledge of the shared secret. I don't think the solution is that complex. If I encrypt the MAC with the pair wise secret I achieve mutual authentication. We use the same mechanism to learn the CEK, we just need to do the same again to prove I know both the KEK and the MAC.

Trevor

-----Original Message-----
From: pgut001 [mailto:[email-masked]]
Sent: Friday, May 09, 2008 6:26 AM
To: [email-masked]; [email-masked]; [email-masked]; Trevor Freeman
Subject: RE: weak authentication issue with rfc5083

Peter.

---

From: [email-masked] (Peter Gutmann)
Date: Tue, 13 May 2008 02:17:29 +1200

Daniel Brown <[email-masked]> writes:

>This is a serious problem, imo.  If Bob receives an AuthenticatedData from
>Alice but it is not really from Alice, then there really is no
>authentication, despite the promise that AuthenticatedData provides
>authentication.  What security service is AuthenticatedData providing in this
>case?

Maybe it would have been better to call it IntegrityProtectedData :-).  That's
actually the only thing I've ever used it for, my assumption was that you sign
email and you MAC stored data.

Peter.