Abstract

There are many well-known open-source cryptography libraries available, which implement many different ciphers. So which library and which cipher(s) should one use for a new program? This comparison presents a wealth of experimentally determined speed test results to allow an educated answer to this question.

The speed tests encompass eight open-source cryptography libraries of which 15 different ciphers are examined. The performance experiments were run on five different computers which had up to six different Linux distributions installed, leading to ten CPU / distribution combinations tests. Ultimately the cipher code was also compiled using four different C++ compilers with 35 different optimization flag combinations.

Two different test programs were written: the first to verify cipher implementations against each other, the second to perform timed speed tests on the ciphers exported by the different libraries. A cipher speed test run is composed of both encryption and decryption of a buffer. The buffer length is varied from 16 bytes to 1 MB in size.

Many of the observed results are unexpected. Blowfish turned out to be the fastest cipher. But cipher selection cannot be solely based on speed, other parameters like (perceived) strength and age are more important. However raw speed data is important for further discussion.

When regarding the eight selected cryptography libraries, one would expect all libraries to contain approximately the same core cipher implementation, as all calculation results have to be equal. However the libraries' performances varies greatly. OpenSSL and Beecrypt contain implementations with highest optimization levels, but the libraries only implement few ciphers. Tomcrypt, Botan and Crypto++ implement many different ciphers with consistently good performance on all of them. The smaller Nettle library trails somewhat behind, probably due to it's age.

The first real surprise of the speed comparison is the extremely slow test results measured on all ciphers implemented in libmcrypt and libgcrypt. libmcrypt's ciphers show an extremely long start-up overhead, but once it is amortized the cipher's throughput is equal to faster libraries. libgcrypt's results on the other hand are really abysmal and trail far behind all the other libraries. This does not bode well for GnuTLS's SSL performance. And libmcrypt's slow start promises bad performance for thousands of PHP applications encrypting small chunks of user data.

Most of the speed test experiments were run on Gentoo Linux, which compiles all programs from source with user-defined compiler flags. This contrasts to most other Linux distributions which ship pre-compiled binary packages. To verify that previous results stay valid on other distributions the experiments were rerun in chroot-jailed installations. As expected Gentoo Linux showed the highest performance, closely followed by the newer versions of Ubuntu (hardy) and Debian (lenny). The oldest distribution in the test, Debian etch, showed nearly 15% slower speed results than Gentoo.

To make the results transferable onto other computers and CPUs the speed test experiments were run on five different computers, which all had Debian etch installed. No unexpected results were observable: all results show the expected scaling with CPU speed. Most importantly no cache effects or special speed-ups were detectable. Most robust cipher was CAST5 and the one most fragile to CPU architecture was Serpent.

Most interesting for applications outside the scope of cipher algorithms was the compiler and optimization flags comparison. The speed test code and cipher library Crypto++ was compiled with many different compiler / flags combinations. It was even compiled and speed measured on Windows to compare Microsoft's compiler with those available on Linux.

The experimental results showed that Intel's C++ compiler produces by far the most optimized code for all ciphers tested. Second and third place goes to Microsoft Visual C++ 8.0 and gcc 4.1.2, which generate code which is roughly 16.5% and 17.5% slower than that generated by Intel's compiler. gcc's performance is highly dependent on the amount to optimization flags enabled: a simple -O3 is not sufficient to produce well optimized binary code. Relative to gcc 4.1.2 the older compiler version 3.4.6 is about 10% slower on most tests.

All in all the experimental results provide some hard numbers on which to base further discussion. Hopefully some of the libraries' spotlighted deficits can be corrected or at least explained. Lastly the most concrete result: the cipher and library I will use for my planned application is Serpent from the Botan library.

Nachdem ich in der letzten Woche die Prüfung zu Algebra 2 abgelegt habe, betrachte ich nun das dazugehörige Skript auch als abgeschlossen.

