About a year ago I wrote this tweet and now I can finally justify it
> Project Wycheproof (<https://t.co/wBz9P8atHs>) is the AFL (<https://t.co/JM2l557PZi>) of #crypto. Thanks a lot @XorNinja and team (notably including Bleichenbacher) for providing such a powerful tool > > — Antonio Sanso (@asanso) April 9, 2018
it is more or less when I found the vulnerabilities discussed in this short post.
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).
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.
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.