Efficient test for weak RSA keys generated in Infineon TPMs / smartcards

1310 views
Skip to first unread message

Matthew Hardeman

unread,
Oct 16, 2017, 3:01:40 PM10/16/17
to mozilla-dev-s...@lists.mozilla.org
The authors of the paper on the weak RSA keys generated by Infineon TPMs and smart cards have published code in multiple languages / platforms that provide for an efficient test for weakness by way of the Infineon TPM bug.

Perhaps this should be a category of issue identified by the crt.sh engine, etc?

Should someone put together a ballot for incorporating this category of weak keys as a mandatory check before issuing certs?

Code for testing keys is at: https://github.com/crocs-muni/roca

It looks like the test is exceptionally easy math against the modulus of the public key.

Thanks,

Matt Hardeman

Rob Stradling

unread,
Oct 16, 2017, 4:15:10 PM10/16/17
to dev-secur...@lists.mozilla.org
On 16/10/17 20:01, Matthew Hardeman via dev-security-policy wrote:
> The authors of the paper on the weak RSA keys generated by Infineon TPMs and smart cards have published code in multiple languages / platforms that provide for an efficient test for weakness by way of the Infineon TPM bug.
>
> Perhaps this should be a category of issue identified by the crt.sh engine, etc?

Hi Matt. Yeah, I'm working on adding the ROCA check to crt.sh.

> Should someone put together a ballot for incorporating this category of weak keys as a mandatory check before issuing certs?
>
> Code for testing keys is at: https://github.com/crocs-muni/roca
>
> It looks like the test is exceptionally easy math against the modulus of the public key.

--
Rob Stradling
Senior Research & Development Scientist
COMODO - Creating Trust Online

Jakob Bohm

unread,
Oct 16, 2017, 6:15:51 PM10/16/17
to mozilla-dev-s...@lists.mozilla.org
Unfortunately, as of right now, their github repository still doesn't
include the promised C/C++ implementation, and their Python
implementation requires a fairly new Python version (with details
inconsistent between README.md and a quick look at setup.py).

They have also obfuscated their test by providing bitmasks as decimal
bigints instead of using hexadecimal or any other format that makes the
bitmasks human readable.

But if you happen to run a new enough environment, their tests may at
least be runable, and you may be able to deobfuscate the bitmasks with
your favorite bignum calculator.


Enjoy

Jakob
--
Jakob Bohm, CIO, Partner, WiseMo A/S. https://www.wisemo.com
Transformervej 29, 2860 Søborg, Denmark. Direct +45 31 13 16 10
This public discussion message is non-binding and may contain errors.
WiseMo - Remote Service Management for PCs, Phones and Embedded

Matt Palmer

unread,
Oct 16, 2017, 9:16:55 PM10/16/17
to dev-secur...@lists.mozilla.org
On Mon, Oct 16, 2017 at 09:14:29PM +0100, Rob Stradling via dev-security-policy wrote:
> On 16/10/17 20:01, Matthew Hardeman via dev-security-policy wrote:
> > The authors of the paper on the weak RSA keys generated by Infineon TPMs and smart cards have published code in multiple languages / platforms that provide for an efficient test for weakness by way of the Infineon TPM bug.
> >
> > Perhaps this should be a category of issue identified by the crt.sh engine, etc?
>
> Hi Matt. Yeah, I'm working on adding the ROCA check to crt.sh.

Whoops, didn't see this before I submitted
https://github.com/awslabs/certlint/pull/55.

- Matt

Nick Lamb

unread,
Oct 17, 2017, 7:36:59 AM10/17/17
to mozilla-dev-s...@lists.mozilla.org
On Monday, 16 October 2017 23:15:51 UTC+1, Jakob Bohm wrote:
> They have also obfuscated their test by providing bitmasks as decimal
> bigints instead of using hexadecimal or any other format that makes the
> bitmasks human readable.

The essential fingerprinting trick comes down to this (I had to work all this out while I was discussing it with Let's Encrypt's @cpu yesterday):

Infineon RSA moduli have weird properties, when you divide them by some (but not all) small primes the remainder isn't zero (which would be instantly fatal to security) but is heavily biased. For example when divided by 11 the remainder is always 1 or 10.

The bitmasks are effectively lists of expected remainders for each small prime, if your modulus has an expected remainder for all the 20+ small primes that distinguish Infineon, there's a very high chance it was generated using their hardware, although it isn't impossible that it was selected by other means. The authors could give firm numbers but I have estimated the false positive rate as no more than 1-in 2 million. If any of the remainders are "wrong" then your keys weren't generated using this Infineon library, there is no "false negative" rate.

