6 ms·

My understanding is that it wasn't that the primes were bad but that they were hard coded, never changed, and the bit size was small enough to make attacks base

by api 6y ago

My understanding is that it wasn't that the primes were bad but that they were hard coded, never changed, and the bit size was small enough to make attacks based on that practical. I'm on the fence about speck. It's so simple that there isn't much room in there for a back door, meaning that if there is one it implies that the NSA knows something we don't about ARX ciphers. If the NSA knows something we dont about ARX, then could they also know something about ChaCha?

Taek 6y ago
All you need to know is one unique property to slip in a backdoor that nobody else may suspect for a long time. The NSA has given us good reason to question everything they release.
- jas- 6y ago
  Have you considered the adversary and their tactics?
cryptonector 6y ago
Rotating DH groups periodically is difficult. SSHv2, for example, has support for this. It takes a lot of computation to generate new groups, but then how do the client and server agree on a group? Well, the server tells the client, and the client has to like it -- i.e., the client has to trust the server's group. This isn't better than just having a bigger nothing-up-my-sleeves group to begin with. That, ultimately, has been the solution the community landed at: nothing-up-my-sleeve curves for ECDH and EdDSA. The nothing-up-my-sleeve part is all about setting / agreeing to obvious and hard guidelines for generating and selecting curves before doing the selection, then you can see that a curve was generated and selected without any hidden agendas. We have several of these now that are generally thought to be secure, though, of course, it's hard to say for sure. It's a pretty good outcome.
- ustolemyname 6y ago
  If the client doesn't trust the server, the crypto protocol is a little irrelevant. I otherwise agree that we (ostensibly) are in a better place now with pre-defined curves.
  - dcow 6y ago
    > If the client doesn't trust the server, the crypto protocol is a little irrelevant. What? No. The protocol is the only thing that is relevant. Peers don't generally trust each other a priori at all. They trust the protocol. If they can authenticate each other within the bounds of the protocol then they trust each other. If one party no has reason to distrust a certain protocol, then it should not be used as a basis for establishing trust. If the two peers can't agree on a protocol: stalemate. If I compromise your server and only serve weak protocols a responsible client won't authenticate me whereas a vulnerable client would take my word that my protocol is secure.
    - kortilla 6y ago
      We’re talking about rotation though, something that can be triggered when both sides are authed.
      - deleted 6y ago
        [deleted]
    - PeterisP 6y ago
      If don't trust a server, then any strong protocol that results in a secure shared secret or session key is trivially sidestepped by the server intentionally leaking these secrets or keys.
      - ben_w 6y ago
        Two interpretations of the same phrase: 1. Do you trust that 123.123.123.123 is the real https://example.com https://example.com ? 2. Do you trust the real https://example.com https://example.com to not leak? The protocol is for 1. You’re right that nothing can help with 2.
- john_alan 6y ago
  Ephemeral ECDH over 25519 solves all of these issues. How is it not standard.
  - cryptonector 6y ago
    Did I say it doesn't? Read carefully.
    - john_alan 6y ago
      Lol
  - zahllos 6y ago
    It is a standard. RFC 7748. It is also a part of TLS 1.3.
- zahllos 6y ago
  Rotating the group was never the point or the problem. The problem was that typically Linux distributions shipped a 1024-bit hard coded DH parameters file and most people didn't bother to change it. Groups with low security remain the default for things like IPsec configurations in firewalls and so on, even now. It's perfectly fine to keep a fixed DH parameter choice. In some senses that's exactly what using ed25519 is. The point is that the strength of the group that results is sufficient to mean that even the NSA with their budget can't break it, even targeting that one curve. It's just that elliptic curves are much more efficient than picking a single 2048-bit or 4096-bit DH group, so why bother with that when we can pick a 256-bit EC group instead? The nothing up my sleeve part isn't particularly relevant to this. The choice of elliptic curve is quite involved so it doesn't make sense to simply spit out a random field and random curve coefficients. Moreover given the server communicates a prime and a generator for the DH group, the client is quite free to do some primality testing and reject the DH group if it wanted to. Also, there's a nice body of work showing NUMS can be manipulated. You might be interested in https://bada55.cr.yp.to/ https://bada55.cr.yp.to/ I think you're muddling the concepts a bit here. Nothing up my sleeve isn't the main and only argument that justifies the move to ed25519; the original group wasn't backdoored in the first place. Just potentially within range of the NSA.
praptak 6y ago
For every X NSA might know something that we don't about X. That does not mean the probability is the same. Whatever X they develop and push has much greater probability than other X-es.
- Godel_unicode 6y ago
  That's absolutely not true, there are tons of deeply flawed crypto systems that have been developed without any input from NSA. If you are not an expert you are virtually guaranteed to create such a flawed system. Conversely NSA has pushed AES very hard, to the point that there are "suite B" implementations approved for safeguarding classified information. Nobody has found a backdoor in any of those.
