Криптографическая защита от брутфорса

Алгоритмы формирования хеша, математическая сложность которых не позволяет делать подбор паролей быстро. Например, злоумышленник украл файл с паролями и начал их брутфорсить. Но если процесс формирования хеша будет занимать, скажем 10 секунд на гигагерцовом пентиуме, особо не разгонишься. Алгоритм должен предполагать задавание математической сложности при формировании нового пароля. (С учетом роста производительности эвм). Но будет одна загвоздка. Можно предварительно сформировать терабайтную базу паролей и хешей и быстренько пробежаться по ней. Нужен какой-то многоэтапный алгоритм, при котором, от одного пароля будет каждый раз формироваться разный хеш, а на втором этапе будет математически доказываться идентичность этого хеша искомому. Что-то вроде этого. Есть ли, возможно ли?

 

возможно, смотри как в раре сделано - куча итераций sha1 с добавлением соли. гигагерцовый проц может дать около 10ка паролей в секунду - тоже не сильный разгон

 

сделай как в RAR - 100000 (не помню сколько) раз SHA

только наверное стоит на каждой итерации добавлять ее номер, а то последовательность выродится (это только предположение, да поправят меня знающие люди)



update: упс. пока писал masquer то же самое сказал

 

А можно так:



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

 

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

 

bogrus



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



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



Затем вычисляем короткий обратный хеш и ксорируем с ним



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

 

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

 

Folk Acid

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

 

т.е. (грубо говоря) берем MD5 хеш от пароля, берем MD5 хеш от времени, ксорим два хеша и храним



потом пришел момент и надо сверить введенный юзером пароль с сохраненным хешем ...



твои действия?

 

bogrus



Не в обиду будет сказано: я чё, пришел лекции читать? Денег мне за это никто не платит.



Я ж ясно написал: вычисленное при генерации пароля (а не проверки) случайное число хранится в контейнере. Потом (при проверке пароля) это число извлекается из контейнера и ксорится с введенным повторно паролем.



И вообще, алгоритмов может быть множество, важна суть а она в двух моментах:

1) Временная сложность хеша достаточно большая и может варьироваться при генерации хеша

2) Не возможность создания универсальной таблицы подбора хешей для конкретного приложения

 

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



Я наверное непонятно изъясняюсь, но да уж ладно, это из-за лени упорядочивать мысли на листке бумаги

 

сделай как в Раре - 224000 SHA1 (хэш от пароля, хэш от полученного хэша, ..., хэш от предоследнего хэша) - на вводе займет максимум 100 миллисекунд, но брутфорсом более 10 в секунду не сделаешь.

 

alpet



Я ничего не смыслю в квантовых вычислениях. Просто не нашел пока толкового популярно написаного мануала на эту тему.



А насчет нелинейности расшифровки - так это последовательное формирование SHA1 (как в Раре), когда неизвестно сколько именно итераций нужно пройти. Просто хешем, полученным после каждой итерации расшифровывать некое заведомо известное число. Расшифровал за 5 секунд определенным хешем - молодец, не расшифровал - хз, забей.



Вот еще интересная задачка "бездоказуемости возможности расшифровки", когда не известно заранее, зашифрованы ли полезные данные или физический рандом.

 

Folk Acid

Во первых не ясно. Во вторых это ничем не отличается от хеширование просто алгоритм усложнится немного.

Почему таблицы должны стать больше? По мойму они либо не изменятся либо уменьшатся.

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

Теории есть, а напрактике системы не устойчивы.

 

Во вторых это ничем не отличается от хеширование просто алгоритм усложнится немного.



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



Почему таблицы должны стать больше? По мойму они либо не изменятся либо уменьшатся.

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

 

О да, вот это защита от брутфорса паролей - хранить ключевые данные на флешке в сейфе, зачем тогда вообще пароль? Я думал ты предлагал такой алгоритм, чтобы нельзя перебрать по словарю (т.е. на "admin" всегда были разные хеши)

 

О нет, bogrus. Эти ключевые данные, как ты сказал, не должны храниться во флешке в сейфе. Они будут известны любому расшифровщику пароля, в т.ч. и брутфорсеру, т.к. должны храниться в открытом виде либо вместе с зашифрованными данными, либо вместе с хешем, если мы храним пароль, как в Винде, например. Это не уменьшает сложности взлома. Точно также, bogrus, в Раре (в программе) хранится случайное число, известное всем. Оно используется для генерации хеша от пароля. Это случайное число нужно для того чтобы хеши, сформированные разными программами, были разными. Подробнее почитай в доке по SHA1 и MD5.



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

 

чтобы нельзя перебрать по словарю



Ты неправильно понимаешь фразу "табличный метод расшифровки" и "перебрать по словарю". Первое - это заранее сформированная таблица соответствий паролей и хешей. Второе - это просто список паролей.

 

Я конечно извеняюсь за вмешательство, но плиз подскажите:

1) что такое "контейнер"!

2) Если как вы говорите Хеши получаются разными, каким образом прога (тот же Рар) понимается что введён правильный пароль?

 

видимо под "контейнером" он имел ввиду зашифрованый файл, там хранить хеш и проверять пароль вообще не надо - в первых 4 байтах хранишь CRC32 расшифрованого файла (plaintext), а в остальных его зашифрованное содержимое



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



если первый блок plaintext'а неизвестен, то скорость подбора будет зависеть от скорости расшифровки файла (чтобы сверить CRC32 прийдется расшифровать весь файл), т.е. от конкретного алгоритма и режима



за AES не скажу, но к примеру только составление ключевой таблицы RC4 займет в 4 раза больше времени чем хеширование пароля алгоритмом MD5 и немного дольше SHA1, если последних используется много итераций, а планируется брутить многократно, то был бы смысл вообще отказатся от хешей, и достаточно один раз составить массив RC4 таблиц на наиболее употребительные словарные пароли, чтобы ни на что не тратить времени, кроме как самой расшифровки, но вот тут (дополнительно) соль (как в раре) и помешает ... зашифрованый архив кажый раз будет разный (для одного и того же пароля и plaintext'а), значит все равно прийдется выполнять все эти итерации



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



для клиент\серверной авторизации есть схема challenge-responce (основаная на посылке сервером случайных чисел и шифрованием их клиентской стороной используя хеш от пароля), но о какой авторизации спрашивал или выдумал Folk Acid - лично я, так и не понял