* 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) [[https://lists.cacert.org/wws/arc/cacert-disputes/2011-03/msg00004.html|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/20110405-S-A-MiniTOP|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/20110405-S-A-MiniTOP|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/20110405-S-A-MiniTOP|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 [[https://bugs.cacert.org/view.php?id=918|918]] (sending mails) and [[https://bugs.cacert.org/view.php?id=954|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 [[Arbitrations/priv/a20110312.1|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 [[DebianVulnerabilityHandling|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