There is a side channel attack on tamper-resistant USB cryptographic tokens using padding-oracle, described by Bardou, Focardi, Kawamoto, Simionato, Steel and Tsay, titled "Efficient padding oracle attacks on cryptographic hardware" (INRIA; CRYPTO 2012, LNCS Volume 7417, 2012, pp 608-625), full paper, brief description. This attack uses vulnerabilities in implementation of PKCS#1v1.5 padding and is an evolution of "million message attack", discovered by Bleichenbacher. Bardou was able to cut cost of attack from 1 million decryption requests down to several tens of thousands requests.
My question is: If somebody owns an vulnerable USB token (listed in the paper), and there is a single RSA key recorded inside this token, can he setup this attack to extract stored private key from this token?
Update: there is FAQ on Bardou web-site: http://www.lsv.ens-cachan.fr/~steel/efficient-padding-oracle-attacks/faq.html
What are the prerequisites for these attacks? You need access to the UnwrapKey function. This could be achieved, for example, directly by putting malware on the host machine, or indirectly if the unwrap key functionality is exposed via a network protocol.
What are the consequences of these attacks? The modified version of the Bleichenbacher attack reveals a plaintext encrypted under an RSA key. That plaintext, in the context of the PKCS#11 UnwrapKey command, is a symmetric key. The same attack can also be used to forge a signature, though this takes longer. Our paper gives full details.
The Vaudenay CBC attack may reveal either a symmetric key or a private RSA key if it has been exported from a device under a symmetric cipher like AES using CBC_PAD.
Do the attacks in the paper reveal the private half of RSA keypairs? Like the original algroithm, our version of the Bleichenbacher attack does not reveal the private half of the RSA key used for encryption.
Riccardo Focardi has online paper Practical Padding Oracle Attacks on RSA with nice description of padding attacks, including Bleichenbacher and Bardou. He also gives a link to Nate Lawson's repsonse to RSA claims (a-la Our tokens are not vulnerable). And after this paper RSA again says: "No smartcard cloning"