Subject: Re: [jose] JWT + JOSE for Java

From: "Vladimir Dzhuvinov / NimbusDS" <[email-masked]>
Date: Thu, 05 Apr 2012 06:03:58 -0700

Hallo Berlin, hallo Bochum, hallo Welt! :)

I just sent an email to a crypto expert at a partner company to ask for
his opinion is on that. My feeling is that when we collect sufficient
opinions on that the "truth" will eventually emerge :)

As mentioned, I don't have a proper crypto background, so during
refactoring I made sure Axel's code remained just as it was.

Vladimir

--
Vladimir Dzhuvinov : www.NimbusDS.com : [email-masked]

-------- Original Message --------
Subject: Re: [jose] JWT + JOSE for Java
From: <[email-masked]>
Date: Thu, April 05, 2012 1:00 pm
To: <[email-masked]>, <[email-masked]>
Cc: [email-masked]

Hi Juraj,

As Vladimir's work is based on my implementation I guess that my
implementation has room for improvement too.
https://code.google.com/p/openinfocard/source/browse/trunk/src/org/xmldap/json/WebToken.java

ENC_ALG_RSA_OAEP is better than ENC_ALG_RSA1_5. 
https://code.google.com/p/openinfocard/source/browse/trunk/src/org/xmldap/json/WebToken.java#116

Both padding algorithms are supported by my code and this RSA bulletin
mentions OAEP as one counter measure against the Bleichenbacher attack.
ftp://ftp.rsasecurity.com/pub/pdfs/bulletn7.pdf

Does "your" attack work against ENC_ALG_RSA_OAEP too? Additional counter
measures suggestions are very welcome.

RSA1_5 is in the proposed standard because it is widely available
although RSA recommends to use OAEP for decades. 
I think that RSA-OAEP should be mandatory to implement and RSA1_5
deprecated.

Cheers. Greetings from Berlin to Bochum.
Axel

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of
Juraj Somorovsky
Sent: Thursday, April 05, 2012 1:13 AM
To: [email-masked]
Cc: [email-masked]
Subject: Re: [jose] JWT + JOSE for Java

Hi Vladimir,

I have took a look at your implementation and found out, that your PKCS1
handling is vulnerable to the Bleichenbacher attack (the adversary could
be able to issue different ciphertexts, send them to the server, and
according to its responses he could learn the encrypted CEK)

I will send you PoCs and instructions how to fix it by tomorrow...or
just take a look at the document written by Eric Rescorla:
http://www.ietf.org/rfc/rfc3218.txt

Regards
Juraj

On 04/03/2012 11:24 AM, Vladimir Dzhuvinov / NimbusDS wrote:
> Today I reached a point in my JWT+JOSE library implementation where I 
> wouldn't feel ashamed to release it to the public :)
> 
> https://github.com/NimbusDS/Nimbus-JWT
> 
> The library is fully documented:
> http://nimbusds.com/files/jwt/javadoc/index.html
> 
> 
> The Nimbus-JWT library started a month ago from code borrowed from 
> Axel Nennker's + Co OpenInfoCard project and at this point covers 
> fully plain and signed JWTs as well as JSON Web Keys (JWK). The JWE 
> implementation still requires a bit of work to add HMAC integrity and 
> cover the remaining elliptic curve and key-wrap encryption algorithms 
> from the JWA spec. I would be very thankful if somebody could help me 
> with that as I don't have much experience with cryptography :)
> 
> For the listing of the supported JWAs:
> http://nimbusds.com/files/jwt/javadoc/com/nimbusds/jwt/JWA.html
> 
> Cheers,
> 
> Vladimir
> --
> Vladimir Dzhuvinov : www.NimbusDS.com : [email-masked]
> 
> _______________________________________________
> jose mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/jose

--
M.Sc. Juraj Somorovsky

Lehrstuhl für Netz- und Datensicherheit
Ruhr Universität Bochum
-----------------------------------
Universitätsstr. 150, Geb. ID 2/411
D-44780 Bochum

Telefon: +49 (0) 234 / 32-26551
Fax: +49 (0) 234 / 32-14347
http://www.nds.rub.de
_______________________________________________
jose mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/jose
_______________________________________________
jose mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/jose

---

From: "Juraj Somorovsky" <[email-masked]>
Date: 5 Apr 2012 17:29:39 +0200

Hi :)

ok, I'll try to explain the Bleichenbacher attack in few sentences...

If you construct your ciphertext using PKCS1, you take your symmetric
key CEK and you padd it with some bytes to achieve a given message
length... it looks like this:
0x00 0x02 ... random bytes (except for 0x00) ... 0x00 CEK

