Neue (?) Verschlüsselung.... Wie sicher ist sie?

[glkgereon]

Hi,

Nach der Lektüre von "Digital Fortress" (Diabolus) Habe ich mich längere Zeit gefragt, was mit einer "rotating cleartext function" gemeint sein könnte (sofern sie existiert). (Ob Dan Brown selbst eine Idee hat wie soetwas gehen könnte?)
Nach einiger Überlegung stieß ich auf eine (mir völlig neue) Idee der Verschlüsselung.
Hierbei generiere ich zunächst eine (peudo-)zufällige Index-Datei zu einer Wortliste.
Dann ersetze ich nach dem in der Index-Datei angegebenen Schema alle Wörter im Ausgangstext (und beim dekodieren wieder zurück).
"Passphrase" ist bisher lediglich die Index-Datei sowie die Wortliste. Ob es sich lohnt (und wie es gehen würde) einen zusätzlichen Passphrase im üblichen Sinne einzubauen, weiss ich (noch?) nicht.

Naja, genug der Theorie, hier etwas Code:

Delphi-Quellcode:

  TForwarding = packed record
    x: Int64;
    y: Int64;
  end;
  TForwardings = array of TForwarding;
  THeader = packed record
    FileSize: Int64;
    Datas: Int64;
  end;
  TEntry = record
    PointSucc: Boolean;
    PointPrec: Boolean;
    Succ: Int64;
    Prec: Int64;
    Index: Int64;
  end;
  TEntries = array of TEntry;

TForwardings ist der eigentliche Inhalt der Index-Datei. Der Index im Array entspricht dem Index in der Wortliste, X ist der Vorgänger und Y der Nachfolger.
TEntries ist ein Array zum Internen Generieren der Forwardings.
THeader wird vorne in die Datei geschrieben. Hat zwar noch keine wichtige Funktion, aber es ist ganz praktisch im vornherein zu wissen wie viele Forwardings man denn nu hat^^

Die Wortliste verwalte ich ganz einfach in einer TStringList.

Das ganze habe ich in eine Klasse geknallt...
CallPrg, CallInitPrg und CallStatus sind Events der Klasse um den Fortschritt und Status-Texte auszugeben...

Nun zum Generieren des Indexes:

Delphi-Quellcode:

procedure TWordEncryption.GenerateIndex;
var FS: TFileStream;
    Head: THeader;
    FW: TForwarding;
    i: Integer;
    E: TEntries;
    S: Int64;
begin
  CallPrg(0,aGenerate);
  CallInitPrg((WL.Count-1) div 1000,aGenerate);

  CallStatus('Übertrage Wortliste...',aGenerate);
  SetLength(E,WL.Count);
  for i:=0 to WL.Count-1 do
    begin //Erstmal alles reinkopieren
    E[i].PointSucc:=False;
    E[i].PointPrec:=False;
    E[i].Index:=i;
    E[i].Succ:=0;
    E[i].Prec:=0;
    end; 
  CallStatus('Generiere Index-Datei...',aGenerate);
  for i:=0 to Length(E)-1 do
    begin //Nochmal alles durchlaufen
    if (i mod 1000 = 0) then
      begin
      CallPrg(i,aGenerate);
      end;
    S:=Random(Length(E)); //Und zufällig ein Element suchen was noch keinen Vorgänger hat.
    while (E[S].PointPrec) do S:=Random(Length(E));
    E[i].PointSucc:=True; //Wenn man dann eins hat die "Zeiger" (=Indexe) richtig setzen
    E[S].PointPrec:=True; //Und die Status-Bools setzen
    E[S].Prec:=E[i].Index;
    E[i].Succ:=E[S].Index;
    end;

  FS:=TFileStream.Create(FIndexFile,fmShareExclusive or fmOpenWrite);
  Head.FileSize:=Length(WL.Text); //Dann bastlen wir uns noch schnell nen Header
  Head.Datas:=WL.Count;
  FS.Size:=0;
  FS.Position:=0;
  FS.Write(Head,SizeOf(THeader));

  CallStatus('Speichere Index-Datei...',aGenerate);

  for i:=0 to Length(E)-1 do
    begin //...und schreiben alles in die Datei
    FW.x:=E[i].Prec;
    FW.y:=E[i].Succ;
    FS.Write(FW,SizeOf(TForwarding));
    end;

  FS.Free;

  CallStatus('Bereit.',aGenerate);
  CallPrg(0,aGenerate); //Fertig
