Subject: [jose] backwards compatibility attack on JWT impls (was: I-D Action: draft-ietf-jose-json-web-algorithms-02.txt)

From: =JeffH <[email-masked]>
Date: Thu, 14 Mar 2013 08:16:38 -0700

back on Fri, 6 Jul 2012  Mike Jones said:
 >
 > Looking at this again, it seems to me that because JWE provides integrity
 > protection for the algorithm, it should be impossible for you to replace
 > "RSA-OAEP" with "RSA1_5" in the header because then the integrity check will
 > fail.  Thus, the attack that you describe below is prevented by the integrity
 > protection of the header.
 >
 > Hence, correct JWE implementations do no provide the OAEP decryption oracle
 > that you describe.  However if I'm missing something, please point it out to
 > me, since if there's an issue, I'd like to understand it and how to mitigate
 > it.

just fyi/fwiw...apologies if this has already been followed up on, but I didn't 
find further discussion of this after the above-quoted msg...

Juraj Somorovsky et al's NDSS-2013 "Backwards Compatibility (BC) attacks" paper 
[1] is now out, and it may help answer the above questions. There's also Kenny 
Patterson's talk [2] from the recent Workshop on Real-World Cryptography.

It seems, from an admittedly cursory glance at both 
draft-ietf-jose-json-web-algorithms (-08) and the above paper/slides, that 
perhaps there should be more implementation advice and security considerations 
in (at least) the -json-web-algorithms spec.

Here's some excerpts from the paper for context...
                ...
In the public-key setting, we show how the well-known attack of Bleichenbacher 
[13] gives rise to a BC [Backwards Compatibility] attack that allows an attacker
to decrypt ciphertexts of PKCS#1 v2.0 encryption in both XML Encryption [27] and 
JSON Web Encryption [42], and to forge signatures for arbitrary messages in XML 
Signature [30] and JSON Web Signature [41]. The attack principle is described in 
Section 4. We furthermore report on our experimental results, executed against 
the Java implementation of JSON Web Encryption and JSON Web Signature Nimbus-JWT 
[53], in Section 5.3.
                ...

Platform for Experimental Analysis: We investigate the practicality and 
performance of our attacks on JWE and JWS by applying them to the Nimbus-JWT 
library [53]. Nimbus-JWT is a Java implementation of JSON Web Encryption (JWE) 
and JSON Web Signature (JWS), developed by NimbusDS to support their Cloud 
Identity management portfolio.

Even though Nimbus-JWT claims to implement version 02 of the JWE standard draft, 
it still supports usage of AESCBC (without MAC), which was available in version 
01, but not in version 02 or any subsequent versions.
                ...

5.2.3 Evaluation

We evaluated performance of our attacks against both WSS4J and Nimbus-JWT. We 
ﬁrst used the libraries to generate valid messages containing AES-GCM 
ciphertexts. Then we modiﬁed the algorithm parameters in the messages, forcing 
the receiver to process the ciphertexts using AES-CBC, and executed the attack 
described in Algorithm 1. The required ciphertext validity oracles were based on 
error messages generated by the libraries.
                ...

Experimental Results. In order to assess the practicability and performance of 
the attack, we implemented Bleichenbacher’s attack on XML Encryption [13, 38] 
and applied it to the Nimbus-JWT library. The PKCS#1 v1.5 validity oracle was 
provided by exceptions thrown by this library.11
                ...

11 In practice one would instead use the more elaborate attack techniques
of [38] to determine whether a given ciphertext is PKCS#1 v1.5 valid.
                ...

[13] D. Bleichenbacher. Chosen ciphertext attacks against protocols based on the 
RSA encryption standard PKCS#1. In H. Krawczyk, editor, Advances in Cryptology – 
CRYPTO’98, volume 1462 of Lecture Notes in Computer Science, pages 1–12. 
Springer, Aug. 1998.

[38] T. Jager, S. Schinzel, and J. Somorovsky. Bleichenbacher’s attack strikes 
again: breaking PKCS#1 v1.5 in XML Encryption. In S. Foresti and M. Yung, 
editors, Computer Security - ESORICS 2012 - 17th European Symposium on Research 
in Computer Security, Pisa, Italy, September 10-14, 2012. Proceedings, LNCS. 
Springer, 2012.

[53] Nimbus Directory Services. Nimbus JSON Web Token, May 2012. 
https://bitbucket.org/nimbusds/nimbus-jwt.

###

[1] One Bad Apple: Backwards Compatibility Attacks on
  State-of-the-Art Cryptography
