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.

InformationsquelleAutor element | 2012-02-02
Schreibe einen Kommentar