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

From: "Vladimir Dzhuvinov / NimbusDS" <[email-masked]>
Date: Mon, 25 Mar 2013 23:08:36 -0700

On Tue, 2013-03-26 at 12:30 +1100, Manger, James H wrote:
> >> 	SecretKey randomCMK = AES.generateAESCMK(keyLength);
> > >>
> > >> 	try {
> > >> 		cmk = RSA1_5.decryptCMK(privateKey, encryptedKey.decode(),
> > >> keyLength);
> > >> 	} catch (Exception e) {
> > >> 		// Protect against MMA attack by generating random CMK on
> > failure,
> > >> 		// see http://www.ietf.org/mail-
> > >> archive/web/jose/current/msg01832.html
> > >> 		cmk = randomCMK;
> > >> 	}
> > >> }
> > >>
> > >>
> > >> This would be perfect and also secure against timing attacks.
> > >
> > >
> > > This code may be a bit more resistant to timing attacks, but it is
> > nowhere near perfect.
> > Agreed, "perfect" was a pretty strong word for that code.
> > 
> > I know that there could appear different processing times due to the
> > decoded key length check, throwing and catching the exception, or
> > randomCMK assignment. But I would say that they would consume much less
> > processing time than the random number generation.
> > 
> > Do you have any measurements / thoughts on this?
> > 
> > Btw, We measured e.g. the timing differences of PKCS1 processing.
> > Decryption of valid (without random number generation) and invalid
> > (with random number generation) PKCS1 messages yielded a difference of
> > about
> > 11 microseconds.
> > 
> > I would be also very interested to know, if you have any major
> > improvements for the code I provided.
> > 
> > Thanks
> > Juraj
> 
> For a start the fixes need to be much lower down where the PKCS#1 padding is first handled, not way up the stack were you see an exception vs a normal return.
> 
> The Go language appears to have code with decent protections to avoid leaking crucial timing details: http://golang.org/src/pkg/crypto/rsa/pkcs1v15.go.
> 
> The Java code I found in a quick search (sun.security.rsa.RSAPadding#unpadV15) makes no effort to be constant time. I doubt there is anything (reasonable) that can be done at a higher layer (such as com.nimbusds.jose.crypto.RSA1_5) to make RSAES-PKCS1-V1_5 safe with that foundation.
> [http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7-b147/sun/security/rsa/RSAPadding.java#RSAPadding.unpadV15%28byte%5B%5D%29]
> 
> Mind you, switching to RSA-OAEP might not help as the unpadOAEP(..) function in the same source file doesn't look much safer (it checks the 1st byte is 0 before doing the OAEP verification).
> 
What do you guys think of precomputing a set of CMKs, e.g. during
decrypter construction, so the actual random number generation doesn't
happen when decrypt requests are served?

I read the paper James suggested, and it advocates achieving constant
time to solve timing attacks. How about doing the opposite, injecting
random duration no-ops in the decryption code?

Vladimir

---

From: "Manger, James H" <[email-masked]>
Date: Wed, 27 Mar 2013 09:32:19 +1100

> random duration no-ops in the decryption code?

That doesn't solve the problem. It makes an attacker’s job harder, but by making more requests and applying statistics the attacker can remove the affect of the random-duration no-ops. And it slows your code down.

--
James Manger

>> Take at look at http://www.imperialviolet.org/2013/02/04/luckythirteen.html for some idea about the care required to actually resist timing attacks.