_How_ many false positives?
_How_ many false positives?
Posted Oct 17, 2017 14:20 UTC (Tue) 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)
I mean, it looked to me - and I confess I'm not exactly confident I understand all of Coppersmith - as if Svenda just wrote out the list of all the small primes, with a bitmask for each one, and it so happens the masks for about half have all the bits set (except the zeroth) and so won't do anything for any real world RSA modulus. I'd taken this as either a gesture to obfuscation (don't spell out what you're actually doing) or as the sort of craziness you see when mathematicians write code, like not knowing that ordinary humans think bitmasks shouldn't be written as decimals...
But it seems like you're saying there's something else here, if we knew p and q we could do... the same trials on those and see something more interesting even for the small primes which aren't interesting with just the modulus, so that's why those tests are left in the code we see ? Or something ? I'd really like to understand this better. I appreciate that only Petr Svenda, his reviewers (and presumably Infineon) know exactly what's actually up here but it feels like you have a better handle than I do.
Posted Oct 17, 2017 15:50 UTC (Tue)
by ballombe (subscriber, #9523)
[Link] (6 responses)
The fact is that just knowing that the (public) modulus is in some congruence class tell you nothing useful about its factors (there is no new information).
So it is reasonable to expect that they found that the (private) prime factors themselves are in some know congruence classes. If the classes are narrow enough and there is not too many to try, Coppersmith algorithm will recovers p and q.
A procedure that perform a check on the private keys is very impractical, so they had to restrict themselves to the public modulus.
So my expectation is that they generated the bitmask for the modulus from the bitmask for p and q with a loop like:
input: l a small prime and the corresponding bitmask M for p and q:
so they get a bitmask for the modulus and did not bother to remove cases where it is just the complement of 1. (this would just increase likelihood of bugs without any real benefit)
Note that the bitmask Mm has much more bits set than the original bitmask for p, so the test is much less accurate, even without taking account that each product mod l can be realized with l-1 different ways.
Posted Oct 17, 2017 16:39 UTC (Tue)
by tialaramex (subscriber, #21167)
[Link] (5 responses)
It's possible I have information that you don't because I have been staring at this for over 24 hours now.
FIMU-RS-2016-03-1, the technical report Svenda and co. wrote last year summarises the knowledge that's now in these bitmasks. See Table 6 on page 33 for the start of the data, and then the text beneath explains that the pattern continues and how.
In 2016, this was just a curiosity. The Infineon device had this unexpected behaviour, but it was not common in the wild and so the main paper (which you're more likely to have seen and is shorter, the technical report is listed in its bibliography) just shrugs and moves on without even actually using it. But they did know about it, they wrote it up in the technical report where there was space. The fingerprinting code they showcased in 2016 doesn't even use these bitmasks because it wasn't central to the thrust of the paper, but the information they're based on is right there in the report eighteen months ago.
So, although your algorithm is possible, it certainly wasn't necessary for the authors to implement it, they had a table of these same patterns already.
Posted Oct 17, 2017 17:18 UTC (Tue)
by ballombe (subscriber, #9523)
[Link] (4 responses)
In the report they focus from identification from public key alone and the largest pattern they report is modulo 157 and yet they check primes 163 and 167.
This suggests they wrote the program from the knowledge of the implementation, and not from the patterns list.
I might be totally wrong, of course.
However anybody able to generate private keys with Infineon device and able to read them should be able to tell (just generate 100 keys and check whether p and q are generic modulo primes from 3 to 167).
Not that Coppersmith attack I mention is not the 'small exponent' attack but 'the known bits attack' (extended to arbitrary bases).
Posted Oct 18, 2017 14:20 UTC (Wed)
by tialaramex (subscriber, #21167)
[Link] (3 responses)
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?
.set Mm to 0
.for i=0 to l do:
...for j = 0 to l do:
.....if bit i of M is set and bit j of M is set then:
.......set bit (i+j) mod p of Mm
output: Mm
_How_ many false positives?
_How_ many false positives?
_How_ many false positives?
_How_ many false positives?
Also I expect this actually holds for both prime factors.
_How_ many false positives?
_How_ many false positives?