使用弱密钥对DES进行暴力破解
我正在上一个关于密码学的课程，但在一个作业上遇到了困难。作业的要求如下：
明文文件 plain6.txt 已经用 DES 加密成 encrypt6.dat，使用的密钥是一个 64 位的字符串，由 8 个字符组成（每 8 位中有一位被忽略），所有字符都是字母（大小写都可以）和数字（0 到 9）。
为了完成作业，请在 2 月 12 日 23:59 之前把加密密钥发给我。
注意：我希望得到一个 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 字符集，它要弱一些。
编辑
由于作业说明有些模糊，这里是完整的描述和一些测试文件供校准使用： http://users.abo.fi/ipetre/crypto/assignment6.html
编辑 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);
}
5 个回答
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
这里有一个明显的256倍速度提升：每个字节只用一个比特位，这个比特位并不算在密钥里。DES加密只用56位的密钥，但实际上传入的是64位。找出那个多余的比特位，然后把相应的字符去掉就行了。
6
我想你想要的解决方案其实是实现这个算法。因为你自己在解密，所以可以提前结束。假设明文只包含字母和数字（A-Z、a-z、0-9），那么你在解密一个字节后，有98%的机会可以停止；解密两个字节后，有99.97%的机会可以停止；而解密三个字节后，有99.9995%的机会可以停止。
另外，建议使用C语言、Ocaml或者类似的语言。你可能在字符串处理上花的时间比在加密上还要多。或者，至少可以使用多进程，把所有的核心都用上...