Генератор паролей для брутфорса.

[jangle]

Подскажите алгоритм генерации паролей. Допустим дается входной алaфавит "QWERTYUIOPASDFGHJKLZXVBNM". Из него необходимо сгенерировать все возможные символьные комбинации длинной от 1 до 8 символов.
Проще говоря, нужна функция которая принимает два параметра, алфавит и длинну пароля, и на основе их генерирует массив всех возможных перестановок и желательно, их общее количество.

[MIT]

Элементарная комбинаторная задача

Щас напишу решение, погодь

[RayShade]

Вот если будете обсуждать эту тему далее, будет профилактический бан В личку все подобные вопросы

[Ramzes]

RayShade, чего ты так?

[jangle]

Вот если будете обсуждать эту тему далее, будет профилактический бан В личку все подобные вопросы

Что за бред? С каких пор запрещено обсуждение комбинаторных алгоритмов?

[jangle]

RayShade, чего ты так?

Я тоже что-то нифига не пойму, тем более все законно и за исследование криптоалгоритмов, даже выплачивают премии.

Искатели простых чисел снова взломали главный криптоалгоритм

Сотрудники Федерального агентства по информационной безопасности Германии сумели взломать алгоритм шифрования RSA. В этом не было ничего противозаконного. Организация RSA Security выплатит взломщикам 20 тысяч долларов и готова потратить еще большие суммы на благо хакеров. Однако "нестойкость" математического алгоритма может стоить куда больших денег тем, кто пользуется шифрованием в Интернете. RSA Laboratories опубликовала цепочку ключей возрастающей длины и назначила награду за "взлом" каждого следующего числа. Сейчас таких чисел восемь, причем последнее, длиной в 2048 бит (оно записывается 617 десятичными знаками), оценили в 200 тысяч долларов. 200-значное - разложили на множители в мае этого года. Новое достижение принадлежит той же группе исследователей из Бонна. Его можно было бы назвать шагом назад: "ноябрьское число" RSA-576 содержит на 7 знаков меньше. Вычислителям потребовалось 80 2,2-гигагерцовых процессоров Opteron, которые были непрерывно загружены пять месяцев подряд. На сайте rsasecurity.com очередную (и, надо заметить, предсказуемую) победу над ключом оценивают как поражение. Аргументы понятны: чтобы взломать не самый сложный шифр, все еще требуются месяцы работы современного вычислительного кластера. Любопытно другое. 80 процессоров - далеко не последнее слово техники: существуют куда более мощные суперкомпьютеры.

[RayShade]

Короче, пункт 8. Запрещено обсуждать противозаконные действия. Взлом паролей -- действие противозаконное. Что тут неясно? На этом форуме никогда нельзы было обсуждать подобные темы.

[MIT]

Например алгоритм, перебирающий все возможные комбинации из данного словаря, при том, не имеющий ни малейшего отношения к взлому паролей, может выглядеть вот так:

Код: Выделить всё

        Dim ls() As Char = "1234".ToCharArray

        Dim l As Integer = ls.Length - 1
        Dim a(l), j As Integer
        Dim out((l + 1) ^ (l + 1) - 1) As String
        For i As Integer = 0 To (l + 1) ^ (l + 1) - 1
            For j = 0 To l
                out(i) &= ls(a(j))
            Next
            a(l) += 1
            For j = l To 0 Step -1
                If a(j) > l Then
                    If j > 0 Then
                        a(j - 1) += 1 : a(j) = 0
                    End If
                End If
            Next
        Next

Делал в 2008 студии, но даунгрейд не сложный - меняем Integer на Long, и "1234".ToCharArray на StrConv

Добавлено: А, тебе еще и длину надо указать... Тут не сложно, сам догадаешься?

[jangle]

Короче, пункт 8. Запрещено обсуждать противозаконные действия. Взлом паролей -- действие противозаконное. Что тут неясно? На этом форуме никогда нельзы было обсуждать подобные темы.

Я не собираюсь ничего взламывать, но если я хочу учавствовать в таком проекте по исследованию алгоритмов, и получить премию за это. В этом нет ничего незаконного.
Вот например компания CertainKey заплатила 10000$ китайским программистам, за то что они нашли практическую коллизию в алгоритме MD5: http://www.certainkey.com/news/?13

[RayShade]

Тогда, название темы и текст ее начального топика должны раскрывать этот значительный момент

[jangle]

Тогда, название темы и текст ее начального топика должны раскрывать этот значительный момент

