Die Community zu .NET und Classic VB.
Menü

Advanced Vigenère

 von 

Übersicht 

Xor-Verschlüsselung, auch als Vigenère bekannt, ist eine bei Programmieranfängern sehr beliebte Methode der Verschlüsselung, da sie wunderbar einfach ist. Leider jedoch hat sie den Haken, daß sie aufgrund ihrer Einfachheit auch mit relativ wenig Aufwand zu knacken ist.

Im ActiveVB-Forum gab es vor kurzem eine recht hitzige Diskussion darüber, ob eine erweiterte Xor-Methode, die in der Theorie unangreifbar ist, sich auch in der Praxis bewähren könnte. Dieser Aufsatz soll zeigen, daß genau das der Fall ist. Die unten geschilderte Methode ist durch kein bisher bekanntes Verfahren der Kryptanalyse brechbar, außer natürlich durch eine Brute-Force-Attacke auf das Kennwort.

Geschichte  

Blaise de Vigenère (*1523) war ein französischer Diplomat, der seinen Lebensabend der Krypto­graphie widmete und verschiedene kryptographische Systeme so weiterentwickelte, daß sie eine quasi sichere Verschlüsselung ergaben, was ihr jahrhundertelang den Namen "chiffre indéchiffra­ble" – unknackbare Chiffre – eintrug. Trotzdem war dem Algorithmus kein großer Erfolg beschert, da das recht einfach anmutende Verfahren in der Praxis doch so aufwendig war, daß sich eine An­wendung nicht ergab, bis das System schließlich im Jahre 1854 von Charles Babbage und unabhän­gig davon noch einmal 1863 von Friedrich Kasiski geknackt wurde.

Das Verfahren basiert darauf, das traditionelle monoalphabetische Verschlüsselungsalphabet (Caesar-Verschlüsselung u.ä.) durch mehrere Alphabete zu ersetzen – um genau zu sein 26, eines für jeden Buchstaben. Um die Erklärung kurz zu halten, sei einfach gesagt, daß das Verfahren mathematisch fast genau der sogenannten Xor-Verschlüsselung entspricht, die wahrscheinlich jeder kennt:

Man nehme einen zu verschlüsselnden Text sowie ein Schlüsselwort. Nun wird das Schlüsselwort so oft hintereinandergeschrieben, bis es genauso lang wie der Text ist. Nun nimmt man je einen Buchstaben des Texts und einen des Schlüssels und Xor't deren Bytewerte. Auf diese Weise verfährt man mit dem gesamten String.

Implementierung  

Ein einfacher Algorithmus dafür in VB sähe folgendermaßen aus:

Private Function Vigenère(Text As String, Key As String) As String
    Dim Position        As Long
    Dim KeyPos          As Long
    Dim PlainChar       As Byte
    Dim KeyChar         As Byte
    Dim CypherChar      As Byte
    
    Vigenère = String$(Len(Text), 0)
    For Position = 1 To Len(Text)
        KeyPos = KeyPos + 1
        If KeyPos > Len(Key) Then KeyPos = 1
        PlainChar = Asc(Mid$(Text, Position, 1))
        KeyChar = Asc(Mid$(Key, KeyPos, 1))
        CypherChar = PlainChar Xor KeyChar
        Mid$(Vigenère, Position, 1) = Chr$(CypherChar)
    Next Position
End Function

Nun ist spätestens seit Kasiski bekannt, wie unsicher der Code vor einer systematischen Analyse ist, es geht sogar noch einfacher: wenn zwei Texte mit dem selben Schlüssel verschlüsselt sind, enthält man ein lösbares Gleichungssystem, das es einem erlaubt, auf mathematischem Wege den Schlüssel zu ermitteln. Nicht so jedoch, wenn für die Verschlüsselung ein sogenanntes OTP als Schlüssel verwendet wird. Ein OneTimePad trägt nur genau dann diesen Namen, wenn es drei Ansprüche erfüllt:

  • Es ist genauso lang wie die zu verschlüsselnde Nachricht
  • Es wird nur genau ein einziges Mal verwendet und dann nie wieder
  • Es besteht aus einer vollkommen zufälligen Zeichenfolge

Und genau aus diesem Grund ist Vigenère sehr schnell in der Senke verschwunden: diese drei Punkte waren absolut unpraktikabel und sind selbst im Computerzeitalter ein quasi unerreichbares Ziel. Man stelle sich vor, man möchte eine Mail verschlüsseln. Überhaupt kein Problem (wenn man einmal davon absieht, daß der Computer keinen echten Zufall kennt), die Mail läßt sich verschlüs­seln und an einen Freund schicken. Wie aber will der Empfänger jetzt die Mail wieder entschlüs­seln? Er bräuchte den Schlüssel. Und da der genauso lang wie die Nachricht selbst ist, fängt das Problem wieder von vorne an. Dies und der Fakt, daß in letzter Zeit andere sehr sichere Verfahren gefunden wurden, haben Vigenère unnötig gemacht.

Warum also interessiert man sich noch immer für Vigenère? Ganz einfach weil Vigenère zumin­dest in der Theorie das einzige bis jetzt bekannte Verfahren ist, das mathematisch bewiesen un­knackbar ist. Und allen Zweiflern zum Trotz kann das Verfahren auch in der Praxis uneinnehmbar gemacht werden. Professionelle Verschlüsselungssoftwares wie zum Beispiel PGP (bis in die neueste Version 8.0) verwenden übrigens ein fast äquivalentes Verfahren.

Advanced Vigenère  

Die Lösung liegt darin, daß man den vom User eingegebenen Schlüssel mittels eines bestimmten Verfahrens in ein OTP verwandelt. Ich habe dieses Konzept Advanced Vigenère getauft. Der wahrscheinlich einfachste Algorithmus der die Ansprüche erfüllt, wäre das Erstellen eines OTP über einen Zufallsgenerator. Nun wird jeder Zufallsgenerator von einer sogenannten Seed initialisiert. Wenn die Seed verschieden ist, ist logischerweise auch das OTP ein anderes. Damit die codierte Nachricht ("Message") wieder entschlüsselt werden kann, muß die Seed des Zufallsgenerators also bekannt sein, und zwar nur demjenigen, der das ganze auch verschlüsselt hat. Es liegt also nahe, ein Paßwort ("Key") als Seed zu verwenden.

Daraus ergibt sich aber ein Problem: wenn der Key mehr als einmal verwendet wird, ist das OTP das selbe und die Message ist somit knackbar. Um das zu verhindern, muß man der Seed noch eine einmalige Komponente hinzugeben und wer einmalig sagt, sagt Zeitstempel. Ein idealer Timestamp zum Beispiel ist die Anzahl Sekunden, die seit dem 1.1.1970 ins Land geflossen sind. In der Praxis läßt sich das ganze sehr einfach realisieren: man hänge den Timestamp an den Key an und kalkuliere vom resultierenden String einen sogenannten Hash. Ein Hash ist eine Zahl, die durch das "Zerhacken" eines Strings erzeugt wird. Ein guter Hash ist quasi einmalig und irreversibel, das heißt, ein Angreifer, der nur über einen Hash verfügt, kann daraus nicht den ursprünglichen String folgern. Für moderne Zwecke wird meist ein vom NSA entwickeltes und allgemein anerkanntes System namens SHA256 (auch SHA-1 oder kurz SHA) verwendet.

Das folgende Schema veranschaulicht das Konzept:


Abbildung 1: Schema

Damit man die Message dann wieder entschlüsseln kann, wird der Cypher Message noch der Timestamp unverschlüsselt angehängt. Das birgt kein Sicherheitsrisiko, da der Timestamp ohne den Key wertlos ist (eine weitere Eigenschaft von SHA ist, daß bei der kleinsten Änderung des Strings der Hash ein gänzlich anderer ist).

Eine verschlüsselte Nachricht besteht also letztendlich aus zwei Komponenten:

CryptoHeader
Cypher block

wobei der CryptoHeader in VB folgendermaßen definiert ist:

Private Type CryptoHeader
    CheckKey    As SHA_Hash ' SHA-1 checksum
    TimeStamp   As Long     ' date of encryption
End Type

Private Type SHA_Hash
    Hash(7) As Long         ' SHA-1 hash
End Type

Beim Cypher block handelt es sich um eine Bytefolge, die zum Beispiel in einem Bytearray, aber auch in einem String abgelegt sein kann. Das Member CheckKey speichert übrigens aus Komfortgründen einen Hash des Keys, dadurch kann man beim Entschlüsseln überprüfen, ob der vom User eingegebene Key überhaupt der richtige ist. Auch das ist kein Sicherheitsrisiko, da der Hash irreversibel ist und man zum Knacken nicht den Hash des Keys, sondern den Hash des Keys plus Timestamp braucht.

Algorithmen  

Da das ganze doch recht kompliziert ist, sind im folgenden noch einmal die Algorithmen fürs Ver- und Entschlüsseln aufgelistet:

Verschlüsseln

  • Timestamp ermitteln, in CryptoHeader.TimeStamp speichern
  • SHA-Hash vom Key generieren, in CryptoHeader.CheckKey speichern
  • Timestamp an Key anhängen
  • SHA-Hash von neuem Key generieren und als Seed für den Zufallsgenerator verwenden
  • Ein Bytearray mit Zufallszahlen generieren, das die Größe des Klartexts hat
  • CryptoHeader im Zielarray speichern
  • Hinter den Header die ge-Xor'ten Bytes schreiben und Cypher zurückgeben

Entschlüsseln

  • SHA-Hash vom Key generieren
  • CryptoHeader aus Cryptotext auslesen
  • Testen, ob Hash des Keys mit Hash in CryptoHeader.CheckKey übereinstimmen
  • CryptoHeader.TimeStamp an Key anhängen
  • SHA-Hash vom neuen Key generieren und als Seed für den Zufallsgenerator verwenden
  • Ein Bytearray mit Zufallszahlen generieren, das die Größe des Cypher blocks hat
  • Alle Bytes des Cypher blocks mit dem OTP Xor'en und in zurückgeben

Fazit  

Die Sicherheit dieser Methode steht und fällt mit der Verläßlichkeit des Zufallsgenerators. Da der VB-interne Generator aus diversen Gründen sowieso ungeeignet ist, muß man sich wohl oder übel eine eigene Klasse basteln. Der Generator im Beispielsprojekt ist in dieser Hinsicht genau richtig, da er eine sehr gute Verteilung und geringe Voraussagbarkeit besitzt. Allerdings benutzt er Long-Werte zum Rechnen und weist daher eine relativ niedrige Periode von "nur" 21474836476 Werten auf, nach denen er sich wiederholt. Das heißt, ein Angreifer müßte lediglich 2147483647 verschiedene Seeds ausprobieren, um die Nachricht knacken zu können.

Diese Schwachstelle läßt sich recht einfach dadurch abdichten, daß man nicht nur einen Zufallsgenerator, sondern mehrere verwendet, die jeder mit einer eigenen Seed initialisiert und immer abwechselnd verwendet werden. Praktischerweise besteht der SHA-Hash aus acht Long-Anteilen. Die Beispielklasse verwendet also acht simultane Zufallsgeneratoren, was die Zahl der zu prüfenden Möglichkeiten ins Astronomische treibt: es blieben nunmehr 8 ^ 2147483647 Möglichkeiten zu testen. Wer Spaß dran hat, kann ja einmal versuchen, diese Zahl auszurechnen, er wird aber wahrscheinlich scheitern. Jedenfalls ist diese Zahl hinreichend groß, um eine Unknackbarkeit zu garantieren.

Beispielklasse  

Download der Beispielklasse 

Mit freundlichen Grüßen
Konrad Rudolph

Ihre Meinung  

Falls Sie Fragen zu diesem Artikel haben oder Ihre Erfahrung mit anderen Nutzern austauschen möchten, dann teilen Sie uns diese bitte in einem der unten vorhandenen Themen oder über einen neuen Beitrag mit. Hierzu können sie einfach einen Beitrag in einem zum Thema passenden Forum anlegen, welcher automatisch mit dieser Seite verknüpft wird.

