5 ms·

I've often thought the use of prime numbers to be the weakness in cryptography. Whilst theory is different in practice due to machine limitations, there are on

I've often thought the use of prime numbers to be the weakness in cryptography. Whilst theory is different in practice due to machine limitations, there are only so many prime numbers a machine can present in a limited timespan restricting the range of primes available to use. With this in mind, and then knowing what a webserver will typically use by simply browsing the website with different encryption algo's disabled in the browser if its not possible to work out the underlying webserver software and version from a variety of methods like a simple 404 message, decoding the URL or using DPI, further limits the encryption algorithms to spend time reversing when using the replay attack method making it somewhat more targeted. Its still a sort of brute force but a more targeted brute force. So should I see primes as a weakness in cryptography?

bdamm 5y ago
No. First of all, primes are only used to arrive at a session key, and once you have a session key you're in the land of symmetric algorithms, which provide security by permutations rather than vectoring into prime spaces. The content of a web page does not matter at all in terms of the security being provided. A 404 is just as secure as a valid home page, in terms of cryptography. (Not in terms of application security, but that's a whole different thing.) Second, the supply of prime numbers is countable but also infinite, and the relation between a number space and the number of primes within it is well established within the workable sizes. We have upper and lower bounds on the number of primes within certain ranges. This is partly why we end up with certain key sizes as being secure and other key sizes as being insufficient. Secure key sizes (in asymmetric algorithms) partly are secure because there are so many primes that can be fodder for key generation.
- schoen 5y ago
  Well said. A fun way to improve one's intuition for the huge space of primes in the regions that are used in cryptography is to run something like openssl prime -generate -bits 1024 (This would give you one of two secret parameters for a 2048-bit RSA modulus.) Here is an example output: 171512683213144641422165911053946068613736141364433791764418217818329805042681574174826781297743340609766353737741548521280185783254625590756752560896455821248403501924867464886010664489035275551178636464876794754383911750620888923620343965444339734253757757361106691647372710935609902417522529107877592063581 Not very easy to guess just because the space in question is limited to "1024-bit primes"! And indeed, that's part of why we use primes that are this big when we still use RSA. They're big enough that the number of possibilities makes them not easy to guess (even given the extra hint of "the secret number you're looking for is one of the factors of this 2048-bit semiprime"). Exponentials are always hard for human intuition. We start with some kind of pattern and it feels like there just aren't that many numbers that would satisfy it. But when you get out to large numbers (even numbers as large as the one above), there just are that many numbers that would satisfy the pattern!
