5 ms·

I think this is a rather about building a backdoor into a library which implements Diffie-Hellman, if I understand this correctly. The method itself is not flaw

by chki 10y ago

I think this is a rather about building a backdoor into a library which implements Diffie-Hellman, if I understand this correctly. The method itself is not flawed.

dogma1138 10y ago
Just to make it slightly clearer this is about a "mathematical backdoor" not a software one. This isn't about making a backdoor that looks like this: for each (user.session.ip_addr in nsa_addrs[]) { user.session.isauth = true; } This is about weakening the mathematical constructs of a DH implementation in a way that would not be noticeable even in a code review conducted by software security experts.
- colechristensen 10y ago
  >not be noticeable even in a code review conducted by software security experts. Unless they've read this :)
  - dogma1138 10y ago
    Only if they have both the capability and knowledge of reviewing how certain cryptographic parameters / initial states were chosen this isn't something you can easily detect unless you know very specifically what you are looking for. This isn't that much different than the ECC "NSA" NIST presumed backdoor in the Dual-EC module of RSA[0]. The Dual-EC backdoor was pretty much identical to a one that 2 cryptographers presented in 1997 however it took about 15 years for this to be "discovered" and even now we don't have decisive proof that the NSA or any other entity had selected those specific values because it pre-computed (or potentially knew it could compute it within X amount of years) the relationship between them. There aren't that many security experts that can audit such systems in the first place, and the few that can will most likely not have the same resources that a state actor level adversary would to select values that could be used for a NBOUS backdoor, even if you know what you are looking for when testing initial values some one with 10 times the computing power you have can select better values that would both serve as a backdoor and would be resistant to reversing by outsiders. My personal projection for the next 10 years or so is that there will be a huge push towards dumping any cryptographic system that is based on some initial seed values and/or a lot of work needs to be done to be able to generate or prove NUMS[1] in regards to those values. [0]https://en.wikipedia.org/wiki/Dual_EC_DRBG https://en.wikipedia.org/wiki/Dual_EC_DRBG [1]https://en.wikipedia.org/wiki/Nothing_up_my_sleeve_number https://en.wikipedia.org/wiki/Nothing_up_my_sleeve_number
    - rocqua 10y ago
      I believe both attacks described here require the modulus to be composite not prime. Wouldn't then the only necessary review necessary be to check the primality of the modulus used in DH?
      - dogma1138 10y ago
        Primality tests are effectively brute force computations, if your adversary has considerably more compute power than you they could calculate values that you would not be able to identify as being composite. For example SSH-Keygen uses the Miller-Rabin[0] test on the moduli and depending on the bit size if your number and the number of rounds you get a probability of how likely it is that the number is prime or not, but effectively there is never a guarantee because of the size of the numbers in question. The likelihood of an adversary being able to compute a value that you would consider to be prime but infact it would not be is directly tied to the size of the number, the method of verification you are using, and how much resources you are spending to evaluate that number. Given an adversary that in all likelihood completely outclasses you in computational capacity, and is also likely to be able to develop more efficient algorithms than those available to you there is a pretty good chance that they will able to backdoor you every time without you having an effective counter measure or the ability to detect it if they choose to do so. [0]https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality...

by chki 10y ago

I think this is a rather about building a backdoor into a library which implements Diffie-Hellman, if I understand this correctly. The method itself is not flawed.

dogma1138 10y ago

Just to make it slightly clearer this is about a "mathematical backdoor" not a software one. This isn't about making a backdoor that looks like this: for each (user.session.ip_addr in nsa_addrs[]) { user.session.isauth = true; } This is about weakening the mathematical constructs of a DH implementation in a way that would not be noticeable even in a code review conducted by software security experts.

colechristensen 10y ago
>not be noticeable even in a code review conducted by software security experts. Unless they've read this :)
- dogma1138 10y ago
  Only if they have both the capability and knowledge of reviewing how certain cryptographic parameters / initial states were chosen this isn't something you can easily detect unless you know very specifically what you are looking for. This isn't that much different than the ECC "NSA" NIST presumed backdoor in the Dual-EC module of RSA[0]. The Dual-EC backdoor was pretty much identical to a one that 2 cryptographers presented in 1997 however it took about 15 years for this to be "discovered" and even now we don't have decisive proof that the NSA or any other entity had selected those specific values because it pre-computed (or potentially knew it could compute it within X amount of years) the relationship between them. There aren't that many security experts that can audit such systems in the first place, and the few that can will most likely not have the same resources that a state actor level adversary would to select values that could be used for a NBOUS backdoor, even if you know what you are looking for when testing initial values some one with 10 times the computing power you have can select better values that would both serve as a backdoor and would be resistant to reversing by outsiders. My personal projection for the next 10 years or so is that there will be a huge push towards dumping any cryptographic system that is based on some initial seed values and/or a lot of work needs to be done to be able to generate or prove NUMS[1] in regards to those values. [0]https://en.wikipedia.org/wiki/Dual_EC_DRBG https://en.wikipedia.org/wiki/Dual_EC_DRBG [1]https://en.wikipedia.org/wiki/Nothing_up_my_sleeve_number https://en.wikipedia.org/wiki/Nothing_up_my_sleeve_number
  - rocqua 10y ago
    I believe both attacks described here require the modulus to be composite not prime. Wouldn't then the only necessary review necessary be to check the primality of the modulus used in DH?
    - dogma1138 10y ago
      Primality tests are effectively brute force computations, if your adversary has considerably more compute power than you they could calculate values that you would not be able to identify as being composite. For example SSH-Keygen uses the Miller-Rabin[0] test on the moduli and depending on the bit size if your number and the number of rounds you get a probability of how likely it is that the number is prime or not, but effectively there is never a guarantee because of the size of the numbers in question. The likelihood of an adversary being able to compute a value that you would consider to be prime but infact it would not be is directly tied to the size of the number, the method of verification you are using, and how much resources you are spending to evaluate that number. Given an adversary that in all likelihood completely outclasses you in computational capacity, and is also likely to be able to develop more efficient algorithms than those available to you there is a pretty good chance that they will able to backdoor you every time without you having an effective counter measure or the ability to detect it if they choose to do so. [0]https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality...