2 ms·

How are they able to test my key within seconds?

iancarroll 9y ago
The full paper is not out yet, so there is limited information. But the official website[0] mentions: > The specific structure of the primes in question allows for a fast detection of vulnerable keys, even in very large datasets. [0] https://crocs.fi.muni.cz/public/papers/rsa_ccs17 https://crocs.fi.muni.cz/public/papers/rsa_ccs17
tialaramex 9y ago
The affected keys are made by Infineon's weird RSA key generator. This produces keys with weird properties, listed in their 2016 paper and more so in the accompanying Technical Report. The test they released today just checks for the oddest of those properties, if you divide the modulus (the main part of the RSA public key) by some small primes (e.g. 11) and take the remainder then instead of a random answer other then zero (zero would be super bad) you always get specific answers. So the code checks about two dozen small primes in this way. This probably had nothing directly to do with the attack, but it finds Infineon keys and only those are affected.
- baybal2 9y ago
  66PE do have a history of strange things happening to their RNG output. I wonder, was the RNG intentionally tampered?
- ibmthrowaway218 9y ago
  I think there's some obfuscation in the tests:- As you say, the first few test numbers correspond just to simple divisor checks:- Prime 3 paired with check number 6 (binary 110). So 1 << (n % 3) will only ever be 'safe' if n % 3 == 0, which is 'super bad' as you put it. (2^3)-2 = 6 (2^5)-2 = 30 so this is a similar division check (2^7)-2 = 126 ditto I think these are just here as distractions as it starts to sometimes do different things at p=11 11 is paired with check number 1026, which is (2^10)+2 not (2^11)-2). So under what conditions does:- ( 1 << (n % 11) ) & 1026 != 0 Given 1026 only has two bits set (1024 and 2) it's a rather specific test for (n%11) = 1 or 10. All other residues would be safe. Don't have time to investigate further for the other primes and check numbers but I can only think of some kind of p-1 or p+1 smoothness they can detect this way.

The full paper is not out yet, so there is limited information. But the official website[0] mentions: > The specific structure of the primes in question allows for a fast detection of vulnerable keys, even in very large datasets. [0] https://crocs.fi.muni.cz/public/papers/rsa_ccs17 https://crocs.fi.muni.cz/public/papers/rsa_ccs17

tialaramex 9y ago

The affected keys are made by Infineon's weird RSA key generator. This produces keys with weird properties, listed in their 2016 paper and more so in the accompanying Technical Report. The test they released today just checks for the oddest of those properties, if you divide the modulus (the main part of the RSA public key) by some small primes (e.g. 11) and take the remainder then instead of a random answer other then zero (zero would be super bad) you always get specific answers. So the code checks about two dozen small primes in this way. This probably had nothing directly to do with the attack, but it finds Infineon keys and only those are affected.

baybal2 9y ago
66PE do have a history of strange things happening to their RNG output. I wonder, was the RNG intentionally tampered?
ibmthrowaway218 9y ago
I think there's some obfuscation in the tests:- As you say, the first few test numbers correspond just to simple divisor checks:- Prime 3 paired with check number 6 (binary 110). So 1 << (n % 3) will only ever be 'safe' if n % 3 == 0, which is 'super bad' as you put it. (2^3)-2 = 6 (2^5)-2 = 30 so this is a similar division check (2^7)-2 = 126 ditto I think these are just here as distractions as it starts to sometimes do different things at p=11 11 is paired with check number 1026, which is (2^10)+2 not (2^11)-2). So under what conditions does:- ( 1 << (n % 11) ) & 1026 != 0 Given 1026 only has two bits set (1024 and 2) it's a rather specific test for (n%11) = 1 or 10. All other residues would be safe. Don't have time to investigate further for the other primes and check numbers but I can only think of some kind of p-1 or p+1 smoothness they can detect this way.