RC4 Wort entschlüsseln

[DienerAl]

Guten Tag,

ein Kumpel hat ein Wort (5stellig) mit RC4 verschlüsselt, wie es bei SSL/TLS gängig gemacht wird. Dazu hat er eine kleine Phyton Bibliothek verwendet:

import random
def gensamples(filename, count, data):
f = open(filename, ’w’)
for i in xrange(count):
a = rc4crypt(data, randkey(16))
f.write(", ".join(a) + "\n")
f.close()
def rc4crypt(data, key):
x = 0
box = range(256)
for i in range(256):
x = (x + box[i] + key[i % len(key)]) % 256
box[i], box[x] = box[x], box[i]
x = 0
y = 0
out = []
for char in data:
x = (x + 1) % 256
y = (y + box[x]) % 256
box[x], box[y] = box[y], box[x]
out.append(str(ord(char) ^ box[(box[x] + box[y]) % 256]))
return out
def randkey(size):
a = []
for i in range(size):
a.append(random.randint(0,255))
return a

welches er mit

#!/usr/bin/python
import rc4
import sys
if (len(sys.argv) != 4):
sys.exit("usage: " + sys.argv[0] + " filename number-of-samples plaintext")
rc4.gensamples(sys.argv[1], eval(sys.argv[2]), sys.argv[3])

aufgerufen hat. Die erzeugte Datei ist rund 27GB groß. Nun will er das Wort von mir wissen. Wie kann ich da vorgehen? Ich weiß, dass RC4 verwundbar wird, wenn man oft das gleiche verschlüsselt. Denn dann kann man über Wahrscheinlichkeitsrechnung zum Ergebnis kommen. Eine weitere Möglichkeit wäre, das ganze einfach zu Brute Forcen. Ich habe hier einen i5 2500K @4,4GHz, das dauert zwar etwas, aber dennoch könnte auch das klappen. Jedoch brauche ich dazu ein Script oder ein Programm. Kann mir da bitte jemand behilflich sein?


Mit freundlichen Grüßen
DienerAl

 

[SchwarzeBeere]

Nanana... "Dein Freund" wollte sicherlich, dass du das selbst machst. So schwer ist das auch garnicht. Ein paar Quellen mit Pseudocode findest sogar recht schnell über Google (Scholar), z.B. mit den Suchbegriffen "RC4", "Ciphertext-only" und "Plaintext recovery": http://cr.yp.to/streamciphers/rc4biases-20130708.pdf. Einen Vortrag dazu findest du auch bei Usenix: https://www.usenix.org/conference/usenixsecurity13/technical-sessions/paper/alFardan

 

[DienerAl]

Die Sache ist ja, ich verstehe was er will und weiß - logisch gesehen - wie man es löst. Jedoch fehlt mir dazu bisher noch die Erfahrung in Scriptsprachen wie Python. Bisher bin ich nur in Java warm, weil ich mich da eingearbeitet hatte.
Ich habe auch einen Code, der jedoch nur einen key einliest.
Ich muss jedoch seeehr viele Keys einlesen und die Ausgabe dann mithilfe der Wahrscheinlichkeit interpretieren.

import base64

with open("/path/to/file.txt", "r") as encrypted_file:
    data = base64.b64decode(encrypted_file.read())
key = "<rc4 key>"

S = range(256)
j = 0
out = []

#KSA Phase
for i in range(256):
    j = (j + S[i] + ord( key[i % len(key)] )) % 256
    S[i] , S[j] = S[j] , S[i]

#PRGA Phase
i = j = 0
for char in data:
    i = ( i + 1 ) % 256
    j = ( j + S[i] ) % 256
    S[i] , S[j] = S[j] , S[i]
    out.append(chr(ord(char) ^ S[(S[i] + S[j]) % 256]))

decrypted_text = ''.join(out)
with open('decrypted.txt', 'w') as decrypted_file:
    decrypted_file.write(decrypted_text)

Ich bitte um Hilfe.

 

[SchwarzeBeere]

Machs doch einfach in Java - du musst ja nur die von ihm generierte Datei verarbeiten und nicht seinen Code in irgendeiner Form weiterverwenden

Schau dir den Code von deinem Freund nochmal genau an:

for i in xrange(count):
     a = rc4crypt(data, randkey(16))
     f.write(", ".join(a) + "\n")
     f.close()

Die Datei hat also eine bestimmte Form, nämlich

,c0\n,c1\n,c2\n...

wobei die Ursprungsnachricht m immer gleich ist und nur der Key geändert wird:

c0 = rc4(m,k0)
c1 = rc4(m,k1)
...

Weiterhin gilt

k0 = r0,0 + r0,1 + ... + r0,15
k1 = r1,0 + r1,1 + ... + r1,15
...

Das Ziel der Aufgabe hast du bereits genannt:

Nun will er das Wort von mir wissen.

Das o.g. Paper enthält mehrere Algorithmen, die dieses Problem behandeln. Alg. 3 auf Seite 10 enthält z.B. einen sehr einfachen Ansatz dar, der allerdings eine sehr hohe Zahl an Ciphertexts benötigt. Alg. 4 und 5 verfeinern den Angriff, in dem sie die Wahrscheinlichkeiten der einzelnen Zeichen im Plaintext justieren. Alg. 4 ist auch noch relativ einfach implementierbar, während Alg. 5 schon ein tieferes Verständnis erfordert (d.h. du solltest zumindest das Paper gelesen haben).

Wenn ich deinen Code richtig verstanden habe, dann hast du dich inzwsichen für die Bruteforce-Methode entschieden, oder? Problematisch ist hier allerdings die Überprüfung, ob das Ergebnis gefunden wurde. Letzten Endes müsstest du alle möglichen Keys überprüfen, alle Ciphertexte mit allen Keys entschlüsseln und den gemeinsamen Plaintext schussendlich wählen, der aus allen c entschlüsselt werden konnte. Du kannst dir also bis zum Ende nicht sicher sein, ob du wirklich den Plaintext gefunden hast. Der Speicheraufwand ist gleichzeitig gigantisch und ein Ergebnis in akzeptabler unrealistisch.