用弱密钥强行强制DES [英] Brute forcing DES with a weak key
问题描述
我正在上一门密码学课程，并且被固定在一项作业上。指令如下：
I am taking a course on Cryptography and am stuck on an assignment. The instructions are as follows:
明文plain6.txt已使用DES加密，使用64位密钥指定为crypto6.dat。一串8个字符的字符串（64个
位，每8位被忽略），所有字符均为字母
（小写或大写）和数字（0至9）。
The plaintext plain6.txt has been encrypted with DES to encrypt6.dat using a 64-bit key given as a string of 8 characters (64 bits of which every 8th bit is ignored), all characters being letters (lower-case or upper-case) and digits (0 to 9).
要完成分配，请在2月
12、23.59之前给我发送加密密钥。
To complete the assignment, send me the encryption key before February 12, 23.59.
注意：我希望获得一个8字节（64位）的密钥。
的每个字节应与我密钥中的相应字节重合，除了
的最低有效位（在DES中不使用，因此可以是任意的）。
Note: I expect to get an 8-byte (64-bits) key. Each byte should coincide with the corresponding byte in my key, except for the least significant bit which is not used in DES and thus, could be arbitrary.
这是我第一次尝试使用Python的代码：
Here is the code to my first attempt 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)
我的速度为每秒60.000次尝试。 8个字节（超过62个字符）的密码提供13万亿种可能性，这意味着以这种速度，我需要130年才能解决。我知道这不是一个有效的实现，并且我可以使用更快的语言（如C或它的风格）来获得更好的速度，但是我从来没有编程过。即使我的速度提高了10，我们仍然要从每小时10,000,000,000跳到小时范围。
I am getting a speed of 60.000 tries / second. A password of 8 bytes over 62 characters gives 13 trillion possibilities, which means that at this speed it would take me 130 years to solve. I know that this is not an efficient implementation and that I could get better speeds in a faster language like C or it's flavors, but I have never programmed in those. Even if I get a speed-up of 10, we're still a huge leap away from 10,000,000,000 per second to get in the hours range.
我还缺少什么？这应该是一个弱键:)。好吧，比完整的256个字符集弱。
What am I missing? This is supposed to be a weak key :). Well, weaker than the full 256 character set.
EDIT
由于关于分配的一些歧义，这里是完整的描述和一些用于校准的测试文件： http：/ /users.abo.fi/ipetre/crypto/assignment6.html
Due to some ambiguity about the assignment, here is the full description and some test files for calibration: http://users.abo.fi/ipetre/crypto/assignment6.html
编辑2
这是一个粗略的C实现，在i7 2600K上每个内核大约获得2.000.000密码/秒。您必须指定密码的第一个字符，并且可以在不同的内核/计算机上手动运行多个实例。我设法在几个小时内在四台计算机上解决了这个问题。
This is a crude C implementation that gets around 2.000.000 passwords/s per core on an i7 2600K. You have to specify the first character of the password and can manually run multiple instances on different cores/computers. I managed to solve the problem using this within a couple of hours on four computers.
#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);
}
推荐答案
我会假设所需的解决方案是实际实现算法。然后，由于您正在解密自己，因此可以提早保释，假设纯文本也是A-Za-z0-9，则可以使您有98％的机会能够在解密单个字节后停止，即99.97％解密2个字节后停止的机会，以及3个字节后停止的机会的99.9995％。
I would assume the desired solution is to actually implement the algorithmn. Then, since your're decrypting yourself, you can bail early, which, assuming the plain text is also A-Za-z0-9, gives you a 98% chance of being able to stop after decrypting a single byte, a 99.97% chance of stoping after decrypting 2 bytes, and a 99.9995% chance of stopping after 3 bytes.
也可以使用C或Ocaml或类似的东西。与进行加密相比，您可能花费更多的时间进行字符串操作。或者，至少使用多重处理并启动所有内核...
Also, use C or Ocaml or something like that. You're probably spending MUCH more time doing string manipulation than you are doing cryption. Or, at least use multi-processing and spin up all your cores...
这篇关于用弱密钥强行强制DES的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