I believe the November paper will _not_ announce a new category of RSA weak keys, but instead will describe how to get better than chance rates of guessing RSA private key bits from the public modulus _if_ the key was generated using Infineon's library. Such knowledge can be leveraged into a cost effective attack using existing known techniques.

Tim Hollebeek

unread,
Oct 17, 2017, 9:48:50 AM10/17/17
to Nick Lamb, mozilla-dev-s...@lists.mozilla.org
I think this is right. ROCA-detect appears to just be an implementation of the fingerprinting algorithm described in the 2016 paper (https://www.usenix.org/system/files/conference/usenixsecurity16/sec16_paper_svenda.pdf). There are already plenty of clues in the 2016 paper that something might be wrong with Infineon's prime selection algorithm. It will be interesting to see what the actual attack is.

Fun quotes from the 2016 paper:

"It is possible to verify ... whether the primes generally do not exhibit same distribution as randomly generated numbers (Infineon JTOP 80K) by computing the distributions of the primes, modulo small primes."

On the factorization of p-1:

"The Infineon JTOP 80K card produces significantly more small factors than usual (compared with both random numbers and other
sources)."

On biases in the random number generator:

" The Infineon JTOP 80K failed the NIST STS Approximate Entropy test (85/100, expected entropy contained in the data) at a significant level and also failed the group of Serial tests from the Dieharder suite (39/100, frequency of overlapping n-bit patterns). Interestingly, the serial tests began to fail only for patterns with lengths of 9 bits and longer (lengths of up to 16 bits were tested), suggesting a correlation between two consecutive random bytes generated by the TRNG."

This is pure speculation on my part, but I'm wondering if they also used the classic smart card "optimization" of using 3 for the public exponent. That would make it easier to exploit biases in selection of primes.

-Tim

-----Original Message-----
From: dev-security-policy [mailto:dev-security-policy-bounces+thollebeek=trustw...@lists.mozilla.org] On Behalf Of Nick Lamb via dev-security-policy
Sent: Tuesday, October 17, 2017 7:37 AM
To: mozilla-dev-s...@lists.mozilla.org
Subject: Re: Efficient test for weak RSA keys generated in Infineon TPMs / smartcards

On Monday, 16 October 2017 23:15:51 UTC+1, Jakob Bohm wrote:
> They have also obfuscated their test by providing bitmasks as decimal
> bigints instead of using hexadecimal or any other format that makes
> the bitmasks human readable.

The essential fingerprinting trick comes down to this (I had to work all this out while I was discussing it with Let's Encrypt's @cpu yesterday):

Infineon RSA moduli have weird properties, when you divide them by some (but not all) small primes the remainder isn't zero (which would be instantly fatal to security) but is heavily biased. For example when divided by 11 the remainder is always 1 or 10.

The bitmasks are effectively lists of expected remainders for each small prime, if your modulus has an expected remainder for all the 20+ small primes that distinguish Infineon, there's a very high chance it was generated using their hardware, although it isn't impossible that it was selected by other means. The authors could give firm numbers but I have estimated the false positive rate as no more than 1-in 2 million. If any of the remainders are "wrong" then your keys weren't generated using this Infineon library, there is no "false negative" rate.

I believe the November paper will _not_ announce a new category of RSA weak keys, but instead will describe how to get better than chance rates of guessing RSA private key bits from the public modulus _if_ the key was generated using Infineon's library. Such knowledge can be leveraged into a cost effective attack using existing known techniques.
_______________________________________________
dev-security-policy mailing list
dev-secur...@lists.mozilla.org
https://scanmail.trustwave.com/?c=4062&d=3Ovl2apWfmmNe_UweJVlyoLYW7IcTt8TvAsvArum1g&s=5&u=https%3a%2f%2flists%2emozilla%2eorg%2flistinfo%2fdev-security-policy

Rob Stradling

unread,
Oct 17, 2017, 9:50:18 AM10/17/17
to Jakob Bohm, mozilla-dev-s...@lists.mozilla.org
On 16/10/17 23:15, Jakob Bohm via dev-security-policy wrote:
<snip>
> Unfortunately, as of right now, their github repository still doesn't
> include the promised C/C++ implementation,

Hi Jakob. Today I ended up rewriting the ROCA fingerprint checker in C
(using OpenSSL BIGNUM calls) to get it working in crt.sh. In case it's
useful, here's a Gist:

https://gist.github.com/robstradling/f525d423c79690b72e650e2ad38a161d

Build it with -lcrypto and pipe a DER cert to STDIN.

Jonathan Rudenberg

unread,
Oct 17, 2017, 1:11:56 PM10/17/17
to Rob Stradling, mozilla-dev-s...@lists.mozilla.org, Jakob Bohm