You can encrypt this message using the server's public key.

On the decryptor's side, the server tries to extract CEK. It decrypts
the message using its RSA private key and *checks the message padding
format* (0x00 0x02 ... 0x00 CEK). Afterwards, it takes CEK.

The problem is: if the server responds differently according to the
PKCS1 padding validity, the attacker can learn some bits of the
plaintext. By sending a huge amount of messages (about 1,000,000 or
more...this depends on the server message check and the transmitted
message), he can learn the secured CEK and thus decrypt the whole message.

When looking at both your codes, I see two problems:

case RSA1_5:
	Cipher cipher = Cipher.getInstance("RSA/ECB/PKCS1Padding");
	cipher.init(Cipher.DECRYPT_MODE, rsaPrivateKey);
// this way, you throw an exception everytime you get invalid PKCS1
message. Your framework says e.g.:
com.nimbusds.jwt.JWEException: Couldn't decrypt: unknown block type
if the decrypted message does not start with 0x00 0x02 or it says
com.nimbusds.jwt.JWEException: Couldn't decrypt: no data in block
if the decrypted message does not contain any 0x00 in the middle
	byte[] secretKeyBytes1 = cipher.doFinal(encryptedKey.decode());
	if (8* secretKeyBytes1.length != keylength) {
// this throws something like
com.nimbusds.jwt.JWEException: Couldn't decrypt: WebToken.decrypt RSA
PKCS1Padding symmetric key length mismatch: 48 != 256
which gives the attacker again the possibility to distinguish between
valid and invalid messages
		throw new Exception("WebToken.decrypt RSA PKCS1Padding symmetric key
length mismatch: " + secretKeyBytes1.length + " != " +  keylength);
	}

	keySpec = new SecretKeySpec(secretKeyBytes1, symmetricAlgorithm);

	break;

Responding with a generalized error message also does not help
completely as the attacker could observe the response time of the
server. Namely, valid PKCS1 messages bring a CEK, which is then used for
data decryption (AES-CBC, AES-GCM...). Invalid PKCS1 messages return a
fault response directly, without data decryption. This offers a nice
timing side-channel. Please note that the attacker can force the server
to process arbitrarily data (also e.g. 1MB), so the attack could become
practical also over the Internet (tested in similar scenario with XML
Encryption :) )

Ok, so additionally to the same error messages, you should also consider
timing and thus regenerate a symmetric key CEK every time, it was
incorrectly decrypted (this way all the invalid PKCS1 ciphertexts will
be processed, CEK generated, and the MAC validation will fail),
something like this:

case RSA1_5:
     // initialize somewhere SecureRandom (e.g. in your JWE constructor)
     // SecureRandom random = SecureRandom.getInstance("SHA1PRNG")
	Cipher cipher = Cipher.getInstance("RSA/ECB/PKCS1Padding");
	cipher.init(Cipher.DECRYPT_MODE, rsaPrivateKey);
        byte[] secretKeyBytes1 = null;
        try {
        	secretKeyBytes1 = cipher.doFinal(encryptedKey.decode());
        } catch(BadPaddingException e) {
// regenerate key if the PKCS1 padding is incorrect
        	secretKeyBytes1 = new byte[keylength / 8];
                random.nextBytes(secretKeyBytes1);
        }

	if (8* secretKeyBytes1.length != keylength) {
// regenerate key if the length is incorrect
        	secretKeyBytes1 = new byte[keylength / 8];
                random.nextBytes(secretKeyBytes1);
	}

	keySpec = new SecretKeySpec(secretKeyBytes1, symmetricAlgorithm);

	break;

I hope this will thwart the attack...

We have already tried to convince the standard developers to exclude
PKCS1 from the standard:
http://www.mail-archive.com/[email-masked]/msg00075.html

...it did not work.

RSA-OAEP is the good choice for JOSE as PKCS1 will cause similar
problems also for other developers.

Regards from Bochum
Juraj

-- 
M.Sc. Juraj Somorovsky

---

From: Tom Ritter <[email-masked]>
Date: Thu, 5 Apr 2012 12:04:14 -0400

> problems also for other developers.

I haven't been following closely, but if it hasn't been already I
should point out there's a very similar attack against RSA-OAEP you
need to take care to avoid: http://ritter.vg/blog-mangers_oracle.html

-tom

---

From: <[email-masked]>
Date: Fri, 6 Apr 2012 08:10:15 +0200

