id: Гость   вход   регистрация
текущее время 05:13 20/11/2017
Автор темы: Вий, тема открыта 25/04/2010 20:20 Печать
Категории: криптография, алгоритмы, хэширование, случайные числа
https://www.pgpru.com/Форум/Криптография/СуществутЛиАбсолютноСлучайныеАлгоритмы
создать
просмотр
ссылки

Существуют ли абсолютно случайные алгоритмы?


Возьмем хеш-функцию и бильярд. На столе есть некоторое количество шаров. Общее число вариантов расположения шаров может быть просто невероятным. Причем новое число получается с каждым новым ударом по битку, при этом за всю историю бильярда и, видимо, за все время его существования в будущем. Кажется у нас получилась идеальная функция – внесение одного нового возмущения дает неповторимую последовательность бит. Но столь ли случайно все-таки новое число? Ведь новая последовательность получена за счет изменения позиции не всех, а двух или трех, реже четырех – пяти шаров. В остальном никакой новой энтропии нет и ее можно просто не брать в расчет. Теоретически для получения абсолютно новой последовательности бит нужно каждому шару придать свое независимое возмущение, но для реальных хешей часто встречается ситуация, когда изменение входного значения как раз очень не велико. Следует ли из этого, что в любой из хеш функций существуют уязвимости подобного рода? Или же существует теория о возможности создания совершенного алгоритма...?



 
Комментарии
— Гость (26/04/2010 03:15)   <#>
Вий, вы меня пугаете...
— Гость (26/04/2010 03:54)   <#>
О, Вий проснулся! Отсюда и далее по треду, а также гуглить Куртуа site:pgpru.com.
Следует ли из этого, что в любой из хеш функций существуют уязвимости подобного рода?
Да, и это следует уже из самого определния хэш-функции, и, более того, как показывают недавние новости, это сугубо теоретическое свойство всё ближе подбирается к вполне практическому тупику.
— unknown (26/04/2010 10:18, исправлен 26/04/2010 11:26)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Бильярд — это недерминированная система. Из одного исходного расположения шаров всегда получается разный конечный результат, который нельзя точно воспроизвести. Можно сказать, что бильярд — это генератор истинно случайных чисел — TRNG (неважно насколько аккуратный), который за определённое число раундов извлекает случайные числа из реакций человека с механическими предметами и из шумов окружающей среды (вибрации, микропотоки воздуха и прочие главным образом механические взаимодействия.).


Хэш-функция детерминирована и работает с дискретными величинами. Это как если бы вместо шариков расположили шашки на шахматной доске и двигали их по строго определённому правилу — каждое новое положение в зависимости от предыдущего без возможности игроков делать свободный выбор и самим вносить случайность в процесс.


Для того, чтобы малое изменение давало такой же эффект, как и большое, в хэш-функциях и блочных шифрах есть диффузия и лавинный эффект (что не так эффективно проявляется в бильярде). Даже если за один раунд изменение неполное, то за много раундов оно становится всё более идеальным. За полное число раундов поиск отличий от идеала должен требовать больше затрат, чем перебор грубой силой. Как если бы в бильярде случайное число считали после множества ударов.


Или тогда уж барабан с лотерейными шариками. Пусть их исходно засыпят туда упорядоченно. После одного раунда прокручивания барабана, если высыпать шарики, то они будут не слишком хорошо перемешаны, но чем больше прокручиваний — тем ближе к идеалу. После определённого числа раундов можно добиться, чтобы затраты на поиск отличий от случайного распределения были 2128, например (если все остальные параметры машинки не дают отклонений). Вообще сравнение всё равно слишком некорректно.


Алгоритм может быть детерминированным (stateful), когда на вход поступают только определённые данные; рандомизированным (randomised), когда на вход поступают обрабатываемые данные и вторым потоком — случайные (которые нельзя произвольно воспроизвести и повторить по собственному желанию).


Случайный оракул не укладывается в эту классификацию (он попеременно то stateful, то randomised, в зависимости от поступающих значений и состояния памяти). Хэши (которые в общем случа stateful) сравнивают с ним. Бильярд (который ближе к true random, чем даже randomised) нельзя сравнивать со случайным оракулом. Что в такой терминологии будет "случайный алгоритм" — неясно.


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

Если на поиск любого различителя от RO требуется меньше времени, чем на простой перебор, то да. Можно ли на основании последних новостей утверждать, что такая ситуация неизбежна и построение идеального алгоритма невозможно в принципе?


Это потребует серьёзных доказательств (кстати, недоказано и обратное):


  1. Что число неизвестных различителей всегда будет оставаться или бесконечным или достаточно большим.
  2. Что затраты на поиск очередного неизвестного различителя также требуют (и всегда будут требовать) меньше работы, чем перебор грубой силой. Но это не поможет справиться с пунктом "1" — найти все различители.
  3. Что создать функцию, стойкую против всех возможных различителей невозможно (следствие из "1" и "2").

В криптографии принято (бездоказательно) считать, что по мере накопления знаний происходит движение к созданию идеального алгоритма (асимптотически, с периодами и колебаниями). Т.е. несмотря на увеличения числа знаний и скорость их накопления, возможностей осуществления практических взломов будет всё меньше и они будут происходить всё реже.


P. S. Общие модели построения систем и самая общая терминология описаны в /FAQ/Криптография: общие вопросы.

Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3