• Arbitrations
• a20110312.1

• Case Number: a20110312.1
• Status: closed
• Claimants: Michael T. (CAcert Support) on behalf of Hanno B.
• Respondents: CAcert

• Initial Case Manager: BernhardFröhlich

• Case Manager: UlrichSchroeter

• Arbitrator: BernhardFröhlich

• Date of arbitration start: 2011-03-12
• Date of ruling: 2011-06-24
• Case closed: 2011-07-28
• Complaint: Weak CAcert certificates found in EFF SSL Observatory data
• Relief: Notify owners and revoke certificates

Before: Arbitrator BernhardFröhlich (A), Respondent: CAcert (R), Claimant: Michael T. (C), Case: a20110312.1

History Log

• 2011-03-12 (Support) Original filing in Dispute Mailing List

• 2011-03-12 (iCM): added to wiki, request for CM / A
• 2011-03-12 (A): I'll take either care about this case as (CM) or (A)
• 2011-03-12 (CM): I'll take either care about this case as (CM)
• 2011-03-12 (A): Sent mail with some technical questions to C.
• 2011-03-12 (C): 1st response to questions of (A)
• 2011-03-12 (A): First intermediate ruling given.
• 2011-03-12 (A): Sent roadmap of further actions. First issue is to find the weak certificates/keys, notify their owners and then revoke them. The second issue is to modify the software that weak keys are not accepted any more in the future.
• 2011-03-12 (C): accepts CCA/DRP, answer to (A)'s roadmap, first results
• 2011-03-13 (Peter): will prepare info text for mailing
• 2011-03-13 (A): quick test for Client certs with IE on Win7
• 2011-03-13 (C): progress report on analyze
• 2011-03-13 (C): response to IE on Win7 quick test
• 2011-03-13 (Alexander P): openssl commandline suggestion
• 2011-03-13 (A): proposal: details of technical implementation as not relevant for the Arbitration, so no addtl. archival
• 2011-03-13 (CM): Aye on (A) proposal
• 2011-03-17 (A): proposal for extracting infos
• 2011-03-18 (C): Dirk can probably review the Perl patch, question regarding installing the openssl-blacklist and openssl-blacklist-extra packages
• 2011-03-19 (Critical Admin): packages are installed with Lenny
• 2011-03-19 (A): req for manpage/documentation of openssl-vulnkey
• 2011-03-20 (C): statement/response
• 2011-03-20 (C): statement/response #2
• 2011-03-20 (Critical Admin): statement/response #2
• 2011-03-21 (C): statement/response #3
• 2011-03-26 (A): statement/response #3
• 2011-03-28 (C): statement/response #4
• 2011-03-28 (A): statement/response #4
• 2011-03-29 (C): statement/response #5
• 2011-04-05 (C): statement/response #6, requests patch review, requests creating wiki info pages
• 2011-04-05 (CM): comment regarding wiki pages creation
• 2011-04-05 (Peter): some questions #1
• 2011-04-05 (C): statement/response #7
• 2011-04-05 (Peter): draft for mailing text
• 2011-04-05 (C): statement/response #8

• 2011-04-05 (C): discussion on Software-Assessment project meeting 2011-04-05 with action items

• 2011-04-06 (C): question to (Wytze) regarding chroot patch on testserver

• 2011-04-06 (CM): created initial wiki pages as of action items from Software-Assessment project meeting 2011-04-05

• 2011-04-06 (Peter): statement, comments, questions
• 2011-04-06 (Critical Admin): added chroot patch exec report on testserver
• 2011-04-06 (C): discovered problem with exec report
• 2011-04-06 (C): proposal using openssl-vulnkey php script
• 2011-04-06 (C): statement/response #9, wiki page infos
• 2011-04-06 (Critical Admin): response to exec report problem
• 2011-04-06 (CM): update on wiki info page
• 2011-04-06 (C): comment/proposal on using openssl-vulnkey php script

• 2011-04-06 (CM): reminder of action item from Software-Assessment project meeting 2011-04-05 to (C)