- Terry_Roll 5y ago
  So in a replay attack all the communication is recorded including the session keys, and whilst primes are infinite dont dispute this, where the theory (human) and the practical (cpu's) differs is the limitations in the machine hardware, in much the same way Spectre and Meltdown exploited the hardware to obtain secrets. The point about the webserver was using methods to work out what the underlying webserver and version was and potentially the OS, after all not much point trying to decrypt an algo that is not used on the webserver, but metadata is given out by many webservers to suggest what type of webserver it is. And then there is education, we see people believe many things because this is what's taught to them, we see this cognitive dissonance with religious people but also in "educated" people like some GP's or academics because its their life's work and I'm sure cryptography has consumed many hours of people thinking things through, without much time spent on other areas of weakness like the limitations of a cpu and memory registers. After all how many crypto experts are fully conversant with the inner workings of a CPU design? If they were conversant with CPU designs would Spectre and Meltdown have been found years earlier? Admittedly side channel attacks but I did say in my original post "Whilst theory is different in practice due to machine limitations" and this is the thing is the current implementation of cryptography on devices suitable when considering the design of CPU's and devices?
  - bdamm 5y ago
    Cryptanalysis is a pretty robust area of research. There are in fact a lot of cryptanalysts that know CPUs quite deeply. Certain organizations spend a great deal of money to make it so. If vulnerabilities are found we learn from them and advance the understanding of cryptography design. It has been that way for 76 years now, at least.
    - Terry_Roll 5y ago
      Not disputing what you say, but mistakes do happen to the best of us. http://sunnyday.mit.edu/accidents/Ariane5accidentreport.html http://sunnyday.mit.edu/accidents/Ariane5accidentreport.html and yet again another OpenSSL bug , another flaw in the open source fallacy of many eyes to spot bugs... https://nakedsecurity.sophos.com/2021/03/28/serious-security-openssl-fixes-two-high-severity-crypto-bugs/ https://nakedsecurity.sophos.com/2021/03/28/serious-security... plus when considering in maths there are ways to rearrange formulas including new discoveries like this one (a new way to do quadratic equations) https://news.ycombinator.com/item?id=29342161 https://news.ycombinator.com/item?id=29342161 https://www.sciencealert.com/math-genius-finally-discovers-easy-way-to-solve-quadratic-equations-after-4-000-years https://www.sciencealert.com/math-genius-finally-discovers-e... I wonder if discovering a new way to do things could be done to cryptographic algorithms.
CasperDern 5y ago
Not an expert, but I don't think it's necessarily a weakness in the current applications of cryptography. In something like RSA a typical key is >=1024 bits, which is 1.7e308 possible number so even though primes are more "limited" the actual reduction in security (if non-primes could have been used by magic) the primes that are left are still plentiful. One reason RSA is not really used anymore is because other algorithms such as elliptic curve cryptography provides much better efficiency (partially due to it not requiring primes keys). So it's less efficient than more modern technologies, but not necessarily weaker.
garmaine 5y ago
Almost no cryptography being deployed today uses prime numbers. (Not because of any weakness, but because there are better, more efficient algorithms instead.)
- marcan_42 5y ago
  RSA is still in wide use in both old and new deployments (e.g. it is still the majority of TLS handshakes). Elliptic curves are faster and use smaller keys, but they're also a more fragmented ecosystem; plus, in particular for the older NIST curves, there is the unshakable fear that they're backdoored by the NSA (since they use magic unexplainable numbers, which RSA does not). Thankfully ed25519 gave us an alternative free of magic numbers, and it's seeing a lot of adoption (in particular in open source software), but it's nowhere near taking over RSA.
  - tptacek 5y ago
    No cryptography engineer seriously believes the NIST P-curves are backdoored, and they are in widespread use. Ed25519 is a signing scheme; it isn't a replacement for the RSA in classic TLS --- you'd be thinking of Curve25519, its sibling. The benefit of the 25519s isn't "no magic numbers", it's a structure that makes it easy to implement relatively safely. And all these curves work over prime subfields. This is all 100% pedantry. But the belief that RSA is risky because "prime numbers" is false, and worth pushing back on. There are reasons not to use RSA, but they're not as simple as "we don't trust prime field cryptography".
    - marcan_42 5y ago
      No magic numbers is certainly one of the advantages of curve25519 and its siblings. The NSA already gave us one backdoored elliptic curve algorithm (Dual EC DRBG); there is no reason to trust them with magic numbers. They may be backdoored or they may not be, but every serious cryptography engineer knows there's no good reason for algorithm constants not to be generated according to public criteria if you aren't hiding anything. Sometimes they're hiding that they picked numbers that made the algorithm stronger against secret attacks they discovered (DES). Sometimes they're hiding a backdoor (Dual EC DRBG). We'd all rather they not hide anything. More info: https://safecurves.cr.yp.to/rigid.html https://safecurves.cr.yp.to/rigid.html Ed25519 is a replacement for RSA in the x.509 WebPKI, which is what I was trying to refer to when I said TLS. Classic TLS (as in non-PFS, the one that also used RSA to encrypt the session secret) is dead and nobody cares about replacing it with anything. There is no public key encryption involved in modern TLS; instead all you need is a signature scheme (for the certificate and for the final server to authenticate itself) and a key exchange scheme. The former can be ed25519. The latter can be curve25519 (specifically, the retroactively named X25519 ECDH key exchange). My point is precisely that there's no inherent distrust in RSA (and some concerns with NIST EC, both the magic numbers and secure implementation difficulty), which is why we haven't abandoned it yet. There is certainly no inherent issue with prime field cryptography.

bdamm 5y ago

No. First of all, primes are only used to arrive at a session key, and once you have a session key you're in the land of symmetric algorithms, which provide security by permutations rather than vectoring into prime spaces. The content of a web page does not matter at all in terms of the security being provided. A 404 is just as secure as a valid home page, in terms of cryptography. (Not in terms of application security, but that's a whole different thing.) Second, the supply of prime numbers is countable but also infinite, and the relation between a number space and the number of primes within it is well established within the workable sizes. We have upper and lower bounds on the number of primes within certain ranges. This is partly why we end up with certain key sizes as being secure and other key sizes as being insufficient. Secure key sizes (in asymmetric algorithms) partly are secure because there are so many primes that can be fodder for key generation.

