Форум   Статьи   Новости   Файлы   Bugtraq   Сниффер   Друзья   О Клубе
  , 23:01   #1
Jedi Knight
 
Аватар для vladyxa13
 
Локация: Планета Земля
Регистрация: 03.04.2013
Сообщений: 1,120

Репутация: 227 / 4
По умолчанию Полный перебор. Честь 1. Теория.

Полный перебор. Теория.


Введение
Доброго времени суток уважаемый читатель! Сегодня я постараюсь помочь тебе разобраться в реализации алгоритма полного перебора.

Что такое полный перебор(brute force)?

Как гласит википедия
Цитата:
Полный перебор (или метод «грубой силы») — метод решения математических задач. Относится к классу методов поиска решения исчерпыванием всевозможных вариантов.

Подробней можно узнать из статьи: https://ru.wikipedia.org/wiki/Полный_перебор
Другими словами полный перебор это метод поиска варианта из всех возможных.

Начинаем перебирать пароли

И так, мы подошли непосредственно к самому перебору.

Обычно люди используют пароли длинной до 6-12 символов. Пароли до 6 символов являються неустойчивыми, а 7-8 относительно устойчивыми, 8-12 есть возможность подобрать.
Для примера возьмем пароль в 1 символ. Словарь это символы которые могли быть использованы при создании пароля, будет состоять из англисский заглавных и маленьких буков+цифры. На выходе мы получим
code:
ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz1234567890
code:
Длинна словаря: 26+26+10 = 62
Это значит, что вариантов пароля всего 62.

Что бы продолжить..
Ниже я буду использовать сокращенные записи:
LEN_PASS - длинна пароля
LIB.SIZE - длинна словаря символов из которого будет перебираться пароль
LIB - словарь(может состоять из букв и смволов)


Для примера, возьмем пароль длинной в 2 символа и длинной словаря в 3 символа, а символы для словаря
code:
АВС
Пример 1. Найдем все варианты исполузуя выше приведенные параметры
code:
LEN_PASS = 2
LIB.SIZE = 2
LIB = "12"
Перебирая все параметры получим:
code:
11
12
21
22
Аналогично используя буквы
code:
LEN_PASS = 2
LIB.SIZE = 2
LIB = "AB"
Выйдет
code:
AA
AB
BA
BB
Пример 2.Давайте попробуем 3 символа
code:
LEN_PASS = 2
LIB.SIZE = 3
LIB = "ABC"
На выходе:
code:
AA
AB
AC
BB
BA
BC
CA
CB
CC
Попробуйте сами придумать пароль длинной до 2-3 символов и словарь 2-3 символа. Распишите на листочке или в екселе все варианты.

Количество вариантов пароля при полном переборе

Теперь вы можете вывести формулу, изучив на практике примеры, максимального количества вариантов пароля
Цитата:
LIB.SIZE^LEN_PASS
Что бы узнать максимальное количество вариантов пароля нам нужно длинну словаря превзойти в степень на длинну пароля.

Вернемся назад к "Примеру 1".
Посчитаем вручную ко-ол вар., оно равно 4.
Теперь используя формулу.
code:
2^2 = 4
4 = 4 - значит все верно!

Возьмем "Пример 2".
Вручную посчитав вышло 9.
Формулой
code:
3^2 = 9
9 = 9 - все верно!

Использование перебора в серьезных масштабах

Теперь возмем пароль длинной 6 символов и словарь
code:
ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz1234567890абвгдеёжзийклмнопрстуфхцчшщъыьэюяАБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ
26*2+33*2+10 = 128

Вариантов на выходе(пспользуя форумул+калькулятор вышло) 4.398.046.511.104 варинтов пароля длинной в 6 символов. Солидная цифра в ≈4,5 милиарда вариантов.

Скорость перебора и его оптимизация
Википедия права

Но там учтены только варианты с алфавитом (a-z)+(1-0) = 36 символов, а унас 128!!!

Как же ускорить перебор?
1. Использовать GPU(простыми словами видеокарту).
2. Разбить задачу между компьютерами(ботнет, сеть подчиненных машин).
3. Использовать потоки.

Но обо всех этих решениях мы подробней поговорим на практике.

Советую к прочьтению:

Спасибо BlackH за помощь!
Если что, пишите в ЛС или прямо здесь в коментариях.
Если найдете ошибку или захотите поправить\предложить - пишите.

Спасибо за внимание, в следующий раз мы рассмотрим ПП уже на практике используя средства С++.

