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

Для подбора паролей часто используется метод полного перебора всех вариантов, поэтому и советуют использовать как можно более длинные пароли. Чем больше символов, тем сложнее такой пароль будет подобрать. Обычно перебор паролей осуществляется в лексикографическом порядке, начиная с "аааааа", заканчивая "яяяяяя", если мы перебираем шестибуквенный пароль, состоящий, предположительно, из маленьких русских букв.
Пароль из 7 символов подобрать будет уже существенно сложнее, чем из 6. Википедия (http://ru.wikipedia.org/wiki/Брутфорс) приводит пример того, что для подбора пароля из 12 символов в определенных условиях нужно до полутора миллионов лет, в то время как пароль из 7 символов при таких же условиях будет раскрыт не более чем за 9 дней.
Лексикографический порядок перебора паролей не является оптимальным в этом случае. Он, наверное, является даже наихудшим вариантом, которым только стоит воспользоваться для подбора пароля, поскольку он не учитывает факт, что пароли создает человек, который придумывает их в соответствии со своим знанием языка. Человек использует в таких паролях одни буквы чаще других (например, “о” чаще “э”), и одни буквосочетания чаще других (так, "ка" и "ый" является куда более вероятными вариантами в пароле, чем "кк" и "ыэ"). Возникает желание перебирать более "правильные" пароли ранее, чем "неправильные". Так, пароль "нудиратор" хоть и представляет из себя выдуманное слово, которого, скорее всего, нет ни в одном словаре, однако он более вероятен, чем такой длинны "чфхпрцшсч".
Почему пароль "нудиратор" более прост для человека, чем "чфхпрцшсч"? Потому что он удовлетворяет представлению человека о том, что может быть словом в русском языке. На самом деле пароль "нудиратор" не так случаен, как хотелось бы пользователю и в этом его главная уязвимость. Если пароль придуман человеком, то он, скорее всего, поддается общей языковой логике образования слов и содержит в себе избыточную информацию.
Информация о языке общеизвестна и избыточна, поэтому реально пароли имеют меньшую сложность, чем хочется их обладателю. Как определить избыточность информации о языке в пароле? Избавляться от избыточной информации умеют алгоритмы сжатия данных. Выпишем несколько паролей и попробуем сжать их неким алгоритмом сжатия. Тот пароль, что сожмется сильнее других — более прост, чем другие и содержит меньше информации.
В качестве алгоритма архивации я предлагаю использовать модифицированный алгоритм Хаффмана. Классический алгоритм определяет частоту использования букв в слове и перекодирует слово использую для более частых букв меньше бит, чем для более редких. Но распределение букв в слове зависит не только от того, что это за буква, но и от ее позиции в слове и, гораздо больше, от предыдущих букв. Поэтому для сжатия нам будет важна не частота букв в тексте, а отдельно —

частоты первых букв в словах,

частоты вторых букв после буквы 'а',
частоты вторых букв после буквы 'б',
..
частоты вторых букв после буквы 'я'

частоты букв после букв 'аа',
частоты букв после букв 'аб',
..
частоты букв после букв 'яя',

В основном алгоритм будет повторять алгоритм сжатия Хаффмана, только в нем будет использоваться не одно общее дерево, а множество деревьев, которые будут выбираться в зависимости от предыдущих букв. В этих деревья хранится "информация о языке". Для их построения я выбрал "Войну и мир" Толстого.
Любое русское слово этот алгоритм может сжать в битовую последовательность. Эта битовая последовательность уже содержит гораздо меньше закономерностей, чем исходное слово, слабо поддается сжатию, ее мы будем называть чистой информацией о пароле. Если для хранения каждой буквы использовать 5 бит (32 буквы без 'ё'), то слово “нудиратор” занимает 5*9 = 45 бит, однако в сжатом виде он выглядит как “110010100101101010011111101110” — 30 бит вместо 46. Я был сильно удивлен, когда узнал, что мой 7ми символьный пароль ужимается с 35 до 19 бит и требует только 200 тысяч итераций для подбора, то есть всего несколько секунд. Если перед началом перебора сгенерировать слова в лексикографическом порядке, а затем сжать их по длине сжатой последовательности, можно перебирать слова уже в порядке их "естественности". Но я предлагаю еще
более простой вариант — создавать эти слова на лету от более простых к более сложным. Более простые имеют меньшую длину в сжатом виде, так давайте просто подавать на вход деархиватору все возможные последовательности нулей и единиц начиная с длинны 1, постепенно увеличивая длину.
так мы получим
1110000 все
1101000 нат
0101100 что
1011100 сво
0000110 был
...
00001100 было
01111100 это
10000010 гра
01100010 каза
...
111110101101 впеч
011001101101 кбо
010101101101 хоч
110101101101 нашн
101101101101 совы
000011101101 быка
...
001100000111110010 интер
000010000111110010 бойди
110010000111110010 никотра
001010000111110010 такотра
101010000111110010 сеи
011010000111110010 ковсел
111010000111110010 водного
...
101100101011100100110 спрядол
011100101011100100110 мотане
111100101011100100110 выратали
000010101011100100110 брядол
100010101011100100110 ееэлед
001110101011100100110 изворав
011110101011100100110 люденийс
000001101011100100110 улюдит
001001101011100100110 деталаз
111001101011100100110 вратали

В этой последовательности нет повторов и в ней рано или поздно встретится любое слово. Так, 541901334-ым номером будет сгенерировано "нудиратор", в то время как в лексикографеческом порядке его номер 16086012579313. Таким образом перебор потребует в 30 тысяч (более точно 29684) раз меньше итераций. При скорости 100000 паролей в секунду 9ти символьный пароль "нудиратор" будет подобран за 90 минут. Перебор в лексикографическом порядке при такой скорости займет более 5 лет. Один из проверенных мною 12 символьных паролей имел сжатую длину 33 бита, номер 4.5 миллиардный по списку, соответственно, для его нахождения при аналогичной скорости понадобится примерно 12 с половиной часов, а совсем не миллион лет.

Описание приложения
Приложение к статье находится по ссылке http://shutov.org.ru/bruteforcer.zip
dict/rus.txt – “Война и Мир” Л.Н. Толстого
dict/eng.txt — “Война и Мир” Л.Н. Толстого, перевод на английский язык
bruteforcer_eng.exe – программа, скомпилированная для английского языка
bruteforcer_rus.exe – программа, скомпилированная для русского языка
main.cpp – исходный текст программы
test.sln, test.vcproj – файлы проекта Microsoft Visual Studio 2003

bruteforcer_rus.exe и bruteforcer_eng.exe принимает 1 входной параметр. Если это число, то программа генерирует данное число слов в порядке “логичности” и пишет их в output. Если это слово, то сначала вычисляется его сжатая длина, а после запускается перебор и в итоге вычисляется порядковый номер этого слова, равный количеству итераций нужных для подбора этого пароля. Так как русская кодировка консоли не совпадает со стандартной Windows 1251, в русской версии программы вывод русских слов на экран происходит некорректно, поэтому выводить результат программы лучше не на экран, а в файл. Например:
bruteforcer_rus.exe нудиратор >file.txt

Здравствуйте, __kot2, Вы писали:

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

__>Для подбора паролей часто используется метод полного перебора всех вариантов, поэтому и советуют использовать как можно более длинные пароли. Чем больше символов, тем сложнее такой пароль будет подобрать. Обычно перебор паролей осуществляется в лексикографическом порядке, начиная с "аааааа", заканчивая "яяяяяя", если мы перебираем шестибуквенный пароль, состоящий, предположительно, из маленьких русских букв.

Обычно? John the Ripper перебирает не в таком порядке. И это всего лишь лучшая из открытых.

"ка" и "ый" является куда более вероятными вариантами в пароле, чем "кк" и "ыэ"). Возникает желание перебирать более "правильные" пароли ранее, чем "неправильные". Так, пароль "нудиратор" хоть и представляет из себя выдуманное слово, которого, скорее всего, нет ни в одном словаре, однако он более вероятен, чем такой длинны "чфхпрцшсч".
__>Почему пароль "нудиратор" более прост для человека, чем "чфхпрцшсч"? Потому что он удовлетворяет представлению человека о том, что может быть словом в русском языке. На самом деле пароль "нудиратор" не так случаен, как хотелось бы пользователю и в этом его главная уязвимость. Если пароль придуман человеком, то он, скорее всего, поддается общей языковой логике образования слов и содержит в себе избыточную информацию.

Как Ваша программа справится с паролем "Лес123"? А с паролем "{htyGjlIe,jq" ("ХренПодШубой" на английской раскладке)?

__>Любое русское слово этот алгоритм может сжать в битовую последовательность. Эта битовая последовательность уже содержит гораздо меньше закономерностей, чем исходное слово, слабо поддается сжатию, ее мы будем называть чистой информацией о пароле. Если для хранения каждой буквы использовать 5 бит (32 буквы без 'ё'), то слово “нудиратор” занимает 5*9 = 45 бит, однако в сжатом виде он выглядит как “110010100101101010011111101110” — 30 бит вместо 46.

А в таком случае "щщщщщщщщщ" должно занимать 46-47 бит вместо 45. Я прав?
Так как быть с цифрами, пунктуацией и прочими знаками?

__>Описание приложения

У меня создаётся упорное впечатление, что Вы изобретаете велосипед, не ознакомившись даже с самыми известными и старыми разработками в этой области.

Интересная идея, по некоторым словам перебор действительно сократится в 1000 раз, но по другим может и увеличиться, к примеру слово "цупурик" требует 52 бит, т.е. его нахождение будет ОЧЕНЬ долгим, в 10000 раз дольше чем полным перебором.

А что заценивать-то? Где идея?

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

Хотите сказать, вы первый до этого додумались, что-ли?

Да и сама мысль о том, что пароли подчиняются закономерностям естественного языка сомнительна.

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

А когда человек сам сочиняет пароль, он скорее будет подчиняться закономерностям расположения клавиш на клавиатуре. Или закономерностям человеческой психологии. Или вообще неизвестно каким закономерностям.

Тяжеловесные рассуждения про сжатие — это просто бессмысленное усложнение тривиальной идеи на пустом месте, зашумление мыслительного процесса.

Здравствуйте, MozgC, Вы писали:

MC>Интересная идея, по некоторым словам перебор действительно сократится в 1000 раз, но по другим может и увеличиться, к примеру слово "цупурик" требует 52 бит, т.е. его нахождение будет ОЧЕНЬ долгим, в 10000 раз дольше чем полным перебором.

Одноклассников ломать, для другого вряд ли (это ж надо — пароль из одного слова и без единой заглавной буквы).

Цупурик, говорите? Запомним:))

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

Алгоритм, конечно, не годится в таком виде для боевого применения, как минимум нужны цифры — генерация которых отдельный вопрос и большие буквы — тоже не сильно понятно, как это делать оптимально.
Но с паролями набранных русскими буквами в английской раскладке он легко справляется — просто в русском тексте надо заменить русские буквы на соот-ие им на клаве английские. Есть целый класс простых паролей, которые он тоже очень плохо обрабатывает, например qqqqq или qwerty — тут нужен другой алгоритм, например, учитывающий взаимоположений клавиш на клаве.

>У меня создаётся упорное впечатление, что Вы изобретаете велосипед, не ознакомившись даже с самыми известными и старыми разработками в этой области.
идея у меня в голове с тех пор, как я увидел файл со списком планет игрушки VGA Planets их не так-то просто найти эти разработки. почему то, например, мой знакомый, недавно занимавшийся брутфорсом, вообще о них ничего не слышал. то есть скорее всего они либо приватные, либо нерабочие. можно ссылки на них? Я, соб-но поэтому и запостил сюда, ожидая, что тут есть люди, которые шарят в этой теме.

Здравствуйте, __kot2, Вы писали:

>>У меня создаётся упорное впечатление, что Вы изобретаете велосипед, не ознакомившись даже с самыми известными и старыми разработками в этой области.
__>идея у меня в голове с тех пор, как я увидел файл со списком планет игрушки VGA Planets :) их не так-то просто найти эти разработки. почему то, например, мой знакомый, недавно занимавшийся брутфорсом, вообще о них ничего не слышал. то есть скорее всего они либо приватные, либо нерабочие. можно ссылки на них? Я, соб-но поэтому и запостил сюда, ожидая, что тут есть люди, которые шарят в этой теме.

Я ссылку на John the Ripper (исходники доступны) кидал в первом комментарии, в Unix мире это вообще "the first".

Здравствуйте, netch80, Вы писали:
N>Обычно? John the Ripper перебирает не в таком порядке. И это всего лишь лучшая из открытых.
посмотрел его. у него есть похожий метод — incremental, он тоже использует информацию о частоте троек букв, но поступает неоптимально, я тоже сначала так делал — он фиксирует длинну слова и потом перебирает его, так у него соотв-но все (n+1)ти символьные пароли сложнее n-символьных, а это не так.

Здравствуйте, __kot2, Вы писали:
__>Здравствуйте, netch80, Вы писали:
N>>Обычно? John the Ripper перебирает не в таком порядке. И это всего лишь лучшая из открытых.
он, кстати, в тройках учитывает, что одни чаще других, но не учитывает, насколько, использует только порядок

Здравствуйте, __kot2, Вы писали:

__>Здравствуйте, netch80, Вы писали:
N>>Обычно? John the Ripper перебирает не в таком порядке. И это всего лишь лучшая из открытых.
__>посмотрел его. у него есть похожий метод — incremental, он тоже использует информацию о частоте троек букв, но поступает неоптимально, я тоже сначала так делал — он фиксирует длинну слова и потом перебирает его, так у него соотв-но все (n+1)ти символьные пароли сложнее n-символьных, а это не так.

Длину слова можно задать, если знать её. Но опять-таки Вы залагаетесь на то, что пароль будет одним словом или хотя бы только буквами. Это, мягко говоря, не так.

Если Вы сможете расширить свою идею на произвольные комбинации с цифрами, знаками, пробелами и прочим что входит в реальные пароли — с нёе будет какой-то толк. Если нет — она бесполезна.

Здравствуйте, netch80, Вы писали:
N>Если Вы сможете расширить свою идею на произвольные комбинации с цифрами, знаками, пробелами и прочим что входит в реальные пароли — с нёе будет какой-то толк. Если нет — она бесполезна.
тут нет никакой принципиальной сложности. Это все муторные доделки, не зависящие от сути. В двух словах — надо добавить к символам пробел, который надо чуть по другому обрабатывать — с учетом длинны слова и иногда считать что там не пробел, а разрыв слов, информацию о больших символах и цифрах генерировать отдельно — независимо от информации о буквах. Но для создания хороших деревьев для них нужна база реальных паролей. Практически — работы, еще, конечно, очень много. Но что касается об-но алгоритма — не впечатлил меня этот Джон, есть ли еще какие-то известные работы в этой области?

Здравствуйте, __kot2, Вы писали:
__>В двух словах — надо добавить к символам пробел...
добавлю
в первом посте я описал алгоритм сжатия, который эффективно сжимает "натуральные слова" и обратил его.

если нам нужен расширенный набр символов — никаких проблем — додумываем этот алгоритм сжатия так, чтобы он сжимал последовательности символов уже с пробелами, регистром и цифрами, учитывающий
факт, что буквы в верхнем регистре и цифры встречаются реже обычных, верхний регистр чаще в начале слова, цифры чаще в конце и обращаем этот алгоритм. вариантов — масса, некоторые сами собой напрашиваются. например, 0 — все буквы маленькие, 10 — первая буква большая, остальные маленькие, 110 — ... Тут для анализа битовых наборов нужна база реальных паролей. Эти биты суммируются с сжатым паролем, получаем общую длинну, распаковывается соотв-но обратно (разве что есть ньюанс с разделителями — где закодир буквы, где регистр, а где цифры). Опять же — Хаффман в чуть измененном виде.

Здравствуйте, netch80, Вы писали:

