The research was done with cryptographers from UC San Diego and Inria. The first finding concerns PKCS#1 v1.5 digital signatures, used among other places in the PKCS#11 interface of hardware security modules (HSMs): once an attacker controls roughly half of the signed block or more, padding adds no protection. In a sandboxed test, two agents re-ran an earlier academic forgery attack and cut CPU time 3.5-fold, to 391 core-years instead of 1,380, in under four days and with about 20 messages from the researcher.
The second finding is an algorithm that makes factoring each additional 1024-bit key about 30 times cheaper on average, after an expensive initial computation. It is a theoretical estimate, and the method has not been implemented. According to the researchers, the signature attack does not recover the private key, requires about 4 billion signing queries in advance and does not work against devices that hash messages internally.
"We cannot treat cryptographic hardness as a fixed assumption," said Pushmeet Kohli, a vice president at Google DeepMind. Organizations still using 1024-bit RSA keys, for example in legacy systems, should move to longer keys.