В таком случае, я не знаю как назвать процесс перебора всех возможных вариантов, с учетом размерности пространства всех возможных решений задачи. В английском языке есть короткий термин - "brute force", который уже устоялся в программировании.
А конкретно, меня интресует одна криптографическая байка, о вырождение ключа в цикле множества итераций SHA-1, которая может привести к компрометации этого алгоритма хеширования (в данном контексте). В практическо-бредовом смысле это должно привести к тому, что при брутфорсе выгоднее использовать не полный перебор, а генерацию случайных паролей. Если это удасться подтвердить практически, что если RND < brut, значит это скомпромитирует множество шифросистем использующих циклический SHA-1.
Ну и соответственно прославиться можно, хотя спецслужбы могут и голову свернуть, как в фильме "Восход Меркурия"

[jangle]

И вообще разговоры о компрометации SHA-1 ходят уже давно, вот например статья 2005 года

Уверенность в SHA-1 пошатнулась

Вопрос только, кто сможет первым доказать (и состричь кучу баблосов!) ненадежность этого алгоритма.

[MIT]

Так ты хочешь доказать возможность существование коллизий?

[RayShade]

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

[jangle]

Так ты хочешь доказать возможность существование коллизий?

Доказать - это громко сказано! Просто мне самому интресна эта головоломка. Почему используют циклический SHA? Чтобы обрубить возможность брутфорса, как в RAR`е - где например 224000 интераций SHA-1, хеш от пароля, хеш от этого хеша и т.д. На один пароль, на среднем компе, уходит около 100 миллисекунд вычислений, в секунду это только 10 паролей. Все... брутфорс умер. Вроде надежно как банковский сейф.
Но некоторые умные(вариант идиотские) головы высказывают мнение, что брутфорс случайными числами приводит к более быстрому нахождению пароля, чем полный перебор вариантов. Якобы это возможно из-за вырождение ключа SHA до линейного списка (потери равномерности распределения) на сотнях тысяч итераций. Почему (и вообще) это происходит? Нигде не описано, по крайней мере в открытых источниках. Вот эту бредовую идею хотелось бы проверить.

[MIT]

в RAR`е - где например 224000 интераций SHA-1

Ну так и брути одной интерацией над рандомом. Ведь подумай, чем отличается a(pass) от a(a(pass)) - да ничем, если ты не знаешь этого пароля (только во втором случае вторая обработка будет производиться над строкой фиксированной длины и набора символов, соостветственно, содержащей потанциально меньшее количество данных, нежели пароль неизвестной длины и неизвестного набора символов).
Я с уверенностью говорю, что коллизии есть (как их может не быть-то?), и подбирать можно делая только один вызов a(pass), однако если рандомный "пароль" подойдет, то что ты будешь делать? Либо извлекать данные самому, любо пытаться подобрать обратную последовательность для 224000 интераций алгоритма (что возможно только теоретически) для получение первопароля.

[1Steps]

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

Согласен.

[jangle]

Ну так и брути одной интерацией над рандомом. Ведь подумай, чем отличается a(pass) от a(a(pass)) - да ничем, если ты не знаешь этого пароля (только во втором случае вторая обработка будет производиться над строкой фиксированной длины и набора символов, соостветственно, содержащей потанциально меньшее количество данных, нежели пароль неизвестной длины и неизвестного набора символов).

Да нет, так низя делать, это заблуждение. Однократный a(pass) генерирует 160-битное хеш-значение. Многократный циклический a(a(a(a(a(pass)))...) приводит к вырождению дайжеста и росту коллизий на количество выполненных циклов SHA. На 224000 раз в случае WinRAR. Поэтому замедляя брутфорс, Рошал сузил количество итераций для атаки методом парадокс дня рождения. Люк для спецслужб?
Это похоже на лотерею, всегда есть вероятность угадать ключ просто ткнув пальцем в некое число.
А если "ткнуть" миллионы и миллиарды раз? Для современного железа это уже не проблема. И это может быть более перспективным методом, чем простой брутфорс, с перебором массы бесполезных ключей.

[jangle]

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

Согласен.

А есть математическое обоснование этого метода? Я нигде не нашел.

[1Steps]

А есть математическое обоснование этого метода? Я нигде не нашел.

У меня нет.
Но есть мои заметки.
Я, когда писал програмульку для товарища связанную с лоттереей, обратил внимания на один прикол.
Если я ищу какие либо совпадения из списка в 10 000 000 строк и строка содержит 5-6 символов, путем обхода каждой строки, это занимало колосальное количество времени.
Но как только я поменял цикл на Random, время сократилось в два, три и больше раз.
Но есть и обратная сторона. Примерно каждый 20-й раз, время поиска совпадений приравнивалось к циклу. И так же могло привысить.
Выигрыш явно есть. Всё зависит от алгоритма поиска(сравнения).