Ну а с вами был vladyxa13
и эта статья специально для HPC.name
__________________

Профессия тыже программист очень популярная!
Почини колонку, тыже программист. Достань кота с дерева тыже программист! ...

Никогда ее не забуду http://www.youtube.com/watch?v=OH15GOMvYUs [►], на ней вырос...

Последний раз редактировалось vladyxa13; 05.04.2015 в 10:56.
Пользователь вне форума    
Наши Спонсоры
  , 10:47   #2
Jedi Knight
 
Аватар для vladyxa13
 
Локация: Планета Земля
Регистрация: 03.04.2013
Сообщений: 1,120

Репутация: 227 / 4
По умолчанию

Статья написана чисто для собственного и развития. В ней я выложил все наработки, которые сделал в блоге. Некоторые аспекты перебора я и сам до сих пор не понимаю. В плане формулы максимальных значений вариантов, я неполностью уверен, ибо одни считают факториалом, я считаю степенью, в принципе, это вызвано неполным понимаем сути перебора.

В практичекской части я планирую ознакомить вас с потоками в С++ и как их можно использовать в нашей задачи перебора. Также мы рассмотрим его оптимизацию и на отладке посмотрим результаты, которые выдает отладчик, таким образом мы лучше поймем работу алгоритма. И еще, сам код взят из киберфорума, я его просто переписал на свой манер и модифицировал. Рассмотрим разные реализации перебора с других сайтов(васм например). Сравним скорость перебора при помощи CPU и GPU.

Буду рад любой критике.
Надо что-то писать ведь форум застыл один оффтоп активен......
И уже при написании практики я полностью проверю свою формулу.
__________________

Профессия тыже программист очень популярная!
Почини колонку, тыже программист. Достань кота с дерева тыже программист! ...

Никогда ее не забуду http://www.youtube.com/watch?v=OH15GOMvYUs [►], на ней вырос...

Последний раз редактировалось vladyxa13; 05.04.2015 в 10:54.
Пользователь вне форума    
  , 11:24   #3
Местный
 
Регистрация: 28.05.2013
Сообщений: 127

Репутация: 23 / 1
По умолчанию

Классная статья, помню читал нечто подобное.
ВК например пассы можно русскими буквами и спец символы @#$%&*-+()
это ещё 36+36+х(хз сколько этих символов)
__________________
Звоню голодающим, африканским детям и чявкаю в трубку.
Пользователь вне форума    
  , 16:32   #4
Jedi Knight
 
Аватар для vladyxa13
 
Локация: Планета Земля
Регистрация: 03.04.2013
Сообщений: 1,120

Репутация: 227 / 4
По умолчанию

popov, тогда выйдет
code:
ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz1234567890абвгдеёжзийклмнопрстуфхцчшщъыьэюяАБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ[email protected]#$%^&*()_+-=|\/?<>Її
128+24 = 152 символа в словаре
__________________

Профессия тыже программист очень популярная!
Почини колонку, тыже программист. Достань кота с дерева тыже программист! ...

Никогда ее не забуду http://www.youtube.com/watch?v=OH15GOMvYUs [►], на ней вырос...
Пользователь вне форума    
  , 14:21   #5
Продвинутый
 
Аватар для BlackH
 
Локация: underworld
Регистрация: 05.12.2011
Сообщений: 1,606

Репутация: 167 / 3
По умолчанию

Цитата:
Сообщение от vladyxa13 Посмотреть сообщение
Скорость перебора и его оптимизация
Википедия права

Но там учтены только варианты с алфавитом (a-z)+(1-0) = 36 символов, а унас 128!!!
Прибавьте к этому еще время потраченное на генерацию какого нибудь sha2))

PS
CPU курит в этом деле,по сравнению с гпу.
У меня проц брутит 80-85 мл.хешей\сек, ГПУ от 600 миллионов в сек(md5).

Pss
В целом молодец.Ждемс практик и кодов))
__________________
Вангую..
Пользователь вне форума    
  , 17:38   #6
Jedi Knight
 
Аватар для vladyxa13
 
Локация: Планета Земля
Регистрация: 03.04.2013
Сообщений: 1,120

Репутация: 227 / 4
По умолчанию

Доведение и обоснование формулы вычисление всех вариантов пароля

Доброго времени суток, уважаемый читатель! Это первое дополнение к статье выше. В этом дополнении я выведу доказательства верности формулы
code:
Длинна_словаря ^ Длинну_пароля = Количество вариантов пароля
И так начнем!

