Qbi's Weblog

Kürzlich ging eine Erschütterung durch die Welt der Kryptografie. Das Paper Quantum Algorithms for Lattice Problems versprach einen neuen Angriff gegen bestimmte Algorithmen. Diese heißen Learning-With-Errors (LWE) und bilden eine Grundlage für Algorithmen, die gegen Quantencomputer sicher sein sollen. Hier spielt eine Menge Mathematik mit hinein. Als Beispiel seht ihr eine halbe Seite aus dem Paper:

Das Thema klang hinreichend interessant und ich wollte mich ein wenig einlesen. Zum konkreten Paper muss man sagen, dass mittlerweile ein Fehler im Algorithmus gefunden wurde und die Autoren schreiben:

Now the claim of showing a polynomial time quantum algorithm for solving LWE with polynomial modulus-noise ratios does not hold.

Beim Lesen fiel mir wieder etwas auf, was mir schon früher auffiel. Es gibt Sätze, die kommen recht unschuldig daher und klingen leicht verständlich. Dennoch steckt soviel Theorie dahinter, dass es eine Weile dauern könnte, um diese zu durchdringen.

Gleich in der Einführung findet sich ein Beispiel: An n-dimensional lattice L is a discrete additive subgroup of ℝⁿ. (Ein n-dimensionales Gitter L ist eine diskrete additive Untergruppe von ℝⁿ.)

Welche Begriffe muss man verstehen oder interpretieren können, um die Definition zu verstehen?

1. n-dimensional
2. diskrete additive Untergruppe
3. ℝⁿ

Das heißt, nahezu jedes Wort ist erklärungsbedürftig und mit Schulwissen kaum zu durchdringen. Wenn wir jetzt die Wikipedia konsultieren, kommen wir ein Stück weiter. Dort findet sich auch eine Definition des Gitters als diskrete Untergruppe eines euklidischen Raums sowie einige Beispiele. Wenn wir beide Definitionen vergleichen, steht in dem Paper zusätzlich das Wort additiv und anstatt euklidischer Raum wird von ℝⁿ gesprochen. Aus der Wikipedia-Seite zum euklidischen Raum wird schnell klar, dass ℝⁿ ein euklidischer Raum ist. Also sind beide Definitionen ähnlich. Das heißt, mit kleinen Einschränkungen können wir mit der Wikipedia-Definition weiterarbeiten.

Um den Satz nun zu verstehen, sollten wir uns dem zweiten Begriff, der diskreten additiven Untergruppe, zuwenden. Beim Aufdröseln ergeben sich neue Begriffe, die man entweder kennen oder lernen muss.

• Untergruppe
  • Eine Untergruppe hat eine Verknüpfung (Addition, Multiplikation etc.) und bildet eine Gruppe.
    • Eine Gruppe ist eine Menge mit einer Verknüpfung (Addition, Multiplikation etc.). Bei der Verknüpfung ist es egal, wie man Klammern setzt (Assoziativgesetz), es gibt ein so genanntes neutrales Element und ein inverses Element. Wenn man ein neutrales Element verknüpft, ändert sich nichts, so wie bei einer Addition mit 0. Wenn man ein Element der Menge mit dessem inversen Element verknüpft, erhält man das neutrale Element (12-12=0 bei der Addition, -12 ist das inverse Element).
• Additive Untergruppe
  • Das ist eine Untergruppe, wo die Verknüpfung Addition heißt.
• Diskrete Untergruppe
  • Eigentlich geht es hier um diskrete Teilmengen eines Raumes mit der zusätzlichen Eigenschaft, dass diese Teilmenge eine Untergruppe bildet.
  • Eine Teilmenge ist, wie der Name schon sagt, ein Teil der Menge.
  • Diskret bedeutet nun, dass jedes Element der Menge eine Umgebung hat, dass kein weiteres Element der Teilmenge enthält. Das heißt, die einzelnen Elemente der Menge sind isolierte Punkte.
  • Die ganzen Zahlen …, -2, -1, 0, 1, 2, … sind als Teilmenge der reellen Zahlen eine solche Menge. Denn bei jeder Zahl gibt es nach links und rechts einen Abstand, wo sich keine andere Zahl drin findet. Bei den Brüchen (rationale Zahlen) ist das anders. Dort finden sich keine zwei Zahlen mit einem kleinen Abstand, dass keine andere rationale drin läge. Daher ist das keine diskrete Teilmenge.