N>Цупурик, говорите? Запомним

Здравствуйте! Я Цупурик. Вот, пришёл.

Здравствуйте, __kot2, Вы писали:

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

Идея безусловно интересная, хотя и не новая. Она основана на людской лени придумывать и/или запоминать стойкие пароли. Таким образом, для взлома "одноглазников" — вполне сработает, а для вскрытия пароля одного зип-файла — тут уж как повезет. Я хочу сказать, что идея основана на массовости пользователей — ее вполне можно использовать для рассылки спама через тех же одноклассников. Скажем из миллиона пользователей, 100 тысяч вполне взломаются таким способом. Но как-то это все паскудненько. Я ничего не имею против лично Вас, уважаемый автор, я всего-лишь хочу сказать, что область применимости этой идеи — это прежде всего (а может быть и только) паскудные спамеры и кракеры. Такие дела.

Здравствуйте, McSeem2, Вы писали:
MS>Идея безусловно интересная, хотя и не новая. Она основана на людской лени придумывать и/или запоминать стойкие пароли. Таким образом, для взлома "одноглазников" — вполне сработает, а для вскрытия пароля одного зип-файла — тут уж как повезет. Я хочу сказать, что идея основана на массовости пользователей — ее вполне можно использовать для рассылки спама через тех же одноклассников. Скажем из миллиона пользователей, 100 тысяч вполне взломаются таким способом. Но как-то это все паскудненько. Я ничего не имею против лично Вас, уважаемый автор, я всего-лишь хочу сказать, что область применимости этой идеи — это прежде всего (а может быть и только) паскудные спамеры и кракеры. Такие дела.

Я конкретно поправлю, в чем идея-то. брутфорс хорош, когда у нас есть хэш или закодир файл и мы можем локально перебирать пароли, со скоростью хотя бы 100 тысяч попыток в секунду. Это сужает область применения брустфорса. Пытаться им ломать одноклассников или там пароли к аське — извращение. И я не говорю, что я, мол, открыл быстрый способ взлома паролей к удаленным ресурсам. да нет, конечно. И прямо сейчас нельзя эту программку использовать для, скажем, генерации словаря и подсовывания переборщику по этому словарю — например John the Ripper может так делать. не сломает он большинство паролей, так как даже сайты сейчас некоторые стали в обязательном порядке требовать цифры. Идея, которую я хочу, чтобы откомментировали, в другом. John the Ripper — отличный переборщик, но его создатель не знает, что понятие информации связано с вероятностью и более вероятный имеет меньше информации в себе, так же как и любой текст имеет в себе тем больше информации, чем он менее вероятен. Это и есть идея — генерировать информацию на уровне бит и пытаться декомпрессировать на основании нее сам пароль. Большинтво людей думает что 0 меньше 1 и что 0000 меньше 1111. Но с точки зрения информации это не так. — 0 так же информативен как 1, а 0000 как 1111. 1 или 0 — совершенно равноважные биты и не факт, что вариант 0000 должен проверяться ранее, чем 1111. Они несут равную информацию, значит, должны проверяться почти друг за другом. John the ripper не пользуется этим фактом, он просто фиксирует длинну пароля и делает некий перебор. У меня даже такое ощущение создается, что он поступает совсем тупо. Не уверен, но по-моему он, переупорядочив буквы по частоте использования, увеличивает набор перебираемых символов от 1 до всех, пока не встретит пароль. Это вообще капец неоптимально. Вот поэтому я и спрашиваю — есть ли еще работы в этой области?

Здравствуйте, __kot2, Вы писали:

__>Здравствуйте, netch80, Вы писали:
N>>Если Вы сможете расширить свою идею на произвольные комбинации с цифрами, знаками, пробелами и прочим что входит в реальные пароли — с нёе будет какой-то толк. Если нет — она бесполезна.
__>тут нет никакой принципиальной сложности. Это все муторные доделки, не зависящие от сути. В двух словах — надо добавить к символам пробел, который надо чуть по другому обрабатывать — с учетом длинны слова и иногда считать что там не пробел, а разрыв слов, информацию о больших символах и цифрах генерировать отдельно — независимо от информации о буквах.

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

