Die folgende Seite enthält Hinweise auf Fehler sowie Ergänzungen zu:
Reinhard Wobst, "Abenteuer Kryptologie", 3.Auflage
Addison-Wesley Verlag 2001, ISBN 3-8273-11815-7
Stand: @(#) Mar 09 2005, 11:03:16
Niemand ist perfekt, und so wird auch die 3.Auflage dieses Buches Fehler enthalten, denn sie wurde stark bearbeitet. Ich freue mich jederzeit über Hinweise, bitte aber darum, mir keine "unknackbaren Codes" oder "völlig neuartige Algorithmen" zu senden - die Begründung dafür findet sich im Vorwort.
Leider konnten mich viele Leser der 1. und 2. Auflage nicht erreichen, da die Mailadresse r.wobst@addison-wesley.de bei der Übernahme von Addison-Wesley durch Pearson Education inaktiv und trotz vieler Hinweise nicht mehr freigeschaltet wurde. Die Mailadresse, unter der mich Leser hoffentlich auf lange Sicht erreichen werden, ist: r.wobst @ gmx.de (ohne Leerzeichen).
NEW (03/09/2005): 2.2.1 - Automatische Kryptanalyse von Substitutionschiffren
NEU (22.10.2004) zu 6.2.2: Ich habe selbst eine Software für Secret Sharing geschrieben.
NEU: (9.12.2004) zu 6.3.1: Erfolgreiche Angriffe auf Hashfunktionen
2.2.1 - Automatische Kryptanalyse von Substitutionschiffren
Meine in diesem Abschnitt beschriebenen Ideen funktionierten nicht in der Praxis. Mittlerweile habe ich ein Python-Skript entwickelt, das auf Wortmustern basiert und Geheimtexte von mindestens 200 Zeichen Länge ziemlich zuverlässig und schnell dechiffriert (5-20 Sekunden). Es wird keine Statistik benutzt. Das Skript wurde für UNIX/Linux entwickelt, doch eine Portierung auf andere Systeme sollte ohne Schwierigkeiten möglich sein. Sie können das 13KB lange Archiv (mit Dokumentation) subscrack.zip herunterladen. Deutschsprachige Anwender können sich auch ein 800KB langes, komprimiertes Wörterbuch wordlst.gz besorgen.
zu 2.2.4 - "Stabchiffrierung"
Der zu Anfang dieses Abschnitts beschriebene Stab wurde nicht von den alten Griechen, sondern von den Spartanern eingeführt, und hieß skytale (vgl. [KahnCode], "The first 3000 years").
zu 2.5.2 - Enigma
Erst 2000 lüftete auch Großbritannien weitere Geheimnisse um die Enigma, 55 Jahre nach Kriegsende. Es zeigte sich, daß zehn Maschinen vom Typ "Colossus II" im Einsatz waren, die vielleicht als erste elektronische Computer der Geschichte bezeichnet werden können, weil sie in beschränktem Maße auch programmierbar waren. Offiziell gilt die 1946 in den USA gebaute Maschine ENIAC als erster elektronischer Computer der Geschichte. Näheres findet sich unter www.telegraph.co.uk/et?ac=003549412141223&rtmo=aqJ4XahJ&atmo=tttttttd&pg=/et/00/9/7/ecfcol07.html sowie www.telegraph.co.uk/et?ac=003549412141223&rtmo=wAfMMQKb&atmo=gggggg3K&pg=/et/00/9/30/ncol30.html .
zu 4.5.3 - RSA: Zusammenhang zwischen Faktorisierung und diskretem Logarithmus
Auf S.165 unten ist mir ein grober Fehler passiert: Die Berechnung von m aus me heißt natürlich nicht, den diskreten Logarithmus zu berechnen, sondern die e-te Wurzel zu ziehen. Das ist offenbar nicht einfacher; auch das Ermitteln der Quadratwurzel ist ein "hartes" Problem.
Allgemein gilt aber, dass die Berechnung des diskreten Logarithmus nicht einfacher ist als die Faktorisierung (vgl. z.B. [MenOOVan, 3.78]). Der Zusammenhang ist nur nicht so einfach wie im Buch dargestellt.
zu 5.4.4 - RC6
Da RC6 nicht als Standard AES angenommen wurde, hat RSA Security den Algorithmus nun doch unter Patentschutz gestellt - leider. Das war bei Drucklegung des Buches noch nicht klar.
zu 5.5 - Kryptanalyse von AES (Rijndael)
Es gibt einen "beunruhigend interessanten" Artikel von Niels Ferguson, Richard Schroeppel und Doug Whiting vom Mai 2001, in dem eine erstaunlich einfache Darstellung der Rijndael-Transformation als Summe von Kettenbrüchen gefunden wird. Zwar stehen auf beiden Seiten der Gleichung dann etwa 225 fünfstufige Kettenbrüche (das sind reichlich 33 Millionen), doch wenn sich daraus ein Angriff ableiten ließe, wäre er vielleicht sogar praktisch realisierbar. Für Kryptologen heißt das: höchste Alarmstufe. Es kann also doch sein, daß die Sorge wegen der auffällig einfachen Struktur von Rijndael berechtigt war.
Die Reaktionen darauf sind unterschiedlich, grundlegend neue Erkenntnisse, die darauf basieren, gibt es z.Z. (Anfang 2002) noch nicht. Den Artikel finden Sie unter www.xs4all.nl/~vorpal/pubs/rdalgeq.html , einige mathematische Vorbildung vorausgesetzt.
Weiter bedanke ich mich beim Leser Pawel Krawczyk der polnischen Ausgabe des Buches für den Hinweis auf die Artikel
und
in denen weitere erfolgversprechende Ansätze der Kryptanalyse dargestellt werden. Die Meinungen über diese Artikel gehen auseinander. In der c't 21/2002, S.38, und in der iX 12/2002, S.100-104, sind zwei Artikel von mir dazu erschienen, die Details darstellen. Genaugenommen war es ziemlich früh, schon darüber zu schreiben, doch allemal besser, als irreführende Gerüchte in Umlauf zu setzen.
Wenn diese Art algebraischer Angriffe Erfolg haben sollte, dann wären Geheimtextangriffe mit wenigen Blöcken denkbar! Auf der anderen Seite streitet man sich noch, ob diese Ansätze überhaupt eine Chance haben. Doch AES scheint tatsächlich "algebraisch gefährdet" zu sein. Mein Tipp: Twofish.
zu 5.6 - RC4
In Schneiers "Angewandter Kryptographie" steht eine etwas andere Definition der Erzeugung des internen Schlüssel (Abb. 5.21, Teil auf S.239). Dort läuft der Index i von 0 bis 256. Ich bin mir nicht ganz sicher, ob sein Verfahren äquivalent zu dem hier angegebenen ist, doch meines entstammt direkt den zugehörigen, allgemein verwendeten C-Programmen, hat also den "Praxistest bestanden".
Auf www.wisdom.weizmann.ac.il/~itsik/RC4/rc4.html gibt es eine Übersicht über aktuelle Kryptanalysen von RC4. Es zeigt sich, dass dieser Algorithmus in vielen Implementierungen angegriffen werden kann, insbesondere im WLAN-Standard 802.11.
zu 5.7.1 - pkzip-Chiffrierung
Auf S.242 (Mitte) hat sich ein Rechenfehler eingeschlichen. Es muss heißen
K = LSB((2b+5)a) + MSB((b+2)(b+3))
Der Angriff klappt trotzdem - auch (2b+5) ist teilerfremd zu 256, und a lässt sich aus b bestimmen.
zu 5.7.2 - GSM-Telefone abhören
Die Aussage auf S.249, dass zwei Minuten des Mitschneidens ausreichen, um ein GSM-Gespräch zu dechiffrieren, ist so nicht richtig. Man braucht den "Output von A5/1" von zwei Minuten, also Klar- und Geheimtext! Die Alternative dazu heißt "zwei Sekunden Klartext und einige Minuten Rechenzeit." Wie weit sich daraus praktikable Angriffe ableiten lassen - vielleicht dank chiffrierter Headerdaten - entzieht sich meiner Kenntnis, und Biryukov, Shamir und Wagner machen ausdrücklich keine Aussagen "über die praktische Sicherheit von GSM-Systemen".
Jedoch fanden Barkan, Biham und Keller 2003 gegen den schwächeren Algorithmus A5/2 hocheffektive und praktikable Angriffe, vgl. http://cryptome.org/gsm-crack-bbk.pdf . Die Autoren nutzen dabei aus, dass Fehlerkorrekturcodes ebenfalls mit chiffriert werden und dadurch eine algebraische Abhängigkeit zwischen Geheimtextteilen entsteht. In der Praxis sieht das so aus:
Man bringt das Telefon mittels IMSI-Catcher (also "Man in the Middle") dazu, A5/2 statt A5/1 zu benutzen - das können alle oder fast alle Geräte -, hört wenige Hundertstel Sekunden (!) mit und benötigt dann eine Sekunde zum Dechiffrieren. Allerdings schalten meines Wissens die Telefone auf Anforderung ihre Chiffrierung ganz aus, und die wenigstens Nutzer werden das bemerken bzw. die Anzeige zu deuten wissen ...
zu 5.9 - Quantencomputer
Es gibt ein gut lesbares Buch zu diesem Thema, und zwar:
Colin P.Williams, Scott H.Clearwater,
Ultimate Zero and One
Copernicus/Springer Verlag New York 2000
ISBN 0-387-94769-8
In meinem Buch wurde das Prinzip der Quantencomputer etwas zu einfach erklärt. Der Idealzustand, daß die gesuchte Lösung die Wahrscheinlichkeit 1 hat, läßt sich nicht immer erreichen. Mittels Quantencomputer kann man jedoch z.B. Perioden von Funktionen direkt ermitteln, ungefähr so, wie man aus Röntgenbeugungsbildern direkt Kristallstrukturen ableiten kann. Nach diesem Prinzip arbeitet der Shor-Algorithmus zur Faktorisierung, der im zitierten Buch genauer erklärt wird.
Das mit der gleichzeitigen, verzögerungsfreien Beeinflussung verschränkter Quantenzustände stimmt zwar, doch darf man daraus nicht so einfach auf die Rechenzeit schließen. Der IBM-"Computer" vom August 2000 beruht offenbar auf fünf Kernspins, wobei die Atomkerne über die Elektronenhüllen gekoppelt werden. Die notwendigen Radiowellenpulse (entsprechend einem Rechenschritt) sind einige Millisekunden lang. Trotzdem: Könnte man 512 Kerne auf diese Weise verknüpfen, hätte man mit 2512 Zuständen gleichzeitig gerechnet - eine unvorstellbar große Zahl.
Mittlerweile haben IBM-Forscher einen 7 bit großen Quantencomputer nach gleichem Prinzip betrieben und damit die Zahl 15 faktorisieren können, vgl. http://www.research.ibm.com/resources/news/20011219_quantum.shtml.
Ein CNN-Meldung vom 17.2.2001, wonach man mittels Lasertechnik große Fortschritte erzielt hätte, betrifft die Kryptografie nicht. Sie taugt offenbar nur für Anwendungen, die keine verschränkten Quantenzustände erfordern (sie sind jedoch bei Faktorisierung und Berechnung diskreter Logarithmen gerade wichtig) - z.B. der schnellen Suche in ungeordneten Datenbeständen. Jedoch habe ich wegen des physikalischen Prinzips starke Zweifel, ob diese Methode für die Suche in Beständen von Billionen Einträgen geeignet ist, da ich zufällig einige grobe Kenntnisse in der Akustooptik habe. Näheres unter www.scienceagogo.com/news/20010417230843data_trunc_sys.shtml.
Ein sehr guter, sehr interessanter Link zur sog. QIS (quantum information science) ist unter www.nsf.gov/pubs/2000/nsf00101/nsf00101.html zu finden.
zu 5.10 - Power Attack
Die Designer halten Schritt mit den Kryptanalytikern: Auf www.cs.cornell.edu/cs789-fa99/rohatgi.htm finden sich einige Informationen über eine IBM-Entwicklung von Chipkarten, die gegen SPA und sogar DPA resistent sein sollen.
zu 6.2.2 - Software zu Secret Sharing
Mittlerweile fanden sich frei verfügbare Implementierungen von Secret Sharing, wenngleich vorerst mehr für Demonstrationszwecke (aber ausbaufähig):
www.ts-networld.de/documents/secshare
Der junge Kryptologe Sebastian Mozejko aus Polen machte mich dankbarerweise auf folgende wesentlich bessere Software aufmerksam:
axion.physics.ubc.ca/crypt.html#SECSPLIT
www.afn.org/~afn21533/rgdprogs.htm#SECSPLIT
www.atomicfrog.com/knowledge/security/misc/
Das C-Programm wurde unter DOS und UNIX getestet, verwendet aber noch IDEA. Man sollte den Algorithmus auswechseln.
NEU: Daher habe ich mich selbst hingesetzt und eine einfach zu nutzende Klasse in Python entwickelt, mit deren Hilfe man beliebige K-aus-N-Schemata erzeugen und nutzen kann. Standardmäßig dient sie zum Chiffrieren und Dechiffrieren von Daten im Speicher (Zeichenketten i.S.v. Python), Dateien und Datenströmen. Die Chiffrierung selbst wird von einem externen C-Programm vorgenommen, das Blowfish-128 oder AES-128 verwendet (sowie die OpenSSL-Bibliothek libcrypto). Das geteilte Geheimnis dient wie üblich nur als Masterkey (KEK, key encryption key), die eigentliche Chiffrierung nutzt zufällige Sitzungsschlüssel. Außerdem wird die Integrität mittels einer MD5-Hashsumme überprüft (was in diesem Kontext sicher ist).
Python ist sehr geeignet für solche Applikationen, da eine schnelle Langzahlarithmetik mit eingebaut ist. Außerdem ist es eine moderne und extrem leicht zu erlernende Sprache mit Schnittstellen zu C/C++ und anderen Sprachen - vgl. www.python.org. Dank zahlreicher Module bleiben kaum Wünsche offen (es muss nicht immer Perl sein - Python-Programme sind in der Regel wesentlich besser zu warten und zu verstehen).
Download: Als zip-Archiv secshare.zip der drei Dateien secshare.py, secshare.txt und enc_stream.c.
NEU: zu 6.3.1 - Erfolgreiche Angriffe gegen Hashfunktionen
Auf der CRYPTO '04 wurden erstmals Kollisionen von MD5 und SHA-0 vorgestellt. Die Chinesen Wang, Feng u.a. berichteten, zur Berechnung einer MD5-Kollision bräuchte ein PC zwischen 15 Sekunden und 5 Minuten. Das ist sensationell, vor allem wenn man bedenkt, wie lange man sich schon daran versucht. Der Franzose Joux benötigte zum Berechnen der SHA-0-Kollision unwesentlich länger, nämlich 80000 Stunden auf Itanium2-CPUs. SHA-0 unterscheidet sich von SHA-1 (im Buch einfach als SHA bezeichnet) nur durch eine Linksrotation um 1 Bit beim Expandieren des Textes. Gegen SHA-1 sind noch keine Angriffe bekannt. Die Fortschritte haben aber die Wissenschaftler alarmiert, und weitere wichtige Ergebnisse werden nicht lange auf sich warten lassen. Eines davon ist das Ergebnis von Kelsey und Schneier, dass die Suche nach einem zweiten Urbild (d.h., nach einem > mit Y with sha(Y) = sha(X) für gegebenes X) nur etwa 2n/2 statt 2n Berechnungen erfordert, und zwar für eine Klasse von Hashfunktionen, zu denen auch SHA-1 gehört.
Digitale Signaturen mit MD5 würde ich nicht mehr anerkennen. Bei HMAC-Summen (die von einem geheimen Schlüssel abhängen) besteht vermutlich keine Gefahr. Ebenso ist es unbedenklich, wenn Hashsummen zusammen mit Klartexten chiffriert werden (wie bei meiner Software zu Secret Sharing, s.o.). Allerdings muss man sich ernsthaft fragen, welche "Langzeitstabilität" heutige digitale Signaturen haben.
Quellen:
www.md5crk.com/sha0col/
(die SHA-0-Kollision)
eprint.iacr.org/2004/199.pdf
(der Artikel von Feng, Wang u.a.)
eprint.iacr.org/eprint/2004/207
(Untersuchung der SHA-1-Nachfolger)
md5coll.py
(mein Python-Skript, das die MD5-Kollision nachvollzieht)
eprint.iacr.org/eprint/2004/304
(Arbeit von Kelsey and Schneier über zweite Urbilder)
Vermutlich erscheint in einer c't im November oder Dezember 2004 ein längerer Artikel zu diesem Thema von mir.
zu 6.5.3 - SecurID Token von RSA
Ein weiterer Hinweis von Sebastian Mozejko aus Polen - man greift die Hashfunktion des SecurID Token von RSA an, vgl. dazu http://eprint.iacr.org/2003/162/ und .../205/. Ich bin leider noch nicht dazu gekommen, mich näher damit zu beschäftigen. Praxisrelevant ist der Angriff offenbar noch nicht, da der Aufwand sehr hoch scheint und andere Angriffe ("Man in the Middle") vielleicht effektiver sind.
zu 7.1.4 - PGP und GnuPG
Inzwischen sind fertige Windows-Versionen von GnuPG verfügbar, und es wurde ein Projekt "Ägypten" gestartet, das GnuPG mit den Welten von S/MIME und X.509 verbinden soll. Näheres auf der Webseite www.gnupg.org .
Nachdem NAI die Entwicklung und den Vertrieb von PGP (und von einigen anderen Produkten wie PGPdisk) einstellte, fand sich schließlich doch noch ein Käufer. Einzelheiten finden sich im Artikel "Auferstanden" (iX 2/2003, S.48-52) von I.Camphausen und S.Kelm über PGP 8.
Generell sieht es mit Mailverschlüsselung aber immer noch äußerst trüb aus.
Auf der anderen Seite unterstützt das Wirtschaftsministerium mit dem Gnu Privacy Project GnuPP (www.gnupg.org) die Anwendung und Verbreitung von GnuPG auch unter Windows.
zu 7.2.1 - Angriffe auf hierarchische PKI-Strukturen
Mein beschriebener Angriff auf hierarchische PKI-Strukturen (bei denen ein Geheimdienst einen privaten Schlüssel erhält) scheint wenig bekannt zu sein. Allerdings muß der Geheimdienst dafür sorgen, daß das "Opfer" auch den falschen öffentlichen Schlüssel erhält. Ich vermute, daß man diese Möglichkeit durch Modifikationen oder Erweiterungen des Standard ausschließen kann.
zu 8.2.1 - Echelon
Der Echelon-Ausschuß der EU schließt seine Arbeit ab. Unter http://cryptome.org/echelon-ep.htm sowie http://www.europarl.eu.int/tmpcom/echelon/prechelon_en.htm findet sich ein lesenswerter Bericht, unter http://www.telepolis.de/deutsch/special/ech/7428/1.html ein interessantes Interview mit dem Berichterstatter der Kommission, Gerhard Schmid.
Generell wird die Existenz von Echelon nicht mehr bestritten, doch die Thematik ist noch sehr im Fluß.
Mit der Initiative "Total Information Awareness" (TIA) versucht man allerdings, Echelon noch um Größenordnungen zu toppen - Informationen dazu u.a. in
www.darpa.mil/iao/index.htm
www.heise.de/tp/deutsch/inhalt/te/13580/1.html
online.securityfocus.com/columnists/126
sowie in populärer Form in "Das Auge Gottes ist noch ziemlich trübe", Computer Zeitung 5/2003, S.8. Gegenwärtig sieht es allerdings so aus, als ob nur Komponenten von TIA eingesetzt werden sollten, das Parlament konnte sich mit dem Projekt nicht anfreunden.
zu 8.2.3 - Schlüsselhinterlegung
Nach den Terroranschlägen vom 11. September 2001 kam das leidige Thema prompt wieder hoch. Schlüsselhinterlegung wirkt aber gegen Terroristen erst recht nicht. Die Argumente aus der Abb. sind ziemlich unvollständig, z.B. ist es heutzutage wohl auch nicht mehr denkbar, sämtliche Software und Protokolle wie SSL, IPSEC, VPNs, OpenPGP, S/MIME usw. nachträglich umzustellen. Auch eine internationale Regelung scheint utopisch, angesichts der Furcht vor Echelon (und generell vor Wirtschaftsspionage). Detailliertere Artikel über dieses Thema erschienen von mir in der iX ("Flaschengeist", Heft 3/2002), Lanline spezial VI/01 und UNIX/open (etwa 3/02). Offenbar muß man diese Argumente ständig parat haben, bis auch alle Entscheidungsträger die Probleme begriffen haben.
Trojanische Kryptografie und Microsoft
Beim LAN-Protokoll Kerberos, das dem verschlüsselten Verkehr lokal vernetzter Rechner dient, werden bestimmte Felder in Headern freigehalten. Das Kerberos-Protokol von Windows 2000 nutzt jedoch diese Felder und wird dadurch inkompatibel zu Rechnern, die nicht unter Microsoft-Systemen laufen. Wie üblich bei Microsoft wird die in diesen Feldern enthaltene Information nicht dokumentiert. Damit nicht genug: Im Web wurde von einer Klage Microsofts gegen Slashdot berichtet, die diesen Sachverhalt als erstes offenlegten. Gegenstand der Klage: Unbefugte Offenlegung von Interna ... Ob dies trojanische Kryptografie ist oder nicht, weiß ich nicht, aber bis zur vollständigen Offenlegung des Protokolles muß man damit rechnen, zumal es durchaus analoge Beispiele bei Microsoft gibt (in weiterem Sinne gehört auch das Einbinden der Prozessor-ID in Word-Dokumente sowie die Online-Meldung dieser ID an Microsoft bei der Registrierung dazu).
Trotzdem wird alle Welt Kerberos unter Windows 2000 nutzen und staunen, warum sich das Protokoll nicht mit anderen Kerberos-Systemen verträgt.
S.52, Formel oben: Ä-Punkte über der 6 (wie erzeugt man denn so etwas??)
S.143, letztes Drittel: C = SB(A xor S)
S.165 unten, Berechnen von m aus me: vgl. die Bemerkungen oben zu 4.5.3
S.167 oben, 2.: Der letzte Satz ist falsch, es wird ja die Teilerfremdheit zu p-1 und q-1 gefordert, nicht zu p und q. Unter Umständen müssen mehrere Primzahlen durchprobiert werden.
S.177 oben, 1.: vgl. Bemerkungen oben zu 4.5.3
S.237, Absatz "Implementierungsfragen", 2.Zeile: "(vgl. Kasten 4)" streichen.
S.247 mitte: IEEE statt IEE
S.254, Überschrift: "wird" statt "wir"
S.254 unten, vorletzter Absatz, letzte Zeile: "... Angriff auf Skipjack [Skipana]." (nicht: IDEA)
S.301, drittletzte Zeile: 5.7.5 statt 5.6.5
S.331, fünftletzte Zeile: "Der ausländische Geldautomat kennt nur einen dieser ..."
S.333, drittletzte Zeile: Abb. 6.10 statt 7.1
Viele Seiten: "Hellmann" schreibt sich korrekt "Hellman", es heißt also "Diffie-Hellman-Verfahren".
XXX S.40: T nicht mit drin im Quadrat, I statt J nehmen! XXX Subscode