8 ms·

I hope that the actual vulnerability is far more complicated. If we can't even get crypto libraries right (where you'd hope most of the formal verification folk

by _hl_ 7y ago

I hope that the actual vulnerability is far more complicated. If we can't even get crypto libraries right (where you'd hope most of the formal verification folks are), then there's not much hope of security for the rest of the industry. I'm normally not much of a pessimist but things like this really make me wish we could just burn all the things and start over.

tptacek 7y ago
There's a history of vulnerabilities like these, in some of the most important crypto libraries. For instance: until 2008, NSS, the TLS library used by Firefox, couldn't properly validate RSA signatures from e=3 RSA keys (it wasn't validating the full signature block, but rather parsing it and looking for the embedded hash). For e=3 roots, which were readily available at the time, you could simply build any signature block you wanted and then take its cube root.
- Herrera 7y ago
  Bleichenbacher'06 never dies.
  - CiPHPerCoder 7y ago
    Neither does BB'98
    - baby 7y ago
      Can’t wait for BB20
- gonnabezuul 7y ago
  Interesting. Were there any similar vulnerabilities in Windows XP's crypto libraries?
  - tptacek 7y ago
    There have been crypto vulnerabilities in Windows libraries before, but not the e=3 vulnerability; CryptoAPI parsed RSA signatures back-to-front, and so sidestepped the issue.
munchbunny 7y ago
This stuff often looks simpler and less subtle in hindsight. Modern cryptography has gotten better at taking human (developer) error into account for designing secure API’s, but the fact of the matter is that the math is subtle, and cryptography in general is subtle due to the places where it collides with reality, so burning everything down and starting over is likely to just cause us to rediscover issues we already know about. Say we stop using X509 certificates. We will continue to use signing to cryptographically bind claims, and we will still use PKI-like structures to attest trustworthiness, so we are still vulnerable to the same approaches of attacks even if we don’t use certificates. We have actually learned a few things, such as that cryptographic agility seems to cause more issues than the problems it solves, so the field is improving in important ways, but if it’s not a key matching weakness, it’s going to be some Unicode encoding BS or some other critical but not validated data somewhere else, or... (because this is a real in the wild problem) using phone numbers to generate cryptographic keys for coin wallets.
- tptacek 7y ago
  This is true, but the bug here is not subtle. It would have been shocking to discover an ECC implementation that let attackers specify curve parameters even 10-15 years ago. When we blogged the e=3 debacle back in '07 or whatever, we linked to a Kaliski presentation from 1999 that called out validating curve parameters. At least with the ACME vulnerability, there was a novel service model involved. Here, we're talking about certificates that allow you to embed what is in effect your own cryptographic algorithm to interpret the certificate under! This is a rare instance where I'm happy to concede that closed source allowed a terrible bug to survive far longer than it would have if nobody needed to break out a copy of Ghidra to read the code that validated elliptic curve signatures.
  - john_alan 7y ago
    Very interesting take. Good description of Pornins thoughts. By the way, when you say closed src allowed... do other libs in the opensrc space check the curve Params?
    - 7y ago
loup-vaillant 7y ago
> If we can't even get crypto libraries right Signature verification is one of the hardest things to get right. One reason is, they're harder to test: when you encrypt or hash something, you have a whole bunch of bits you can check against test vectors. With signature verifications, you only have one bit: it's a match, or it's a fail. Moreover, it's very easy to forget to check something (here, that we are using the same base point). Other constructions, like EdDSA, are simpler, and verification requires a single equality check. Harder to botch. And even then, implementers can be tempted to get clever, which requires extra care. I've personally been bitten by not verifying mathematical jargon, and mistakenly thought "birational equivalence" was complicated speak for "bijection". Almost, but not quite. This single oversight lead to a critical, easy to find, easy to exploit vulnerability. We found out 15 months later, 1 full year after public release, by tinkering with the tests. A cryptographer would have found it in 5 minutes, but as far as I can tell, they're all very busy.
- baby 7y ago
  That’s an interesting assessment. Rogaway just gave a talk at RWC about APIs for secret splitting schemes. IIRC he said that the API needed to be closer to what symmetric crypto was. But from the diagram it seemed like you were obtaining some associated data back to check that the secret was correct (not sure if this would work/is relevant with more recent DKG schemes). A signature verification returning an actual AD would be interesting as well.
  - loup-vaillant 7y ago
    EdDSA can have something close. Long story short, an EdDSA signature has two parts, often called "R" and "s". Verification works by producing a number using the public key and "s", then checking that this number is the same as "R". There are basically 3 steps: 1. h_ram <- HASH(R || public_key || message) 2. R_check <- obscure_computation(public_key, s, h_ram) 3. if R_check == R, accept, else reject Steps 1 and 3 are straightforward (the hash and the constant time comparison are almost always implemented in dedicated routines, tested separately). Step 2 is the most dangerous (that's where the elliptic curve magic happens). EdDSA Implementations would be easier to check against one another if they all exposed step 2 as part of the public API. Bonus points if step 2 can handle invalid inputs (low order point, point on the twist...) in a standard manner. I haven't seen such a thing though, probably because end users never need a separate step 2. Still, I can already envision the benefits. I'll probably use it myself.
mleonhard 7y ago
We need one time pads. They're the only really trustworthy crypto.
- tptacek 7y ago
  By all means: make yourself some one-time pads. Maybe you can convince Google to accept one from you at a dead drop somewhere in Mountain View.
- bscphil 7y ago
  Hmm. Maybe I'll generate some high quality OTPs for myself with a good CSPRNG. I could use any decent block cipher in counter mode, just need to guard against counter re-use, and then ship my OTPs off to anyone I need to communicate with. Hang on, if I could come up with a way of securely sharing the key I used with my recipient, I wouldn't need to actually mail the OTP to them, since they could generate it themselves. Should probably include a nonce too. Now, if only there were a secure method to share the key...
  - Tomte 7y ago
    > Maybe I'll generate some high quality OTPs for myself with a good CSPRNG That's not a one-time pad, it's simply a stream cipher.
    - schoen 7y ago
      That's the joke!
  - jancsika 7y ago
    > Now, if only there were a secure method to share the key... ... that doesn't include a critical cryptographic vulnerability. :) To be generous to the now greyed GP, there's probably a way to teach a recipient a short pad and its proper use so that the recipient can later decode a short ciphertext sent over Twitter. Perhaps even performing that feat in their head. None of the cryptography that could fit your quip has that property. And if the recipient does something catastrophic like resend the pad over Twitter to confirm they memorized it correctly, there's at least a chance they may catch their error. Perhaps they may even correct it without the goddamned Department of Defense coming into it. I don't get cryptographers' condescension toward OTP zealots. All they want is a better boat. At least have the decency of the captain from Titanic and apologize while we sink for not having delivered it.
derefr 7y ago
> If we can't even get crypto libraries right (where you'd hope most of the formal verification folks are) Personally, I'd hope most of the formal verification folks are working in firmware for industrial/medical embedded systems, and/or the microcontroller designs that go into those same systems. A lack of encryption (outside of military contexts) doesn't usually directly cause people to die.
- jpgoldberg 7y ago
  Interestingly Microsoft presented EverParse designed to produce verified parsers for these sorts of data formats at USENIX Security 2019. https://www.usenix.org/conference/usenixsecurity19/presentation/delignat-lavaud https://www.usenix.org/conference/usenixsecurity19/presentat... But it's only for parsing the data. What gets down with it after parsing can still be buggy.
0xff00ffee 7y ago
> just burn all the things and start over Wrap all of this with an "IN MY OPINION"... That would make things worse because we'd make the same mistakes again. I've been on many start over projects (Xeon Phi, for example, threw out the P4 pipeline and went back to the Pentium U/V). It doesn't work. You know what the most robust project I've worked on? The instruction decoder on Intel CPUs. The validation tests go back to the late 1980's! You make progress by building on top and fixing your mistakes because there literally IS NO OTHER WAY. Go read about hemoglobin, its the one of the oldest genes in the genome, used by everything that uses blood to transport oxygen, and it is a GIGANTIC gene, full of redundancies. Essentially a billion years of evolution accreted one of the most robust and useful genes in our body, and there's nothing elegant about it. I think that's where we are headed. Large systems that bulge with heft but contain so many redundant checking code that they become statistically more robust.
- _nedR 7y ago
  Yep : https://www.joelonsoftware.com/2000/04/06/things-you-should-never-do-part-i/ https://www.joelonsoftware.com/2000/04/06/things-you-should-...
  - SeekingMeaning 7y ago
    > April 6, 2000 Wow. That goes waaaaaaay back. It’s crazy to think that 1980 was to him at the time as 2000 is to us _right now_.
    - Moru 7y ago
      This is nothing new. Our parents all saw this already 50 years ago wherever they were working at the time.
  - leeoniya 7y ago
    > That LoadLibrary call is ugly but it makes the code work on old versions of Windows 95. with the proper code comments for the hair (in the code or in the source repo) and regression tests it becomes possible to clean up and even rewrite. floppy disks are no longer a thing and neither is windows 95. RAM & swap space are abundant, so that OOM may never happen any more IRL. the app's whole architecture may have been carefully chosen for the hardware and simplistic compilers of another age. is it okay never to rewrite a webpage where 50% of the codebase is IE6 hacks? if it is code that must be maintained, then at some point the hair may need to be shaved; it simply cannot grow forever as the world moves on around it. the doma of "never rewrite" is silly without further context.
makach 7y ago
Crypto is hard. Choose your libraries carefully, stay updated and for Zimmermann's sake: don't roll your own.

by _hl_ 7y ago

tptacek 7y ago

There's a history of vulnerabilities like these, in some of the most important crypto libraries. For instance: until 2008, NSS, the TLS library used by Firefox, couldn't properly validate RSA signatures from e=3 RSA keys (it wasn't validating the full signature block, but rather parsing it and looking for the embedded hash). For e=3 roots, which were readily available at the time, you could simply build any signature block you wanted and then take its cube root.

Herrera 7y ago
Bleichenbacher'06 never dies.
- CiPHPerCoder 7y ago
  Neither does BB'98
  - baby 7y ago
    Can’t wait for BB20
gonnabezuul 7y ago
Interesting. Were there any similar vulnerabilities in Windows XP's crypto libraries?
- tptacek 7y ago
  There have been crypto vulnerabilities in Windows libraries before, but not the e=3 vulnerability; CryptoAPI parsed RSA signatures back-to-front, and so sidestepped the issue.

munchbunny 7y ago

This stuff often looks simpler and less subtle in hindsight. Modern cryptography has gotten better at taking human (developer) error into account for designing secure API’s, but the fact of the matter is that the math is subtle, and cryptography in general is subtle due to the places where it collides with reality, so burning everything down and starting over is likely to just cause us to rediscover issues we already know about. Say we stop using X509 certificates. We will continue to use signing to cryptographically bind claims, and we will still use PKI-like structures to attest trustworthiness, so we are still vulnerable to the same approaches of attacks even if we don’t use certificates. We have actually learned a few things, such as that cryptographic agility seems to cause more issues than the problems it solves, so the field is improving in important ways, but if it’s not a key matching weakness, it’s going to be some Unicode encoding BS or some other critical but not validated data somewhere else, or... (because this is a real in the wild problem) using phone numbers to generate cryptographic keys for coin wallets.

tptacek 7y ago
This is true, but the bug here is not subtle. It would have been shocking to discover an ECC implementation that let attackers specify curve parameters even 10-15 years ago. When we blogged the e=3 debacle back in '07 or whatever, we linked to a Kaliski presentation from 1999 that called out validating curve parameters. At least with the ACME vulnerability, there was a novel service model involved. Here, we're talking about certificates that allow you to embed what is in effect your own cryptographic algorithm to interpret the certificate under! This is a rare instance where I'm happy to concede that closed source allowed a terrible bug to survive far longer than it would have if nobody needed to break out a copy of Ghidra to read the code that validated elliptic curve signatures.
- john_alan 7y ago
  Very interesting take. Good description of Pornins thoughts. By the way, when you say closed src allowed... do other libs in the opensrc space check the curve Params?
  - 7y ago

loup-vaillant 7y ago

> If we can't even get crypto libraries right Signature verification is one of the hardest things to get right. One reason is, they're harder to test: when you encrypt or hash something, you have a whole bunch of bits you can check against test vectors. With signature verifications, you only have one bit: it's a match, or it's a fail. Moreover, it's very easy to forget to check something (here, that we are using the same base point). Other constructions, like EdDSA, are simpler, and verification requires a single equality check. Harder to botch. And even then, implementers can be tempted to get clever, which requires extra care. I've personally been bitten by not verifying mathematical jargon, and mistakenly thought "birational equivalence" was complicated speak for "bijection". Almost, but not quite. This single oversight lead to a critical, easy to find, easy to exploit vulnerability. We found out 15 months later, 1 full year after public release, by tinkering with the tests. A cryptographer would have found it in 5 minutes, but as far as I can tell, they're all very busy.

baby 7y ago
That’s an interesting assessment. Rogaway just gave a talk at RWC about APIs for secret splitting schemes. IIRC he said that the API needed to be closer to what symmetric crypto was. But from the diagram it seemed like you were obtaining some associated data back to check that the secret was correct (not sure if this would work/is relevant with more recent DKG schemes). A signature verification returning an actual AD would be interesting as well.
- loup-vaillant 7y ago
  EdDSA can have something close. Long story short, an EdDSA signature has two parts, often called "R" and "s". Verification works by producing a number using the public key and "s", then checking that this number is the same as "R". There are basically 3 steps: 1. h_ram <- HASH(R || public_key || message) 2. R_check <- obscure_computation(public_key, s, h_ram) 3. if R_check == R, accept, else reject Steps 1 and 3 are straightforward (the hash and the constant time comparison are almost always implemented in dedicated routines, tested separately). Step 2 is the most dangerous (that's where the elliptic curve magic happens). EdDSA Implementations would be easier to check against one another if they all exposed step 2 as part of the public API. Bonus points if step 2 can handle invalid inputs (low order point, point on the twist...) in a standard manner. I haven't seen such a thing though, probably because end users never need a separate step 2. Still, I can already envision the benefits. I'll probably use it myself.

mleonhard 7y ago

We need one time pads. They're the only really trustworthy crypto.

tptacek 7y ago
By all means: make yourself some one-time pads. Maybe you can convince Google to accept one from you at a dead drop somewhere in Mountain View.
bscphil 7y ago
Hmm. Maybe I'll generate some high quality OTPs for myself with a good CSPRNG. I could use any decent block cipher in counter mode, just need to guard against counter re-use, and then ship my OTPs off to anyone I need to communicate with. Hang on, if I could come up with a way of securely sharing the key I used with my recipient, I wouldn't need to actually mail the OTP to them, since they could generate it themselves. Should probably include a nonce too. Now, if only there were a secure method to share the key...
- Tomte 7y ago
  > Maybe I'll generate some high quality OTPs for myself with a good CSPRNG That's not a one-time pad, it's simply a stream cipher.
  - schoen 7y ago
    That's the joke!
- jancsika 7y ago
  > Now, if only there were a secure method to share the key... ... that doesn't include a critical cryptographic vulnerability. :) To be generous to the now greyed GP, there's probably a way to teach a recipient a short pad and its proper use so that the recipient can later decode a short ciphertext sent over Twitter. Perhaps even performing that feat in their head. None of the cryptography that could fit your quip has that property. And if the recipient does something catastrophic like resend the pad over Twitter to confirm they memorized it correctly, there's at least a chance they may catch their error. Perhaps they may even correct it without the goddamned Department of Defense coming into it. I don't get cryptographers' condescension toward OTP zealots. All they want is a better boat. At least have the decency of the captain from Titanic and apologize while we sink for not having delivered it.

derefr 7y ago

> If we can't even get crypto libraries right (where you'd hope most of the formal verification folks are) Personally, I'd hope most of the formal verification folks are working in firmware for industrial/medical embedded systems, and/or the microcontroller designs that go into those same systems. A lack of encryption (outside of military contexts) doesn't usually directly cause people to die.

jpgoldberg 7y ago
Interestingly Microsoft presented EverParse designed to produce verified parsers for these sorts of data formats at USENIX Security 2019. https://www.usenix.org/conference/usenixsecurity19/presentation/delignat-lavaud https://www.usenix.org/conference/usenixsecurity19/presentat... But it's only for parsing the data. What gets down with it after parsing can still be buggy.

0xff00ffee 7y ago

> just burn all the things and start over Wrap all of this with an "IN MY OPINION"... That would make things worse because we'd make the same mistakes again. I've been on many start over projects (Xeon Phi, for example, threw out the P4 pipeline and went back to the Pentium U/V). It doesn't work. You know what the most robust project I've worked on? The instruction decoder on Intel CPUs. The validation tests go back to the late 1980's! You make progress by building on top and fixing your mistakes because there literally IS NO OTHER WAY. Go read about hemoglobin, its the one of the oldest genes in the genome, used by everything that uses blood to transport oxygen, and it is a GIGANTIC gene, full of redundancies. Essentially a billion years of evolution accreted one of the most robust and useful genes in our body, and there's nothing elegant about it. I think that's where we are headed. Large systems that bulge with heft but contain so many redundant checking code that they become statistically more robust.

_nedR 7y ago
Yep : https://www.joelonsoftware.com/2000/04/06/things-you-should-never-do-part-i/ https://www.joelonsoftware.com/2000/04/06/things-you-should-...
- SeekingMeaning 7y ago
  > April 6, 2000 Wow. That goes waaaaaaay back. It’s crazy to think that 1980 was to him at the time as 2000 is to us _right now_.
  - Moru 7y ago
    This is nothing new. Our parents all saw this already 50 years ago wherever they were working at the time.
- leeoniya 7y ago
  > That LoadLibrary call is ugly but it makes the code work on old versions of Windows 95. with the proper code comments for the hair (in the code or in the source repo) and regression tests it becomes possible to clean up and even rewrite. floppy disks are no longer a thing and neither is windows 95. RAM & swap space are abundant, so that OOM may never happen any more IRL. the app's whole architecture may have been carefully chosen for the hardware and simplistic compilers of another age. is it okay never to rewrite a webpage where 50% of the codebase is IE6 hacks? if it is code that must be maintained, then at some point the hair may need to be shaved; it simply cannot grow forever as the world moves on around it. the doma of "never rewrite" is silly without further context.

makach 7y ago

Crypto is hard. Choose your libraries carefully, stay updated and for Zimmermann's sake: don't roll your own.