| Vernam - Mr. Knack schlägt zurück |
|
|
Letztmalig dran rumgefummelt: 11.02.14 16:18:07 |
 |
Richtig angewandt ist der VERNAM-Code definitiv nicht zu knacken - er ist dann ein One Time Pad. Das ist aber in der Praxis bei großem Nachrichtenaufkommen sowie langen Texten reine Utopie in der Durchfürhrbarkeit. Die korrekte Bereitstellung geeigneter Schlüssel macht hier die Probleme - es müssen reale Zufallsmuster in großer Zahl sowie Länge beschafft werden. | |||||||||
 |
0. Das Problem "Zufall" 1. Zur Geschichte 2. Der Vernam-Chiffre binär klassisch 3. Die Software-Lösungen ... 4. Verwandte Themen |
|||||||||
|
|
|||||||||
 |
Quellen:
|
|||||||||
|
|
| 0. Das Problem "Zufall" |
|
|
 |
|
|
Mit der Elektrifizierung der
Nachrichtenübertragung wurde eine binäre Umsetzung des Alphabets nötig, da
elektrischer Draht nur Stromstösse weiterleiten kann. Als eine Folge wurde
das Morsealphabet entwickelt. Von da an war es auch zum chiffrierten Text
nicht mehr weit. |
||||||||||
|
|
|
||||||||||
|
|
|
| 1. Angriffspunkte |
|
|
|
|
|
In seinem Beitrag in mc 9/90 schlägt Hans-Georg Nacke zur Verschlüsselung das Vernam-Verfahren mit einem Pseudo-Zufallsgenerator auf der Basis eines Schieberegisters und eine anschließende Umordnung des Textes mit Hilfe eines weiteren kleinen Schieberegisters vor. Schieberegister werden in der Kryptologie für solche Zwecke oft benutzt, und der Beitrag von Herrn Nacke gibt eine schöne Einführung in dieses interessante Thema. Nun sind gerade in Sicherheitsfragen immer die Details zu beachten, und so liefert Herr Nacke einige Angriffspunkte, die es ermöglichen, das komplette Verfahren mit geringem Aufwand auszuhebeln. Wir analysieren jedes der beiden vorgeschlagenen Verfahren für sich und geben zum Schluss eine Betrachtung des Gesamtverfahrens. Im ersten Teil wird eine Vernam-Verschlüsselung mit einem Pseudo- Zufallsgenerator auf der Basis eines Schieberegisters beschrieben. Der Startwert des Schieberegisters ist der Schlüssel für diesen Teil. Wir werden für das Beispiel in Tabelle 4 von [3] aufgrund von minimalen Annahmen über den Klartext den Inhalt des Schieberegisters berechnen. Die Kryptoanalyse eines so kleinen Beispiels mag unfair erscheinen, aber hier kann man noch alle Rechnungen per Hand nachvollziehen und die Vorgehensweise gilt auch für größere Beispiele, die man angehen kann. |
|
|
Erster Angriffspunkt: Das Schieberegister ist zu klein. Wir brauchen nur 9 Bit Information und können dann den Zufallvorhersagen. |
|
|
Zweiter Angriffspunkt: Die Dezimation (d=5) ist zu klein. Teile der Zufallsbitfolge werden bei zwei aufeinanderfolgenden Zeichen benutzt. |
|
|
Dritter Angriffspunkt: Die ASCII-Zeichen sind ungleich verteilt. Texte bestehen in der Regel zum größten Teil aus Kleinbuchstaben. Großbuchstaben, Zwischenräume und Sonderzeichen sind seltener und bilden keine langen Ketten. |
|
|
Glücklicherweise haben alle kleinen Buchstaben einen ASCII-Code, der mit den
Bit 011...B (61H
bis 7AH) beginnt. Finden wir eine Stelle
im Text, bei der mehrere Kleinbuchstaben aufeinanderfolgen (solche Stellen
gibt es ja immer), so können wir berechnen, welchen Wert die führenden drei
Bit des Zufallsgenerators hatten. Da die drei erkannten Bit wegen der
geringen Dezimation im nächsten Byte des Zufallsgenerators wieder vorkommen,
kennen wir nun schon sechs Bit. Die restlichen drei Bit liefert eine
einfache Rechnung. (Bild 1) zeigt das Schieberegister, auf das wir uns im
folgenden beziehen.
... das Schieberegister
|
| 2. Berechnung der fehlenden Bits |
|
|
|
|
|
Der eigentliche Rechenvorgang bei der Vernamverschlüsselung ist bestechend einfach, da es sich um eine einfache Addition (Kodierung: x ¤ y) bzw. Subtraktion (Dekodierung: [x ⊕ y] ⊕ y = x ) von Ziffern handelt. Trotz der Einfachheit des Verfahrens wählt man in der Praxis zweckmäßigerweise zwei leicht voneinander verschiedene Verfahren, je nachdem ob von Hand oder mit dem Computer gearbeitet wird. |
|
|
Vom Inhalt des Schieberegisters an der Stelle, wo u verschlüsselt ist, kennen wir schon sechs von neun Bit. Die Register Z8, Z7, Z6, Z5, Z4, Z2, Z1, Z0, haben nacheinander und in dieser Reihenfolge den Inhalt x, 1, 0, 1, y, 0, 1, 0, z an der Stelle von u. |
|
|
|
|
|
ergibt keinen Widerspruch. Anhand der Probe kann man feststellen, ob man
an der richtigen Stelle im verschlüsselten Text kleine Buchstaben vermutet
hat. Unser Angriff benötigt also mindestens sechs aufeinanderfolgende
beliebige kleine Buchstaben, um den Inhalt des Schieberegisters zu
berechnen. Die Kenntnis von zwei aufeinanderfolgenden Buchstaben (solche Paare gibt es ja im Deutschen jede Menge) würde auch genügen. Mit etwas mehr Information kann man weitere Parameter des Schieberegisters, wie das Rückkopplungspolynom, berechnen. Diese Attacken würden sehr erschwert, wenn
|
|
|
 |
