4 ms·

I particularly enjoyed the section where he talks about the importance of distributions for security, and how the product of two independent random primes in th

I particularly enjoyed the section where he talks about the importance of distributions for security, and how the product of two independent random primes in the {2^1023,...,2^1024} is harder to factor than the same in the {1,...,2^1024} space despite the latter having far more possibilities available. His explanation of this is concise and clear, and while the point is fairly simple once understood it's a great example of how counter-intuitive this stuff can be.

tialaramex 7y ago
You also have to be careful here because such unintuitive factors plus a desire for optimisation can lead to grave security holes, and DJB links such a thing in that section. ROCA (Return of Coppersmith's Attack) is a weakness where Infineon designed a hardware library RSAlib that chooses numbers that were much more likely to be prime, so that (as I understand it) their key generation is nice and fast because it spends less time failing primality tests and trying again. Unfortunately it uses very particular smooth numbers (1 x 3 x 5 x 7 x 11 and so on) to pick keys for each key size, and so an attacker who knows this essentially get some bits from the private key for free, whereupon Coppersmith's approach may turn that into a working attack. The people who found ROCA started by examining the key pairs chosen by different generators because they were interested in whether you can diagnose who made a key based on what you see of the public key. They wrote a paper about this showing that e.g. sometimes you'd get a certificate with a particular 2048-bit RSA key in it and you could tell immediately oh, that's from OpenSSL even though this cert is deployed on a Windows server with IIS, so that's interesting. For example let's say you pick random 1024-bit integers and multiply them together, but you insist on trying again if you get anything other than a 2048-bit result, this will be annoyingly slow, it often fails, so you of course optimise by picking only a specific range of integers where a 2048-bit result seems likely. Exactly how you do this may give away _at least_ exactly which implementation was used to make the keys, and as ROCA shows maybe much more. One of the clearly better things about public key cryptographic systems that depend on arbitrary random integers as keys rather than primes/semi-primes like RSA is that it's less tempting to build very complicated contraptions like RSAlib which may conceal this sort of terrible flaw.

tialaramex 7y ago

You also have to be careful here because such unintuitive factors plus a desire for optimisation can lead to grave security holes, and DJB links such a thing in that section. ROCA (Return of Coppersmith's Attack) is a weakness where Infineon designed a hardware library RSAlib that chooses numbers that were much more likely to be prime, so that (as I understand it) their key generation is nice and fast because it spends less time failing primality tests and trying again. Unfortunately it uses very particular smooth numbers (1 x 3 x 5 x 7 x 11 and so on) to pick keys for each key size, and so an attacker who knows this essentially get some bits from the private key for free, whereupon Coppersmith's approach may turn that into a working attack. The people who found ROCA started by examining the key pairs chosen by different generators because they were interested in whether you can diagnose who made a key based on what you see of the public key. They wrote a paper about this showing that e.g. sometimes you'd get a certificate with a particular 2048-bit RSA key in it and you could tell immediately oh, that's from OpenSSL even though this cert is deployed on a Windows server with IIS, so that's interesting. For example let's say you pick random 1024-bit integers and multiply them together, but you insist on trying again if you get anything other than a 2048-bit result, this will be annoyingly slow, it often fails, so you of course optimise by picking only a specific range of integers where a 2048-bit result seems likely. Exactly how you do this may give away _at least_ exactly which implementation was used to make the keys, and as ROCA shows maybe much more. One of the clearly better things about public key cryptographic systems that depend on arbitrary random integers as keys rather than primes/semi-primes like RSA is that it's less tempting to build very complicated contraptions like RSAlib which may conceal this sort of terrible flaw.