Brutowe zmuszanie DES ze słabym kluczem

Question

Biorę udział w kursie dotyczącym kryptografii i utknąłem na zleceniu. Instrukcje są w następujący sposób:

tekstu jawnego plain6.txt został zaszyfrowany za pomocą algorytmu DES do encrypt6.dat użyciu klucza 64-bitowego podane jako ciąg 8 znaków (64 bitów, z których każdy 8-cie bit jest ignorowany), wszystkie znaki to litery (małe litery lub wielkie litery) oraz cyfry (od 0 do 9).

Aby wykonać zadanie, wyślij mi klucz szyfrowania przed 12 lutego, 29,59.

Uwaga: Oczekuję uzyskania klucza 8-bajtowego (64-bitowego). Każdy bajt powinien być zbieżny z odpowiednim bajtem w moim kluczu, z wyjątkiem najmniejszego znaczącego bitu o wartości , który nie jest używany w DES, a zatem może być arbitralny.

Oto kod do mojej pierwszej próbie w Pythonie:

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) 

jestem coraz prędkość 60.000 stara/sekundę. Hasło 8 bajtów na 62 znaki daje 13 trylionów możliwości, co oznacza, że ​​przy tej prędkości rozwiązywanie będzie wymagało 130 lat. Wiem, że to nie jest wydajna implementacja i że mogę uzyskać lepsze prędkości w szybszym języku, takim jak C lub jego smaki, ale nigdy w nich nie zaprogramowałem. Nawet jeśli otrzymam przyspieszenie o wartości 10, wciąż jesteśmy ogromnym skokiem z 10 000 000 000 na sekundę, aby uzyskać zakres godzin.

Czego mi brakuje? To ma być słaby klucz :). Cóż, słabszy niż pełny zestaw 256 znaków.

EDIT

Ze względu na pewne niejasności dotyczące cesji, tutaj jest pełny opis i niektóre pliki testowe do kalibracji: http://users.abo.fi/ipetre/crypto/assignment6.html

EDIT 2

Jest to realizacja surowej C to daje około 2.000.000 haseł/s na rdzeń na i7 2600K. Musisz określić pierwszy znak hasła i możesz ręcznie uruchomić wiele instancji na różnych rdzeniach/komputerach. Udało mi się rozwiązać problem za pomocą tego w ciągu kilku godzin na czterech komputerach.

#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

Założę, że pożądanym rozwiązaniem jest faktyczne zaimplementowanie algorytmu. Następnie, odkąd odszyfrowujesz sam siebie, możesz wcześnie wyskoczyć, co, zakładając, że zwykły tekst to również A-Za-z0-9, daje ci 98% szansy na zatrzymanie się po odszyfrowaniu pojedynczego bajtu, 99,97% szansa na zatrzymanie po odszyfrowaniu 2 bajtów i szansa na zatrzymanie się po 3 bajtach po 99,9995%.

Używaj również C lub Ocaml lub czegoś w tym stylu. Prawdopodobnie więcej czasu spędzasz manipulując strunami niż robisz cryption. Lub przynajmniej używaj multi-przetwarzania i zakręć wszystkie swoje rdzenie ...

Answer 2

Ta odpowiedź może być uzupełnieniem innych, bardziej konkretnych sugestii, ale pierwszą rzeczą, jaką należy zrobić, to uruchomić profilera.

Są naprawdę ładne przykłady tutaj:

How can you profile a python script?

EDIT:

Dla tego konkretnego zadania, zdaję sobie sprawę, że to nie pomoże. Częstotliwość próbna 10 GHz to ... Mocna na jednej maszynie z częstotliwością mniejszą niż ta. Być może mógłbyś wspomnieć o dostępnym sprzęcie. Nie staraj się również uruchamiać go przez kilka godzin. Kiedy znajdziesz metodę, która daje uzasadnione prawdopodobieństwo sukcesu w ciągu tygodnia, pozwól jej działać, poprawiając metody.

Answer 3

Nie mogę pomóc, ale zauważyłem sformułowanie zadania: w rzeczywistości nie jesteś proszony o samodzielne wdrożenie DES lub crackera. Jeśli tak jest, to dlaczego nie przyjrzeć się narzędziom takim jak John the Ripper lub hashcat.

Answer 4

Istnieje oczywisty czynnik przyspieszenia 256: Jeden bit na bajt nie jest częścią klucza. DES ma tylko klucz 56-bitowy, ale jeden przechodzi w 64 bitach. Ustal, który to jest, i wyrzuć równoważne znaki.

Answer 5

Mam dużo pomocy i jest to rozwiązanie w C. Ponieważ jestem początkującym C, to jest prawdopodobnie pełne błędów i złych praktyk, ale działa.

Jak CodeInChaos zorientowali się, tylko 31 znaków muszą być badane, ponieważ DES ignoruje co 8 bit klucza, dzięki czemu na przykład znaków ASCII b: *0110001*0 i c: *0110001*1 identycznej szyfrowanie/deszyfrowanie kiedy jest stosowany jako część klucza.

Używam biblioteki OpenSSL do deszyfrowania DES. Na moim komputerze prędkość, jaką osiąga, wynosi ~ 1,8 miliona haseł na sekundę, co daje całkowity czas na przetestowanie całej przestrzeni kluczy do około 5 dni. Wypada dzień przed upływem terminu. O wiele lepiej niż powyższy kod Pythona, który znajduje się na terytorium lat.

Jest jeszcze wiele do zrobienia, prawdopodobnie kod mógłby zostać zoptymalizowany i wkręcony. Gdybym mógł wykorzystać wszystkie moje rdzenie, oszacowałbym, że czas spadnie do nieco więcej niż jednego dnia, jednak nie mam jeszcze doświadczenia z wątkami.

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