RSA-512 Certificates abused in the wild

During recent weeks we have observed several interesting publications which have a direct relation to an investigation we worked on recently. On one hand there was a Certificate Authority being revoked by Mozilla, Microsoft and Google (Chrome), on the other hand there was the disclosure of a malware attack by Mikko Hypponen (FSecure) using a government issued certificate signed by the same Certificate Authority. That case however is not self-contained and a whole range of malicious software had been signed with valid certificates. The malicious software involved was used in targeted attacks focused on governments, political organizations and the defense industry. The big question is of course, what happened, and how did the attackers obtain access to these certificates? We will explain here in detail how the attackers have used known techniques to bypass the Microsoft Windows code signing security model.

Recently Mikko Hypponen wrote a blog on the F-Secure weblog detailing the discovery of a certificate used to sign in the wild malware. Specifically this malware was embedded in a PDF exploit and shipped in August 2011. Initially Mikko also believed the certificate was stolen, as that is very common in these days, with a large amount of malware families having support, or optional support, for stealing certificates from the infected system. Apparently someone Mikko spoke to mentioned something along the lines that it had been stolen a long time ago. During the symposium Mikko mentioned the certificate again, but now he mentioned that according to the people involved with investigating the case in Malaysia it likely wasn’t stolen.

The reason why Mikko looked at this specific sample and this certificate was likely the recent revocation of Digisign Server ID (Enrich) by Microsoft and earlier by Mozilla. The interesting part in those articles is that Microsoft does not mention anything about the code signing abilities of certificates while Mozilla does. Microsoft does mention that the certificates were not fraudulently issued but were duplicated due to cryptographically weak keys. The option of stolen certificates is left completely in the middle here.

The whole commotion around Digisign was actually caused by an investigation completed by Fox-IT in mid-October, in which we recovered a number of signed executables embedded in exploits and downloaded additionally by any of the executables. While our investigation did not focus on the signing of those executables, the report was shared in the relevant community, and if you looked at the 4 certificates initially found, it was easy to determine that all were 512bit RSA and used on HTTPS websites, which were still up at the time of writing. Later during our investigation we encountered 5 more certificates which also were used to successfully sign malware throughout 2011 by the same attacker, all 512 bit RSA.

So it is rather obvious what happened, all related RSA-512 keys had been factored and also abused to sign malicious software for the purpose of infiltrating high value targets. You might ask how difficult it is to execute an attack against RSA-512, well, over 12 years ago the RSA-512 challenge was successfully factored. Also we still encounter RSA-512 in protection systems deployed even today, with relatively modern hardware in a small cluster, relatively inexpensive, it takes a couple of weeks. With the lifetime of these certificates being a couple of years, the attackers had plenty of time to do the factoring.

So the reason why Digisign Server ID (Enrich)/DigiCert Sdn. Bhd, was revoked was because their certificates had no CRL in the certificate which allowed to easily revoke the certificate. Also all those certificates were issued without a purpose, in which case the certificates can be used for anything. The certificates we found to be used in the wild recently are:

  • (Digicert Sdn. Bhd.)
  • (Digicert Sdn. Bhd.)
  • (Digicert Sdn. Bhd.)
  • (Cybertrust)
  • (Cybertrust)
  • (Cybertrust)
  • (GlobalSign Inc)
  • (TAIWAN-CA.COM Inc.)
  • (Anthem Inc)

Additionally an external party found several other samples which contained 512 bit RSA certificates signed by Digicert Sdn. Bhd:

One of those samples was found in August 2010, and possibly used back in March 2010, indicating how long this issue has been going on without any clear action from the industry. Microsoft whose platform has been targeted by this is the victim of this, and I think that Microsoft should not have relied on weak security properties for a security solution that can apparently be bypassed by parties far outside of the control of Microsoft. Microsoft could simply deny verification of executables which have been signed with a 512bit RSA key after a certain date, as 512 bit RSA has been considered weak for a long time. From the article at TechNet it is clear that Microsoft understand the problem and that they have acted on this accordingly, but the question is if it was not a bit late. Also interesting is that none of the samples have an actual timestamp, we think this is another design decision made that makes these executables pass verification, but it might cause the executables to no longer pass verification after the certificate has expired, we were unable to test this however.

