Лабы / Лаба3 / лаба3

Описаниелабораторной работы00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 лабораторной работы

Цель работы:

Расшифровать пароль из хэша MD5

1. Девяти символьный пароль

ХЭШ: 96484AF2B85280B49C475366705F03BDB49C475366705F03BD

2. Восьми символьный пароль

ХЭШ: ac495c020e636979a1238d371e9bedc6

3. Семи символьный пароль

ХЭШ: f4a949cf2a5e56d7396ed24a3b509bfb

Теоретические сведения

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

1. Необходимы большие вычислительные мощности (один компьютер в состоянии расшифровать хэш только за 15 дней и более).

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

Для ускорения расшифровки хэшей использовался готовый алгоритм RainbowCrack, основанный на поиске хэш- коллизий. Хэш-коллизия – это соответствие одному значению хэш-функции- нескольких паролей.

И строго говоря взлом хэша есть ни что иное, как поиск этих коллизий.

Принцип работы RainbowCrack, взято с ресурса passcrack.spb.ru:

«….Все началось чуть раньше, чем ты предполагал. Еще в 1980 году Мартин Хеллман предложил кардинально новый подход к криптоанализу хэш-функций: он предложил использовать предварительно вычисленные таблицы, размещенные в памяти. Однако совершенно понятно, что хранить хэш-значения всех возможных вариантов ключей - абсурдная затея, которая ни к чему хорошему не приведет. Мало того, что такие таблицы будут занимать умопомрачительное количество терабайт, так еще и поиск по ним будет занимать невероятное количество времени.

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

1. Фиксируется рабочий алфавит, то есть задается множество Q всех возможных ключей.

2. Фиксируется элемент q из множества Q и вычисляется значение h хэш-функции на нем.

3. При помощи некоторой «срезающей» функции R из хэша генерируется ключ, принадлежащий множеству Q: q=R(h). Если число элементов в цепочке меньше заданного, осуществляется переход к пункту 2.

Такой итеративный процесс выполняется до тех пор, пока мы не получим цепочку длиной t ключей. Эта последовательность не размещается целиком в памяти, записывается лишь первый и последний ее элементы. В этом и заключается суть метода: если в цепочке, скажем, 1500 ключей, то мы неслабо экономим памяти, обменивая ее на время, необходимое для дальнейшего криптоанализа. К слову, в исходном варианте название этого метода переводится как «компромисс между затратами времени и памяти в криптоанализе», так что все логично. Но вернемся к описанию метода.

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

Задается значение хэш-функции, для которого необходимо получить коллизию. При помощи срезающей функции R строится значение ключа K0, из которого выводится по описанному алгоритму цепочка поиска длиной не более чем t элементов. Если в таблице есть искомый ключ, то один из сгенерированных элементов новой цепочки будет являться терминальным элементом нашей таблицы. Далее не составляет труда по известному начальному элементу вывести всю соответствующую терминалу цепочку, включая элемент, непосредственно предшествующий начальному значению K0, то есть ключ, который мы ищем. Однако такой позитивный расклад возможен только в том случае, если в сгенерированных таблицах действительно есть коллизия. Здесь вплотную встает резонный вопрос: сколько же нужно сгенерировать цепочек, чтобы они покрывали все множество возможных ключей. И к сожалению, дать односложный ответ невозможно.

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

А я пока продолжу отвечать на вопрос о количестве цепочек. Вообще говоря, чтобы обеспечить полное покрытие множества Q, необходимо сгенерировать бесконечно большую таблицу с цепочками. Дело в том, что частота слипания цепей быстро увеличивается вместе с ростом таблицы. Поэтому число требуемых последовательностей характеризуется требуемой вероятностью (обозначу ее как P*) того, что произвольный ключ q из Q окажется в нашей системе подмножеств, в нашей таблице. Именно требуемая вероятность P* определяет необходимый размер таблицы с цепочками. Обрати внимание, что под «размером» таблицы я понимаю как число цепочек, так и их длину, оба эти параметра влияют на частоту слипания и эффективность покрытия.

В работе Хеллмана строго выводится формула, по которой можно вычислить P* как функцию от числа цепочек, их длины и числа элементов во множестве Q. Это довольно здоровое выражение, и само по себе нас мало интересует, нас больше заботит, что оно показывает. Собственно, ничего кардинально нового: при росте размеров таблицы вероятность P* практически перестает увеличиваться. По этой причине для эффективного использования метода необходимо создавать несколько таблиц, сгенерированных независимым образом. В этом случае общая вероятность успеха (P) выражается так: P=1-(1-P*)^l, l - число таблиц. Эту формулу очень легко получить из простейших соображений: (1-P*) - это вероятность того, что мы не найдем ключ в одной из таблиц; (1-P*)^l - вероятность, что вообще не найдем ключ ни в одной из l таблиц. Соответственно, вероятность обратного события - это P=1-(1-P*)^l.

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

Практическая часть.

Раcшифровка хэшей методом RainbowCrack с помощью, ресурса http://passcrack.spb.ru:

Хэш	Начало процесса	Окончание процесса	Результат
f4a949cf2a5e56d7396ed24a3b509bfb	2006-03-29 19:57:29	2006-03-29 21:06:49	cCna934
ac495c020e636979a1238d371e9bedc6	2006-03-29 15:31:00	2006-03-29 16:35:32	56ruvzcf

Расшифровка 9 символьного пароля оказалась не возможна на ресурсе http://passcrack.spb.ru, по причине отсутствия на ресурсе необходимых таблиц, потому решено было использовать другие ресурсы для этих целей.

Был выбран ресурс http://www.plain-text.info, как один из быстрых и стабильных, результаты расшифровки 9 символьного пароля:

Хэш	Начало процесса	Длительность	Результат
96484AF2B85280B49C475366705F03BD	2006/03/29 21:15:05	5:11:0	ltdznmcjn