Опять-таки — я, видимо, смотрю не на тот "рынок". Вы целитесь на пароли одного вида публики (который напишет что-то вроде "вечная любовь"), а я оцениваю способности программы по тем случаям, когда будет что-то вроде "Аап4чхИИ!!". А ещё есть случаи автогенерируемых паролей — например, как Вы будете подбирать "zMnDwSDOxdTSwcTJw8nPzs7PyiDT==" (ну-ка посмотрите на свой пароль для RSDN;)) В способности Вашего подхода экономно искать второй и третий случай я, мягко говоря, сомневаюсь.

__> Но для создания хороших деревьев для них нужна база реальных паролей. Практически — работы, еще, конечно, очень много. Но что касается об-но алгоритма — не впечатлил меня этот Джон, есть ли еще какие-то известные работы в этой области?

С исходниками и толкового — я больше не видел.

Здравствуйте, netch80, Вы писали:
N>Мнэээ... в теории звучит хорошо. А на практике? На практике, например, с числами Вы уже не получите никакой корреляции. А воткнуты цифры могут быть в произвольное место.
ну конечно могут. и мы должны проверить все варианты. но одни варианты все-таки используются чаще других, мы этим можем воспользоваться. Так же, как с реестром, с цифрами принципиально никакой проблемы нет, легко можно додумать предложенный мною способ учета реестра на цифры. Только тут муторнее и больше ньюансов, конкретнее:
N>Опять-таки — я, видимо, смотрю не на тот "рынок". Вы целитесь на пароли одного вида публики (который напишет что-то вроде "вечная любовь"), а я оцениваю способности программы по тем случаям, когда будет что-то вроде "Аап4чхИИ!!"
например, люди чаще всего используют цифры так
0 место о
4 место ч
2 место ту

цифры для сложности добавляют часто в конец пароля. причем цифры 1, 2 или 3 выбираются чаще других
пароль123

"мусорные" символы типа ! или =- чаще всего ставят в конец пароля

пар0ль123=!

N>А ещё есть случаи автогенерируемых паролей — например, как Вы будете подбирать "zMnDwSDOxdTSwcTJw8nPzs7PyiDT==" (ну-ка посмотрите на свой пароль для RSDN) В способности Вашего подхода экономно искать второй и третий случай я, мягко говоря, сомневаюсь.
если же пароль сгенерирован полностью случайно, где каждый символ из набора выбирается равномерным рандомом, то __самый оптимальный способ__ подбора такого пароля — побуквенно инкрементируя индексы букв. если использовать любой другой алгоритм ставящий одни n-символьные наборы наперед других n-символьных, то ожидаемое время подбора только увеличится (тут конечно абв ставится ранее вба, но это не выбор алгоритма, а просто случайная последовательность, без учета языка, с учетом мы бы поставили абв и бва в конец проверок). То есть предложенный мною алгоритм будет заведомо хуже лексикографического перебора в этом случае. Но есть ньюанс. Во-первых в автогенерированных паролях одни символы могут использоваться чаще других, тогда можно воспользоваться классическим Хаффманом, алгоритм опять не меняется, перебор опять ускоряется. Во-вторых, автогенерированный пароль сложно запомнить и его приходится записывать, а записанный где-то пароль уже наполовину плохой пароль. Поэтому автогенераторы часто идут навстречу пользователю и генерят пароль, который легко запомнить. Хорошо, что пароль rsdn не нужно вводить постоянно, как, допустим, при логине на рабочем компе или, например, если я делаю архив и генерю пароль к нему, то факт — где-то этот пароль надо сохранить поэтому мало кто так делает. чаще берут пароли из головы. Существует класс совсем "плохих" паролей. допустим, я помню пароль от 15ого уровня принца персии — 88724447, который раньше кое-где ставил. тут только обычный брутфорс.

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

__>> Но для создания хороших деревьев для них нужна база реальных паролей. Практически — работы, еще, конечно, очень много. Но что касается об-но алгоритма — не впечатлил меня этот Джон, есть ли еще какие-то известные работы в этой области?
N>С исходниками и толкового — я больше не видел.
жаль

