Мне кажется, функция перехода между состояниями достаточно похожа на случайную, поэтому в среднем будет цикл длины порядка sqrt(порядок g). И я сомневаюсь, что NIST/NSA/кто-либо другой в состоянии проверить, что длина цикла достаточно длинна (тем более, что при различных S могут получаться различные циклы и все их найти/проверить просто нереально).
Кроме того, никто не мешает оставить «заапрувленное» NIST'ом g (P на кривой) и выбрать случайно h (Q на кривой). Период последовательности зависит только от g, а выход при этом будет совсем другой.
Можно собрать 2^32 выходов этого генератора (не так просто конечно, но все же возможно). И потом брать случайное состояние s от 0 до N-1, с вероятностью 1/2^32 оно попадет в то, что мы собрали. Проверив K выходов, начиная с этого состояния, можно убедиться, что оно верное (при выходе LCG в 16 бит получается в среднем 1-3 шага вперед нужно проверить). Дальше несложно вычислить последнее состояние, и угадывать последующие выходы LCG.
Сложность получается 2^32 собранных выходов + 3*2^32 перебор. Можно регулировать, получив меньше выходов, потратить больше времени на перебор. И кстати, если выход LCG будет меньше, то метод не сильно ослабится. Если будет выплевываться всего один бит, получим среднюю длину цепочки 32, то есть 32 * 2^32 = 2^37 операций.
Для атаки в лоб (поиск коллиззии 2 рода) на md5 необходимо примерно 2^64 операций (т.к. хэш 128 битный). В те годы это было заоблачным числом операций, да и сейчас это не мало. Зато сейчас практически любая слабость md5 позволяет атаке стать реальной (что и вышло на практике).
Хотя на вики написано, что для того же SHA1 есть теоретическая атака за 2^69 операций (причем еще в 2005 году). Странно, что до сих пор не нашли хотя бы одну коллизию…
Проблема в том, что можно подписать одно, а использовать другое. Да, для «связного текста» это практически нереально, зато в бинарных файлах — запросто. Вот тут хороший пример, почему коллизии второго рода — это плохо.
Зная ((s>>32)*n)>>32, можно перебирать 2^32 значений части, которая пропала после последнего сдвига, умножать на обратное n, и проверять, равны ли старшие 32 бита нулю (т.к. у s>>32 старшие 32 бита равны нулю). Подозреваю вариантов для старшей части s останется не так и много.
(прогнал тест — от 1 до 7 кандидатов получилось). Получается перебор 2^32 + 7 * 2^32.
Да вроде в курсе. Был когда-то. Забыл видимо.
И все-таки, мне интересно, почему нельзя взять рандомные точки на кривой; и какое кольцо они должны породить
Если K небольшое, можно перебрать все возможные начальные состояния и проверить, генерируют ли они такую же последовательность. Это действительно вариант, т.к. использовать длинную арифметику ради LCG вряд ли кто-то будет, обычно модуль делают небольшим, чтобы влез в регистр.
Гораздо хуже, если используют младшие биты по модулю 2^K. Тогда по одному выходу можно узнать то же количество младших битов в слелующем выходе (просто считаем по модулю 2^T вместо 2^K).
PS. К генератору из статьи это всё неприменимо, поэтому NIST и рекомендует полностью использовать выход
To avoid using potentially weak points, the points specified in Appendix A.1 should be used. However, an implementation may use different pairs of points, provided that they are verifiably random, as evidenced by the use of the procedure specified in Appendix A.2.1 below, and the self — test procedure in Appendix A.2.2
Палево, что они не привели там seed для какого-либо PRNG, на основе которого они сгенерировали эти параметры, как и положено. И странно, что на это никто не обратил внимания.
Например, для задач на дискретное логарифмирование нужно брать группы с большим простым делителем порядка группы. То есть для классического Диффи-Хеллмана желательно использовать в качестве модуля «безопасные простые числа».
Эти «скульптуры» конечно выглядят получше простой рандомной мешанины из полигонов, но всё же отличить их от обычных моделей достаточно просто. Про скрытность передачи тут говорить нет смысла
Да, основная проблема это затраты на использование шифра. И в некоторых случаях, передачу ключа (например если бы для установления ssl соединения нужно было установить общий мегабайтный ключ, первый коннект был бы оочень медленным).
Также, наверняка придумано много безопасных конструкций для использования длинных ключей применяя те же быстродействующие примитивы на маленьких ключах (хотя вот например прямолинейная конструкция как в 3DES оказалась небезопасной — атака meet-in-the-middle).
Правда, это формула для получения n-го члена последовательности, а не генерации всей последовательности.
Кроме того, никто не мешает оставить «заапрувленное» NIST'ом g (P на кривой) и выбрать случайно h (Q на кривой). Период последовательности зависит только от g, а выход при этом будет совсем другой.
gray(n) = n ^ (n >> 1)
Сложность получается 2^32 собранных выходов + 3*2^32 перебор. Можно регулировать, получив меньше выходов, потратить больше времени на перебор. И кстати, если выход LCG будет меньше, то метод не сильно ослабится. Если будет выплевываться всего один бит, получим среднюю длину цепочки 32, то есть 32 * 2^32 = 2^37 операций.
Лучше придумать не получилось.
Хотя на вики написано, что для того же SHA1 есть теоретическая атака за 2^69 операций (причем еще в 2005 году). Странно, что до сих пор не нашли хотя бы одну коллизию…
(прогнал тест — от 1 до 7 кандидатов получилось). Получается перебор 2^32 + 7 * 2^32.
И все-таки, мне интересно, почему нельзя взять рандомные точки на кривой; и какое кольцо они должны породить
Гораздо хуже, если используют младшие биты по модулю 2^K. Тогда по одному выходу можно узнать то же количество младших битов в слелующем выходе (просто считаем по модулю 2^T вместо 2^K).
PS. К генератору из статьи это всё неприменимо, поэтому NIST и рекомендует полностью использовать выход
For performance reasons, ага…
Палево, что они не привели там seed для какого-либо PRNG, на основе которого они сгенерировали эти параметры, как и положено. И странно, что на это никто не обратил внимания.
Фэйспалм.
400438 в шестнадцатеричной. 4096 это 0x1000. Ничего делить не надо, смотрим последние 3 цифры
alias hist='history | grep'
Также, наверняка придумано много безопасных конструкций для использования длинных ключей применяя те же быстродействующие примитивы на маленьких ключах (хотя вот например прямолинейная конструкция как в 3DES оказалась небезопасной — атака meet-in-the-middle).