Algorithmus, der in eine Richtung lange benötigt?

[Kukulkan]

Hallo,

Ich benötige eine Formel oder sowas, mit dem ich eine 128 Byte grosse Zeichenkette schnell verschlüsseln kann. Aber das Entschlüsseln muss dann lange dauern (auch wenn ich den Schlüssel kenne). Im Prinzip was ähnliches wie RSA, aber gerne einfacher, wenn auch mit grösserer Zeitdifferenz.

Gibt es da etwas?

Schön wäre folgendes (Beispiel zur Veranschaulichung):

Geheimtext: "hbzuBuBVTzUBGHuzG ... VGhVtu6F56vtzVghF56Ftvz"

Verschlüsseln mit dem Key "nj4i32432mgvk" dauert 0,1 Sekunden

Entschlüsseln mit dem Key "nj4i32432mgvk" dauert 2 Sekunden

Das wäre Perfekt! Gibt es da was?

Edit: Also sowas wie eine Einwegfunktion: http://de.wikipedia.org/wiki/Einwegfunktion

Grüsse,

Volker

[NicTheQuick]

Muss der Chiffrierte Text die selbe Länge haben wie der Originaltext?

Wenn der chiffrierte Text länger sein darf, könntest du beim Chriffrieren
Zufallsbytes und zusätzliche Prüfsummen einbauen, sodass du beim
Dechiffrieren immer ein paar Bytes ausprobieren musst, bis die Prüfsumme
übereinstimmt. Dafür muss die Prüfsumme natürlich eindeutig sein.

Hier mal mein Beispielcode:

Code: Alles auswählen

#Code_Min = -64   ;minimal -128
#Code_Max = 63    ;maximal 127

