Hacker News new | past | comments | ask | show | jobs | submit login

From my point of view, RSA has been damaged by too many bad implementations and standards, eventhough it is a legitimate cryptographic algorithm. I even co-authored a paper[1] with Shamir himself that ended on recommending not to use RSA in 2019.

I'm currently writing a book targetted to developers[2] and I'm wondering how much I should write about RSA.

There are two cryptographic primitives (types of algorithm) exposed by RSA:

* Encryption

* Signature

The signature algorithm has two adopted standards usually named RSA PKCS#1v1.5 and RSA-PSS. The latter one is more recent and provides a proof of security but everyone still use the former. The former hasn't been broken and is still pretty solid. Most internet certificates are signed using RSA PKCS#1v1.5 I believe.

The encryption algorithm is the problem (also used to perform key exchanges). It also has two adopted standards usually called RSA PKCS#1v1.5 (same name as the signature scheme I know...) and OAEP. OAEP is more recent and quite secure, but nobody seems to use it. Instead the former is still largely used in applications, and is often the default algorithm you use when you write RSA in many cryptographic libraries. Unfortunately it has been broken by Bleichenbacher in 1998 and it is practical to attack it. There's been many attempts to "fix" it and they have been repeatidly broken as well. So don't expect the library you use to implement it correctly.

[1]: https://eprint.iacr.org/2018/1173 [2]: https://www.manning.com/books/real-world-cryptography

> The former hasn't been broken and is still pretty solid. Most internet certificates are signed using RSA PKCS#1v1.5 I believe.

FYI, RSA PKCS#1v1.5 signatures can be broken due to trivial implementation errors. [1]

[1]: https://www.cs.purdue.edu/homes/schau/files/pkcs1v1_5-ndss19...

Thanks! I hadn't seen that paper :)

From a cursory glance, all of these implementations are in C it seems like a C systemic issue, not an issue with RSA.

But I might be wrong because I've yet to read the paper.

I'm confident you were aware of the bug in that paper, David, since it's just the e=3 cube-root attack on unvalidated P1v15 padding.

Are you talking about the broadcast attack? This is on signatures, and it seems different from bleichenbacher's signature forgery.

(But again, haven't read the paper, also don't remember how bb signature forgery works)

(I'll read the paper but right now I'm in Hawaii doing snorkeling)

This is in Cryptopals! You were a Cryptopal! How did you get through that without implementing the e=3 sig attack?

The bug is straightforward: RSA implementations don't verify all the bits in the padding, but rather "parse" it to find the digest, and then verify that. But there are, of course, bajillions of potential padded signature block representations that contain any given digest, since the block is so much bigger than the digest. For e=3, and for particularly naive implementations (like Firefox's, at the time) you can almost literally just formulate the signature block you want, then take its cube root to forge a signature.

Oh right. Thanks for the reminder :)

Sorry to disapoint I did not do all the cryptopals :P filippo actually has a good blogpost on that attack IIRC.

You have, in fact, disappointed me! :|

(There are some set-7 problems I haven't done yet, for whatever that's worth. But e=3 sigs are a big one!)

Alright I will do it :D

Honestly, if you can find a broken implementation (or just write one; do the RSA "decrypt" of the signature block, and then just use a constant offset to get to the digest bytes), you should be able to knock it out just from the description I provided in like, 30 minutes.

The issues are not due to C but rather failing to verify the PKCS#1v1.5 format. For example, skip verifying the padding or metadata, etc. This allows to insert garbage data in the signatures which leads to successful signature forging.

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact