7 ms·

Double encryption: Analyzing the NSA/GCHQ arguments against hybrids

171 points by weinzierl 3y ago

halJordan 3y ago
Idk you lost me when you said using two schemes is not more complex than using one scheme. That doing two things at once is more complex than doing one is just not an axiom I'm willing to give up. And if you're willing to then i have to guess it's for ideological reasons than rational or logical ones. So at that point we're not analyzing the opinions of an expert organization we're just blasting cynicism at the "bad guy."
- squigz 3y ago
  I don't believe the claim was that it adds no complexity, but was saying it adds no complexity due to the reasons mentioned. He then goes on to write a paragraph about why that is the case, which you could of course respond to.
  - lifthrasiir 3y ago
    To add more, we are talking about a hybrid scheme that uses both a post-quantum algorithm and a classical algorithm, where the former is much slower than the later and a mere hybrid doesn't make much difference in performance. And this scheme will be presented as a single choice in cryptographic protocols, so if the protocol already supports multiple cryptosystems it should be just fine to adopt. DJB also explains needs for hybrids as follows: we don't yet have any post-quantum algorithm that we can confidently use as a direct substitute for well-established classical algorithms. So for now we need to consider possibilities for QC becoming real and PQ algorithms broken, hence hybrids.
- hannob 3y ago
  This sentence also bothered me, however, later in the text he says that of course there's a complexity cost, but that he believes the costs are quite low. I think one can reasonably argue that. One sentence with unfortunately chosen words shouldn't invalidate the - in my view largely reasonable - arguments of the whole text.
- _notreallyme_ 3y ago
  You might have read that wrong. The article acknowledges the added complexity: > "hybrid solutions make implementations even more complex". > If the words are taken purely at face value then they're clearly correct The argument here is that the complexity is mostly due to the adding of new algorithm, not the hybridization. It goes on to argue that the added complexity due to the hybridization itself is negligible, especially considering the level of security provided.
- adrian_b 3y ago
  Doing 2 things is more complex than 1, but doing 1 new and much more complex thing in addition to 1 old much simpler and already verified thing has very little complexity over omitting the old thing and doing just the new one. In both cases the work is in adding and testing the new thing. Whether you comment out or not the old thing does not really change the amount of programmer work and the execution time and required resources are also not affected significantly in this case.
contingencies 3y ago
<non-cryptanalyst blather>It seems to me that in all but the most resource constrained systems any novel implementation of hashing for source file validation should be multi-algorithm by default, since typical processing overheads are minimal and IO is already paid for. (IO could/should be pseudorandom and non-linear, FWIW). Encryption however can be more complex and expensive and there could potentially be more risk of recombinant side channels.</non-cryptanalyst blather>
- Vecr 3y ago
  Unless you have a weak hash function anyway you probably don't need to double it up (unless it's a weird non-standard construction like what Bitcoin does, there it's absolutely needed). Just use truncated blake2bp or something like that.
- hoytech 3y ago
  This is not necessarily as secure as you might expect. See Joux's "Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions" https://link.springer.com/content/pdf/10.1007/978-3-540-28628-8_19.pdf https://link.springer.com/content/pdf/10.1007/978-3-540-2862...
  - dfox 3y ago
    The paper refers to the case where you build a even more secure hash function by concatenating output of multiple presumably secure hash functions. The resulting construction will still be as secure as the strongest component hash function used, which is what you want for the case of long term archival hashes/signatures (the obvious question is exactly what asymetric construction you are going to use to sign the resulting hash which preserves this property). Of note is that when you look at the multiple parallel executions of an iterated hash function at the level of whatever round structure that it is inside its compression function it becomes quite obvious that the result will not have the security level of 2^(m+n+...) as one would expect from the output length, but somewhere around 2^m+2^n (=2^m if m>n) as there is absolutely no mixing of state between the parallel executions.
RcouF1uZ4gsC 3y ago
I think there is a possibility that the NSA doesn't know much more about ECC than the open crypto community. However, I think there is a decent chance that the NSA does know more about post-quantum cryptography than the open crypto community. If post-quantum algorithms are used alone, everyone is playing into the NSA's strengths and gives them the ability to break encryption, that they would not have today with ECC. Given that we are still some ways off from quantum computers that can actually break ECC, we would be trading security now for insecurity now.
- Eisenstein 3y ago
  > Given that we are still some ways off from quantum computers that can actually break ECC, we would be trading security now for insecurity now. What makes you think that practical quantum computers are a certainty? Everything I have read makes it seem more like a 'we can't not try to figure it out, because it might work' rather than a 'we are on the way to doing it, it just needs more time'.
  - hdhfjkrkrme 3y ago
    You can use this argument against anything not done yet: "we've been trying to build fusion reactors for 50 years now, we should give up now"
    - deleted 3y ago
      [deleted]
    - Eisenstein 3y ago
      Except that isn't the argument I am making.
      - hdhfjkrkrme 3y ago
        We have small quantum computers, we don't have big ones. We have fusion power on small scale, we don't have it on commercial scale. Seems to be the same argument.
fuklief 3y ago
I didn't know US/UK gov were against hybrids. AFAIU, the French and Germans are recommending hybrids as a first step before stand alone PQC [0]. [0]: https://cyber.gouv.fr/en/publications/follow-position-paper-post-quantum-cryptography https://cyber.gouv.fr/en/publications/follow-position-paper-...
- Scarjit 3y ago
  From the German BSI-TR-02102-1 ([0],[1]) guidelines "Combination of Classical and PQC Security: The secure implementation of PQC mechanisms, especially with regard to side-channel security, avoidance of implementation errors and secure implementation in hardware, and also their classical cryptanalysis are significantly less well studied than for RSA- and ECC-based cryptographic mechanisms. In addition, there are currently no standardised versions of these mechanisms. Their use in productive systems is currently only recommended together with a classic ECC- or RSA-based key exchange or key transport. In this case, one speaks of a so-called hybrid mechanism. Parallel to a PQC key transport, an ECC-based key exchange using Brainpool or NIST curves with at least 256 bits key length should be performed. The two shared secrets generated in this way should be combined with the mechanism given in Section B.1.1 of this Technical Guideline. Here, the standard [96] in its current version explicitly provides the possibility to combine several partial secrets. A hybrid approach, as proposed here, is further described for example in [5] as the most feasible alternative for a use of PQC mechanisms in the near future. Provided that the restrictions of the stateful mechanisms XMSS and LMS recommended in this TechnicalGuideline are carefully considered, these hash-based signatures can in principle also be used alone (i.e., not hybrid), see Chapter 6" [0]: English version: https://www.bsi.bund.de/SharedDocs/Downloads/EN/BSI/Publications/TechGuidelines/TG02102/BSI-TR-02102-1.pdf?__blob=publicationFile&v=6 https://www.bsi.bund.de/SharedDocs/Downloads/EN/BSI/Publicat... [1]: German version: https://www.bsi.bund.de/SharedDocs/Downloads/DE/BSI/Publikationen/TechnischeRichtlinien/TR02102/BSI-TR-02102.pdf?__blob=publicationFile&v=9 https://www.bsi.bund.de/SharedDocs/Downloads/DE/BSI/Publikat...
JoachimS 3y ago
If I'm not missing anything, DJB does not consider constrained devices, where the code size and execution time with two algorithms may be a problem. Unfortunately these types of devices are also the types that may have very long lifetimes. But for all other devices - server, desktop, mobile phones etc which sports 64-bit CPUs clocked in GHz speeds, and GByte of storage, RAM this is seems sensible. Performing x25519 on these devices in addition to the PQC-algoritm should be a negligible cost.
- adrian_b 3y ago
  Constrained devices should rather stick to the existing key exchange methods, until more certainty exists about the threat of quantum computers. The current methods have much lower overhead than any of the post-quantum methods. Constrained devices that must be quantum-resistant while not affording the cost of hybrid algorithms, which are only slightly less expensive than pure post-quantum algorithms, should better use key-exchange methods based on pre-shared authentication keys, which have much lower overhead than the public-key methods. They could still use hybrid key exchange methods, but very infrequently, only for updating the pre-shared authentication keys, in which case the slowness of the hybrid key exchange method would not matter.
  - JoachimS 3y ago
    The problem is that constrained devices with planned lifetimes of 20-30 years being specified today already are getting requests for inclusion, usage of PQC as well as classical algorithms. Pre-shared only works for deployments with low-ish number of devices. We are talking about 1000+ devices.
    - adrian_b 3y ago
      That is why I have said that if updating the pre-shared authentication keys through separate communication channels is impractical, they can be updated through hybrid public-key based key exchange methods. If a hybrid key exchange method is used e.g. only after one thousand or even after one hundred of connections made with pre-shared keys, then the hybrid method can be very slow without significant impact. This is the same like reusing in TLS 1.3 a previously computed shared secret for a new connection, just using this for a large enough number of successive connections so that the slowness of the constrained device does not matter.
JacobiX 3y ago
I believe there is maybe a little contradiction with the NSA's own 'Rule of Two,' as outlined in their Commercial Solutions for Classified Program (CSfC). It specifies two completely independent layers of cryptography to protect data :)
- api 3y ago
  Good catch. If one is PQ and one is not, that accomplishes the same thing as a hybrid.
mplewis9z 3y ago
Putting on my tinfoil hat, I think there’s also an argument to be made that the NSA might want to slow down adoption of post-quantum algorithms, which their stance against hybrids definitely accomplishes. If there’s a single organization that could be 10-20 years ahead of where people think they are on something like a useful quantum computer, it’s the NSA (powered by the US’s absurd defense budget). If they can slow down the adoption of post-quantum algorithms, they can maintain their potential head start for longer and be able to break current cryptosystems and extract actually valuable information. Outside of the NSA (and its affiliates), most of the cryptographic community seems to have come together in support of hybrids, which would greatly accelerate the adoption of some level of post-quantum defense. With even the most “liberal” cryptographers thinking that more careful cryptanalysis of post-quantum algorithms is needed before widespread adoption as the sole line of cryptographic defense, if the NSA manages to convince sufficient people that hybrids aren’t viable enough for production (and thus stick with classical algorithms) they may be able to maintain the ability to break sensitive communications for longer when and if their quantum computer efforts have a breakthrough.
- Gustomaximus 3y ago
  Or could it be a bluff. Act like they don't want it, so some players feel they can use more advanced post-quantum algorithms and be secure, while NSA is decrypting it.
  - mplewis9z 3y ago
    Maybe, but this argument holds less weight given that they’re the ones pushing for inclusion of these algorithms in the NIST standards, and are really only advocating against the hybrid algorithms. I honestly think the NSA learned their lesson with the whole debacle around Dual_EC_DRBG and skepticism about their elliptic curve seeds - especially given the continued exponential growth in sensitive electronic communications and records, they want the algorithms as secure as possible without a backdoor that could leak and be a foot-gun for US communications as well. Instead, they’ll just throw more money at making a usable quantum computer than the next country spends on their entire cryptographic infrastructure, and get targeted backdoors into software/hardware implementations of the encryption algorithms so they can focus their attacks more precisely.
deleted 3y ago
[deleted]
bbqbbqbbq 3y ago
[dead]
vinay_ys 3y ago
Thoroughly enjoyed reading DJB's writing. That style of arguing is so effective and yet so easily understandable by anyone having even basic understanding of cryptography. I hope there are students of his who are as good as him (or even better) and continue this kind of work for decades to come.
- hdevalence 3y ago
  I can’t recommend that anyone would be Dan’s student.
  - trillic 3y ago
    Why’s that? I had him back in undergrad and he was a spectacular lecturer. Course wasn’t too rigorous but definitely inspired a further interest in security.
    - tptacek 3y ago
      The person you're responding to, themselves a cryptography engineer, was, famously, one of his students.
    - count 3y ago
      https://medium.com/@hdevalence/when-hell-kept-on-payroll-somewhere-is-where-you-are-f419d3022d0 https://medium.com/@hdevalence/when-hell-kept-on-payroll-som... He's written about it here.
- warner25 3y ago
  It looks like he doesn't have many students. His current title appears to be "Research Professor" and he's the sole author of every "new paper" mentioned in this blog post and most of the recent papers listed on this page: https://cr.yp.to/papers.html https://cr.yp.to/papers.html I'm really curious about this now. How does he write something like half a dozen different papers per year as a sole author? These aren't short papers either; they're dozens of pages. Usually when I see a professor with an incredibly prolific publication history, it's because they have a bunch of PhD students (each working on a paper per year) and they collaborate with a bunch of other professors. He also seems to be quite a character; unafraid to publicly document battles with his employer, IEEE, and the US government.
Retr0id 3y ago
> Any reasonable risk assessment will conclude that the probability of an exploitable arithmetic bug or timing leak or randomness-usage mistake in the UltraKEM software is higher than the probability of such a exploit in the X25519 software. It seems strange to pit a specific classical algorithm against a general-case PQ algorithm made up for the sake of argument, it feels like a bit of a straw man. I've written hobbyist-grade implementations of both X25519 and ML-KEM-768 (aka Kyber). All other things being equal, I think arithmetic bugs in X25519 are more likely, given that it uses 255-bit integer arithmetic, requiring a custom bigint implementation if you want peak performance. Doing 255-bit arithmetic that is both fast, and provably does not contain limb overflow edge-cases (to name just one possible bug class), is hard. At the very least, it's not something I'd trust myself to be able to do. On the other hand, Kyber arithmetic all fits within standard register sizes, without needing to split things up. This doesn't make it immune from arithmetic-related issues (as KyberSlash demonstrates), but it's probably easier to get right overall. I agree that for the time being, the average X25519 impl will be significantly more trustworthy than the average Kyber implementation (or any other PQ construction), due to its maturity, but it seems dishonest to imply that PQ algorithms are inherently harder to get right. Despite this, I am broadly in favour of Hybrid schemes. It seems like the anti-hybrid stance is mostly coming from large slow-moving orgs - sucks to suck, but don't let your unagility hold the rest of us back!
- Beldin 3y ago
  > I agree that for the time being, the average X25519 impl will be significantly more trustworthy than the average Kyber implementation (or any other PQ construction), due to its maturity, but it seems dishonest to imply that PQ algorithms are inherently harder to get right. I understood TFA's point to be exactly this. That is, security designs that have existed significantly longer and were in active, widespread use will have been analysed far better than the new kids on the block.
tptacek 3y ago
No serious organization is going to deploy pure, non-hybrid PQC, as Bernstein tacitly acknowledges when he lists essentially all the major deployments of PQC in production to date, all of which are hybrids.
- Retr0id 3y ago
  Isn't that kinda the whole point? If deploying non-hybrid schemes is needlessly risky (I agree), then why should NIST et al certify those deployments?
- rainworld 3y ago
  [flagged]
heads 3y ago
I’m very naive about the upcoming quantum cryptography switchover. Can anyone here recommend a good podcast to learn about it more?
- dave1010uk 3y ago
  Not a podcast but if it helps, I wrote an overview article that goes from the basics of cryptography (eg RSA) and quantum computers (eg qubits), explaining how a post quantum cryptographic algorithm works (Kyber) and briefly touches on current hybrid implementations: https://medium.com/@dave1010/post-quantum-cryptography-its-already-here-and-it-s-not-as-scary-as-it-sounds-cb8ea70e8f1c https://medium.com/@dave1010/post-quantum-cryptography-its-a...
atoav 3y ago
Not to suggest anything, but imagine you are a secret service in a world in which the cat (knowledge about safe cryptograophic procedures) is out of the bag. Wouldn't a great strategy be to invent some sort of story why that old reliable crypto is now potentially unsafe, so you propose a new standard, that may or may not have a known weakness. And then some paranoid freaks come along that just use both.. Jikes. This is of course just me thinking loud here and pure speculation. We will probably never know for sure.
- thelittleone 3y ago
  Like the Dual_EC_DRBG issue involving the NSA?

171 points by weinzierl 3y ago

Idk you lost me when you said using two schemes is not more complex than using one scheme. That doing two things at once is more complex than doing one is just not an axiom I'm willing to give up. And if you're willing to then i have to guess it's for ideological reasons than rational or logical ones. So at that point we're not analyzing the opinions of an expert organization we're just blasting cynicism at the "bad guy."

squigz 3y ago
I don't believe the claim was that it adds no complexity, but was saying it adds no complexity due to the reasons mentioned. He then goes on to write a paragraph about why that is the case, which you could of course respond to.
- lifthrasiir 3y ago
  To add more, we are talking about a hybrid scheme that uses both a post-quantum algorithm and a classical algorithm, where the former is much slower than the later and a mere hybrid doesn't make much difference in performance. And this scheme will be presented as a single choice in cryptographic protocols, so if the protocol already supports multiple cryptosystems it should be just fine to adopt. DJB also explains needs for hybrids as follows: we don't yet have any post-quantum algorithm that we can confidently use as a direct substitute for well-established classical algorithms. So for now we need to consider possibilities for QC becoming real and PQ algorithms broken, hence hybrids.
hannob 3y ago
This sentence also bothered me, however, later in the text he says that of course there's a complexity cost, but that he believes the costs are quite low. I think one can reasonably argue that. One sentence with unfortunately chosen words shouldn't invalidate the - in my view largely reasonable - arguments of the whole text.
_notreallyme_ 3y ago
You might have read that wrong. The article acknowledges the added complexity: > "hybrid solutions make implementations even more complex". > If the words are taken purely at face value then they're clearly correct The argument here is that the complexity is mostly due to the adding of new algorithm, not the hybridization. It goes on to argue that the added complexity due to the hybridization itself is negligible, especially considering the level of security provided.
adrian_b 3y ago
Doing 2 things is more complex than 1, but doing 1 new and much more complex thing in addition to 1 old much simpler and already verified thing has very little complexity over omitting the old thing and doing just the new one. In both cases the work is in adding and testing the new thing. Whether you comment out or not the old thing does not really change the amount of programmer work and the execution time and required resources are also not affected significantly in this case.

contingencies 3y ago

<non-cryptanalyst blather>It seems to me that in all but the most resource constrained systems any novel implementation of hashing for source file validation should be multi-algorithm by default, since typical processing overheads are minimal and IO is already paid for. (IO could/should be pseudorandom and non-linear, FWIW). Encryption however can be more complex and expensive and there could potentially be more risk of recombinant side channels.</non-cryptanalyst blather>

Vecr 3y ago
Unless you have a weak hash function anyway you probably don't need to double it up (unless it's a weird non-standard construction like what Bitcoin does, there it's absolutely needed). Just use truncated blake2bp or something like that.
hoytech 3y ago
This is not necessarily as secure as you might expect. See Joux's "Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions" https://link.springer.com/content/pdf/10.1007/978-3-540-28628-8_19.pdf https://link.springer.com/content/pdf/10.1007/978-3-540-2862...
- dfox 3y ago
  The paper refers to the case where you build a even more secure hash function by concatenating output of multiple presumably secure hash functions. The resulting construction will still be as secure as the strongest component hash function used, which is what you want for the case of long term archival hashes/signatures (the obvious question is exactly what asymetric construction you are going to use to sign the resulting hash which preserves this property). Of note is that when you look at the multiple parallel executions of an iterated hash function at the level of whatever round structure that it is inside its compression function it becomes quite obvious that the result will not have the security level of 2^(m+n+...) as one would expect from the output length, but somewhere around 2^m+2^n (=2^m if m>n) as there is absolutely no mixing of state between the parallel executions.

RcouF1uZ4gsC 3y ago

I think there is a possibility that the NSA doesn't know much more about ECC than the open crypto community. However, I think there is a decent chance that the NSA does know more about post-quantum cryptography than the open crypto community. If post-quantum algorithms are used alone, everyone is playing into the NSA's strengths and gives them the ability to break encryption, that they would not have today with ECC. Given that we are still some ways off from quantum computers that can actually break ECC, we would be trading security now for insecurity now.

Eisenstein 3y ago
> Given that we are still some ways off from quantum computers that can actually break ECC, we would be trading security now for insecurity now. What makes you think that practical quantum computers are a certainty? Everything I have read makes it seem more like a 'we can't not try to figure it out, because it might work' rather than a 'we are on the way to doing it, it just needs more time'.
- hdhfjkrkrme 3y ago
  You can use this argument against anything not done yet: "we've been trying to build fusion reactors for 50 years now, we should give up now"
  - deleted 3y ago
    [deleted]
  - Eisenstein 3y ago
    Except that isn't the argument I am making.
    - hdhfjkrkrme 3y ago
      We have small quantum computers, we don't have big ones. We have fusion power on small scale, we don't have it on commercial scale. Seems to be the same argument.

fuklief 3y ago

I didn't know US/UK gov were against hybrids. AFAIU, the French and Germans are recommending hybrids as a first step before stand alone PQC [0]. [0]: https://cyber.gouv.fr/en/publications/follow-position-paper-post-quantum-cryptography https://cyber.gouv.fr/en/publications/follow-position-paper-...

Scarjit 3y ago
From the German BSI-TR-02102-1 ([0],[1]) guidelines "Combination of Classical and PQC Security: The secure implementation of PQC mechanisms, especially with regard to side-channel security, avoidance of implementation errors and secure implementation in hardware, and also their classical cryptanalysis are significantly less well studied than for RSA- and ECC-based cryptographic mechanisms. In addition, there are currently no standardised versions of these mechanisms. Their use in productive systems is currently only recommended together with a classic ECC- or RSA-based key exchange or key transport. In this case, one speaks of a so-called hybrid mechanism. Parallel to a PQC key transport, an ECC-based key exchange using Brainpool or NIST curves with at least 256 bits key length should be performed. The two shared secrets generated in this way should be combined with the mechanism given in Section B.1.1 of this Technical Guideline. Here, the standard [96] in its current version explicitly provides the possibility to combine several partial secrets. A hybrid approach, as proposed here, is further described for example in [5] as the most feasible alternative for a use of PQC mechanisms in the near future. Provided that the restrictions of the stateful mechanisms XMSS and LMS recommended in this TechnicalGuideline are carefully considered, these hash-based signatures can in principle also be used alone (i.e., not hybrid), see Chapter 6" [0]: English version: https://www.bsi.bund.de/SharedDocs/Downloads/EN/BSI/Publications/TechGuidelines/TG02102/BSI-TR-02102-1.pdf?__blob=publicationFile&v=6 https://www.bsi.bund.de/SharedDocs/Downloads/EN/BSI/Publicat... [1]: German version: https://www.bsi.bund.de/SharedDocs/Downloads/DE/BSI/Publikationen/TechnischeRichtlinien/TR02102/BSI-TR-02102.pdf?__blob=publicationFile&v=9 https://www.bsi.bund.de/SharedDocs/Downloads/DE/BSI/Publikat...

JoachimS 3y ago

If I'm not missing anything, DJB does not consider constrained devices, where the code size and execution time with two algorithms may be a problem. Unfortunately these types of devices are also the types that may have very long lifetimes. But for all other devices - server, desktop, mobile phones etc which sports 64-bit CPUs clocked in GHz speeds, and GByte of storage, RAM this is seems sensible. Performing x25519 on these devices in addition to the PQC-algoritm should be a negligible cost.

adrian_b 3y ago
Constrained devices should rather stick to the existing key exchange methods, until more certainty exists about the threat of quantum computers. The current methods have much lower overhead than any of the post-quantum methods. Constrained devices that must be quantum-resistant while not affording the cost of hybrid algorithms, which are only slightly less expensive than pure post-quantum algorithms, should better use key-exchange methods based on pre-shared authentication keys, which have much lower overhead than the public-key methods. They could still use hybrid key exchange methods, but very infrequently, only for updating the pre-shared authentication keys, in which case the slowness of the hybrid key exchange method would not matter.
- JoachimS 3y ago
  The problem is that constrained devices with planned lifetimes of 20-30 years being specified today already are getting requests for inclusion, usage of PQC as well as classical algorithms. Pre-shared only works for deployments with low-ish number of devices. We are talking about 1000+ devices.
  - adrian_b 3y ago
    That is why I have said that if updating the pre-shared authentication keys through separate communication channels is impractical, they can be updated through hybrid public-key based key exchange methods. If a hybrid key exchange method is used e.g. only after one thousand or even after one hundred of connections made with pre-shared keys, then the hybrid method can be very slow without significant impact. This is the same like reusing in TLS 1.3 a previously computed shared secret for a new connection, just using this for a large enough number of successive connections so that the slowness of the constrained device does not matter.

JacobiX 3y ago

I believe there is maybe a little contradiction with the NSA's own 'Rule of Two,' as outlined in their Commercial Solutions for Classified Program (CSfC). It specifies two completely independent layers of cryptography to protect data :)

api 3y ago
Good catch. If one is PQ and one is not, that accomplishes the same thing as a hybrid.

mplewis9z 3y ago

Putting on my tinfoil hat, I think there’s also an argument to be made that the NSA might want to slow down adoption of post-quantum algorithms, which their stance against hybrids definitely accomplishes. If there’s a single organization that could be 10-20 years ahead of where people think they are on something like a useful quantum computer, it’s the NSA (powered by the US’s absurd defense budget). If they can slow down the adoption of post-quantum algorithms, they can maintain their potential head start for longer and be able to break current cryptosystems and extract actually valuable information. Outside of the NSA (and its affiliates), most of the cryptographic community seems to have come together in support of hybrids, which would greatly accelerate the adoption of some level of post-quantum defense. With even the most “liberal” cryptographers thinking that more careful cryptanalysis of post-quantum algorithms is needed before widespread adoption as the sole line of cryptographic defense, if the NSA manages to convince sufficient people that hybrids aren’t viable enough for production (and thus stick with classical algorithms) they may be able to maintain the ability to break sensitive communications for longer when and if their quantum computer efforts have a breakthrough.

Gustomaximus 3y ago
Or could it be a bluff. Act like they don't want it, so some players feel they can use more advanced post-quantum algorithms and be secure, while NSA is decrypting it.
- mplewis9z 3y ago
  Maybe, but this argument holds less weight given that they’re the ones pushing for inclusion of these algorithms in the NIST standards, and are really only advocating against the hybrid algorithms. I honestly think the NSA learned their lesson with the whole debacle around Dual_EC_DRBG and skepticism about their elliptic curve seeds - especially given the continued exponential growth in sensitive electronic communications and records, they want the algorithms as secure as possible without a backdoor that could leak and be a foot-gun for US communications as well. Instead, they’ll just throw more money at making a usable quantum computer than the next country spends on their entire cryptographic infrastructure, and get targeted backdoors into software/hardware implementations of the encryption algorithms so they can focus their attacks more precisely.

deleted 3y ago

[deleted]

bbqbbqbbq 3y ago

[dead]

vinay_ys 3y ago

Thoroughly enjoyed reading DJB's writing. That style of arguing is so effective and yet so easily understandable by anyone having even basic understanding of cryptography. I hope there are students of his who are as good as him (or even better) and continue this kind of work for decades to come.

hdevalence 3y ago
I can’t recommend that anyone would be Dan’s student.
- trillic 3y ago
  Why’s that? I had him back in undergrad and he was a spectacular lecturer. Course wasn’t too rigorous but definitely inspired a further interest in security.
  - tptacek 3y ago
    The person you're responding to, themselves a cryptography engineer, was, famously, one of his students.
  - count 3y ago
    https://medium.com/@hdevalence/when-hell-kept-on-payroll-somewhere-is-where-you-are-f419d3022d0 https://medium.com/@hdevalence/when-hell-kept-on-payroll-som... He's written about it here.
