Praktikum Kryptographie

Sommersemester 2007 (U. Schöning, S. Gog, T. Eibach)

Ankündigung im Hochschulportal: Link

Das Kryptographie Praktikum besteht zur Hälfte aus Theorieteilen (selbständige Einarbeitung in ein Thema und damit verbundene Literaturrecherche) und zur Häfte aus Praxisteilen (Implementierung und numerische Experimente). Damit sollen die Teilnehmer die Möglichkeit erhalten, einen Einblick in das wissenschaftliche Arbeiten in der Theoretischen Informatik (insbesondere hier im Bereich Kryptographie) zu erhalten. Weiter besteht die Möglicheit eigene Interessensschwerpunkte zu vertiefen. Und aus dem Praktikum dann eventuell ein Diplomarbeitsthema zu gewinnen. Nützliche Voraussetzung ist eine Kryptographie Vorlesung, sowie Grundlagen in Mathematik und grundlegende Programmierkenntnisse.

Dauer insgesammt: 12 Wochen. Ablauf:

• 1. Theorie Teil, 3 Wochen
• 1. Praxis Teil, 3 Wochen, zu dem ersten Theorie Teil
• 2. Theorie Teil
• 2. Praxis Teil, 3 Wochen, zu dem zweiten Theorie Teil
  

Die Themen stammen aus ausgewählten kryptographischen Bereichen wie:

• Automatische Entschlüsselungsverfahren
• Optimieren von Faktorisierungsverfahren
• Elektronische Gesundheitskarte
• Visuelle Kryptographie
• Steganographie
• digitale Wasserzeichen
• Anonymität in Netzen
• Mind Poker
• Faktorisieren mittels SAT Solvern
• weitere Themen nach Rücksprache
  

Anmeldung bitte per Email an: tobias (Punkt) eibach (at) uni-ulm (Punkt) de

Scheinvergabe: bei aktiver Teilnahme

Vorbesprechnung 13.4.2007, 14:15 Uhr, Raum 545
Stand: 11.4.2007

Update vom 13.4.2007
Es ist noch bis Freitag 20.4.2007 möglich an dem Praktikum teilzunehmen. Dazu bitte eine Email schicken. Als erstes Thema wird Steganographie besprochen. Wobei in der ersten Woche rel. wenig Stoff erarbeitet werden soll, daher ist noch bis Freitag eine Anmeldung ohne Probleme möglich. Das nächste Treffen ist am Freitag den (20.4.) um 12:15 Uhr in 532.

Update vom 25.4.2007
Hier noch mal eine kurze Zusammenstellung der bislang verteilen Informationen:

Die Einführung in das Thema Steganographie erfolgt durch Bearbeiten von PraktikumStego.pdf (Quelle: http://www.inf.tu-dresden.de/index.php?node_id=1033&ln=de).

In der zweiten Woche soll ein besserer Überblick gewonnen werden mit dem Paper jsac98-limsteg.pdf und Ergänzungen von ieee99-infohiding.pdf. Weitere Informationen findet man unter anderem bei eprint.iacr.org (einem Kryptographie Paper Archiv), bei citeseer.ist.psu.edu (einer Suchmaschine für wissenschaftliche Veröffentlichungen) oder natürlich auch bei Suchmaschinen oder Wikipedia.

Das aktuelle Ziel besteht darin, während dem Praktikum ein Stega-Tool zu entwickeln und zu analysieren. Dazu muss ein Dateiformat und ein Angriffs-Szenario festgelegt werden. Unter http://www.jjtc.com/mwiki/index.php?title=Main_Page findet man eine ziemlich lange Liste mit Stega-Tools, die zuerst bewertet werden sollen, dann sollen potenzielle Dateiformate genauer untersucht werden (u.a. hinsichtlich Redundanz). Bild-, Video- und Audio-Formate sind schon ziemlich ausgiebig untersucht worden (Agriffe auf Bild-Steganographie findet man zum Bsp. hier: ihw99.pdf), deswegen sollen eher bislang weniger beachtete Formate untersucht werden.

Update vom 7.5.2007
Folgende Formate wurden bzgl. des Einsatzes in der Steganographie untersucht:

Update vom 16.5.2007
Es soll nochmals nach möglichen Dateiformaten für Steganographie gesucht werden. Dateiformaten, die genug Redundanz bieten um Informationen zu verstecken. Hilfreich sind evtl. auch die folgenden beiden URLs: http://www.burks.de/krypto.html#Steganografie und http://de.wikipedia.org/wiki/Steganographie.

Update vom 18.5.2007
Noch ein Hinweis zum thema "Informationsbeschaffung". Häufig bieten Conference Proceedings einen guten Überblick über aktuelle Forschung zu einem Thema. Confernce Proceedings findet man hauptsächlich bei www.springer.com indem man dort nach dem entsprechenden Thema sucht. Zum Thema Steganographie findet man zum Bsp.:

• Intelligent Multimedia Data Hiding (2007): Inhaltsverzeichniss
• Information Hiding, 6th International Workshop, IH 2004: Inhaltsverzeichniss
• Information Hiding 7th International Workshop, IH 2005

Oder auch hier die akzeptierten Papers zur IH2006 Konferenz: http://ih2006.jjtc.com/papers.html

Update vom 21.5.2007
Mal ein (vorläufiges?) Fazit zum Thema Steganographie - eine Zusammenfassung der letzten Besprechung: Es wurden noch mal unterschiedliche Dateiformate hinsichtlich Redundanz und weißem Rauschen untersucht. Aber keine wirklich viel versprechenden gefunden. Nochmal die besprochenen Formate:

• Postscript: bietet etwas Redundanz, wie von B. Weggenmann vorgestellt.
• PDF: sollte so ähnlich sein, ist aber schwerer zugänglich
• FAX Dokumente: Haben Rauschen aber wenig Daten insgesamt
• JPEG: Wurde schon sehr gründlich untersucht, aber bislang alles gebrochen (s.o.)
• Andere Bildformate: Haben das gleiche Problem wie JPEG oder sind an sich schon verdächtig (wie BMP)
• Spam: Texte in Spam zu codieren, ist eine lustieg Idee die unter http://www.spammimic.com/index.shtml umgesetzt wurde
• CAPTCHA: wäre ein Kandidat für ein rel. zufällig erzeugtes Bild, das man auch so erzeugen könnte, dass es Informationen enthält
• Raytracing: ein anderes Verfahren mit dem möglichst realistische Bilder erzeugt werden, eventuell können in dem Bild oder dem dabei entstehenden Rauschen Informationen kodiert werden
• Nicht deterministische Algorithemn könnten umfunktioniert werden, indem man keinen "echten" Zufall verwendet sondern statt der Zufalls-Bits solche wählt die nachher Informationen kodieren
• Code Obfuscating: wird zum Bsp. bei Java .class Dateien genutzt um reverse engineering zu behindern, auch bei PHP. Dabei werden Klassen, Funktionen, Variablen umbenannt, um den Code schwerer lesbar zu machen. Es werden auch andere Umformungen gemacht. Diese könnte man zum Watermarking oder auch für Steganographie nutzen.
• Fehler korrigierende Codes: Diese Codes bieten eine gewisse Redundanz. Wenn man diese ausnutzt kann der Code aber keien Fehler mehr korrigieren. Trozdem könnte es interessant sein aus einem 5-Fehler-korrigierendem Code einen 4-Fehler-korrigierenden-Code zu machen (durch einfügen von "Fehlern" bzw. den zu versteckenden Daten) und dabei bestimmen wieviele Daten sich so verstecken lassen. Fehlerkorrigierende Codes treten zum Bsp. auf in Musik CDs, Daten CDs, Zip-Dateien, ...
• Aus der Überlegung dass die meisten Dateiformate zu wenig Redundanz bieten noch folgender Ansatz: Man müsste zuerst bestehende Dateiformate mit Redundanz versehen. Zum Bsp. durch ein Outlook Plugin dass in JEDER Email im Header 100 zufällige Zeichen unterbringt, die dann natürlich später mal für STeganographie genutzt werden könnten. Das erinnert irgendwo an das Freenet Projekt, in dem natürlich auch sehr viel mehr Traffic (Redundanz) erzeugt wird, um nachher darin unbemerkt zu kommunizieren.
• Smilies: in Emails könnten Informationen kodieren, oder auch Tippfehler / Fehler in der Zeichensetzung

Also, das absolute perfekte Steganographie-Verfahren wird dabei wohl nicht rauskommen. Grundsätzlich ist das Interesse an dem Thema sehr hoch, was man einfach bei Internet Rechere feststellen kann. Es gibt sehr viele Webseiten und Prpogramme zu dem Thema, nur die meisten sind veraltet und gebrochen. Kürzlich gewann ein 16 jähriger Schüler bei Jugend Forscht mit einem Steganographie Programm (http://www.tagesschau.de/aktuell/meldungen/0,1185,OID6784618,00.html) über das es aber bislang keine Informationen gibt ...

Die bislang ausgearbeiten Ansätze sind bestimmt nicht völlig wertlos und eignen sich zum Bsp. für Bachelor oder Master Arbeiten zu einem sehr beliebtem Thema :-)

Update vom 21.5.2007
Es soll nun ein neues Thema bearbeitet werden, nämlich Angriffe auf Strom-Chiffren mit Hilfe von SAT Solvern. Dazu gilt es zuerst wieder selbstständig die Grundlagen zu erarbeiten. Ausgangspunkt ist das im eSTREAM Projekt veröffentliche Paper Attacking Bivium with MiniSat und der Vortrag von T. Johansson zum Thema Feedback Shift Register Based Stream Ciphers. Es gibt noch weiterführende Folien im Vortrag Stream Ciphers: Cryptanalytic Techniques. In der nächsten Besprechung sollen dann diese Grundlagen gemeinsam diskutiert werden und die Aufgaben/Literatur über die Reading Week aufgeteilt werden.

Update vom 24.5.2007
Die 3 wichtigstens referenzierten Paper:

• Raddum, "Cryptanalytic Results on Trivium", ps, 2006-03-27.
• Bard, "Efficient Methods for Conversion ... SAT-Solvers", pdf, 2007-01-25.
• Maximov, "Two Trivial Attacks on Trivium", pdf, 2007-01-23.

• Handbook of applied cryptography: www.cacr.math.uwaterloo.ca/hac (insb. Kapitel 6)
• Eine Doktorarbeit zu Strom-Chiffren: uni-mannheim.de/.../thesis-zenner.pdf (insb. der einfürende Teil)
• Angriffsbezogener Technical Report von der Uni Waterloo: corr2002-29.ps (nicht gereviewed - dafür viele Referenzen)

• http://www.satlib.org/ubcsat/ - schnelle Implementierung aktueller SAT Algorithmen
• http://www.satcompetition.org/ - Webseite zu dem regelmäßig stattfindenden SAT Solver Wettbewerb
• http://www.cs.chalmers.se/Cs/Research/FormalMethods/MiniSat/ - Webseite zu MiniSat
• http://www.satlive.org/ - Umfangreiche Webseite zu SAT Solvern inkl. aktueller Beiträge

Update vom 18.6.2007
Unter http://deposit.ddb.de/cgi-bin/dokserv?idn=982398042 gibt es eine interessante Doktor-Arbeit zu Algebraischen Angriffen auf Strom Chiffren.

Update vom 28.6.2007
Noch ein paar weiterführende Informationen/Links:

• http://www4.gu.edu.au:8080/adt-root/uploads/approved/adt-QGU20070216.143447/public/02Whole.pdf  - Doktorarbeit zum Thema SAT
• http://www.carstensinz.de/papers/SAT-2004-Visualization.pdf - Paper zu der Software unter http://www-sr.informatik.uni-tuebingen.de/~sinz/DPvis/, mit der man CNF Formeln grafisch darstellen kann

• http://www.wisdom.weizmann.ac.il/~albi/ac00tradeoff.ps