Zu der Vorlesung im Sommersemester 2006 entstand kooperativ per Internet eine LaTeX-Mitschrift. Das gemeinsame Mitschreiben/Nach-TeXen wurde möglich durch das LaTeX-Wikisystem latexki von Joachim Breitner. Auf dem Mitschrieb-Wiki haben damals verschiedene Leute zusammen das LaTeX kapitelweise zusammengestellt. Ich habe ungefähr sechs Vorlesungen dazu beigetragen.

Irgendwann hatte ich damals einen lokalen Branch der LaTeX Dateien mittels SVK angefangen. Dafür gab es verschiedene Gründe. Insbesondere war lokales Editieren der LaTeX-Dateien mit XEmacs sehr viel bequemer als online im Browser-Formularfeld. Außerdem war das Einbinden von externen EPS/PDF Graphiken auf dem Wiki-System leider nicht möglich. Ich hatte auch andere Vorstellungen vom optischen Seitenlayout und Schriften, welche das LaTeX-Wiki nicht akzeptierte.

Der Branch ist dann permanent geworden und ich habe beim Lernen sehr, sehr viele kleine Fehler im Skript gefunden und einige kurz gefasste Stellen ergänzt. Leider ist es nicht mehr möglich die Änderungen auf das Wiki hochzuladen, da einige Neuerungen insbesondere die Graphiken nicht unterstützt werden und die ganzen anderen kleinen Änderungen nur noch schwer nachvollziehbar sind.

Darum gibt es hier meine (private) Version des Mitschrieb-PDFs und des LaTeX-Quellcodes.

Das fertig kompilierte Skript Algebra2.pdf ist 611 kB groß.

Der LaTeX-Code zum Skript ist in eine Hauptdatei und kleine Kapitel-Dateien aufgeteilt. Die folgenden Links führen zum Quellcode mit Syntaxhighlighting.

Da ich mein altes Algebra 1 Skript zusammen mit dem neuen Algebra 2 Skript zu einem kleinen Buch binden wollte, habe ich noch ein Deckblatt-PDF (Cover-Algebra12.pdf) für die beiden Teile angefertigt.

Released a bugfix version 0.8.1 of the STX B+ Tree C++ Template Classes package. The bug fixed is a possibly illegal memory access during find() function.

I received a new test case via email in which valgrind detected an uninitialized memory access. By tracing it, I soon found that it happens during any find(key) call with a key that is larger than any item contained in the tree. During the find() function find_lower() is called on a leaf node and returns the slot number with the smallest or equal key. However if the queried key is larger than all keys in a leaf node or in the whole tree, find_lower() returns a slot number past the last valid key slot. Comparison of this invalid slot with the queried key then yields an uninitialized memory error in valgrind.

The updated source code package including the wxBTreeDemo source is available for download from this webpage.

Some compiled binaries of wxBTreeDemo for Win32 and Linux are available on the demo download page.

As before, the updated main B+ tree implementation can be found in doxygen stx/btree.h or with plain text comments stx/btree.h.

While stumbling around the web, today I found some fantastic instrumental classic-metal music. Listening into some random web music streams, I heard a piece that immediately matched my music taste. That taste is maybe best described as symphonic epic metal, though I'm generally against over-detailed (music) categorization.

Consequently I entered the song's name into Amazon's search, but nothing was found. Some googling revealed that the song is downloadable for free: http://www.cryofdolour.ru - (download page)

It is part of a complete album of similar pieces composed by this Russian musician who signed the page with RAO. The pieces combine classic music motifs with metallic drumming and guitars. Sounds impossible, yet the songs masterfully weaved both styles together creating a bombastic epic expression. Yes, the songs are all instrumental, and yes, you need some patience for the first track. Having heard the pieces over and over again, I soon noticed that while the musical composition is excellent the tracks' sound itself does not reach usual CD production quality. They sound a bit synthetic and miss some bass blast. But hey, it's free.

