DES di forza bruta con una chiave debole

Question

Sto seguendo un corso su Crittografia e sono bloccato su un compito. Le istruzioni sono le seguenti:

Il plain6.txt testo in chiaro è stato criptato con DES per encrypt6.dat utilizzando una chiave a 64 bit dato come una stringa di 8 caratteri (64 bit di cui si ignora ogni 8 bit), tutti i caratteri sono lettere (minuscole o maiuscole) e cifre (da 0 a 9).

Per completare l'incarico, inviare la chiave di crittografia prima del febbraio 12, 23,59.

Nota: prevedo di ottenere una chiave da 8 byte (64 bit). Ogni byte dovrebbe coincidere con il byte corrispondente nella mia chiave, ad eccezione del minimo significativo che non è utilizzato in DES e quindi potrebbe essere arbitrario.

Ecco il codice per il mio primo tentativo 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) 

sto ottenendo una velocità di 60.000 tentativi/secondo. Una password di 8 byte oltre 62 caratteri offre 13 trilioni di possibilità, il che significa che a questa velocità mi ci vorranno 130 anni per risolvere. So che questa non è un'implementazione efficiente e che potrei ottenere migliori velocità in un linguaggio più veloce come C o i suoi sapori, ma non ho mai programmato in quelli. Anche se ottengo un aumento della velocità di 10, siamo ancora a un enorme balzo da 10.000.000.000 al secondo per entrare nell'intervallo di ore.

Cosa mi manca? Questa dovrebbe essere una chiave debole :). Bene, più debole del set completo di 256 caratteri.

EDIT

causa di una certa ambiguità circa l'assegnazione, ecco la descrizione completa e alcuni file di prova per la calibrazione: http://users.abo.fi/ipetre/crypto/assignment6.html

EDIT 2

Questa è un'implementazione grezza C che ottiene circa 2.000.000 di password/s per core su un i7 2600K. È necessario specificare il primo carattere della password e può eseguire manualmente più istanze su diversi core/computer. Sono riuscito a risolvere il problema utilizzando questo entro un paio d'ore su quattro computer.

#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); 
} 

Answer 1

Suppongo che la soluzione desiderata sia quella di implementare effettivamente l'algoritmo. Quindi, dal momento che stai decodificando te stesso, puoi eseguire il bail in anticipo, il che, assumendo che il testo in chiaro sia anche A-Za-z0-9, ti dà una probabilità del 98% di essere in grado di fermarti dopo la decrittografia di un singolo byte, un 99,97% possibilità di fermarsi dopo la decrittografia di 2 byte e una possibilità del 99,9995% di fermarsi dopo 3 byte.

Inoltre, utilizzare C o Ocaml o qualcosa del genere. Probabilmente stai spendendo MOLTO più tempo a manipolare le stringhe piuttosto che a criptare. O, almeno, usa la multielaborazione e fai ruotare tutti i tuoi core ...

Answer 2

Questa risposta può essere complementare ad altri suggerimenti più specifici, ma la prima cosa da fare è eseguire un profiler.

Ci sono veramente bello esempi qui:

How can you profile a python script?

EDIT:

Per questo particolare compito, mi rendo conto che non vi aiuterà. Una frequenza di prova di 10 GHz è ... Difficile su una singola macchina con frequenza inferiore a quella. Forse potresti menzionare l'hardware che hai a disposizione. Inoltre, non mirare a farlo funzionare durante alcune ore. Quando trovi un metodo che dà una ragionevole probabilità di successo entro la settimana, allora lascialo correre mentre migliora i tuoi metodi.

Answer 3

Non posso fare a meno di notare la formulazione del compito: in realtà non sei tenuto a fornire personalmente un'implementazione DES o un cracker. Se è così, perché non dai un'occhiata a strumenti come John the Ripper o hashcat.

Answer 4

C'è un evidente aumento di velocità del fattore 256: un bit per byte non fa parte della chiave. DES ha solo una chiave a 56 bit, ma una passa a 64 bit. Scopri qual è il bit e getta via personaggi equivalenti.

Answer 5

Ho avuto un po 'di aiuto e questa è una soluzione in C. Siccome sono un principiante C, probabilmente è pieno di bug e cattive pratiche, ma funziona.

Come CodeInChaos capito, solo 31 caratteri devono essere testati, perché DES ignora ogni 8 bit della chiave, rendendo per esempio, i caratteri ASCII b: *0110001*0 e c: *0110001*1 identici in crittografia/decrittografia quando viene utilizzato come parte della chiave.

Sto utilizzando la libreria OpenSSL per la decrittografia DES. Sulla mia macchina la velocità raggiunta è di circa 1,8 milioni di password al secondo, il che mette il tempo totale per testare l'intero spazio chiave a circa 5 giorni. Questo cade un giorno prima della scadenza. Molto meglio del codice Python sopra il quale si trova nel territorio degli anni.

C'è ancora spazio per miglioramenti, probabilmente il codice potrebbe essere ottimizzato e filettato. Se potessi usare tutti i miei core, stimerei che il tempo sarebbe passato a un po 'più di un giorno, tuttavia non ho ancora esperienza con il threading.

#include <stdio.h> 
#include <unistd.h> 
#include <string.h> 
#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() 
{ 
    (void) signal(SIGINT, ex_program); 

    FILE *f, *g; // file handlers 
    int counter, i, len = 8; // counters and password length 
    char cbuff[8], mbuff[8]; // buffers 
    char letters[] = "02468ACEGIKMOQSUWYacegikmoqsuwy"; // reduced letter pool for password brute force 
    int nbletters = sizeof(letters)-1; 
    int entry[len]; 
    char *password, *decrypted; 

    // read first 8 bytes of the encrypted file 
    f = fopen("test2.dat", "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("test2.txt", "r"); 
    if(!f) { 
     printf("Unable to open the file\n"); 
     return 1; 
    } 
    for (counter = 0; counter < 8; counter ++) mbuff[counter] = fgetc(g); 
    fclose(g); 

    // fill the initial key 
    for(i=0 ; i<len ; i++) entry[i] = 0; 

    // 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++; 

     if(nrkeys % 10000000 == 0) { 
      printf("Current key: %s\n", password); 
     } 

     // 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", 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); 
}