Extract private RSA key from USB cryptographic token using Bardou et al. attack (variant of "million message attack")

Question

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"

Answer 1

Their attack does not recover the private key. Instead, it gives the attacker a way to decrypt an arbitrary ciphertext of the attacker's choosing. (This is not the same thing.)

If the attacker has a ciphertext $c$, the attacker can query the hardware device tens of thousands of times and then based upon the responses, deduce what the decryption of $c$ is. If the next day the attacker runs across another ciphertext $c'$ that he wants to decrypt, he needs to issue another tens of thousands of queries to the hardware device. That's pretty bad -- but it's not as bad as revealing the private key.

So, the answer to your question is: no, their attack does not reveal the private key.

(I think all of this is already covered in the links you mentioned in the question, so I'm not sure whether I understood what you were asking.)