> On Oct 17, 2017, at 09:49, Rob Stradling via dev-security-policy <dev-secur...@lists.mozilla.org> wrote:
>
> On 16/10/17 23:15, Jakob Bohm via dev-security-policy wrote:
> <snip>
>> Unfortunately, as of right now, their github repository still doesn't
>> include the promised C/C++ implementation,
>
> Hi Jakob. Today I ended up rewriting the ROCA fingerprint checker in C (using OpenSSL BIGNUM calls) to get it working in crt.sh. In case it's useful, here's a Gist:
>
> https://gist.github.com/robstradling/f525d423c79690b72e650e2ad38a161d

I just pushed an implementation written in Go that only uses standard library packages: https://github.com/titanous/rocacheck

Jonathan

Rob Stradling

unread,
Oct 18, 2017, 5:15:03 AM10/18/17
to mozilla-dev-s...@lists.mozilla.org
I've completed a full scan of the crt.sh DB, which found 171 certs with
ROCA fingerprints.

The list is at https://misissued.com/batch/28/

Many of these are Qualified/EUTL certs rather than anything to do with
the WebPKI. Only about half of them chain to roots that are trusted by NSS.

On 17/10/17 14:49, Rob Stradling via dev-security-policy wrote:
> On 16/10/17 23:15, Jakob Bohm via dev-security-policy wrote:
> <snip>
>> Unfortunately, as of right now, their github repository still doesn't
>> include the promised C/C++ implementation,
>
> Hi Jakob.  Today I ended up rewriting the ROCA fingerprint checker in C
> (using OpenSSL BIGNUM calls) to get it working in crt.sh.  In case it's
> useful, here's a Gist:
>
> https://gist.github.com/robstradling/f525d423c79690b72e650e2ad38a161d
>
Message has been deleted

Kim Nguyen

unread,
Oct 18, 2017, 3:30:25 PM10/18/17
to mozilla-dev-s...@lists.mozilla.org
Hi Rob, all,

we are treating this as an incident although all certs related to D-Trust are indeed Qualified/EUTL certs governed by National German Law and are not chaining up to roots that trusted by NSS, hence are not related to the WekbPKI. An incident report will be submitted by tomorrow noon (Thursday, 2017/10/19, German time).

None of the systems used within D-Trust to operate WebPKI CAs are affected by the weak RSA key generation topic reported today.

Kim Nguyen, D-Trust

Erwann Abalea

unread,
Oct 19, 2017, 2:36:12 AM10/19/17
to mozilla-dev-s...@lists.mozilla.org
Estonian eID being affected, the 2 keys allowed to sign the Estonian TSL are weak. These are the only TSL signer keys vulnerable. This was notified yesterday.
(TSL is a list of Qualified trust service providers issued by every Member State, a list of Trust Anchors for eIDAS)

Nick Lamb

unread,
Oct 19, 2017, 4:30:53 AM10/19/17
to mozilla-dev-s...@lists.mozilla.org
On Wednesday, 18 October 2017 10:15:03 UTC+1, Rob Stradling wrote:
> I've completed a full scan of the crt.sh DB, which found 171 certs with
> ROCA fingerprints.
>
> The list is at https://misissued.com/batch/28/
>
> Many of these are Qualified/EUTL certs rather than anything to do with
> the WebPKI. Only about half of them chain to roots that are trusted by NSS.

I have been looking mainly at those certificates which seem like they might be accepted by plausible Web PKI clients (say, curl for example) regardless of their root.

Several have a property that passes the Infineon fingerprint test as written but I believe it's as a result of some other (even worse?) flaw in the actual key generation method used for these keys. The ones that most confused me have M mod p = 1 for all small primes p. The odds against that happening by chance with fair random candidates are astronomical. I am pretty sure they aren't from Infineon devices because earlier work showed the Infineon key gen process gives a very narrow range of Most Significant Bytes for the modulus, and the strange moduli are outside that range.

For example: https://crt.sh/?id=13734110

Whatever is wrong with these keys it's separate from the Infineon issue.

Erwann Abalea

unread,
Oct 19, 2017, 9:09:02 AM10/19/17
to mozilla-dev-s...@lists.mozilla.org
Le mercredi 18 octobre 2017 11:15:03 UTC+2, Rob Stradling a écrit :
> I've completed a full scan of the crt.sh DB, which found 171 certs with
> ROCA fingerprints.
>
> The list is at https://misissued.com/batch/28/
>
> Many of these are Qualified/EUTL certs rather than anything to do with
> the WebPKI. Only about half of them chain to roots that are trusted by NSS.

