469
-format:NAME force ciphertext format NAME (DES/BSDI/MD5/BF/AFS/LM)
-savemem:LEVEL enable memory saving, at LEVEL 1..3
reader@hacking:
/booksrc $ sudo tail -3 /etc/shadow matrix:$1$zCcRXVsm$GdpHxqC9epMrdQcayUx0//:13763:0:99999:7:::
jose:$1$pRS4.I8m$Zy5of8AtD800SeMgm.2Yg.:13786:0:99999:7:::
reader:U6aMy0wojraho:13764:0:99999:7:::
reader@hacking:
/booksrc $ sudo john /etc/shadow
Loaded 2 passwords with 2 different salts (FreeBSD MD5 [32/32])
guesses: 0 time: 0:00:00:01 0% (2) c/s: 5522 trying: koko guesses: 0 time: 0:00:00:03 6% (2) c/s: 5489 trying: exports guesses: 0 time: 0:00:00:05 10% (2) c/s: 5561 trying: catcat guesses: 0 time: 0:00:00:09 20% (2) c/s: 5514 trying: dilbert!
guesses: 0 time: 0:00:00:10 22% (2) c/s: 5513 trying: redrum3
testing7 (jose)
guesses: 1 time: 0:00:00:14 44% (2) c/s: 5539 trying: KnightKnight guesses: 1 time: 0:00:00:17 59% (2) c/s: 5572 trying: Gofish!
Session aborted
Этот листинг показывает, что у пользователя jose пароль testing7.
0x763 Справочная хеш-таблица
Еще одна интересная идея для взлома паролей заключается в создании гигантской справочной таблицы хешей. Если заранее вычислить хеш- значения для всех возможных паролей и поместить их в какую-нибудь структуру данных, позволяющую вести поиск, то любой пароль можно будет взломать в течение того времени, которое требуется для выпол- нения поиска. В случае бинарного поиска оно составит около O(log
2
N), где N – число различных элементов. Для восьмисимвольных паролей
N равно 95 8
, что приводит к оценке O(8 log
2 95) – достаточно быстро.
Однако справочная таблица такого размера заняла бы порядка сотни тысяч терабайт памяти. Кроме того, в алгоритме хеширования паро- лей была учтена возможность такой атаки, и для противодействия ей введена привязка (salt). Поскольку пароли будут давать разные значе- ния хеша в зависимости от привязки, для каждого значения salt при- дется построить отдельную справочную таблицу. В основанной на DES функции crypt() есть 4096 возможных значений salt, в результате чего таблица хешей даже для коротких четырехсимвольных паролей не- реализуема. Для одной справочной таблицы хешей четырехсимволь- ных паролей при фиксированной привязке требуется около гигабайта памяти, но из-за salt у каждого пароля оказывается 4096 возможных значений хеша, а потому требуется 4096 таблиц. В результате объем необходимой памяти возрастает до 4,6 терабайт, что делает такую ата- ку малопривлекательной.
4700x700 Криптология
0x764 Матрица вероятностей паролейПри любых вычислениях мы сталкиваемся с компромиссом между вы- числительной мощностью и объемом памяти. Он проявляется в эле- ментарных задачах вычислительной техники и в повседневной жизни.
В файлах MP3 применяется сжатие, что позволяет записать высокока- чественный звук в относительно небольшом объеме памяти, но это до- стигается ценой роста необходимых вычислительных ресурсов. В кар- манных калькуляторах этот компромисс «развернут» в обратном на- правлении: функции вроде синуса и косинуса хранятся в виде таблиц, что позволяет избежать интенсивных вычислений.
Этот компромисс действует и в криптографии. В атаках, основанных на компромиссе между временем и памятью, вероятно, наиболее эф- фективны методы Хеллмана, но здесь приведен другой код, который проще понять. Общий принцип в любом случае тот же: попытаться найти баланс между вычислительной мощностью и объемом памяти, чтобы достаточно быстро выполнить полный перебор ключей, обхо- дясь приемлемым объемом памяти. К сожалению, проблема увеличе- ния объема памяти из-за salt все равно сохраняется. Поскольку раз- ных значений salt для паролей, обрабатываемых функцией crypt(), всего 4096, надо постараться уменьшить объем необходимой в этом ме- тоде памяти настолько, чтобы и с увеличением в 4096 раз он оставался в разумных пределах.
В данном методе применяется своего рода сжатие с потерей информа- ции.
Вместо точного поиска по таблице, для каждого значения хеша возвращается несколько тысяч возможных открытых паролей. Эти значения можно быстро проверить и найти настоящий пароль, при этом сжатие с потерей информации позволяет существенно сократить необходимый размер памяти. В приведенном ниже коде участвует ключевое пространство всех четырехсимвольных паролей (с фиксиро- ванным salt). Необходимый объем памяти уменьшен на 88% по срав- нению со справочной таблицей хешей (для одного salt), а простран- ство ключей, проверяемое полным перебором, уменьшено примерно в 1018 раз. Если выполнять 10 000 проверок в секунду, то этим мето- дом можно взломать пароль из четырех символов (для фиксированного значения salt) меньше чем за 8 секунд, что существенно меньше, чем
2 часа, необходимые для полного перебора всех ключей.
В этом методе строится трехмерная двоичная матрица, связываю- щая части значений хешей с частями значений открытого текста. По оси
X – обычный текст, разделенный на две пары: первые два симво- ла и вторые два символа. Все их возможные значения перенумерованы в виде двоичного вектора длиной 95 2
, или 9025 бит (около 1129 байт).
По оси
Y – шифрованный текст, разбитый на четыре трехсимвольных участка. Они также нумеруются по столбцам, но из третьего симво- ла берутся только четыре бита. Таким образом, столбцов будет 64 2
×
4,
0x760 Взлом паролей
471или 16 384. Ось
Z нужна, чтобы хранить восемь двумерных матриц, по четыре для каждой пары обычного текста.
Основная идея состоит в том, что обычный текст разбивается на две пары символов, которые пронумерованы. Для каждого обычного тек- ста с помощью хеш-функции
вычисляется шифрованный текст, по ко- торому определяется соответствующий столбец матрицы. После это- го устанавливается бит на пересечении со строкой матрицы, соответ- ствующей обычному тексту. Поскольку значения шифрованного тек- ста урезаются, неизбежно возникнут коллизии.
Обычный текстХешtest je
HEAX1m66RV.
!J)h je
HEA38vqlkkQ
".F+
je
HEA1Tbde5FE
"8,J
je
HEAnX8kQK3I
В данном случае в столбце
HEA должны быть установлены биты, со- ответствующие парам обычного текста te, !J, “. и “8, когда эти пары обычного текста/хеша будут добавляться в матрицу.
Пусть матрица заполнена. Тогда, если нам требуется взломать хеш jeHEA38vqlkkQ
, смотрим в столбец
HEA матрицы и получаем из него зна- чения te, !J, “. и “8 для первых двух символов открытого текста. Для первых двух символов таких матриц четыре – для подстрок шифрован- ного текста из символов со второго по четвертый, с четвертого по ше- стой, с шестого по восьмой и с восьмого по десятый – и в каждой из матриц свой вектор возможных значений первых двух символов от- крытого текста. Извлекаем эти векторы и применяем к ним поразряд- ное И. В результате установленными останутся только биты, соответ-
ствующие парам обычного текста, входящим в число возможных для каждой подстроки шифрованного текста. Аналогично обращаемся с четырьмя матрицами, соответствующими последним двум символам обычного текста.
Размер матриц был установлен на основании принципа Дирихле. Этот простой принцип утверждает, что если
k + 1 объектов разложить по
k ящикам, то хотя бы в одном из ящиков окажется не менее двух объ- ектов. Поэтому лучшие результаты будут получены, если в каждом векторе окажется чуть меньше половины единиц. Поскольку в матри- цах будет размещено 95 4
, или 81 450 625, элементов, для достижения
50-процентного насыщения требуется примерно вдвое больше ящиков.
Так как каждый вектор имеет длину 9025, столбцов должно быть при- мерно (95 4
× 2) / 9025, то есть примерно 18 000. Если использовать для столбцов трехсимвольные подстроки шифрованного текста, то первые два символа и четыре бита третьего символа дадут 64 2
× 4, или около
4720x700 Криптология
16 000 столбцов, (символы шифрованного текста могут принимать
64 различных значения). Это довольно близко к требуемому, потому что, если бит добавляется дважды, перекрытие игнорируется. На практике каждый вектор оказывается заполненным единицами примерно на 42%.
Для каждого шифрованного текста выбираются четыре вектора, и ве- роятность того, что в заданной позиции значение 1
окажется во всех четырех векторах, равна примерно 0,42 4
, или 3,11%. Это означает, что
9025 возможных комбинаций первых двух символов сокращаются на
97% – до 280 вариантов. То же справедливо и для последних двух сим- волов, и в итоге получается около 280 2
, или 78 400, вариантов обычно- го текста. Если осуществлять 10 000 проверок в секунду, это сокращен- ное ключевое пространство будет проверено меньше чем за 8 секунд.
Конечно, есть и недостатки. Во-первых, изначальное создание матри- цы требует не меньше времени, чем занял бы простой полный перебор, хотя это единовременные затраты. Кроме того, если учитывать значе- ния salt, то такая атака делается невозможной, несмотря на достигну- тое сокращение объема необходимой памяти.
Следующие две распечатки демонстрируют код, который строит ма- трицу вероятностей паролей (Password Probability Matrix, PPM) и взламывает пароли с ее помощью. Первый листинг содержит код, ге- нерирующий матрицу для взлома всех четырехсимвольных паролей со значением salt, равным je. Код из второго листинга осуществляет фак- тический взлом паролей.
ppm_gen.c/*********************************************************\
* Матрица вероятностей паролей * Файл: ppm_gen.c *
***********************************************************
* *
* Автор: Jon Erickson
*
* Организация: Phiral Research Laboratories *
* *
* Это программа-генератор для проверки идеи МВП. *
* Она создает файл 4char.ppm с данными по всем допустимым *
* 4-символьным паролям с привязкой ‘je’. С помощью этого *
* файла и соответствующей программы ppm_crack.c *
* можно быстро вскрывать пароли из этого пространства. *
* *
\*********************************************************/
#define _XOPEN_SOURCE
#include
#include
#include
#define HEIGHT 16384
0x760 Взлом паролей
473
#define WIDTH 1129
#define DEPTH 8
#define SIZE HEIGHT * WIDTH * DEPTH
/* Отобразить 1 байт хеша в порядковое число. */
int enum_hashbyte(char a) {
int i, j;
i = (int)a;
if((i >= 46) && (i <= 57))
j = i - 46;
else if ((i >= 65) && (i <= 90))
j = i - 53;
else if ((i >= 97) && (i <= 122))
j = i - 59;
return j;
}
/* Отобразить 3 байта хеша в порядковое число. */
int enum_hashtriplet(char a, char b, char c) {
return (((enum_hashbyte(c)%4)*4096)+(enum_hashbyte(a)*64)+enum_
hashbyte(b));
}
/* Вывести сообщение и завершить работу. */
void barf(char *message, char *extra) {
printf(message, extra);
exit(1);
}
/* Создать файл 4–char.ppm всех 4-символьных паролей (с привязкой je). */
int main() {
char plain[5];
char *code, *data;
int i, j, k, l;
unsigned int charval, val;
FILE *handle;
if (!(handle = fopen(“4char.ppm”, “w”)))
barf(“Error: Couldn’t open file ‘4char.ppm’ for writing.\n”, NULL);
data = (char *) malloc(SIZE);
if (!(data))
barf(“Error: Couldn’t allocate memory.\n”, NULL);
for(i=32; i<127; i++) {
for(j=32; j<127; j++) {
printf(“Adding %c%c** to 4char.ppm..\n”, i, j);
for(k=32; k<127; k++) {
for(l=32; l<127; l++) {
plain[0] = (char)i; // Построить все plain[1] = (char)j; // возможные 4-байтные plain[2] = (char)k; // пароли.
474
0x700 Криптология plain[3] = (char)l;
plain[4] = ‘\0’;
code = crypt((const char *)plain, (const char *)”je”);
// Вычислить хеш.
/* Сохранить статистические данные
/* о соответствиях без потерь.
*/
val = enum_hashtriplet(code[2], code[3], code[4]);
// Сохранить сведения о байтах 2-4.
charval = (i-32)*95 + (j-32);
// Первые 2 байта обычного текста data[(val*WIDTH)+(charval/8)] |= (1<<(charval%8));
val += (HEIGHT * 4);
charval = (k-32)*95 + (l-32); // Последние 2 байта
// обычного текста data[(val*WIDTH)+(charval/8)] |= (1<<(charval%8));
val = HEIGHT + enum_hashtriplet(code[4], code[5], code[6]);
// Байты 4-6
charval = (i-32)*95 + (j-32); // Первые 2 байта
// обычного текста data[(val*WIDTH)+(charval/8)] |= (1<<(charval%8));
val += (HEIGHT * 4);
charval = (k-32)*95 + (l-32); // Последние 2 байта
// обычного текста data[(val*WIDTH)+(charval/8)] |= (1<<(charval%8));
val = (2 * HEIGHT) + enum_hashtriplet(code[6], code[7], code[8]); // Байты 6-8
charval = (i-32)*95 + (j-32); // Первые 2 байта
// обычного текста data[(val*WIDTH)+(charval/8)] |= (1<<(charval%8));
val += (HEIGHT * 4);
charval = (k-32)*95 + (l-32); // Последние 2 байта
// обычного текста data[(val*WIDTH)+(charval/8)] |= (1<<(charval%8));
val = (3 * HEIGHT) + enum_hashtriplet(code[8], code[9], code[10]); // Байты 8-10
charval = (i-32)*95 + (j-32); // Первые 2 байта
// обычного текста data[(val*WIDTH)+(charval/8)] |= (1<<(charval%8));
val += (HEIGHT * 4);
charval = (k-32)*95 + (l-32); // Последние 2 байта
// обычного текста data[(val*WIDTH)+(charval/8)] |= (1<<(charval%8));
}
}
}
0x760 Взлом паролей
475 }
printf(“finished.. saving..\n”);
fwrite(data, SIZE, 1, handle);
free(data);
fclose(handle);
}
Первый фрагмент кода (
ppm_gen.c) может сгенерировать
матрицу для взлома четырехсимвольных паролей, как показано ниже. Опция -O3 компилятора GCC указывает на необходимость компиляции с оптими- зацией по скорости.
reader@hacking:/booksrc $ gcc -O3 -o ppm_gen ppm_gen.c -lcrypt reader@hacking:/booksrc $ ./ppm_gen
Adding ** to 4char.ppm..
Adding !** to 4char.ppm..
Adding “** to 4char.ppm..
.:[ вывод сокращен ]:.
Adding |** to 4char.ppm..
Adding }** to 4char.ppm..
Adding ** to 4char.ppm..
finished.. saving..
@hacking: $ ls -lh 4char.ppm
-rw-r--r-- 1 142M 2007-09-30 13:56 4char.ppm reader@hacking:/booksrc $
Файл
4char.ppm размером 142 Мбайт содержит неточные связи между обычным текстом и хешем для всех четырехсимвольных паролей. Эти данные можно использовать в другой программе, чтобы быстро взла- мывать четырехсимвольные пароли, не поддающиеся атаке со слова- рем.
ppm_crack.c/*********************************************************\
* Матрица вероятностей паролей * Файл: ppm_crack.c *
***********************************************************
* *
* Автор: Jon Erickson
*
* Организация: Phiral Research Laboratories *
* *
* Это программа-взломщик для проверки идеи МВП. *
* Она использует готовый файл 4char.ppm данных по всем *
* допустимым 4-символьным паролям с привязкой ‘je’. Такой *
* файл можно создать с помощью программы ppm_gen.c. *
* *
\*********************************************************/
#define _XOPEN_SOURCE
#include
476
0x700 Криптология
#include
#include
#define HEIGHT 16384
#define WIDTH 1129
#define DEPTH 8
#define SIZE HEIGHT * WIDTH * DEPTH
#define DCM HEIGHT * WIDTH
/* Отобразить 1 байт хеша в порядковое число. */
int enum_hashbyte(char a) {
int i, j;
i = (int)a;
if((i >= 46) && (i <= 57))
j = i - 46;
else if ((i >= 65) && (i <= 90))
j = i - 53;
else if ((i >= 97) && (i <= 122))
j = i - 59;
return j;
}
/* Отобразить 3 байта хеша в порядковое число. */
int enum_hashtriplet(char a, char b, char c) {
return (((enum_hashbyte(c)%4)*4096)+(enum_hashbyte(a)*64)+ enum_hashbyte(b));
}
/* Объединить два вектора. */
void merge(char *vector1, char *vector2) {
int i;
for(i=0; i < WIDTH; i++)
vector1[i] &= vector2[i];
}
/* Возвращает разряд вектора по заданному индексу*/
int get_vector_bit(char *vector, int index) {
return ((vector[(index/8)]&(1<<(index%8)))>>(index%8));
}
/* Подсчитывает количество пар (обычный текст) в заданном векторе */
int count_vector_bits(char *vector) {
int i, count=0;
for(i=0; i < 9025; i++)
count += get_vector_bit(vector, i);
return count;
}
/* Выводит пары (обычный текст), соответствующие всем установленным битам вектора. */
void print_vector(char *vector) {
0x760 Взлом паролей
477
int i, a, b, val;
for(i=0; i < 9025; i++) {
if(get_vector_bit(vector, i) == 1) { // Если бит установлен,
a = i / 95; // вычислить b = i - (a * 95); // пару printf(“%c%c “,a+32, b+32); // и напечатать ее.
}
}
printf(“\n”);
}
/* Вывести сообщение и завершить работу. */
void barf(char *message, char *extra) {
printf(message, extra);
exit(1);
}
/* Взлом 4-символьного пароля с помощью готового файла 4char.ppm. */
int main(int argc, char *argv[]) {
char *pass, plain[5];
unsigned char bin_vector1[WIDTH], bin_vector2[WIDTH], temp_vector[WIDTH];
char prob_vector1[2][9025];
char prob_vector2[2][9025];
int a, b, i, j, len, pv1_len=0, pv2_len=0;
FILE *fd;
if(argc < 1)
barf(“Usage: %s
(will use the file 4char.ppm)\n”, argv[0]);
if(!(fd = fopen(“4char.ppm”, “r”)))
barf(“Fatal: Couldn’t open PPM file for reading.\n”, NULL);
pass = argv[1]; // Первый аргумент - хеш пароля printf(“Filtering possible plaintext bytes for the first two characters:\n”);
fseek(fd,(DCM*0)+enum_hashtriplet(pass[2], pass[3], pass[4])*WIDTH,
SEEK_SET);
fread(bin_vector1, WIDTH, 1, fd); // Прочитать вектор,
// связывающий байты 2-4 хеша.
len = count_vector_bits(bin_vector1);
printf(“only 1 vector of 4:\t%d plaintext pairs, with %0.2f%% saturation\n”, len, len*100.0/9025.0);
fseek(fd,(DCM*1)+enum_hashtriplet(pass[4], pass[5], pass[6])*WIDTH,
SEEK_SET);
fread(temp_vector, WIDTH, 1, fd); // Прочитать вектор,
// связывающий байты 4-6 хеша.
478
0x700 Криптология merge(bin_vector1, temp_vector); // Объединить его с первым вектором.
len = count_vector_bits(bin_vector1);
printf(“vectors 1 AND 2 merged:\t%d plaintext pairs, with %0.2f%% saturation\n”, len, len*100.0/9025.0);
fseek(fd,(DCM*2)+enum_hashtriplet(pass[6], pass[7], pass[8])*WIDTH,
SEEK_SET);
fread(temp_vector, WIDTH, 1, fd); // Прочитать вектор,
// связывающий байты 6-8 хеша.
merge(bin_vector1, temp_vector); // Объединить его
// с первыми двумя векторами.
len = count_vector_bits(bin_vector1);
printf(“first 3 vectors merged:\t%d plaintext pairs, with %0.2f%% saturation\n”, len, len*100.0/9025.0);
fseek(fd,(DCM*3)+enum_hashtriplet(pass[8], pass[9],pass[10])*WIDTH,
SEEK_SET);
fread(temp_vector, WIDTH, 1, fd); // Прочитать вектор,
// связывающий байты 8-10 хеша.
merge(bin_vector1, temp_vector); // Объединить его с остальными векторами.
len = count_vector_bits(bin_vector1);
printf(“all 4 vectors merged:\t%d plaintext pairs, with %0.2f%% saturation\n”, len, len*100.0/9025.0);
printf(“Possible plaintext pairs for the first two bytes:\n”);
print_vector(bin_vector1);
printf(“\nFiltering possible plaintext bytes for the last two characters:\n”);
fseek(fd,(DCM*4)+enum_hashtriplet(pass[2], pass[3], pass[4])*WIDTH,
SEEK_SET);
fread(bin_vector2, WIDTH, 1, fd); // Прочитать вектор,
// связывающий байты 2-4 хеша.
len = count_vector_bits(bin_vector2);
printf(“only 1 vector of 4:\t%d plaintext pairs, with %0.2f%% saturation\n”, len, len*100.0/9025.0);
fseek(fd,(DCM*5)+enum_hashtriplet(pass[4], pass[5], pass[6])*WIDTH,
SEEK_SET);
fread(temp_vector, WIDTH, 1, fd); // Прочитать вектор,
// связывающий байты 4-6 хеша.
merge(bin_vector2, temp_vector); // Объединить его с первым вектором.
len = count_vector_bits(bin_vector2);
printf(“vectors 1 AND 2 merged:\t%d plaintext pairs, with %0.2f%% saturation\n”, len, len*100.0/9025.0);
Скачать 2.5 Mb.