• ℝⁿ
  • ℝⁿ ist der n-dimensionale Raum der reellen Zahlen. Aus der Schule kennt man ℝ¹ (Zahlenstrahl), ℝ² (Zahlenebene) und ℝ³ (dreidimensionaler Raum).

Damit haben wir alle Bauteile zusammen, um den obigen Satz zu verstehen. Wobei ich zugeben, muss, dass ich oben einige Abkürzungen genommen habe und auf intuitives Verständnis gesetzt habe. Dennoch reicht das in der Mathematik oftmals nicht. Es ist sinnvoll, sich Beispiele auszudenken. Diese sollten sowohl den positiven Fall abdecken (erfüllt die Definition), aber auch den negativen Fall (erfüllt die Definition nicht). Das sorgt dann wirklich für ein Verständnis des Ganzen.

Das war es auch, was ich am Anfang meinte, als ich von dem kleinen unschuldig klingenden Satz schrieb. Um den zu verstehen, muss man entweder tief im irgendwann mal Erlernten graben oder neues lernen und es dauert eine längere Zeit, bis man ein Paper einmal durchgearbeitet hat. Noch viel länger dauert es, bis man es verstanden hat.

Der obige Satz war der Einstieg in das Paper und nur die Einleitung. Später geht es um gaussche Funktionen und Fouriertransformationen. Das sind Konzepte über die es semesterlange Vorlesungen gibt. Das heißt, um das zu verstehen, kann man wirklich aus den Tiefen der Mathematik schöpfen. Ich wünsche euch viel Spaß bei der Lektüre.

Mit dem Paper haben sich einige andere auseinandergesetzt. Hier findet ihr interessante Lektüre dazu:

• Implications of the Proposed Quantum Attack on LWE
• A quick post on Chen’s algorithm

Ich hatte heute den verwegenen Plan und wollte die Webseite des sächsischen Landtages per HTTPS aufrufen. Der Browser stoppte mich und zeigte eine schöne Fehlermeldung:

Fehlermeldung zum Zertifikat von edas.landtag.sachsen.de

Also dem Zertifikat traut der Browser nicht. Außerdem fehlen dem weitere Bestandteile. Das Zertifikat ist eigentlich für eine andere Domain und schon längst abgelaufen.

Hier frage ich mich, ob jemand schon mal eine Liste von Zertifikatsfehlern gesehen hat, die länger ist, als die obige.

Das wunderbare Projekt »Chaos macht Schule« des CCC versucht, Medienkompetenz und Technikverständnis von Kindern und Jugendlichen zu fördern. Verschlüsselung gehört mit in diesen Bereich und Bruce Schneier wies kürzlich auf ein Gerät hin, das in jedes Kinderzimmer gehört.

Von Mattel gibt es eine Schreibmaschine für Kinder, die eine einfache Verschlüsselung beherrscht. Das Modell E-118 wird von der slowenischen Firma Mehano hergestellt. Mittels der Tastenkombination Shift-Lock und 1, 2, 3 oder 4 wird die Verschlüsselung aktiviert. Die Nachricht kann dann über die Tastatur eingegeben werden und die Maschine druckt den Geheimtext aus. Die Schreibmaschine führt dabei eine einfache Ersetzung (Substitution) aus. Aber für einen Einstieg in die Welt der geheimen Kommunikation ist das sicher sehr gut.

• Barbie™ Typewriter
• Neues zur verschlüsselnden Barbie-Schreibmaschine

Was hat der Text NDXOXCHWDRGHDXORVI zu bedeuten? Diese Frage stellt das British Museum sich und der Allgemeinheit.

Ein etwa 700 Jahre altes Schwert wird derzeit ausgestellt. Auf der Klinge findet sich die obige Inschrift. Laut der Webseite des Museums vermutet man, dass es die Initialen einer religiösen Handlung darstellt. So steht die Abkürzung ND für Nostrum Dominus (unser Herr) und das X könnte für Christus stehen.

Das Museum ist an weiteren Deutungen sehr interessiert. Wenn ihr etwas wisst oder ahnt, wendet euch an das Museum.

via Ancient Origins: Medieval Sword contains Cryptic Code. British Library appeals for help to crack it.

