[HN Gopher] RSA is deceptively simple and fun
___________________________________________________________________
RSA is deceptively simple and fun
Author : mikecarlton
Score : 60 points
Date : 2024-01-17 15:46 UTC (1 days ago)
(HTM) web link (ntietz.com)
(TXT) w3m dump (ntietz.com)
| lisper wrote:
| The basics of RSA are deceptively simple and fun but if you
| actually care about security then there are dozens of details you
| have to worry about which are deceptively nuanced and
| complicated. It's fine to play around with toy implementations
| like this, but you should never ever use such an implementation
| in an application where security actually matters. (In fact, if
| security matters, you probably should not be using RSA at all
| because there are so many ways to shoot yourself in the foot with
| it if you are not extremely careful. ECDH and ECDSA are much
| better, especially when used with Edwards curves like
| Curve25519.)
| glial wrote:
| I always hear this caveat, and I'm sure you're right, but I'm
| curious about the threat model here. If I roll my own RSA using
| e.g. GMP[1], what would it take to find vulnerabilities? Is
| there some automated software that could do it automatically
| for free/cheap, or would it take the resources of a highly
| specialized org?
|
| [1] https://gmplib.org
| pvg wrote:
| Random nerds on the internet with little more training than a
| few of the cryptopals exercises will likely find gaping,
| game-over vulnerabilities in an RSA implementation you threw
| together with an arbitrary precision maths library.
| woodruffw wrote:
| Generally speaking: if your RSA decryption implementation has
| _any_ timing sidechannels, then it is probably vulnerable to
| some kind of Bleichenbacher variant.
|
| As far as I know, GMP doesn't many any attempts to be
| generally resistant to timing channels. This year's
| Bleichenbacher variant[1] specifically calls out GMP's
| modular exponentiation API (which is what you'd use for RSA)
| as being susceptible to timing.
|
| [1]: https://people.redhat.com/~hkario/marvin/
| remexre wrote:
| The post linked in the article as "shouldn't use RSA" has a
| few examples: https://blog.trailofbits.com/2019/07/08/fuck-
| rsa/
| nolist_policy wrote:
| A single fault during signature computation (bit-flip, etc.)
| allows an attacker to derive the private key[1], if you don't
| guard against it by validating everything before sending it
| over the wire.
|
| [1] https://eprint.iacr.org/2023/1711.pdf
| mratsim wrote:
| GMP is not a cryptographic library and using it prevents you
| from being constant-time, you'll also be very slow. That's
| for the math.
|
| Then you'll have non-erased secrets in memory.
|
| Now for RSA specifically, you'll likely have one or more
| issues linked to: - padding oracles - falling to fake primes
| due to using non-hardened Miller-Rabin vs Baillie - Confusion
| on the various PKCS specs - Bleichenbeicher attacks -
| anything in the Wycheproof repo or cryptofuzz
| BunsanSpace wrote:
| The issue with RSA is mainly that not all primes are treated
| equally.
|
| Certain primes are easier to factor which can weaken your
| encryption. That was the biggest one when we where taught
| RSA.
| wim wrote:
| Meanwhile on the web RSA keeps popping up because for some odd
| reason it's the easiest way to do public key encryption using
| the built-in option, Web Crypto (it does support RSA-OAEP, but
| still). With interfaces like this
| https://developer.mozilla.org/en-US/docs/Web/API/RsaHashedKe...
| I'm sure there's plenty of typos to be found just setting the
| publicExponent for example.
|
| There are good third-party libraries but it's too bad Web
| Crypto doesn't offer something like libsodium's sealed box (or
| XChaCha for that matter on the symmetric side) to make
| encryption less of a footgun for devs building web apps.
| thadt wrote:
| WebCrypto also supports ECDH/ECDSA, so one _could_ get by
| without RSA. But point well made about it being too bad that
| WebCrypto doesn 't offer higher level tools. I'm developing
| one such third-party library right now, and while HPKE[1] is
| a pretty thin layer on top of WebCrypto, it's unfortunate
| that it has to be written in JS at all. Last I checked, the
| crypto library sitting under Chrome (and probably Firefox as
| well?) already has HPKE implemented. If only there were a
| nice API through to it..
|
| [1] https://datatracker.ietf.org/doc/rfc9180/
| tptacek wrote:
| There aren't many times where direct application of RSA's
| encryption transform, to recover semantically meaningful
| data, is useful. But widespread use of RSA predates modern
| crypto (what people used to call "Crypto 2.0", hallmark
| feature being authenticated encryption), so it's still in all
| the APIs.
| medo-bear wrote:
| This is somewhat of a side question, but do you have an opinion
| on Ironclad, the Common Lisp encryption library?
|
| https://github.com/sharplispers/ironclad
| woodruffw wrote:
| Nice writeup, and the point (RSA _is_ very simple, until you
| actually to need it securely!) is conveyed well.
|
| One thing of note: BB98 essentially springs eternal; a new way to
| find the single bit of oracle state needed for it is discovered
| every few years. See ROBOT[1] (2018) and this year's Marvin[2].
|
| [1]: https://robotattack.org/
|
| [2]: https://people.redhat.com/~hkario/marvin/
| tptacek wrote:
| This is a fun exploit to code up, and, stealing a note from a
| workshop tutorial we found, we build up to it with an RSA parity
| oracle in Cryptopals 6:
|
| https://cryptopals.com/sets/6
|
| The parity oracle is much easier to code, but I've never seen it
| in the wild. BB'98 (the "million message attack") on the other
| hand comes up all the time, even in new code; it's deceptively
| tricky to prevent.
|
| I think this bug is probably a contender for the top 3 practical
| cryptography vulnerabilities on the Internet. Its close cousin,
| Vaudenay's CBC padding oracle, is a lock for #1. Then it's just
| down to whether nonce reuse is #2 or #3.
| 616c wrote:
| > I think this bug is probably a contender for the top 3
| practical cryptography vulnerabilities on the Internet. Its
| close cousin, Vaudenay's CBC padding oracle, is a lock for #1.
| Then it's just down to whether nonce reuse is #2 or #3.
|
| Is this top 3 list from some public resource that exists and I
| am a noob who missed the reference and how the community knows
| what the Top 3 are? If not a resource would love to see it or
| help make it.
|
| P.S. Been loving SCW podcast from time to time when I can list,
| keep up the good work!
| tptacek wrote:
| Nope, it's off the top of my head, and partially proffered as
| a provocation to other professionals to protest.
| uticus wrote:
| I always wonder who's watching the watchers with encryption. I
| know there are standard, recommended libraries available. But how
| are those vetted if mere mortals like myself don't even know what
| known vulnerabilities to look for? Is there like a high council
| of crypto wizards that keep checks and balances on each other?
| sacrosanct wrote:
| As a rule of thumb, pay attention to crypto parameters and
| cipher 'suites'. Use the highest SHA, use seven word diceware
| phrases for the password, ensure the latest TLS version is
| used, use a reputable & robust RNG, etc
| tptacek wrote:
| SHA2 is fine. The "reputable" RNG comes with your OS; just
| use getrandom.
| Buttons840 wrote:
| Whenever I'm roleplaying with my tinfoil hat, I say that the
| NSA is behind the "never implement your own crypto" advice.
|
| If you're really worried, roll your own encryption, and then
| also run the encrypted message through standard encryption
| implementations. After all, if the standard implementations
| work, it doesn't matter if you mess up your own crypto
| implementation, because the standard implementation is
| unbreakable.
| Analemma_ wrote:
| Whenever _I 'm_ roleplaying with my tinfoil hat, I say that
| the NSA is behind comments like yours.
|
| You cannot assume that the security of a composite
| crypotsystem is max(system1, ..., systemN), i.e. that bolting
| a secure system to an insecure one is at least as secure as
| the most secure system. Sometimes it is; sometimes it is not
| and the insecure system breaks the whole thing in a way that
| casual analysis can't spot. If _I_ were the NSA trying to
| inject memes into the software ecosystem to make my job
| easier, I would definitely recommend that everybody start
| with vetted open-source cryptosystems and then bolt their
| hand-rolled crap to them.
| Buttons840 wrote:
| If it's true that modifying my plaintext before putting it
| through a standard encryption algorithm might affect the
| security, then it might also be possible that sending, say,
| an HTML payload is more secure than sending a JSON payload.
| That would be weird.
|
| Can existing encryption algorithms encrypt _any_ payload or
| can 't they? It would be odd if we're worrying about timing
| attacks, etc, when we can't even securely encrypt any
| possible plaintext first.
| tptacek wrote:
| Cryptography engineers and vulnerability researchers who
| specialize in cryptography look for vulnerabilities in the
| popular libraries. Cryptographic vulnerabilities are high-
| status (if you find a pattern of them, you can even get
| published in the Big 4 academic venues). So there's a lot of
| incentive to find stuff, at least in popular software.
|
| It's a much bigger problem for bespoke crypto people roll
| themselves, because the expertise required to find crypto
| vulnerabilities is uncommon, and there's not that much
| incentive at all to find a vulnerability in something nobody
| uses.
| Sohcahtoa82 wrote:
| > Is there like a high council of crypto wizards that keep
| checks and balances on each other?
|
| Not exactly, but certainly there are some crypto wizards that
| would love to get famous for figuring out how to break the so-
| called trusted algorithms and libraries.
| lnrd wrote:
| I think this "high council of crypto wizards" is academia, at
| the end of the day we are talking about advanced math and i
| think there are many experts on that field eager to prove and
| correct each other.
| coppsilgold wrote:
| The way RSA key exchange has been implemented everywhere involves
| padding. RSA-KEM[1] has been available since forever and no
| padding is required, though no one uses it for some reason.
|
| RSA-KEM is also trivial to implement as it's virtually identical
| to textbook RSA, with the sole restriction that m has to be
| randomly sampled from 1 .. n-1. The shared secret (technically,
| the encapsulated key) is the hash of the randomly sampled number.
|
| And just like that, no padding oracles or the headache of
| implementing padding in the first place.
|
| [1] <https://en.wikipedia.org/wiki/Key_encapsulation_mechanism> ,
| <https://datatracker.ietf.org/doc/html/rfc5990>
| SAI_Peregrinus wrote:
| RSA-KEM _is_ nice, but RSA keygen is expensive. That makes
| using RSA for ephemeral key exchange less attractive than
| ECDHE. RSA-KEM is fine for static-static key exchanges, and
| RSASSA-PSS is fine for signatures. But we often want ephemeral-
| static or ephemeral-ephemeral key exchange, and there RSA is
| slow for little benefit.
| coppsilgold wrote:
| One aspect of RSA that may help it become relevant again is
| that the key size can be arbitrary by utilizing multiple
| primes (RSA-MP[1]) and therefore increase the qubit
| requirement for a successful quantum attack. This could lead
| to a situation where large RSA keys would remain secure for
| decades longer than ECC keys, and if quantum computers hit a
| growth wall then those RSA keys could remain secure forever.
|
| RSA-MP would then serve as a hedge (by either ending up
| completely secure, or buying time) against novel* PQC
| algorithms being broken. The cost being large public keys,
| large ciphertexts, slow decryption and very slow keygen.
|
| Another option is to come up with enormous safe primes for
| good old DH. This would result is very fast keygen, and
| decryption performance will equal encryption - but will
| probably be worse than RSA anyway. The biggest public DH safe
| prime I'm aware of is 16384 bits (unofficially released by
| someone who worked on some DH standard which ended on 8192
| bits).
|
| * McEliece is not novel but did not see as much scrutiny as
| RSA. And has huge public keys - so might as well be paired
| with RSA?
|
| [1] <https://www.degruyter.com/document/doi/10.1515/JMC.2008.
| 006/...>
| jbverschoor wrote:
| 0 lessons learned in this write up without knowing almost
| everything about RSA..
|
| Better watch some discrete math 2 videos from Kimberly Brehm or
| TrevTutor to see how you can actually compute it.
___________________________________________________________________
(page generated 2024-01-18 23:00 UTC)