Simplify/optimize/deobfuscate checker code

[marcan]

The core of the key checker seems to be written in an oddly obtuse way for some reason, including some tests that are redundant. Specifically, the only primes that matter are 11,13,17,19,37,53,61,71,73,79,97,103,107,109,127,151,157. The others have check bitmasks that are all 1s (except for bit 0 = residue 0), which pass for all RSA keys (unless they have a small prime factor, but then you have bigger issues to worry about than the Infineon bug).

For some reason the bitmasks are expressed as decimal numbers (instead of hex or binary), which further obfuscates their meaning. These masks apparently have been generated from a simpler relation of the form n ^ r mod p = 1 for a prime p and a small exponent r, as documented here.

I've written a simpler implementation which omits the useless entries and directly computes the sets of indicator residues from the simpler relation, using more Pythonic constructs (sets instead of bitmasks). I think something along these lines would make more sense than the current code, and it is also ~3 times faster.

[ph4r05]

Mathematical fingerprinting won't be published until CCS 2017 takes place in (2.11.2017) :)

Till then the detection mechanism is "no comment" including any optimizations which may leak not yet published information.

[marcan]

Kind of sad seeing serious academic researchers somehow believe that security through obscurity (and a 3x slowdown) is worth anything. Oh well.

[mimoo]

@marcan "security through obscurity" usually refers to the building of cryptographic primitives and their testing. The sentence is sometimes also referred as something along the lines "in a cryptographic algorithm, only the secret key should not be known".

When it comes to security, obscurity (obfuscation & co) does help/slow down attacks. We often include it in "defense in depth".

When it comes to disclosure and security updates, obfuscation (and encryption of updates) is also a thing. I don't think it is good to shame academic researchers who have decided to open source their code.

[marcan]

It is. They believe the security of their research results is helped by obfuscating the checker code to hinder people trying to understand it ahead of the conference. Obfuscation is always security through obscurity.

Edit: the prior comment by mimoo used to just say (paraphrasing) "That isn't what security through obscurity means". His subsequent edit has made this comment appear out of context.

[mimoo]

How would de-obfuscating the code help the security here (rather than the bad guyz™)? Correct me if I'm wrong:

• isn't the vulnerability only fixable on the vendor side (and the vendors have been warned).
• isn't there nothing more that can be done for third-parties but to check if the keys are impacted (and these scripts help).

Thanks!

[marcan]

You're mixing together a bunch of different things. Removing security through obscurity doesn't help security. Security through obscurity doesn't hurt security either. It's just useless.

The "security" we're talking about here isn't the actual Infineon problem, it's the "security" problem of "we don't want anyone to guess our method before the conference".

The only thing this obfuscation accomplishes is confusing people who can't see through this kind of BS as quickly as experienced reverse engineers can, increase the chance of bugs, reduce performance, and look ugly. This applies to everyone trying to incorporate that code to detect vulnerable keys (like CAs like Let's Encrypt, which are using a Go port of this code). And it annoys people. Security researchers should know better than to try such a trivial, petty obfuscation for silly reasons.

Besides, since I already posted the optimized/deobfuscated version, and it's trivially provably equivalent, this whole exercise is pointless. There's no reason not to use the better code now, instead of waiting until the results are published.

[marcan]

To give another angle, the phrase "any optimizations which may leak not yet published information" is an oxymoron. If you think any kind of optimization may leak not yet published information, you're doing it wrong. If the code accomplishes the same thing and was derived from the original then by definition it does not leak any (additional) information. And if the code is out there, which it is because I wrote it and linked to it, then by definition incorporating it doesn't leak anything because if there were anything to leak, it's already leaked.

[ph4r05]

3x slowdown:

• at the moment this is not pain for us as the fingerprinting runs quite fast even on large datasets.
• I did not inspect your code in depth. I did not verify your claims on the effectivity so I cannot confirm or reject claims it works in the same way as our code and I won't get to that till conf.
• till 2.11.2017 there is no modification of the code planed. Take it as it is. Feel free to use any versions you like. Thanks for the contribution
• using decimal constants instead of hex can hardly be called "obfuscation"
• if you want to contribute with more effective detection algorithm do that please with PR.

We published detection tool that works quite reasonably, 2 weeks before conference so people can check the vulnerability of their own keys. Code is very simple and easily portable to many other languages (again, "obfuscation", really?). We did that without revealing too much mathematical details before the conference takes place. I mean the real math structure not some code optimizations. And obviously it works as we didn't notice the general structure being reverse engineered by the general public - your code does not reveal it either. If you call the sub-optimality of the detection code "obfuscation" then be it. We don't deny an existence of potentially faster detection tool. Yours can be better.

We don't have time resources for discussions like this at the moment. I consider this discussion done.

More details will be available on the conference. Stay tuned.

[marcan]

If there was no deliberate obfuscation involved, I have one question: where did the 21 red herring (all-1 constants except for bit 0) tests come from? Of the 38 entries, only 17 actually do anything. Using decimal constants instead of hex/binary for what actually are sets of integers encoded as a mask (which is already nonstandard in Python, as it has a perfectly good set type) is definitely, well, at best a really strange choice unlikely to be made by accident.

Either way, I'll send a PR and you can take it or leave it.

[marcan]

PR: #40

[marcan]

And obviously it works as we didn't notice the general structure being reverse engineered by the general public

I'll just leave this here: https://twitter.com/jix_/status/925129065715126273

Turns out it didn't work - someone figured out what you were doing and implemented it before the conference. I suggest avoiding obfuscation next time. That stuff tends to motivate people into reverse engineering your approach instead of slowing them down ;)

[ph4r05]

@marcan Our paper was made publicly available on 30.10 by ACM (the tweet date), conference started today.

I like the community involvement, nobody wants to slow them down. But as I said - I didn't saw the mathematical prime structure being published prior our article went out. So in our perspective it worked perfectly. We released detection tool, give people time to assess vulnerability of the keys and keeping potential attackers from easy attack manual. Works for us ;)

[marcan]

The above factoring was accomplished without reference to the (now) publicly available paper. Obviously someone didn't implement your approach without a reference the same day, work had started earlier.

[ph4r05]

Looking forward to seeing an another independent implementation of the ROCA attack! That is exciting. We already wait for DJB write up:
https://twitter.com/hashbreaker/status/922229745454022656