Archivierte Nutzerkommentare 

Klicken Sie diesen Text an, wenn Sie die 31 archivierten Kommentare ansehen möchten.
Diese stammen noch von der Zeit, als es noch keine direkte Forenunterstützung für Fragen und Kommentare zu einzelnen Artikeln gab.
Aus Gründen der Vollständigkeit können Sie sich die ausgeblendeten Kommentare zu diesem Artikel aber gerne weiterhin ansehen.

Kommentar von Konrad L. M. Rudolph am 29.04.2005 um 13:46

Hallo,

> Meines Erachtens ist die angegebene Function Vigenere() nicht korrekt!

Doch, die Funktion ist schon korrekt. Ich erkläre mal, wieso:

> Zum Erzeugen des Austauschzeichens wird das Klartextzeichen mit dem
> Schlüsselzeichen verXORt.

Ja, das ist ja aber nicht schlimm. Ob ich nun Xor verwende oder eine Addition in einem Modulkörper (= Ring), das ist im Endeffekt das selbe (solange der Ring 2^n Elemente besitzt, was hier der Fall ist).
Der Unterschied ist, dass aufgrund der Architektur des Prozessors die Operation Xor um ein Vielfaches schneller ist als die Addition mit einem Modul.

> Da kommt doch aber ein falsches Austauschzeichen heraus!

Nein, tut es nicht. Ich verwende halt ein anderes Alphabet als Blaise de Vigenère, was ja auch logisch ist: Vigenère brauchte lediglich die üblichen Buchstaben, Satzzeichen wurden nicht berücksichtigt, selbst Zahlen brauchte man nicht, die wurden dann eben als Wort ausgeschrieben. Der *Sinn* der Botschaft kam trotzdem an, auch wenn evtl. ein minimaler Informationsverlust herrschte (eben durch Wegfall von Satzzeichen, Formatierungen etc.).
In der EDV ist das aber natürlich nicht akzeptabel, man braucht schon ein bytegleiches Ergebnis, weswegen verschiedene standardisierte Zeichensätze eingeführt wurden. VB verwendet z.B. den ANSI-Zeichensatz. Und damit Vigenère auf dem PC etwas bringt, muss es selbstverständlich *alle* Zeichen codieren können, nicht nur eine Teilmenge. Daher reicht es nicht, sich auf das Alphabet der Buchstaben zu beschränken, so wie Blaise de Vigenère das tat. Man muss schon den gesamten ANSI-Bereich mit einbeziehen.

lg,
Konrad -

Kommentar von Frank Kremer am 29.04.2005 um 10:57

Hallo,

ich beschäftige mich ein wenig mit Kryptographie und habe in dem Zusammenhang auch über die Vigenere-Verschlüsselung gelesen.

Meines Erachtens ist die angegebene Function Vigenere() nicht korrekt!
Zum Erzeugen des Austauschzeichens wird das Klartextzeichen mit dem Schlüsselzeichen verXORt.

Da kommt doch aber ein falsches Austauschzeichen heraus!

Wenn ich vom klassischen Vigenere-Quadrat ausgehe, habe ich zum Beispiel so etwas:

A B C D E
B C D E F
C D E F G
D E F G H

usw.

Angenommen, das Klartextzeichen ist "C" und das Schlüsselzeichen ist ein "B", dann ergibt sich als Austauschzeichen ein "D".

Wenn ich die Asciiwerte von "C" und "B" XORe, erhalte ich als Ergebnis aber "1" !?
Und Chr(1) ist nie und nimmer ein "D"!

Mach ich da irgendwas falsch?

Gruß aus München,
Frank

Kommentar von Konrad L. M. Rudolph am 22.02.2005 um 10:58

>> Vernam besitzt also keine Schlüssellänge im klassischen Sinne des
>> Wortes!
>
> Das stimmt, ABER: du benutzt hier weder echtes Vernam noch ein echtes
> OTP. Die Bezeichnung als solche ist irrefuehrend.

Gut. Worum es mir bei Advanced Vigenère ging, war aber im Prinzip, eine
realisierbare Annäherung an Vernam vorzustellen. Natürlich ist das ganze
idealisiert, mit einem guten Zufallsgenerator aber machbar.

> Habe mir das Zeug allerdings nochmal durchgelesen: Du hast Recht, du
> benutzt ja 8 Seeds gleichzeitig dadurch steigt die Anzahl der
> Schluesselbereich von 31 Bit auf 248 Bit. Unter diesen Umstaenden ist
> eine Bruteforceattacke (fuer Privatpersonen zumindest) nicht mehr so
> leicht durchfuehrbar.
> Nur der Richtigkeit halber: 8*2^32? Du benutzt 8 Long-Ganzahlen
> gleichzeitig - davon nur die positiven Werte. Das macht 31 Bit pro
> Wert also 248 Bit insgesamt. Somit hoechstens 2^248 verschiedene
> Moeglichkeiten die getestet werden muessen. Oder seh ich da was
> falsch?

Sorry, ich war von einer falschen Voraussetzung ausgegangen, nämlich
der, dass man als Angreifer jedes Long einzeln auf Korrektheit
überprüfen kann – was aber nicht der Fall ist. Daher hast Du recht: es
sind in der Tat 2^248 Kombinationen, die ein Angreifer testen müsste.

> Ich frage mich nur warum man noch son Zeug wie Rjindael etc erfindet
> wenn dein Prinzip doch eigentlich viel einfacher, beliebig
> erweiterbar und wirklich so sicher ist.