Procedure Encode(*mem, Size.l)
  Protected *b.Byte = *mem
  Protected *emem, *eb.Byte
  Protected r.b = (Random(#Code_Max - #Code_Min) + #Code_Min)
  Protected md5.s = MD5Fingerprint(*mem, Size)
  
  If Size = 0 : ProcedureReturn #False : EndIf
  
  *emem = AllocateMemory(Size + 32 + SizeOf(Long))
  If Not *emem : ProcedureReturn #False : EndIf
  *eb = *emem
  
  PokeL(*eb, Size)
  *eb + SizeOf(Long)
  
  While Size
    *eb\b = *b\b ! r
    r = *b\b
    
    *eb + 1
    *b + 1
    Size - 1
  Wend
  
  PokeS(*eb, md5, 32, #PB_Ascii)
  
  ProcedureReturn *emem
EndProcedure

Procedure Decode(*mem)
  Protected *b.Byte, Size.l = PeekL(*mem)
  Protected *dmem, *db.Byte
  Protected r.b = 0, c.l, rtmp.l
  Protected md5.s = ""
  
  *dmem = AllocateMemory(Size)
  If Not *dmem : ProcedureReturn #False : EndIf
  
  rtmp = #Code_Min
  While rtmp <= #Code_Max And md5 <> PeekS(*mem + SizeOf(Long) + Size, 32, #PB_Ascii)
    r = rtmp
    *db = *dmem
    *b = *mem + SizeOf(Long)
    c = Size
    While c
      *db\b = *b\b ! r
      r = *db\b
      
      *db + 1
      *b + 1
      c - 1
    Wend
    md5 = MD5Fingerprint(*dmem, Size)
    rtmp + 1
  Wend
  
  ProcedureReturn *dmem
EndProcedure

s.s = "Ich versuche jetzt mal einen etwas längeren Text zu schreiben, damit man die Zeiten auch noch gut messen kann. "
s   + "Ob mir das aber gelingt, kann ich nicht genau sagen. Notfalls kann man sich ja einen anderen Text dazu nehmem. "
s   + "Witzig finde ich aber, dass die Zeilen, die ich hier mal so frei dahin schreibe, immer genau gleich lang sind. "
s   + "Das könnte man jetzt noch länger so weiter machen, aber irgendwie wird es langweilig und spät ist es außerdem. "
s   + "Also höre ich mit dieser Zeile auf und versuche noch schnell die Zeitmessung zum Testen dazu zu programmieren."

Debug s

DisableDebugger
  time = ElapsedMilliseconds()
    For a = 1 To 100
      If *cipher : FreeMemory(*cipher) : EndIf
      *cipher = Encode(@s, Len(s))
    Next
  time = ElapsedMilliseconds() - time
EnableDebugger

Debug time

DisableDebugger
  time = ElapsedMilliseconds()
    For a = 1 To 100
      If *decipher : FreeMemory(*decipher) : EndIf
      *decipher = Decode(*cipher)
    Next
  time = ElapsedMilliseconds() - time
EnableDebugger

Debug time

Debug PeekS(*decipher)

Der Decoder kann bis zu 256 mal langsamer sein. Das kann man dann
genauer mit '#Code_Min' und '#Code_Max' einstellen. Die Differenz gibt
den maximalen Multiplikator der Encode-Dauer für die Decode-Dauer an.

Man könnte das ganze sicherlich auch ohne MD5 lösen, aber so war's
einfacher.

///Edit:
Mir fällt grad auf, dass ich deinen Key vergessen habe. Aber so siehst du
zumindest, dass man mittels 'Random()' die Ausführungsdauer natürlich
sehr leicht erhöhen kann. Im besten Fall, läuft 'Decode()' genau so lange
wie 'Encode()', im schlechtesten Fall braucht 'Decode()' (#Code_Max -
#Code_Min) mal so lange wie 'Encode()'.

[Kukulkan]

Hi Nic

Vielen Dank für deine Idee. Ich habe selbst sowas mit einem Hashcode gemacht. Allerdings so, dass ich so kodiert habe:

String = "HALLO WELT"

H -> MD5
HA -> MD5
HAL -> MD5
HALL -> MD5
HALLO -> MD5
HALLO -> MD5
HALLO W -> MD5
HALLO WE -> MD5
HALLO WEL -> MD5
HALLO WELT -> MD5

Kodiert: MD5-MD5-MD5-MD5-MD5-MD5-MD5-MD5-MD5-MD5

Zum entschlüsseln muss das Tool nun immer alle Varianten durchprobieren. Und das für jeden Buchstaben erneut. Leider geht das noch immer viel zu schnell, denn jeder Buchstabe bedarf nur ca. 100 Versuche. Das sind dann nur 1000 Berechnungen. Ich werde mal versuchen was passiert, wenn ich immer zwei Buchstaben kodiere. Dann müssten das theoretisch schon 50'000 Versuche sein.

Hintergrund:

Ich will ein Captcha für Webseiten machen, dass nur schwer zu knacken ist. Dabei soll ein JavaScript eine Grafik aus kleinen DIV-Boxen mit jeweils 1px auf 1px zusammensetzen. Die Grafikinformationen möchte ich so kodieren, dass das JavaScript auf einem aktuellen Browser und Rechner mindestens 4 Sekunden benötigt. Dann muss ein Spam-Roboter für jeden Versuch etwa 4 Sekunden Rechenzeit opfern (Einloggen, Captcha entschlüsseln, OCR machen und dann versuchen). Dadurch sinkt die Trefferquote sicher dramatisch. Mal sehen was ich da so basteln kann...

Grüsse,

Volker

[edel]

ja die Nutzer werden sich freuen ...

Es gibt durchaus Captcha die sicher sind ,oder baue Fragen ein.

[Kukulkan]

ja die Nutzer werden sich freuen ...

Aber er bekommt das ja gar nicht mit. Bis der Nutzer alle Felder ausgefüllt hat und dann unten im Formular ankommt ist sein ganz normales Captcha ja inzwischen dekodiert und wird angezeigt (ca. 4 Sekunden nach dem Seitenaufbau). Das Captcha selbst ist dann ein ganz normales (vermutlich mit einer Frage zur Grafik. zB Anzahl Striche oder Anzahl Buchstaben oder Ergebnis der Rechnung etc.). Wo liegt das Problem?

Volker

[Xaby]

Wieso muss das dekodieren so lange dauern?

Du kannst doch die IP-Adresse für eine bestimmte Zeit sperren.
So dass man nur alle 4 Sekunden einen Versuch zur Entschlüsselung starten kann.

Das läuft allerdings über PHP.

Ansonsten wäre noch die Frage, wieso du keine Zeitschleifen in dein JAVAScript einbaust.

So ganz habe ich den Sinn noch nicht verstanden. Du kannst ja auch gleich einen Broodforce-Code basteln, wo der Nutzer nur zwei Zahlen eingeben kann und die anderen 6 Zeichen müssen ausprobiert werden.

[Kaeru Gaman]

"Bruteforce" heit dat...

[Kukulkan]

Hi Xaby,

Du unterschätzt die "Hacker"

Wenn ich IP-Adressen sperre, dann lassen die eben einige Rechner parallel den Job machen. Wenn das jeder alle 4 Sekunden macht ist das kein Thema. Desshalb will ich gezielt Rechenleistung fordern. Eine einfache Zeitschleife in JavaScript würde ich innerhalb von einer Minute umbauen und damit aushebeln. Das ist völlig wirkungslos. Ich will ganz klar eine benötigte Information nur gegen Rechenleistung hergeben. Das dann in Verbindung mit einem guten Captcha sollte recht wirkungsvoll sein. Es darf allerdings nix sein, was man mit vorberechneten Tabellen ganz einfach abkürzen kann. Mein Beispiel oben wird im Moment noch durch einen SALT erschwert, der aus 100000 Zeichen besteht die vor dem eigentlichen Text stehen. So sind Rainbow-Tables aussen vor...

Recht komplex, das ganze zu verstehen wenn man sich noch nicht mit Kryptografie beschäftigt hat. Drum hab ich gedacht, dass hier jemand eine gute Idee hat. Die Idee von Nic geht ja im Prinzip in meine Richtung. Ich bin davon aber noch nicht überzeugt. Ich werd noch weiter grübeln...

Grüsse,

Volker

[Daniel P.]

Ich will ein Captcha für Webseiten machen, dass nur schwer zu knacken ist. Dabei soll ein JavaScript eine Grafik aus kleinen DIV-Boxen mit jeweils 1px auf 1px zusammensetzen. Die Grafikinformationen möchte ich so kodieren, dass das JavaScript auf einem aktuellen Browser und Rechner mindestens 4 Sekunden benötigt. Dann muss ein Spam-Roboter für jeden Versuch etwa 4 Sekunden Rechenzeit opfern (Einloggen, Captcha entschlüsseln, OCR machen und dann versuchen). Dadurch sinkt die Trefferquote sicher dramatisch. Mal sehen was ich da so basteln kann...

Sobald die JavaScript-Engine des Bots (sofern er überhaupt sowas hat) das Captcha zusammengebastelt hat, muss er nur die Positionen der DIV-Boxen auslesen und sich selbst daraus ein Bildchen basteln, um an die verschlüsselte Botschaft zu kommen. Sprich der Hacker muss sich nicht mal die Mühe machen, den Text zu dekodieren. Er brauch nur Sitzfleisch - ansonsten lässt sich das Captch genauso knacken wie viele andere auch. Auch wenn der Aufwand etwas höher ist...

[Kukulkan]

muss er nur die Positionen der DIV-Boxen auslesen und sich selbst daraus ein Bildchen basteln, um an die verschlüsselte Botschaft zu kommen.

Im Prinzip hast Du recht, aber dann ist es immer noch ein Captcha, das er normal lösen muss (zB eine Gleichung oder einen Text in diesem Bild erkennen etc.). Der Gesamtaufwand ist deutlich höher.

Nebenbei hab ich noch ein neues Captcha entwickelt. Ich nenne es Rainman-Captcha, da man die Holzstäbchen auf einem Tisch zählen muss. Wen's interessiert:
http://www.inspirant.de/captcha/captchatest2.php (da merkt man mal wie langsam diese gemieteten Server sind)
Das ist auch nicht unlösbar, aber zumindest kann man keine gewöhnliche OCR verwenden...

Grüsse,

Volker