• 2011-04-06 (CM): added subpage of wiki info page
• 2011-04-06 (A): second intermediate ruling given.
• 2011-06-24 (A): third intermediate ruling given.

Original Dispute, Discovery (Private Part)

Corresponding bugreport in Mantis are 918 (sending mails) and 954 (mass revocation).

Original Dispute

• Original mailing (Sa 12.03.2011 03:03) to: Board-private list, CAcert-disputes list, Philipp G., Dirk A., Ulrich S., Markus W.

  Hi,
  
  Hanno Böck informed support@cacert.org about having found a security
  issue, he then mailed me encrypted.
  
  I don't know whether this needs to be dealt with an Arbitration.
  Definitely we should patch this as soon as possible.
  
  This issue means that anyone can just look in the EFF data base to find
  a weak certificate, do some number crunching to compute the private key
  (which might take as short as 72 hours or even less) and act as the
  party the certificate belongs to. This even includes signing in on
  cacert.org if that's activated.
  
  Why should we react if our users make the mistake of generating weak
  keys? For the same reason we force them to choose strong passwords: if
  they or their account are attacked it redounds upon us if we didn't
  implement _some_ safeguards to prevent it. In the worst case even our
  whole web of trust may collapse like a house of cards if a critical mass
  of accounts are attacked.
  
  Hanno gives us 2 weeks to get this sorted out. It would be brilliant if
  we could fix that within this time frame (well, "brilliant" is probably
  the wrong word, "not as bad" is probably better).
  
  
  ====
  
  More detailed description of the issue (this is still abbreviating in
  many places, but it should do the job to explain why this is a serious
  issue):
  
  = Small Modulus =
  
  RSA uses something called a modulus which is a product of two long
  primes. The trick is, that if you only know the modulus, it's very
  difficult to compute the primes it is made of (at least it's widely
  believed that it's difficult) but if you know the primes computing the
  modulus is trivial (just multiply them) and only if you know those
  primes you can do some operations efficiently. So to make a
  cryptographic scheme out of it you only publish the modulus N and a
  so-called exponent e, the party which wants to send you a message does
  some operation with the modulus and the message (it computes c:= m^e mod
  N) and sends you the cyphertext c. Only you having the extra information
  about the modulus (the primes) can revert that operation efficiently, eh
  voilà.
  The problem is: if your modulus is too short an attacker might be able
  to compute the primes it is made of (just by trying all possibilities,
  this is called factoring) and therefore has the same information as you.
  Therefore he can fully impersonate you, including decrypting your
  messages, signing documents in your name, using your certificate in
  authentication protocols like SSL/TLS with client authentication as used
  for our certificate login.
  
  
  = Small Exponent =
  
  The exponent 3 Hanno mentions is a little more tricky. If you send
  someone a message that is "smaller" than N^(1/3) then reverting m^3 mod
  N is not a difficult operation at all because there was no modulus
  reduction (i.e. no overflow) taking place so you can just compute the
  cubic root over the integers (which is hard to do in your head but
  computers can do it fairly well). For larger exponents e this becomes
  less feasible because you need to be very lucky that the message you're
  looking at is < N^(1/e).
  Messages smaller than N^(1/3) are more common than one thinks because
  often RSA is used to exchange a key for a symmetric cypher (e.g. AES)
  which is then used to encrypt the real message (because AES is faster
  than RSA) and those keys are very short. For example if you use a 512
  bit N the key must be smaller than about 170 bits which is the case for
  the smallest key size of AES (128 bit). If you use a 2048 bit N (which
  is considered more secure against factoring described above) things get
  worse and the attack works if the key is smaller than about 682 bit
  which is more than enough for the strongest version of AES (256 bit) and
  even if the exponent e was 7 instead of 3 it would break 256 bit AES
  (128 bit AES is broken up to e = 13). So we have the absurd situation
  that choosing a more secure modulus decreases security if an unsafe
  exponent is chosen.
  
  This attack only allows to recover messages, it doesn't allow to compute
  the private key and I don't know if it can be used to sign messages.
  However this might be enough to break some authentication protocols
  (probably not SSL/TLS though, as they are hopefully not using Textbook
  RSA, see below).
  
  Another attack against small exponents e is known which allows to
  recover any message (no matter how large) that is sent to more than e
  parties all using the same e as their public key. The math involved is a
  little more sophisticated and involves the chinese remainder theorem so
  I'll spare you with this. I think this case is more of academical
  concern and probably not seen in reality. But you know sometimes reality
  sucks and there's always Murphy's law waiting around the corner.
  
  
  
  The Bad News:
  These attacks against small exponents e are efficient (i.e. they will
  take less than a few minutes to complete)
  
  The Good News:
  They only work against so-called Textbook RSA which hopefully nobody on
  this planet uses any more (because it is insecure in any way you can
  think of).
  Non-Textbook RSA uses a padding before encrypting the messages which
  makes sure that
  a) the message is about as big as N => it is not smaller than N^(1/e)
  b) the message contains some randomness => the exact same message is
  never sent to multiple parties.
  
  
  = Exponent is exactly 3 =
  
  There was a security vulnerability in OpenSSL (and other crypto
  libraries) in 2006 that allowed an attacker to forge signatures if the
  exponent e was 3. As this is only an implementation issue that came into
  effect upon _verifying_ signatures it should be fixed everywhere by now.
  In contrast to the debian vulnerability this does not affect the present
  because the error does not manifest in persistent things like keys or
  signatures, only the check was broken.
  
  
  I'll ask Hanno what his exact concern with exponent e = 3 is. Whether
  it's the small exponent, which should not be possible to exploit on
  Non-Textbook RSA, the OpenSSL vulnerability or something completely
  different I haven't thought about before.
  
  
  = Debian Vulnerability =
  
  We had some blog post about this http://blog.cacert.org/2008/05/308.html
  We didn't revoke any certificates back then because our roots are
  themselves not affected by the vulnerability but as stated above we
  should protect our users to protect ourselves.
  
  
  -------- Original-Nachricht --------
  Betreff: Re: [s20110310.75] reporting security issue
  Datum: Fri, 11 Mar 2011 23:38:57 +0100
  Von: Hanno Böck
  An: Michael Tänzer
  
  Okay:
  
  You probably know about the eff observatory project:
  https://www.eff.org/observatory
  (if you don't know: they scanned the full ipv4 space and collected all
  https certificates they could find and put them in a database - they
  found some interesting things, e.g. a couple of EV certificates that
  don't comply with the EV rules)
  
  
  I did a little analyze of the certs signed by cacert. Security wise the
  most relevant part is that the eff database contains around 150 valid
  cacert-signed certificates with 512 bit rsa modulus. (though I have not
  checked all of then via ocsp, just did some random checks, most of them
  seem to be valid)
  
  Also, I found two certificates with exponent 3 (this is much less
  severe than the 512 bit issue) and still most of the certs issued by
  cacert are 1024 bit rsa.
  
  I have not yet checked for certificates vulnerable to the debian
  openssl bug (this is a bit more complicated), but I'll probably do that
  too.
  
  
  I'll write a report about my findings in my blog, maybe in 2-3 weeks
  from now (if you need more time to handle it, I can wait longer).
  
  I think especially the 512 bit certs are a problem. According to a
  report, in 2009 it was possible to factor a 512 bit modulus in 72 hours
  on a normal dualcore home pc. I consider 512 bit rsa fully broken.
  
  My suggestions would be:
  - informing the people with 512 bit rsa certificates and revoking them.
  - setting up some checks for new certificates if they have sane
    parameters - exponent 3 rsa and certs below 2048 bit should be
    avoided.
  
  cu,
  -- 
  Hanno Böck

Discovery

• 2011-03-12 (A): Sent mail with some technical questions to (C)

  • Hi Michael,
    
    I guess it would make sense to handle this problem under supervision of an Arbitrator, since the resolution of the case probably includes revoking certificates of several members. Since I cannot see a precedence case this should be authorized by an Arbitrator.
    
    I have opened the case with the Arbitration Mailing List and will probably be either Arbitrator or Case Manager. To speed up the process I have some technical questions:
    
    Should communication about the case go to you personally or do you think support@c.o. would be more appropriate 
    Can you already query the EFF database? 
    If yes, could you already validated the statements of Hanno and therefor extract mail adresses of affected members? 
    Kind regards
    Ted
    ;)