;-)
Nun ja, mein Verfahren steht und fällt eben mit der Sicherheit des
Zufallsgenerators. Der in meiner Beispielimplementierung verwendete ist
*nicht* kryptosicher. Ein versierter Angreifer könnte eventuell
Regelmäßigkeiten aufdecken und ausnutzen. Leider gibt es keine
effizienten Softwaremethoden, um kryptosichere Zufallsgeneratoren zu
implementieren und eine der Voraussetzungen in der AES-Ausschreibung
war, dass der Algorithmus sowohl in Hardware als auch in Software
effizient zu implementieren sein muss.
Und das amerikanische Heer verwendet, soweit ich weiß (Gerüchten
zufolge), teilweise wirklich zu Advanced Vigenère ähnliche Verfahren.

Kommentar von Kampf-Sushi am 22.02.2005 um 10:28

>>Genau das ist die Definition von einem sicheren Passwort: wenn der
Angreifer länger bräuchte, das Passwort zu knacken als den Code selbst.

Worauf ich hinaus wollte, war: ab einer gewissen Passwortlaenge bringt es keinen Sicherheitsvorteil mehr weil die Schluessellaenge (oder meinetwegen der Schluesselbereich)
Egal, ist unwichtig.

>>Vernam besitzt also keine Schlüssellänge im klassischen Sinne des Wortes!

Das stimmt, ABER: du benutzt hier weder echtes Vernam noch ein echtes OTP.
Die Bezeichnung als solche ist irrefuehrend.

Begruendung: wenn man so will ist das Passwort nur der Algo aus dem der Schluessel generiert wird.
Die 8 Seed Werte sind der eigentliche (Sitzungs-) Schluessel - hat man die Seeds, kennt man die Nachricht.
Das (Pseudo-)OTP ist quasi nur eine Streckung des Schluessels.
Es kann aber nie mehr (Pseudo-)OTPs geben als es Seeds gibt.
Demnach gibt es bei deinen "Advanced Vigenere" sehr wohl eine Schluessellaenge und zwar 248 Bit.


>>Himmel! Wer behauptet denn am laufenden Band, man könne die Schlüssellängen verschiedener Verfahren vergleichen?

Ich behaupte ja garnicht das die Schluessellaengen verschiedener Algos miteinander vergleichbar sind.
Es ging nur um den Schluesselbereich der fuer eine Bruteforce getestet werden muesste.

>>Und wie kommst Du darauf, dass es reichen würde, einen Long-Wert durchzuprobieren?

Mein Fehler.
Hab beim Ueberfliegen des Quelltextes nur einen Zufallsgenerator gesehen und bin davon ausgegangen das die Sache mit den 8 verschiedenen Zufallsgeneratoren noch nicht implentiert ist.
Ich dachte ausserdem, das du mit 'abwechselnd' unterschiedliche Verschluesselungen meinst. Also einmal mit Generator1 und bei der naechsten Nachricht Generator2 usw... das wuerde nartuerlich keinen Sinn machen.

Habe mir das Zeug allerdings nochmal durchgelesen: Du hast Recht, du benutzt ja 8 Seeds gleichzeitig dadurch steigt die Anzahl der Schluesselbereich von 31 Bit auf 248 Bit.
Unter diesen Umstaenden ist eine Bruteforceattacke (fuer Privatpersonen zumindest) nicht mehr so leicht durchfuehrbar.

>> Wir verwenden acht Zufallsgeneratoren, acht Long-Seeds
und somit 8*2^32 Werte (da steht in der Kolumne leider noch etwas falsches). Verdammt viel.

Nur der Richtigkeit halber: 8*2^32?
Du benutzt 8 Long-Ganzahlen gleichzeitig - davon nur die positiven Werte.
Das macht 31 Bit pro Wert also 248 Bit insgesammt.
Somit hoechstens 2^248 verschiedene Moeglichkeiten die getestet werden muessen.
Oder seh ich da was falsch?

Naja ist ja auch nicht so wichtig, Bruteforce ist unter diesen Umstaenden jedenfalls nicht mehr so leicht wie ich zuerst annahm.

Das Verfahren das du beschreibst ist jedenfalls eine interesannte Methode gegen Woerterbuchattacken.
Ich frage mich nur warum man noch son Zeug wie Rjindael etc erfindet wenn dein Prinzip doch eigentlich viel einfacher, beliebig erweiterbar und wirklich so sicher ist.

Kommentar von Konrad L. M. Rudolph am 14.02.2005 um 17:41

Hmm, also anscheinend kann ich echt nicht erklären. Das sollte alles
klar sein.

> 'Vollkommen Zufaellig' bedeutet doch eigentlich das es keinen
> berechenbaren Regeln folgt. Wenn der Zufallsgenerator bei identischen
> Seed (welcher den Schluessel darstellt) aber immer die gleichen
> Werte ausspuckt kann das hier nicht der Fall sein. Also kann man wohl
> kaum von einem OTP reden.

Quatsch. Vollkommen zufällig heißt lediglich, dass es sich nicht
nachvollziehen lässt. Auch ein Zufallsgenerator, der mit Seed arbeitet,
kann nicht-nachvollziehbar sein. Dann ist er kryptosicher. Natürlich ist
mein Zufallsgenerator *nicht* kryptosicher, das schrieb ich ja auch.

> Irgendwie will das nicht in meinen Kopf rein das er ein echtes
> Sicherheitsmerkmal ist wenn er mitgliefert wird. Rein theoretisch
> muesste man ihn dann doch rausrechnen koennen.

Wie kommst Du darauf? Das ganze ist eine Gleichung mit zwei Unbekannten.
Und eine Gleichung mit zwei Unbekannten ist, wie der Mathematiker weiß,
nicht eindeutig lösbar.

> Wenn DES mit seiner Schluessellaenge von 56 Bit schon lange per
> Bruteforce knackbar ist, so sollten deine 32 Bit doch eigentlich
> keine Herrausforderung darstellen, oder?

Himmel! Wer behauptet denn am laufenden Band, man könne die
Schlüssellängen verschiedener Verfahren vergleichen? Nun, noch einmal
deutlich: *man kann es nicht*!
Abgesehen davon funktioniert Vernam *ganz* anders, Vernam besitzt also
keine Schlüssellänge im klassischen Sinne des Wortes! Und *wenn* man
darauf beharrt, dass er eine besitze, dann ist es die Länge der
Nachricht (in Bits), also verdammt lang. Aber noch einmal: das kann man
nicht sagen.

> Macht es wirklich Sinn ein Passwort mit 10 Woertern zu nehmen? Der
> Angreifer wird, im Falle einer Bruteforceattacke, doch warscheinlich
> direkt den Long-Wert nehmen. Der ist wie bereits gesagt auf
> 2147483647 verschiedene Werte begrenzt.

Genau das ist die Definition von einem sicheren Passwort: wenn der
Angreifer länger bräuchte, das Passwort zu knacken als den Code selbst.
Und wie kommst Du darauf, dass es reichen würde, einen Long-Wert
durchzuprobieren? Wir verwenden acht Zufallsgeneratoren, acht Long-Seeds
und somit 8*2^32 Werte (da steht in der Kolumne leider noch etwas
falsches). Verdammt viel. Trotzdem ist das natürlich nicht kryptosicher
-- in Realweltanwendungen müsste man natürlich weit mehr Seeds verwenden.

>> Nehmen wir mal an ich schicke an Konrad eine Truhe mit meinem
>> Vorhängeschloss. Er kann sie nicht öffnen weil er den Schlüssel
>> nicht hat. Also macht er zusätzlich zu meinem sein eigenes Schloss
>> drauf und schickt mir die Kiste. Ich nehm mein schloss runter und
>> die Truhe geht zurück zu Konrad. Es ist nur noch sein Schloss dran
>> zu dem er ja den Schlüssel hat.
>
> Auf die Truhe mag das zutreffen. Wenn man das jedoch mit einer
> Xor-Verschlüsselung macht, kann man gleich in Klartext senden. Sogar
> wenn ein echtes OTP verwendet wird.

Jap, das stimmt. Zum Schlüsselaustausch ist Advanced Vigenère natürlich
*nicht* geeignet -- da ein OTP eben nur *einmal* verwendet werden darf.

Kommentar von Kampf-Sushi am 14.02.2005 um 13:16

Irgendwie habe ich Bedenken das dieser Algo wirklich sicher ist.

OTP:
'Vollkommen Zufaellig' bedeutet doch eigentlich das es keinen berechenbaren Regeln folgt. Wenn der Zufallsgenerator bei identischen Seed (welcher den Schluessel darstellt) aber immer die gleichen Werte ausspuckt kann das hier nicht der Fall sein. Also kann man wohl kaum von einem OTP reden.

Wechselnde Zufallsgeneratoren:
Wenn man die Zufallsgeneratoren wechselt, muesste man aber auch mitsenden welcher verwendet wurde. Dadurch geht der komplette Vorteil aber zunichte.
Man muss ausserdem immer davon ausgehen das der 'Feind' das Verfahren kennt, sonst koennte man ja davon ausgehen das der Angreifer alle Crypto-Moeglichkeiten durchprobieren muesste.

Timestamp:
Irgendwie will das nicht in meinen Kopf rein das er ein echtes Sicherheitsmerkmal ist wenn er mitgliefert wird. Rein theoretisch muesste man ihn dann doch rausrechnen koennen.

Schluessellaenge:
Wenn DES mit seiner Schluessellaenge von 56 Bit schon lange per Bruteforce knackbar ist, so sollten deine 32 Bit doch eigentlich keine Herrausforderung darstellen, oder?
Zumal du anscheinend nur die positive Haellfte des Long Datentypes benutzt und die Schluesselanzahl (zumindest Theoretisch, unter Umstaenden;)) durch den Hash zusaetzlich begrenzt ist.

Passwort:
Macht es wirklich Sinn ein Passwort mit 10 Woertern zu nehmen?
Der Angreifer wird, im Falle einer Bruteforceattacke, doch warscheinlich direkt den Long-Wert nehmen. Der ist wie bereits gesagt auf 2147483647 verschiedene Werte begrenzt.

Meine Kritik ist wohlbemerkt eher theoretischer Natur, ich bin schliesslich kein Kryptologe... auch wenn ich mich seit kuerzerer Zeit dafuer interessiere.

>>Nehmen wir mal an ich schicke an Konrad eine Truhe mit meinem Vorhängeschloss. Er kann sie nicht öffnen weil er den Schlüssel nicht hat. Also macht er zusätzlich zu meinem sein eigenes Schloss drauf und schickt mir die Kiste. Ich nehm mein schloss runter und die Truhe geht zurück zu Konrad. Es ist nur noch sein Schloss dran zu dem er ja den Schlüssel hat.

Auf die Truhe mag das zutreffen. Wenn man das jedoch mit einer Xor-Verschlüsselung macht, kann man gleich in Klartext senden. Sogar wenn ein echtes OTP verwendet wird.

-Übertragung1: verschlüsselt mit KeyA
-Übertragung2: verschlüsselt mit KeyA + KeyB
-Übertragung3: verschlüsselt mit KeyB

Angenommen, alle drei Übertragungen wurden abgehört:

-Aus der Differenz zwischen Übertragung1 und Übertragung2 lässt sich KeyB errechnen.
-Aus der Differenz zwischen Übertragung2 und Übertragung3 lässt sich KeyA errechnen.

Oder seh ich das grad' falsch? Müsste (bei der simplen Xor Verschlüsselung wohlbemerkt) einfach durch eine Xor-Verknüpfung der entsprechenden Nachrichten gehen.

Bei anderen Verschlüsselungsalgos waehre das eventuell etwas schwerer zu bewerkstelligen, ist aber nicht auszuschliessen das dies dort ebenfalls moeglich ist.

Kommentar von Konrad L. M. Rudolph am 12.09.2004 um 15:33

Zeus, in der Kolumne wird erläutert, warum der Schlüssel mit verschlüsselt wird. Das hat nichts damit zu tun, dass es "nötig" ist -- nur, dass es Komfort bietet.
Ich habe den Eindruck, Du verwechselst diese Kolumne mit der über Schlüsselaustausch.

lg,
Konrad -

Kommentar von Zeus557 am 12.09.2004 um 15:25