end;

Nun hat man eine Index-Datei...Soweit so gut.

Nun kommt es zum Kodieren bzw zum Dekodieren.

Delphi-Quellcode:

  TStringDynArray = array of String;
  TCodeDirection = (cdEncode,cdDecode);


function TWordEncryption.CodeIt(Src, Passphrase: String; T: TCodeDirection): String;
/* 
  Src wird (De-)Kodiert
  Passphrase ist zZ noch ohne Funktion
  T ist die Richtung (cdEncode oder cdDecode)
*/
var i,j,k: Integer;
    F: TForwardings;
    Head: THeader;
    FS: TFileStream;
    D: TStringDynArray;
begin
  CallPrg(0,aCode);
  Result:='';
  CallStatus('Lade Index-Datei...',aCode);
  FS:=TFileStream.Create(FIndexFile,fmShareExclusive or fmOpenRead);
  FS.Read(Head,SizeOf(THeader)); //Erstmal wieder auspacken
  SetLength(F,Head.Datas);
  for i:=0 to Head.Datas-1 do
    FS.Read(F[i],SizeOf(TForwarding));
  FS.Free; //Nu ist alles in F drin

  CallStatus('Kodiere Text...',aCode);
  D:=Explode(' ',Src); //In die Einzel-Wörter Splitten
  for i:=0 to Length(D)-1 do
    begin
    CallPrg(i,aCode);
    j:=WL.IndexOf(D[i]); //Den Index des Wortes holen
    if (j<0) or (j>=WL.Count) then
      Result:=Result+D[i]+' ' //Wenn Wort nicht in der Wortliste ist, dann schreiben wirs einfach wieder so rein
    else if T=cdEncode then
      begin //Kodieren
      for k:=1 to i do
        j:=F[j].y; //Wir nehmen und ein i-mal den Nachfolger
      Result:=Result+WL[F[j].y]+' ';
      end
    else if T=cdDecode then
      begin //Dekodieren
      for k:=1 to i do
        j:=F[j].x; //Wir nehmen und ein i-mal den Vorgänger
      Result:=Result+WL[F[j].x]+' '; 
      end;
    end;
  CallPrg(0,aCode); //Fertig.
  CallStatus('Bereit.',aCode);
end

Ja und das war es eigentlich auch schon :-)

Nun meine Frage:
Wie sicher ist so eine "Verschlüsselung"?
Durch herkömmliche Brute-Force Attacken ist sie ja nun kaum zu verwunden, da sie beim richtigen Text keine signifikanten unterschiede zu einer falschen version aufweist. (Es ist immer, mehr oder weniger, sinnvoller Text. Daher bräuchte es wirklich eine Brute-Force welche auf Satzzusammenhang prüft....).

Ich hänge mal
a) die Unit + Beispielprogramm und
b) eine Wortliste an

damit habe ich einen Text verschlüsselt.
Dier Kodierte Fassung ist:
"Fadensonde Disziplinargericht Duschnik Puppenwagen . zugemacht Schaufensterwettbewerb Schriftart umsatzlos !"

kann es wer entschlüsseln?

[Ratte]

a) deine Schlüsseldatei ist relativ groß
b) muss sie auf den Text angepasst sein --> wenn bestimmte Worte beim erstellen des Schlüssels nicht vorgesehen waren, hast du pech gehabt.
c) funktioniert nur bei Texten
d) insbesondere wenn man mehrere Nachrichten hat ann man mit Satzbau evt. einiges erschließen.
e) Wörter mit Satzzeichen dahinter werden nicht verschlüsselt (Satzzeichen sind allgemein ein Risiko bei deinem Verfahren, erlauben Rückschlüsse auf den Satzbau)
f) Die Tatsache dass du Wörter aus der Wortliste mit Wörtern aus der Wortliste verschlüsselst, lässt Rückschlüsse auf die Wortliste zu --> Angreifpunkt
Nette Spielerei. Zur Sicherheit kann ich nicht viel sagen, dürfte aber mit vertretbarem Aufwand zu knacken sein. Allgemein sind mir AES, RSA und Konsorten sympathischer.
mfg,

Ratte

P.S. mal sehen was Cryptomeister negaH dazu sagt, ich hoffe ich hab nix elemtares bei meiner Kurzanalyse übersehen.

[glkgereon]

In der Tat, die Satzzeichen sind (bisher) echt ein Manko...
Allerdings könnte man vielleicht die kodierung der Satzzeichen mit einer Kodierung von Zahlen koppeln (aber da hab ich bisher noch kein brauchbares Ergebnis...)

Die Große Schlüsseldatei ist imho kein Sooo großes Problem, da sie zum einen (wenn man das mal auf Integer reduziert, was völlig ausreicht) nur noch halb so groß ist und sich ziemlich komprimieren lassen sollte (hoffe ich zumindest).

In der Tat funktioniert das ganze nur bei Texten. Das ist klar.

Mit dem Erschließen nach dem Satzbau ist so eine sache...
Angenommen du hast eine Wortliste mit mehreren hunderttausend wörtern, wie meine sie hat.
Dann geht das Index erstellen sowie ver und entschlüsseln noch sehr schnell.
Gleichzeitig ist die möglichkeit der kombinationen aber schon SO groß, das ein prüfen per hand völlig sinnlos ist.
also würde es eventuell reichen, Wörter durch gleichartige (nomen durch nomen, verben durch verben zB) zu ersetzen, und damit einen korrekte Grammatik zu erhalten.
In wie weit diese erstzungen die stärke der verschlüsselung beeinflussen weiss ich nicht...

[Meflin]

Zitat:

Zitat von glkgereon

Nach der Lektüre von "Digital Fortress" (Diabolus) Habe ich mich längere Zeit gefragt, was mit einer "rotating cleartext function" gemeint sein könnte (sofern sie existiert).

Manche Leute merkens leider wirklich nicht, aber Dan Brown schreibt nicht wissenschaftlich korrekt. (Das artet dann manchmal in derart sinnlosen Diskussionen aus dass es nicht fierlich ist.) Löblicherweise bezweifelst du immerhin deren Existenz ;)

Rotating Irgendwasauchimmer fällt definitiv unter die künstlerische Freiheit, die ein Romanautor eben hat, aber so etwas gibt es definitiv nicht! Ich erinnere mich nicht mehr genau wie er es meint dass es funktionieren soll, aber ich meine mich zu erinnern dass das nichtmal theoretisch funktionieren würde :mrgreen:

[glkgereon]

Zitat:

Zitat von Meflin

Zitat:

Zitat von glkgereon

Nach der Lektüre von "Digital Fortress" (Diabolus) Habe ich mich längere Zeit gefragt, was mit einer "rotating cleartext function" gemeint sein könnte (sofern sie existiert).

Manche Leute merkens leider wirklich nicht, aber Dan Brown schreibt nicht wissenschaftlich korrekt. (Das artet dann manchmal in derart sinnlosen Diskussionen aus dass es nicht fierlich ist.) Löblicherweise bezweifelst du immerhin deren Existenz ;)

Rotating Irgendwasauchimmer fällt definitiv unter die künstlerische Freiheit, die ein Romanautor eben hat, aber so etwas gibt es definitiv nicht! Ich erinnere mich nicht mehr genau wie er es meint dass es funktionieren soll, aber ich meine mich zu erinnern dass das nichtmal theoretisch funktionieren würde :mrgreen:

Ich sagte ja, ich habe mich auch gefragt was er damit meint^^
Und so wie ich es verstanden hab heisst das nur das am ende wieder (theoretisch) lesbarer Text rauskommt...was ja geht :-)
Aber dass das was er da schreibt nicht 100%ig korrekt ist ist klar^^

[Dax]

Ich hab mir deinen Code nicht sooo genau angekuckt (;)), aber der Erklärung nach ist das nicht weiter als ein Substitutionsalgorithmus. Du ersetzt einfach ein Wort durch ein anderes. Das ist wie Cäsar-Verschlüsselung, nur statt pro Buchstabe findet die Ersetzung pro Wort statt. Es ist um einiges schwieriger, dieses Ding zu knacken, aber mit genügend Ausgangsdaten wird das ohne Zweifel viel einfacher. Von AES und Konsorten kann man das (finde ich) nicht behaupten.

[negaH]

Keine Ahnung was Dan Brown damit gemeint hat aber wir können mal einen Vergleich der Komplexität (und darum gehts bei der Kryptographie immer!) zwischen deinem Verfahren und einem anerkannten Verfahren wie AES machen.


AES arbeitet mit 128 Bit Schlüsseln und ist ein 128 Bit Blockcipher. Interessant für uns sind die 128 Bit Blockgröße. Das bedeutet das es exakt 2^128 verschiedene Datenblöcke als Inputs geben kann die dann auf exakt 2^128 andere Output Blöcke transformiert werden. Ohne den Passwordstream ist diese Transformation nicht umkehrbar.

Angenommen du benutzt eine Indexdatei die 4 Gb groß ist. Pro Index verbrauchen wir 4 Bytes macht also 1 Milliarde unterschiedlicher Transpositionen beim Mapping von einem Wort zu einem anderen Wort. Wir können also mit max. 1 Million unterschiedlicher Worten arbeiten. Das dürfte damit ca. 4 mal mehr sein als es zb. deutsche Worte gibt (ca. 250000).

Im vergleich heist dies

AES 2^128 mögliche Transpositionen
Dein Verfahren ca. 250.000 mögliche Transpositionen.

Die Komplexität eines guten Verfahrens (nur einfach berechnet OHNE dabei auch die Art&Weise der mathematischen Operation dieser Transpositon zu berücksichtigen !!) ist demnach x := 2^128 / 250.000 mal größer und X als Zahl ausgeschrieben ist

2^128 = 340282366920938463463374607431768211456
250000 ~ 2^19

2^128 / 250000 = 1361129467683753853853498429727072

x := 1361129467683753853853498429727072

Also 1361129467683753853853498429727072 mal ist ein normaler Cipher heute stärker als deine Methode.


Nimmt man also deine Textdatei die verschlüselt werden soll, so kannst du mit deinem Verfahren nur soviele Wörter umkodieren wie es in unserem Sprachschatz tatsächlich gibt. Würde man die gleiche Datei mit AES verschlüsseln so würde es zu jedem möglichen deutschen Wort ca. 1361129467683753853853498429727072 verschiedene Kombinationen geben, statt nur eine 1 zu 1 Transposition.
Damit ist der Symbol-Raum der binären Verschlüsseung mit AES nicht nur weit weit stärker sondern hat noch den Vorteil das es zu keinerlei Veränderung der Dateigröße gibt. In deinem Falle könnte ja ein Wort wie UND in ein Wort wie HAUSFRAU gemappt weden, ergo eine Änderung in der Datengröße. Das gibts bei AES nicht, trotz weit besserer Komplexität, und dies ist ein großer technischer Vorteil vom AES im praktischen Betrieb.

[edit]
Soweit zur Komplexität und meiner Kritik an deinem Verfahren. Nun noch einige Verbersserungsvorschläge die dein Verfahren mehr Sinn verleihen.

Also deine Index-Datei bleibt erhalten und mappt ein Wort zu einem Index der zb. 24 Bit pro Eintrag groß ist. Das wären also 3 Bytes pro Wort. Nun hats du noch eine Wortdatenbank, natürlich effizient sortiert und durchsuchbar. Beim Verschlüsseln wird deine Testdatei geladen und Wortweise zerlegt. Jedes Wort wird in deiner Wortdatenbank gesucht und dessen Index als Zahl ermittelt. Dieser Index dient als Index zum Zugriff auf deine Indexdatei, eher eine SBox-Datei. Du nimmst nun den darin hinterlegten 24 Bit Zahlenwert und speicherst diesen in unsere verschlüsselte Output-datei.