• 2011-03-12 (C): 1st response to questions of (A)

  • > I guess it would make sense to handle this problem under supervision of
    > an Arbitrator, since the resolution of the case probably includes
    > revoking certificates of several members. Since I cannot see a
    > precedence case this should be authorized by an Arbitrator.
    
    You're probably right.
    
    
    > I have opened the case with the Arbitration Mailing List and will
    > probably be either Arbitrator or Case Manager. To speed up the process I
    > have some technical questions:
    > 
    >     * Should communication about the case go to you personally or do you
    >       think support@c.o. would be more appropriate
    
    We could CC support, direct communication is still preferred though
    given the required quickness of response. I always have my mail client
    running which notifies me when a new mail comes in which is not the case
    with OTRS. Apart from that I'm also involved as Software Assessor.
    
    
    >     * Can you already query the EFF database?
    
    The data base is public so I will try.
    
    
    >     * If yes, could you already validated the statements of Hanno and
    >       therefor extract mail adresses of affected members?
    
    Just extracting the members from the EFF data base won't suffice as the
    EFF data base might not be complete and it doesn't contain client
    certificates. We at least additionally have to query our own data set.
    Maybe I can extract the information from the EFF data base so we can
    notify the members as an immediate action until the patches and queries
    for our own data set are ready to automatically revoke and notify cases
    where the first notification didn't succeed.

