На размышления о необходимости генерации псевдослучайных паролей меня натолкнула достаточно безрадостная статистика взлома паролей, созданных при помощи МОЗГ v1.0; однако взять какой-то первый попавшийся программный генератор паролей и с помощью него поменять все пароли — выглядит безрассудством. Я не проводил детальный анализ готовых программ-генераторов, однако расскажу некоторые достаточно простые, но познавательные факты, связанные с математикой генерации псевдослучайных чисел хорошего качества, которые позволят выбрать нужную программу самостоятельно.
В основе любой программы подобного класса лежит некоторый псевдослучайный генератор, то есть функция G: {0,1}n -> {0,1}n+1. Действительно, задача псевдослучайного генератора — получения хотя бы одного бита «случайности» на базе некоторых исходных данных. Затем, такой генератор можно запустить несколько раз, для получения нужного количества бит, и перевести их в символьный диапазон, получив новый пароль. Собственно, возникают две проблемы:
Достаточно хорошо знакомый каждому C программисту способ инициализации генератора случайных чисел это установка начального значения по текущему значению времени:
Такой способ очень плох, это просто катастрофа! Читаем описание функции
Таким образом, зная, что человек использовал определенный генератор, работающий на функции
Несколько лучше дела обстоят с функцией RDTSC, возвращающей число тактов с момента сброса процессора, однако, ее значения лежат в пределах от 0 до 264-1 и дискретны для разных процессоров с разным шагом; для удовлетворения своей паранойи — это не годится. В действительности этого запаса случайности будет хватать только для 6-8 символьных генерируемых паролей (в зависимости от используемого набора символов).
Это самые простые способы (и надеюсь, не самые часто используемые, иначе толку от таких программ ноль). Что же может дать достаточно хорошее начальное значение?
Во-первых анализ окружения: программа, при запуске, считающая хеш документов пользователя. Никто не может предугадать какие они будут, и мы получим начальное значение для генератора практически любой длины и хорошего качества. Исключение — практический «голый» компьютер, где ничего нет.
Во-вторых, интерактив с пользователем: заставлять нажимать десяток кнопок, наверное, бессмысленно, ибо и здесь почти очевидны закономерности вроде qwerty123456 (это не пароль, а инициализатор генератора случайных чисел, который конечно и выдаст потом сложный пароль, навроде A6@sIp!v0]x, но сломать его будет очень просто, зная, что за программой-генератором вы пользовались), но вот предложить подергать мышку — вполне неплохой вариант, здесь будет очень большой объем случайных чисел, без общих закономерностей.
Еще лучше, включить камеру или сделать запись с микрофона — огромный поток «шумных» данных, которые, пропустив через хеш функцию дадут отличный инициализатор произвольной длины.
Отсюда некоторая мораль: не столь важно, каким образом программа генератор получает пароли, сколь — откуда берет начальные данные. Если не происходит никакого интерактива вообще, следует усомниться.
На самом деле здесь нет особого смысла что-то изобретать. Самый простой объект который может дать хорошую случайность это хеш-функции.
Если в программе используется что-то другое, то есть все шансы ей не доверять. Никакие замечательные магические последовательности вроде Xi+1 = (a*Xi + c) mod m не дадут никакой надежной (криптографической случайности).
Для хеш-функций существует достаточно нехитрое обоснование законности их применения. Итак.
Функция F: {0,1}n -> {0,1}m называется односторонней функцией, если
1) она вычислима за полиномиальное время;
2) не существует полиномиального алгоритма, который верно вычисляет F-1 с хорошей вероятностью (большей 2-m).
Если m = n, такая функция называется односторонней перестановкой.
Вообще, любой псевдослучайный генератор является односторонней функцией.
А любая односторонняя перестановка позволяет сконструировать псевдослучайный генератор:
G({a1,a2,...an}) = {a1,a2,...an,F({{a1,a2,...an})}.
Общая схема построения такая:
Где G — вызов односторонней функции, например MD5, а y', y,… — биты выходного случайного пароля.
Так вот, утверждается [*], что существование псевдослучайных генераторов следует из существования односторонних функций, которые в свою очередь существуют, если P != NP.
Для конкретных случаев хеш-функций (MD5, SHA1, GOST) пока просто не существует таких алгоритмов вычисления F-1, чтобы поставить под сомнение случайность выходных значений.
Таким образом, бояться использования хеш-функций в псевдослучайной генерации можно будет только если вдруг окажется, что P = NP.
Но и нас это не беспокоит: ведь если удастся легко строить обратную к хеш-функции, то пароль будет проще получить обратив хеш-значение из базы, а не строить цепочку псевдослучайных байт, приводящих к теоретическому паролю, который еще надо будет проверить на соответствие значению из базы.
Простой тезис: даже MD5 можно использовать для псевдослучайных генераторов (для паролей)!
Часто применяют блочные шифры, для получения псевдослучайных генераторов, а также эллиптические кривые и решения дифференциальных уравнений — и на то есть свои причины, но я (пока?) не буду их трогать.
[*] Handbook of Applied Cryptography, A. Menezes, P. van Oorschot, S. Vanstone.
UDP: Автор аккуратной картинки — bad_guy
В основе любой программы подобного класса лежит некоторый псевдослучайный генератор, то есть функция G: {0,1}n -> {0,1}n+1. Действительно, задача псевдослучайного генератора — получения хотя бы одного бита «случайности» на базе некоторых исходных данных. Затем, такой генератор можно запустить несколько раз, для получения нужного количества бит, и перевести их в символьный диапазон, получив новый пароль. Собственно, возникают две проблемы:
- откуда брать начальные данные (инициализация генератора);
- какие функции можно использовать.
Начальные данные
Достаточно хорошо знакомый каждому C программисту способ инициализации генератора случайных чисел это установка начального значения по текущему значению времени:
srand ( time(NULL) );Такой способ очень плох, это просто катастрофа! Читаем описание функции
time — и видим, что она выдает число целых секунд, начиная с 00:00 hours, Jan 1, 1970 UTC. Таким образом, зная, что человек использовал определенный генератор, работающий на функции
time достаточно просто узнать дату его регистрации на ресурсе (или последней смены пароля, например при последнем заходе на сайт) и перебрать 86400 начальных значений (столько секунд в сутках), что делается за минуты. И не важно, что при этом его пароль из сотни символов разных регистров, цифр, спецзнаков, ведь единственная случайность — время запуска генератора.Несколько лучше дела обстоят с функцией RDTSC, возвращающей число тактов с момента сброса процессора, однако, ее значения лежат в пределах от 0 до 264-1 и дискретны для разных процессоров с разным шагом; для удовлетворения своей паранойи — это не годится. В действительности этого запаса случайности будет хватать только для 6-8 символьных генерируемых паролей (в зависимости от используемого набора символов).
Это самые простые способы (и надеюсь, не самые часто используемые, иначе толку от таких программ ноль). Что же может дать достаточно хорошее начальное значение?
Во-первых анализ окружения: программа, при запуске, считающая хеш документов пользователя. Никто не может предугадать какие они будут, и мы получим начальное значение для генератора практически любой длины и хорошего качества. Исключение — практический «голый» компьютер, где ничего нет.
Во-вторых, интерактив с пользователем: заставлять нажимать десяток кнопок, наверное, бессмысленно, ибо и здесь почти очевидны закономерности вроде qwerty123456 (это не пароль, а инициализатор генератора случайных чисел, который конечно и выдаст потом сложный пароль, навроде A6@sIp!v0]x, но сломать его будет очень просто, зная, что за программой-генератором вы пользовались), но вот предложить подергать мышку — вполне неплохой вариант, здесь будет очень большой объем случайных чисел, без общих закономерностей.
Еще лучше, включить камеру или сделать запись с микрофона — огромный поток «шумных» данных, которые, пропустив через хеш функцию дадут отличный инициализатор произвольной длины.
Отсюда некоторая мораль: не столь важно, каким образом программа генератор получает пароли, сколь — откуда берет начальные данные. Если не происходит никакого интерактива вообще, следует усомниться.
Функции генерации
На самом деле здесь нет особого смысла что-то изобретать. Самый простой объект который может дать хорошую случайность это хеш-функции.
Если в программе используется что-то другое, то есть все шансы ей не доверять. Никакие замечательные магические последовательности вроде Xi+1 = (a*Xi + c) mod m не дадут никакой надежной (криптографической случайности).
Для хеш-функций существует достаточно нехитрое обоснование законности их применения. Итак.
Функция F: {0,1}n -> {0,1}m называется односторонней функцией, если
1) она вычислима за полиномиальное время;
2) не существует полиномиального алгоритма, который верно вычисляет F-1 с хорошей вероятностью (большей 2-m).
Если m = n, такая функция называется односторонней перестановкой.
Вообще, любой псевдослучайный генератор является односторонней функцией.
А любая односторонняя перестановка позволяет сконструировать псевдослучайный генератор:
G({a1,a2,...an}) = {a1,a2,...an,F({{a1,a2,...an})}.
Общая схема построения такая:
Где G — вызов односторонней функции, например MD5, а y', y,… — биты выходного случайного пароля.
Так вот, утверждается [*], что существование псевдослучайных генераторов следует из существования односторонних функций, которые в свою очередь существуют, если P != NP.
Для конкретных случаев хеш-функций (MD5, SHA1, GOST) пока просто не существует таких алгоритмов вычисления F-1, чтобы поставить под сомнение случайность выходных значений.
Таким образом, бояться использования хеш-функций в псевдослучайной генерации можно будет только если вдруг окажется, что P = NP.
Но и нас это не беспокоит: ведь если удастся легко строить обратную к хеш-функции, то пароль будет проще получить обратив хеш-значение из базы, а не строить цепочку псевдослучайных байт, приводящих к теоретическому паролю, который еще надо будет проверить на соответствие значению из базы.
Простой тезис: даже MD5 можно использовать для псевдослучайных генераторов (для паролей)!
Часто применяют блочные шифры, для получения псевдослучайных генераторов, а также эллиптические кривые и решения дифференциальных уравнений — и на то есть свои причины, но я (пока?) не буду их трогать.
[*] Handbook of Applied Cryptography, A. Menezes, P. van Oorschot, S. Vanstone.
UDP: Автор аккуратной картинки — bad_guy