Es ist doch eigentlich nicht nötig den Schlüssel zu übertragen.

Nehmen wir mal an ich schicke an Konrad eine Truhe mit meinem Vorhängeschloss. Er kann sie nicht öffnen weil er den Schlüssel nicht hat. Also macht er zusätzlich zu meinem sein eigenes Schloss drauf und schickt mir die Kiste. Ich nehm mein schloss runter und die Truhe geht zurück zu Konrad. Es ist nur noch sein Schloss dran zu dem er ja den Schlüssel hat.

Hab aber noch n kleines prob mit der Verschlüsselung:

und zwar wenn als Ergebnis vom xor 0 rauskommt.
chr(0) = "" also geht der Buchstabe verloren und wegen meinem Algo stimmen dann auch die nachfolgenden nicht mehr.

Kennt jemand eine Lösung ?

Kommentar von Claus von der Burchard am 07.07.2004 um 11:51

Wie wäre es, wenn Du das Beispielprojekt benutzt ???
Da wird doch gezeigt, wie das geht!

Gruß,
Claus

Kommentar von Axel Wagner am 07.07.2004 um 11:31

Ööhm... wenn ich euch hier so reden höre, fühle ich mich ehrlich gesagt wie ein Neandertaler... ^^
Ich hab mir mal die Klassen etc. runtergeladen, aber irgendetwas mache ich wohl falsch, so sehr ich mich auch anstrenge, ich KANN einfach nichts damit verschlüsseln.... vom entschlüsseln mal ganz zu schweigen... ^^
Kann mir vielleicht irgendwer einen einfach Code posten, für eine De- und eine encrypt-Funktion? ^^

Kommentar von Claus von der Burchard am 04.01.2004 um 17:53

>> solange Du Message und Schlüssel schickst, kann und wird
das System nicht sicher sein

Absolute Sicherheit kann nur Vigenère bieten, oder eher gesagt ist das die einzig bekannte Methode. Das Problem ist es, einen Kompromiss zu finden zwischen absoluter Sicherheit, die praktisch gesehen unmöglich ist wegen zu großer Komplexität, und der praktischen Lösung, die keine Sicherheit bietet.

Das Advanced Vigenère Verfahren ist IMHO ein sehr guter Kompromiss. Es wird ja nicht der gesamte Schlüssel übergeben, sondern nur ein Ausschnitt. Es liegt am Benutzer, verhältnismäßig sichere Schlüssel zu nehmen, bsp. ein Satz mit 10 Wörtern.

Praktisch an diesem System ist, dass außer dem Passwort nichts übermittelt werden muss. Wenn Du die Möglichkeit hast, ein vollständiges OTP zu übertragen, ist das schön. Diese Möglichkeit ist aber meistens nicht gegeben!

Mfg
Claus von der Burchard

Kommentar von LotharK am 03.01.2004 um 19:02

Hallo Konrad,
solange Du Message und Schlüssel schickst, kann und wird das System nicht sicher sein. Wie ich bei den Freaks von GNuPP erfahren habe - die es sich zum Sport machen, Systeme zu knacken - schließen die schon mehrere 100 Rechner zusammen um solche Code zu hacken. Im Zeitalter der Rechentechnik ist es doch bei wachsender PC-Geschwindigkeit nur eine Frage der Zeit -oder? Einen total interessanten Artikel habe ich hier gefunden. Ich wollte nach dieser genauen Anleitung schon mal so ein System selbst in VB schreiben, habe es dann aber aufgegeben. Für jemanden der Lust hat, sicher kein Problem.

http://www.gnupp.de/


MfG LotharK

Kommentar von Konrad Rudolph am 26.09.2003 um 22:01

@Claus:

ja, da hast du allerdings recht. Z.B. war der "Heiße Draht" zwischen Washington und Moskau wahrscheinlich (nur "wahrscheinlich", da diese Information klassifiziert und nicht offiziell bestätigt ist) per OTP. Auch große Firmen (die es sich leisten können) verwenden das Verfahren, da werden dann sogenannte Schlüsselkuriere losgeschickt, die die OTPs verteilen, was natürlich recht teuer ist.
Auch gibt es seit einiger Zeit quantenkryptographische Geräte zu erwerben (für Unsummen), die OTPs austauschen.

Wenn ich also sage "hat sich nicht durchgesetzte", dann meine ich zwei Sachen:

1) Nach der Erfindung von Vigenère hat es an die 400 (vierhundert!) Jahre gedauert, bis das Verfahren praktisch zum ersten Mal zum Einsatz kam.
2) trotz der Existenz von Vigenère wurden in letzter Zeit immer kompliziertere Methoden der Kryptographie entwickelt (Blowfish, etc.).

Kommentar von Claus vdb am 26.09.2003 um 21:13

Hi!

Erstmal muss ich sagen, dass dieses Verfahren echt sehr gut und zuverlässig funktioniert; ich benutze es fast nur noch für Verschlüsselung.

Wo ich heute den Artikel nochmal lese, fällt mir auf, dass es nicht stimmt, dass sich Vigenère nie durchgesetzt hat. In allen Geheimdiensten der Welt spielte oder spielt das OTP-Verfahren eine Rolle. Die Sowjetunion benutzte bis zu ihrem Untergang die sog. "Einmalblocks", und auch die USA benutzen auch heute noch trotz 256-Bit Verschlüsselung usw. (ich will hier jetzt nicht in die technischen Details vom STU eingehen...) für besonders wichtige Nachrichten OTP. Vor allem im kalten Krieg, wenn mal wieder angeblich ihr Nachrichtensystem geknackt wurde.

Fiel mir nur so grade ein, vielleicht interessiert es jemanden. Irgendwer hatte natürlich auch mal die glorreiche Idee, das ganze auf den Computer umzusetzen (Einmaldisketten), und so wird Vigenère wohl zumindest noch sehr lange eine Rolle spielen.

Mfg
Claus

Kommentar von devnull am 16.05.2003 um 00:20

Ohne klugscheißen zu wollen ... die Wahrscheinlichkeit ist ja gerade der Knackpunkt.