Also one certificate that was used,, did not have the “Digital Signature” property in “Key Usage”, thus it should not have passed verification. But we wonder if that indeed is true, as why would the attackers go through great lengths of factoring the RSA key and using it to sign their executables, if it did not pass verification? Either the attackers overlooked something here, or the digital signature verification system in Windows is at fault. We are however unable to verify this as the relevant certificate has expired in April 2011.

So the problem will solve itself eventually with CAs no longer signing 512 bit and more attention is given on the subject. The model of code signing certificates is however not very good as even the expensive code signing certificates can be stolen, and this can be done by simple off-the-shelf malware, such as ZeuS and SpyEye. But let’s focus on the issue at hand, how could we go about finding other certificates that might have been abused or could be abused, but that we do not have the executables from to prove it? Well someone already did all the work for us, that would be Peter Eckersly (EFF), Jesse Burns (iSec Partners) and Chris Palmer (EFF) who have worked in 2010 on EFF SSL Observatory that has indexed certificates used on port 443 (HTTPS). They have done presentations on this various times and we want to explicitly thank these guys for their hard work.

So we have used the database from mid-2010 which might be more close to the data the attackers had. So lets see, if we check the 9 certificates we have found being abused in the wild:

DigitalSignature Key Usage    Ext. Key Usage    RSA bits   Common Name
+                             -                 512
+                             -                 512
-                             -                 512
+                             -                 512
+                             -                 512
+                             -                 512
+                             -                 512
+                             -                 512
+                             -                 512
+                             -                 512
+                             -                 512

Bingo, they are all there, this is a good indication the people who found these certificates used a similar method to find these certificates, scanning port 443 (HTTPS) for valid 512 bit RSA certificates with no Extended Key Usage property defined and being usable. Note again that the has no Digital Signature Key Usage property.

Okay, so now let’s see what other certificates there are in the database from mid-2010 which match similar search criteria, that were valid according the the certificates from Microsoft at the time and have not expired yet.

Key Usage    Ext. Key Usage    RSA bits   Common Name                    Issuer
+            -                 512         GlobalSign nv-sa
+            -                 512               DigiNotar B.V.
+            -                 512  DigiNotar B.V.
+            -                 512           DigiNotar B.V.
+            -                 512          DigiNotar B.V.
+            -                 512  DigiNotar B.V.
+            -                 512           DigiNotar B.V.
+            -                 512          DigiNotar B.V.
+            -                 512             GlobalSign nv-sa
+            -                 512         GlobalSign nv-sa
+            -                 512          Digicert Sdn. Bhd.
+            -                 512           Digicert Sdn. Bhd.
+            -                 512    Cybertrust

Okay, we can find two certificates in there which we know that have been abused, specifically and, those have 512 bit RSA keys that have been factored. All other certificates seem to have been either revoked directly or indirectly, these are the ones related to DigiNotar and Digicert Sdn. Bhd/Digisign Server ID (Enrich). Others have been individually revoked after they have been replaced in the past. So, it looks like indeed the problem has been solved by revoking trust in Digicert Sdn. Bhd. and DigiNotar B.V. (unrelated) and revoking those specific certificates. We have not observed in the wild usage of other certificates such as the ones signed by DigiNotar, possibly there are other constraints which make it unusable for Code Signing. We will leave it as an exercise to the reader to inspect the other databases which the EFF SSL Observatory has created to find other certificates.