warner25 3y ago
It looks like he doesn't have many students. His current title appears to be "Research Professor" and he's the sole author of every "new paper" mentioned in this blog post and most of the recent papers listed on this page: https://cr.yp.to/papers.html https://cr.yp.to/papers.html I'm really curious about this now. How does he write something like half a dozen different papers per year as a sole author? These aren't short papers either; they're dozens of pages. Usually when I see a professor with an incredibly prolific publication history, it's because they have a bunch of PhD students (each working on a paper per year) and they collaborate with a bunch of other professors. He also seems to be quite a character; unafraid to publicly document battles with his employer, IEEE, and the US government.

Retr0id 3y ago

> Any reasonable risk assessment will conclude that the probability of an exploitable arithmetic bug or timing leak or randomness-usage mistake in the UltraKEM software is higher than the probability of such a exploit in the X25519 software. It seems strange to pit a specific classical algorithm against a general-case PQ algorithm made up for the sake of argument, it feels like a bit of a straw man. I've written hobbyist-grade implementations of both X25519 and ML-KEM-768 (aka Kyber). All other things being equal, I think arithmetic bugs in X25519 are more likely, given that it uses 255-bit integer arithmetic, requiring a custom bigint implementation if you want peak performance. Doing 255-bit arithmetic that is both fast, and provably does not contain limb overflow edge-cases (to name just one possible bug class), is hard. At the very least, it's not something I'd trust myself to be able to do. On the other hand, Kyber arithmetic all fits within standard register sizes, without needing to split things up. This doesn't make it immune from arithmetic-related issues (as KyberSlash demonstrates), but it's probably easier to get right overall. I agree that for the time being, the average X25519 impl will be significantly more trustworthy than the average Kyber implementation (or any other PQ construction), due to its maturity, but it seems dishonest to imply that PQ algorithms are inherently harder to get right. Despite this, I am broadly in favour of Hybrid schemes. It seems like the anti-hybrid stance is mostly coming from large slow-moving orgs - sucks to suck, but don't let your unagility hold the rest of us back!

Beldin 3y ago
> I agree that for the time being, the average X25519 impl will be significantly more trustworthy than the average Kyber implementation (or any other PQ construction), due to its maturity, but it seems dishonest to imply that PQ algorithms are inherently harder to get right. I understood TFA's point to be exactly this. That is, security designs that have existed significantly longer and were in active, widespread use will have been analysed far better than the new kids on the block.

tptacek 3y ago

No serious organization is going to deploy pure, non-hybrid PQC, as Bernstein tacitly acknowledges when he lists essentially all the major deployments of PQC in production to date, all of which are hybrids.

Retr0id 3y ago
Isn't that kinda the whole point? If deploying non-hybrid schemes is needlessly risky (I agree), then why should NIST et al certify those deployments?
rainworld 3y ago
[flagged]

heads 3y ago

I’m very naive about the upcoming quantum cryptography switchover. Can anyone here recommend a good podcast to learn about it more?

dave1010uk 3y ago
Not a podcast but if it helps, I wrote an overview article that goes from the basics of cryptography (eg RSA) and quantum computers (eg qubits), explaining how a post quantum cryptographic algorithm works (Kyber) and briefly touches on current hybrid implementations: https://medium.com/@dave1010/post-quantum-cryptography-its-already-here-and-it-s-not-as-scary-as-it-sounds-cb8ea70e8f1c https://medium.com/@dave1010/post-quantum-cryptography-its-a...

atoav 3y ago

Not to suggest anything, but imagine you are a secret service in a world in which the cat (knowledge about safe cryptograophic procedures) is out of the bag. Wouldn't a great strategy be to invent some sort of story why that old reliable crypto is now potentially unsafe, so you propose a new standard, that may or may not have a known weakness. And then some paranoid freaks come along that just use both.. Jikes. This is of course just me thinking loud here and pure speculation. We will probably never know for sure.

thelittleone 3y ago
Like the Dual_EC_DRBG issue involving the NSA?