http://www.nds.ruhr-uni-bochum.de/media/nds/veroeffentlichungen/2013/03/08/BackwardsCompatibilityAttacks.pdf

[2] Key Reuse: Theory and Practice
http://crypto.stanford.edu/RealWorldCrypto/slides/kenny.pdf

HTH,

=JeffH

---

From: Mike Jones <[email-masked]>
Date: Thu, 14 Mar 2013 15:48:50 +0000

I believe that these attacks are only possible on encryption without integrity, which in turn was only possible, because Nimbus-JWT continued to implement encryption algorithms without integrity protection.  Someone should please correct me if I'm misunderstanding the situation.

As most of you know, JWE now only allows authenticated encryption algorithms to be used, for reasons exactly such as these.

				-- Mike

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of =JeffH
Sent: Thursday, March 14, 2013 8:17 AM
To: IETF JOSE WG
Cc: Juraj Somorovsky
Subject: [jose] backwards compatibility attack on JWT impls (was: I-D Action: draft-ietf-jose-json-web-algorithms-02.txt)

back on Fri, 6 Jul 2012  Mike Jones said:
 >
 > Looking at this again, it seems to me that because JWE provides integrity  > protection for the algorithm, it should be impossible for you to replace  > "RSA-OAEP" with "RSA1_5" in the header because then the integrity check will  > fail.  Thus, the attack that you describe below is prevented by the integrity  > protection of the header.
 >
 > Hence, correct JWE implementations do no provide the OAEP decryption oracle  > that you describe.  However if I'm missing something, please point it out to  > me, since if there's an issue, I'd like to understand it and how to mitigate  > it.

just fyi/fwiw...apologies if this has already been followed up on, but I didn't find further discussion of this after the above-quoted msg...

Juraj Somorovsky et al's NDSS-2013 "Backwards Compatibility (BC) attacks" paper [1] is now out, and it may help answer the above questions. There's also Kenny Patterson's talk [2] from the recent Workshop on Real-World Cryptography.

It seems, from an admittedly cursory glance at both draft-ietf-jose-json-web-algorithms (-08) and the above paper/slides, that perhaps there should be more implementation advice and security considerations in (at least) the -json-web-algorithms spec.

Here's some excerpts from the paper for context...
                ...
In the public-key setting, we show how the well-known attack of Bleichenbacher [13] gives rise to a BC [Backwards Compatibility] attack that allows an attacker to decrypt ciphertexts of PKCS#1 v2.0 encryption in both XML Encryption [27] and JSON Web Encryption [42], and to forge signatures for arbitrary messages in XML Signature [30] and JSON Web Signature [41]. The attack principle is described in Section 4. We furthermore report on our experimental results, executed against the Java implementation of JSON Web Encryption and JSON Web Signature Nimbus-JWT [53], in Section 5.3.
                ...

Platform for Experimental Analysis: We investigate the practicality and performance of our attacks on JWE and JWS by applying them to the Nimbus-JWT library [53]. Nimbus-JWT is a Java implementation of JSON Web Encryption (JWE) and JSON Web Signature (JWS), developed by NimbusDS to support their Cloud Identity management portfolio.

Even though Nimbus-JWT claims to implement version 02 of the JWE standard draft, it still supports usage of AESCBC (without MAC), which was available in version 01, but not in version 02 or any subsequent versions.
                ...

5.2.3 Evaluation

We evaluated performance of our attacks against both WSS4J and Nimbus-JWT. We ﬁrst used the libraries to generate valid messages containing AES-GCM ciphertexts. Then we modiﬁed the algorithm parameters in the messages, forcing the receiver to process the ciphertexts using AES-CBC, and executed the attack described in Algorithm 1. The required ciphertext validity oracles were based on error messages generated by the libraries.
                ...

Experimental Results. In order to assess the practicability and performance of the attack, we implemented Bleichenbacher’s attack on XML Encryption [13, 38] and applied it to the Nimbus-JWT library. The PKCS#1 v1.5 validity oracle was provided by exceptions thrown by this library.11
                ...

11 In practice one would instead use the more elaborate attack techniques of [38] to determine whether a given ciphertext is PKCS#1 v1.5 valid.
                ...

[13] D. Bleichenbacher. Chosen ciphertext attacks against protocols based on the RSA encryption standard PKCS#1. In H. Krawczyk, editor, Advances in Cryptology – CRYPTO’98, volume 1462 of Lecture Notes in Computer Science, pages 1–12. 
Springer, Aug. 1998.

