Хэширование и пароли

Задачи

1. Зашифруйте с помощью шифра Цезаря со сдвигом 6 высказывание «ЛЮДИ ОХОТНО ВЕРЯТ ТОМУ, ЧЕМУ ЖЕЛАЮТ ВЕРИТЬ».

2. Напишите программу, которая выполняет шифрование строки с помощью шифра Цезаря.

3. *Попытайтесь расшифровать сообщение, закодированное шифром Цезаря с неизвестным

сдвигом: «ХШЖНПУТ ФКХКОЙКТ». Для этого можно написать программу.

4. Используя шифр Виженера с ключом «ЛЕНА», зашифруйте сообщение «НЕЛЬЗЯ ОБИЖАТЬ

ГОСТЯ».

5. *Измените программу для шифрования Цезаря так, чтобы учитывать букву Ё.

6. *Измените программу для шифрования Цезаря так, чтобы учитывать и букву Ё, и пробел.

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

это не совсем так. Можно хранить не пароли, а некоторые числа, полученные в результате обра‐

ботки паролей. Простейший вариант – сумма кодов символов, входящих в пароль. Для пароля

«A123» такая сумма равна

215 = 65 (код «A») + 49 (код «1») + 50 (код «2») + 51 (код «3»).

Фактически мы определили функцию

H (M), которая сообщение M любой длины превращает в

короткий код m заданной длины. Такая функция называются хэш‐функцией (от англ. hash – «ме‐ шанина», «крошить»), а само полученное число – хэш‐кодом, хэш‐суммой или просто хэшем ис‐ ходной строки. Важно, что зная хэш‐код, невозможно восстановить исходный пароль! В этом смысле хэширование – это необратимое шифрование.

Итак, вместо пароля «A123» мы храним число 215. Когда пользователь вводит пароль, мы считаем сумму кодов символов этого пароля и разрешаем вход в систему только тогда, когда она

равна 215. И вот здесь возникает проблема: существует очень много паролей, для которых наша хэш‐функция дает значение 215, например, «B023». Такая ситуация – совпадение хэш‐кодов раз‐ личных исходных строк – называется коллизией (англ. collision – «столкновение»). Коллизии будут

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

что мы выбрали плохую хэш‐функцию.

Математики разработали надежные (но очень сложные) хэш‐функции, обладающие особы‐

ми свойствами:

1) хэш‐код очень сильно меняется при малейшем изменении исходных данных;

2) при известном хэш‐коде m невозможно за приемлемое время найти сообщение M с таким хэш‐кодом (H (M) = m);

3) при известном сообщении M невозможно за приемлемое время найти сообщение таким же хэш‐кодом (H (M) = H (M 1)).

M 1 с

Здесь выражение «невозможно за приемлемое время» (или «вычислительно невозможно») озна‐ чает, что эта задача решается только перебором вариантов (других алгоритмов не существует), а количество вариантов настолько велико, что на решение уйдут сотни и тысячи лет. Поэтому даже если взломщик получил хэш‐код пароля, он не сможет за приемлемое время получить сам пароль (или пароль, дающий такой же хэш‐код).

6 Назван по имени Блеза Виженера, швейцарского дипломата XVI века.

Чем длиннее пароль, тем больше количество вариантов. Кроме длины, для надежности па‐

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

щие только из цифр. Если же пароль состоит из 10 символов и содержит латинские буквы (заглав‐

ные и строчные) и цифры, перебор вариантов (англ. brute force – метод «грубой силы») со скоро‐

стью 10 млн. паролей в секунду займет более 2000 лет.

Надежные пароли должны состоять не менее чем из 7‐8 символов; пароли, состоящие из 15

символов и более взломать методом «грубой силы» практически невозможно. Нельзя использо‐

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

Сегодня для хэширования в большинстве случаев применяют алгоритмы MD5, SHA1 и рос‐ сийский алгоритм, изложенный в ГОСТ Р 34.11 94 (он считается одним из самых надежных). В криптографии хэш‐коды чаще всего имеют длину 128, 160 и 256 бит.

Хэширование используется также для проверки правильности передачи данных. Различные

контрольные суммы, используемые для проверки правильности передачи данных, – это не что иное, как хэш‐коды.

? Контрольные вопросы

1. Что такое хэширование? хэш‐функция? хэш‐код?

2. Какую хэш‐функцию вы используете, когда начинаете искать слово в словаре?

3. Что такое коллизии? Почему их должно быть как можно меньше?

4. Какие требования предъявляются к хэш‐функциям, которые используются при хранении па‐

ролей?

5. Что значит «вычислительно невозможно»?

6. Взломщик узнал хэш‐код пароля администратора сервера. Сможет ли он получить доступ к

секретным данным на сервере?

7. Какие свойства пароля влияют на его надежность?

8. Как выбрать надежный пароль?

9. Какие алгоритмы хэширования сейчас чаще всего применяются?

10. *Предложите какой‐нибудь свой метод хэширования. Подумайте, как часто при его исполь‐

зовании могут происходить коллизии.

Дата добавления: 2015-05-31