schoen 5y ago
Well said. A fun way to improve one's intuition for the huge space of primes in the regions that are used in cryptography is to run something like openssl prime -generate -bits 1024 (This would give you one of two secret parameters for a 2048-bit RSA modulus.) Here is an example output: 171512683213144641422165911053946068613736141364433791764418217818329805042681574174826781297743340609766353737741548521280185783254625590756752560896455821248403501924867464886010664489035275551178636464876794754383911750620888923620343965444339734253757757361106691647372710935609902417522529107877592063581 Not very easy to guess just because the space in question is limited to "1024-bit primes"! And indeed, that's part of why we use primes that are this big when we still use RSA. They're big enough that the number of possibilities makes them not easy to guess (even given the extra hint of "the secret number you're looking for is one of the factors of this 2048-bit semiprime"). Exponentials are always hard for human intuition. We start with some kind of pattern and it feels like there just aren't that many numbers that would satisfy it. But when you get out to large numbers (even numbers as large as the one above), there just are that many numbers that would satisfy the pattern!
Terry_Roll 5y ago
So in a replay attack all the communication is recorded including the session keys, and whilst primes are infinite dont dispute this, where the theory (human) and the practical (cpu's) differs is the limitations in the machine hardware, in much the same way Spectre and Meltdown exploited the hardware to obtain secrets. The point about the webserver was using methods to work out what the underlying webserver and version was and potentially the OS, after all not much point trying to decrypt an algo that is not used on the webserver, but metadata is given out by many webservers to suggest what type of webserver it is. And then there is education, we see people believe many things because this is what's taught to them, we see this cognitive dissonance with religious people but also in "educated" people like some GP's or academics because its their life's work and I'm sure cryptography has consumed many hours of people thinking things through, without much time spent on other areas of weakness like the limitations of a cpu and memory registers. After all how many crypto experts are fully conversant with the inner workings of a CPU design? If they were conversant with CPU designs would Spectre and Meltdown have been found years earlier? Admittedly side channel attacks but I did say in my original post "Whilst theory is different in practice due to machine limitations" and this is the thing is the current implementation of cryptography on devices suitable when considering the design of CPU's and devices?
- bdamm 5y ago
  Cryptanalysis is a pretty robust area of research. There are in fact a lot of cryptanalysts that know CPUs quite deeply. Certain organizations spend a great deal of money to make it so. If vulnerabilities are found we learn from them and advance the understanding of cryptography design. It has been that way for 76 years now, at least.
  - Terry_Roll 5y ago
    Not disputing what you say, but mistakes do happen to the best of us. http://sunnyday.mit.edu/accidents/Ariane5accidentreport.html http://sunnyday.mit.edu/accidents/Ariane5accidentreport.html and yet again another OpenSSL bug , another flaw in the open source fallacy of many eyes to spot bugs... https://nakedsecurity.sophos.com/2021/03/28/serious-security-openssl-fixes-two-high-severity-crypto-bugs/ https://nakedsecurity.sophos.com/2021/03/28/serious-security... plus when considering in maths there are ways to rearrange formulas including new discoveries like this one (a new way to do quadratic equations) https://news.ycombinator.com/item?id=29342161 https://news.ycombinator.com/item?id=29342161 https://www.sciencealert.com/math-genius-finally-discovers-easy-way-to-solve-quadratic-equations-after-4-000-years https://www.sciencealert.com/math-genius-finally-discovers-e... I wonder if discovering a new way to do things could be done to cryptographic algorithms.

CasperDern 5y ago

Not an expert, but I don't think it's necessarily a weakness in the current applications of cryptography. In something like RSA a typical key is >=1024 bits, which is 1.7e308 possible number so even though primes are more "limited" the actual reduction in security (if non-primes could have been used by magic) the primes that are left are still plentiful. One reason RSA is not really used anymore is because other algorithms such as elliptic curve cryptography provides much better efficiency (partially due to it not requiring primes keys). So it's less efficient than more modern technologies, but not necessarily weaker.

garmaine 5y ago

Almost no cryptography being deployed today uses prime numbers. (Not because of any weakness, but because there are better, more efficient algorithms instead.)

marcan_42 5y ago
RSA is still in wide use in both old and new deployments (e.g. it is still the majority of TLS handshakes). Elliptic curves are faster and use smaller keys, but they're also a more fragmented ecosystem; plus, in particular for the older NIST curves, there is the unshakable fear that they're backdoored by the NSA (since they use magic unexplainable numbers, which RSA does not). Thankfully ed25519 gave us an alternative free of magic numbers, and it's seeing a lot of adoption (in particular in open source software), but it's nowhere near taking over RSA.
- tptacek 5y ago
  No cryptography engineer seriously believes the NIST P-curves are backdoored, and they are in widespread use. Ed25519 is a signing scheme; it isn't a replacement for the RSA in classic TLS --- you'd be thinking of Curve25519, its sibling. The benefit of the 25519s isn't "no magic numbers", it's a structure that makes it easy to implement relatively safely. And all these curves work over prime subfields. This is all 100% pedantry. But the belief that RSA is risky because "prime numbers" is false, and worth pushing back on. There are reasons not to use RSA, but they're not as simple as "we don't trust prime field cryptography".
  - marcan_42 5y ago
    No magic numbers is certainly one of the advantages of curve25519 and its siblings. The NSA already gave us one backdoored elliptic curve algorithm (Dual EC DRBG); there is no reason to trust them with magic numbers. They may be backdoored or they may not be, but every serious cryptography engineer knows there's no good reason for algorithm constants not to be generated according to public criteria if you aren't hiding anything. Sometimes they're hiding that they picked numbers that made the algorithm stronger against secret attacks they discovered (DES). Sometimes they're hiding a backdoor (Dual EC DRBG). We'd all rather they not hide anything. More info: https://safecurves.cr.yp.to/rigid.html https://safecurves.cr.yp.to/rigid.html Ed25519 is a replacement for RSA in the x.509 WebPKI, which is what I was trying to refer to when I said TLS. Classic TLS (as in non-PFS, the one that also used RSA to encrypt the session secret) is dead and nobody cares about replacing it with anything. There is no public key encryption involved in modern TLS; instead all you need is a signature scheme (for the certificate and for the final server to authenticate itself) and a key exchange scheme. The former can be ed25519. The latter can be curve25519 (specifically, the retroactively named X25519 ECDH key exchange). My point is precisely that there's no inherent distrust in RSA (and some concerns with NIST EC, both the magic numbers and secure implementation difficulty), which is why we haven't abandoned it yet. There is certainly no inherent issue with prime field cryptography.