INFSEC.de

Autor: Tim

  • Sicherheit beim Online-Poker

    Hallo zusammen,

    erneut ein Problem, erneut eine Lösung.

    Bei einem Online-Poker Spiel (PokerTH, ein Open-Source-Projekt unter GPL) habe ich mir die Frage gestellt, wie fair so ein System überhaupt sein kann, unabhängig von der zugrunde liegenden Netzstruktur (P2P, Client/Server).

    Das ist meiner Meinung nach eine sehr wichtige Frage, da der Einsatz, anders als in meinem Fall, auch Echtgeld sein könnte. Nehmen wir an, der Server (bzw. der Betreiber) würfelt die Karten und übermittelt sie den Teilnehmern. Dann muss dieser auch absolut vertrauenswürdig sein. An dieser Stelle entscheidet ganz allein die Serverapplikation über Sieg oder Niederlage der Spieler – zumindest bei reinen Glücksspielen. Hier hätte jemand mit Serverzugriff gleichzeitig Einblick in alle Karten. Böswillig könnte man sogar unterstellen, der Betreiber nimmt selbst am Spiel teil und nutzt diese Kenntnis aus – ein solches Spiel kann nicht gewonnen werden. In einem Netzwerk von gleichberechtigten, also ein P2P-Netzwerk, existiert dagegen kein Host, daher müsste ein LEA (Leader Election Algorithm) entscheiden, wer die Spielrunde leitet. Das Problem bleibt jedoch bestehen: ein Teilnehmer der Runde besitzt die Möglichkeit das Spiel zu manipulieren.

    Die andere Seite ist jedoch genauso kritisch. Würfelt der Teilnehmer/Spieler die eigenen Karten, ist dies ganz offensichtlich (insbesondere bei einem Open Source Projekt), keine gute Idee. Eine weitere Möglichkeit wäre, dass ein Teilnehmer die Karten des unmittelbaren Banknachbarn bestimmt, aber von Fairness kann hier auch kaum gesprochen werden.

    Beide Lösungen sind nicht wirklich überzeugend und bedeuten stets, dass mindestens einer einen Vorteil erhält. Letztenendes besteht das Problem, dass alle Teilnehmer gemeinsam etwas bestimmen müssen, also wer welche Karten bekommt, ohne diese konkret zu erfahren. Gibt es dazu eine Lösung? Die Antwort lautet: ja.

    Aber leider nicht von mir, sondern von Adi Shamir, Ron Rivest und Len Adleman – den Entwicklern der RSA Verschlüsselung. Es handelt sich um ein Protokoll für ein faires Pokerspiel, welches hier zu finden ist. Bevor ich nun die Algorithmus skizziere, möchte ich allerdings noch erklären was eine kommutative Chiffre ist. Normalerweise muss beim Ver- und Entschlüsseln eine Reihenfolge eingehalten werden, z.B.:

    D_key1(E_key1(x))

    und

    D_key1(D_key2(E_key2(E_key1(x))))

    also sozusagen wie bei einer Zwiebel: jede Schale muss sauber und nacheinander aufgetragen und wieder entfernt werden um an den Inhalt zu gelangen. Bei einer Kommutativen Chiffre ist diese Reihenfolge irrelevant – funktionieren würde also ebenso:

    D_key2(D_key1(E_key2(E_key1(x))))

    Also: die Reihenfolge der Entschlüsselung spielt keine Rolle. Diese Eigenschaft wird beim folgenden Pokerprotokoll ausgenutzt, wobei es in der Praxis effektiv keine Einschränkung darstellt:

    1. Parteien A und B einigen sich bezüglich einer klaren Kodierung der Spielkarten.
    2. Die Partei A wählt einen beliebigen geheimen Schlüssel und verschlüsselt jede Karte einzeln.
    3. Partei A mischt die Karten
    4. Partei A übermittelt die neuen (verschlüsselten und gemischten) Karten der Partei B; B weiß daher nicht, welche Karten sich wo befinden.
    5. B verschlüsselt ebenso jede Karte mit einem Schlüssel -> jede Karte ist nun sowohl von A als auch von B mit jeweils einem Schlüssel verschlüsselt worden.
    6. B mischt die Karten.
    7. B übermittelt die doppelt verschlüsselten und gemischten Karten der Partei A.
    8. A entschlüsselt alle Karten mit seinem Schlüssel (hier tritt die Kommutativität hervor).
    9. A verschlüsselt nun jede Karte einzeln, mit jeweils einem anderen Schlüssel. Die Karten sind nun alle mit einem Schlüssel von B verschlüsselt, sowie jede einzelne mit einem jeweils anderen Schlüssel von A.
    10. A übermittelt B die neuen Karten.
    11. B entfernt seine alte Verschlüsselung (erneut die Kommutativität).
    12. B verschlüsselt, genau wie A, jede Karte mit einem eigenen und anderen Schlüssel.
    13. B übergibt A die verschlüsselten Karten.
    14. A legt die Karten für alle Teilnehmer (hier 2) offen.

    Was liegt nun vor? Die Karten wurden alle gemischt und doppelt verschlüsselt – jeweils mit einem anderen Schlüssel von A und  B. Die Karten liegen nun „auf dem Tisch“ und die Teilnehmer einigen sich darüber, wer welche Karten bekommt. Werden die ersten 5 Karten A zugeteilt, teilt B die dafür notwendigen Schlüssel mit, und umgekehrt. Jeder besitzt also nun Karten aus diesem Kartenpool die nur dem Spieler selbst bekannt sind. Ein grundsätzlich sehr solides Verfahren. Insbesondere ist es relativ intuitiv, da in der ersten Runde die Karten lediglich verdeckt gemischt werden und in der zweiten Runde dafür gesorgt wird, dass niemand die gemischten Karten „einsehen“ kann.

    Wie schon erwähnt, muss hier zwar keine asymmetrische, jedoch eine kommutative Chiffre verwendet werden. In der oben genannten Quelle wird erklärt, dass ein XOR hier nicht genügt. Wie jedes Protokoll/Verfahren hat auch dieses Schwachstellen, welche sich allerdings beheben lassen und eventuell in einem eigenen Beitrag behandelt werden.

    Ob nun die oben genannte Open Source Software diese Verfahren einsetzt, kann ich nicht beantworten – vielleicht irgendein anderer interessierter Leser. Grundsätzlich besteht jedoch die Möglichkeit solch ein Pokerspiel durchzuführen – unter Umständen wesentlich sicherer als in den Spielcasinos.

  • Primfaktorzerlegung und NP

    Hallo,

    zunächst eine Warnung: dieser Beitrag ist relativ schwierig und ohne Vorkenntnisse in theoretischer Informatik nicht zu verstehen.

    Im Laufe einer Lehrveranstaltung hat sich die Frage gestellt, ob die Primfaktorzerlegung (genauer: RSA – also 2 Primfaktoren) in NP liegt bzw. sogar NP-vollständig ist – ums populärer auszudrücken: wie viel Ärger bekommen wir, falls P=NP gilt.

    Wir haben allerdings an dieser Stelle jedoch das Problem, dass die Komplexitätsklasse NP bzw. die Laufzeitfunktion NTIME auf Sprachprobleme – also Entscheidungen definiert ist. Innerhalb der Literatur finden sich wenig und vor allem sehr oberflächliche Aussagen darüber („es ist leicht einzusehen dass dieses Problem in NP liegt…“). Die letzten Wochen habe ich intensiver darüber nachgedacht und ich denke, eine brauchbare Lösung anbieten zu können.

    Zunächst wichtige Vorarbeit:  die Frage, ob eine natürliche Zahl eine Primzahl ist oder nicht, liegt in P (also deterministischer Polynomialzeit). Erreicht wird dies durch den AKS-Primzahltest. Damit ist auch die Frage, ob eine Zahl n (ungleich 1) Primteiler besitzt in P feststellbar, da dies immer der Fall ist, sofern es sich um keine Primzahl handelt (Hauptsatz der Zahlentheorie).

    Im nächsten Schritt prüfen wir, ob die Zerlegung des RSA-Moduls in NP liegt.

    Nichtdeterministische ZerlegungNehmen wir hierzu beispielhaft die Primzahlen p=7 und q=11 also M=p*q = 7*11=77, binär dargestellt 1001101. Mittels eines naiven Nichtdeterministischen Algorithmus, können wir von 1 bis sqrt(M) alle möglichen Teiler durchprobieren. Dass dies in NP liegt, soll mittels der Abbildung gezeigt werden. Die Baumtiefe entspricht n/2, also die halbe Eingabelänge n(=7). Der Übersicht halber hier nur die Tiefe 3 anstelle 4.

    Durch diese Verzweigung erhalten wir also alle Lösungskandidaten h.

    Im blauen Kasten prüfen wir nun, ob h ein Primteiler von M ist. Sowohl der Primzahltest „ist h eine Primzahl?“ liegt in P (wie oben erwähnt), als auch die Division „ist h ein Teiler von M“. Auch würde der Primzahltest des zweiten Divisors in P liegen. Dementsprechend liefert der skizzierte Nichtdeterministische Algorithmus am Ende ein „ja“, da 111 (=7) sowohl Primzahl, als auch Teiler von M (77) ist.

    Wir haben also nun festgestellt, dass die Frage nach der Primfaktorzerlegung in NP liegt. Das hilft uns allerdings nur bedingt, da diese Antwort schon vorher bekannt war. Per Definition besitzt ein RSA-Modul zwei Primteiler, daher würde der Algorithmus natürlich stets ein ja liefern. Wir müssen also dieses Entscheidungsproblem (1)  nutzen, um effizient das Optimierungsproblem (2) zu lösen.

    Aus diesem Grund definieren also das Problem in folgender Weise neu:

    Eingabe: (M,k) wobei m das RSA-Modul (bestehen aus dem Produkt zweier Primzahlen), und k eine beliebige Zahl k<=M.

    Zulässige Lösung: ja/nein

    Frage: liegt ein Primfaktor des RSA-Moduls M unterhalb von k.

    Wir übergeben also das Modul M=(p*q) und fragen, ob sich der kleinere Primfaktor unterhalb von k befindet. Dieses Entscheidungsproblem ändert am oben skizzierten Algorithmus die Laufzeit nur um einen konstanten Faktor, welche in der polynomiellen Unschärfe sowieso verschwindet. Wir sind inder Lage, wie in der nächsten Abbildung zu sehen, mittels einer binären Suche den Primfaktor exakt zu bestimmen:


    Binäre Suche nach dem Primfaktor

    Können wir also das Entscheidungsproblem (1) als Orakel verwenden, so lässt sich auch dieses Optimierungsproblem (2) sehr effizient (logarithmisch) lösen. Die binäre Suche geht in der polynomiellen Unschärfe verloren, womit wir informell bewiesen haben: bei P=NP liegt die Faktorisierung auch in P.

    Welche Auswirkungen hätte P=NP auf den Alltag? Diese Frage lässt sich leider nicht beantworten, da nicht jeder Algorithmus in P auch effizient ist. Wäre der Exponent jedoch niedrig, wären die Folgen schwerwiegend: die PKI würde zusammenbrechen, wodurch sicheres Online Banking unmöglich wäre. Jedes asymmetrische und damit auch jedes hybride Verschlüsselungssystem wäre hinfällig. Die Quantenkryptographie, die hiervon nicht betroffen wäre, liefert keinen adäquaten Ersatz.

    Hoffen wir also, dass P != NP gilt.

  • Peer to Peer – Sicherheit

    Hallo zusammen,

    vor Kurzem ist in einem Spieleforum die Frage aufgekommen, wie es mit der Sicherheit von Peer-to-Peer Systemen aussieht. Vermutlich werden jetzt viele Leser an die juristischen Folgen durch, populär ausgedrückt, „illegale Downloads“ denken. Damit soll sich dieser Beitrag allerdings nicht befassen. Außerdem muss auch die Frage geklärt werden, wieso sich ein „Spieler“, eine möglicherweise leicht Klieschee behaftete Gruppe, dafür interessiert.

    Insbesondere MMORPGs zeichnen sich durch einen sehr dynamischen Inhalt aus, was für viele einen Reiz darstellt, eine beachtliche Menge an Zeit zu investieren. Dies erfordert jedoch einen permanenten Aktualisierungsvorgang aller Clients. Viele „Kleinigkeiten“, wie Art/Position/Verhalten von s.g. NPCs können durchaus „on the fly“ dem Spieler mitgeteilt werden. Umfangreichere Änderungen, insbesondere neue Grafiken, erfordern jedoch eine Änderung des Programms bzw. der verwendeten Bibliotheken. Hiervon soll allerdings der Spieler möglichst wenig betroffen sein – insbesondere soll er nicht gezwungen sein auf dubiosen Webseiten die Patches zu laden und dann auf dem jeweiligen Rechner zu installieren. Jedoch ein Client-Server Modell, bei dem ein Server die Daten für alle Clients bereitstellt, ist nur für geringe Benutzerzahlen praktikabel. So bedeutet ein 100 MB Update, was durchaus nicht selten ist, bei 100.000 Spielern nunmal 10.000.000 MB Traffic, also 10 TB. An dieser Stelle sei noch anzumerken, dass es durchaus Spiele mit 5-10 Millionen aktiven Spieler gibt. Außerdem besteht ein betriebswirtschaftliches Interesse, die Kosten solcher Prozesse möglichst gering zu halten.

    Was also tun? Das Thema liefert die Antwort: Peer to Peer Netzwerke, kurz P2P. Wie funktioniert das?
    Nunja, viele leichtverständliche Informationen findet man auf einschlägigen Webseiten. Ich möchte an dieser Stelle insbesondere auf das P2P Netz eingehen, welches überwiegend beim Filesharing eingesetzt wird. Auch wenn „Filesharing“, „Peer to Peer“, etc. vielen Lesern die roten Alarmglocken schlagen lässt: es ist eine Technik, die von vielen Unternehmen eingesetzt wird und daran ist überhaupt nichts Illegal. Sie eignet sich allerdings auch zum Tausch von geschütztem Material wodurch sie häufig in einen falschen Zusammenhang gesetzt wird. Um dieses System in kurzen Worten zu erklären, möchte ich mich der Schneeball-Metapher bedienen:

    Durch umfangreiche Aufklärungsarbeit der öffentlich rechtlichen Funk und Fernsehanstalten sollte vielen Lesern bekannt sein, wie ein Schneeballsystem (oder ein Kettenbrief) funktioniert. Wir definieren eine Person, die ein Produkt an eine Reihe von Personen anbietet und nennen diesen Tracker. Diese Reihe von Personen bemühen sich, aus eigenem Interesse, möglichst viele weitere Personen für dieses Produkt zu gewinnen. Wir bezeichnen alle Personen, die daran interessiert sind, als Schwarm. Angenommen jeder Teilnehmer gibt das Produkt (oder die Information) nur an zwei Andere weiter, haben wir nach 30 Schritten schon eine Schwarmgröße von 1.073.741.823 (2^30-1). Der Aufwand für den Einzelnen, 2 weitere zu „finden“ bzw. zu bedienen, war relativ gering – in der Gesamtheit war das Produkt jedoch ein riesen Erfolg.

    Als Informatiker möchte ich jedoch an dieser Stelle anmerken, dass es sich hierbei um einen Baum der Ordnung 2 handelt – hingegen ein P2P System als ein Multigraph anzusehen ist. Übertragen auf das „Updateproblem“: der Tracker wirft den Patch also in die Menge (den Schwarm) und die Spieler organisieren sich untereinander diesen zu verteilen. Also läd man, bei diesem Vorgang, nicht vom offiziellen Server, sondern von Personen „wie dich und mich“ – jedoch natürlich nur von den Beteiligten.

    Nun zurück zu dem besorgten Spieler. Grundsätzlich handelt es sich hierbei auch um Programmaktualisierungen. D.h. der Programmcode wird entweder ersetzt oder Neuer wird eingefügt – je nach Updatestrategie. Ein Beweis hierfür ist auch leicht erbracht: Updater sind immer „extra“ Programme, also kein Unterprozess. So findet sich in dem entsprechenden Spielordner stets das Spiel selbst, als auch ein Updater als ausführbare (exe) Datei.

    Und daher nun endlich die Frage: Können mir andere Spieler „Schadcode“ übergeben, der sich dann, durch den Updatevorgang, auf meinem Rechner befindet?

    Damit habe ich mich etwas Näher befasst. Zunächst muss natürlich klar sein, dass diese Frage nicht für alle Spiele geklärt werden kann. Grundsätzlich werden Daten von unbekannten Quellen geladen und diese können durchaus Fehlerhaft sein – gewollt oder ungewollt. Das ist die schlechte Nachricht. Die Gute ist, dass sich viele Spielebetreiber Techniken bedienen, die sich mittlerweile als Standard etabliert haben. Das relativ bekannte „BitTorrent“ Protokoll ist eines dieser – wofür es auch sehr viele und gute Clients gibt. Bei dieser Technik erhält der Client ein File genannt „Torrentfile“. Dieses enthält eine Auflistung der Dateien, die geladen und verteilt werden müssen – zusätzlich weitere triviale Informationen.
    Am Ende, das lässt uns wieder aufatmen, ein SHA-1 Hash für jeden Part. Wer mag, kann an dieser Stelle einen Exkurs zum aktuellen Stand der Technik bzgl. der Sicherheit des SHA-1 unternehmen.

    ~

    Wieder zurück? Gut. Denn selbst wenn wir ein Programm hätten, das uns „günstig“ Kollisionen des SHA1 aufzeigt, wäre es sehr unwahrscheinlich, dass dabei ein Teil eines ausfühbaren Programmes herauskommt und gleichzeitig auch den gewollten Schadcode enthält. Diese Thematik lässt sicherlich Platz für Diskussionen – allerdings kann an dieser Stelle und an diesem Tag festgehalten werden, dass der SHA-1 Hashalgorithmus für diesen Einsatzzweck noch völlig genügt. Was ein Hashcode „genau“ ist, habe ich in diesem Beitrag beschrieben: http://cryptblog.de/2008/06/18/hacken-fur-anfanger/

    Es besteht also keinen Anlass zur Beunruhigung. Sofern der Tracker das Torrentfile korrekt an den Benutzer überträgt, ist ein P2P System (basierend auf BitTorrent), für diesen Einsatzzweck ausreichend sicher.

  • Warum nichts tun eine „gute Arbeit“ ist

    Es gibt einen ganz einfachen Grund warum „nichts“ arbeiten eine „gute Arbeit“ ist.

    Wir definieren uns eine Menge A welche das Ergebnis unserer Arbeit repräsentiert. Wie angegeben ist dies „nichts“ also
    A = { } (die leere Menge).

    Nun definieren wir uns eine Menge G, welches die „gute Arbeit“ darstellt, also alle sinnvollen Tätigkeiten; x0, x1, x2, … xn seien die Elemente dieser Menge:

    G = {x0, x1, x2, … xn}

    Nun zeigen wir, dass unsere Arbeit A eine Teilmenge von G ist.

    Dies gelingt über einen Widerspuchsbeweis:
    Sei A (also die leere Menge) keine Teilmenge von G, so existiert ein x element A welches in G nicht zu finden ist.
    Dieses x ist also ein Element der leeren Menge -> Widerspruch gemäß Definition der leeren Menge, welche die Mächtigkeit |{ }|=0 besitzt.

    Damit ist also unsere Arbeit A eine Teilmenge von G und wir leisten täglich, auf dem Sofa, eine gute Arbeit. Und es erklärt, warum hier in der letzten Zeit so wenig passiert ist.

  • Cluedo und Informatik

    Ausnahmsweise mal etwas, was nichts mit Kryptographie und IT-Sicherheit zu tun hat.

    Während einem Spiel Cluedo, bei dem es darum geht mittels eigenen (eigene Karten) und fremde Informationen (fremde Karten) auf neue Informationen (Lösungskarten) zu schließen, habe ich mir die Frage gestellt, in wie fern die Informatik einem an dieser Stelle helfen kann. Zunächst eine Spielbeschreibung von Wikipedia.de:

    Auf dem Spielplan ist der Grundriss eines Hauses mit neun Räumen und dem Flur dargestellt. In diesem Haus ist Dr. Schwarz (auch Graf Eutin) ermordet worden und alle Mitspieler übernehmen im Verlaufe des Spiels die Rolle eines Detektivs. Am Anfang wird von jedem Kartenstapel der Verdächtigen, Mordwerkzeuge und Mordzimmer jeweils eine Karte verdeckt gezogen. Diese gilt es im Laufe des Spiels zu ermitteln. Alle übrigen Karten werden an die Mitspieler verteilt. Diese können nun durch geschickte kombinierte Verdächtigungen, die sie immer den anderen Mitspielern vortragen, erfahren, welche Karte diese besitzen. Dadurch muss jeder auf den korrekten Mörder, die Tatwaffe und den Tatort Rückschlüsse ziehen. Wer zuerst diese drei Fragen richtig beantworten kann, hat gewonnen. Wer allerdings eine falsche Anklage erhebt, scheidet aus. Es existieren mit sechs Verdächtigen, sechs Tatwaffen und neun Räumen insgesamt 324 verschiedene Lösungskombinationen.

    Die Anzahl der Möglichkeiten ist also die Mächtigkeit aus dem Kreuzprodukt: Verdächtige (Täter) x Waffen x Räume. Bei 3 Spielern erhält jeder Spieler 6 Karten auf die Hand (3*6+3). Je nachdem von welchem Typ diese Karte sind, verringert sich die Lösungsmenge zunächst. Nun hat jeder Spieler das Ziel, diese Menge auf 1 zu reduzieren, indem er anderen Spielern Fragen stellt (Täter – Waffe – Raum). Sofern der nächste Spieler in der Runde eine (oder mehrere) dieser genanntne Karten besitzt, muss sie, allerdings im Verborgenen, dem Fragesteller gezeigt werden. Damit kann dieser die mögliche Lösungsmenge weiter vermindern.
    (1) Diese Menge mit Hilfe der eigenen Karte und die Karten, die einem von anderen gezeigt worden sind zu reduzieren ist vergleichsweise einfach bzw. müssen nur von der Liste gestrichen werden.
    Kritischer ist die Einschränkung durch Kommunikation der anderen Spieler untereinander (2). Fragt beispielsweise Spieler B nach 3 Karten und zeigt Spieler C eine dieser, ist zunächst nicht bekannt welche, außer ich besitze konkrete Informationen über 2 dieser 3 Karten und kann ausschließen, dass eine dieser vorgezeigt wurde. Kann ein Spieler auf eine Anfrage nicht antworten (3), ist dies erneut eine wichtige Information, denn wenn bekannt ist, dass alle Spieler eine Karte nicht besitzen, ist dies die gesuchte Gewinnkarte.

    Es ist allerdings nur sehr schwer möglich ALLE Informationen auf einem kleinen Zettel durch Striche, Kreise und Pfeile zu notieren. Insbesondere die Auswertung fällt sehr schwer. Deshalb übergehen viele Spieler einfach Informationen welche sie zunächst nicht direkt in eindeutige Informationen umwandeln können. Lässt sich also aus einer Handlung (Spieler B zeigt Spieler C eine unbekannte Karte) nicht direkt eindeutig verarbeiten (Spieler B besitzt Karte X), wird diese Information nicht weiter notiert. Dies ist natürlich ein Fehler welcher durch die Informatik korrigiert werden soll. Daher habe ich ein 4-Tupel zur Speicherung jeder Information gewählt, welche sich aus Täter (Verdächtiger), Waffe, Raum und dem Spieler der darauf antworten konnte, zusammensetzt. Aufgrund der vorherigen Informationen und jener, die erst im weiteren Verlauf des Spiels gewonnen werden, lässt sich unter Umständen (in manchen Fällen auch nachträglich) ermitteln, um welche Karte es sich dabei gehandelt hat. Wie diese Informationsmengen (Eindeutige Karten, Mehrdeutige Karten (siehe Beispiel), Negationale Karten (falls jemand nicht Antworten kann)) zu verarbeiten sind, habe ich in einem PDF zusammengefasst. Es enthält durchaus noch einige Fehler und ist auch nicht als wissenschaftliche Veröffentlichung anzusehen – ist ist mehr eine Skizze aus der noch weiteres entstehen kann.

    Hier das PDF:
    http://www.cryptblog.de/cluedo1.pdf

    Ich habe das Ganze auch in Java programmiert und einem Praxistest unterzogen. Dabei hat es sich durchaus bewährt – wobei die Leistung nur schwierig einzuschätzen ist, da Glück ein wichtiger Bestandteil dieses Spiels ist.
    Es handelt sich dabei allerdings AUSSCHLIESSLICH um die Aufarbeitung und Auswertung bekannter Informationen. Der Algorithmus bietet keinen dominanten Lösungsweg durch das Spiel bzw. stellt (noch) nicht Fragen an andere Spieler. Dies wäre eine Arbeit, die darauf aufsetzen könnte.

  • Mathematik zum Anfassen – Kryptographie

    Hallo!

    Diesmal nur ganz kurz eine kleine und Interessante Einführung in die Kryptographie, aus der Reihe „Mathematik zum Anfassen“ von Prof. Albrecht Beutelspacher:
    -> Video <-

    Einges davon sollte dem treuen cryptblog.de Fan schon bekannt sein.

  • Zufällige Entscheidungen

    Hallo zusammen,

    vor kurzem hatten ein Kommilitone und ich ein Problem. Wir wollten (über das Internet) ausknobeln, wer von uns mit dem Auto fahren muss und wer dafür Alkohol trinken kann. Ein Schnick-Schnack-Schnuck über das Internet sozusagen. Beide hatten wir nach einer Lösung für dieses Problem gesucht jedoch keine wirklich gute gefunden. Zuletzt entschieden wir uns dazu, es über die Anzahl der Heise.de-News des nächsten Tages zu bestimmen. Je nachdem ob es eine gerade oder ungerade Anzahl ist, muss der eine oder der andere.

    Die Frage ist also, ob es dafür bessere Lösungen gibt. Mit Hilfe einer dritten, unabhängigen Instanz sollte dies nicht so schwierig sein, einige Lösungsbeispiele habe ich dafür mal ausgearbeitet:

    Beide Parteien könnten mit einem Client auf einen Server verbinden. Sobald alle verbunden sind, gibt dieser eine zufällige Zahl aus. So hat man, synchronisiert, allen Teilnehmern dieses Ereignis zugänglich gemacht.

    Oder man könnte eine Webseite bereitstellen, die alle 5 Minuten eine zufällige Zahl ausgibt. So könnten beide Parteien Vermutungen über die nächste Ausgabe treffen und diesbezüglich eine Entscheidung finden. Um dieses Beispiel zu verdeutlichen habe ich diese Webseite angefertigt: http://www.cryptblog.de/random.php.

    Eine weitere Möglichkeit wären Kryptogramme eines Servers: Partei A bezieht ein aktuelles Kryptogramm von einem Server, welches eine verschlüsselte Zahl enthält. Er übergibt das Kryptogramm der Partei B und beide einigen sich darauf, welche Entscheidung bei einer geraden/ungeraden getroffen wird. Die Entschlüsselung ist allerdings erst später (~5 Minuten) möglich. Ich denke allerdings, dass diese Lösung unnötig kompliziert ist und kaum einen Vorteil gegenüber den anderen besitzt.

    Aber nun die Frage: ist es möglich eine solche Entscheidung zu treffen, ohne dass ein Dritter (Server) beteiligt ist? Meine Antwort darauf ist JA. Folgendes Verfahren habe ich mir überlegt:

    Sowohl A, als auch B, denken sich eine möglichst große zufällige Zahl (a und b) aus. Mit Hilfe einer Webseite, die hier lediglich als „Taschenrechner“ dient, berechnen A und B jeweils einen Hash (Fingerabdruck, beispielsweise MD5) ihrer Zahl, also z.B. H(a) und H(b). Über ein beliebiges Kommunikationsmedium kann nun dieser Hashwert ausgetauscht werden. Außerdem müssen sich A und B jeweils für eine gerade oder ungerade Zahl entscheiden. Durch diesen Austausch, haben sich beide auch damit einverstanden erklärt, dieses Verfahren zu nutzen. Nachdem also Hashwerte ausgetauscht sind, ist jeder im Besitz seiner eigenen Zahl und einem Fingerabdruck der Zahl des anderen.

    Jetzt kann jeder seine Zahl dem anderen nennen, ob nun A oder B zuerst ist egal. Beide Zahlen werden miteinander addiert, also m = a + b berechnet, und je nachdem ob diese Zahl gerade oder ungerade ist, fällt die Entscheidung für A oder B aus. Aufgrund des vorherigen Austausch der Hashwerte, ist ein nachträgliches ändern der Zahl nicht möglich bzw. A und B können die Aussagen des anderen verifizieren.

    Um dieses Beispiel zu verdeutlichen, existiert eine neue Sektion und ein Script um die Durchführung zu vereinfachen: http://cryptblog.de/muenzwurf/.

    Nochmal grob zusammengefasst:

    zufallprotokoll
    A prüft H(b)=H(b‘), B prüft H(a)=H(a‘). Sofern beides wahr, kann von a’=a und b’=b ausgegangen werden.
    Beide berechnen m = a+b.

    Mittels diesem Protokoll hat jeder Teilnehmer eine 50% Chance zu gewinnen:

    geradeungerade

    In der Anwendung ist folgendes zu beachten:

    Die Hashfunktion sollte einigermaßen sicher sein und um Rainbowtables entgegenzuwirken, sollten die Zahlen möglichst groß sein. Sofern dies erfüllt ist, können auch JavaScript Lösungen zum berechnen verwendet werden, wie z.B. http://aktuell.de.selfhtml.org/artikel/javascript/md5/ .

    Nachtrag:
    Grundsätzlich kann man dieses System auch, leicht modifiziert, für das bekannte Stein-Schere-Papier einsetzen, indem ein Hash von Stein|Zufallszahl, Schere|Zufallszahl oder Papier|Zufallszahl gebildet und später ausgetauscht wird. Das macht die vorherige Absprache ob gerade oder ungerade unnötig.

  • ITS-Quiz für Zwischendurch

    Hallo,

    es handelt es sich um Protokollsicherheit in Verbindung mit asymmetrischer Verschlüsselung. In diesem Szenario möchte die Partei A eine geheime Information an Partei B senden. A besitzt den geheimen Schlüssel zum öffentlichen Schlüssel PK_A, und B äquivalent PK_B. Hierbei wird folgendes Protokoll verwendet:

    (1) A –> B:     (A, E(PK_B, A|M), B)
    (2) B –> A:     (B, E(PK_A, A|M), A)

    also: (Absender, Nachricht, Empfänger) wobei Nachricht = Absender|Information.

    Schritt für Schritt: A sendet an B eine Nachricht, diese besteht aus

    • dem Absender (A),
    • dem asymmetrisch verschlüsselten Text M wobei dieser noch mit  und dem Absender verbunden wurde (A|M),
    • dem Empfänger (B).

    daraufhin bestätigt B den Erhalt der Nachricht durch:

    • den Empfänger (B),
    • die exakt identische Nachricht, diesmal allerdings mit dem öffentlichen Schlüssel des ursprünglichen Absenders – also des neuen Empfängers (PK_A) verschlüsselt,
    • den Absender der usprünglichen Nachricht (A).

    E(PK_X, M) ist die asymmetrische Verschlüsselung, z.B. RSA, mit Hilfe des öffentlichen Schlüssels X, im obrigen Beispiel also jeweils des Empfängers. Das Ganze etwas anders ausgedrückt: Die Partei A sendet eine Nachricht an B, wobei diese mit dem öffentlichen Schlüssel des Empfängers verschlüsselt wurde und außerdem auch den Absender enthält.

    Im Zuge einer Umstellung wurde das Protokoll abgeändert auf:

    A –> B:     (A, E(PK_B, M), B)
    B –> A:     (B, E(PK_A, M), A)  (Bestätigung)

    Der Unterschied: der Absender ist hier nun nicht mehr innerhalb der verschlüsselten Nachricht enthalten.

    Frage: ergibt sich daraus ein Problem? Wo ist der Unterschied bzw. gibt es überhaupt einen?

  • Auflösung Februar

    Hallo liebe Gemeinde,

    eine Vermutung wurde ja geäußert (siehe Kommentare). Dieser geht in die Richtung, den Klartext mit einem zufälligen Schlüssel zu chiffrieren und diesen wiederrum mit dem geheimen (ausgetauschten) zu verschlüsseln und an die Nachricht anzuhängen. Also: [E_tempkey(Text) | E_key(tempkey)]. Also ein ähnliches System wie bei den DLC-Containern.

    Die Idee ist natürlich nicht schlecht, allerdings handelt es sich hierbei um etwas anderes. Und zwar gibt es in der Praxis verschiedene Betriebsmodi; um einige zu nennen: ECB, OFB, CFB. Und an dieser Stelle wurde der CBC „Cipher Block Chaining“ Modus verwendet. Was dies nun genau bedeutet ist etwas schwierig zu eklären, daher beschränke ich mich an dieser Stelle darauf den Unterschied zwischen dem simpelsten (ECB) darzustellen.

    Beim ECB-Modus wird der Klartext in gleiche Stücke getrennt. Im Beitrag zur Bildverschlüsselung (http://cryptblog.de/2008/10/06/bildverschlusselung/) hatte ich dieses Verfahren bereits erläutert. Dort wurde

    “Hallo, wie geht es dir  ”

    in:

    “Hallo, w”, “ie geht “, “es dir  ”

    aufgeteilt. Jeder dieser Blöcke wird mit dem gleichen Key verschlüsselt und so erhalten wir am Ende wieder 3 Blöcke. Beispielhaft dargestellt:

    “mdjwbcxg”, “ötüeoejd”, “ndkrdkdp”.

    Angenommen ich ändere das „Hallo“ im Klartext in ein „Hello“, so würde sich nur der erste Block ändern, die anderen zwei blieben unberührt. Und um diesen Einfluss zu vergrößern gibt es die oben genannten Betriebsmodi. Ein Bild dazu aus Wikipedia zum CBC-Modus:

     cbc_encryption

    Zunächst schwierig zu verstehen. Auf der linken Seite haben wir den sehr bekannten Initialisierungsvektor. Bei der Blowfish-Implementierung wird dieser einfach zufällig gewählt. Er wird mit dem Klartext verrechnet (XOR). Das Ergebnis daraus, wird verschlüsselt und ergibt den Chiffretext welches wiederrum auf den nächsten Klartextblock Einfluss nimmt. Durch diese Pfeile ist also zu sehen, dass der Vorgänger immer auf den unmittelbaren Nachfolger einwirkt.

    Dadurch ergibt sich eine Kette: wird am Anfang eine Veränderung vorgenommen, ändert dies den kompletten restlichen Chiffretext. Und da, wie schon erwähnt, der IV gewürfelt wird, ergibt sich bei jeder Verschlüsselung einen anderen Chiffretext. Zur Entschlüsselung wird allerdings dieser Vektor benötigt, daher wird er einfach mitgeschickt. Aus dem Plaintext P wird also nicht nur ein Chiffretext C, sondern beinhaltet auch einen IV.

    Verstanden sollte sein, dass diese „Block für Block“-Verschlüsselung Probleme bereiten kann und ein Betriebsmodus, wie der CBC, für noch mehr Einflussnahme des Klartextes sorgt.

  • „Sicher im Internet“

    Ich möchte an dieser Stelle  nur kurz auf den neuen Bereich „Sicher im Internet“ hinweisen.  Es handelt sich dabei um einen Teil meiner Abschlussarbeit. 

    Im Laufe der zunehmenden Verbreitung des Internetzugangs sind Anwender häufig damit überfordert die Gefahren richtig einzuschätzen, die im Umgang mit den neuen Medien entstehen können. Die Anzahl der Internetnutzer – sowohl geschäftlich als auch privat –  steigt kontinuierlich. Im Mai 2007 wurde festgestellt, dass bereits jeder 5. Mensch (1,23 Milliarden) daran teilnimmt.

    Nach Untersuchungen des Antivirus-Herstellers „Kaspersky Lab“ ist jeder zehnte PC Teil eines Bot-Netzwerkes. Die Ursache liegt häufig in Fehleinschätzungen von E-Mail Dateianhängen oder heruntergeladenen Dateien aus dem Internet. Nur in seltenen Fällen sind sog. Exploits die Ursache, bei denen der Anwender keine Mitschuld trägt.

    Probleme dieser Art lassen sich häufig schon durch Aufklärung vermeiden oder zumindest eindämmen. Informationsmaterial zu dem Thema PC–Sicherheit, welches auch für Laien verständlich und leicht zugänglich ist, soll dem Benutzer helfen Gefahren rechtzeitig zu erkennen. Innerhalb der Abschlussarbeit wurden verschiedene Gefahrenquellen analysiert und in geeigneter Weise aufgearbeitet.
    Eine Quiz soll u. A. zur Wissensvermittlung dienen.

     >>> Hier geht es zum Quiz