HeadsUpHigh 6y ago
It's subtle but basically NSA supported primes but they didn't say anything about hard coded primes. They knew that if we primarily used primes we would probably use hard-coded ones for the majority of the traffic so they could decrypt them. But of course they never said that directly. They just pushed towards that direction.
- dependenttypes 6y ago
  I thought that the issue about primes was concerning the elliptic curves rather than the DH groups.
zahllos 6y ago
Your understanding is correct. Before these leaks and when DH was widespread you could generate your own dhparams file for DH connections, both for sshd and for TLS connections. It was advised to do so in corners that understood what that meant. It's just that many people didn't bother, so the NSA took advantage. The parent comment to yours gets a bit excitable about ed25519 being a prime-rejecting miracle cure. Indeed 2^255-19... is prime. Elliptic curve cryptography still relies on large prime order subgroups for its security and that's not going away until and if quantum computers get good enough to break it. The main advantage of ed25519 is that it is fairly hard to implement badly. No k=3 randomness issues as with ECDSA (you can also use deterministic ECDSA to get this property). Constant time curve constructions. Etc etc. The same team who designed SIMON and SPECK designed SHA2 so, worth thinking about that. My personal opinion is that there's nothing wrong with SIMON and SPECK. However there's also not a lot wrong with AES and so little reason to downgrade to something else in almost all use cases. The reason Germany and Israel kicked them out of ISO was likely entirely politically motivated. I mean if I were them and I'd maybe been stung by some of the Snowden leaks e.g. using weaker crypto, or had lost trust in the NSA, I'd probably do the same. The argument for lightweight crypto is not at all clear. I've heard of people implementing AES in less than 1000 gate equivalents, with the target GE in the NIST lightweight competition being 2000. There is somewhat more justification for lightweight hashing because of say the large internal state size of Keccak not being particularly embedded friendly. But we're talking about super constrained devices here. RFID tags or encrypted flash storage to go with a cortex-m. It's entirely justified to remove SIMON/SPECK from the Linux kernel. To run vanilla Linux you need an MMU, and the cortex-m series of processors that power most embedded stuff don't have one. Even then, they're actually powerful enough to do full TLS anyway if coded properly (bearssl for example).
- tialaramex 6y ago
  The reason you'd want a super-constrained cheap AXR in Linux isn't because Linux runs on the tiny devices but because Linux talks to the tiny devices. But the politics meant it doesn't matter in the end. People convinced themselves the NSA backdoored XOR or that the number five is secretly composite or whatever and you can't use logic to fix something like that.

by api 6y ago

Taek 6y ago

All you need to know is one unique property to slip in a backdoor that nobody else may suspect for a long time. The NSA has given us good reason to question everything they release.

jas- 6y ago
Have you considered the adversary and their tactics?

cryptonector 6y ago

Rotating DH groups periodically is difficult. SSHv2, for example, has support for this. It takes a lot of computation to generate new groups, but then how do the client and server agree on a group? Well, the server tells the client, and the client has to like it -- i.e., the client has to trust the server's group. This isn't better than just having a bigger nothing-up-my-sleeves group to begin with. That, ultimately, has been the solution the community landed at: nothing-up-my-sleeve curves for ECDH and EdDSA. The nothing-up-my-sleeve part is all about setting / agreeing to obvious and hard guidelines for generating and selecting curves before doing the selection, then you can see that a curve was generated and selected without any hidden agendas. We have several of these now that are generally thought to be secure, though, of course, it's hard to say for sure. It's a pretty good outcome.

ustolemyname 6y ago
If the client doesn't trust the server, the crypto protocol is a little irrelevant. I otherwise agree that we (ostensibly) are in a better place now with pre-defined curves.
- dcow 6y ago
  > If the client doesn't trust the server, the crypto protocol is a little irrelevant. What? No. The protocol is the only thing that is relevant. Peers don't generally trust each other a priori at all. They trust the protocol. If they can authenticate each other within the bounds of the protocol then they trust each other. If one party no has reason to distrust a certain protocol, then it should not be used as a basis for establishing trust. If the two peers can't agree on a protocol: stalemate. If I compromise your server and only serve weak protocols a responsible client won't authenticate me whereas a vulnerable client would take my word that my protocol is secure.
  - kortilla 6y ago
    We’re talking about rotation though, something that can be triggered when both sides are authed.
    - deleted 6y ago
      [deleted]
  - PeterisP 6y ago
    If don't trust a server, then any strong protocol that results in a secure shared secret or session key is trivially sidestepped by the server intentionally leaking these secrets or keys.
    - ben_w 6y ago
      Two interpretations of the same phrase: 1. Do you trust that 123.123.123.123 is the real https://example.com https://example.com ? 2. Do you trust the real https://example.com https://example.com to not leak? The protocol is for 1. You’re right that nothing can help with 2.