Здравствуйте, __kot2, Вы писали:

__>... так давайте просто подавать на вход деархиватору все возможные последовательности нулей и единиц начиная с длинны 1, постепенно увеличивая длину.
__>так мы получим
__>1110000 все
__>1101000 нат
__>0101100 что
__>1011100 сво
__>0000110 был
__>...
__>00001100 было
__>01111100 это
__>10000010 гра
__>01100010 каза

На мой взгляд, отцитированная идея очень красивая! Фишка тут в том, что ничто не мешает сделать деархиватор с навороченной логикой. Например, первое, что приходит в голову — взять статистику биграмм/триграмм по тестовому набору данных, и закодировать наиболее популярные биграммы наименее короткими кодами.
Кстати, судя по исследованиям в соседней ветке

Автор: Muxa
Дата: 01.08.09

, статистика n-грамм будет сильно отличаться от обычного русского языка

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

Здравствуйте, __kot2, Вы писали:

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

Я бы заценил, если бы было обоснование что время подбора 1000(например) придуманных людьми паролей вашим методом существенно меньше чем обычным перебором. Нудиратор меня не покорил.

Здравствуйте, funikov, Вы писали:
F>Я бы заценил, если бы было обоснование что время подбора 1000(например) придуманных людьми паролей вашим методом существенно меньше чем обычным перебором. Нудиратор меня не покорил.
Для проведения хорошего теста нужен набор паролей, которому можно доверять. Поэтому я вчера достал базу паролей, которые недавно сперли из вконтакта. Пытаться проверять все подряд пароли — нужно многое дописывать, ни цифер, ни регистра алгоритм пока не понимает. для паролей же типа qwerty или asdcxz нужны другие деревья, перебор с текущими деревьями будет скорее всего медленнее брутфорса и пробовать даже не стоит. в реале стоит запускать параллельно несколько экземляров брутфорса с разными деревьями. одни — русские, второй — русские набранные в другой раскладке, третьи — ...
Зато прямо сейчас можно оценить насколько эффективен будет алгоритм на классе паролей, созданных из маленьких русских букв. (да, это не есть широкой класс, но любой другой пароль тоже в некоем классе находится, их немного, и там же картина, скорее всего, не отличаться принципиально). Для чистоты эксперимента я стал подряд просматривать все пароли, которые попадают в этот класс, не выкидывая какие-либо, не добавляя свои, не меняя регистр и символы в них вообще. Любой человек это может проделать и получит набор паролей именно в том же порядке, в котором они приведены в таблице.
Таблица — <пароль> <миллионов итераций этим алгоритмом> <миллионов итерация брутфорсом 32 символьным (без ё)> <отношение второго к первому>
во втором столбце после некот паролей написано — "посчит" — значит, кол-во итерация точно, иначе — оценка с погрешностью (обычно процентов 20)

не знаю я, как сделать красиво табличку, пусть будет так.

кериловка                    4000            3*10^8        75000
космос                           2 посчит           335          167        
мухтарчик                  2*10^7            4*10^8           20
последниймесяцотдыха       10^18           6*10^23       600000
шерминская                    10^6            8*10^8          800
кнопачка                    8200            340000           41
люблютебя                    10^5            4*10^8         4000
романчикова                    10^5           2*10^10       200000
максим                         827 посчит           402          0.5
людочка                          54 посчит      12000          220
виктория                      92 посчит         68000          740
кирилл                         343 посчит           343            1 (! :))
карраказ                    4000            343000           86
сверхъестественное          2*10^9           6*10^20      3*10^11
масенька                      82 посчит        400000         4900
хопмагони                 3*10^10            7*10^8         0.02 (!)
максимова                  8*10^6            4*10^8           50
ворона                        0.03 посчит            67         2200     
капитанскаядевочка         7*10^13           4*10^20       6*10^6
насрать                          11 посчит         14000         1300
светикангелочег              8*10^9           2*10^16     2.5*10^6
саньзайтымой             9*10^12           6*10^11         0.06 (!)