[Crypto] SSL/TLS certificates survey (in wild) + (failed) RSA GCD attack in 2022

In summer 2022 I collected ~1,500,000 SSL/TLS certificates, fetching them from random hosts.

This is how:

openssl s_client -connect yurichev.com:443

OpenSSL can unpack all the info from base64-encoded cert:

openssl x509 -in 1 -text < cert

But I used Python"s cryptography.io library to process them all.

Now some statistics.

All certs: 1497463

1241697 RSA
 252936 EllipticCurve

As of RSA:
1119996 key_size= 2048
   7897 key_size= 3072
 113762 key_size= 4096
     35 key_size= 8192

So RSA-2k is still prevalent for TLS servers in 2022, not EC.

Who are popular issuers?

 769913 <Name(C=US,O=Let's Encrypt,CN=R3)>
 166729 <Name(C=US,O=Cloudflare\, Inc.,CN=Cloudflare Inc ECC CA-3)>
  81081 <Name(C=GB,ST=Greater Manchester,L=Salford,O=Sectigo Limited,CN=Sectigo RSA Domain Validation Secure Server CA)>
  67272 <Name(C=US,O=Amazon,OU=Server CA 1B,CN=Amazon)>
  51046 <Name(C=US,ST=TX,L=Houston,O=cPanel\, Inc.,CN=cPanel\, Inc. Certification Authority)>
  47041 <Name(C=US,ST=Arizona,L=Scottsdale,O=GoDaddy.com\, Inc.,OU=http://certs.godaddy.com/repository/,CN=Go Daddy Secure Certificate Authority - G2)>
  42186 <Name(C=US,O=DigiCert Inc,CN=DigiCert TLS RSA SHA256 2020 CA1)>
  31082 <Name(C=US,O=DigiCert Inc,OU=www.digicert.com,CN=Encryption Everywhere DV TLS CA - G1)>
  16682 <Name(C=US,O=Let's Encrypt,CN=E1)>
  15021 <Name(C=US,ST=Arizona,L=Scottsdale,O=Starfield Technologies\, Inc.,OU=http://certs.starfieldtech.com/repository/,CN=Starfield Secure Certificate Authority - G2)>
  14847 <Name(C=US,ST=MI,L=Ann Arbor,O=Internet2,OU=InCommon,CN=InCommon RSA Server CA)>
  13229 <Name(C=US,O=DigiCert Inc,CN=RapidSSL TLS DV RSA Mixed SHA256 2020 CA-1)>
  12023 <Name(C=JP,O=Cybertrust Japan Co.\, Ltd.,CN=Cybertrust Japan SureServer CA G4)>
  10467 <Name(C=US,O=Google Trust Services LLC,CN=GTS CA 1D4)>
  10310 <Name(C=US,O=DigiCert Inc,CN=DigiCert SHA2 Secure Server CA)>
   8926 <Name(C=NL,O=GEANT Vereniging,CN=GEANT OV RSA CA 4)>
   8891 <Name(C=GB,ST=Greater Manchester,L=Salford,O=Sectigo Limited,CN=Sectigo RSA Organization Validation Secure Server CA)>
   8742 <Name(C=BE,O=GlobalSign nv-sa,CN=AlphaSSL CA - SHA256 - G2)>
   6888 <Name(C=BE,O=GlobalSign nv-sa,CN=GlobalSign RSA OV SSL CA 2018)>
   6690 <Name(C=US,O=DigiCert Inc,OU=www.digicert.com,CN=GeoTrust RSA CA 2018)>
   6632 <Name(C=US,O=DigiCert Inc,CN=GeoTrust TLS DV RSA Mixed SHA256 2020 CA-1)>
   6507 <Name(C=AT,O=ZeroSSL,CN=ZeroSSL RSA Domain Secure Site CA)>
   6071 <Name(C=US,O=Entrust\, Inc.,OU=See www.entrust.net/legal-terms,OU=(c) 2012 Entrust\, Inc. - for authorized use only,CN=Entrust Certification Authority - L1K)>
   5411 <Name(C=US,O=DigiCert Inc,OU=www.digicert.com,CN=Thawte RSA CA 2018)>
   4842 <Name(C=BE,O=GlobalSign nv-sa,CN=GlobalSign GCC R3 DV TLS CA 2020)>
   4391 <Name(C=US,O=DigiCert Inc,OU=www.digicert.com,CN=DigiCert SHA2 Extended Validation Server CA)>
   4374 <Name(C=FR,ST=Paris,L=Paris,O=Gandi,CN=Gandi Standard SSL CA 2)>
   3287 <Name(C=US,O=DigiCert Inc,OU=www.digicert.com,CN=DigiCert SHA2 High Assurance Server CA)>
   3243 <Name(C=BE,O=GlobalSign nv-sa,CN=GlobalSign Atlas R3 DV TLS CA 2022 Q2)>
   3129 <Name(C=US,O=DigiCert Inc,CN=DigiCert TLS Hybrid ECC SHA384 2020 CA1)>
   2810 <Name(C=DE,O=Verein zur Foerderung eines Deutschen Forschungsnetzes e. V.,OU=DFN-PKI,CN=DFN-Verein Global Issuing CA)>
   2476 <Name(C=JP,O=Japan Registry Services Co.\, Ltd.,CN=JPRS Domain Validation Authority - G4)>
   2289 <Name(C=AT,O=ZeroSSL,CN=ZeroSSL ECC Domain Secure Site CA)>
   2195 <Name(C=US,O=DigiCert Inc,OU=www.digicert.com,CN=Thawte TLS RSA CA G1)>
   2127 <Name(C=BE,O=GlobalSign nv-sa,CN=GlobalSign Domain Validation CA - SHA256 - G3)>
   1792 <Name(C=PL,O=Unizeto Technologies S.A.,OU=Certum Certification Authority,CN=Certum Domain Validation CA SHA2)>
   1557 <Name(C=GB,ST=Greater Manchester,L=Salford,O=Sectigo Limited,CN=Sectigo RSA Extended Validation Secure Server CA)>
   1517 <Name(C=BE,O=GlobalSign nv-sa,CN=GlobalSign Atlas R3 DV TLS CA 2022 Q1)>

Full statistics

"Let"s Encrypt" is the most popular issuer.

RSA GCD attack

If a PRNG that generated factors is of low-quality or improperly seeded, it is possible that PRNG will genereate same factors from time to time. Even if running for different users.

And if first user generated p1, q1, second --- p2, q2, and q1=q2, GCD(p1*q1, p2*q2)=q1=q2. Then you can easily factor both moduli.

~10 years ago, when RSA-1k keys were prevalent, generated by faulty PRNGs, this was possible: 1, 2, 3, 4, 5, 6.

And so I tried this for RSA-2k certs I collected. Alas, no luck. Not a low-hanging fruit anymore.

If you think I'm wrong, and your kung fu is stronger than mine, these are: 891,190 unique RSA-2k moduli, in decimal form. (My first collection contained many duplicates, since one cert may be used for several websites.)

But the attack can be still feasible if you work with old RSA implementation with bad or improperly seeded PRNG. And if modulus is shorter (e.g., RSA-1k). And if you amassed a huge set of moduli. Or if you can generate random factors/moduli with faulty PRNG of the same version in the roughly same environment. But keep in mind that finding a pair of moduli with common factor is order of magnitude easier than finding a factor for a specific modulus, due to birthday problem/paradox.

Moral of the story: upgrade your software, take PRNG seriously.

(the post first published at 20220925.)

List of my other blog posts.

Yes, I know about these lousy Disqus ads. Please use adblocker. I would consider to subscribe to 'pro' version of Disqus if the signal/noise ratio in comments would be good enough.