• 2011-03-12 (A): Sent roadmap of further actions. First issue is to find the weak certificates/keys, notify their owners and then revoke them. The second issue is to modify the software that weak keys are not accepted any more in the future.

  • OK, in the meantime I became Arbitrator for the case, Uli will act as Case Manager.
    
    I guess I can safely assume that you have already accepted CCA and DRP and so on. The case's status page is at https://wiki.cacert.org/Arbitrations/a20110312.1
    
    Am 12.03.2011 15:42, schrieb Michael Tänzer: 
     > Hi Ted,
    
     > [...]
      
     >     * If yes, could you already validated the statements of Hanno and
     >       therefor extract mail adresses of affected members?
        
     > Just extracting the members from the EFF data base won't suffice as the
     > EFF data base might not be complete and it doesn't contain client
     > certificates. We at least additionally have to query our own data set.
     > Maybe I can extract the information from the EFF data base so we can
     > notify the members as an immediate action until the patches and queries
     > for our own data set are ready to automatically revoke and notify cases
     > where the first notification didn't succeed.
      
    
    Agreed. So I guess the following course of action would be appropriate to handle the affected certificates:
    
    Execute an SQL query on the main database which extracts the (file-)names of all non-expired server certificates. 
    Write a script to execute on the main server, which parses all those certificate files for small keysize or dangerous exponent 
    Whith the names of all affected files, do another SQL query which extracts mail addresses (and probably names) of the owners of this certificates 
    Send a mail to all owners found and warn them that the certificates will be revoked. 
    After a grace period, revoke all weak certificates, probably by another SQL script. 
    The SQL queries and scripts have to prepared, then I'll have to have a look at them and authorize their execution on the server.
    
    So will you coordinate the development work on the scripts and queries? Of course each script should be reviewed by someone not too deeply involved in the development of that script before I do the final review. 
    
    I can assist in development if needed, just tell me which part I should try myself upon.
    
    The second issue is how to make sure that no weak certificates will be created in the future. This is probably a small thing for Arbitration (I'll probably just order that it shall be done), but maybe not for Software Development. So I'll leave this completely to Software Development... :-)
    
    BTW, I guess current state of the art is to use 2048 bit keys for new certificates, but 1024 bit keys are not considered as easily breakable. So we should accept only 2048 bit keys for new certificates, but revoke only certs with keysize < 1024. Does this make sense for everyone?
    
    Ted
    ;)

• 2011-03-12 (C): accepts CCA/DRP, answer to (A)'s roadmap, first results

  • > OK, in the meantime I became Arbitrator for the case, Uli will act as
    > Case Manager.
    > 
    > I guess I can safely assume that you have already accepted CCA and DRP
    > and so on. The case's status page is at
    > https://wiki.cacert.org/Arbitrations/a20110312.1
    
    Yes, I accept CCA and DRP.
    
    
    > Am 12.03.2011 15:42, schrieb Michael Tänzer:
    >> Hi Ted,
    >>
    >> [...]
    >>   
    >>>     * If yes, could you already validated the statements of Hanno and
    >>>       therefor extract mail adresses of affected members?
    
    I have downloaded the EFF data base by now and ran some queries on it.
    There are 240 certificates signed by CAcert with a key size < 1024 bit
    (all of them 512 bit). Many are already expired though. That leaves 78
    certs still valid with a weak key. I can get you a list with any
    information you like as long it's contained in the cert (e.g. the host
    name, expiry date, etc.).
    
    
    >> Just extracting the members from the EFF data base won't suffice as the
    >> EFF data base might not be complete and it doesn't contain client
    >> certificates. We at least additionally have to query our own data set.
    >> Maybe I can extract the information from the EFF data base so we can
    >> notify the members as an immediate action until the patches and queries
    >> for our own data set are ready to automatically revoke and notify cases
    >> where the first notification didn't succeed.
    >>   
    > 
    > Agreed. So I guess the following course of action would be appropriate
    > to handle the affected certificates:
    > 
    >     * Execute an SQL query on the main database which extracts the
    >       (file-)names of all non-expired server certificates.
    >     * Write a script to execute on the main server, which parses all
    >       those certificate files for small keysize or dangerous exponent
    
    I would propose to do this in one step as otherwise the first list might
    be quite huge and it contains data we don't need, so better not extract
    it in the first place.
    
    
    >     * Whith the names of all affected files, do another SQL query which
    >       extracts mail addresses (and probably names) of the owners of this
    >       certificates
    >     * Send a mail to all owners found and warn them that the
    >       certificates will be revoked.
    
    The mail should clearly state that they need completely new keys, they
    can't just renew the old cert.
    
    
    >     * After a grace period, revoke all weak certificates, probably by
    >       another SQL script.
    
    We probably should have the fix that prevents issuing a new cert with
    the old keys ready at this point so we don't have to recheck after that
    patch is ready.
    
    
    > The SQL queries and scripts have to prepared, then I'll have to have a
    > look at them and authorize their execution on the server.
    > 
    > So will you coordinate the development work on the scripts and queries?
    > Of course each script should be reviewed by someone not too deeply
    > involved in the development of that script before I do the final review.
    
    Sure. I hope we can spread the load among the software assessment team a
    bit, because I'm also pretty busy in the non-CAcert life currently.
    
    Also it would be good to have someone prepare the mailing that should be
    sent to the affected users (I guess I'm a little too involved into the
    crypto to explain this in a way an average human can understand it, a
    native speaker would probably help too)
    
    
    > I can assist in development if needed, just tell me which part I should
    > try myself upon.
    
    Pick anything you like.
    
    
    > The second issue is how to make sure that no weak certificates will be
    > created in the future. This is probably a small thing for Arbitration
    > (I'll probably just order that it shall be done), but maybe not for
    > Software Development. So I'll leave this completely to Software
    > Development... :-)
    
    As mentioned it has to go hand in hand to prevent we have to do another
    arbitration for all those certs that would have been created between
    revoking the present weak certs and preventing new weak ones.
    
    
    > BTW, I guess current state of the art is to use 2048 bit keys for new
    > certificates, but 1024 bit keys are not considered as easily breakable.
    > So we should accept only 2048 bit keys for new certificates, but revoke
    > only certs with keysize < 1024. Does this make sense for everyone?
    
    Yep, that's what I thought too. One hindrance that comes to my mind: Is
    it currently possible to generate 2048 bit client certs in-browser with
    Internet Explorer? Can someone running Windows please check? Thanks.

Results of Script run:

It turns out that a single run of the script took about 9 hours So if we need to run this script again in the future with multiple output filters, I'll think of a more efficient way; mkfifo and tee might come to our rescue here

The job finished this morning at 6:30am ... The outcome of the first run (with openssl-vulnkey filtering) reported 879 lines, while the second run (without filter) reported 1679 lines. In addition the output contains a number of warnings for certificates with 8192-bit keys, like:

• WARN: could not open database for 8192 bits. Skipped ....crt

This happened for 64 certificates in each run. Since you seemed to insist on storing as little information as possible on disk, I have removed those WARN lines from the attached script output. But they are still available when really needed.

+ date
Mon Apr 18 12:26:55 CEST 2011
+ ./DumpWeakCerts.pl
+ grep openssl-vulnkey
+ wc -l
879

real    525m23.119s
user    298m11.082s
sys     108m13.862s
+ ./DumpWeakCerts.pl
+ wc -l
1679

real    555m6.856s
user    298m17.675s
sys     108m25.471s
+ date
Tue Apr 19 06:27:26 CEST 2011

Confirmation of mass revocation script run by critical admins:

Op 28-7-2011 10:10, Wytze van der Raay schreef:
> On 27.07.2011 23:02, Bernhard Fröhlich wrote:
>> ...
>> Once the scripts are installed you should execute them according to
>> https://wiki.cacert.org/Arbitrations/a20110312.1
>> The execution command is to pipe the result of DumpWeakCerts.pl into
>> mass-revoke.php:
>>   ./DumpWeakCerts.pl | ./mass-revoke.php
> The run has been started. I will mail you the results when it has completed
> (probably some time later today).
Here is the result of the mass-revoke run:

Started: Thu Jul 28 10:08:12 CEST 2011
Certificates revoked: 938 server certs, 133 client certs, 57 Org server
certs, 0 Org client certs.
Update failures: 0
Finished: Thu Jul 28 20:09:14 CEST 2011

Regards,
-- wytze

• Link to Arbitration case a20110312.1 (Private Part)

EOT Private Part

Discovery

• The Claimant's explanations make it plausible that CAcert has probably issued certificates for weak keys.
• The Claimant confirms that he could reproduce the results of Hanno B. in the EFF SSL Observatory database.

Ruling

First intermediate Ruling

Like explained by the Claimant it seems that CAcert has issued certificates for keys which can easily be broken. As part of our mission to educate and protect our members action shall be taken to investigate the problem in detail.

I therefore rule that Software Development shall create a set of scripts to find out the affected certificates and their owners, which will be executed on CAcert's main database.

Also I rule that Software Development shall prepare a patch to the web page so that weak keys will not be accepted for certificate creation in the future.

Second intermediate Ruling

After discussion with Software Development "weak keys" are defined as

• RSA keys having a modulus size of less than 1024 bit or
• RSA keys having an exponent of 3 or

• keys failing the openssl-vulnkey-test

A test run of the created scripts is authorized to evaluate number of affected keys per category.

Third and last intermediate Ruling

After the software fixed have been installed creating new certificates for weak keys should not be possible anymore. Now the owners of weak keys must be notified that they should create new keys to avoid being attacked, and the existing certificates must be revoked after a grace period for user interaction.

The scripts extracting the mail adresses of affected users and sending the mails have already been prepared and reviewed. Their execution is hereby authorised, the action date (line 140 in mail-weak-keys.php) shall be set to '2011-07-15'.

Software Development shall prepare the necessary tools to revoke all weak key certificates as soon as possible after July 15, as announced in the mails.

Execution

• 2011-04-14 (A): Sent instructions for test run to Critical Sysadmins
• 2011-04-19 Support sends results of script run.
• 2011-06-22 Software Development reports that the necessary software fixes have been deployed on the productive systems.
• 2011-06-27 Critical admins report that the script has been executed and mails have been sent.
• 2011-07-27 (A): Patch for mass revocation and execution request sent to critical admins.
• 2011-07-28 (A): Critical admins confirm that the mass revocation script has been run.
• 2011-07-28 The case is closed now.

Similiar Cases

• CategoryArbitration

• CategoryArbCaseSystemTasks