Nimm die Bibel, verschlüssele sie mit einem echten OTP. Wenn jemand mit Brute Force versuchen würde, das zu knacken, würde er dabei nacheinander ALLE bekannten und noch unbekannten gleichlangen Schundromane lesen dürfen. Alles durchaus sinnvolle UND plausible Texte. Alles klar?

Kommentar von Leif am 15.05.2003 um 20:13

Ok, aber wie hoch schätzt ihr die Wahrscheinlichkeit ein, dass ein "plausibler" (O-Ton Konrad) oder "sinnvoller" (O-Ton devnull) Text herauskommt? Das müsste zuallerst einmal bedeuten, dass alle sich ergebenden Bytes lesbare Zeichen sind. Von den Wörtern ganz zu schweigen.
Außerdem bezweifle ich nicht die Sicherheit deines Verfahrens, ich finde es sogar genial.

Kommentar von Konrad Rudolph am 15.05.2003 um 19:05

@Leif (und devnull?):

aah, ich habe soeben erst kapiert, was du meinst...
allerdings stimt auch das nicht, denn das Paßwort wird ja garnicht verwendet, um das OTP zu bilden... und um zu testen, welches das richtige OTP ist, muß man das Plaintext-Paßwort kennen, nicht den Hash davon...

das heißt: wenn ich das Paßwort direkt verwendet hätte, um das OTP zu erstellen, dann könnte man in der Tat alle in Frage kommenden OTPs ausprobieren (was sowieso abwegig ist, es gibt einfach weitaus zuviele!) und dann jedesmal das Keyword errechnen, hashen, und mit dem Hash im Header vergleichen. So könnte man in der Tat unter allen falschen Nachrichten die richtige erhalten.

Aber das geht nicht, denn selbst wenn man das OTP hätte, ließe sich daraus nicht das Keyword zurückverfolgen, nur der Hash... und das ist ein _anderer_ als der im Header, denn im Header ist ja der Zeitstempel nicht mitverrechnet! Also wüßte man nicht, ob man das richtige OTP hat oder nur eine andere plausible Lösung. Finde dich mit ab: so klappt's nicht.

naa, noch jemand anders eine Idee, wie mein Verfahren zu knacken wäre? *g*

Kommentar von devnull am 15.05.2003 um 14:04

@Leif:
Damit wir uns nicht missverstehen :-)
Es ist völlig klar, dass sich durch den Hash der sinnvolle Text "relativ" leicht ermitteln lässt. Mir ging es um den grundsätzlichen Aspekt des OTP. Dies ist ohne Hash NIEMALS zu entschlüsseln. Man erhält zwar unter anderem den richtigen Text aber auch ALLE ANDEREN sinnvollen Texte der gleichen Länge. Und das können viele sein *g*

Kommentar von Leif am 15.05.2003 um 13:51

Ich lege es nicht speziell darauf an, dir deine Illusionen zu nehmen, aber...

Zitat: "Du kannst ihn aber niemals von allen anderen gleich langen sinnvollen Klartexten unterscheiden. Das heißt, Du weißt bei einer Länge von 6 Zeichen nicht, ob das Wort "LIEBEN" oder "HASSEN" heißt. Beides ist absolut gleich wahrscheinlich und evtl. gleich sinnvoll."

Wenn irgendein falscher Key dazu führt, dass irgendwo ein Wort in ein anderes gültiges geändert wird, so ist der restliche Text trotzdem noch unlesbar, es wird schließlich binär verschlüsselt.

Allerdings kann man jeden beliebigen Text durch ein passendes OTP in einen beliebigen anderen umwandeln. Es ist nur praktisch (höchstwahrscheinlich auch prinzipiell auf Grund der Länge des Hashes, die nur !begrenzt! viele Seeds zulässt) unmöglich, einen Key zu finden, der ein solches OTP generiert. Also ein OTP bei dem zufällig alle falsch dekodierten Bytes auch Textzeichen sind UND Worte ergeben. Ich persönlich halte es für prinzipiell unmöglich, da es eben nur begrenzt viele Hashes gibt.

Kommentar von devnull am 15.05.2003 um 09:49

@Leif:
Ja, da gebe ich Dir recht. In dem hier geschilderten Verfahren inkl. Hash hat sich eine zusätzliche Unsicherheit eingeschlichen.

Kommentar von Leif am 14.05.2003 um 13:59

@devnull:
Nachdem man ein Kennwort generiert hat, muss man nur den Hash davon bilden und mit dem Hash vergleichen, der im Crypto-Header gespeichert ist. Dann weiß man mit ziemlicher Sicherheit, dass der Key richtig ist. Es gibt zwar auch andere Keys mit dem selben Hash, aber diese werden höchstwahrscheinlich nicht mal aus lesbaren Zeichen bestehen.

Kommentar von ErAzEr am 13.05.2003 um 12:40

Super Beitrag!

Kommentar von Konrad Rudolph am 07.05.2003 um 18:14

@Devnull:
klasse erkannt ;-)
Darauf beruht ja die Stärke von Xor. Daß man es nicht knacken kann, heißt einfach, daß man nicht entscheiden kann, welcher Inhalt richtig und welcher falsch ist.

(PS: komm auch mal wieder ins Forum... wir sehnen uns nach dir ;-)

Kommentar von devnull am 07.05.2003 um 13:40

Im ersten Abschnitt schreibst Du, dass diese Methode durch kein bekanntes Verfahren der Kryptoanalyse brechbar sei, "außer natürlich durch eine Brute-Force-Attacke auf das Kennwort". Da muss ich Dir vehement widersprechen. Natürlich findest Du unter anderem den korrekten Klartext, Du kannst ihn aber niemals von allen anderen gleich langen sinnvollen Klartexten unterscheiden. Das heißt, Du weißt bei einer Länge von 6 Zeichen nicht, ob das Wort "LIEBEN" oder "HASSEN" heißt. Beides ist absolut gleich wahrscheinlich und evtl. gleich sinnvoll.

Kommentar von Konrad Rudolph am 04.05.2003 um 19:36