john_alan 6y ago
Ephemeral ECDH over 25519 solves all of these issues. How is it not standard.
- cryptonector 6y ago
  Did I say it doesn't? Read carefully.
  - john_alan 6y ago
    Lol
- zahllos 6y ago
  It is a standard. RFC 7748. It is also a part of TLS 1.3.
zahllos 6y ago
Rotating the group was never the point or the problem. The problem was that typically Linux distributions shipped a 1024-bit hard coded DH parameters file and most people didn't bother to change it. Groups with low security remain the default for things like IPsec configurations in firewalls and so on, even now. It's perfectly fine to keep a fixed DH parameter choice. In some senses that's exactly what using ed25519 is. The point is that the strength of the group that results is sufficient to mean that even the NSA with their budget can't break it, even targeting that one curve. It's just that elliptic curves are much more efficient than picking a single 2048-bit or 4096-bit DH group, so why bother with that when we can pick a 256-bit EC group instead? The nothing up my sleeve part isn't particularly relevant to this. The choice of elliptic curve is quite involved so it doesn't make sense to simply spit out a random field and random curve coefficients. Moreover given the server communicates a prime and a generator for the DH group, the client is quite free to do some primality testing and reject the DH group if it wanted to. Also, there's a nice body of work showing NUMS can be manipulated. You might be interested in https://bada55.cr.yp.to/ https://bada55.cr.yp.to/ I think you're muddling the concepts a bit here. Nothing up my sleeve isn't the main and only argument that justifies the move to ed25519; the original group wasn't backdoored in the first place. Just potentially within range of the NSA.

praptak 6y ago

For every X NSA might know something that we don't about X. That does not mean the probability is the same. Whatever X they develop and push has much greater probability than other X-es.

Godel_unicode 6y ago
That's absolutely not true, there are tons of deeply flawed crypto systems that have been developed without any input from NSA. If you are not an expert you are virtually guaranteed to create such a flawed system. Conversely NSA has pushed AES very hard, to the point that there are "suite B" implementations approved for safeguarding classified information. Nobody has found a backdoor in any of those.

HeadsUpHigh 6y ago

It's subtle but basically NSA supported primes but they didn't say anything about hard coded primes. They knew that if we primarily used primes we would probably use hard-coded ones for the majority of the traffic so they could decrypt them. But of course they never said that directly. They just pushed towards that direction.

dependenttypes 6y ago
I thought that the issue about primes was concerning the elliptic curves rather than the DH groups.

zahllos 6y ago

Your understanding is correct. Before these leaks and when DH was widespread you could generate your own dhparams file for DH connections, both for sshd and for TLS connections. It was advised to do so in corners that understood what that meant. It's just that many people didn't bother, so the NSA took advantage. The parent comment to yours gets a bit excitable about ed25519 being a prime-rejecting miracle cure. Indeed 2^255-19... is prime. Elliptic curve cryptography still relies on large prime order subgroups for its security and that's not going away until and if quantum computers get good enough to break it. The main advantage of ed25519 is that it is fairly hard to implement badly. No k=3 randomness issues as with ECDSA (you can also use deterministic ECDSA to get this property). Constant time curve constructions. Etc etc. The same team who designed SIMON and SPECK designed SHA2 so, worth thinking about that. My personal opinion is that there's nothing wrong with SIMON and SPECK. However there's also not a lot wrong with AES and so little reason to downgrade to something else in almost all use cases. The reason Germany and Israel kicked them out of ISO was likely entirely politically motivated. I mean if I were them and I'd maybe been stung by some of the Snowden leaks e.g. using weaker crypto, or had lost trust in the NSA, I'd probably do the same. The argument for lightweight crypto is not at all clear. I've heard of people implementing AES in less than 1000 gate equivalents, with the target GE in the NIST lightweight competition being 2000. There is somewhat more justification for lightweight hashing because of say the large internal state size of Keccak not being particularly embedded friendly. But we're talking about super constrained devices here. RFID tags or encrypted flash storage to go with a cortex-m. It's entirely justified to remove SIMON/SPECK from the Linux kernel. To run vanilla Linux you need an MMU, and the cortex-m series of processors that power most embedded stuff don't have one. Even then, they're actually powerful enough to do full TLS anyway if coded properly (bearssl for example).

tialaramex 6y ago
The reason you'd want a super-constrained cheap AXR in Linux isn't because Linux runs on the tiny devices but because Linux talks to the tiny devices. But the politics meant it doesn't matter in the end. People convinced themselves the NSA backdoored XOR or that the number five is secretly composite or whatever and you can't use logic to fix something like that.