Mehr als zwanzig Jahre ist es nun her, als sich eine Gruppe von Leuten auf einer Mailingliste »traf«. Die Cypherpunks diskutierten in den folgenden Jahren Kryptografie, Anonymität und andere Techniken zum Schutz der Privatsphäre. Letztlich ist über verschiedene Ecken auch Bitcoin ein Produkt der Cypherpunks-Zeit. Allerdings diskutierten die Teilnehmer nicht nur, sondern viel wichtiger, sie programmierten. Ein Spruch aus den Zeiten lautet: »Cypherpunks write code.«

Nun fand ich eine E-Mail in meiner Inbox, die das erneute Aufleben der Mailingliste ankündigte. Und prompt trudelten hier einige E-Mails ein. Wer also an den Themen Kryptografie, Politik und Privatsphäre interessiert ist, kann sich dort eintragen. Allerdings kamen früher recht viele E-Mails über die Liste und auch in den letzten Tagen erhielt ich recht viele Nachrichten. Ihr solltet also mit eurem E-Mail-Client gut filtern.

Ich bin gespannt, ob die Liste neuen Drive gewinnt. Immerhin habe ich durch die Diskussion der letzten Tage ein paar Zufallszahlenerzeuger für den Rechner kennengelernt und habe nun was zum Testen.

Die beiden Kryptografen Shafrira »Shafi« Goldwasser und Silvio Micali erhalten den ACM Turing Award. Das ist so eine Art Nobelpreis in der Informatik. Goldwasser und Micali sind vermutlich nur Insidern bekannt. Sie lieferten allerdings wesentliche Beiträge zur Kryptografie. Die Begriffe der Semantic Security und Ununterscheidbarkeit eines Algorithmus’ vom Zufall gehen auf die Forscher zurück. Sie legten damit die Grundlagen für eine Formalisierung des Wissenschaftszweiges. Ich gratuliere beiden Wissenschaftlern für die Auszeichnung!

Pressemitteilung der ACM

Patrick Beuth hat für die ZEIT ein Experiment gemacht. Er stellte sich die Frage, wie schwierig es für Laien ist, sich anonym und sicher zu bewegen. Diese Erfahrungen schrieb Beutch in der Serie »Mein digitaler Schutzschild« nieder. Für das Experiment kaufte er sich einen neuen Rechner und installierte Ubuntu. Später machte er sich Gedanken zu sicheren Verbindungen über VPN und Tor, nutzte E-Mail-Verschlüsselung mit OpenPGP und verschlüsselte die Festplatte. Die Artikel sind aus der Sicht eines neuen Benutzers geschrieben und sehr interessant zu lesen.

• Mein digitaler Schutzschild
• Ubuntu – die Basis für einen sicheren Computer
• Tor – die Tarnkappe fürs Netz
• VPN – durch einen Tunnel ins Internet
• Hushmail – auch E-Mails können anonym sein
• OpenPGP – E-Mails verschlüsseln, damit sie keine Postkarten mehr sind
• TrueCrypt – der Tresor auf der Festplatte

ZEIT Online macht sogar den Sprung vom Artikel in die Praxis und organisiert am 26. Februar eine CryptoParty. Dort zeigen Patrick Beuth und die Organisatoren der CryptoPartys in Berlin, wie die verschiedenen Werkzeuge zu benutzen sind. So wird die anfängliche Hürde, derartige Werkzeuge zu benutzen sicher kleiner.

Woody Guthrie mit Gitarre (Quelle: Wikipedia bzw. Library of Congress)

Der Titel des Buches klingt spektakulär: »Die Maschine, die Geheimnisse vernichtet«. Der Journalist Andy Greenberg berichtet im gleichnamigen Buch von dieser Maschine und hat an vielen Stellen spektakuläres zu berichten. Greenberg kam durch die Gitarre von Woody Guthrie auf den Titel. Die Gitarre trug den Aufkleber: »This machine kills fascists« (siehe Bild).

Die Maschine, die Geheimnisse vernichtet, beginnt mit den Pentagon-Papers ihr Werk. Daniel Ellsberg veröffentlichte die geheimen Dokumente damals mit Hilfe der NY Times. Julian Assange und neuere Entwicklungen sind noch lange nicht das Ende der Maschine. Vielmehr wird sie wohl lange weiterleben. Das Buch zeichnet den Weg der Maschine nach.