[38] T. Jager, S. Schinzel, and J. Somorovsky. Bleichenbacher’s attack strikes
again: breaking PKCS#1 v1.5 in XML Encryption. In S. Foresti and M. Yung, editors, Computer Security - ESORICS 2012 - 17th European Symposium on Research in Computer Security, Pisa, Italy, September 10-14, 2012. Proceedings, LNCS. 
Springer, 2012.

###

HTH,

=JeffH

_______________________________________________
jose mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/jose

---

From: Brian Campbell <[email-masked]>
Date: Thu, 14 Mar 2013 12:38:44 -0400

But the integrity protected encryption happens using the key that's been
wrapped/encrypted using "RSA-OAEP" or "RSA1_5".  That key needs to be
unwrapped/decrypted before any of the integrity checks even come into play,
which is where the attack takes place. So I don't see how the AEAD (or
composite AEAD like) algorithms help for preventing Bleichenbacher attacks
on RSA1_5 or BC attacks on RSA-OAEP to RSA1_5?

(the general disclaimer correcting me, if I'm wrong, applies)

On Thu, Mar 14, 2013 at 11:48 AM, Mike Jones <[email-masked]>wrote:

> I believe that these attacks are only possible on encryption without
> integrity, which in turn was only possible, because Nimbus-JWT continued to
> implement encryption algorithms without integrity protection.  Someone
> should please correct me if I'm misunderstanding the situation.
>
> As most of you know, JWE now only allows authenticated encryption
> algorithms to be used, for reasons exactly such as these.
>
>                                 -- Mike
>
> Subject: [jose] backwards compatibility attack on JWT impls (was: I-D
> Action: draft-ietf-jose-json-web-algorithms-02.txt)
>
>  > Looking at this again, it seems to me that because JWE provides
> integrity  > protection for the algorithm, it should be impossible for you
> to replace  > "RSA-OAEP" with "RSA1_5" in the header because then the
> integrity check will  > fail.  Thus, the attack that you describe below is
> prevented by the integrity  > protection of the header.
>  >
>  > Hence, correct JWE implementations do no provide the OAEP decryption
> oracle  > that you describe.  However if I'm missing something, please
> point it out to  > me, since if there's an issue, I'd like to understand it
> and how to mitigate  > it.
>
> just fyi/fwiw...apologies if this has already been followed up on, but I
> didn't find further discussion of this after the above-quoted msg...
>
> Juraj Somorovsky et al's NDSS-2013 "Backwards Compatibility (BC) attacks"
> paper [1] is now out, and it may help answer the above questions. There's
> also Kenny Patterson's talk [2] from the recent Workshop on Real-World
> Cryptography.
>
> perhaps there should be more implementation advice and security
> considerations in (at least) the -json-web-algorithms spec.
>
> In the public-key setting, we show how the well-known attack of
> Bleichenbacher [13] gives rise to a BC [Backwards Compatibility] attack
> that allows an attacker to decrypt ciphertexts of PKCS#1 v2.0 encryption in
> both XML Encryption [27] and JSON Web Encryption [42], and to forge
> signatures for arbitrary messages in XML Signature [30] and JSON Web
> Signature [41]. The attack principle is described in Section 4. We
> furthermore report on our experimental results, executed against the Java
> implementation of JSON Web Encryption and JSON Web Signature Nimbus-JWT
> [53], in Section 5.3.
>                 ...
>
> performance of our attacks on JWE and JWS by applying them to the
> Nimbus-JWT library [53]. Nimbus-JWT is a Java implementation of JSON Web
> Encryption (JWE) and JSON Web Signature (JWS), developed by NimbusDS to
> support their Cloud Identity management portfolio.
>
> Even though Nimbus-JWT claims to implement version 02 of the JWE standard
> draft, it still supports usage of AESCBC (without MAC), which was available
> in version 01, but not in version 02 or any subsequent versions.
>                 ...
>
> 5.2.3 Evaluation
>
> We evaluated performance of our attacks against both WSS4J and Nimbus-JWT.
> We ﬁrst used the libraries to generate valid messages containing AES-GCM
> ciphertexts. Then we modiﬁed the algorithm parameters in the messages,
> forcing the receiver to process the ciphertexts using AES-CBC, and executed
> the attack described in Algorithm 1. The required ciphertext validity
> oracles were based on error messages generated by the libraries.
>                 ...
>
> Experimental Results. In order to assess the practicability and
> performance of the attack, we implemented Bleichenbacher’s attack on XML
> Encryption [13, 38] and applied it to the Nimbus-JWT library. The PKCS#1
> v1.5 validity oracle was provided by exceptions thrown by this library.11
>                 ...
>
> [13] D. Bleichenbacher. Chosen ciphertext attacks against protocols based
> on the RSA encryption standard PKCS#1. In H. Krawczyk, editor, Advances in
> Cryptology – CRYPTO’98, volume 1462 of Lecture Notes in Computer Science,
> pages 1–12.
> Springer, Aug. 1998.
>
> editors, Computer Security - ESORICS 2012 - 17th European Symposium on
> Research in Computer Security, Pisa, Italy, September 10-14, 2012.
> Proceedings, LNCS.
> Springer, 2012.
>

---

From: Mike Jones <[email-masked]>
Date: Thu, 14 Mar 2013 17:56:42 +0000

Hi Juraj,

Thanks for looking at the security characteristics of JWE.

I don't think that either of your scenarios (a) or (b) apply to JWE.

For (a), a server implementing JWE will not accept unsigned (really, non-integrity-protected) requests because encryption algorithms not providing integrity protection may not be used.

For (b), it doesn't matter if the attacker has a valid public key that the server would accept for signatures, because the integrity protection applied to JWE is not simply a separate signature applied after the fact.  The JWE's contents are protected using a randomly generated key that is encrypted by the key wrapping step.  Unless the attacker already possess the key to decrypt the encrypted key (the objective of the attack in the first place!), he can't learn what key was used to apply the integrity protection, and without that key, the attacker can't apply a different signature.

The description of the "enc" parameter in http://tools.ietf.org/html/draft-ietf-jose-json-web-encryption-08#section-4.1.2 begins with:
   The "enc" (encryption method) header parameter identifies the block
   encryption algorithm used to encrypt the Plaintext to produce the
   Ciphertext.  This algorithm MUST be an Authenticated Encryption
   algorithm with a specified key length.

If you think that's not clear enough, we could certainly say more - particularly in the Security Considerations section.  Suggested text would be more than welcomed.

Also, responding to Brian's scenario, I believe that the attack on RSA PKCS #1 1.5 requires the ability for the attacker to submit valid modified messages to the server.  Because the JWE messages are integrity-protected using a wrapped key, the reasoning of (b) above applies in this case too.  Specifically, without knowing the RSA key in the first place, it's not possible to learn the key used to provide the integrity check, and so not possible to create modified messages that pass the integrity check.

But by all means, if any of my reasoning is wrong or incomplete, please do point it out!

				Thanks again, Juraj,
				-- Mike

-----Original Message-----
From: Juraj Somorovsky [mailto:[email-masked]] 
Sent: Thursday, March 14, 2013 9:42 AM
To: Mike Jones
Cc: =JeffH; IETF JOSE WG; Tibor Jager
Subject: Re: [jose] backwards compatibility attack on JWT impls (was: I-D Action: draft-ietf-jose-json-web-algorithms-02.txt)

Hi Jeff, hi Mike,

I am sorry, it seems that I have totally missed your previous email. I try to answer some of your questions...

> I believe that these attacks are only possible on encryption without integrity, which in turn was only possible, because Nimbus-JWT continued to implement encryption algorithms without integrity pr…
These attacks were basically possible because:
1) Nimbus-JWT allowed us to use AES-CBC. As we explicitly state in our paper, this is not problem of the jose specification as it forbids AES-CBC in the newer versions