Вечерком, когда готовил жрать, я вывел на бумаге обоснование этой формулы.
Читая статью ниже вам потребуються знания из Множеств.

Во многих статьях по полному перебору, учитывая статью с васма и эту, все отталкиваеться от множест, а словарь являеться тем же множеством.

Перейдем к самому доведению....

Возьмем множество
code:
1,2,3
По свойству множества(1)добавление к множеству элементов, идентичных уже принадлежащим множеству, не меняет его, 2)любое сменение и перестановка элементов множеств не меняет его( это при перемещении слагаемых сума не меняеться)).
Количество элементов в нашем множестве равно 3
Что бы узнать все варианты перестановки в множестве нам нужно вычислить факториал(!) количества элементов множеств(у нас 3 елемента).
code:
!3 = 1*2*3 = 6
Вот все варианты перестановки
code:
1,2,3
1,3,2
2,1,3
2,3,1
3,1,2
3,2,3
Все это 3-ех символьный пароль при словаре "123" используя свойство множеств. На этом и основан метод переребора сравнением. О нем можно почитать здесь. Выходя из свойства множест описаном выше, мы не можем опредилить множество вида
code:
1,1,3
потому что оно будет сведено к виду
code:
1,3
Подберем пароль со словарем "12" и длинной 2 символа

Используя множества унас выйдет только такое
code:
1,2
2,1
А используя все варианты из этого словаря, то выйдет
code:
11
12
21
22
Тоесть второй метод более продуктивен, чем первый и выдает на этом уровне в 2 раза больше вариантов, чем первый.
Вариантов из первого выйдет
code:
!ко-ол элементов множеств
code:
!2 = 1*2 = 2
Два варианта, все верно, мы так и расписали в первом примере.

Вариантов во втором примере, уже используя формулу
code:
Длинна_словаря ^ Длинну_пароля = Количество вариантов пароля
code:
2^2 = 4
Ну и как видим 4 варианта, знач все верно и мы с вами молодци, как соленые огурцы.

Минутка отдыха мозга...нужно же отдыхать =)
ШУТЕЕЧКА
Мальчик пришел в магазин и говорит "Дайте мне кирпичик хлеба", а пока продавщица давала ему хлеб, он убежал.
(с)Егорка Д.


И так продолжим...
.емм возьмем пароль со словарем "123" и длинной 3 символа
По множествам эта задача решена выше просто ctrl+c ctrl+v и вааля
code:
!3 = 1*2*3 = 6
Вот все варианты перестановки
code:
1,2,3
1,3,2
2,1,3
2,3,1
3,1,2
3,2,3
Используя формулку мы сможем вычислить ко-ол макс. вариантов
code:
Длинна_словаря ^ Длинну_пароля = Количество вариантов пароля
code:
3^3 = 27
Так как вариантов 27 и мне лень их набирать вручную просто обрежу
code:
111
.....
....
...
333

Заключение

Ну вот и доказательства работоспособности формулы, теперь мы можем ее использовать в своих наработках. Думаю вы поняли разницу перестановки в вольном алфавите и множествах. Надеюсь это вам поможет!

Спасибо за то, что прочитали это дополнение))

С вами был я, владюха13!
__________________

Профессия тыже программист очень популярная!
Почини колонку, тыже программист. Достань кота с дерева тыже программист! ...

Никогда ее не забуду http://www.youtube.com/watch?v=OH15GOMvYUs [►], на ней вырос...

Последний раз редактировалось vladyxa13; 09.04.2015 в 17:04.
Пользователь вне форума    
  , 13:44   #7
Новичок
 
Регистрация: 14.12.2017
Сообщений: 16

Репутация: 0 / 0
По умолчанию

Под реальный сервис трудно подобрать
Помню те времена, когда люди к паролю добавляли 123 и он оказывался валидным
 
Пользователь вне форума    
 

Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
SQL injection полный FAQ deihack Сайты, Форумы, CMS 0 21.01.2012 12:16



Часовой пояс GMT +2
Powered by vBulletin® 3.x.x Copyright ©2000 - 2012, Jelsoft Enterprises Ltd.

Copyright © 2008 - 2013 «HPC» Реклама на сайте Правила Форума Пользовательское соглашение Работа на сайте
При копировании материалов ставьте ссылку на источник
Все материалы представлены только в ознакомительных целях, администрация за их использование ответственности не несет.