Cryptography

As the article some days ago about SHA1 got a lot of interest, I thought I'll write some more background info about this, especially for people thinking that collisions aren't a big problem.

Cryptographic hash functions are functions where you can put a string of any length and get a fixed-size result. E. g. with SHA1, you get 160 bit, with MD5 128 bit. The hash-function has to fulfill some requirements:
- It should be hard to get two strings with the same hash (collision-resistant).
- It should be hard to get a string to a given hash (one-way-function).
To be more precise: In an optimal case, hard means that it shouldn't be possible with all hardware on earth in the timeframe that your cryptography needs to be secure. Some examples where cryptographic hashes are used are shadown-passwords, digital signatures or verification of file downloads.

Xiaoyun Wang, chinese cryptographer and well known for her analysis of the SHA1 function, was not allowed to travel to the US to attend the Crypto conference starting today (via Bruce Schneier).

Too bad, because she discovered some new results on the attacks on SHA1, which reduce it to a complexity of 2^63 to generate a collission. Adi Shamir, well known cryptographer and one of the RSA-inventors, presented these results.
These news are important, because 2^63 is a complexity that can be broken with todays hardware if you invest enough money and time. This would be an interesting project for distributed computing, although I don't know if the attack can be implemented on common hardware (maybe someone with cryptographic experiences wants to comment if this is possible).

Too bad that most software devs have not noticed the recent results on hash-functions. Most of them still use MD5 (which has been broken about a year ago), SHA-1 is widely used. The GNU Coreutils don't have any tools for modern hash-functions, same goes with most programming languages (PHP, Python), while they implement some sort of md5sum or sha1sum, no sha256sum or whirlpoolsum at all.

I recently installed privoxy and tor and Lars asked me to write some words about it. So here it goes:

Privoxy is an ad-blocking proxy, which means it filters out banners, pop-ups and other annoying stuff. It's highly configurable, but I use it in the basic configuration, which should be enough for most needs. The advantage is that privoxy, unlike for example the firefox ad-block extensions, can be used within any browser. It's the successor of junkbuster.
tor is a project by the Electronic Frontier Foundation, an internet anonymizing system. It's internals are complex, but the basic funktion is that you connect encrypted to a tor-node, it forwards your request through several other tor-nodes and then it get's answered. It doesn't provide full anonymity, you have to trust the tor-node you connect to. But it's definitely better than nothing.

Both integrate well, if you are a Gentoo user, just emerge tor pricoxy, add forward-socks4a / localhost:9050 . to your /etc/privoxy/config, copy the torrc.sample to torrc (in /etc/tor), add both to your runlevels (rc-update add tor default, rc-update add privoxy default) and you are done.
Now set your Browser to use Proxy localhost and Port 8118.
For other Linux-Distributions, it's probably similar. I have no idea if and how tor and privoxy work on other OSes (especially the evil one with the W), so don't ask me, you'll have to find out yourself.

This will save you some privacy and you'll get rid from a lot of internet ads.

Note: tor had some security-issues recently, so take care that you use the latest version available (0.1.0.14).

Heute lief in SAT1 der Film "Enigma" über die Entschlüsselungsaktivitäten der Engländer im 2. Weltkrieg in Bletchley Park. Hab leider erst nach der Hälfte reingeschaltet.
Der geniale Kryptograf Tom Jericho, der wohl die historische Figur des Alan Turing darstellen soll, ist schlauer als alle anderen, deckt nebenher noch ein paar Verschwörungen auf etc. Hollywood-Style eben.

Was mich aber richtig geärgert hat: Dem fiktiven Alan Turing wurde eine Liebesbeziehung zu einer hübschen Frau (Kate Winsley) angedichtet.
Die Realität sah etwas anders aus: Alan Turing war homosexuell. Er wurde deswegen nach dem Krieg verurteilt und musste sich "den Geschlechtstrieb hemmende" Hormone spritzen lassen. Zwei Jahre später beging er Selbstmord.
Aber das hätte halt nicht in das Heldenbild eines Hollywoodfilms gepasst.

Wikipedia über Alan Turing

Meistens les ich ja telepolis ganz gerne. Nur gelegentlich kommt völliger Bullshit dabei heraus. So schwadroniert heute ein Artikel, dass asymmetrische Kryptografie bald obsolet werden könnte.

Kleine Einführung für nicht-Mathematiker: Bei fast allen sicheren Online-Verbindungen wie ssl, ssh o.ä., sowie bei eMail-Verschlüsselung mit PGP/GnuPG und in vielen weiteren Fällen wird sogenannte asymmetrische Kryptografie (auch Public Key-Verfahren genannt) eingesetzt. Das bekannteste und am weitesten verbreitete Verfahren ist RSA, die meisten anderen Verfahren (El Gamal, DSA) basieren auf ähnlichen mathematischen Problemen.

Die Sicherheit von RSA beruht darauf, dass es zwar einfach ist, zwei große Primzahlen miteinander zu multiplizieren, umgekehrt jedoch schwierig, eine Zahl in ihre Primfaktoren zu zerlegen. Hat man also beispielsweise zwei große Primzahlen a und b, so ist es einfach a*b=c zu berechnen. Umgekehrt ist es jedoch nur mit hohem Rechenaufwand möglich, von c auf a und b zu schließen.

2001 haben drei Inder den AKS-Test entwickelt, mit dem man in polynomialer Rechenzeit (einfach gesprochen heißt das: auch bei großen Zahlen noch schnell) herausfinden kann, ob eine große Zahl eine Primzahl ist oder nicht. Für die Sicherheit von RSA ist dies jedoch völlig unbedeutend. Im Gegenteil: Um RSA nutzen zu können, benötigt man schnelle Primzahltests bei der Schlüsselgenerierung. Es ist mathematisch gesehen ein völlig anderes Problem, eine Zahl zu faktorisieren oder sie auf ihre Primzahleigenschaft zu testen.

Nun ist das schon einige Jahre her und war auch damals nicht wirklich überraschend. Das einzige, was passiert ist: Der bekannte AKS-Test wurde in einer mathematischen Zeitschrift veröffentlicht. Genaugenommen ist also garnichts passiert.

Übrigens gibt es bereits seit den 70er-Jahren den sogenannten Miller-Rabin-Test, von dem man ebenfalls vermutet, dass er in polynomialer Zeit Primzahlen erkennen kann. Dafür fehlt bislang jedoch der Beweis. Überraschen konnte das Ergebnis der drei Inder daher aber auch 2001 nicht wirklich.

Korrekt ist im übrigen, dass es rein theoretisch möglich wäre, dass ein bisher unbekannter Algorithmus zur schnellen Faktorisierung existiert. Nur hat ihn bisher noch niemand gefunden (und da sich mit diesem Problem Mathematiker schon ziemlich lange rumschlagen, ist damit auch nicht in absehbarer Zeit zu rechnen).

Daneben strotzt der Artikel nur so von inhaltlichen Fehlern. So wird behauptet, die Faktorisierung von Zahlen sei nur in exponentieller Rechenzeit möglich. Mit modernen Verfahren, etwa dem Zahlkörpersieb, ist dies deutlich schneller möglich, nur eben immer noch zu langsam, um RSA mit ausreichend großer Schlüssellänge (>=2048 bit) in annehmbarer Zeit zu brechen.

Kleiner Tipp an telepolis: Wenn ihr das nächste Mal etwas über Kryptografie schreibt, sucht doch erstmal jemand, der zumindest mal eine Anfängervorlesung dazu besucht hat. Dann würdet ihr vielleicht nicht so einen Unfug schreiben.

Quellen:
Vorlesungsskript über den AKS-Algorithmus (war selber in der Vorlesung)
Miller-Rabin-Test bei Wikipedia
AKS-Test bei Wikipedia