|
|
Im zweiten Verfahren wird eine Umordnung des Textes mit Hilfe eines
weiteren kleinen Schieberegisters realisiert. Da die Werte eines
Schieberegister mit richtig gewählter Rückkopplung alle 2" - 1 Werte
ungleich Null nacheinander durchläuft, ist es hervorragend geeignet, eine
Umsortierung zu beschreiben, denn kein Wert kommt während eines Durchlaufs
doppelt vor. So muss sich der Umsortieralgorithmus keine Tabelle anlegen,
sondern kann munter drauflos kopieren. Um diesen Vorteil nicht zu verlieren,
o- kann die Ordnung des Schieberegisters nicht er größer sein als das benutzte Feld. Es gibt 64 Fakultät (64!= 64 * 63 * 62 * ...) Möglichkeiten ein Feld mit 64 Elementen umzusortieren, aber das vorgeschlagene Verfahren nutzt davon nur 64. Das heißt, man muß durchschnittlich 32 mal einen Startwert raten, zurücksortieren und die obige Attacke durchführen, um zum Erfolg zu kommen. Auch ein Feld mit zweitausend Elementen würde den Aufwand für die Attacke nurvertausendfachen. Ein solcher Faktor macht aus einem angreifbaren Verfahren (Teil 1 mit den kritisierten Mängeln) kein sicheres. Betrachtet man die effektive Schlüssellänge des Verfahrens von Heinz-Georg Nacke, das heißt die minimale Information in Bit, die man braucht um zu entschlüsseln, so kommen wir auf 9 + 6 = 15 Bit. Das ist entschieden zu wenig, aber nur im ersten Teil ist es möglich, den Schlüssel wesentlich zu vergrößern. Moderne Kryptoverfahren haben erheblich größere Schlüssel, so stellt der DES (Data Encryption Standard) mit 56 Bit effektive Schlüssellänge etwa das gängige Minimum dar. Dr. Gunterlaßmann/ks Literatur Zur Kryptodiskussion: [l] Schlessmann, K: „Ein unknackbares Chiffrierverfahren".mc 1/89 , S. 86-89. [2] Laßmann, G.: „Der Schlüssel zum Schlüssel". mc 7/89, S. 50-51. [3] Nacke, H.-G.: „Eine harte Nuß für 'Knack'". mc 9/90, S.84-92. Zum Vertiefen des Themas: [4] Denning. „Cryptography and data security". Addison-Wesley, 1982. [5] Heider, Kraus, Welschenbach: „Mathematische Methoden der Kryptoanalyse". DuDFachbeiträge B. Vieweg, 1985. |
| 3. Die Software-Lösungen ... |
|
|
|
|
|
Die Software zu diesem
Problemkreis wurde im Frühjahr 2012 mit Delphi 6.0 erstellt. Dies hat zum
einen den Grund, dass wir als Schule die erforderlichen Lizenezen halten
sowie den, dass dieses System in sich vollkommen zur Problemlösung
ausreichend und dabei doch aufwärtskompatibel ist und "sauber" programmiert
werden muss. Für die Anwendung, welche auf den ersten Blick etwas umständlich erscheinen mag, stand als Entscheidungskriterium vor allem die Nachvollziehbarkeit im Raum. Und da auch ich nicht solche Projekte an einem Tag stricke (zumal man bei diesen Dimensionen wirklich erst bei der Arbeit am Projekt seine innewohnenden Potenzen bemerkt), gibt's hier mal die Komplettübersicht, wie dieses Projekt "gewachsen" ist. |
||||||||
|
|
||||||||
|
... und was man beachten muss: zuerst der Text (Plain- oder Ciphertext) |
||||||||
|
|
| 4. Verwandte Themen |
|
|
|
|
|
Der VERNAM-Chiffre war als der Hammer, welcher er dann wurde, zu seiner Geburt als solcher nicht abzusehen, dabei gehört er zu den Chiffren, welche die Kryptologie um wesentliche Aspekte bereichert haben. Grundsätzlich und bis heute unbestritten sowie mathematisch klar nachweisbar, liegen in diesem Verfahren die Möglichkeiten zum nicht knackbaren Chiffre/Code! Im Versuch blickt er da ja durchaus auf einige repräsentative Verwandte zurück | ||||||||||||
|
|
||||||||||||
 |
|
||||||||||||
 zur Hauptseite |
© Samuel-von-Pufendorf-Gymnasium Flöha | © Frank Rost am 1.November 2013 um 10.29 Uhr |
|
... dieser Text wurde nach den Regeln irgendeiner Rechtschreibreform verfasst - ich hab' irgendwann einmal beschlossen, an diesem Zirkus nicht mehr teilzunehmen ;-) „Dieses Land braucht eine Steuerreform, dieses Land braucht eine Rentenreform - wir schreiben Schiffahrt mit drei „f“!“ Diddi Hallervorden, dt. Komiker und Kabarettist |
|
Diese Seite wurde ohne Zusatz irgendwelcher Konversationsstoffe erstellt ;-) |
Version 1.0 vom 14.3.12
als startbare EXE-Datei
