ECDSA Key Extraction Side Channel in Multiple Crypto Libraries

ECDSA Key Extraction Side Channel in Multiple Crypto Libraries(nccgroup.trust)

86 points by randombit 8 years ago | 8 comments

nayuki 8 years ago |

This is where BearSSL discusses its deliberate design choice to implement constant-time, constant-memory-access arithmetic for its cryptography:

* https://bearssl.org/constanttime.html

* https://bearssl.org/ctmul.html

jamoes 8 years ago |

Looking at libgcrypt's patch [1], it looks like the mitigation technique they're using is to blind the private key and message hash with a random number before performing point addition, and then unblinding the result of the point addition. This unfortunately requires an extra 3 point multiplication operations, so it probably isn't a good solution where performance is critical.

According to the article, the private key information is leaked through memory caches, so it looks like libgcrypt's solution just ensures that the data written to memory caches is random, rather than leaking the private key.

Also according to the article, libsecp256k1 isn't vulnerable, and they still only do 2 point multiplications [2] (compared to libgcrypt's 5 point multiplications). So it is possible to mitigate this attack efficiently.

[1] https://lists.gnupg.org/pipermail/gnupg-announce/2018q2/0004...

[2] https://github.com/bitcoin-core/secp256k1/blob/master/src/ec...

Empact 8 years ago |

The constant-time operation implementation commits to libsecp256k1:

https://github.com/bitcoin-core/secp256k1/search?utf8=%E2%9C...

profquail 8 years ago |

Could this attack be mitigated or otherwise slowed down by using non-temporal memory loads (x86: movntdqa) when reading the private key from memory? Or using clflush to evict the cached private key data from memory after each time it’s used?

The constant-time crypto in BearSSL seems like the best approach — I’m just curious if the above approaches could be used as a quick fix for the affected codebases until they can be fixed properly.

amaccuish 8 years ago |

Was just deciding whether to order smartcards with 4096 RSA or NIST ECC curve support. Whilst not directly related to this, I feel RSA has been examined more closely than ECC given it's long history now of use. Not sure I fully trust the NIST curves, or have faith that ECC implementations have been thoroughly tested.

tptacek 8 years ago | |

I don't think this is a particularly productive way to look at things. RSA has been used for a long time, but the vulnerabilities we find in RSA implementations (for instance, the recent Yubikey RSA keygen flaw) tend to be traceable to things we knew a decade, or sometimes two decades, ago. There's very little general evidence of maturity in crypto development, so that you'd assume that a vendor would learn from industry experience in building something. You just have to sort of guess which constructions they'd have an easier time coding safely.

myWindoonn 8 years ago | |

Disregard feelings, acquire evidence: http://safecurves.cr.yp.to/index.html

pfg 8 years ago | |

One could argue that things like the Infineon prime number generator weakness affecting RSA keys are much more severe than this, but honestly, just flip a coin until modern curves become viable for typical smartcard use-cases.