Im Prolog wird ein Treffen mit Julian Assange beschrieben. Julian kündigt dort die MegaLeaks an und verspricht einen Leak über eine US-Bank. Der erste Teil startet mit einer Gegenüberstellung von Ellsberg und Bradley Manning. Greenberg vergleicht im Kapitel »The Whistleblowers« ihre Herkunft und ihr Vorgehen. Ellsberg hatte seinerzeit die Berechtigung sehr geheime Dokumente zu lesen. Ein Privileg, was nur wenige mit ihm teilten. Manning auf der anderen Seite war einer von 2,5 Millionen Amerikanern, die aufgrund lascher Voreinstellungen auf viele geheime Dokumente Zugriff hatten. Beide waren der Meinung, dass »ihre« Dokumente an die Öffentlickeit müssen. Ellsberg war sich sicher, dass er für die Veröffentlichung der Pentagon-Papiere für den Rest seines Lebens im Gefängnis landen würde. Manning, auf der anderen Seite, schien Hoffnung zu hegen, dass er unerkannt davon kommt. Zumindest arbeitet Greenberg diesen Punkt im Buch heraus. Die realen Entwicklungen waren jedoch genau gegenteilig. Ellsberg wurde nicht bestraft und Manning wird aller Voraussicht nach lange Zeit im Gefängnis bleiben.

Das erste Kapitel ist sehr schön geschrieben. Man merkt hier schon, wie gut Greenberg seine Geschichte recherchiert hat. Mit der Gegenüberstellung der beiden Protagonisten gelingt ihm ein schöner Spannungsaufbau.

Cover des Buches

Die folgenden drei Kapitel widmen sich der »Evolution of Leaking«. Greenberg erzählt die Geschichte der Cypherpunks detailliert nach. Den Startpunkt bilden dabei die Lebensläufe von Tim May und Phil Zimmerman, der Erfinder von PGP. Mit Geschichten zu Julian Assange und John Young, dem Gründer von Cryptome geht es weiter. Schließlich spielen die Diskussionen auf der Mailingliste und der Artikel »Assassination Politics« von Jim Bell eine Rolle. Der Keynote-Sprecher des 29C3, Jacob Appelbaum, mit dem Tor-Projekt bilden den Abschluss.

Der dritte Teil hat die Zukunft (»The Future of Leaking«) zum Gegenstand. Dort geht es um »Plumbers«, »Globalizers« und »Engineers«. Das Kapitel beginnt mit Peiter Zatko. Mudge, wie er sich nannte, war einer der Köpfe der Hacker-Gruppe Cult of the Dead Cow und hatte engere Kontakte zu Assange. Mittlerweile arbeitet er bei der DARPA und soll Gegentaktikten zum Leaking entwickeln. Das langfristige Ziel des Projektes ist, Leaking komplett zu unterbinden. Greenberg beschreibt im Kapitel HBGary und den Anonymous-Hack sehr lebendig. Der Autor nutzt IRC-Logs und persönliche Gespräche und kann dadurch eine sehr detaillierte Sicht auf die Dinge bieten. Die Isländische Initiative zu modernen Medien (IMMI) und BalkanLeaks sind die Vorboten der Zukunft. Schließlich traf Greenberg zufällig den Architekten. Derjenige, der nur unter dem Namen »Der Architekt« agiert, war für die sichere Neugestaltung von WikiLeaks zuständig und arbeitet jetzt bei OpenLeaks. Greenberg traf ihn zufälligerweise beim Chaos Communication Camp.

Am Ende des Buches steht ein kurzer Abschnitt zur »Machine«. Greenberg macht klar, dass heute jeder zum Leaker werden kann. Mobiltelefone und andere elektronische Gegenstände erlauben es, Reportagen von Ereignissen anzufertigen oder eine Vielzahl elektronischer Dokumente zu kopieren. GlobaLeaks wird kurz beleuchtet. Das Projekt baut an einer Lösung für eine Leakingplattform mit Freier Software. Greenberg schließt mit den Worten:

We don’t yet know the names of the architects who will build the next upgrade to the secret-killing machine. But we’ll know them by their work.