2) We were able to force the Nimbus-JWT framework to decrypt RSA-OAEP ciphertexts with RSA1_5. You are right, in our scenarios, the Headers were not signed and thus we were able to switch from RSA-OAEP to RSA1_5.
However, if I take a look at the JSON Web Encryption standard, there is not explicitly written that the messages must be signed. And even if the messages would be signed, there could still exist scenarios where it is possible to apply these attacks. See below.
> As most of you know, JWE now only allows authenticated encryption algorithms to be used, for reasons exactly such as these.
It is great that you removed AES-CBC. RSA1_5 encryption is still however in the standard.
>  > Hence, correct JWE implementations do no provide the OAEP decryption oracle  > that you describe.  However if I'm missing something, please point it out to  > me, since if there's an issue, I'd…
Yes, this is true, if the attacker is not able to create valid signatures AND he is not able to force the server to process unsigned elements. However, there are few scenarios, where the attacks could still be applied.

I am not that familiar with all the JSON scenarios but I assume that they are very close to the scenarios where XML Security is applied.
Thus, I would say it is possible to assume the following scenarios:

a) If the server is not correctly configured, it could accept unsigned requests JSON elements. Thus, the attacker could simply extract the signature or create an additional encryption element.

b) in some Public-Key scenarios, the attacker will have a valid key to sign his JSON requests. In that case, he is able to:
  1) take an RSA_OAEP request from his victim
  2) extract the signature from this request
  3) replace the algorithm (RSA_OAEP -> RSA1_5) and
  4) resign the request with his own key.
