Brute buộc DES với khóa yếu

Question

Tôi đang tham gia một khóa học về Mật mã học và bị kẹt trong một bài tập. Các hướng dẫn như sau:

các plain6.txt bản rõ đã được mã hóa với DES để encrypt6.dat sử dụng một chìa khóa 64-bit được coi là một chuỗi 8 ký tự (64 bit trong đó mỗi bit thứ 8 được bỏ qua), tất cả các ký tự là chữ cái (chữ thường hoặc chữ thường) và chữ số (0 đến 9).

Để hoàn thành bài tập, hãy gửi cho tôi khóa mã hóa trước ngày 12, 23.59.

Lưu ý: Tôi hy vọng sẽ nhận được khóa 8 bit (64 bit). Mỗi byte cần trùng với byte tương ứng trong khóa của tôi, ngoại trừ ít nhất bit quan trọng không được sử dụng trong DES và do đó, có thể tùy ý.

Đây là đoạn mã để nỗ lực đầu tiên của tôi bằng 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) 

Tôi nhận được một tốc độ 60.000 cố gắng/giây. Mật khẩu 8 byte trên 62 ký tự cho 13 nghìn tỷ khả năng, có nghĩa là ở tốc độ này, tôi sẽ mất 130 năm để giải quyết. Tôi biết rằng đây không phải là một việc thực hiện hiệu quả và tôi có thể có được tốc độ tốt hơn trong một ngôn ngữ nhanh hơn như C hoặc hương vị của nó, nhưng tôi chưa bao giờ được lập trình trong đó. Ngay cả khi tôi tăng tốc độ 10, chúng tôi vẫn là một bước nhảy vọt lớn từ 10.000.000.000 mỗi giây để có được trong phạm vi giờ.

Tôi đang thiếu gì? Điều này được coi là một khóa yếu :). Vâng, yếu hơn bộ 256 ký tự đầy đủ.

EDIT

Do một số mơ hồ về nhiệm vụ, đây là mô tả đầy đủ và một số tác phẩm thử nghiệm cho hiệu chuẩn: http://users.abo.fi/ipetre/crypto/assignment6.html

EDIT 2

Đây là một thực hiện thô C có khoảng 2.000.000 mật khẩu/s trên mỗi lõi trên i7 2600K. Bạn phải chỉ định ký tự đầu tiên của mật khẩu và có thể chạy thủ công nhiều phiên bản trên các lõi/máy tính khác nhau. Tôi đã giải quyết vấn đề bằng cách sử dụng điều này trong vòng một vài giờ trên bốn máy tính.

#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

Tôi cho rằng giải pháp mong muốn là thực sự triển khai thuật toán. Sau đó, vì bạn đang giải mã chính mình, bạn có thể bảo lãnh sớm, giả sử văn bản thuần túy cũng là A-Za-z0-9, cho bạn cơ hội 98% có thể dừng sau khi giải mã một byte, 99,97% cơ hội dừng sau khi giải mã 2 byte và 99,9995% cơ hội dừng sau 3 byte.

Ngoài ra, hãy sử dụng C hoặc Ocaml hoặc một cái gì đó tương tự. Bạn có thể dành nhiều thời gian hơn để thực hiện thao tác chuỗi hơn là bạn đang thực hiện thao tác cryption. Hoặc, ít nhất sử dụng đa xử lý và quay lên tất cả các lõi của bạn ...

Answer 2

Câu trả lời này có thể bổ sung cho lời đề nghị cụ thể hơn khác, nhưng điều đầu tiên bạn nên làm là chạy một profiler.

Có những ví dụ thật sự tốt đẹp ở đây:

How can you profile a python script?

EDIT:

Đối với nhiệm vụ đặc biệt này, tôi nhận ra nó sẽ không giúp đỡ. Tần số dùng thử là 10 GHz là ... Cứng trên một máy có tần số nhỏ hơn. Có lẽ bạn có thể đề cập đến phần cứng nào bạn có sẵn. Ngoài ra, bạn không nên chạy nó trong vài giờ nữa. Khi bạn tìm thấy một phương pháp cung cấp cho một xác suất hợp lý của sự thành công trong tuần bạn có sau đó để cho nó chạy trong khi cải thiện phương pháp của bạn.

Answer 3

Tôi không thể không chú ý đến từ ngữ của bài tập: bạn không thực sự được yêu cầu cung cấp bản triển khai DES hoặc cracker. Nếu đó thực sự là trường hợp, tại sao bạn không xem xét các công cụ như John the Ripper hoặc hashcat.

Answer 4

Có một yếu tố rõ ràng 256 tăng tốc: Một bit trên mỗi byte không phải là một phần của khóa. DES chỉ có một khóa 56 bit, nhưng một trong 64 bit. Tìm ra bit đó là gì, và vứt bỏ các ký tự tương đương.

Answer 5

Tôi đã có một chút trợ giúp và đây là giải pháp trong C. Vì tôi là người mới bắt đầu C, có thể có đầy đủ các lỗi và thực hành không tốt, nhưng nó hoạt động.

Như CodeInChaos tìm ra, chỉ có 31 ký tự cần phải được kiểm tra, vì DES bỏ qua tất cả các bit thứ 8 của khóa, làm cho các ký tự ASCII Ví dụ b: *0110001*0 và c: *0110001*1 giống hệt nhau trong mã hóa/giải mã khi được sử dụng như một phần của chìa khóa.

Tôi đang sử dụng thư viện OpenSSL để giải mã DES. Trên máy tính của tôi tốc độ đạt được là 1,8 triệu mật khẩu mỗi giây, trong đó đặt tổng thời gian để kiểm tra toàn bộ không gian chính trong khoảng 5 ngày. Điều này rơi một ngày ngắn hạn của thời hạn. Tốt hơn rất nhiều so với mã Python ở trên trong lãnh thổ năm.

Vẫn còn chỗ để cải thiện, có thể mã được tối ưu hóa và được tạo luồng. Nếu tôi có thể sử dụng tất cả các lõi của tôi, tôi ước tính thời gian sẽ giảm xuống còn hơn một ngày, tuy nhiên tôi chưa có kinh nghiệm về luồng.

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