_How_ many false positives?
_How_ many false positives?
Posted Oct 18, 2017 14:20 UTC (Wed) by tialaramex (subscriber, #21167)In reply to: _How_ many false positives? by ballombe
Parent article: Millions of high-security crypto keys crippled by newly discovered flaw (Ars Technica)
The actual pattern is that M^a mod s = 1 for (some?) small primes s and some particular value of a that's a factor of (s-1) in the case of each prime. The other numbers in the Technical Report and in the fingerprinting code are an artefact of that caused by how modulus groups work. The researchers didn't mention this in 2016. I assume that's because they didn't know (mathematicians are welcome to chime in and say e.g. "It's obvious from a glance at that table what's going on" and I'll believe them).
My conjecture is that you're at least half right, it's not some, but all small primes p, but the researchers did not desire to spell this part out so their code rather than compute M^a mod s does M mod s and checks the bitmask. For some primes this doesn't do anything useful, but it rhymes nicely with the original Technical Report output.
This would mean M-1 is ludicrously smooth. M-1 has every small prime as a factor. My further conjecture is that M-1 is so smooth because p-1 and q-1 are also ridiculously smooth, each contributing enough smoothness on its own so that the result is ludicrous. It seems to me that if this is so, even without anything else, you've got yourself what, several hundred bits of knowledge about the private keys from knowing they're so smooth on its own ? Seems pretty bad.
But the first conjecture is directly testable. I will write some code this evening if nobody beats me to it, m.d.s.policy regular and crt.sh developer Rob Stradling has uploaded a list of certificates sent to CT logs (thus public keys) which are marked as likely Infineon by the existing fingerprint test. If all of them have this ludicrously smooth M-1 then my conjecture is correct. If all but one or two do then we have also demonstrated that the test has a small false positive rate as written, and if few or none do then my conjecture is entirely wrong and I need to reconsider.
Posted Oct 18, 2017 16:40 UTC (Wed)
by ballombe (subscriber, #9523)
[Link] (2 responses)
Posted Oct 19, 2017 9:16 UTC (Thu)
by tialaramex (subscriber, #21167)
[Link] (1 responses)
This is probably from an Infineon device: https://crt.sh/?id=215433230
This one, though it passes that test, is not: https://crt.sh/?id=3084867 - something else is afoot here.
Posted Nov 1, 2017 9:34 UTC (Wed)
by tialaramex (subscriber, #21167)
[Link]
https://crocs.fi.muni.cz/_media/public/papers/nemec_roca_...
It mentions these strange keys, but offers no particular insight into them, other than agreeing they cannot have been made by an unaltered version of the library from Infineon.
The ROCA attack only needs
p=k * M+((65537 ^ a) mod M)
[and q is the same but for different k, a ]
Where M is a primorial (the product of all the primes from 2 upwards) chosen to be slightly smaller than the desired key size and thus M varies only with the key size, which we know. It remains unclear to me exactly why Infineon's library causes this to happen.
The paper's attack is a speed-up of a naive attack from just knowing the above, which is already bad enough to consider the keys unusable, but not bad enough to be a practical attack on its own. The mathematics is too hard for me to actually attempt their speed-up, but I think I understand roughly what they intend. The paper indicates that they've confirmed their attack works on smaller keys by actually doing it in full, and on larger keys where they took a "sneak peak" so they can choose to attack one that will fall much earlier than would be expected by chance.
_How_ many false positives?
Also I expect this actually holds for both prime factors.
_How_ many false positives?
_How_ many false positives?