Ich habe es sehr genossen, das Buch zu lesen. Zum einen hat Greenberg einen schönen, lebendigen Schreibstil. Obwohl ich viele Aspekte der Geschichten kannte, hatte das Buch einiges Neues zu bieten. Faktisch auf jeder Seite ist die gute Recherchearbeit des Autors zu spüren. Es war spannend für mich den Handlungssträngen zu folgen. »This machine kills secrets« war eines der Bücher, was ich nur schwer aus der Hand legen konnte und am liebsten am Stück durchgelesen hätte. Leseempfehlung!

Wer von euch einen Verlag kennt, der das Buch ins Deutsche übersetzen will, kann sich gern an mich oder an Andy Greenberg wenden.

In aller Welt finden momentan so genannte CryptoPartys statt. Diese sollen in einer entspannten Atmosphäre Nutzer über verschiedene Aspekte von Kryptografie bzw. Anwendungen aufklären. Die erste CryptoParty in Jena steht vor der Tür. Am kommenden Freitag, dem 23. November 2012, startet im Krautspace eine CryptoParty. Ich werde dort ein paar Worte zu Kryptografie im Allgemeinen verlieren und später tiefer in Richtung OTR eintauchen. Vermutlich werde ich nur die theoretische Seite erklären können, da es im Krautspace immer noch kein Internet gibt. Weitere Vorschläge sind im Wiki unter dem Punkt Inhalte aufgelistet. Die Veranstaltung findet nach dem Prinzip der Barcamps statt. Das heißt, wer will, kann einen Vortrag oder Workshop halten.

Ich würde mich freuen, wenn recht viele zu der Veranstaltung kommen und sich von den Vorteilen der Kryptografie überzeugen lassen. Vermutlich sind auch Reporter von Dradio Kultur anwesend. Also seid darauf gefasst, interviewt zu werden.

Update: Kleinen Fehler beseitigt. Vielen Dank an fpunktk

Das National Institute of Standards and Technology (NIST) gab heute bekannt, wer den SHA-3-Wettbewerb gewonnen hat: Keccak. Der Algorithmus wird nun die neue Empfehlung für einen kryptografischen Hash. Er stammt von den Forschern Guido Bertoni, Joan Daemen, Michaël Peeters und Gilles Van Assch. Besonders erwähnenswert ist Daemen. Denn er war schon für den Verschlüsselungsalgorithmus AES zuständig, der vor mehr als zehn Jahren standardisiert wurde.

Die bisher oft genutzten Algorithmen benutzen das so genannte Merkle-Damgård-Verfahren. Keccak geht einen neuen Weg (cryptographic sponge). Das erinnert mich ein wenig an AES. Denn auch damals kamen die Standardisierer von dem Feisteldesign ab.

Daniel Bernstein hat Benchmarks für verschiedene Algorithmen auf verschiedenen Plattformen gemacht. Nach der Seite ist beispielsweise BLAKE wesentlich schneller als Keccak. Im Allgemeinen scheint SHA-3 in Hardware gegossen schneller als SHA-2 zu sein. Aber die Softwarevariante ist wesentlich langsamer. Mal sehen, was die nächsten Tage ergeben. Aber momentan kann man wohl Bruce Schneier recht geben, der mal sagte, dass niemand SHA-3 nutzen wird. Nichtsdestotrotz: Alles Gute zur Wahl.

Der Mathematiker John Nash wird einigen aus dem Spielfilm A beautiful mind bekannt sein. Dort wird sein Leben (zum Teil etwas ungenau) nachgezeichnet. Noch heute ist der Begriff des Nashgleichwichts in der BWL und der Informatik wichtiger Lehrstoff. Vor kurzem veröffentlichte die NSA einen Brief von Nash (lokale Kopie), den er 1955 an den Geheimdienst schrieb.

In dem Brief beschreibt Nash ein Kryptosystem, oder Ver-/Entschlüsselungsmaschine. Es ist unklar, inwieweit die NSA hierauf reagiert hat. Dennoch äußert Nash einige grundlegende Ideen. Ron Rivest hat für seinen Krypto-Kurs eine Implementation in Python geschrieben. Wer es mag, kann ja eine Kryptoanalyse versuchen. :-) 

 via Turing's Invisible Hand: John Nash's Letter to the NSA

Update: Link aktualisiert und lokale Kopie eingebaut