Original, incredible music by an unknown artist! My three favourite tracks are: "Hymn to Solitude", "Dies Irae", "It is Coming" and "Prelude". Ah, that is now four and I still missed some of the best. Just hear them yourself.

If you also have no clue as to what the Russian text on the main page is about, I suggest reading Google's translation of that page.

The idea strikes me as very strange: to take the impossible figures sketched by Escher and build Lego models of them.

Someone actually took up this seemingly "impossible" feat. Yesterday I found their pictures of "Relativity", of which I have a poster on the wall left of my PC. I've had some long looks at the poster. So the minute details of the Lego reconstruction interested me immediately. Due to the studs of (standard) Lego tiles pointing in only one direction they had to leave out a few railings, which help form the twisted triangle's composition lines. Each of the red Lego men are at the correct place and hold the correct action props. Sweetest are the Lego flowers and plants positioned at the picture's upper left, lower right and center. A very good job indeed.

Released example source code package Flex Bison C++ Example. The example source code is released into the public domain or, at your option, under the Do What The Fuck You Want To Public License (WTFPL).

This example shows how to use both Flex and Bison in C++ mode. This way both lexer and parser code and data is encapsulated into classes. Thus the lexer and parser are fully re-entrant, because all state variables are contained in the class objects. Furthermore multiple different lexer-parser pairs can easily be linked into one binary, because they have different class names and/or are located in a different namespace.

Why Use These Old Tools? Well, they are here to stay and they work well. But most important, the code generated by Flex and Bison requires no compile-time dependencies, because they generate fully autonomous source code. So far I have not found any modern parser generator which outputs independent code. It is even possible to compile the generated source on Windows with Visual C++ 2005.

For more information and the download package see the Flex Bison C++ Example web page.

Released the first version 0.7 of the STX Expression Parser C++ Framework package. The library is licensed under the GNU Lesser General Public License (LGPL) (2.1 or later).

The STX Expression Parser provides a C++ framework, which can process user-specified expression strings containing program-specific variables. It can be integrated into applications to allow user-customized data selection and filtering. The expresssion strings are intuitive SQL-like WHERE-clauses and can contain arbitrarily complex arithmetic. At the same time the expression processing time is guaranteed to be fast enough to safely iterate over larger data sets.

The expression parser can process arbitrarily complex arithmetic expressions like those seen below. To access application-defined data, functions and variables may be included in the expression. An expression can be used as a boolean filter by using comparison and logic operators.

• 6 + 3 * 12
• a == 6 * 9
• (a - 28) * (int)(e + 0.4 * 2.5 / (PI() - EXP(-0.644) * 4))
• a >= 5 OR (42 <= field2 AND field2 <= 48) || NOT(got == "yes")

For more information see the STX Expression Parser web page.

Most impressive are the interactive online CGI parser demo and the online CSV file filter.

Online-Durchsuchungen sind zur Zeit wieder auf der politischen Tagesordnung, denn "Das Internet ist das entscheidende Kommunikationsmittel des internationalen Terrorismus [...]" (Zitat vom BKA-Chef auf tagesschau.de).

Windows wird aber nicht in Deutschland entwickelt und daher kann das BKA nur schwer bei Microsoft ein eigenes Backdoor beantragen. Das (angeblich) bereits vorhandene Backdoor der NSA kann wohl rechtsstaatlich nicht verwendet werden.

Daher ist es notwendig ein "Bundestrojaner" auf den zu untersuchenden Rechnern zu installieren. Dieses (Schad-)Programm soll dann vom BKA ferngesteuert die Festplatten durchsuchen.

Auf www.bundestrojaner.net gibt es bereits eine Betaversion zum Ausprobieren. Nein, nicht wirklich: es ist eine mit vielen politischen Sprüchen aufgemachte Satire-Webpage. Durch Appelle an unseren Patriotismus und Glauben an rechtsstaatlichen Grundsätze wird man aufgefordert den "Bundestrojaner" herunterzuladen und sich freiwillig durchsuchen zu lassen. Hier einige Zitate:

Leider ist das downloadbare Programm nicht sehr ausgereift: es zeigt (anscheinend) nur eine kurze Slideshow-Sequenz und bittet den Benutzer um "Geduld, Ihre Daten werden übertragen".

Außerdem hat der CCC am 1. April diesen Jahres bereits den "Bundestrojaner" ausgemacht: in der Elster-Software des Finanzamts.

This post completes the small C++ function collection of simple STL string manipulations. The following code snippet shows simple locale-unware uppercase and lowercase conversion functions using tolower and toupper. Nothing revolutionary; I'm just misusing this weblog as a code-paste dump for reuseable code.

Sometimes it is better to have a case-insensitive string class. More about ci_string can be found at Guru of the Week (GotW) #29: Case-Insensitive Strings.

#include <string>
#include <cctype>

// functionals for std::transform with correct signature
static inline char string_toupper_functional(char c)
{
    return std::toupper(c);
}

static inline char string_tolower_functional(char c)
{
    return std::tolower(c);
}

static inline void string_upper_inplace(std::string &str)
{
    std::transform(str.begin(), str.end(), str.begin(), string_toupper_functional);
}

static inline void string_lower_inplace(std::string &str)
{
    std::transform(str.begin(), str.end(), str.begin(), string_tolower_functional);
}

static inline std::string string_upper(const std::string &str)
{
    std::string strcopy(str.size(), 0);
    std::transform(str.begin(), str.end(), strcopy.begin(), string_toupper_functional);
    return strcopy;
}

static inline std::string string_lower(const std::string &str)
{
    std::string strcopy(str.size(), 0);
    std::transform(str.begin(), str.end(), strcopy.begin(), string_tolower_functional);
    return strcopy;
}

Yesterday I once again stumbled upon whitespace trimming of STL strings: a check was required if the given user input is empty. Where "empty" also means some user-given string containing only spaces. After one hour of unproductive searching for something as simple as a space trimming function, I decided to put the resulting code here for future reference.

The following code snippet contains two versions of the function: in-place trimming and string-copy trimming. I prefer the copy-trimming function because they allow a more functional programming style. The functions only trim spaces, but can be modified by replacing each ' ' with something like " \n\r\t".

#include <string>

static inline void string_trim_left_inplace(std::string &str)
{
    str.erase(0, str.find_first_not_of(' '));
}

static inline void string_trim_right_inplace(std::string &str)
{
    str.erase(str.find_last_not_of(' ') + 1, std::string::npos);
}

static inline std::string string_trim_left(const std::string &str)
{
    std::string::size_type pos = str.find_first_not_of(' ');
    if (pos == std::string::npos) return std::string();

    return str.substr(pos, std::string::npos);
}

static inline std::string string_trim_right(const std::string &str)
{
    std::string::size_type pos = str.find_last_not_of(' ');
    if (pos == std::string::npos) return std::string();

    return str.substr(0, pos + 1);
}

static inline std::string string_trim(const std::string& str)
{
    std::string::size_type pos1 = str.find_first_not_of(' ');
    if (pos1 == std::string::npos) return std::string();

    std::string::size_type pos2 = str.find_last_not_of(' ');
    if (pos2 == std::string::npos) return std::string();

    return str.substr(pos1 == std::string::npos ? 0 : pos1,
                      pos2 == std::string::npos ? (str.length() - 1) : (pos2 - pos1 + 1));
}

static inline void string_trim_inplace(std::string& str)
{
    std::string::size_type pos = str.find_last_not_of(' ');
    if(pos != std::string::npos) {
        str.erase(pos + 1);
        pos = str.find_first_not_of(' ');
        if(pos != std::string::npos) str.erase(0, pos);
    }
    else
        str.erase(str.begin(), str.end());
}