[tptacek]

You read that when SaltStack managed to set e=1 in their SSH replacement protocol, and what you read was SaltStack and its defenders arguing that the mistake wasn't as calamitous as it actually was. And you probably read about it because people like Coda Hale (and, yes, me) pointed it out on Twitter.

It eludes me how you turn someone's terrible custom crypto into a parable about how we should be nicer to custom crypto.

[tzs]

Wow...e=1? That makes me feel better about my biggest crypto goof, which I had assumed was the stupidest mistake anyone had ever made with RSA, but e=1 is worse.

Briefly, I was doing a single RSA encryption on the client and corresponding RSA decryption on the server as part of a login procedure, and using e=3 (which, at the time, was considered acceptable by most experts). Due to licensing issues the client code had to be all ours, so I was using an old arbitrary precision integer library I had written years before. It was not super fast. The multiplication wasn't too bad (Karatsuba), but division was the classical division algorithm. On the server there were no licensing issues, and I was using gmp.

So I had this "brilliant" realization. Why not do the division ON THE SERVER? The client could simply compute M^3 and send that to the server. The message would be 3 times longer but bandwidth was cheap. The server could then do the modular reduction.

I quickly made the change to the client and then started to revise the server code, when it occurred to me that since the client had made no use whatsoever of the modulus there must be a way to decrypt the message without using the modulus--like by just taking the cube root. Doh!

[tptacek]

Yes, that actually happened:

https://github.com/saltstack/salt/commit/5dd304276ba5745ec21...

There's an interesting real-world RSA bug related to yours: in the absence of proper padding, it's possible that e=3 RSA of a small plaintext might not wrap the modulus. A similar cube root operation produces a signature that naive implementations (the ones that check the digest embedded in a signature block, but not the padding) will validate, despite the attacker lacking the signing key. That bug bit Firefox's NSS library; for a little while, it was possible to use a short Python script to forge any certificate.

(That bug is due to Bleichenbacher, who called it a "pencil-and-paper" attack in the rump session he presented it in).

e=3 RSA isn't insecure per se, but it does magnify the impact of other vulnerabilities, and so it's best avoided.

As my literal not-making-this-up favorite HN commenter and someone who has previously expressed an interest in crypto, I'd love it if sometime you could take some time to demolish our crypto challenges. I'd be happy to send them all at once to you.

[tzs]

I have signed up for the first set of challenges, although I doubt I'll do well on them. I'm not very good at that kind of challenge--with crypto I tend to do better on the theory side [1] than on the practical side when it comes to dealing with breaking things.

[1] by "theory" I mean vigorous and convincing hand waving and white board diagramming...