Love the play by play. Was aware of the handshake after that I thought there would be some matrix like kung-fu fight scene...
Seriously, thanks for the share and kudos to the author.
Really well written! One thing I was curious about was the use of TLS_RSA_WITH_RC4_128_MD5 instead of TLS_DHE_RSA_WITH_AES_256_CBC_SHA: what's the difference between these setups in terms of mem/cpu usage? Obviously it varies between servers, but is it roughly 2x, 10x slower?
The relative cost of the symmetric bulk encryption algorithms (RC4 vs AES here) is irrelevant compared to the expense of the key exchange/agreement and authentication.
The first ciphersuite uses the most common option where the server sends a certificate containing an RSA public key and the client chooses a random number, encrypts it with this key, and sends the encrypted value to the server. The server then decrypts this value with the private half of the key and derives the session keys from it. The expense of this decryption increases with the length of the RSA modulus.
The second ciphersuite uses ephemeral diffie-hellman where both sides choose a random number, and then exchange them. In order to accomplish this securely, the server must at least provide a certificate with an RSA key that supports signing (and signature verification) so that the client can verify that the diffie-hellman parameter received from the server has not been tampered with.
The DH parameter sent from the client to the server needs to be checked out too, and there are two ways this can be accomplished. If the server certificate contains a second RSA key which is marked as suitable for encryption, then the client can simply encrypt with this key as in the simple RSA key exchange described above. If this encryption key does not exist, then TLS provides a crazy way that the handshake can still succeed:
1) The server generates a temporary RSA key pair (very expensive)
2) The server signs the public half of the key pair with the RSA signing key in the certificate, and sends it to the client.
3) The client uses this key to encrypt the diffie-hellman value to send to the server.
When the diffie-hellman parameters have been exchanged the server must perform an RSA private-key operation to either decrypt the client value or verify the signature on it. This has the same cost as in the first type of key exchange and depends again on the length of the RSA key. After verifying the client value, the server must complete the DH protocol which requires an expensive modular exponentiation which is roughly as expensive as an RSA operation.
So no matter what, the second option is going to perform worse than the first option. The real reason though that the server probably rejected the second ciphersuite is because no certificate was available with an RSA signing key needed to complete the protocol.
Unfortunately, RC4 and AES are not comparably secure, and by conflating the cipher with the protocol variants, that issue is somewhat muddied by the article. Nobody should be using RC4. It's also a bit misleading to say that AES encrypts "16 bytes at a time" where RC4 encrypts 1 at a time: AES can easily be turned into a byte-at-a-time stream cipher using CTR mode; there's just not much value to doing so in TLS.
There's another reason why DHE isn't super popular: inside enterprises, security groups will have reasons to want to monitor connections to their servers. DHE makes that pretty much impossible, by decoupling the server's private key from the actual session key. This sounds like a good thing until you realize that such monitoring has no privacy implications at all (they own the server, they can just sniff the sockets), only (negative) operational implications.
I don't think this opinion gets enough play. A collision attack on SHA-1 is published which is still 'academic' enough that nobody has actually produced a single collision and Debian thinks it's worth re-keying their entire infrastructure over ("Attacks will only get better!").
Meanwhile, Fluhrer, Mantin, Shamir tore RC4 a new one almost a decade ago and everybody just applied a kludge and forgot about it. Then 5 years later, improved attacks are published and still no talk about permanently retiring RC4.
I could be wrong but I think what's happening is this:
RC4 is the only stream cipher anybody really knows.
People don't really understand how OFB and CTR mode work, and don't get that AES is already a serviceable stream cipher.
Therefore, people don't really have a "go-to" stream cipher besides RC4.
You'd hope eSTREAM would change that --- Trivium would make a great replacement for RC4 --- but it may be that NIST simply has to bless something to make RC4 go away.
RC4 is also just plain beautiful; it's a permutation of all unique bytes with just two pointers into the array. It's implementable in what, 4 lines of code?
Trivium is comparably simple, I guess, but the LFSR-like structure makes for significantly longer (and uglier, IMHO) code. Trivium is also brand new and has had vastly less attention paid to it. RC4 isn't "unbroken" exactly, but even after all these years RC4-based protocols are working securely in the real world right now, and that has to count for something.
I'm not arguing for using RC4 either. The sentiment is more: "Don't diss RC4, it's still a really great piece of work."
The fact that the most elegant solutions are rarely secure is yet another reason why otherwise sane developers shouldn't be going anywhere near cryptography.
RSA is elegant and secure. MD5 is ugly and broken. RC4 is really elegant and not-quite-unbroken. I've extended the data set now to three points, and the graph looks like a pretty good correlation between elegance and security, actually. Your text implies the opposite, and I think that's wrong.
Crypto stuff is just hard. But I think that elegance is as good a guide to correctness there as it is anywhere else. Elegance never gets you correctness automatically anywhere. But it's not a bad place to start your analysis.
RSA quickly becomes a lot less elegant once you start patching in all the cracks.
What I mean is that if you give an otherwise competent developer who is not a cryptographer a description of the elegant version of the RSA algorithm and ask them to implement it and design a secure protocol what they come up with will be completely broken.
Sure. But to be honest, that point is kinda trivial, no? If you give any competent developer a hard problem in an area where they are not a domain expert and ask them to deliver a correct solution based on nothing but an elegant description of an algorithm, they're likely to fail.
My point was this: it's easy from your perspective to complain about subtle practical details with stuff like RC4. But that obscures the fact that RC4 is an important algorithm, and worth studying. It's prudent to put on your expert hat and warn amateurs away from crypto stuff, but if they're going to study it, they should know about RC4.
I guess I'm not so much dissing RC4 as pointing out a ridiculous double-standard. Almost every application of RC4 depends on correlation immunity while most applications of SHA-1 do not require collision resistance.
That said, I don't think RC4 is a reasonable cipher to use anymore. It has fallen to so many attacks already that it's impractical to expect people to be aware of all the caveats and pitfalls regarding it's use. At the very least it should be respecified with a new key schedule that drops the first N keystream bytes rather than leaving that as an 'implementation detail'.
> This sounds like a good thing until you realize that such monitoring has no privacy implications at all
If you don't have forward secrecy then there is the possibility that an adversary can silently sniff your traffic for as long as they want and then later steal your private key and decrypt everything.
This is a threat that really matters to some people:
That's true, and my point isn't that EDH is bad; it's that there are cases where you don't want it used, like when you own the servers and operationally want the ability to monitor connections from other vantage points that would also have the server's private key.
I need to correct something here. The temporary RSA key generation is never used for ephemeral DH, but rather for the situation where RSA key exchange is requested and only a signing key is available.
The server does not even verify an explicit signature on the client DH value because this is covered when the entire handshake is validated in the final step (The finish message).
Since the server does not perform an RSA operation on the client value, my conclusion about performance is totally bogus.
I frequently wish descriptions like this existed in a fractal form with ever increasing complexity that could be "zoomed in" (or out) for more or less detail. Many times the problem is the inverse, some overly generalized news blurb lacking details or even reference links.
This seems like the well crafted super magnified version. I loved all of the in-line reference links!
But rather than just section headings, perhaps complete sentences that you could "zoom-in" to more detailed wording. Or if things seem to be too detailed, you could zoom-out.
Seems hard to automate.
Better writing could probably solve a lot of my frustration (not for this article though).
An ideal application would be for educational material (such as this post). Where it's worth the significant human effort to craft the multiple variants of the subject.
I'm a really noob coder, and not a web developer, so I don't know what functions etc are responsible for this, but couldn't you use the code governing the common "More..." link often used to truncate reviews?
(e.g. Sesame Street is... (More...) - > Sesame Street is a children's show.)
Also, each sentence could be an object of sorts with one value for the simplified version and references to other objects that constitute the detail of the simple sentence. The referenced objects could be of the same class, and, in turn, resolve to even further detail by reference.
The pitfall is, of course, that it would require some extra thought while writing to keep everything cohesive and sensible with varying levels of complexity on the page at the same time.
This is a fine article. Unfortunately, it describes very specifically how not to verify an PKCS RSA signature, perpetuating a mistake that screwed over browser vendors a couple years back:
To wit: you verify specifically cannot look at the SHA-1 hash at the end of an RSA block and compare it to your own hash, because there are hundreds of zillions of other RSA blocks that can result from the RSA algorithm that could contain a SHA-1 block of an attacker's choosing.
Vendors learned the hard way that to verify an RSA signature, you have to reconstruct the entire m block you'd expect to see, and byte compare it to the entire "decrypted" m block from the certificate.
Don't link to that source code. Mozilla's RSA implementation is really hard to follow. The most important security check there is nowhere near the function you've linked to. The "length" of the block isn't the issue (the "length" is the key size); verifying that every bit of the expected m block matches, bit for bit, with the received m block is.
Don't get me wrong. Great article. It has to be possible for general practitioners to write about encryption without inciting people to write their own, the same way it has to be possible for general practitioners to write about brain surgery without inciting people to cut other people's heads open. You didn't intend this as an implementation guide. =)
Thanks for the kind words! It's humbling to have a security pro like you even read it :). I dabble with this stuff because I find it interesting (especially the number theory). The Wireshark'ing was to see how things really worked.
Hopefully the links I made to the Netscape and Debian OpenSSL RNG fiascos along with at least some coverage of how many subtle checks the handshake performs terrifies people enough to follow the exhortation I put at the end: "It's certainly better to use TLS than inventing your own solution."
Most developers would probably find Crypt++'s implementation of RSA verification --- or even, gag, LibTomcrypt --- a better rundown of how to do this safely. Too much of Mozilla NSS's functionality is scattered across multiple modules and indirected through function pointers.
Vendors learned the hard way that to verify an RSA signature, you have to reconstruct the entire m block you'd expect to see, and byte compare it to the entire "decrypted" m block from the certificate.
Not exactly. Yes, you have to verify the padding; no, you don't have to build a decrypted signature and compare the two byte by byte.
The lesson here is "use proper padding and follow the published instructions for verifying it".
33 comments
[ 0.20 ms ] story [ 81.5 ms ] threadThe first ciphersuite uses the most common option where the server sends a certificate containing an RSA public key and the client chooses a random number, encrypts it with this key, and sends the encrypted value to the server. The server then decrypts this value with the private half of the key and derives the session keys from it. The expense of this decryption increases with the length of the RSA modulus.
The second ciphersuite uses ephemeral diffie-hellman where both sides choose a random number, and then exchange them. In order to accomplish this securely, the server must at least provide a certificate with an RSA key that supports signing (and signature verification) so that the client can verify that the diffie-hellman parameter received from the server has not been tampered with.
The DH parameter sent from the client to the server needs to be checked out too, and there are two ways this can be accomplished. If the server certificate contains a second RSA key which is marked as suitable for encryption, then the client can simply encrypt with this key as in the simple RSA key exchange described above. If this encryption key does not exist, then TLS provides a crazy way that the handshake can still succeed:
1) The server generates a temporary RSA key pair (very expensive)
2) The server signs the public half of the key pair with the RSA signing key in the certificate, and sends it to the client.
3) The client uses this key to encrypt the diffie-hellman value to send to the server.
When the diffie-hellman parameters have been exchanged the server must perform an RSA private-key operation to either decrypt the client value or verify the signature on it. This has the same cost as in the first type of key exchange and depends again on the length of the RSA key. After verifying the client value, the server must complete the DH protocol which requires an expensive modular exponentiation which is roughly as expensive as an RSA operation.
So no matter what, the second option is going to perform worse than the first option. The real reason though that the server probably rejected the second ciphersuite is because no certificate was available with an RSA signing key needed to complete the protocol.
There's another reason why DHE isn't super popular: inside enterprises, security groups will have reasons to want to monitor connections to their servers. DHE makes that pretty much impossible, by decoupling the server's private key from the actual session key. This sounds like a good thing until you realize that such monitoring has no privacy implications at all (they own the server, they can just sniff the sockets), only (negative) operational implications.
I don't think this opinion gets enough play. A collision attack on SHA-1 is published which is still 'academic' enough that nobody has actually produced a single collision and Debian thinks it's worth re-keying their entire infrastructure over ("Attacks will only get better!").
Meanwhile, Fluhrer, Mantin, Shamir tore RC4 a new one almost a decade ago and everybody just applied a kludge and forgot about it. Then 5 years later, improved attacks are published and still no talk about permanently retiring RC4.
RC4 is the only stream cipher anybody really knows.
People don't really understand how OFB and CTR mode work, and don't get that AES is already a serviceable stream cipher.
Therefore, people don't really have a "go-to" stream cipher besides RC4.
You'd hope eSTREAM would change that --- Trivium would make a great replacement for RC4 --- but it may be that NIST simply has to bless something to make RC4 go away.
Trivium is comparably simple, I guess, but the LFSR-like structure makes for significantly longer (and uglier, IMHO) code. Trivium is also brand new and has had vastly less attention paid to it. RC4 isn't "unbroken" exactly, but even after all these years RC4-based protocols are working securely in the real world right now, and that has to count for something.
I'm not arguing for using RC4 either. The sentiment is more: "Don't diss RC4, it's still a really great piece of work."
Crypto stuff is just hard. But I think that elegance is as good a guide to correctness there as it is anywhere else. Elegance never gets you correctness automatically anywhere. But it's not a bad place to start your analysis.
What I mean is that if you give an otherwise competent developer who is not a cryptographer a description of the elegant version of the RSA algorithm and ask them to implement it and design a secure protocol what they come up with will be completely broken.
My point was this: it's easy from your perspective to complain about subtle practical details with stuff like RC4. But that obscures the fact that RC4 is an important algorithm, and worth studying. It's prudent to put on your expert hat and warn amateurs away from crypto stuff, but if they're going to study it, they should know about RC4.
If, like me, they're faced with it in practice, then what they need to know is, "bad".
That said, I don't think RC4 is a reasonable cipher to use anymore. It has fallen to so many attacks already that it's impractical to expect people to be aware of all the caveats and pitfalls regarding it's use. At the very least it should be respecified with a new key schedule that drops the first N keystream bytes rather than leaving that as an 'implementation detail'.
If you don't have forward secrecy then there is the possibility that an adversary can silently sniff your traffic for as long as they want and then later steal your private key and decrypt everything.
This is a threat that really matters to some people:
http://www.libertysecurity.org/article342.html
http://techmeet.sarava.org/uploads/Agenda/SSL_For_Activists....
The server does not even verify an explicit signature on the client DH value because this is covered when the entire handshake is validated in the final step (The finish message).
Since the server does not perform an RSA operation on the client value, my conclusion about performance is totally bogus.
I frequently wish descriptions like this existed in a fractal form with ever increasing complexity that could be "zoomed in" (or out) for more or less detail. Many times the problem is the inverse, some overly generalized news blurb lacking details or even reference links.
This seems like the well crafted super magnified version. I loved all of the in-line reference links!
If you (or anyone really) are interested in hearing me out or helping, email me.
But rather than just section headings, perhaps complete sentences that you could "zoom-in" to more detailed wording. Or if things seem to be too detailed, you could zoom-out.
Seems hard to automate. Better writing could probably solve a lot of my frustration (not for this article though).
An ideal application would be for educational material (such as this post). Where it's worth the significant human effort to craft the multiple variants of the subject.
(e.g. Sesame Street is... (More...) - > Sesame Street is a children's show.)
Also, each sentence could be an object of sorts with one value for the simplified version and references to other objects that constitute the detail of the simple sentence. The referenced objects could be of the same class, and, in turn, resolve to even further detail by reference.
The pitfall is, of course, that it would require some extra thought while writing to keep everything cohesive and sensible with varying levels of complexity on the page at the same time.
http://www.matasano.com/log/558/public-key-signature-forgery...
To wit: you verify specifically cannot look at the SHA-1 hash at the end of an RSA block and compare it to your own hash, because there are hundreds of zillions of other RSA blocks that can result from the RSA algorithm that could contain a SHA-1 block of an attacker's choosing.
Vendors learned the hard way that to verify an RSA signature, you have to reconstruct the entire m block you'd expect to see, and byte compare it to the entire "decrypted" m block from the certificate.
Crypto sucks.
and link to the matasano series, would that better address your concern?
Don't get me wrong. Great article. It has to be possible for general practitioners to write about encryption without inciting people to write their own, the same way it has to be possible for general practitioners to write about brain surgery without inciting people to cut other people's heads open. You didn't intend this as an implementation guide. =)
Hopefully the links I made to the Netscape and Debian OpenSSL RNG fiascos along with at least some coverage of how many subtle checks the handshake performs terrifies people enough to follow the exhortation I put at the end: "It's certainly better to use TLS than inventing your own solution."
And did you mean Crypto++?
Not exactly. Yes, you have to verify the padding; no, you don't have to build a decrypted signature and compare the two byte by byte.
The lesson here is "use proper padding and follow the published instructions for verifying it".