Хабр Курсы для всех
РЕКЛАМА
Большая витрина: от крупнейших школ до частных авторов. Сравнивайте по цене, длительности, формату и выбирайте самый подходящий курс!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 50
Все вполне понятно, если знаешь что такое асимметричная криптография. Идея от Дифи-Хелмана ничем не отличается, поэтому почитав википедию и осознав его, даже не подготовленный читатель сможет понять и эту статью. Автору спасибо.
Такие пироги.
Автор просто пересказал комментарий с Crypto.StackExchange, ссылку на который ему дали в прошлой статье.
У меня только два вопроса:
1. Почему для этого «объяснения» потребовалась отдельная «статья», ведь можно было дополнить первую — в комментариях как раз высказывалась мысль, что было бы неплохо раскрыть суть;
2. Почему в этой «статье» нет ссылки на первоисточник, коли уж по сути это «перевод».
У меня только два вопроса:
1. Почему для этого «объяснения» потребовалась отдельная «статья», ведь можно было дополнить первую — в комментариях как раз высказывалась мысль, что было бы неплохо раскрыть суть;
2. Почему в этой «статье» нет ссылки на первоисточник, коли уж по сути это «перевод».
Насколько я знаю, для числа, учавствующие в работе подобных алгоритмов (в частности — на модулярной арифметике), должны удовлетворять сложным математическим критериям, чтобы как раз не возникало такого. Те же генераторы ключей отбрасывают их, если они не удовлетворяют критериям.
А можно поподробнее? Я знаю, что для конкретных криптоалгоритмов бывают «слабые» параметры. Например, для нашего ГОСТ 28147-89 бывают слабые узлы замены (s-box'ы). А про требования к параметрам асимметричной криптографии я нигде пока не читал, хотя у нас в стране их тоже выдает ФСБ, поэтому весьма вероятно, что такие требования есть.
S-Box — это из DES вообще-то. И там, действительно, бывают конкретно слабые узлы замены (как и в ГОСТе, где это называется «блок подстановки», впрочем, как и в любом другом симметричном шифре, там ни разу не достаточно «просто перемешать как придется»).
Параметры эллиптических кривых (о которых и идет речь в исходной статье), являются фиксированными параметрами конкретного алгоритма. И разработчик алгоритма их и фиксирует. Очевидно, что произвольный выбор точек на эллиптической кривой столь же опасное мероприятие, как и сочинение произвольных S-Box'ов для симметричных алгоритмов.
Параметры эллиптических кривых (о которых и идет речь в исходной статье), являются фиксированными параметрами конкретного алгоритма. И разработчик алгоритма их и фиксирует. Очевидно, что произвольный выбор точек на эллиптической кривой столь же опасное мероприятие, как и сочинение произвольных S-Box'ов для симметричных алгоритмов.
Вообще-то в ГОСТе это зовется узлом замены, а s-box — это общее понятие для элемента криптографии, использующееся дофига где.
Если честно, наличие слабых параметров для какого-то алгоритма нифига не очевидно. Например, вот обоснование слабых ключей и УЗ для ГОСТа и известно это стало далеко на в 89 году.
Покажите мне, пожалуйста, какую-нибудь статью, где будут описаны требования к параметрам (кроме требований из самого стандарта о простоте, положительности, меньше основания и др. очевидных) для какого-нибудь алгоритма на дискретном логарифме.
Если честно, наличие слабых параметров для какого-то алгоритма нифига не очевидно. Например, вот обоснование слабых ключей и УЗ для ГОСТа и известно это стало далеко на в 89 году.
Покажите мне, пожалуйста, какую-нибудь статью, где будут описаны требования к параметрам (кроме требований из самого стандарта о простоте, положительности, меньше основания и др. очевидных) для какого-нибудь алгоритма на дискретном логарифме.
Например, для задач на дискретное логарифмирование нужно брать группы с большим простым делителем порядка группы. То есть для классического Диффи-Хеллмана желательно использовать в качестве модуля «безопасные простые числа».
Позабавила цитата из сертификата от NIST:
Палево, что они не привели там seed для какого-либо PRNG, на основе которого они сгенерировали эти параметры, как и положено. И странно, что на это никто не обратил внимания.
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, на основе которого они сгенерировали эти параметры, как и положено. И странно, что на это никто не обратил внимания.
Вот о чем писал Браун — «Цифровая Крепость» :)
А кто сказал, что у АНБ есть значение e?
И вообще это не баг, а фитча ассимитричной криптографии. Если h — генератор группы, тогда всегда найдётся такое e, что g=he (mod p).
Такие же баги/фитчи есть и в цифровых подписях, например DSA или ECDSA.
И вообще это не баг, а фитча ассимитричной криптографии. Если h — генератор группы, тогда всегда найдётся такое e, что g=he (mod p).
Такие же баги/фитчи есть и в цифровых подписях, например DSA или ECDSA.
Они случайным образом взяли h и e, посчитав g. Таким образом между h и g есть отношение, о котором не знает никто, кроме АНБ. Собственно h и g должны были быть случайными, без каких либо явных отношений между ними. Самому выбрать случайные h и g опасно, они должны соответствовать ряду критериев, о которых можно забыть.
Так где подтверждения того, что АНБ сгенерировало h и e и получило g. Может быть они просто научились логарифмировать в поле за полиномиальное время..
Одно другого не исключает. Если АНБ сделало такой прорыв, то стоит порадоваться за человечество. Сам факт, что это возможно уже радует.
С другой стороны, предоставить статичные параметры алгоритма не сложно. Опасения у криптографов были, просто авторитет NIST был непоколебим. Оказалось, в мире возможно все. Проблема в криптографии в том, что хоть чему-то надо доверять: вера в стойкие начальные параметры алгоритмов, доверие CA-сертификатам, вера в качественный rand, вера в действительно стойкое хеширование и т.д. А то, во что мы верим, не всегда соответствует нашим ожиданиям.
С другой стороны, предоставить статичные параметры алгоритма не сложно. Опасения у криптографов были, просто авторитет NIST был непоколебим. Оказалось, в мире возможно все. Проблема в криптографии в том, что хоть чему-то надо доверять: вера в стойкие начальные параметры алгоритмов, доверие CA-сертификатам, вера в качественный rand, вера в действительно стойкое хеширование и т.д. А то, во что мы верим, не всегда соответствует нашим ожиданиям.
доверие CA-сертификатам
Вы до сих пор верите? Особенно, если мы говорим о правительстве?
вера в действительно стойкое хеширование
После конкурса SHA-3 я склонен доверять финалистам.
Всегда лишь один вопрос возникает: от кого защищаемся?
Если ФСБ теперь обязывает операторов теперь хранить ВЕСЬ трафик (до почты и гугла, например, даже в https), то у них тоже появилась эта отвертка?
А зачем кто-то вообще будет использовать всё значение t? Почему не брать несколько старших битов (32 или 64), а остальные игнорировать? Тогда добраться до состояния генератора спецслужбам будет не так просто.
Это не сильно усложнит жизнь спецслужбам. Криптография она такая, в ней простые и очевидные решения могут давать совершенно неожиданные результаты.
Как, хотя бы, восстановить состояние линейного конгруэнтного датчика (s'=s*N+1 mod 2^K) по последовательности старших битов {s}, если N известно? С какой стороны тут подходить, или где про это написано?
Если честно, я никогда серьезно не занимался криптоанализом, просто моя работа сильно связана с криптографией. Я бы начал с гугления, возможно это что-то прояснит. Тем не менее, я многократно читал о том, что LCG не является криптографически стойким генератором и применять его в криптографии нельзя (также как MT, WELL и т.д.)
Анализ криптостойкости RNG — нетривиальная область, я тоже был бы рад, если бы кто-нибудь из экспертов написал на хабр цикл статей «криптоанализ для чайников».
Анализ криптостойкости RNG — нетривиальная область, я тоже был бы рад, если бы кто-нибудь из экспертов написал на хабр цикл статей «криптоанализ для чайников».
Если K небольшое, можно перебрать все возможные начальные состояния и проверить, генерируют ли они такую же последовательность. Это действительно вариант, т.к. использовать длинную арифметику ради LCG вряд ли кто-то будет, обычно модуль делают небольшим, чтобы влез в регистр.
Гораздо хуже, если используют младшие биты по модулю 2^K. Тогда по одному выходу можно узнать то же количество младших битов в слелующем выходе (просто считаем по модулю 2^T вместо 2^K).
PS. К генератору из статьи это всё неприменимо, поэтому NIST и рекомендует полностью использовать выход
Гораздо хуже, если используют младшие биты по модулю 2^K. Тогда по одному выходу можно узнать то же количество младших битов в слелующем выходе (просто считаем по модулю 2^T вместо 2^K).
PS. К генератору из статьи это всё неприменимо, поэтому NIST и рекомендует полностью использовать выход
K=64 достаточно небольшое, и это сейчас не длинная арифметика. Но перебрать 2^64 состояний не очень просто. Особенно, если берутся не старшие биты, а что-нибудь вроде ((s>>32)*n)>>32, где n — нечётно, чтобы ни одного бита из s в чистом виде в результат не попало.
Но, наверное, и это вскрывается без проблем.
Но, наверное, и это вскрывается без проблем.
Зная ((s>>32)*n)>>32, можно перебирать 2^32 значений части, которая пропала после последнего сдвига, умножать на обратное n, и проверять, равны ли старшие 32 бита нулю (т.к. у s>>32 старшие 32 бита равны нулю). Подозреваю вариантов для старшей части s останется не так и много.
(прогнал тест — от 1 до 7 кандидатов получилось). Получается перебор 2^32 + 7 * 2^32.
(прогнал тест — от 1 до 7 кандидатов получилось). Получается перебор 2^32 + 7 * 2^32.
Если, скажем, n=257, то для конкретного значения x=((s>>32)*n)>>32 у нас будет примерно 2^64/n возможных значений s. Правда, они идут подряд. Но следующий шаг LCG (s'=s*N+1, где N — достаточно большое, больше 2^62) перемешает этот отрезок так, что в нём уже не разберёшься. И новое x даст фрагмент этой каши (из 2^64/n^2) элементов, которые так просто не описываются. И их всё ещё 2^48.
Можно собрать 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^32 собранных выходов + 3*2^32 перебор. Можно регулировать, получив меньше выходов, потратить больше времени на перебор. И кстати, если выход LCG будет меньше, то метод не сильно ослабится. Если будет выплевываться всего один бит, получим среднюю длину цепочки 32, то есть 32 * 2^32 = 2^37 операций.
Лучше придумать не получилось.
Почитал ещё рекоммендацию NIST, вроде там про это написано (стр. 65):
For performance reasons, ага…
For performance reasons, the value of outlen should be set to the maximum value as provided in Table 4.
For performance reasons, ага…
Ну, правильно. Шаг генератора — дорогая штука, если выбрасывать 90% выданной информации, то программе пользователя придётся работать в 10 дольше. А программам спецслужб — и того больше. Экономьте своё и чужое время, господа!
А какие есть криптографические задачи, в которых требуется на столько много случайных чисел, чтобы замедление в 10 раз RNG заметил пользователь? Как правило RNG — это соль, ключи и т.д. т.е. очень небольшие объемы данных.
Разве что использовать One Time Pad… Но его, вроде, особо не используют :)
А xor с выходом RNG сейчас уже не популярен? Раньше, вроде бы, было основным способом шифровки. Или это и есть эквивалент One Time Pad?
Да, это и есть One Time Pad :) И, несмотря на «абсолютную криптостойкость», он мало применим на практике.
Откуда у него «абсолютная криптостойкость»? Если известен фрагмент данных, который был зашифрован, то получаем фрагмент выхода RND… остальное — подбор констант и состояния, решается «грубой силой», ха-ха… А если (точнее, «поскольку») автору не повезло — то и логикой.
Под «абсолютной криптостойкостью» подразумевается, что если у нас есть идеально-случайная последовательность длинной в сообщение, которую мы передали по идеально защищенному каналу, то xor сообщения с этой последовательностью, никаким криптоанализом нельзя расшифровать, так как он не несет в себе вообще никакой информации об исходном сообщении. Если я не ошибаюсь, это доказал Шенон.
r=gs(mod p), s′=gr(mod p)
Слишком красиво и алгебраично, за что и поплатились.
Нужно было нарушить эту красоту грязными бит-операциями, например:
r=rol(13,gs(mod p)), s′=gr(mod p) xor r
И всё, тысячелетний аппарат алгебры, матанализа и т.п. тут забуксует.
Слишком красиво и алгебраично, за что и поплатились.
Нужно было нарушить эту красоту грязными бит-операциями, например:
r=rol(13,gs(mod p)), s′=gr(mod p) xor r
И всё, тысячелетний аппарат алгебры, матанализа и т.п. тут забуксует.
gr(mod p) — это не очень алгебраично: r пришло из Zp, а используется в качестве показателя степени, как элемент из Zp-1. Вряд ли анализ этого будет очень уж приятным и красивым.
Ну в данном случае мы имеет два последовательных возведения в степень в одном поле, что хитрые чекисты заменили одним. А если между ними вставить операцию «не в тему», такую как XOR или циклический сдвиг, алгебраисты с ума сойдут прятать там бекдор.
Так что берём алгоритм, разбавляем его такими грязными трюками и получаем профит, несмотря на вопли «профессионалов» о недопустимости лезть своими руками в их отточенные алгоритмы (теперь-то мы знает, откуда эти вопли).
Так что берём алгоритм, разбавляем его такими грязными трюками и получаем профит, несмотря на вопли «профессионалов» о недопустимости лезть своими руками в их отточенные алгоритмы (теперь-то мы знает, откуда эти вопли).
Извращенное усложнение алгоритма не только усложнит взлом, но и доказательство криптоскойкости, а это важнее.
Попробуйте доказать криптостойкость SHA256. Даже не представляю, куда копать.
Формальные доказатальства криптостойкости шифров мало известны (кроме одноразового блокнота).
Все доказательства опираются на гипотезы о трудноразрешимости некоторых задач, а последний алгоритм, в котором бекдор, и вообще не подвергался доказательствам.
Формальные доказатальства криптостойкости шифров мало известны (кроме одноразового блокнота).
Все доказательства опираются на гипотезы о трудноразрешимости некоторых задач, а последний алгоритм, в котором бекдор, и вообще не подвергался доказательствам.
Ну так можно ведь один раз сделать правильно а сверху еще кривым методом чтобсначала мозги тем кто математически разобраться пытается сломать, а потом уже если математики были правы будет нетронутый алгоритм.
Если доступна реализация алгоритма в исходном коде (википедия: «Также реализован в OpenSSL.»), то как они смогли спрятать закладку?
Сомнения насчет генератора от АНБ зародились в 2006-м.
Доказательства приведены в 2007-м.
По поводу этого генератора даже Шнайер высказывался в стиле «Если вам нужен генератор случайных последовательностей, то я не рекомендую использовать Dual_EC_DRBG ни под какими предлогами. Если вы хотите следовать NIST SP 800-90, используйте CTR_DRBG или Hash_DRBG».
habrahabr.ru/post/193584/
www-cs-faculty.stanford.edu/~eroberts/cs201/projects/ethics-of-surveillance/tech_encryptionbackdoors.html
Доказательства приведены в 2007-м.
По поводу этого генератора даже Шнайер высказывался в стиле «Если вам нужен генератор случайных последовательностей, то я не рекомендую использовать Dual_EC_DRBG ни под какими предлогами. Если вы хотите следовать NIST SP 800-90, используйте CTR_DRBG или Hash_DRBG».
habrahabr.ru/post/193584/
www-cs-faculty.stanford.edu/~eroberts/cs201/projects/ethics-of-surveillance/tech_encryptionbackdoors.html
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Как АНБ внедрило закладку в генератор псевдослучайных чисел