Afterwards, he could send the request to the server and force it to process RSA1_5

Please see our paper for more details (Section 4):
http://www.nds.ruhr-uni-bochum.de/research/publications/breaking-xml-encryption-countermeasures/

It describes some techniques how to apply such attacks on signed symmetrically encrypted XML documents.
> It seems, from an admittedly cursory glance at both draft-ietf-jose-json-web-algorithms (-08) and the above paper/slides, that perhaps there should be more implementation advice and security consid…
Agreed. Some of these attacks are e.g. explicitly handled in the XML Encryption specification:
http://www.w3.org/TR/xmlenc-core1/#sec-chosen-ciphertext-attacks

You could include similar sections in your spec. If you would need some help, just let us know.

Thanks
Juraj

---

From: Justin Richer <[email-masked]>
Date: Thu, 14 Mar 2013 14:02:05 -0400

Also, the Nimbus-JWT library has been deprecated in favor of 
Nimbus-JOSE-JWT:

   https://bitbucket.org/nimbusds/nimbus-jose-jwt/

The new library is tracking the JOSE specs even more closely, and I'd be 
very interested to hear if the attack is still possible against the new 
library.

  -- Justin

---

From: "Juraj Somorovsky" <[email-masked]>
Date: 14 Mar 2013 17:41:37 +0100

Hi Jeff, hi Mike,

I am sorry, it seems that I have totally missed your previous email. I
try to answer some of your questions...

These attacks were basically possible because:
1) Nimbus-JWT allowed us to use AES-CBC. As we explicitly state in our
paper, this is not problem of the jose specification as it forbids
AES-CBC in the newer versions

2) We were able to force the Nimbus-JWT framework to decrypt RSA-OAEP
ciphertexts with RSA1_5. You are right, in our scenarios, the Headers
were not signed and thus we were able to switch from RSA-OAEP to RSA1_5.
However, if I take a look at the JSON Web Encryption standard, there is
not explicitly written that the messages must be signed. And even if the
messages would be signed, there could still exist scenarios where it is
possible to apply these attacks. See below.
> As most of you know, JWE now only allows authenticated encryption algorithms to be used, for reasons exactly such as these.
It is great that you removed AES-CBC. RSA1_5 encryption is still however
in the standard.
>  > Hence, correct JWE implementations do no provide the OAEP decryption oracle  > that you describe.  However if I'm missing something, please point it out to  > me, since if there's an issue, I'd…
Yes, this is true, if the attacker is not able to create valid
signatures AND he is not able to force the server to process unsigned
elements. However, there are few scenarios, where the attacks could
still be applied.

I am not that familiar with all the JSON scenarios but I assume that
they are very close to the scenarios where XML Security is applied.
Thus, I would say it is possible to assume the following scenarios:

a) If the server is not correctly configured, it could accept unsigned
requests JSON elements. Thus, the attacker could simply extract the
signature or create an additional encryption element.

b) in some Public-Key scenarios, the attacker will have a valid key to
sign his JSON requests. In that case, he is able to:
  1) take an RSA_OAEP request from his victim
  2) extract the signature from this request
  3) replace the algorithm (RSA_OAEP -> RSA1_5) and
  4) resign the request with his own key.
Afterwards, he could send the request to the server and force it to
process RSA1_5

It describes some techniques how to apply such attacks on signed
symmetrically encrypted XML documents.
> It seems, from an admittedly cursory glance at both draft-ietf-jose-json-web-algorithms (-08) and the above paper/slides, that perhaps there should be more implementation advice and security consid…
Agreed. Some of these attacks are e.g. explicitly handled in the XML
Encryption specification:
http://www.w3.org/TR/xmlenc-core1/#sec-chosen-ciphertext-attacks

You could include similar sections in your spec. If you would need some
help, just let us know.

Thanks
Juraj

---

From: "Juraj Somorovsky" <[email-masked]>
Date: 14 Mar 2013 18:02:21 +0100