Sorry, was meinst du mit der "'normalen' Xor Abfrage"???

Also, ich habe die Klasse mal mit dem Text "Hallo" und dem Key "a" ausprobiert und es klappt hervorragend:

Dim CryptoInstance As New CCrypto
Dim a As String
Dim b As String
a = "Hallo"
CryptoInstance.CreateSession
CryptoInstance.Key = "a"
CryptoInstance.EncodeString a, b
MsgBox b
CryptoInstance.CloseSession
CryptoInstance.CreateSession
CryptoInstance.Key = "a"
CryptoInstance.DecodeString b, a
MsgBox a
CryptoInstance.CloseSession

Kommentar von Tester am 04.05.2003 um 18:05

Probiert mal die "normale" Xor Abfrage dieser Kolumne mit dem Text "Hallo" und dem Passwort "a" dann funktioniert sie namlich nicht!

Kommentar von Konrad Rudolph am 02.05.2003 um 12:04

@Pille:
dann hast du das Verfahren von SHA anscheinend nicht ganz verstanden. SHA256 ist genau deswegen so sicher, weil selbst bei fast gleichen Messages der Message Digest ein vollkommen anderer ist.
Das heißt, selbst wenn du das selbe Dokument zweimal mit dem selben Key verschlüsselst und nur der Timestamp unterschiedlich ist, bekommst du den Key nicht raus.

Zwar könntest du in diesem Fall (wenn du _weißt_, daß die beiden Dokumente die selben sind) das OTP herausbekommen, das ist aber auch schon alles.
Wenn bei zwei Dokumenten nur ein bestimmter Teil übereinstimmt (z.B. der Doc-Header), dann kann man auch nur diesen Teil des OTP herausbekommen.

Nun ergibt sich hier tatsächlich ein Problem, denn der Zufallsgenerator basiert auf einem linearen Verfahren, dessen Seed sich schon durch relativ (!!!) wenige Werte ermitteln läßt.
Dadurch, daß aber acht simultane Generatoren verwendet werden, ist dieses Risiko praktisch ausgeschlossen.
Und selbst wenn jemand diese Seed ermitteln sollte könnte er zwar die entsprechende Nachricht entschlüsseln, würde aber immer noch nicht den Schlüssel gefunden haben.
Das heißt: selbst mit einer entschlüsselten Nachricht sind alle anderen immer noch sicher.

Kommentar von Pille am 02.05.2003 um 11:38

Problem: für einen ähnlichen Text (z.B. nur Ähnlichheit des Dokumenten Headers einer .doc Datei) wird der selbe Key verwendet - Timestamp wird mitgeliefert - wo ist das schwer zu knacken?
Es ist theoretisch recht sicher - aber sobald ein Key 2x verwendet wird ist es dies nicht mehr. (Es gibt dazu eine recht interessante Geschichte: von russischen Spionen im 2. WK in Amerika die eine ähnliche Methode verwendeten - nur irgendwann benutzten sie die (Schlüssel) OTPs doppelt). Ich glaube nicht dass das Verfahren durch Vignere Sicherer gemacht wird - es basiert auf SHA, mit diesem steigt und fällt die Sicherheit. (Der Timestamp, Zufallsgenerator, das OTP und der Vignere sind letztendlich egal. Die Periodendauer wird nicht durch den Zufallgenerator bestimmt sondern durch den mit SHA verschlüsselten Key - und dort liegt das Problem) - ich denke, dass das Verfahren interessant ist - kann mir aber nicht vorstellen, dass ein User für jedes verschlüsselte Dokument ein neues Kennwort wählen will und würde so eher zu RC4 oder Ähnlichen Verfahren raten...

Grüsse

Kommentar von Konrad Rudolph am 30.04.2003 um 18:38

an Florian:

Dieses Risiko wird außer Acht gelassen. Es ist generell üblich, einen Hash des Kennworts mitzuliefern, auch PGP macht das, scheinbar ohne sich Sorgen um die Sicherheit des Kennworts zu machen.
Natürlich, ein Brute-Force (Dictionary Attack) ist hierdurch eventuell erleichtert, allerdings nicht, wenn man sich an gewisse Regeln der Kennworterzeugung hält. So hat z.B. jede Sprache einen Faktor, der angibt, wie lang Kennsätze in "normaler" Sprache sein müssen, um als unknackbar zu gelten.
Mit Satzzeichen und alternierter Groß-kleinschreibung reicht im Deutschen ein Satz á 40 Zeichen vollauf, um eine Unknackbarkeit zu garantieren. Da stellt auch der Hash kein zusätzliches Risiko dar.

Wem das nicht genug ist, der kann natürlich in der praktischen Anwendung den Header dementsprechend modifizieren.

Kommentar von Florian Rittmeier am 30.04.2003 um 17:57

Ist es nicht doch ein Risiko für die Sicherheit, dass ein Hash des Passwortes gespeichert wird?

Zwar lässt sich aus dem Hash das Passwort nicht direkt errechnen, aber für einen Brute-Force-Angreifer ist es doch wesentlich einfacher, von allen Passworten einen Hash zu errechnen und diesen dann mit dem mitgelieferten Hash zu vergleichen.

Wenn dieser Hash nicht gegeben ist, muss er zur Überprüfung erst noch auf den Zufallszahlengenerator warten und schließlich die komplette Nachricht dekodieren und dann überprüfen, ob er erfolgt hatte. Und dies kann er dann auch nur ehr schwer automatisch tun.

MfG Florian

Kommentar von Konrad Rudolph am 30.04.2003 um 12:14

Fehler in Crypto-Routine

Anscheinend macht die Crypto-Routine in Verbindung mit .NET Streß: ich habe das Projekt als ActiveX-Dll kompiliert in VB.NET eingesetzt. Die Daten, die dabei rauskamen, waren Schrott. Diesen Fehler habe ich allerdings bisher nur unter .NET, nicht unter VB Classic bemerkt. Hier funktioniert die Klasse einwandfrei. Warum das so ist, ist mir leider nicht bekannt.