Force Brute DES avec une faible clé

Je prends un cours sur la Cryptographie et je suis bloqué sur un exercice. Les instructions sont comme suit:

Le texte en clair plain6.txt a été chiffré avec DES à encrypt6.dat à l'aide d'une clé de 64 bits donnée par une chaîne de 8 caractères (64
bits dont tous les 8 bits est ignoré), tous les caractères des lettres
(minuscules ou majuscules) et les chiffres (0 à 9).

Pour terminer le travail, envoyez-moi la clé de chiffrement avant février
12, 23h59.

Note: je m'attends à obtenir une 8 octets (64 bits) clé. Chaque octet doit
coïncider avec l'octet correspondant à ma clé, sauf pour le moins
bit significatif qui n'est pas utilisé dans DES et ainsi, peut être qu'arbitraire.

Voici le code de ma première tentative en 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)

J'obtiens une vitesse de 60.000 tente /seconde. Un mot de passe de 8 octets de plus de 62 caractères donne 13 milliards de possibilités, ce qui signifie qu'au de cette vitesse, il me faudrait plus de 130 ans à résoudre. Je sais que ce n'est pas une mise en œuvre efficace et que je pourrais obtenir une meilleure vitesse plus rapide des langages comme le C ou c'est de saveurs, mais je n'ai jamais programmé dans ceux-ci. Même si j'ai une vitesse de 10, nous sommes encore un énorme bond loin de 10,000,000,000 par seconde pour obtenir dans la gamme heures.

Ce qui me manque? C'est censé être une faiblesse de la clé :). Eh bien, plus faible que la totalité de 256 caractères.

MODIFIER

En raison d'une certaine ambiguïté au sujet de la cession, est ici une description complète et certains fichiers d'essai pour l'étalonnage: http://users.abo.fi/ipetre/crypto/assignment6.html

EDIT 2

C'est un brut, C la mise en œuvre qui obtient environ 2.000.000 de mots de passe/s par cœur sur un i7 2600K. Vous devez spécifier le premier caractère du mot de passe et pouvez exécuter manuellement plusieurs instances sur les différents cœurs ou des ordinateurs. J'ai réussi à résoudre le problème en utilisant ce dans un délai de quelques heures sur quatre ordinateurs.

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

OriginalL'auteur element | 2012-02-02