| View previous topic :: View next topic |
| Author |
Message |
Admin
Joined: 09 Nov 2005
Posts: 7408
Location: Russia
|
 Posted: Wed May 03, 2006 7:14 pm Post subject: 'Циклический инкремент паролей' |
 |
|
Обсуждение статьи "Циклический инкремент паролей".
Автор: InsidePro. |
|
| Back to top |
|
 |
FreeMan
Joined: 13 May 2007
Posts: 4
Reputation: 0
|
| Posted: Sun May 13, 2007 6:08 pm Post subject: |
|
|
статья очень помогла. использовал предложенный алгоритм, только слегка модифицированный (для перебора пароля с 1ого символа aaa aab aac...).
реализовал так:
| Code: | proc Brute pHash,pPass,pAlpha,count
;Routine description:
; Brutes count passwords from pointed by pPass, using alphabet pointed by pAlpha.
;
;Arguments:
; pPass - Pointer to null-terminated first password string
; pHash - Pointer to null-terminated hash string to brute
; pAlpha - Pointer to null-terminated alphabet.
; count - the number of passwords to brute
;
;Return:
; eax = 0 if found
; eax = 1 if there is no such password
; pPass - result
;
locals
szPass db 50h dup (?)
table db 100h dup (?)
hash dd ?,?
endl
;
;Convert hash 2 2 dwords
;
lea eax,[hash]
stdcall ConvertHash,[pHash],eax;не интересна
;
;Fill tables with zeros
;
xor eax,eax
lea edi,[szPass]
mov ecx,150h/4
rep stosd
;
;Copy first pass 2 szPass
;
lea edi,[szPass+20h]
mov [pCurPass],edi
invoke lstrcpyn,edi,[pPass],2fh
;
;Goto end char
;
invoke lstrlen,edi
add edi,eax
dec edi
;
;Generate alphabet table
;
xor ecx,ecx
mov esi,[pAlpha]
lea ebx,[table]
@@:
lodsb
mov byte[ecx+ebx],al
test al,al
jz @f
movzx ecx,al
jmp @b
@@:
;
;Process passwords
;
lea esi,[hash]
@@:
;
;Check password's hash
;
stdcall Check__pass
test eax,eax
jz .ret
push edi
.L1:
movzx eax,byte[edi]
mov al,byte[ebx+eax]
test al,al
jz .L3
mov byte[edi],al
jmp .L5
.L3:
mov al,byte[ebx+eax]
mov byte[edi],al
dec edi
jmp .L1
.L5:
pop edi
dec [count]
jnz @b
xor eax,eax
inc eax
.ret:
ret
endp |
использовать так
| Code: | | stdcall Brute,hash,pass,аlpha,1000000000 |
Last edited by FreeMan on Mon May 14, 2007 8:59 pm; edited 1 time in total |
|
| Back to top |
|
|
Admin
Joined: 09 Nov 2005
Posts: 7408
Location: Russia
|
| Posted: Sun May 13, 2007 6:20 pm Post subject: |
|
|
Очень рад, что статья помогла.  |
|
| Back to top |
|
|
BEKAS
Joined: 21 Sep 2009
Posts: 2
Reputation: 0
|
| Posted: Sat Sep 26, 2009 5:40 pm Post subject: |
|
|
| А как можно задать ограничение для перебора (количество символов)? Если я знаю длину пароля( например 7 символов) в описанном алгоритме http://www.insidepro.com/doc/003r.shtml |
|
| Back to top |
|
|
Admin
Joined: 09 Nov 2005
Posts: 7408
Location: Russia
|
| Posted: Sun Sep 27, 2009 5:12 pm Post subject: |
|
|
| Как вариант - ввести новую переменную с текущей длиной паролей и проверять ее, когда инкремент переходит на соседний символ. |
|
| Back to top |
|
|
gorodon
Joined: 28 Aug 2009
Posts: 38
Reputation: 7
|
| Posted: Mon Sep 28, 2009 8:36 pm Post subject: |
|
|
Да, статья хорошая - если кол-во тактов процессора, затраченное на генерацию символов пароля, сопоставимо с количеством тактов, затраченных на получение хэша из этого пароля - то да, надо биться за каждый такт...
Но, я бы хотел поделиться с Вами своей идеей (речь об алгоритмах хэширования, типа md5) - как известно, хэш снимается с определееного количества байт, которые в нашем случае и составляют пароль.
Теперь представьте ситуацию (брутфорс):
1) был вычислен хэш пароля "АА" - он не подошел
2) через некоторое время брутфорса был вычислен хэш к паролю "ААА" - не подошел
3) потом был вычислен хэш к паролю "АААА" и т.д.
Т.е. первые байты паролей совпадают, а это значит, что если мы сохраним контент алгоритма хаширования на этапе 1, то для вычисления хеша на этапе 2 мы можем использовать контент пароля с этапа 1 "АА", досчитав хэш всего по одному последнему байту пароля "ААА" и т.д. - получается, что мы экономим в тактах процессора на самом алгоритме хэширования - не делаем повторно ту работу по вычислению хэша, которую мы уже проделали...
Эта идея хорошо реализуется с помощью рекурсивных алгоритмов.
Да, и насколько я понимаю, rainbow-таблицы сделаны именно по этому принципу (или я ошибаюсь?). |
|
| Back to top |
|
|
Admin
Joined: 09 Nov 2005
Posts: 7408
Location: Russia
|
| Posted: Mon Sep 28, 2009 8:54 pm Post subject: |
|
|
Несколько неверно.
| gorodon wrote: | | досчитав хэш всего по одному последнему байту пароля "ААА" и т.д. |
Именно в этом и ошибка - такое позволяет только один алгоритм (из всех тех, что есть в составе PasswordsPro, к примеру, или в EGB) - MySQL. Действительно, в нем можно "досчитать" хэш и это уже реализовано, в остальных - нельзя. |
|
| Back to top |
|
|
gorodon
Joined: 28 Aug 2009
Posts: 38
Reputation: 7
|
| Posted: Mon Sep 28, 2009 10:01 pm Post subject: |
|
|
Хм, не буду голословным - продолжим пример с md5:
/* Copyright (C) 1991-2, RSA Data Security, Inc. Created 1991. All
rights reserved.*/
/* MD5 context. */
typedef struct {
DWORD state[4]; /* state (ABCD) */
DWORD count[2]; /* number of bits, modulo 2^64 (lsb first) */
unsigned char buffer[64]; /* input buffer */
} MD5_CTX;
//
void MD5Init (MD5_CTX *);
void MD5Update (MD5_CTX *, PBYTE, UINT);
void MD5Final (unsigned char [16], MD5_CTX *);
MD5_CTX - это тот самый "контент"
Как видите, алгоритм реализован в 3 функциях MD5Init, MD5Update, MD5Final
Так вот, если для пароля "AA" выполнить MD5Init, MD5Update, MD5Final - на выходе MD5Final получим хэш для этого пароля. Теперь сохранипм данный контент MD5_CTX (save1).
Используем сохраненный контент save1 для получения пароля "AAA":
MD5Update (&save1,"A",1);//"AA"+"A"
MD5Final(...,&save1);
- на выходе получаем хэш с пароля "ААА".
Ну, у меня, во всяком случае, работает... :-) |
|
| Back to top |
|
|
Admin
Joined: 09 Nov 2005
Posts: 7408
Location: Russia
|
| Posted: Mon Sep 28, 2009 10:12 pm Post subject: |
|
|
| gorodon wrote: | | Ну, у меня, во всяком случае, работает... |
А скорость добавляет?
Может, я не совсем понял вопрос - согласен, что все "контекстовые" алгоритмы позволяют вместо однократного подсчета хэша от строки "AAAAA" (к примеру) 5 раз вычислить и суммировать контекст для "A". Я же имел ввиду прикладной смысл - "досчитать хэш", не теряя скорости - невозможно. Опять же - сколько места займет сохранение всех контекстов??
Идея понятна, нужно ее математическое обоснование - нужно просто рассчитать, что даст эта идея на конкретном диапазоне паролей. Пусть это будет алфавит a...z, а длина паролей - 1...7 символов. И все станет понятно... |
|
| Back to top |
|
|
gorodon
Joined: 28 Aug 2009
Posts: 38
Reputation: 7
|
| Posted: Tue Sep 29, 2009 12:32 am Post subject: |
|
|
| Admin wrote: | | gorodon wrote: | | Ну, у меня, во всяком случае, работает... :-) |
А скорость добавляет? :)
Может, я не совсем понял вопрос - согласен, что все "контекстовые" алгоритмы позволяют вместо однократного подсчета хэша от строки "AAAAA" (к примеру) 5 раз вычислить и суммировать контекст для "A". Я же имел ввиду прикладной смысл - "досчитать хэш", не теряя скорости - невозможно. Опять же - сколько места займет сохранение всех контекстов??
Идея понятна, нужно ее математическое обоснование - нужно просто рассчитать, что даст эта идея на конкретном диапазоне паролей. Пусть это будет алфавит a...z, а длина паролей - 1...7 символов. И все станет понятно... |
>Опять же - сколько места займет сохранение всех контекстов??
При реализации итерационным алгоритмом количество контекстов, одновременно находящихся в памяти будет равно количеству символов в пароле (+ 1 или 2).
Пример от 1 до 4 символов:
Первая рекурсия до ААА:
А-АА-ААА-АААА
-АААВ
....
Вторая рекурсия до ААВ:
-ААВ-ААВА
-ААВВ
.....
>А скорость добавляет? :)
Провел я эксперименты. Исходные данные:
strcpy(strAlphavit,"ABCDEFJHIJKLMNOPQRSTUVWXYZ0123456789");
Password = "AD9OL1K";//7 символов, как вы и просили
Прогнал 2 алгоритма - оба рекурсивные (формирование самого пароля одинаковое), отличаются только передачей контекста на следующий уровень рекурсии.
Т.е. Алгоритм 1 считает хэш полностью по всему паролю
Алгоритм 2 досчитывает хэш пароля по полученному контексту с вышележащего уровня рекурсии.
Результаты:
Алгоритм 1: 1,593-1,595 Мп/с
Алгоритм 2: 1,667-1,670 Мп/с
Как видите, пиррост скорости ~4%
Еще раз оговорюсь - мои алгоритмы не заточены на скорость, возможно Ваши алгоритмы заточены так, что "досчитывать" хэш невозможно или не рационально (накладные расходы на копиравание контекста равны или больше расчету хэша заново). |
|
| Back to top |
|
|
Admin
Joined: 09 Nov 2005
Posts: 7408
Location: Russia
|
| Posted: Tue Sep 29, 2009 5:57 pm Post subject: |
|
|
4% - это хороший прирост.
При скорости 5 млн. п/с для MD5 это даст дополнительно 200 тысяч п/с, но у меня еще возник вопрос.
У MySQL (про который я уже упоминал) хэширование идет посимвольно, да еще и с накоплением результатов от каждого символа, что и позволяет предвычислять часть хэша заранее, но в том же MD5 хэширование паролей идет DWORD'ами (т.е. по 4 символа за раз), поэтому по тактам CPU абсолютно без разницы - хэшировать пароль 'A', или 'AA', или 'AAA', так откуда же появляется увеличение скорости?? Может, тут сам компилятор что-то наоптимизировал? |
|
| Back to top |
|
|
gorodon
Joined: 28 Aug 2009
Posts: 38
Reputation: 7
|
| Posted: Wed Sep 30, 2009 12:45 pm Post subject: |
|
|
| Admin wrote: | 4% - это хороший прирост.
При скорости 5 млн. п/с для MD5 это даст дополнительно 200 тысяч п/с, но у меня еще возник вопрос.
У MySQL (про который я уже упоминал) хэширование идет посимвольно, да еще и с накоплением результатов от каждого символа, что и позволяет предвычислять часть хэша заранее, но в том же MD5 хэширование паролей идет DWORD'ами (т.е. по 4 символа за раз), поэтому по тактам CPU абсолютно без разницы - хэшировать пароль 'A', или 'AA', или 'AAA', так откуда же появляется увеличение скорости?? Может, тут сам компилятор что-то наоптимизировал? |
Да, вы правы. Т.к. я использовал неоптимизированные по скорости алгоритмы, то "выигрыш" у меня получается только из-за того, что не выполняются предварительные функции MD5Init, MD5Update(часть), в которых происходит вообщем-то только ПОДГОТОВКА контекста к хэшированию. А само хэширование происходит в MD5Final, а эта функция вызывается на каждой итерации... А само хэширование, как я понимаю, происходит над БЛОКОМ в 64 байта - т.е. если длина пароля менее 64 байт (а это вообщем-то 99,999999%), то выигрыш по хэшированию получить не удасться. |
|
| Back to top |
|
|
gorodon
Joined: 28 Aug 2009
Posts: 38
Reputation: 7
|
| Posted: Tue Oct 06, 2009 12:10 am Post subject: |
|
|
| 2Admin: Вы, кстати, для ускорения работы алгоритмов хэширования используете команды MMX-расширения и т.п.? |
|
| Back to top |
|
|
Admin
Joined: 09 Nov 2005
Posts: 7408
Location: Russia
|
| Posted: Tue Oct 06, 2009 4:53 pm Post subject: |
|
|
Если это приводит к ускорению хэширования, то - да, применяю.
Ассемблерный MMX-код уже есть в некоторых моих модулях, а в некоторых - перевод на MMX/SSE пока только в планах... |
|
| Back to top |
|
|
passcape
Joined: 09 Dec 2005
Posts: 39
Reputation: 7
|
| Posted: Fri Dec 04, 2009 2:54 pm Post subject: |
|
|
Похоже, для инкремента NTLM паролей подойдет только индексный метод.
Хотя, если все символы укладываются в ASCII диапазон (1-127), то можно по-прежнему воспользоваться циклическим инкрементом, предложенным автором. |
|
| Back to top |
|
|
|
