首页 文章

使用弱密钥强制DES

提问于
浏览 次
10

我正在修读一门关于密码学的课程，我被困在一项任务上 . 说明如下：

明文plain6.txt已使用DES加密加密6.dat，使用64位密钥作为8个字符的字符串给出（64位，其中每8位被忽略），所有字符都是字母（小写或上限） -case）和数字（0到9） . 要完成分配，请在23.59年2月12日之前将加密密钥发送给我 . 注意：我希望得到一个8字节（64位）密钥 . 每个字节应与我的密钥中的相应字节一致，除了DES中未使用的最低有效位，因此可以是任意的 .

这是我在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)

我的速度达到60,000次/秒 . 密码为8个字节，超过62个字符，可提供13万亿个可能性，这意味着在这个速度下，我需要130年才能解决 . 我知道这不是一个有效的实现，我可以用更快的语言（如C或它的味道）获得更好的速度，但我从来没有编程 . 即使我加速10，我们仍然可以从每秒10,000,000,000的巨大飞跃中获得小时范围 .

我错过了什么？这应该是一个弱键:) . 好吧，弱于完整的256个字符集 .

EDIT

由于对分配的一些模糊性，这里有完整的描述和一些用于校准的测试文件：http://users.abo.fi/ipetre/crypto/assignment6.html

EDIT 2

这是一个原始的C实现，在i7 2600K上每个核心获得大约2.000.000个密码/秒 . 您必须指定密码的第一个字符，并且可以在不同的核心/计算机上手动运行多个实例 . 我设法在四台计算机上用几个小时就解决了这个问题 .

#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);
}
python cryptography brute-force des

5 回答

  • 1

    我认为理想的解决方案是实际实现算法 . 然后，由于你自己解密，你可以提前保释，假设纯文本也是A-Za-z0-9，你在解密单个字节后有98％的机会能够停止，99.97％在解密2个字节后停止的几率，以及在3个字节后停止的几率为99.9995％ .

    此外，使用C或Ocaml或类似的东西 . 你可能花费大量时间进行字符串操作而不是进行加密 . 或者，至少使用多处理并启动所有核心......

    回复于
  • 1

    有一个明显的因素256加速：每字节一位不是密钥的一部分 . DES只有56位密钥，但有一个通过64位密钥 . 弄清楚它是哪一位，扔掉相同的字符 .

    回复于
  • 2

    我有很多帮助，这是C语言的解决方案 . 由于我是C初学者，它可能充满了错误和不良习惯，但它确实有效 .

    正如CodeInChaos所知，只需要测试31个字符，因为DES会忽略密钥的每个第8位，例如，当用作密钥的一部分时，加密/解密中的ASCII字符 b: *0110001*0 和 c: *0110001*1 相同 .

    我正在使用OpenSSL库进行DES解密 . 在我的机器上，它达到的速度是每秒约180万个密码，这使得测试整个密钥空间的总时间大约为5天 . 距离截止日期还有一天 . 比上面的Python代码要好得多 .

    仍有改进的余地，可能代码可以进行优化和线程化 . 如果我可以使用我的所有核心，我估计时间会减少到一天以上，但我还没有使用线程的经验 .

    #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);
}
    回复于
  • 5

    我可以't help but notice the wording of the assignment: you are not actually requested to provide a DES implementation or cracker yourself. If that is indeed the case, why don'你看看John the Ripper或hashcat等工具 .

    回复于
  • 5

    这个答案可能是其他更具体的建议的补充，但你应该做的第一件事是运行 profiler .

    这里有很好的例子：

    How can you profile a python script?

    编辑：

    对于这项特殊任务，我意识到它无济于事 . 10 GHz的试用频率是......在频率低于此值的单台机器上很难 . 也许你可以提一下你有哪些硬件 . 此外，不要瞄准在几个小时内运行它 . 如果您找到一种方法可以在一周内给出合理的成功概率，那么您可以在改进方法的同时运行它 .

    回复于

相关问题