[Cryptography] Millions of high-security crypto keys crippled by newly discovered flaw

[John Gilmore]

Today's revelation that Infineon "Trusted Platform Module" TPM chips
produce insecure RSA keys has a bright side.  Those chips were largely
created for Internet-based DRM schemes.  It means that it should be
possible to take a public key generated by such a TPM chip, factor it
to produce the matching private key, and then break the DRM by signing
or "attesting" to any damn thing the corporate mothership wants to
hear.

The mothership won't be able to disable all the TPM-created keys, since
that would force them to deny service to ALL their customers.

Hmm, I wonder if Infineon TPMs contain the broken library burned into
ROM or flash, or whether they get the library loaded from the system
they are securing.  Presumably if the library is loaded from the
outside, it's signed, and the signature is checked, so that you can't
just load ANY old library into it.  Was it signed with a TPM-generated
RSA key, perhaps?  Shall we find the matching private key?  :-)

Is this sort of scheme used to force registration of Microsoft OS's,
perhaps?  Or require that modern x86 tablets can only boot Microsoft
OS's?  Or secure Blu-Ray drives, maybe?  Howabout that
turncoat-Tim-Berners-Lee-approved DRM-for-websites that the quislings
at Mozilla have already secretly rolled out by having "free software"
Firefox quietly download, install and run a secret proprietary binary
plugin after you install it?

Let's have some fun.

	John

PS:  I don't need to point out to THIS audience the irony in the
"Trusted" platform module that nobody can actually trust (or verify).
We've been complaining about that for a decade or more.

PPS: The essence of the test for broken keys is a list of primes and a
list of remainder masks.  "git clone
https://github.com/crocs-muni/roca" and examine roca/roca/detect.py:

Here's the test:

        for i in range(0, len(self.primes)):
            if (1 << (modulus % self.primes[i])) & self.prints[i] == 0:
                return False

        self.primes = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101,
                       103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167]

        self.prints = [6, 30, 126, 1026, 5658, 107286, 199410, 8388606, 536870910, 2147483646, 67109890, 2199023255550,
                       8796093022206, 140737488355326, 5310023542746834, 576460752303423486, 1455791217086302986,
                       147573952589676412926, 20052041432995567486, 6041388139249378920330, 207530445072488465666,
                       9671406556917033397649406,
                       618970019642690137449562110,
                       79228162521181866724264247298,
                       2535301200456458802993406410750,
                       1760368345969468176824550810518,
                       50079290986288516948354744811034,
                       473022961816146413042658758988474,
                       10384593717069655257060992658440190,
                       144390480366845522447407333004847678774,
                       2722258935367507707706996859454145691646,
                       174224571863520493293247799005065324265470,
                       696898287454081973172991196020261297061886,
                       713623846352979940529142984724747568191373310,
                       1800793591454480341970779146165214289059119882,
                       126304807362733370595828809000324029340048915994,
                       11692013098647223345629478661730264157247460343806,
                       187072209578355573530071658587684226515959365500926]
  
So you divide the RSA public key by this set of small primes, and
examine the remainder.  If the bit in the matching "prints" number that
matches the remainder is on, the key is not vulnerable.  If any of the
remainders indexes a bit that's zero, the key is vulnerable.

All the "prints" numbers are even, i.e. their low order bit is zero:
if the remainder when dividing by any small prime is zero, then, ahem,
the number is easy to factor!

What does this tell us about how the keys were poorly generated, and
what does it tell us about how to factor them?  (We'll find out in
early November, but we might as well think about it.)