Millions of high-security crypto keys crippled by newly discovered flaw (Ars Technica)
While all keys generated with the library are much weaker than they should be, it's not currently practical to factorize all of them. For example, 3072-bit and 4096-bit keys aren't practically factorable. But oddly enough, the theoretically stronger, longer 4096-bit key is much weaker than the 3072-bit key and may fall within the reach of a practical (although costly) factorization if the researchers' method improves. To spare time and cost, attackers can first test a public key to see if it's vulnerable to the attack. The test is inexpensive, requires less than 1 millisecond, and its creators believe it produces practically zero false positives and zero false negatives. The fingerprinting allows attackers to expend effort only on keys that are practically factorizable. The researchers have already used the method successfully to identify weak keys, and they have provided a tool here to test if a given key was generated using the faulty library. A blog post with more details is here."
Posted Oct 16, 2017 15:49 UTC (Mon)
by danielpf (guest, #4723)
[Link] (6 responses)
Posted Oct 16, 2017 16:08 UTC (Mon)
by clump (subscriber, #27801)
[Link] (2 responses)
Posted Oct 16, 2017 18:38 UTC (Mon)
by flussence (guest, #85566)
[Link] (1 responses)
Posted Oct 16, 2017 22:30 UTC (Mon)
by DOT (subscriber, #58786)
[Link]
Posted Oct 16, 2017 16:23 UTC (Mon)
by excors (subscriber, #95769)
[Link] (1 responses)
> Our work highlights the dangers of keeping the design secret and the implementation closed-source, even if both are thoroughly analyzed and certified by experts. The lack of public information causes a delay in the discovery of flaws (and hinders the process of checking for them), thereby increasing the number of already deployed and affected devices at the time of detection.
Posted Oct 17, 2017 6:32 UTC (Tue)
by jem (subscriber, #24231)
[Link]
Posted Oct 17, 2017 6:13 UTC (Tue)
by jem (subscriber, #24231)
[Link]
Posted Oct 16, 2017 16:40 UTC (Mon)
by daves (guest, #109019)
[Link] (4 responses)
I've sent a notice to those key owners.
Posted Oct 16, 2017 18:22 UTC (Mon)
by sgourichon (guest, #88605)
[Link]
Good action!
Posted Oct 16, 2017 18:24 UTC (Mon)
by gwolf (subscriber, #14632)
[Link]
- Gunnar, from keyring-maint ☺
Posted Oct 17, 2017 14:08 UTC (Tue)
by N0NB (guest, #3407)
[Link] (1 responses)
Posted Oct 17, 2017 14:31 UTC (Tue)
by tialaramex (subscriber, #21167)
[Link]
It is anticipated that affected keys will be rarer in applications which are focused around general purpose computers acting as servers, such as the Web PKI ("SSL"); and more common where keys are associated with a human individual who might find it useful to embody them in a small device or token they can carry, such as PGP or S/MIME. But they could be found almost anywhere.
m.d.s.policy is currently discussing whether Public CAs have (or will have in November) a responsibility to reject requests from applicants for a certificate covering a public key that smells like Infineon generated it, as this key is presumably weak. Today CAs reject Debian Weak Keys, and certain other categories of key known to be bad choices or indicative of unsafe practices.
Posted Oct 16, 2017 18:26 UTC (Mon)
by tialaramex (subscriber, #21167)
[Link] (14 responses)
Here's what the fingerprint tool is doing (I just had to figure this out because @cpu over at Let's Encrypt almost had me persuaded this wasn't a thing and then I realised their understanding had caused me to misunderstand what I was reading)
Infineon's devices pick p and q (primes) for RSA in a strange way. We don't know exactly how, (maybe the researchers now have a good guess) but we do know this results in the modulus being unusual in a bunch of ways:
The easy one is this: Both p and q will be picked such that in binary they start 1100 and as a result the high byte of the modulus will be in a relatively small range. There's nothing wrong with that, necessarily, but it is _strange_. However, this difference would have a fairly high false positive rate, maybe 1-in-40 or something. So that's not what they're checking.
For small primes the RSA modulus is of course never exactly divisible (that would be fatal) but the remainder would be expected to be fairly uniformly distributed so that we couldn't guess what, say, M % 11 will be. For Infineon though, it's always either 1 or 10. Never 4 or 6 or any other number. So that's weird.
And the same applies for some (but not all) other small primes, in their 2016 paper they list enough to have only 1-in-480 false positive rate, this tool must do the same thing for many other primes. The question is, how many more, and what's the actual rate?
Posted Oct 16, 2017 19:24 UTC (Mon)
by ncm (guest, #165)
[Link] (13 responses)
The false negative rate is of more interest. We know of a subset of keys that are very likely bad, but we don't know if there are other bad keys. Bugs rarely travel alone. It would be prudent to invalidate *all* keys generated by this software, and obtain new keys by more trustworthy means.
Posted Oct 16, 2017 19:35 UTC (Mon)
by tialaramex (subscriber, #21167)
[Link]
For the original work they generated 100 000 key pairs, 100 000 values of M. In every case (M % 11) is either 1 or 10. Not "a lot of them", not "more than you'd expect", all of them.
The fingerprinting takes that, iterates it over all the primes (amusingly it does even ones like 5 or 7 for which there's nothing to discover I can't tell if that's an obfuscation or just a generalisation they felt wasn't important to optimise out) and gets out an answer with some very low false positive rate. I just haven't worked out the actual rate yet.
The fingerprinting identifies all keys from the affected devices. Some of those keys will be very, very bad, others are effectively not a problem unless there's a further breakthrough (which is equally true for, say, the OpenJava generated keys, or the OpenSSL keys, or any other source of keys) and the fingerprinting paints them all as bad, since we can't be sure and as you observe the right thing to do is discard them all.
Posted Oct 16, 2017 20:14 UTC (Mon)
by ballombe (subscriber, #9523)
[Link] (11 responses)
The check only looks at the public key. If your key is a false positive and you know the private key, you can prove to yourself your key is not suitable for the attack, but you cannot prove it to other party without revealing the private key.
Posted Oct 16, 2017 21:39 UTC (Mon)
by prometheanfire (subscriber, #65683)
[Link]
Posted Oct 17, 2017 8:43 UTC (Tue)
by tialaramex (subscriber, #21167)
[Link] (9 responses)
Can you? I'm not sure how. Maybe once the attack method is published this will be evident, but the fingerprinting doesn't care about anything beyond the public modulus. The provided offline check can process a private key, and it will simply discard everything except the (public) modulus and test that anyway.
In most cases if you're in possession of the private key you also know how it was generated. If it was generated in software on a general purpose computer, ie not an Infineon chip or some hardware that might plausibly be using the same approach then it's safe.
It is reasonable to suppose that this is true EVEN IF it happens that your OpenSSL (or whatever) has coincidentally picked a modulus which could plausibly have been picked by Infineon's library. That's because it would be _very_ strange if RSA has secretly had a category of extra weak keys we knew nothing about, rather than Infineon screwing up in a way that makes the values of p and q more guessable than expected. The latter just opens Infineon up to a category of attack in which partial knowledge of the private key can be expanded into full knowledge at a proportional cost, if you know four bits of the private key it's not much help, four hundred goes a long way and so on. The former would be a significant cryptographic breakthrough, thus, it's much less likely that's what will be published in November.
In follow-up to my original question: On top of the 1-in-480 from the 2016 paper this new work uses 12 extra small primes - assuming they're each 50% accurate for distinguishing keys that's about 1-in-2million false positives. If they're more diagnostic (as the small prime 11 is with only 1-in-5 false positives on its own) it could be a much lower rate. This seems acceptable, likely a few dozen people around the world at most will be inconvenienced, a small price for fixing what may be a serious bug.
Posted Oct 17, 2017 11:05 UTC (Tue)
by ballombe (subscriber, #9523)
[Link] (8 responses)
Given the hints available (the code, the reference to Coppersmith), it looks like that both p and q belong to some congruence classes modulo the small primes.
If p and q are in the right classes, then the corresponding instance of Coppersmith algorithm will factor p*q independently of how the key was generated.
Posted Oct 17, 2017 14:20 UTC (Tue)
by tialaramex (subscriber, #21167)
[Link] (7 responses)
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.
Posted Oct 16, 2017 19:17 UTC (Mon)
by alonz (subscriber, #815)
[Link] (2 responses)
Posted Oct 17, 2017 14:14 UTC (Tue)
by david.a.wheeler (subscriber, #72896)
[Link] (1 responses)
Posted Oct 18, 2017 11:07 UTC (Wed)
by hkario (subscriber, #94864)
[Link]
Posted Oct 17, 2017 16:27 UTC (Tue)
by tialaramex (subscriber, #21167)
[Link]
I can't read German and the translation (?) is mangled sufficiently badly that it casts almost as much shadow as light, but this is clearly a Fast Primality invention, patented by Infineon in the right period. The "invention" is a technique for picking several prime numbers but sharing the work so that effort expended isn't proportional to the number of primes found. The confusing language combined with my lack of specialist knowledge [I know roughly what Miller-Rabin is, but I couldn't implement it without a proper explanation to crib from] means I don't know exactly how they do this, but it's pretty obvious that a good RSA private key has primes p, q unrelated except for the fact that they're roughly the same size. Two primes produced in the manner described are surely related and thus unsuitable for a private key.
Am I wrong? Is it somehow OK to have an algorithm that picks related primes and then use them for p, q ?
The ROCA site is adamant that this isn't just "smart cards have crappy RNGs" again, and indeed they go out of their way to say the chips don't have a problem (so far as they know) for ECC key generation where the same card offers both. That puts the code for picking primes square in the focus, because that's one of the few things you could get wrong and not notice if the RNGs work and your adjacent ECC key generator works too.
Millions of high-security crypto keys crippled by newly discovered flaw (Ars Technica)
Millions of high-security crypto keys crippled by newly discovered flaw (Ars Technica)
Millions of high-security crypto keys crippled by newly discovered flaw (Ars Technica)
Millions of high-security crypto keys crippled by newly discovered flaw (Ars Technica)
Millions of high-security crypto keys crippled by newly discovered flaw (Ars Technica)
I don't think any other industry is more paranoid about open information than the digital security industry. Security processors aren't even mentioned in data catalogs, and when they are the information is very sparse. See for instance this Maxim DS2436 Secure Coprocessor. Without signing an NDA you get only an abridged data sheet that tells you in broad terms what the chip can do, but nothing about the internals, not even how you talk to the chip. Even the current consumption is a secret.
Millions of high-security crypto keys crippled by newly discovered flaw (Ars Technica)
Millions of high-security crypto keys crippled by newly discovered flaw (Ars Technica)
Millions of high-security crypto keys crippled by newly discovered flaw (Ars Technica)
Millions of high-security crypto keys crippled by newly discovered flaw (Ars Technica)
Millions of high-security crypto keys crippled by newly discovered flaw (Ars Technica)
Millions of high-security crypto keys crippled by newly discovered flaw (Ars Technica)
Millions of high-security crypto keys crippled by newly discovered flaw (Ars Technica)
_How_ many false positives?
_How_ many false positives?
_How_ many false positives?
_How_ many false positives?
If the false positive rate was 10%, then invalidating false positive would destroy the web of trust.
_How_ many false positives?
_How_ many false positives?
> you can prove to yourself your key is not suitable for the attack
_How_ many false positives?
If you know p and q, you can check if this is true.
If you only know p*q, then you can check if p*q belongs to one of the possible product of congruences classes, but it is a less accurate check (the number of possibility get squared).
(at least, this explains why half the tests done in the fingerprinting code are useless).
_How_ many false positives?
_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?
I wonder if this will impact industry perception of the certification bodies that evaluated this library (or even the Common Criteria EAL processes themselves)?
Millions of high-security crypto keys crippled by newly discovered flaw (Ars Technica)
The Infineon library was supposedly evaluated for compliance to Common Criteria EAL5, which was supposed to prevent such issues…
Millions of high-security crypto keys crippled by newly discovered flaw (Ars Technica)
Millions of high-security crypto keys crippled by newly discovered flaw (Ars Technica)
Millions of high-security crypto keys crippled by newly discovered flaw (Ars Technica)