I think you are arguing on a protocol level (like SSL) but this is not how I understand JOSE. 
JSON Encryption and Signing defines formats and suggests which algorithms to use.
We do not define things like "you should change your keys after n operations or N megabytes of plaintext processed (or when a BadPadding Exception is thrown). I think that my code should throw all exceptions in all their glory details and that e.g. the application server "above" me should then decide which action to take: like "Give a standard error message" to the sender of the bad message and wait a random amount of time before sending error messages. But this is not the task of this code.
https://code.google.com/p/openinfocard/source/browse/trunk/src/org/xmldap/json/WebToken.java 

My understanding of the level that we are describing here is "below" protocols.
Although I give it to you that the security considerations section should recommend usage of the formats and algorithms defined here and discourage certain uses.

I fear that we end up in a discussion that I followed in the NSS discussion group years ago. "Should we give developers cryptographic building blocks that could be used wrong". Then NSS decided  not to do it but I think that was wrong.

I think that the protocols that use the JOSE formats/algs like openid connect (https://openid.net/connect/) have the duty to use them correctly. Your advice on how to make openid connect secure is very welcome. Please analyze it and tell us your findings. http://lists.openid.net/pipermail/openid-specs-ab/ 

Axel

-----Original Message-----
From: Juraj Somorovsky [mailto:[email-masked]] 
Sent: Thursday, April 05, 2012 5:30 PM
To: Vladimir Dzhuvinov / NimbusDS
Cc: Nennker, Axel; [email-masked]
Subject: Re: [jose] JWT + JOSE for Java

Hi :)

If you construct your ciphertext using PKCS1, you take your symmetric key CEK and you padd it with some bytes to achieve a given message length... it looks like this:
0x00 0x02 ... random bytes (except for 0x00) ... 0x00 CEK

On the decryptor's side, the server tries to extract CEK. It decrypts the message using its RSA private key and *checks the message padding
format* (0x00 0x02 ... 0x00 CEK). Afterwards, it takes CEK.

The problem is: if the server responds differently according to the
PKCS1 padding validity, the attacker can learn some bits of the plaintext. By sending a huge amount of messages (about 1,000,000 or more...this depends on the server message check and the transmitted message), he can learn the secured CEK and thus decrypt the whole message.

case RSA1_5:
	Cipher cipher = Cipher.getInstance("RSA/ECB/PKCS1Padding");
	cipher.init(Cipher.DECRYPT_MODE, rsaPrivateKey); // this way, you throw an exception everytime you get invalid PKCS1 message. Your framework says e.g.:
com.nimbusds.jwt.JWEException: Couldn't decrypt: unknown block type if the decrypted message does not start with 0x00 0x02 or it says
com.nimbusds.jwt.JWEException: Couldn't decrypt: no data in block if the decrypted message does not contain any 0x00 in the middle
	byte[] secretKeyBytes1 = cipher.doFinal(encryptedKey.decode());
	if (8* secretKeyBytes1.length != keylength) { // this throws something like
com.nimbusds.jwt.JWEException: Couldn't decrypt: WebToken.decrypt RSA PKCS1Padding symmetric key length mismatch: 48 != 256 which gives the attacker again the possibility to distinguish between valid and invalid messages
		throw new Exception("WebToken.decrypt RSA PKCS1Padding symmetric key length mismatch: " + secretKeyBytes1.length + " != " +  keylength);
	}

	break;

Responding with a generalized error message also does not help completely as the attacker could observe the response time of the server. Namely, valid PKCS1 messages bring a CEK, which is then used for data decryption (AES-CBC, AES-GCM...). Invalid PKCS1 messages return a fault response directly, without data decryption. This offers a nice timing side-channel. Please note that the attacker can force the server to process arbitrarily data (also e.g. 1MB), so the attack could become practical also over the Internet (tested in similar scenario with XML Encryption :) )

Ok, so additionally to the same error messages, you should also consider timing and thus regenerate a symmetric key CEK every time, it was incorrectly decrypted (this way all the invalid PKCS1 ciphertexts will be processed, CEK generated, and the MAC validation will fail), something like this:

case RSA1_5:
        } catch(BadPaddingException e) { // regenerate key if the PKCS1 padding is incorrect

	if (8* secretKeyBytes1.length != keylength) { // regenerate key if the length is incorrect
        	secretKeyBytes1 = new byte[keylength / 8];
                random.nextBytes(secretKeyBytes1);
	}

	break;

...it did not work.

RSA-OAEP is the good choice for JOSE as PKCS1 will cause similar problems also for other developers.

Regards from Bochum
Juraj

On 04/05/2012 03:03 PM, Vladimir Dzhuvinov / NimbusDS wrote:
> I just sent an email to a crypto expert at a partner company to ask 
> for his opinion is on that. My feeling is that when we collect 
> sufficient opinions on that the "truth" will eventually emerge :)
> 
> Does "your" attack work against ENC_ALG_RSA_OAEP too? Additional 
> counter measures suggestions are very welcome.
> 
> From: [email-masked] [mailto:[email-masked]] On Behalf 
> Of Juraj Somorovsky
> I have took a look at your implementation and found out, that your 
> PKCS1 handling is vulnerable to the Bleichenbacher attack (the 
> adversary could be able to issue different ciphertexts, send them to 
> the server, and according to its responses he could learn the 
> encrypted CEK)
> 
> Lehrstuhl für Netz- und Datensicherheit Ruhr Universität Bochum

--
M.Sc. Juraj Somorovsky

---

From: "Juraj Somorovsky" <[email-masked]>
Date: 6 Apr 2012 15:34:05 +0200

Thanks Tom, I know there is the Manger's attack and I already read your
blog a few months ago ;)

...but considering Bleichenbacher's and Manger's attacks there are a few
differences between PKCS#1.5 and PKCS#2.0 (RSA-OAEP):

