5 ms·

Scientists crack RSA SecurID 800 tokens, steal cryptographic keys

116 points by alsothings 14y ago

moonboots 14y ago
Direct link to researcher's blog post about the exploit: http://blog.cryptographyengineering.com/2012/06/bad-couple-of-years-for-cryptographic.html http://blog.cryptographyengineering.com/2012/06/bad-couple-o...
- siculars 14y ago
  "... The 'best practice' in implementing RSA is: don't implement RSA. Other people have done it better than you can. Go find a good implementation of RSA-OAEP and use that. End of story..."
  - dchest 14y ago
    Is there a reason why people still use RSA instead of ECC?
    - tptacek 14y ago
      No; ECC is better. But as an implementor, if you're hoping to DIY, you're even worse off with ECC than with RSA; there are more parameters and validations steps you can get wrong with ECC that will result in a flawed implementation. The security of these hardware devices is not tied to the RSA algorithm per se. The devices might not be more resilient against these attacks simply by using ECC instead of RSA. Either way: don't implement RSA or ECC yourself. Use something like PGP/GPG.
      - __alexs 14y ago
        (FYI, The OpenPGP specification got ECC support a couple of weeks ago http://tools.ietf.org/html/rfc6637 http://tools.ietf.org/html/rfc6637)
      - sandGorgon 14y ago
        (warning: noob alert) just out of curiosity, is there an open source implementation of a securid-like server/client. I'm not even sure what the encryption technology is called, but it would be very cool to play with.
        icebraining 14y ago
        OATH is the competing open standard to SecurID, as far as I know, and there's plenty of code that supports it. It's also what the Gmail 2FA and Google Authenticator are based on (so you can use any OATH client to authenticate to Gmail).
    - tedunangst 14y ago
      http://en.wikipedia.org/wiki/ECC_patents http://en.wikipedia.org/wiki/ECC_patents
      - tptacek 14y ago
        http://cr.yp.to/patents.html http://cr.yp.to/patents.html Patents used to be the reason ECC was rarely used (that and novelty), but there are ECC systems in somewhat wide use that aren't patent-licensed.
        tedunangst 14y ago
        Right. I mentioned it because any discussion of why something isn't used should mention why it wasn't used. "It's ok to use this" is more compelling if it explains why the observed reality differs. :)
    - elehack 14y ago
      Tin-foil-hat reason: it has been shown that there exist a set of numbers with a particular relationship to the elliptic curve numbers, and that it is possible that whoever generated the elliptic curve numbers may also have generated the other set of numbers, which basically form a skeleton key to ECC. Schneier on the attack: http://www.wired.com/politics/security/commentary/securitymatters/2007/11/securitymatters_1115 http://www.wired.com/politics/security/commentary/securityma...
      - dchest 14y ago
        Isn't this the case for almost any cryptosystem? There's JP Aumasson's paper on the possibility of hash backdoor: http://www.131002.net/data/papers/Aum11a.pdf http://www.131002.net/data/papers/Aum11a.pdf
        tveita 14y ago
        Not for RSA. It's highly unlikely that anyone has hidden a backdoor in the set of primes. They'd have to solve the RSA problem, which is believed to be difficult. When you do require a "magic constant" in a cryptographic algorithm, it is common to show good faith by deriving it in a way that would make it difficult to embed a backdoor. For instance ascii text, digits of pi, or the lowest AES encrypted number that fulfils certain criteria. Edit: these is also called "nothing up my sleeve numbers".
        dchest 14y ago
        There are methods of embedding backdoors into the RSA key generation scheme, though (e.g. http://crypto.cs.mcgill.ca/~crepeau/PDF/CS02.pdf http://crypto.cs.mcgill.ca/~crepeau/PDF/CS02.pdf). When you do require a "magic constant" in a cryptographic algorithm, it is common to show good faith by deriving it in a way that would make it difficult to embed a backdoor. For instance ascii text, digits of pi, or the lowest AES encrypted number that fulfils certain criteria. The initialization constant in SipHash is awesome: "somepseudorandomlychosenbytes".
        14y ago
deleted 14y ago
[deleted]
ajross 14y ago
The title is correct, but misleading if you don't know the product. "RSA SecurID" is the name of a two-factor authentication product from RSA Security. This isn't a crack of RSA, what they did is pull private keys out of a "secure" device. (Edit: never mind, it looks like it's a chosen plaintext attack against the RSA on the device, not a direct hack. So yeah, this is cryptographically impressive. It looks like they're exploiting a bad padding protocol?)
- tptacek 14y ago
  They're relying on two classic attacks, one on AES-CBC and one one RSA with PKCS1.5 padding. The former is probably the best known cryptanalytic attack in the world (it's the one Thai Duong and Juliano Rizzo used against J2EE and .NET 2 years ago, and there are publicly available attack tools that will attempt to exploit it against arbitrary targets. The latter is Bleichenbacher's, very well known in the literature but not widely exploited (this is a crypto attack that involves some linear algebra). The rough sketch of both attacks is similar. It exploits a target that holds a secret key and reacts to arbitrary attacker-chosen messages. The attacker has no knowledge of the key, but might have knowledge of a known-good message. The attacker modifies the message in targeted ways and sends to the target; the target attempts to decrypt the message; the decryption goes haywire (because the attacker has modified the message without knowing the key); the target's behavior changes visibly as a result of the decryption going haywire. The attacker knows (1) the nature of the targeted change they made, and (2) whether or not the target reacted weirdly (raised an error, took longer to respond, failed to respond). The attacker continues changing messages and collecting 2-tuples of [change, result]. The whole cryptographic attack then analyzes the list of 2-tuples and from it discerns some secret.
  - caf 14y ago
    The researchers in this case have actually made a significant improvement to the Bleichenbacher attack, extending it to use division (multiplication by an inverse) as well as multiplication as in the classic attack.
andrewaylett 14y ago
Note that this is the 800 token, with a USB port, and it's the USB bit that's been broken, not the six-digit ID part that people usually associate with SecurID. My understanding is that the USB port enables the token to sign data on demand, and it's this signing key that's been compromised -- not just for SecurID, but for a whole range of similar encryption tokens.
- regularfry 14y ago
  I don't know how these things work. Is the generator for the six-digit string related to the signing key?
  - astral303 14y ago
    No, those two functions are unrelated. It's a two-in-one: smart card w/ signing key and one-time-password token.
gouranga 14y ago
When we start shipping revokable 64gb compressed one time pad data sticks, I'll have some faith in crypto. Until then, one eye always open.
- romaniv 14y ago
  I think the motivation behind RSA tokens is that while you can steal them, you shouldn't be able to silently copy one. That's not something you get with an OTP on a USB stick, unless you invest into tamper-proof hardware. Aside from that, I'm not sure why OTPs aren't more commonly used. They're easy to reason about, and while you still need some protocol to use them correctly, it would seem that protocol would be much simpler than for fancy crypto like RSA.
  - tptacek 14y ago
    The "some protocol to use them" part is where the crypto in the hardware devices in this attack fell down, which is one of the many reasons people don't use OTPs: they shift all of the security of the system from the cryptographic algorithm itself to the protocol, which is the most error-prone part of the system. Neither RSA nor AES were damaged by this attack.
  - tedunangst 14y ago
    You would need a OTP for every one you wanted to talk to. If I had a OTP for every https site I visit, I'd need hundreds. Facebook would need hundreds of millions. They're not going to be mailing out USB sticks on a weekly basis.
    - romaniv 14y ago
      You need an RSA token for each server you talk to as well. It's not a replacement for asymmetric cryptography.
      - tptacek 14y ago
        You'd "need" (in the handwaviest sense, because nobody had designed a crypto token based on one-time pads here) OTP content for every authentication attempt.
zokier 14y ago
Reducing number of iterations by two orders of magnitude is quite impressive. But I don't like how one product is singled out when the attack seems rather generic.
killpg 14y ago
Steal? Those scientists earned those keys.

116 points by alsothings 14y ago

Direct link to researcher's blog post about the exploit: http://blog.cryptographyengineering.com/2012/06/bad-couple-of-years-for-cryptographic.html http://blog.cryptographyengineering.com/2012/06/bad-couple-o...

siculars 14y ago
"... The 'best practice' in implementing RSA is: don't implement RSA. Other people have done it better than you can. Go find a good implementation of RSA-OAEP and use that. End of story..."
- dchest 14y ago
  Is there a reason why people still use RSA instead of ECC?
  - tptacek 14y ago
    No; ECC is better. But as an implementor, if you're hoping to DIY, you're even worse off with ECC than with RSA; there are more parameters and validations steps you can get wrong with ECC that will result in a flawed implementation. The security of these hardware devices is not tied to the RSA algorithm per se. The devices might not be more resilient against these attacks simply by using ECC instead of RSA. Either way: don't implement RSA or ECC yourself. Use something like PGP/GPG.
    - __alexs 14y ago
      (FYI, The OpenPGP specification got ECC support a couple of weeks ago http://tools.ietf.org/html/rfc6637 http://tools.ietf.org/html/rfc6637)
    - sandGorgon 14y ago
      (warning: noob alert) just out of curiosity, is there an open source implementation of a securid-like server/client. I'm not even sure what the encryption technology is called, but it would be very cool to play with.
      - icebraining 14y ago
        OATH is the competing open standard to SecurID, as far as I know, and there's plenty of code that supports it. It's also what the Gmail 2FA and Google Authenticator are based on (so you can use any OATH client to authenticate to Gmail).
  - tedunangst 14y ago
    http://en.wikipedia.org/wiki/ECC_patents http://en.wikipedia.org/wiki/ECC_patents
    - tptacek 14y ago
      http://cr.yp.to/patents.html http://cr.yp.to/patents.html Patents used to be the reason ECC was rarely used (that and novelty), but there are ECC systems in somewhat wide use that aren't patent-licensed.
      - tedunangst 14y ago
        Right. I mentioned it because any discussion of why something isn't used should mention why it wasn't used. "It's ok to use this" is more compelling if it explains why the observed reality differs. :)
  - elehack 14y ago
    Tin-foil-hat reason: it has been shown that there exist a set of numbers with a particular relationship to the elliptic curve numbers, and that it is possible that whoever generated the elliptic curve numbers may also have generated the other set of numbers, which basically form a skeleton key to ECC. Schneier on the attack: http://www.wired.com/politics/security/commentary/securitymatters/2007/11/securitymatters_1115 http://www.wired.com/politics/security/commentary/securityma...
    - dchest 14y ago
      Isn't this the case for almost any cryptosystem? There's JP Aumasson's paper on the possibility of hash backdoor: http://www.131002.net/data/papers/Aum11a.pdf http://www.131002.net/data/papers/Aum11a.pdf
      - tveita 14y ago
        Not for RSA. It's highly unlikely that anyone has hidden a backdoor in the set of primes. They'd have to solve the RSA problem, which is believed to be difficult. When you do require a "magic constant" in a cryptographic algorithm, it is common to show good faith by deriving it in a way that would make it difficult to embed a backdoor. For instance ascii text, digits of pi, or the lowest AES encrypted number that fulfils certain criteria. Edit: these is also called "nothing up my sleeve numbers".
        dchest 14y ago
        There are methods of embedding backdoors into the RSA key generation scheme, though (e.g. http://crypto.cs.mcgill.ca/~crepeau/PDF/CS02.pdf http://crypto.cs.mcgill.ca/~crepeau/PDF/CS02.pdf). When you do require a "magic constant" in a cryptographic algorithm, it is common to show good faith by deriving it in a way that would make it difficult to embed a backdoor. For instance ascii text, digits of pi, or the lowest AES encrypted number that fulfils certain criteria. The initialization constant in SipHash is awesome: "somepseudorandomlychosenbytes".
        14y ago

deleted 14y ago

[deleted]

ajross 14y ago

The title is correct, but misleading if you don't know the product. "RSA SecurID" is the name of a two-factor authentication product from RSA Security. This isn't a crack of RSA, what they did is pull private keys out of a "secure" device. (Edit: never mind, it looks like it's a chosen plaintext attack against the RSA on the device, not a direct hack. So yeah, this is cryptographically impressive. It looks like they're exploiting a bad padding protocol?)

tptacek 14y ago
They're relying on two classic attacks, one on AES-CBC and one one RSA with PKCS1.5 padding. The former is probably the best known cryptanalytic attack in the world (it's the one Thai Duong and Juliano Rizzo used against J2EE and .NET 2 years ago, and there are publicly available attack tools that will attempt to exploit it against arbitrary targets. The latter is Bleichenbacher's, very well known in the literature but not widely exploited (this is a crypto attack that involves some linear algebra). The rough sketch of both attacks is similar. It exploits a target that holds a secret key and reacts to arbitrary attacker-chosen messages. The attacker has no knowledge of the key, but might have knowledge of a known-good message. The attacker modifies the message in targeted ways and sends to the target; the target attempts to decrypt the message; the decryption goes haywire (because the attacker has modified the message without knowing the key); the target's behavior changes visibly as a result of the decryption going haywire. The attacker knows (1) the nature of the targeted change they made, and (2) whether or not the target reacted weirdly (raised an error, took longer to respond, failed to respond). The attacker continues changing messages and collecting 2-tuples of [change, result]. The whole cryptographic attack then analyzes the list of 2-tuples and from it discerns some secret.
- caf 14y ago
  The researchers in this case have actually made a significant improvement to the Bleichenbacher attack, extending it to use division (multiplication by an inverse) as well as multiplication as in the classic attack.

andrewaylett 14y ago

Note that this is the 800 token, with a USB port, and it's the USB bit that's been broken, not the six-digit ID part that people usually associate with SecurID. My understanding is that the USB port enables the token to sign data on demand, and it's this signing key that's been compromised -- not just for SecurID, but for a whole range of similar encryption tokens.

regularfry 14y ago
I don't know how these things work. Is the generator for the six-digit string related to the signing key?
- astral303 14y ago
  No, those two functions are unrelated. It's a two-in-one: smart card w/ signing key and one-time-password token.

gouranga 14y ago

When we start shipping revokable 64gb compressed one time pad data sticks, I'll have some faith in crypto. Until then, one eye always open.

romaniv 14y ago
I think the motivation behind RSA tokens is that while you can steal them, you shouldn't be able to silently copy one. That's not something you get with an OTP on a USB stick, unless you invest into tamper-proof hardware. Aside from that, I'm not sure why OTPs aren't more commonly used. They're easy to reason about, and while you still need some protocol to use them correctly, it would seem that protocol would be much simpler than for fancy crypto like RSA.
- tptacek 14y ago
  The "some protocol to use them" part is where the crypto in the hardware devices in this attack fell down, which is one of the many reasons people don't use OTPs: they shift all of the security of the system from the cryptographic algorithm itself to the protocol, which is the most error-prone part of the system. Neither RSA nor AES were damaged by this attack.
- tedunangst 14y ago
  You would need a OTP for every one you wanted to talk to. If I had a OTP for every https site I visit, I'd need hundreds. Facebook would need hundreds of millions. They're not going to be mailing out USB sticks on a weekly basis.
  - romaniv 14y ago
    You need an RSA token for each server you talk to as well. It's not a replacement for asymmetric cryptography.
    - tptacek 14y ago
      You'd "need" (in the handwaviest sense, because nobody had designed a crypto token based on one-time pads here) OTP content for every authentication attempt.

zokier 14y ago

Reducing number of iterations by two orders of magnitude is quite impressive. But I don't like how one product is singled out when the attack seems rather generic.

killpg 14y ago

Steal? Those scientists earned those keys.