I assume this also depends on the scenario. If you use public key
signatures, you can sign whatever you want with your key, even the the
RSA1_5 / RSA_OAEP ciphertexts and their algorithms
(again, I am not familiar with the json scenarios, but in XML Encryption
applications, the RSA ciphertexts are typically *not* signed)

If you use HMACs, you need to transport somehow your HMAC key. You would
do this probably with RSA-OAEP. In this case, the scenario described by
Brian applies.

Juraj

---

From: "Juraj Somorovsky" <[email-masked]>
Date: 15 Mar 2013 00:52:35 +0100

Hi Mike,

you are right, your symmetric encryption algorithms are ok and Section
4.1.2 is clear enough. My concern was rather about the asymmetric
encryption.

I also agree with the description of Brian's scenario:
1) the server first decrypts RSA ciphertext using RSA1_5 / RSA_OAEP and
obtains CMK
2) the server uses CMK to validate signature and decrypt json data

Of course, if the attacker would modify the RSA ciphertext, the server
would decrypt a different CMK value and the signature would thus be
incorrect.

In our paper we *assumed* that the RSA decryption is vulnerable to
Bleichenbacher's attack (this is a valid assumption since most of the
XML Encryption implementations were vulnerable to this attack, Nimbusds
is still vulnerable to it). In that case, if the adversary modifies
RSA1_5 ciphertext and sends it to the server, he is able to distinguish
if the ciphertext was valid or not. This can be e.g. done using error
messages sent from the server:
a) in case of an invalid RSA1_5 ciphertext, the server stops its
processing in step 1) and directly responds with "RSA1_5 invalid"
b) in case of a valid RSA1_5 ciphertext, the server decrypts CMK and
tries to validate signature. The signature is of course invalid, which
leads to a different response.

(See more details in:
http://www.nds.ruhr-uni-bochum.de/research/publications/breaking-xml-encryption-pkcs15/
)

This gave us also the possibility to execute backwards compatibility
attacks on RSA OAEP.

Please note that our point was not to state that jose is in general
insecure. Our point was that allowing insecure algorithms (e.g. RSA1_5)
and their bad implementation could spoil the security of secure ones
(e.g. RSA-OAEP).

Generally, such an attack could be of course *mitigated* by generating
random CMKs, when the RSA1_5 is invalid. Thus, I would propose to
reference Eric's
https://tools.ietf.org/rfc/rfc3218.txt
in your security considerations. Maybe, it would be even better to
explicitly sketch these countermeasures as done in TLS1.2
(http://www.ietf.org/rfc/rfc5246.txt Section 7.4.7.1.)

Regards
Juraj

---

From: "Juraj Somorovsky" <[email-masked]>
Date: 15 Mar 2013 01:00:48 +0100

Ok, thank you for mentioning. The attacks were implemented in August
2012. I mean I used the old library.

The newest library seems not to use AES-CBC. However, by taking a look at
https://bitbucket.org/nimbusds/nimbus-jose-jwt/src/69de24720368c480ee93479ca84f3801a3f8909d/src/main/java/com/nimbusds/jose/crypto/RSADecrypter.java?at=master#cl-153
I assume it is still vulnerable to Bleichenbacher's attack (as it
responds with different Exceptions according to the PKCS1 validity).

I reported this almost 1 year ago:
http://www.ietf.org/mail-archive/web/jose/current/msg00419.html

Regards
Juraj