Manger's attack on RSA-OAEP is rather theoretical. As you also mention
in your post, the security libraries handle it correctly:
- if there is no 0x00 on the beginning, they simply ignore it and  check
integrity by verifying hash values.
- even if the library would not handle this step correctly, the timing
difference is really small (of course, if not considering the timing
attack in the Manger's paper in Section 4.4) and not measurable over the
Internet.

Bleichenbacher's attack on PKCS#1.5 is practical. This results from
missing integrity check in PKCS#1.5 after ciphertext decryption, which
gives the attacker a possibility to create related plaintexts. The main
point is: if the attacker creates a ciphertext resulting in a valid CEK,
he forces the server to use this CEK and decrypt the payload data
(encrypted e.g. with AES). In comparison to small timing differences in
RSA-OAEP, the timing differences between valid and invalid PKCS#1.5
ciphertexts can be enlarged by sending a greater amount of payload data.

Thus, even if the ciphertext is not valid, when using PKCS#1.5 the
server should generate a new key and decrypt the payload in order not to
reveal a timing side-channel. This must be explicitly handled by the
application developer and cannot be handled in the security library.

In comparison to PKCS#1.5, RSA-OAEP can be used directly...the
application developer does not have to care about any countermeasures in
his application. If the developer relies on a good security library
(OpenSSL, BouncyCastle...), his application will not reveal any
side-channels with RSA-OAEP.

Regards
Juraj

-- 
M.Sc. Juraj Somorovsky

---

From: "Cantor, Scott" <[email-masked]>
Date: Fri, 6 Apr 2012 13:48:31 +0000

> We do not define things like "you should change your keys after n operations
> or N megabytes of plaintext processed (or when a BadPadding Exception is
> thrown). I think that my code should throw all exceptions in all their glory
> details and that e.g. the application server "above" me should then decide
> which action to take: like "Give a standard error message" to the sender of
> the bad message and wait a random amount of time before sending error
> messages. But this is not the task of this code.

Yes, it is. If you want to use PKCS#1.5, then you need to make that usable safely without extra precautions by your caller. If we were talking about the actual implementation of PKCS1.5, then you might be right, but you're not implementing that, you're using it to encrypt objects you're trying to abstract in a library. That makes it your job to make encryption a "safe" operation for somebody using that abstraction, if you can.

In the case of this attack, detailed error information can be put in logs, and doesn't need to be exposed to callers, and the generation of a random key easily defeats the timing attack.

There are harder problems that are virtually impossible to solve that way (the CBC attack). This one is easy and entirely appropriate to fix below any protocol.

> My understanding of the level that we are describing here is "below"

And the encryption here is also below the protocol. If it weren't, that would be a different matter.

> I fear that we end up in a discussion that I followed in the NSS discussion
> group years ago. "Should we give developers cryptographic building blocks
> that could be used wrong". Then NSS decided  not to do it but I think that
> was wrong.

NSS is a crypto library (meaning it actually implements PKCS1.5). That's a different layer.

> I think that the protocols that use the JOSE formats/algs like openid connect
> (https://openid.net/connect/) have the duty to use them correctly.

They do, but that doesn't absolve libraries of the responsibility of being implemented correctly also. Otherwise, be prepared for most of the protocol implementations using your code to get it wrong.

-- Scott

---

From: Tom Ritter <[email-masked]>
Date: Fri, 6 Apr 2012 09:51:52 -0400

There's two different opinions here:

> side-channels with RSA-OAEP.

Axel says "It's the developer's job to use my code correctly", Juraj
says "if the library is good, I don't need to do anything extra".

There's good arguments for both approaches.  I mentioned the OAEP
attack because I hadn't seen it mentioned before, and I would rather
look a fool and tell something everyone knows versus lose the
opportunity to fix a bug in dozens or hundreds of applications before
they're written.

The templating engines, the database libraries, and the cryptographic
libraries that make it _hard_ for a user to introduce vulnerabilities
they don't understand, are preferable to ones that don't.  Check out
the near-end of [0], where Pascal Junod compares crypto libraries and
what attacks they protect against: timing, cache, fault, oracle, and
leakage.  Protecting against power leakage attacks is way overboard -
but protecting against timing attacks is pretty much the minimum
standard these days.

I *don't* understand JOSE, I don't know where this code fits in.  I
don't know the appropriate level to defend against developer
omissions.  It's almost certainly too high-level to make an API that
_requires_ a developer to pass in a MAC along with the ciphertext -
even though protecting ciphertext with a MAC is pretty much an "Always
Do This!" these days with all of the adaptive-ciphertext attacks we've
been seeing.[1]  I do think putting in non-branching code for timing
defense in the decryption routine is appropriate.  And if it were _me_
were defining an API, I would make the cipher constructor or
decryption function take an optional parameter that determined whether
verbose or identical errors are thrown, and the default would be
identical.

Until developing becomes like bridge-building, and people have to take
a test to see if they can do it safely - I think it's very important
for anyone who's writing code that will be called by others to make it
'safe by default' and not rely on intelligence or thoroughness of the
calling developer.

-tom

[0] http://crypto.junod.info/hashdays10_talk.pdf
[1] CBC Padding Oracle, OAEP, Bleichenbacher, and more

---

From: John Bradley <[email-masked]>
Date: Fri, 6 Apr 2012 11:05:12 -0300

I largely agree with Scott,

The security considerations for people implementing JOSE libraries are going to be important.

The upper level protocols like Connect are not going to cover all the possible side channel attacks against a library.
Yes messages should be available to the upper level application so that it can decide what to report on the wire.

However every effort to protect from side channel and other attacks need to be taken by the crypto libraries themselves.

If there are algorithm choices we could make like only supporting PKCS#2 OAEP in the JOSE spec to reduce the potential implementation issues.

That is probably the level we need to have the discussion  at right now.

John B.

---

From: "Cantor, Scott" <[email-masked]>
Date: Fri, 6 Apr 2012 14:14:18 +0000

> If there are algorithm choices we could make like only supporting PKCS#2
> OAEP in the JOSE spec to reduce the potential implementation issues.
> 

I would agree, and I would also question the need to include PKCS1.5 in this
work. Every algorithm that's duplicative is just more work, let alone when
they introduce risk.

-- Scott

---

From: "Juraj Somorovsky" <[email-masked]>
Date: 6 Apr 2012 20:53:42 +0200

> There are harder problems that are virtually impossible to solve that way (the CBC attack). This one is easy and entirely appropriate to fix below any protocol.
I fully agree with Scott, I want to add only two remarks:

1) timing and random amount of time: each security researcher interested
in side-channels would tell you that handling timing side-channels with
a random amount of time is generally a bad idea.

Moreover, what should be the random amount of time for decryption of
100KB of data? What about decryption of 1MB of data? Should each
developer test his server performance before deploying the library?
...thus, random key regeneration is needed.

2) Exceptions: as Scott already mentioned, the exceptions can be checked
in the server logs. The developer does not have to get three different
exception types with concrete errors since he needs to tell the
application user only: "during the decryption process something went wrong".
If you give the developer these three exceptions, he will most probably
forward them to the user (which causes direct application of the
Bleichenbacher's attack)

JBossWS or Axis2 Web Services Frameworks e.g. return to the service
client only "Security processing failed" or "Decryption processing
failed" error messages when the request is invalid. If the user needs to
get more information, he needs to check the server logs.

Regards
Juraj
-- 
M.Sc. Juraj Somorovsky

---

From: "Juraj Somorovsky" <[email-masked]>
Date: 6 Apr 2012 21:02:20 +0200

> work. Every algorithm that's duplicative is just more work, let alone when
Agreed, removing PKCS1.5 and supporting only PKCS2.0 is the good way to
go. It will be much more easier for the library developers not to take
care about the attacks resulting from the PKCS1.5 standard.

Regards
Juraj

-- 
M.Sc. Juraj Somorovsky