Skip to main content

Side channel timing attacks against (EC)DSA in RSA BSAFE CVE-2019-3739/CVE-2019-3740 - Project Wycheproof is the AFL for Cryptography

About a year ago I wrote this tweet and now I can finally justify it
it is more or less when I found the vulnerabilities discussed in this short post.

Introduction

RSA BSAFE is a FIPS 140-2 validated cryptography library offered by RSA Security (now Dell). After almost a year they just published an advisory containing two fixes of two vulnerabilities I found in their Java ECDSA (CVE-2019-3739) and DSA (CVE-2019-3740) implementations. But here it comes the sweet part: I shamelessly did not do too much in order to find them. The credits are indeed all for Project Wycheproof: a tests crypto libraries against known attacks developed and maintained by members of Google Security (notably Daniel Bleichenbacher and Thai Duong).

DSA Information Exposure Through Timing Discrepancy – CVE-2019-3740

The DSA#testTiming() in Wycheproof is pretty clever
Running this versus a vulnerable RSA BAFE version outputs 
count:50000 cutoff:2262000 relative average:0.998277088525826 sigmas:0.6672807446465763
count:25179 cutoff:546000 relative average:0.9787025288365749 sigmas:5.853395982678107
count:12779 cutoff:518000 relative average:0.9099341394956977 sigmas:17.634748289624707
count:6370 cutoff:502000 relative average:0.8926655555837028 sigmas:14.837798062055764
count:3342 cutoff:492000 relative average:0.8153311004028044 sigmas:18.490881332398143
count:1674 cutoff:487000 relative average:0.6381163969813222 sigmas:25.6452690568035
count:962 cutoff:484000 relative average:0.4906264183495749 sigmas:27.36431494195024
count:462 cutoff:481000 relative average:0.2929275162925562 sigmas:26.3236163006087
count:219 cutoff:478000 relative average:0.1590303398169923 sigmas:21.555743778906088
count:109 cutoff:475000 relative average:0.07842002641253994 sigmas:16.665060900087063
count:57 cutoff:472000 relative average:0.053156617273047706 sigmas:12.38158386200097
count:25 cutoff:469000 relative average:0.027495532091447193 sigmas:8.422135745026752
count:13 cutoff:466000 relative average:0.0065219160932997585 sigmas:6.2042686454500195

The first line uses about 50'000 signatures. The average k of these signatures is close to the expected value q/2. But restricting the focus to the  fastest signatures we can observe the bias. Now it is possible to use lattice attacks (leveraging LLL similar to the more famous LLL RSA attacks) as described in this classic paper from Howgrave-Graham and Nigel Smart in order to recover the private key.

ECDSA Information Exposure Through Timing Discrepancy – CVE-2019-3739

The related ECDSA attack can be found in Wycheproof in the EcdsaTest#testTiming method which outputs the following.
count:50000 cutoff:2045000 relative average:1.0022638605003167 sigmas:0.8767894015863159
count:25115 cutoff:482000 relative average:0.9815589218529944 sigmas:5.061899599173188
count:13131 cutoff:458000 relative average:0.9364617484305727 sigmas:12.610862424378672
count:6664 cutoff:447000 relative average:0.9005783600238418 sigmas:14.057530814869727
count:3197 cutoff:439000 relative average:0.8555929171049407 sigmas:14.142312859507411
count:1624 cutoff:433000 relative average:0.8233806969577667 sigmas:12.32797674499385
count:867 cutoff:428000 relative average:0.7998398841996252 sigmas:10.208165905819119
count:423 cutoff:423000 relative average:0.8286801004516601 sigmas:6.102933280661882
count:215 cutoff:419000 relative average:0.7691284728535714 sigmas:5.86340959001382
count:112 cutoff:416000 relative average:0.7532127255580198 sigmas:4.523685462728861
count:53 cutoff:412000 relative average:0.7880582101693218 sigmas:2.6724842828320603
count:35 cutoff:410000 relative average:0.8764428135129847 sigmas:1.2660844067129347
count:13 cutoff:406000 relative average:0.9413265661768302 sigmas:0.36641547678485636

The bias is  less prominent in this case and this only means that more signatures are needed in order to recover the private key.

That's all folks! For more Crypto stuff follow me on Twitter.

Comments

Post a Comment

Popular posts from this blog

OpenSSL Key Recovery Attack on DH small subgroups (CVE-2016-0701)

Usual Mandatory Disclaimer: IANAC (I am not a cryptographer) so I might likely end up writing a bunch of mistakes in this blog post... tl;dr The OpenSSL 1.0.2 releases suffer from a Key Recovery Attack on DH small subgroups . This issue got assigned CVE-2016-0701 with a severity of High and OpenSSL 1.0.2 users should upgrade to 1.0.2f. If an application is using DH configured with parameters based on primes that are not "safe" or not Lim-Lee (as the one in RFC 5114 ) and either Static DH ciphersuites are used or DHE ciphersuites with the default OpenSSL configuration (in particular SSL_OP_SINGLE_DH_USE is not set) then is vulnerable to this attack.  It is believed that many popular applications (e.g. Apache mod_ssl) do set the  SSL_OP_SINGLE_DH_USE option and would therefore not be at risk (for DHE ciphersuites), they still might be for Static DH ciphersuites. Introduction So if you are still here it means you wanna know more. And here is the thing. In my last bl...
23 comments
Read more

Critical vulnerability in JSON Web Encryption (JWE) - RFC 7516

tl;dr if you are using go-jose , node-jose , jose2go , Nimbus JOSE+JWT or jose4j with ECDH-ES please update to the latest version. RFC 7516 aka JSON Web Encryption (JWE) hence many software libraries implementing this specification used to suffer from a classic Invalid Curve Attack . This would allow an attacker to completely recover the secret key of a party using JWE with Key Agreement with Elliptic Curve Diffie-Hellman Ephemeral Static (ECDH-ES) , where the sender could extract receiver’s private key. Premise In this blog post I assume you are already knowledgeable about elliptic curves and their use in cryptography. If not Nick Sullivan 's A (Relatively Easy To Understand) Primer on Elliptic Curve Cryptography or Andrea Corbellini's series Elliptic Curve Cryptography: finite fields and discrete logarithms are great starting points. Then if you further want to climb the elliptic learning curve including the related attacks you might also want to visit https://s...
2 comments
Read more

The Curious Case of WebCrypto Diffie-Hellman on Firefox - Small Subgroups Key Recovery Attack on DH

tl;dr Mozilla Firefox prior to version 72 suffers from Small Subgroups Key Recovery Attack on DH in the WebCrypto 's API. The Firefox's team fixed the issue r emoving completely support for DH over finite fields (that is not in the WebCrypto standard). If you find this interesting read further below. Premise In this blog post I assume you are already knowledgeable about Diffie-Hellman over finite fields and related attacks. If not I recommend to read any cryptography book that covers public key cryptography. Here is a really cool simple explanation by David Wong : I found a cooler way to explain Diffie-Hellman :D pic.twitter.com/DlPvGwZbto — David Wong (@cryptodavidw) January 4, 2020 If you want more details about Small Subgroups Key Recovery Attack on DH I covered some background in one of my previous post ( OpenSSL Key Recovery Attack on DH small subgroups (CVE-2016-0701) ). There is also an academic pape r where we examine the issue with some more rigors. ...
2 comments
Read more