Du hast also eine Textdatei so umkodiert das sie pro Wort nur 3 Bytes benötigt im Output. Du müsstest damit also eine Komprimierung erhalten. Defakto kannst du je nach Wahrscheinlichkeiten der Worte im Text die Größe der Kodierungsbytes dynamisch anpassen, so wie bei der Huffman Komprimierung. Sehr häufige Wörter werden also mit kurzen Codes kodiert und seltene Wörter mit langen Codes. Damit bekommst du eine Komprimierungsrate hin die höher ist als jede ZIP Komprimierung und denoch keine verlustbehaftete Komprimierung ist.

So, fehlt noch unser Passwort. Ohne Passwort funktioniert das Verfahreen wie eben beschrieben, es mappt nur die Wörter in IDs basierend auf unsere Index-Datei. Mit Passwort würde der Index unseres Wortes in der Wortdatenbank erstmal mit einem Passwortstream umkodiert und dann erst als Index in unsere ID-Index-Datei benutzt. Oder besser noch wird man nachdem man unsere ID zum Wort ermittelt wurde diese ID mit dem Passwortstrom umkodiert. Dh. selbst mit bekannter Wortdatenbank und ID-Index-Datei benötigt man noch das Passwort um die verschl. Datei zu entschlüsseln und zu dekomprimieren.

[/edit]

Gruß Hagen

[glkgereon]

Zitat:

Zitat von negaH

Pro Index verbrauchen wir 4 Bytes macht also 1 Milliarde unterschiedlicher Transpositionen beim Mapping von einem Wort zu einem anderen Wort. Wir können also mit max. 1 Million unterschiedlicher Worten arbeiten.

Den teil versteh ich irgendwie nicht so ganz :gruebel:

wieso dividierst du da auf einmal durch 1000?
zudem ist die substitution ja auch noch von der position im Text abhängig (ergo eigentlich noch mal länge des textes... oder?)

[negaH]

Die Länge des Textes ist erstmal irrelevant. Wir analysieren einfach nur die Komplexität beim Mappen eines Wortes in einen anderen Code. Dieser Prozess ist vergleichbar mit dem Mappen eines Datenblockes zu einem anderen Datenblock bei einer Blockverschlüsselung. Wenn wird davon ausgehen das es nur 250000 deutsche Wörter gibt so ist die Komplexität dieser Operation exakt 250000 zu 250000 andere Wörter. Bei AES sind es 340282366920938463463374607431768211456 zu 340282366920938463463374607431768211456 anderen Datenblöcken.

Klar, wir müssten theoretisch sogar noch berücksichtigen das ein Datenblock bei AES ja aus 16 Bytes besteht und ein durchschnittliches deutsches Wort wohl weniger als 128 * 3.6/8 = 58 Zeichen ! Defakto würde eine korrekte Anpassung sogar noch die Komplexität des Verfahrens im Vergleich zu AES noch weiter reduzieren. (3.6 = Entropie der Buchstaben unseres deutschen/englischen Alphabethes in das 256 Symbole umfassende ASCII Charset, die binäre Codierung im AES ist also wesentlich weniger redundant als normale Wörter basierend aus Textzeichen).

Gruß Hagen

[glkgereon]

meiner ansicht nach hinkt der vergleich.

der knackpunkt ist imho gar nicht, wieviele möglichkeiten es gibt das ganze zu dekodieren, sondern die fehlende möglichkeit den korrekt dekodierten Text als solchen zu erkennen.

Was hilft dir die bewiesene unsicherheit eines Verfahrens wenn du keine möglichkeit hast sie auszunutzen?
natürlich wäre es wahrscheinlich recht einfach möglich alle möglichen mappings durchzuprobieren (wobei ich selbst das bezweifle).
aber wie hilft dir nichts. du müsstest per Hand jeden einzelnen Versuch prüfen, da jeder zunächsteinmal sinn ergeben könnte.