On 03/14/2013 07:02 PM, Justin Richer wrote:
>> integrity, which in turn was only possible, because Nimbus-JWT
>> continued to implement encryption algorithms without integrity
>> protection.  Someone should please correct me if I'm misunderstanding
>> the situation.
>>
>> integrity  > protection for the algorithm, it should be impossible for
>> you to replace  > "RSA-OAEP" with "RSA1_5" in the header because then
>> the integrity check will  > fail.  Thus, the attack that you describe
>> below is prevented by the integrity  > protection of the header.
>>   >
>>   > Hence, correct JWE implementations do no provide the OAEP
>> decryption oracle  > that you describe.  However if I'm missing
>> something, please point it out to  > me, since if there's an issue,
>> I'd like to understand it and how to mitigate  > it.
>>
>> just fyi/fwiw...apologies if this has already been followed up on, but
>> I didn't find further discussion of this after the above-quoted msg...
>>
>> Juraj Somorovsky et al's NDSS-2013 "Backwards Compatibility (BC)
>> attacks" paper [1] is now out, and it may help answer the above
>> questions. There's also Kenny Patterson's talk [2] from the recent
>> Workshop on Real-World Cryptography.
>>
>> draft-ietf-jose-json-web-algorithms (-08) and the above paper/slides,
>> that perhaps there should be more implementation advice and security
>> Bleichenbacher [13] gives rise to a BC [Backwards Compatibility]
>> attack that allows an attacker to decrypt ciphertexts of PKCS#1 v2.0
>> encryption in both XML Encryption [27] and JSON Web Encryption [42],
>> and to forge signatures for arbitrary messages in XML Signature [30]
>> and JSON Web Signature [41]. The attack principle is described in
>> Section 4. We furthermore report on our experimental results, executed
>> against the Java implementation of JSON Web Encryption and JSON Web
>> Signature Nimbus-JWT [53], in Section 5.3.
>>                  ...
>>
>> Platform for Experimental Analysis: We investigate the practicality
>> and performance of our attacks on JWE and JWS by applying them to the
>> Nimbus-JWT library [53]. Nimbus-JWT is a Java implementation of JSON
>> Web Encryption (JWE) and JSON Web Signature (JWS), developed by
>> NimbusDS to support their Cloud Identity management portfolio.
>>
>> Even though Nimbus-JWT claims to implement version 02 of the JWE
>> standard draft, it still supports usage of AESCBC (without MAC), which
>> was available in version 01, but not in version 02 or any subsequent
>> versions.
>>                  ...
>>
>> 5.2.3 Evaluation
>>
>> We evaluated performance of our attacks against both WSS4J and
>> Nimbus-JWT. We ﬁrst used the libraries to generate valid messages
>> containing AES-GCM ciphertexts. Then we modiﬁed the algorithm
>> parameters in the messages, forcing the receiver to process the
>> ciphertexts using AES-CBC, and executed the attack described in
>> Algorithm 1. The required ciphertext validity oracles were based on
>> performance of the attack, we implemented Bleichenbacher’s attack on
>> XML Encryption [13, 38] and applied it to the Nimbus-JWT library. The
>> PKCS#1 v1.5 validity oracle was provided by exceptions thrown by this
>> library.11
>>                  ...
>>
>> 11 In practice one would instead use the more elaborate attack
>> techniques of [38] to determine whether a given ciphertext is PKCS#1
>> v1.5 valid.
>>                  ...
>>
>> [13] D. Bleichenbacher. Chosen ciphertext attacks against protocols
>> based on the RSA encryption standard PKCS#1. In H. Krawczyk, editor,
>> Advances in Cryptology – CRYPTO’98, volume 1462 of Lecture Notes in
>> Computer Science, pages 1–12.
>> Springer, Aug. 1998.
>>
>> again: breaking PKCS#1 v1.5 in XML Encryption. In S. Foresti and M.
>> Yung, editors, Computer Security - ESORICS 2012 - 17th European
>> Symposium on Research in Computer Security, Pisa, Italy, September
>> 10-14, 2012. Proceedings, LNCS.
>> Springer, 2012.
>>

---

From: Brian Campbell <[email-masked]>
Date: Fri, 15 Mar 2013 14:03:29 -0600

+1

Thanks Juraj.

---

From: Richard Barnes <[email-masked]>
Date: Mon, 18 Mar 2013 13:41:20 -0400

Hi Juraj,

Thanks for engaging in this discussion.  I'm sorry it didn't happen
earlier!  I would like to confirm that I've understood your paper
correctly, and discuss what it implies for JOSE.

