Весь диапазон - Обратный поиск MD5

Question

Я узнаю о методах шифрования, и у меня есть вопрос о MD5.

Я видел, что есть несколько сайтов, которые имеют «таблицы радуги», которые дадут вам обратный поиск MD5, но они не смогут найти все возможные комбинации.

ради знания, мой вопрос заключается в следующем:

Гипотетически, если группа людей, должны были рассмотреть верхний предел (например, 5 или 6 символов.) И решить, чтобы наметить весь MD5 хеш для всех значения внутри этого диапазона, сохраняя результаты в базе данных для обратного поиска.

1. Как вы думаете, такая вещь вероятна.
2. Если вы можете предположить, какой масштаб ресурсов это означал бы?
3. Насколько вам известно, были ли какие-либо публичные или частные попытки сделать это?

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

(я refered на This вопрос уже.)

Answer 1

5 или 6 символов легко. 6 байт выполнимо (это 2 комбинаций), даже с ограниченным оборудованием.

А именно, простой процессор Core2 от Intel сможет хэшировать один пароль примерно за 150 тактов (при условии, что вы используете реализацию SSE2, которая будет бить четыре пароля параллельно в 600 тактов). Благодаря четырехъядерному процессору с тактовой частотой 2,4 ГГц (это мой компьютер, а не совсем новейшая машина), я могу попробовать примерно 2 паролей в секунду. Для такого рода работ массивная параллельная архитектура прекрасна, поэтому имеет смысл использовать графический процессор. Возможно, за 200 $ вы можете купить видеокарту NVidia, которая будет примерно в четыре раза быстрее (т. Е. 2 ​​ паролей в секунду). 6 буквенно-цифровых символов (в верхнем, нижнем регистре и цифрах) близки к 2 комбинации; пробовать их все, то вопрос 2 ^(36-28) секунд, который меньше, чем пять минут. С 6 случайными байтами потребуется 2 секунд, то есть чуть меньше двух недель.

Это для стоимости процессора. Если вы хотите ускорить фактическую атаку, вы сохраняете результаты хэша: таким образом, вам не нужно будет перекомпилировать все эти хэшированные пароли каждый раз, когда вы нападете на пароль (но вы все равно должны сделать это один раз). 2 хэш-результаты (по 16 байт) означают 1 терабайт. Вы можете купить жесткий диск, который будет стоить 100 долларов. 2 Результаты хэша предполагают 4096 раз, что место для хранения; в простых жестких дисках это будет стоить столько же, сколько дома: немного дорого для среднего скучного студента, но доступного для большинства видов правительственных или преступных организаций.

Радужные столы - это трюк оптимизации для хранения. Грубо говоря, вы хранить только один каждый т результатов хэширования, в обмен того, чтобы сделать T поисках, и ^{T 2} хэш вычислений для каждой атаки. Например, вы выбираете t = 1000, вам нужно купить только четыре жестких диска вместо четырех тысяч, но вам нужно будет сделать 1000 поисковых запросов и миллион хэшей каждый раз, когда вы захотите взломать пароль (это потребует дюжины секунд в большинство, если вы это сделаете правильно).

Следовательно, у вас есть два вида издержек:

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

• Стоимость хранения - это хранение результатов хэширования, чтобы легко атаковать несколько паролей. Жесткие диски не очень дороги, как показано выше. Таблицы Rainbow помогут вам снизить затраты на хранение.

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

Стоимость ЦП может быть увеличена путем определения того, что хеш-процедура - это не только один хэш-расчет; например, вы можете определить «хэш пароля» как применение MD5 по конкатенации 10000 копий пароля. Это заставит каждого злоумышленника угадать один тысяч в несколько раз дороже. Он также делает законную проверку пароля в тысячу раз дороже, но большинство пользователей не будут возражать (пользователь только что набрал свой пароль, он не может действительно проверить, не была ли проверка пароля занятой 10 мс или 10 мкс).

Современные Unix-подобные системы (например, Linux) используют пароли «MD5», которые фактически сочетают солевое и итерированное хеширование, как описано выше. (На самом деле, современная система Linux может использовать другую хеш-функцию, такую ​​как SHA-256, но это ничего не меняет здесь.) Таким образом, предварительно вычисленные таблицы не помогут, а взлом паролей «на лету» стоит дорого. Пароль с 6 буквенно-цифровыми символами может быть взломан в течение нескольких дней, потому что в любом случае 6 символов слабы. Кроме того, многие более длинные пароли являются взломанными, потому что оказывается, что люди начинают плохо, помня пароли; поэтому они не будут выбирать какую-либо случайную последовательность символов, они будут выбирать пароли, которые имеют некоторое «значение». Это уменьшает пространство возможных паролей.

Answer 2

1. Это возможно. Для небольшого количества символов это уже сделано. В ближайшем будущем для большего числа символов будет легко. MD5 не становится сильнее.

2. Это функция времени. Для изменения всего буквенно-цифрового пространства на 6 или менее символов потребуется вычислить 62^6 записей. Это 56 триллионов MD5. Это выполнимо определенной небольшой группой или просто для правительства, прямо сейчас. В будущем это будет выполнимо на домашнем компьютере. Помните, однако, что по мере увеличения количества допустимых символов или максимальной длины увеличение сложности экспоненциально.

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

Answer 3

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

Answer 4

1. Да, это не только возможно, но это, вероятно, было сделано раньше.

2. Это зависит от того, являются ли они отображением всего возможного диапазона или всего диапазона символов ASCII. Допустим, вам нужно 128 бит + 6 байтов для хранения каждого совпадения. Это 22 байта. Вы должны были бы:

   • 6,32 GB для хранения всех строчных буквенных комбинаций [а-г]
   • 405 GB для всех буквенных комбинаций [A-Za-Z]
   • 1.13 TB для всех алфавитно-цифровых комбинаций [a-zA-Z0-9]
   • 5.24 TB для всех комбинаций, состоящих из букв, цифр и 18 символов.

Как вы видите, она увеличивается в геометрической прогрессии, но даже при 5,24 ТБ, что нет ничего для агентств, скажем, АНБ или ЦРУ. Вероятно, они это сделали.

Как все говорят, соление может легко победить радужные столы, и это почти так же важно, как хеширование. Читайте это: Just hashing is far from enough - How to position against dictionary and rainbow attacks