Older blog entries for jas (starting at number 15)

CACert and GnuTLS

I haven’t seen this before, so I thought I’d documment how to generate a server TLS certificate using CACert. This can be useful if you are running a mail or web server and easily (and cost free) want to support TLS for integrity/confidentiality. I just re-installed my secondary mail server, and tested this recipe with Exim4 with Debian. See below for a step-by-step howto.

First make sure you have the GnuTLS command line tools installed:

kniv:~# apt-get install gnutls-bin

The next step is to generate a private key:

kniv:/etc/exim4# certtool –generate-privkey –outfile exim.key
Generating a 2048 bit RSA private key…
kniv:/etc/exim4#

You can use --dsa if you want to use DSA instead of RSA, and can change the key size using --bits. The default is 2048-bit RSA which should be good enough for most people.

The next step is to generate a Certificate Request. CACert only looks at the Common Name field, so I left the rest empty. If you are using some commercial CA, you may need to enter something in the other fields.

kniv:/etc/exim4# certtool –generate-request –load-privkey exim.key –outfile exim.csr
Generating a PKCS #10 certificate request…
Country name (2 chars):
Organization name:
Organizational unit name:
Locality name:
State or province name:
Common name: kniv.josefsson.org
UID:
Enter a challenge password:
kniv:/etc/exim4#

Then login to CACert and click on ‘Server Certificates’ and then ‘New’. It will ask you to paste in the certificate request. Here you paste in the content of the exim.csr file. CACert will ask you to confirm the hostname. After that it will show a certificate in the resulting web page. Put the certificate in a file exim.crt like this:

kniv:/etc/exim4# cat>exim.crt
-----BEGIN CERTIFICATE-----
MIIEuDCCAqCgAwIBAgICegUwDQYJKoZIhvcNAQEFBQAwVDEUMBIGA1UEChMLQ0Fj
ZXJ0IEluYy4xHjAcBgNVBAsTFWh0dHA6Ly93d3cuQ0FjZXJ0Lm9yZzEcMBoGA1UE
AxMTQ0FjZXJ0IENsYXNzIDMgUm9vdDAeFw0wOTA0MTYxNTIyNDFaFw0xMTA0MTYx
NTIyNDFaMB0xGzAZBgNVBAMTEmtuaXYuam9zZWZzc29uLm9yZzCCASIwDQYJKoZI
hvcNAQEBBQADggEPADCCAQoCggEBAOCA/9NCraz72OG9c41w0aPenWZcdyiwI+OZ
2drOFHAQf0y9ihKZtZSkMJHHQBIdYwQPvaXuvzWJG6leaIeed4/Er/7BMvN4NqhU
r28qPv5HHCkGEKfUmmc5+sorYSCAgsEJU5SITIjpeSZqcL07hib+Mj0PUUkcVRZU
Jk7WHMaHFUZ1gvbYHEvk9C29CS/yq6SqAWdLwY8FRBHW9XvQa+zVp9j+ZecwS87i
NjzCMI13NAMEBanEc4LKuG2bN0EGGbceyd91YnCxQNDSiXrm9GvAfboidKmNmgAI
LJqAy3gXCCu0BXHDtJut8Z6mOz6gu5bFeLV3jARk+/CHVXypi7sCAwEAAaOByjCB
xzAMBgNVHRMBAf8EAjAAMDQGA1UdJQQtMCsGCCsGAQUFBwMCBggrBgEFBQcDAQYJ
YIZIAYb4QgQBBgorBgEEAYI3CgMDMAsGA1UdDwQEAwIFoDAzBggrBgEFBQcBAQQn
MCUwIwYIKwYBBQUHMAGGF2h0dHA6Ly9vY3NwLmNhY2VydC5vcmcvMD8GA1UdEQQ4
MDaCEmtuaXYuam9zZWZzc29uLm9yZ6AgBggrBgEFBQcIBaAUDBJrbml2Lmpvc2Vm
c3Nvbi5vcmcwDQYJKoZIhvcNAQEFBQADggIBABi/NjSTTFvw9XLWgfm7wnnOO9LP
U8yEgrQYCNIW6Zh7zH5w+pGzvBUSMOthMnmyfLacZSYjtOknlIG2kNDZEGaWznCN
WPMjNTctarR/g2qnD329o6orxPiK6Nmtcvcrj7BTecHDcExtE7CPe+msBN4OzIj1
zQGTMjge/Ofhft4Y2vYHOJMqsrQ2vj8xnUE7yGpw7IPDFTnyIyw55lSSbnAhACkp
eLrTcyYpxs7gTcaKqTOUEmUKCFqPsGPRGP3cgIMn3MHgqdq6b0XeF8E9+4iSuHBa
yPOxeWDLV4OEZZ0ygiQBgXyZQ+aRsuLo2BTSW0UEf+/J4ZbPiZlrUPouJ5tADceN
7DDhZu3q2RtCQLTNrMaUUY0uvUS41T8iox00tphi7DsOqq/Sku8vVR370NJJmWix
ChD74seszVlU+nPsrvFGN53+1wbgvtFSOSTRol7AvaPnx2TvC215GZ3wRb/WGCm4
r2em9QsI1T+7AjSHoFoaCWfFekHa1x+q7IJoAt/uMJBrvimC0ioTUMkyfrkcLWTr
mFObSwvq6zhV+MhgtYe/nEkb45eAyy5TP3qvmrjBAKad0qUpazmRbiWsb5VLK1hO
+FR6nD1aNDyukCSO0UH6bu9BzcbET5kkybkSlslDnrNfpn16EsIlrQgZ9RrF1Dr/
a6rS5JJX1gbewzse
-----END CERTIFICATE-----
kniv:/etc/exim4#

That’s it!

You need to finish the Exim4 configuration. Below ^D means to type ctrl-d.

kniv:/etc/exim4# chgrp Debian-exim exim.key
kniv:/etc/exim4# chmod g+r exim.key
kniv:/etc/exim4# cat>/etc/exim4/conf.d/main/000_local
MAIN_LOG_SELECTOR=+tls_cipher +tls_peerdn
MAIN_TLS_ENABLE=t
^D
kniv:/etc/exim4# update-exim4.conf
kniv:/etc/exim4# /etc/init.d/exim4 restart
Stopping MTA for restart: exim4_listener.
Restarting MTA: exim4.
kniv:/etc/exim4#

You can test the setup by using gnutls-cli. Again, ^D means ctrl-d.

kniv:/etc/exim4# gnutls-cli -s -p 25 kniv.josefsson.org
Resolving 'kniv.josefsson.org'...
Connecting to '195.238.76.189:25'...

- Simple Client Mode:

220 kniv ESMTP Exim 4.69 Thu, 16 Apr 2009 18:10:19 +0200
ehlo foo
250-kniv Hello kniv.josefsson.org [195.238.76.189]
250-SIZE 52428800
250-PIPELINING
250-STARTTLS
250 HELP
starttls
220 TLS go ahead
^D
*** Starting TLS handshake
- Successfully sent 0 certificate(s) to server.
- Ephemeral Diffie-Hellman parameters
 - Using prime: 2056 bits
 - Secret key: 2040 bits
 - Peer's public key: 2048 bits
- Certificate type: X.509
 - Got a certificate list of 1 certificates.

 - Certificate[0] info:
 # The hostname in the certificate matches 'kniv.josefsson.org'.
 # valid since: Thu Apr 16 17:22:41 CEST 2009
 # expires at: Sat Apr 16 17:22:41 CEST 2011
 # fingerprint: 21:C5:4E:60:02:02:93:9A:3B:B6:F0:D6:8E:6B:6C:B0
 # Subject's DN: CN=kniv.josefsson.org
 # Issuer's DN: O=CAcert Inc.,OU=http://www.CAcert.org,CN=CAcert Class 3 Root

- Peer's certificate issuer is unknown
- Peer's certificate is NOT trusted
- Version: TLS1.0
- Key Exchange: DHE-RSA
- Cipher: AES-128-CBC
- MAC: SHA1
- Compression: NULL
quit
221 kniv closing connection
- Peer has closed the GNUTLS connection
kniv:/etc/exim4#

Syndicated 2009-04-16 15:51:02 from Simon Josefsson's blog

OpenWRT 8.09 plus Huawei E220

Now that OpenWRT 8.09 has been released, I finally took the time to write down my notes on how to use it together with the Huawei E220 dongle, which supports 3G/HSDPA.

Huawei E220

The writeup on how to do this is long, so I put it at a separate page:
http://josefsson.org/openwrt/dongle.html

Syndicated 2009-03-05 15:39:53 from Simon Josefsson's blog

Redmine on Debian Lenny Using Lighttpd

The GnuTLS trac installation is in a poor shape. To fix that, I looked into alternatives and found Redmine. Redmine appears to do most things that I liked in Trac (wiki, roadmap and issue tracking) plus it supports more than one project (would come in handy for my other projects) and has built-in git support. I would like to see better spam handling and OpenID support, but it is good enough for our purposes now, and there are similar concerns with trac.

However, getting it up and running with lighttpd on a modern debian lenny installation was not trivial, and I needed some help from #redmine (thanks stbuehler). After finally getting it up and running, I made a copy of the machine using rsync and rsnapshot, so I could re-create a working configuration if I get stuck, and then re-installed the virtual machine.

The notes below are the steps required to set up Redmine using Lighttpd and MySQL on a Debian Lenny. I’m posting this to help others searching for the error messages I got, and to help my own memory in case I need to re-install the server sometime.

I assume you have installed Debian Lenny, and have root access to it. You need to install some dependencies:

apt-get install mysql-server rails lighttpd
apt-get install librmagick-ruby
apt-get install subversion git-core

First, you need to download and install Redmine. There are official Redmine installation instructions, and these steps follow them but contains more details.

You could check out the code using SVN although I chosed to use a stable release. I created a new user for the redmine installation, to reduce root account usage.

adduser –disabled-password redmine
su redmine
wget http://rubyforge.org/frs/download.php/39477/redmine-0.7.3.tar.gz
tar xfz redmine-0.7.3.tar.gz
ln -s redmine-0.7.3 redmine

Next create the database:

redmine@li37-61:~$ mysql
Welcome to the MySQL monitor. Commands end with ; or \g.
Your MySQL connection id is 5
Server version: 5.0.51a-15 (Debian)

Type ‘help;’ or ‘\h’ for help. Type ‘\c’ to clear the buffer.

mysql> create database redmine character set utf8;
Query OK, 1 row affected (0.00 sec)

mysql> Bye
redmine@li37-61:~$

Modify the file redmine*/config/database.yml to read:

production:
  adapter: mysql
  database: redmine
  host: localhost
  username: root
  password:
  encoding: utf8

You should now run ‘rake db:migrate RAILS_ENV=”production”‘ however I got the following error at this point:

redmine@li37-61:~/redmine$ rake db:migrate RAILS_ENV=”production”
(in /home/redmine/redmine)
rake aborted!
No such file or directory - /tmp/mysql.sock

(See full trace by running task with –trace)
redmine@li37-61:~/redmine$

The problem is that you need the Ruby MySQL wrappers. This isn’t really clear from the error message. Install it using:

# apt-get install libmysql-ruby

Now re-run ‘rake db:migrate RAILS_ENV=”production”‘ as the redmine user.

redmine@li37-61:~/redmine$ rake db:migrate RAILS_ENV=”production

redmine@li37-61:~/redmine$ rake redmine:load_default_data RAILS_ENV=”production”
(in /home/redmine/redmine-0.7.3)

Select language: bg, cs, da, de, en, es, fi, fr, he, hu, it, ja, ko, lt, nl, no, pl, pt, pt-br, ro, ru, sr, sv, th, uk, zh, zh-tw [en]
====================================
Default configuration data loaded.
redmine@li37-61:~/redmine$

At this point you should be able to test the Redmine installation using:

ruby script/server -e production

Shut it down before you continue with next steps.

Create a file called /etc/lighttpd/conf-available/20-redmine.conf and put the following in it. Change the filename and hostname as appropriate, but be sure the change commands later on.

server.modules   += ( "mod_fastcgi" )

$HTTP["host"] == "redmine.josefsson.org" {
  server.document-root = "/home/redmine/redmine/public/"
  fastcgi.server    = ( ".fcgi" =>
        ((
                "bin-path" => "/home/redmine/redmine/public/dispatch.fcgi",
                "socket" => "/tmp/ruby-rails.socket",
                "max-procs" => 5,
                "idle-timeout" => 20,
                "bin-environment" => (
                        "RAILS_ENV" => "production",
                        "RAILS_ROOT" => "/home/redmine/redmine"
                ),
        ))
  )
  magnet.attract-physical-path-to = ( "/home/redmine/cleanurl.lua" )
}

Enable the module using:

# lighttpd-enable-mod redmine

You will also need to create a FastCGI wrapper:

li37-61:/home/redmine/redmine/public# cp dispatch.fcgi.example dispatch.fcgi
li37-61:/home/redmine/redmine/public# chmod +x dispatch.fcgi

At this point, it can be useful to tail the various log files, I’m using a command like:

tail -F /var/log/lighttpd/access.log /var/log/lighttpd/error.log /home/redmine/redmine/log/production.log

Starting the lighttpd server at this point results in an error message:

li37-61:~# /etc/init.d/lighttpd restart
Stopping web server: lighttpd.
Starting web server: lighttpd.
li37-61:~#
2008-10-17 04:50:03: (mod_fastcgi.c.1047) the fastcgi-backend /home/redmine/redmine/public/dispatch.fcgi failed to start:
2008-10-17 04:50:03: (mod_fastcgi.c.1051) child exited with status 9 /home/redmine/redmine/public/dispatch.fcgi
2008-10-17 04:50:03: (mod_fastcgi.c.1054) If you’re trying to run PHP as a FastCGI backend, make sure you’re using the FastCGI-enabled version.
You can find out if it is the right one by executing ‘php -v’ and it should display ‘(cgi-fcgi)’ in the output, NOT ‘(cgi)’ NOR ‘(cli)’.
For more information, check http://trac.lighttpd.net/trac/wiki/Docs%3AModFastCGI#preparing-php-as-a-fastcgi-programIf this is PHP on Gentoo, add ‘fastcgi’ to the USE flags.
2008-10-17 04:50:03: (mod_fastcgi.c.1358) [ERROR]: spawning fcgi failed.
2008-10-17 04:50:03: (server.c.908) Configuration of plugins failed. Going down.

FastCGI modules are not installed by default, so you will need to install them:

li37-61:~# apt-get install libfcgi-ruby1.8

Restarting the server again, and accessing dispatch.fcgi using your browser, will result in errors like:

Status: 500 Internal Server Error
No route matches “/dispatch.fcgi” with {:method=>:get}

Solving this is the most complicated part, and I’m not sure whether there are better solutions. Here is what I did. First, install lighttpd’s mod-magnet:

# apt-get install lighttpd-mod-magnet
# lighttpd-enable-mod magnet

Then get a small script to invoke dispatch.fcgi properly:

cd /home/redmine
wget http://nordisch.org./cleanurl.lua

For reference, the contents of the script is:

-- little helper function
function file_exists(path, ftype)
  local attr = lighty.stat(path)
  return (attr and attr[ftype])
end

function check_path(path)
    local rv = path
    if (not file_exists(path, "is_file")) then
        rv = nil
        local html_file = path .. ".html"
        if (file_exists(html_file, "is_file")) then
            rv = html_file
        else
            -- handle directory indeces
            -- we first check if we have a dir and than look for an index.html
            local index_file = path .. "/index.html"
            if (file_exists(path,"is_dir") and file_exists(index_file, "is_file")) then
                rv = index_file
            end
        end
    end
    if rv then
        lighty.env["physical.path"] = rv
    end
    return rv
end

-- the magic ;)
if (not check_path(lighty.env["physical.path"])) then
    -- file still missing. pass it to the fastcgi backend
    lighty.env["uri.path"]          = "/dispatch.fcgi"
    lighty.env["physical.rel-path"] = lighty.env["uri.path"]
    lighty.env["request.orig-uri"]  = lighty.env["request.uri"]
    lighty.env["physical.path"]     = lighty.env["physical.doc-root"] .. lighty.env["physical.rel-path"]
end
-- fallthrough will put it back into the lighty request loop
-- that means we get the 304 handling for free. ;)
-- debugging code
-- print ("final file is " ..  lighty.env["physical.path"])

At this point, you should be able to restart lighttpd and access your server successfully!

If you get permission errors such as:

Status: 500 Internal Server Error
file /home/redmine/redmine-0.7.3/tmp/sessions//ruby_sess.c06b5f395568fd87 not readable

You need to re-run these commands:

li37-61:/home/redmine/redmine-0.7.3# chgrp -R www-data files log tmp
li37-61:/home/redmine/redmine-0.7.3# chmod -R 775 files log tmp

Happy hacking!

Syndicated 2008-10-17 09:47:59 from Simon Josefsson's blog

FSCONS / Nordic Free Software Award Nomination

The Free Software & Culture conference FSCONS is held in Gothenburg October 24-26th. Having been there and given talks last year, I can recommend it for anyway interested in what’s going on the free software and culture world.

I’m happy and proud to notice that I have been nominated for their award, for my work on security packages for the GNU project. Too bad I cannot make it to the conference this year.

Syndicated 2008-10-14 09:59:51 from Simon Josefsson's blog

Cyclomatic Code Complexity

Inspired by my own OWASP Sweden chapter talk last night, I learned more about Cyclomatic Code Complexity and did some practical experiments.

Cyclomatic Code Complexity was described by Thomas J. McCabe in 1976. Read the Wikipedia entry for the entire story, but in short it is a measure of C code complexity relevent to code testing.

I learned about its practical use from GNUPDF’s nice cyclomatic report. They use a tool called PMCCABE which happen to be packaged in Debian, so it was easy for me to test it.

I produced reports for some of my projects and some other popular tools, and put them online at:
http://josefsson.org/cyclo/.

Hopefully this will help me and others to find where the complex code is located. Knowing where to look is the first step towards improving things.

In my projects (e.g., gnutls, gnu sasl, shishi, libidn) I use gnulib for portability modules and maintainer scripts. Thus it felt natural to integrate GNUPDF’s custom scripts into a gnulib module. I’m discussing the module now.

Syndicated 2008-10-07 11:57:01 from Simon Josefsson's blog

My blog uses yubikey authentication

Thanks to Henrik Schack’s great work in developing a Wordpress Yubikey plugin, I now use two-factor hardware-assisted authentication technology (i.e., the Yubikey) to log in to my blog. Kudos, Henrik!

Since my server still uses php4 (sigh), I had to create a small patch to make it use mhash instead of hash.

Syndicated 2008-06-30 15:32:13 from Simon Josefsson's blog

Home Wireless Network

Using OpenWRT with WPA-PSK 2 on Broadcom WLAN routers have been stuck on a quite old bug. Recently someone suggested that it may have been fixed in trunk, which caused me to test it. And it works!

It took some time to work out the details here. To save myself time to reconstruct the commands, and hopefully save you some time too, I wrote down how to use OpenWRT with two Asus WL-500g Premium linked together wirelessly using WDS and PSK2 encryption.

The writeup is long, so I put it on a separate page:

http://josefsson.org/openwrt/wlan.html.

If you are interested in using OpenWRT with a 3G connection, you may find my summer house internet writeup more useful.

Syndicated 2008-05-08 13:48:42 from Simon Josefsson's blog

Real-world Performance Tuning with Callgrind

This post describe the process of identifying and profiling an inefficient part of GnuTLS. The tool I’m using is callgrind. I won’t describe the tool in detail since I’m not a callgrind expert, instead the focus is on the methodology in finding and fixing a problem. My hope is that this is useful as an insight to how maintainers go about fixing a performance-related problem. It also demonstrates how immensely useful tools like valgrind and callgrind are.

Today I stumbled over something as rare as a post that contains example code to reproduce a problem. The post was written by Edgar Fuß on the openldap list: link to edgars post. First, there is something to be learned here: if there hadn’t been code in that post, I would most likely have ignored it because it is too much trouble for me to understand and duplicate the problem. Especially when this isn’t a real GnuTLS bug report, but just discussion on a non-GnuTLS mailing list. By posting such example code, it was easy for me to compile and run it. As it turned out, the code was very slow and my curiosity peeked. Edgar’s bug triggering code was (somewhat modified for readability):

d = opendir("/etc/ssl/certs");
gnutls_certificate_allocate_credentials(&ca_list);
while ((dent = readdir(d)) != NULL) {
  sprintf(ca_file, "/etc/ssl/certs/%s", dent->d_name);
  stat(ca_file, &s);
  if (!S_ISREG(s.st_mode)) continue;
  gnutls_certificate_set_x509_trust_file(ca_list, ca_file,
       GNUTLS_X509_FMT_PEM);
}
closedir(d);

If you aren’t familiar with GnuTLS, I’ll describe what the code is intended to do. The code will iterate over all files in /etc/ssl/certs/ and calls gnutls_certificate_set_x509_trust_file for each file. That function will read one or more X.509 CA certificates stored in the file, and add it to the CA trust store inside GnuTLS. The files are typically small (1-2kb) but contain base64 encoded ASN.1 data which is decoded by GnuTLS. The CA trust store is used to determine whether to trust a client or server’s certificate or not. While this is typically only done at startup, and not during each TLS connection, it is not particulary performance critical. Still, if it is excessively slow it will slow down application startup.

On my system (x86 Debian testing) the /etc/ssl/certs directory contains 206 files. I compiled the test code and ran it:

jas@mocca:~$ gcc -o foo foo.c -lgnutls
jas@mocca:~$ time ./foo /etc/ssl/certs/

real 0m40.821s
user 0m40.743s
sys 0m0.036s
jas@mocca:~$

40 seconds! Delaying startup of an application by that amount is pretty significant, so I understand this was considered a problem.

I became curious how much memory the process was using. If my machine had started paging (unlikely with 2GB but you never know), I could understand if it was this slow. However, the top output was relatively stable:

PID USER PR NI VIRT RES SHR …
6538 jas 20 0 5548 3668 752 …

In other words, the virtual size was about 6MB, which seemed normal. My next step was to run the binary under valgrind, to possibly detect any memory corruption or other problem that might explain the slowness. Valgrind slows down execution significantly, and after around 7 minutes I gave up and modified the code slightly so that it only iterated over the first couple of files. After running valgrind once, I discovered that the code didn’t call the needed gnutls_certificate_free_credentials() and gnutls_global_deinit(). You can download the updated example code gnutls-callgrind.c. The valgrind suppressions file to shut up some known libgcrypt internal memory leaks is available as libgcrypt.supp.

jas@mocca:~$ gcc -o foo foo.c -lgnutls
jas@mocca:~$ time ./foo

real 0m0.222s
user 0m0.216s
sys 0m0.004s
jas@mocca:~$ time valgrind –suppressions=foo.supp –quiet ./foo

real 0m7.619s
user 0m7.488s
sys 0m0.108s
jas@mocca:~$

Nice! No memory leaks. We can now be relatively certain that the problem is really with the intention of the code, rather than some memory related bug. Given that we use C here, you want to rule out such problems early on because they are a nightmare to debug.

Now for the performance tuning session. Let’s run callgrind on the application. First, we must make sure we use a GnuTLS compiled with debugging information. The easiest way to do this is to compile it against the static libgnutls. Proceed as follows.

jas@mocca:~$ gcc -o foo foo.c /usr/lib/libgnutls.a -lgcrypt -ltasn1 -lz
jas@mocca:~$ time valgrind –tool=callgrind –quiet ./foo

real 0m18.292s
user 0m18.129s
sys 0m0.084s
jas@mocca:~$ ls -la callgrind.out.8164
-rw——- 1 jas jas 69654 2008-02-26 21:46 callgrind.out.8164
jas@mocca:~$ kcachegrind &

As you can see, execution time is even slower than with valgrind. The profile data output file is quite small. Running kcachegrind yields this output (click to enlarge):

The amount of information in kcachegrind can be overwhelming at first. However, the interesting values are in the percentages and call counts columns to the left. It tells us that gnutls_certificate_set_x509_trust_file() was invoked 22 times, and that 98% of the time is spent there. (If you are surprised by the 22, look at the code, the variable i starts at 0, and the loop is run until it is larger than 20, i.e., it is 21, which makes for 22 iterations in the loop.) The code for that function looks like:

{
  int ret, ret2;
  size_t size;
  char *data = read_binary_file (cafile, &size);

  if (data == NULL)
    {
      gnutls_assert ();
      return GNUTLS_E_FILE_ERROR;
    }

  if (type == GNUTLS_X509_FMT_DER)
    ret = parse_der_ca_mem (&res->x509_ca_list,
                            &res->x509_ncas,
			    data, size);
  else
    ret = parse_pem_ca_mem (&res->x509_ca_list,
                            &res->x509_ncas,
			    data, size);

  free (data);

  if (ret 

The callgrind output tells us that 96% of the programs time is spent inside the 22 calls to generate_rdn_seq(), which in turn call gnutls_x509_crt_get_raw_dn a total of 506 times. The calls to gnutls_x509_crt_get_raw_dn make up 95% of the program’s execution time.

We can now conclude that the problem is inside the generate_rdn_seq() function, and not in the rest of the gnutls_certificate_set_x509_trust_file() function body. Given that 95% of the time is actually in a function that generate_rdn_seq calls (i.e., gnutls_x509_crt_get_raw_dn), the problem is either that the function is called too many times or that it is too slow.

Some words about what generate_rdn_seq() is intended to do: it pre-computes a list of names of the CA certificates. In TLS servers, this list of names of trusted CAs is sent to clients. The list is used by the client to find a client certificate issued by a CA that the server recognize. To avoid computing the list every time it is needed (i.e., for every connection), GnuTLS pre-computes this and store it in the credential structure. One credential structure can be associated with one or more TLS sessions.

We are now prepared to look at the code for generate_rdn_seq:

static int
generate_rdn_seq (gnutls_certificate_credentials_t res)
{
  gnutls_datum_t tmp;
  int ret;
  unsigned size, i;
  opaque *pdata;

  /* Generate the RDN sequence
   * This will be sent to clients when a certificate
   * request message is sent.
   */

  /* FIXME: in case of a client it is not needed
   * to do that. This would save time and memory.
   * However we don't have that information available
   * here.
   */

  size = 0;
  for (i = 0; i x509_ncas; i++)
    {
      if ((ret = gnutls_x509_crt_get_raw_dn
                      (res->x509_ca_list[i], &tmp)) x509_rdn_sequence.data != NULL)
    gnutls_free (res->x509_rdn_sequence.data);

  res->x509_rdn_sequence.data =
          gnutls_malloc (size);
  if (res->x509_rdn_sequence.data == NULL)
    {
      gnutls_assert ();
      return GNUTLS_E_MEMORY_ERROR;
    }
  res->x509_rdn_sequence.size = size;

  pdata = res->x509_rdn_sequence.data;

  for (i = 0; i x509_ncas; i++)
    {
      if ((ret = gnutls_x509_crt_get_raw_dn
                       (res->x509_ca_list[i], &tmp)) x509_rdn_sequence);
	  gnutls_assert ();
	  return ret;
	}

      _gnutls_write_datum16 (pdata, tmp);
      pdata += (2 + tmp.size);
      _gnutls_free_datum (&tmp);
    }

  return 0;
}

Take some time to read and understand this code. Really. I’ll be here waiting to explain it when you are finished.

The res->x509_ca_list variable contains the entire list of CA’s stored in memory so far. It is initially empty. After reading the first file, it will contain one certificate. After reading the second file, it will contain two certificates, and so on.

What is happening here is that FOR EVERY certificate to add, the entire list of certificates is iterated, not just once but twice! The computational complexity of invoking the function is O(2*n^2) where n is the number of certificate names to be added. The first iteration is to compute the size of the string to hold the CA names. The actual data is discarded. The second iteration calls the same function, for the same data, but now store the output in the appropriate place.

The first step to optimize this is to realize that you don’t need to iterate through all CAs every time a new one has been added. Adding the name for the most recently added certificate should be sufficient. Since more than one CA can be added at each time, the function needs to take another parameter: the number of recently added CAs for which to pre-compute the names for.

Our new code will look like:

static int
add_new_crt_to_rdn_seq (gnutls_certificate_credentials_t res, int new)
{
  gnutls_datum_t tmp;
  int ret;
  size_t newsize;
  unsigned char *newdata;
  unsigned i;

  /* Add DN of the last added CAs to the RDN sequence
   * This will be sent to clients when a certificate
   * request message is sent.
   */

  /* FIXME: in case of a client it is not needed
   * to do that. This would save time and memory.
   * However we don't have that information available
   * here.
   * Further, this function is now much more efficient,
   * so optimizing that is less important.
   */

  for (i = res->x509_ncas - new; i x509_ncas; i++)
    {
      if ((ret = gnutls_x509_crt_get_raw_dn
                        (res->x509_ca_list[i], &tmp)) x509_rdn_sequence.size +
                       2 + tmp.size;
      if (newsize x509_rdn_sequence.size)
	{
	  gnutls_assert ();
	  _gnutls_free_datum (&tmp);
	  return GNUTLS_E_SHORT_MEMORY_BUFFER;
	}

      newdata = gnutls_realloc
                        (res->x509_rdn_sequence.data, newsize);
      if (newdata == NULL)
	{
	  gnutls_assert ();
	  _gnutls_free_datum (&tmp);
	  return GNUTLS_E_MEMORY_ERROR;
	}

      _gnutls_write_datum16 (newdata +
            res->x509_rdn_sequence.size, tmp);
      _gnutls_free_datum (&tmp);

      res->x509_rdn_sequence.size = newsize;
      res->x509_rdn_sequence.data = newdata;
    }

  return 0;
}

I changed the function name, to reflect that it now just update the list of names for a set of recently added certificates. That also helps to find and update all callers of the old function.

As you can see, this function should be of complexity O(n) instead, since it just adds the name of the most recently added CA’s.

But is it faster in practice? Let’s check it! First, remove the if (i++ > 20) break; statement in the test code, so that we do the full test. First link against our old libgnutls.a and run the old test case again, for illustrative purposes.

jas@mocca:~$ gcc -o foo foo.c /usr/lib/libgnutls.a -lgcrypt -ltasn1 -lz
jas@mocca:~$ time ./foo

real 0m40.756s
user 0m40.679s
sys 0m0.052s
jas@mocca:~$

Again, it takes around 40 seconds. Now recompile against our modified libgnutls and run the same test:

jas@mocca:~$ gcc -o foo foo.c /home/jas/src/gnutls/lib/.libs/libgnutls.a -lgcrypt -ltasn1 -lz
jas@mocca:~$ time ./foo

real 0m0.288s
user 0m0.280s
sys 0m0.012s
jas@mocca:~$

Wow! Down from 40 seconds to 0.3 seconds. Let’s take a look at the callgrind output now.

The code now spends around 60 % of the time in add_new_crt_to_rdn_seq() which seems reasonable. There are 206 files in /etc/ssl/certs, which explains the call count. Some of the files actually contain several CA certificates (in particular /etc/ssl/certs/ca-certificates.crt contains a lot of certificates), which explains why gnutls_x509_crt_get_raw_dn is called 408 times.

At this point, I stopped optimizing the code further.

Syndicated 2008-02-26 23:17:45 from Simon Josefsson's blog

IDNA flaws with regard to U+2024

In a bug report against libidn, Erik van der Poel gives an example of an internationalized domain name that is handled differently by different implementation. Another example of one such string is:

‘räksmörgås’ U+2024 ‘com’

If your browser supports Unicode, the string is: räksmörgås․com. Use cut’n'paste of the string into your browser and see what it tries to lookup (please let me know what you notice!).

The problem with this string is that it is on the form “[non-ASCII][DOT-Like code point]com”. Here ‘räksmörgås’ represents the non-ASCII string, which can be any non-ASCII string. Further, the U+2024 represent one character which looks like a dot, there are others that also contain dot-like characters.

The IDNA algorithm (section 3.1) implies that applications should treat the string as one label. The U+2024 character is not one of the dot-like characters that needs to be treated as a label separator. The ASCII string which is output after applying the IDNA algorithm is:

xn--rksmrgs.com-l8as9u

Note that the string contains an ASCII dot ‘.’ (0×0E). If applications are not careful how they resolv the name in the DNS, they will request information in a non-existing top-level domain ‘com-l8as9u’. This is because the DNS do not use ‘.’ to separate labels, but instead uses a length-value pair for each label. Thus the wrong string to lookup would be:

(11)xn--rksmrgs(10)com-l8as9u

Whereas the right string to lookup would be:

(22)xn--rksmrgs.com-l8as9u

Using DNS master file syntax, the name to lookup is xn--rksmrgs\.com-l8as9u.

What’s interesting here is that some implementations, such as Microsoft Internet Explorer and Firefox implements IDNA not according to the standard. Instead, they compute the following string:

xn--rksmrgs-5wao1o.com

Arguable, this is a better approach than what is specified by RFC 3490. MSIE/Firefox recognize that U+2024 is a “dot-like” character, by using NFKC. What is debatable is whether U+2024 will actually occur in practice, Unicode expert Kenneth Whistler says U+2024 will not be entered accidentally.

As the maintainer of GNU Libidn, I’m not yet sure about what to do about the situation. The conservative approach is to do nothing until the RFCs are updated. I have come up with a patch to add a new IDNA flag that treat U+2024 as a dot-like character early on. This would at least make it possible to produce the same (RFC non-conforming) output that MSIE/Firefox computes.

Syndicated 2008-01-14 15:38:27 from Simon Josefsson's blog

PAM module for Yubico

During the autumn, in Yubico, we have been working on a PAM module for the Yubikey. It allows you to use the Yubikey to login to your machine, to unlock the screensaver, and so on. I decided to let Google Code host this project, which is the first time I’ve used them. It will be interesting to see how working with their site is going to turn out.

ObLink: code.google.com/p/yubico-pam/

You can buy Yubikeys on our web shop. If you have an interesting idea about what can be done with the key, let me know and I may be able to arrange a good deal for you. :)

Syndicated 2008-01-14 10:39:22 from Simon Josefsson's blog

6 older entries...

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!