Concluding we can say that definitely there has been a lot of attention on Certificate Authorities and their procedures and also with several incidents such as the forging of data to match an md5 signature and the more recent DigiNotar incident. But this specific issue, while factoring is widely known, had not been addressed and has been used over a year for targeted break-ins of high value targets. While it has not been used for signing of drivers as far as we know, as was done with the stolen certificates used in the Stuxnet and Duqu attacks, it did play a part in the attacks we have observed and as such we think that letting the issue unaddressed for such a long time might have helped the attackers. It was trivial to find these certificates using published data by EFF and luckily it appears that all known certificates have now been revoked, but the question is if there are more certificates which have not been recorded in a database and have been, for example, used on other ports than HTTPS. The fact remains that the code signing mechanism is relying on trust in many parties which are not necessarily trusted, as human error and intentional or unintentional bypassing of procedures can break the entire security model.

Download the print version here.

Michael Sandee,
Principal Security Expert at Fox-IT

29 thoughts on “RSA-512 Certificates abused in the wild

    1. What you are proposing (and I cannot verify) is using a cloud service, which for these attackers would be a no go. Given their type of attack they left as little traces possible which led back to them. Also the executables were not equipped with a signed timestamp from a timestamp authority, likely because it leaves a trail, even it had much added benefit for the lifetime of these executables.

  1. What actual evidence is there that the attacker(s) really did factor the keys rather than just stealing them like everyone else does? I’ve seen this assertion in a few places, “they were 512-bit keys so they must have been factored”, but what actual evidence is there of this? Given the ease with which you can steal keys, why bother trying to factor them?

    1. From all the signed executables we found related to this attack all were exactly signed with a 512 bit RSA certificate and Mikko Hyponnen stated during the closing keynote that the certificate in Malaysia was explicitly not stolen. Since it is relatively cheap to factor a 512 bit RSA key it is the only plausible explanation, especially when looking at the variety of targets and they all being used HTTPS certificates. Stolen certs would exhibit more 1024 bit or higher keys and as our query finds 2 of the certificates which were still valid at the time we are pretty sure a similar method for HTTPS spidering and looking for weak keys that could be used for code signing was used by the attackers.

  2. …Couple of weeks to decode a few years ago.
    …30-48 hours now.

    If you make use of distributed computing, today’s multiprocessor computers, or better-yet, graphics cards with a lot of built-in co-processors, then it’s easily summarized that breaking into or cracking security like this becomes easier and quicker with time.

    This is a good article to “hopefully” get people aware/motivated to wake-up and move-up to bigger and harder to crack security.

  3. Mikko says this and Mikko says that. With all due respect to Mikko, I am sure that he has not spoken with anyone in Malaysia about this. Liar.

    “Apparently someone Mikko spoke to mentioned something along the lines that it had been stolen a long time ago. During the symposium Mikko mentioned the certificate again, but now he mentioned that according to the people involved with investigating the case in Malaysia it likely wasn’t stolen”

  4. How secure are the modern 2048-bit certificates when people have botnets with thousands of computers at their comnmand to crack them?

  5. Quentin: pretty safe. RSA-768 was factored in 2009, and “The effort took almost 2000 2.2GHz-Opteron-CPU years according to the submitters, just short of 3 years of calendar time.” and that is a single 768 number.

    So, do not worry about your 2048-bit keys until some more time passes.

    1. I wonder. Consider some malefactor using a botnet to crack it. With 100,000 or more computers – many with more than one core and most of which are considerably faster than the 2006- vintage Opterons – at their command, it might be quite quick, especially if they throttle it to not be too noticeable. That 3 years (1000 days?) quickly becomes 2 weeks. Haven’t there been reports of botnets that ‘don’t seem to be doing anything’?

      What is the overhead of using a significantly larger – say a 4k or 16k – key?

  6. Pingback: HitmanPro 3.6 «
  7. >> “We are however unable to verify this as the relevant certificate has expired in April 2011”

    Couldn’t you just “go back in time” on your workstation by adjusting the time and date? Seems all other checks are off anyway.

    1. Yeah, after I wrote the blog a colleague noticed me, kind of a slap in face moment. To date I haven’t though, will post a comment if I have.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s