Als ich das Buch zur Anonymität im Internet schrieb, gab es eine Person, die mir immer wieder „über den Weg“ lief. Len Sassaman hatte sehr früh Probleme beim Cypherpunk-Remailer gefunden und daraufhin Mixmaster mit entwickelt. The Pynchon Gate war eines der Ideen aus jüngerer Zeit, welches Len zusammen mit Nick Matthewson vom Tor Project und Bram Cohen von BitTorrent entwickelte. Len bat mich damals, eine Beschreibung mit in das Buch aufzunehmen. Die Zeit war jedoch zu kurz, um eine ordentliche Beschreibung einzubauen.

Im Laufe der Zeit sah ich Len Sassaman immer mal wieder auf Konferenzen. Wir unterhielten uns und ich lernte ihn sehr zu schätzen. Denn neben der Tatsache, dass er wirklich ein Fachmann auf seinem Gebiet war, war er ein unheimlich, hilfsbereiter Mensch.

Umso schockierter war ich, als ich gestern eine Twitter-Nachricht seiner Frau Meredith las. Sie schrieb, dass sie gerade mit der Polizei wegen seines Selbstmordes telefoniert hatte. Was zuerst noch wie ein schlechter Scherz klang, hat sich bestätigt. Len Sassaman ist aus dem Leben geschieden. Lebe wohl!

Bild von Wikipedia (Benutzer:AlexanderKlink)

Jetzt ist es endlich soweit. Die letzte Runde im Wettbewerb um einen neuen Hash-Standard wurde eingeläutet. Fünf Kandidaten gehen in die letzte Runde:

• BLAKE
• Grøstl
• JH
• KECCAK und
• Skein

Bis zum Januar nächsten Jahres besteht nochmals die Möglichkeit, die Hashes zu verbessern. Dann gibt es wieder Konferenzen und schließlich steht dann bald die Wahl einer neuen Hashfunktion vor der Tür.

Schönen guten Tag, die von Ihnen entwickelte Verschlüsselung ist zu sicher. Bauen Sie bitte eine Hintertür ein. Sie bekommen von uns steuerfrei n Millionen US-Dollar. Solche Gespräche kennt man üblicherweise aus diversen Agentthrillern. Der Chef der tschechischen Firma CircleTech hat das nun am eigenen Leib erlebt.

Die Firma stellt Verschlüsselungslösungen her. Im Jahr 2006 meldeten Heise, Golem und andere, dass die Firma mit SMS007 eine Java-Anwendung hat. Diese verschlüsselt Kurznachrichten. Die Webseite der Firma listet weitere Produkte.

Nun bekam CircleNet Besuch vom Bezpe?nostní informa?ní služba oder kurz BIS. Das ist der Inlandsgeheimdienst von Tschechien. Die Geheimdienstleute wollten eine Hintertür im Programm haben. Damit soll der BIS dann alle Nachrichten entschlüsseln können. Einer der Firmengründer zeichnete das Gespräch auf und dort ist unter anderem zu hören, dass der Firma steuerfreie Einnahmen versprochen wurden. Nachdem sie nicht darauf einging, gab es weitere Erpressungsversuche.

Der Prague Monitor meldet, dass der Vorfall vom BIS untersucht wird. Angeblich liegen derartige Deals außerhalb der Kompetenzen des Dienstes.

Es wäre gut, wenn ich tschechisch könnte. Denn die meisten Nachrichten zu CircleTech sind in der Landessprache und die automatischen Übersetzer sind nicht ausgereift. Falls also jemand weitere Details zu dem Vorfall kennt, die Kommentare sind offen.

Kürzlich hatte ich eine Prüfung im Fach Kryptologie. Das war eine Prüfung mit mehreren Personen. Eine wurde gefragt, warum der Algorithmus DES unsicher ist. Nachdem keine Antwort kam, versuchte der Prüfer eine Brücke zu bauen und fragte, wieviele Schlüssel es gäbe. Es entspann sich folgender Dialog:

P: Wie groß ist der Schlüsselraum?
S: 10¹⁰⁰?
P: Gut geraten. Aber daneben. Aus welchen Zeichen besteht der Schlüssel bei DES?
S: ?
P: Bitfolgen! Was sind Bitfolgen?
S: 0 und 1
P: Welches Zeichen kommt in Frage?
S: 2
P: *augenroll*