Brute Force DES mit einem schwachen Schlüssel
Nehme ich einen Kurs über Kryptographie und komme an einer Aufgabe. Die Anweisungen sind wie folgt:
Klartext plain6.txt verschlüsselt mit DES zu encrypt6.dat mit einem 64-bit-Schlüssel (gegeben als string von 8 Zeichen (64
bits, von denen jedes 8. bit ignoriert wird), werden alle Zeichen als Buchstaben
(Kleinbuchstaben oder Großbuchstaben) und Ziffern (0 bis 9).Um die Zuordnung abgeschlossen haben, senden Sie mir die Schlüssel bereits vor dem Februar
12, 23.59.Hinweis: ich erwarten Sie, dass ein 8-byte (64-bit) - Taste. Jedes byte soll
zeitgleich mit dem entsprechenden byte in mein key, außer für die am wenigsten
significant bit ist nicht im DES und so könnte willkürlich sein.
Hier ist der code zu meinem ersten Versuch in Python:
import time
from Crypto.Cipher import DES
class BreakDES(object):
def __init__(self, file, passwordLength = 8, testLength = 8):
self.file = file
self.passwordLength = passwordLength
self.testLength = testLength
self.EncryptedFile = open(file + '.des')
self.DecryptedFile = open(file + '.txt')
self.encryptedChunk = self.EncryptedFile.read(self.testLength)
self.decryptedChunk = self.DecryptedFile.read(self.testLength)
self.start = time.time()
self.counter = 0
self.chars = range(48, 58) + range(65, 91) + range(97, 123)
self.key = False
self.broken = False
self.testPasswords(passwordLength, 0, '')
if not self.broken:
print "Password not found."
duration = time.time() - self.start
print "Brute force took %.2f" % duration
print "Tested %.2f per second" % (self.counter / duration)
def decrypt(self):
des = DES.new(self.key.decode('hex'))
if des.decrypt(self.encryptedChunk) == self.decryptedChunk:
self.broken = True
print "Password found: 0x%s" % self.key
self.counter += 1
def testPasswords(self, width, position, baseString):
for char in self.chars:
if(not self.broken):
if position < width:
self.testPasswords(width, position + 1, baseString + "%c" % char)
self.key = (baseString + "%c" % char).encode('hex').zfill(16)
self.decrypt()
# run it for password length 4
BreakDES("test3", 4)
Bin ich immer eine Geschwindigkeit von 60.000 versucht /Sekunde. Ein Passwort von 8 bytes über 62 Charaktere gibt 13 Billionen Möglichkeiten, was bedeutet, dass bei dieser Geschwindigkeit, es würde mich 130 Jahren zu lösen. Ich weiß, dass dies nicht für eine effiziente Umsetzung und, dass ich konnte besser Geschwindigkeit in eine schnellere Sprache wie C oder Aromen, aber ich habe noch nie programmiert diese. Auch, wenn ich einen speed-up von 10, wir sind immer noch ein großer Sprung Weg von 10,000,000,000 pro Sekunde, um in den Stunden-Bereich.
Was bin ich? Dies soll zu einer schwachen Schlüssel :). Naja, schwächer als die 256-Zeichen-set.
BEARBEITEN
Aufgrund einiger Unklarheit über die Zuordnung, hier ist die vollständige Beschreibung und ein paar test-Dateien für die Kalibrierung: http://users.abo.fi/ipetre/crypto/assignment6.html
EDIT 2
Dies ist eine grobe C-Implementierung, wird um 2.000.000 Kennwörter/s pro Kern auf einem i7 2600K. Sie geben die ersten Zeichen des Kennworts und können manuell führen Sie mehrere Instanzen auf verschiedenen Kernen/Rechnern. Ich habe es geschafft das problem zu lösen mit dieser innerhalb von ein paar Stunden auf vier Computern.
#include <stdio.h> /* fprintf */
#include <stdlib.h> /* malloc, free, exit */
#include <unistd.h>
#include <string.h> /* strerror */
#include <signal.h>
#include <openssl/des.h>
static long long unsigned nrkeys = 0; // performance counter
char *
Encrypt( char *Key, char *Msg, int size)
{
static char* Res;
free(Res);
int n=0;
DES_cblock Key2;
DES_key_schedule schedule;
Res = ( char * ) malloc( size );
/* Prepare the key for use with DES_ecb_encrypt */
memcpy( Key2, Key,8);
DES_set_odd_parity( &Key2 );
DES_set_key_checked( &Key2, &schedule );
/* Encryption occurs here */
DES_ecb_encrypt( ( unsigned char (*) [8] ) Msg, ( unsigned char (*) [8] ) Res,
&schedule, DES_ENCRYPT );
return (Res);
}
char *
Decrypt( char *Key, char *Msg, int size)
{
static char* Res;
free(Res);
int n=0;
DES_cblock Key2;
DES_key_schedule schedule;
Res = ( char * ) malloc( size );
/* Prepare the key for use with DES_ecb_encrypt */
memcpy( Key2, Key,8);
DES_set_odd_parity( &Key2 );
DES_set_key_checked( &Key2, &schedule );
/* Decryption occurs here */
DES_ecb_encrypt( ( unsigned char (*) [8]) Msg, ( unsigned char (*) [8]) Res,
&schedule, DES_DECRYPT );
return (Res);
}
void ex_program(int sig);
int main(int argc, char *argv[])
{
(void) signal(SIGINT, ex_program);
if ( argc != 4 ) /* argc should be 2 for correct execution */
{
printf( "Usage: %s ciphertext plaintext keyspace \n", argv[0] );
exit(1);
}
FILE *f, *g;
int counter, i, prime = 0, len = 8;
char cbuff[8], mbuff[8];
char letters[] = "02468ACEGIKMOQSUWYacegikmoqsuwy";
int nbletters = sizeof(letters)-1;
int entry[len];
char *password, *decrypted, *plain;
if(atoi(argv[3]) > nbletters-2) {
printf("The range must be between 0-%d\n", nbletters-2);
exit(1);
}
prime = atoi(argv[1])
// read first 8 bytes of the encrypted file
f = fopen(argv[1], "rb");
if(!f) {
printf("Unable to open the file\n");
return 1;
}
for (counter = 0; counter < 8; counter ++) cbuff[counter] = fgetc(f);
fclose(f);
// read first 8 bytes of the plaintext file
g = fopen(argv[2], "r");
if(!f) {
printf("Unable to open the file\n");
return 1;
}
for (counter = 0; counter < 8; counter ++) mbuff[counter] = fgetc(g);
fclose(g);
plain = malloc(8);
memcpy(plain, mbuff, 8);
// fill the keys
for(i=0 ; i<len ; i++) entry[i] = 0;
entry[len-1] = prime;
// loop until the length is reached
do {
password = malloc(8);
decrypted = malloc(8);
// build the pasword
for(i=0 ; i<len ; i++) password[i] = letters[entry[i]];
nrkeys++;
// end of range and notices
if(nrkeys % 10000000 == 0) {
printf("Current key: %s\n", password);
printf("End of range ");
for(i=0; i<len; i++) putchar(letters[lastKey[i]]);
putchar('\n');
}
// decrypt
memcpy(decrypted,Decrypt(password,cbuff,8), 8);
// compare the decrypted with the mbuff
// if they are equal, exit the loop, we have the password
if (strcmp(mbuff, decrypted) == 0)
{
printf("We've got it! The key is: %s\n", password);
printf("%lld keys searched\n", nrkeys);
exit(0);
}
free(password);
free(decrypted);
// spin up key until it overflows
for(i=0 ; i<len && ++entry[i] == nbletters; i++) entry[i] = 0;
} while(i<len);
return 0;
}
void ex_program(int sig) {
printf("\n\nProgram terminated %lld keys searched.\n", nrkeys);
(void) signal(SIGINT, SIG_DFL);
exit(0);
}
- Vielleicht Lesen Sie über die Struktur DES. Es gibt exploits, die basieren auf, wie Informationen verbreitet über die Pässe.
- Bravo für die, die nicht warten, bis die Nacht vor.
- Wenn Sie Geld herumliegen, und Sie wirklich wollen, um brute-force, betrachten, dass Sie 10^16 amazon ec2-jobs, von denen jeder nur verschlüsselt gegebenen Klartext mit der zugewiesenen Taste.
- Sie könnten immer versuchen, dieses posting auf das crypto-stack exchange.
- Dieser Kerl Fragen über Schwächen in der Initialisierungsvektor des Algorithmus. Vielleicht haben Sie etwas gelernt?
- Lassen Sie uns sein klar vorne: mit den Informationen, die Sie zur Verfügung gestellt, Sie können dies nicht in reinem python auf einem PC-Klasse Maschine.
Du musst angemeldet sein, um einen Kommentar abzugeben.
Ich würde davon ausgehen, die gewünschte Lösung zu implementieren, die algorithmn. Dann, da Sie entschlüsseln sich selbst, können Sie Kaution früh, die werden, vorausgesetzt, die plain-text ist auch A-Za-z0-9 gibt Ihnen eine 98% chance in der Lage zu stoppen, nachdem er einen einzelnen byte eines 99.97 - % - chance Stoppt nach der Entschlüsselung von 2 bytes und einem 99.9995% chance auf beenden nach 3 bytes.
Nutzen Sie auch C oder Ocaml, oder so. Du bist wahrscheinlich verbringen VIEL mehr Zeit damit, string-manipulation, als Sie tun cryption. Oder zumindest die Verwendung von multi-processing-und spin-up alle Ihre Kerne...
Es ist ein offensichtlicher Faktor 256 speedup: Ein bit pro byte ist nicht Teil des Schlüssels. Hat DES nur einen 56 bit-Schlüssel, aber man geht in 64 bit. Herauszufinden, welche es ist, und wegwerfen, entsprechende Zeichen.
Ich habe ganz ein bisschen helfen, und dies ist eine Lösung in C. ich bin ein C-Anfänger, es ist wahrscheinlich voll von bugs und die schlechte Praxis, aber es funktioniert.
Als CodeInChaos herausgefunden, nur 31 Zeichen geprüft werden müssen, weil DES ignoriert jedes 8. bit des Schlüssels, so dass zum Beispiel ASCII-Zeichen
b: *0110001*0
undc: *0110001*1
identisch in der Verschlüsselung/Entschlüsselung, wenn verwendet, als ein Teil des Schlüssels.Ich bin mit dem OpenSSL-Bibliothek für die DES-Entschlüsselung. Auf meiner Maschine die Drehzahl erreicht ist ~1,8 Millionen Passwörter pro Sekunde, was bringt die Gesamt Zeit zum testen des gesamten key space für rund 5 Tage. Dies fällt am Tag kurz vor der deadline. Viel besser als Python-code über die in den Jahren Hoheitsgebiet.
Gibt es noch Raum für Verbesserungen, die wahrscheinlich den code optimiert werden konnten und Gewinde. Wenn ich könnte alle meine Kerne überschlage ich die Zeit, würde nach unten gehen, um ein bisschen mehr als einen Tag, aber ich habe keine Erfahrung mit threading noch.
Kann ich nicht helfen, aber beachten Sie die Formulierung der Abtretung: Sie sind nicht eigentlich gebeten, eine DES-Implementierung oder cracker selbst. Wenn das wirklich der Fall ist, warum nimmst du nicht einen Blick auf tools wie John the Ripper oder hashcat.
Diese Antwort eine Ergänzung zu anderen mehr konkrete Vorschläge, aber das erste, was Sie tun sollten, ist zu laufen ein profiler.
Gibt es wirklich schöne Beispiele hier:
Wie kann man profile ein python-script?
EDIT:
Für diese Besondere Aufgabe, ich weiß, es wird nicht helfen. Eine trial-Frequenz von 10 GHz ist... Schwer, auf einer einzigen Maschine mit Frequenz weniger als das. Vielleicht könntest du erwähnen, welche hardware Sie zur Verfügung haben.
Auch nicht unser Ziel, für Sie läuft es in ein paar Stunden. Wenn Sie eine Methode finden, die einen vernünftigen Wahrscheinlichkeit des Erfolges innerhalb der Woche haben Sie dann laufen lassen, während die Verbesserung Ihrer Methoden.