Of all the Trust Anchors present in the German TSL and ROCA-fingerprinted (I've counted 79 certificates), 8 still have a "granted" status, the other ones have a "withdrawn" status.

Among the "granted" ones, 4 are 2048bits keys, 4 are 3072bits keys.

All the D-Trust affected services have been withdrawn on 25 September 2017.
22 of the other withdrawn services have been switched on 4 August 2017.

Hector Martin 'marcan'

unread,
Oct 20, 2017, 8:32:31 AM10/20/17
to Nick Lamb, mozilla-dev-s...@lists.mozilla.org
On 17/10/17 20:36, Nick Lamb via dev-security-policy wrote:
> The bitmasks are effectively lists of expected remainders for each small prime, if your modulus has an expected remainder for all the 20+ small primes that distinguish Infineon, there's a very high chance it was generated using their hardware

Yup, that seems to be it. In fact, according to [1], those lists are
just an optimization for the check N^r = 1 mod p for various values of
r,p (plus some dummy entries with all bits but bit 0 set to 1, which are
useless and apparently further obfuscation; they can be removed to speed
up the test with no effect on the outcome). I believe further tests can
be constructed following that same pattern to further reduce the false
positive rate.

Here's a non-obfuscated version of the modulus check without the
redundant entries:

https://mrcn.st/p/MOEoh2EH

(It's kind of sad seeing trivial obfuscation in a tool like this; come
on guys, this isn't going to slow anyone down, it's just makes you look
silly.)

FWIW, I tested 8 keys generated by affected Yubikeys and all failed the
test (as in were detected), so it seems this issue affects 100% of
generated keys, not just some fraction (or at least 100% of keys
generated on affected hardware are detected by the test tool regardless
of how vulnerable they are).

[1] https://crypto.stackexchange.com/questions/52292/what-is-fast-prime

--
Hector Martin "marcan"
Public key: https://mrcn.st/pub

Hanno Böck

unread,
Oct 20, 2017, 8:41:23 AM10/20/17
to dev-secur...@lists.mozilla.org, Rob Stradling
Hi,

For completeness:
I checked some of the eIDAS providers after this and I found a couple
of non-logged certificates that are also vulnerable. They don't seem to
chain up to any CA that is loggable by CT logs. But for completeness
I'll post them here.

These are the subjects:

C=DE, O=Deutscher Sparkassen Verlag GmbH, OU=ZDA mit Anbieterakkreditierung, CN=S-TRUST CA fuer qualifizierte Zertifikate 2014-01 1:PN
C=DE, O=Deutscher Sparkassen Verlag GmbH, OU=ZDA mit Anbieterakkreditierung, CN=S-TRUST CA fuer qualifizierte Zertifikate 2014-02 1:PN
C=DE, O=Deutscher Sparkassen Verlag GmbH, OU=ZDA mit Anbieterakkreditierung, CN=S-TRUST CA fuer qualifizierte Zertifikate 2014-03 1:PN
C=DE, O=Deutscher Sparkassen Verlag GmbH, OU=ZDA mit Anbieterakkreditierung, CN=S-TRUST CA fuer qualifizierte Zertifikate 2014-04 1:PN
C=DE, O=Deutsche Rentenversicherung, OU=QC Root CA, CN=DRV QC Root CA 2017a
C=DE, O=D-Trust GmbH, CN=D-TRUST akkr 2014 CRL 1 1:PN
C=DE, O=D-Trust GmbH, CN=D-TRUST akkr 2014 CRL 2 1:PN
C=DE, O=D-Trust GmbH, CN=D-TRUST akkr 2014 CRL 3 1:PN
C=DE, O=D-Trust GmbH, CN=D-TRUST akkr 2014 CRL 4 1:PN
C=DE, O=D-Trust GmbH, CN=D-TRUST akkr 2014 CRL 5 1:PN
C=DE, O=D-Trust GmbH, CN=D-TRUST akkr 2014 CRL 6 1:PN

I have no detailed knowledge what the exact usage of these certs is,
but some of it can be guessed based on the subjects.

--
Hanno Böck
https://hboeck.de/

mail/jabber: ha...@hboeck.de
GPG: FE73757FA60E4E21B937579FA5880072BBB51E42

Hector Martin 'marcan'

unread,
Oct 20, 2017, 9:16:55 AM10/20/17
to Hector Martin 'marcan', Nick Lamb, mozilla-dev-s...@lists.mozilla.org
On 20/10/17 21:31, Hector Martin 'marcan' via dev-security-policy wrote:
> Here's a non-obfuscated version of the modulus check without the
> redundant entries:
>
> https://mrcn.st/p/MOEoh2EH

Even simpler version, using the original relations directly (or
precalculating the same lists):

https://gist.github.com/marcan/fc87aa78085c2b6f979aefc73fdc381f
Reply all
Reply to author
Forward
0 new messages