As I read the paper, the backward-compatibility attack arises when a
recipient R is willing to use the same key (symmetric or private) to
process both a new algorithm (GCM / OAEP) and an old algorithm (CBC /
PKCS#1).  The willingness to process the old algorithm allows the necessary
oracles to be constructed, which can then be used to attack the new
algorithm, as long as the new algorithm uses the same key as the old
algorithm.  I would also note that cross-protocol attacks exacerbate this
problem: A BC vulnerability arises if a key is re-used with a different
algorithm ANYWHERE -- not just for another JWE, but for any other protocol.

For the purposes of discussion, I would like to note that two putative
security mechanisms in the current JOSE spec do NOT mitigate BC attacks.
-- Use of only authenticated encryption.  The an implementation can safely
support CBC and GCM (for example), as long as the same key is not used for
both.
-- Integrity protection of the algorithm value (as part of the JWS/JWE
header).  The attacker doesn't need to change the algorithm used for any
given object, only for two types of (independent, valid) objects to be
processed.

On the other hand, the following changes to the spec WOULD mitigate BC
attacks.
-- Recommending the use of a random CMK wherever possible
-- Recommending that implementations follow the guidelines in RFC 3218 [1]
-- Recommending that implementations track which keys are used with which
algorithms, and prevent key reuse
-- Deprecating / removing the "direct" mode of encryption [2], which
encourages key reuse by making it harder to use random, ephemeral CMK
values.

Thanks a lot,
--Richard

[1] <http://tools.ietf.org/html/rfc3218>
[2] <
http://tools.ietf.org/html/draft-ietf-jose-json-web-algorithms-08#section-4.6

---

From: Richard Barnes <[email-masked]>
Date: Wed, 20 Mar 2013 00:25:09 -0400

<snip>

> We did not understand this, could you please clarify?
>

The current JWE format provides an integrity check on the header
parameters, including the name of the algorithm with which the JWE should
be processed.  In the BC attack, the attacker does not need to modify the
algorithm name on a GCM-encrypted object, he merely needs to construct
CBC-encrypted objects with which to query the oracle.  So the integrity
check on the algorithm name does not stop the BC attack.

> What do you mean by "wherever possible" please? ...it is just necessary
> to use this as a countermeasure against Bleichenbacher's attacks on
> PKCS1.5. Reference to RFC 3218 and a short description of this
> countermeasure would be enough.
>

An example of the case where using a random CMK is not currently possible
is in JWS, which does not allow wrapped keys for MAC.  One might also
imagine deprecating the "alg":"dir" mode for JWE, where a static key is
used (or at least putting a big warning label on it).

> see above.
> Yes, it would be nice to enforce key separation in the JOSE
> implementations and libraries by default so that users cannot use the
> same key for different algorithms (e.g., a library could enforce the
> user to generate two key pairs: one for signature processing and one for
> encryption processing). I do not know how feasible this is in general.
>

Note that in order to prevent the attack, the checking only needs to be in
the recipient side.  It seems like this could be done pretty trivially and
safely.
-- Every time you decrypt an object, store the tuple (hash(key), algorithm)
in a table
-- Before you decrypt the next object, look up hash(key) in the table and
see if the algorithm is the same as the one you're about to use.

> Yes, this would be reasonable.
>
> But we took e.g. a look at section 4.5:
>
> http://tools.ietf.org/html/draft-ietf-jose-json-web-algorithms-08#section-4.5
> This section does not explicitly enforce key separation. If you want to
> enforce a key separation (in case you are in possession of a shared
> symmetric key), you could enforce to derive a new key from the shared
> symmetric key and the algorithm identifier. This would result in
> different keys for AES-CBC and AES-GCM and thwart a BC attack.
>
> See also the last section of the paper by Kelsey et al. for more details.
>
> Thanks
> Juraj
> >
> > Thanks a lot,
> > --Richard
> >

---

From: "Juraj Somorovsky" <[email-masked]>
Date: 20 Mar 2013 15:15:09 +0100

> check on the algorithm name does not stop the BC attack.
Correct, the attacker just needs to "include" an object encrypted with
an insecure algorithm...it does not matter, if he modifies an existing
secure object or creates a totally new object encrypted with an insecure
algorithm and appends it to the document.
> see if the algorithm is the same as the one you're about to use.
This is in general a very bad idea. Consider e.g.:
1) an attacker who is strong enough to eavesdrop an encrypted message
with AES-GCM and who is fast enough to modify this message and claim the
message is encrypted with AES-CBC. In this case, the server would store
the tuple (hash(key), AES-CBC) instead of (hash(key), AES-GCM) in its
hash table.
2) a scenario where the same key is shared between different servers. In
that case, you would have to enforce that the hashtable is updated in
parallel on different servers at the same time. This could lead to
serious implementation problems.

Another questions, which would arise are e.g. how long should be this
hash table? How many keys and for how long should be stored? What
happens after server restart?

Your approach would introduce new issues, but not solve the original
problem.

Juraj

---

From: "Juraj Somorovsky" <[email-masked]>
Date: 19 Mar 2013 21:42:48 +0100

Hi Richard,

> algorithm ANYWHERE -- not just for another JWE, but for any other protocol.
Yes, this is true. If the server e.g. uses the same key for JWE and SSL
and if JWE would be vulnerable, this could of course have an impact on
the security of the SSL protocol.

See also this publication by Kelsey, Schneier and Wagner on Chosen
Protocol attacks: http://www.schneier.com/paper-chosen-protocol.html

Last section gives a good summary of countermeasures.
> support CBC and GCM (for example), as long as the same key is not used for
If "safely" means that GCM cannot be broken, this is correct.
see above.

Thanks
Juraj