Здравствуйте, уважаемые. Изучаю тут одну программу, которая на основе входных данных генерит (вероятно) хеш длиной 8 байт. Вопроc: сколько по времени может занять прямой перебор значений входных данных, хотя бы приблизительно? Сам алгоритм хеширования занимает на ассембле где-то строк двести. Спасибо.
Зависит от многих факторов. От частоты процесора, оперативки, от непосредственно алгоритмов генерации входных данных и генерации хэша. Скорость выполнения различных инструкций так же варьируется Учитывая все вышеприведенные факторы, однозначно ответить нельзя, кто дождется окончания перебора, прапрапраправнуки или прапрапрапрапрапрапраправнуки
поэтому и 2^127 а не 2^128 =) PS: Скорее всего еще куча коллизий будет, так что однозначно трудно сказать.
MSoft 2^128/2 = 2^127 2^64 - это сложность совсем другой атаки, которая ставит своей задачей не поиск прообраз заданного хеш-значения, а поиск двух разных прообразов, ведущих к одинаковому хеш значению (т.е. коллизии).
Господа, опечатался. В оригинале необходимо читать "8 байт", т.е. 64 бита. По силам ли среднему комьютерую сделать полный переобор? Уж больно не хочется патчить программу
Можно вставлю свои чайниковские пять копеек? Получение хэша - процесс односторонний. Даже делая полный перебор всех вариантов хэша, Вы не получите входные данные, т.к. при такой постановке задачи входные данные могут иметь любой размер, и о структуре входных данных тоже ничего не сказано. Отсюда, вспоминая обсуждение принципа Дирихле в третьем классе, для "худшего" хэша размером 8 байт может быть, например, не менее 2^64 вариантов входных данных, размером в 16 байт. Для идеального алгоритма хэширования слово "худший" можно опустить, т.к. каждый хэш будет соответствовать одинаковому числу вариантов входных данных. Может я совсем тупой, чтобы осилить программу третьего класса? Ну тогда поправьте, если ошибаюсь.
flankerx Вы говорите загадками. Уточню, что меня интересует именно вариант решения данной проблемы, когда возможно получение оригинального или другого ключа, главное чтобы он подошёл. Наверное надо было указать ранее, что в качестве входного массива принимается строка из 13 символов, содержащая цифры от 0 до 9 и латинские буквы от 'а' до 'z'.
kiprirrpik Если проверка правильности ключа идет только по хешу, тогда возможно использовать перебор вариантов. Следует учесть, что в процессе перебора могут попасться разные строки, но хеш у которых будет одинаков. Что же касается времени перебора, то расчитывается оно элементарно: количество всех вариантов ключей: 36^13 (flankerx правильно? ) количество вариантов хешей: 2^64 по теории вероятности "достаточно" перебрать: 2^63 Чтобы узнать время, за которое ты достигнешь цели, раздели количество вариантов на скорость перебора на твоем компе.
MSoft Правильно kiprirrpik Я говорю не загадками. Просто задача сформулирована не очень четко, поэтому мне приходится делать предположения. Перед тем как начинать полный перебор я бы поковырял алгоритм "хеширования". Если он действительно строк 200, то это не займет много времени. Вполне возможно что алгоритм имеет недостатки, снижающие его стойкость и облегчающие перебор. Что касается времени перебора... В озвученных условиях это будет выглядеть примерно так: скорость перебора ~10 млн. паролей на одном ядре нужно перебрать примерно 2^63 вариантов (т.к. 36^13=2^67, т.е. больше чем мощность пространства хешей). Делим одно на другое, получаем 10,6 млн. суток. Думаю, все понятно?
