Aris Adamantiadis, исследователь безопасности из Бельгии, развивающий проект libssh (http://libssh.org), опубликовал (http://blog.0xbadc0de.be/archives/155) рабочий прототип приложения (https://github.com/arisada/dualec_poc), подтверждающего теорию о возможном наличии бэкдора в алгоритме генерации псевдослучайных чисел Dual EC DRBG (http://ru.wikipedia.org/wiki/Dual_EC_DRBG), до недавних пор входящим в стандарт NIST SP 800-90 и использованном по умолчанию в продуктах Bsafe и RSA Data Protection Manager от компании RSA.
Алгоритм Dual EC DRBG, описывающий способ генерации псевдослучайных чисел на основе методов криптографии по эллиптическим кривым, был разработан и продвинут в состав стандарта Агентством национальной безопасности США (АНБ). Теоретические опасения о возможных проблемах в Dual_EC_DRBG были опубликованы (http://www.schneier.com/blog/archives/2007/11/the_strange_st... ещё в 2007 году, но всерьёз они насторожили общественность лишь в сентябре 2013 года, после публикации Эдвардом Сноуденом материалов, свидетельствующих о работе АНБ по внедрению бэкдора, кардинально упрощающего предсказание генерируемых через Dual_EC_DRBG последовательностей.
После появления этих сведений компания RSA и Национальный институт стандартов и технологий США (NIST) выпустили рекомендации не использовать Dual_EC_DRBG. В декабре появились новые материалы (http://www.reuters.com/article/2013/12/20/us-usa-security-rs... указывающие на заключение секретного контракта между АНБ и RSA, размером в 10 млн долларов, подразумевающего применение Dual_EC_DRBG в качестве алгоритма по умолчанию в Bsafe.
Суть проблемы в Dual_EC_DRBG связана с наличием в рекомендованной стандартом эталонной реализации алгоритма нескольких констант, которые потенциально могут быть связаны с наличием скрытого решения, известного только тем, кто знает параметры генерации данных констант. Подобное скрытое решение не исключает возможность определения состояния генератора случайных чисел, достаточного для предсказания выводимой случайной последовательности, при наличии данных об уже сгенерированных 32 случайных байтов.
Aris Adamantiadis сумел успешно продемонстрировать возможность предсказывать выдаваемые на выходе значения, используя лишь одну изменённую константу в Dual_EC_DRBG. Весь код и инструкции, позволяющие повторить эксперимент, опубликованы (https://github.com/arisada/dualec_poc) на GitHub. Параметры генерации констант, указанных в стандарте NIST, остаются известны только АНБ. При этом данные константы обязательны для использования в неизменном виде при прохождении сертификатции по FIPS 140-2.
<font color="#461b7e">
aris@kalix86:~/dualec$ ./dual_ec_drbg_poc
s at start of generate:
E9B8FBCFCDC7BCB091D14A41A95AD68966AC18879ECC27519403B34231916485
[omitted: many output from openssl]
y coordinate at end of mul:
0663BC78276A258D2F422BE407F881AA51B8D2D82ECE31481DB69DFBC6C4D010
r in generate is:
96E8EBC0D507C39F3B5ED8C96E789CC3E6861E1DDFB9D4170D3D5FF68E242437
Random bits written:
000000000000000000000000000000000000000000000000000000000000
y coordinate at end of mul:
5F49D75753F59EA996774DD75E17D730051F93F6C4EB65951DED75A8FCD5D429
s in generate:
C64EAF10729061418EB280CCB288AD9D14707E005655FDD2277FC76EC173125E
[omitted: many output from openssl]
PRNG output: ebc0d507c39f3b5ed8c96e789cc3e6861e1ddfb9d4170d3d5ff68e242437449e
Found a match !
A_x: 96e8ebc0d507c39f3b5ed8c96e789cc3e6861e1ddfb9d4170d3d5ff68e242437
A_y: 0663bc78276a258d2f422be407f881aa51b8d2d82ece31481db69dfbc6c4d010
prediction: a3cbc223507c197ec2598e6cff61cab0d63a89a68ccffcb7097c09d3Reviewed 65502 valid points (candidates for A)
PRNG output: a3cbc223507c197ec2598e6cff61cab0d63a89a68ccffcb7097c09d3</font>
URL: http://blog.0xbadc0de.be/archives/155
Новость: http://www.opennet.me/opennews/art.shtml?num=38768
> с наличием в рекомендованной стандартом эталонной реализации алгоритма нескольких константУ кого паранойя, в Linux подобные константы тоже могут поменять на свои,
пусть упадёт суммарная криптостойкость, но не будет бэкдоров.Елси память не изменяет, копать где-то в drivers/char/random.c иль типа того.
---
Кстати эти патчи https://lkml.org/lkml/2013/9/9/61 только в 3.13 ядро пойдут,
все предыдущие версии считаются дырявыми с "бэкдорами".
В этой области итак осталось только полтора-два дедульки, которые реально чего-то могут
в криптоанализе. Иначе и воплей бы и небыло, еслибы каждый slowpoke мог бы...
http://eprint.iacr.org/2012/251.pdf
В параграфе 3.1.1 написано, что надо сделать, чтоб всунуть свои константы.Собственно в файле drivers/char/random.c, уже есть готовые, рабочие примеры.
Просто майнтейнеры пожалели людей и не стали делать по-дефолту случайные числа
на основе полинома 2048-степени.
Гы-гы-гыhttps://www.kernel.org/diff/diffview.cgi?file=%2Fpub�...
crypto: ansi_cprng - Fix off by one error in non-block size request
commit 714b33d15130cbb5ab426456d4e3de842d6c5b8a upstream.
Stephan Mueller reported to me recently a error in random number generation in
the ansi cprng. If several small requests are made that are less than the
instances block size, the remainder for loop code doesn't increment
rand_data_valid in the last iteration, meaning that the last bytes in the
rand_data buffer gets reused on the subsequent smaller-than-a-block request for
random data.
The fix is pretty easy, just re-code the for loop to make sure that
rand_data_valid gets incremented appropriately
# head -n 10 linux-3.12/drivers/char/random.c
/*
* random.c -- A strong random number generator
*
* Copyright Matt Mackall <mpm@selenic.com>, 2003, 2004, 2005
*
* Copyright Theodore Ts'o, 1994, 1995, 1996, 1997, 1998, 1999. All
* rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditionsКакие к черту элиптические кривые?
Проблема в том, что кривые используются в продуктах RSA.
У тех, кто не использует продуктов RSA и не прикручивает себе кривые -- проблем нет.
> У тех, кто не использует продуктов RSA и не прикручивает себе кривыеА это кто на нынешний день?
>> У тех, кто не использует продуктов RSA и не прикручивает себе кривые
> А это кто на нынешний день?Все, кто не платит за http://www.emc.com/security/index.htm
Что за бредовое квакание? Те кто платит за мутную проприетарь всегда должны быть в курсе что подляны от проприетарщиков по ним плачут.
И зачем алгоритму случайных чисел общепринятые константы? Он должен быть с чем-то совместим что ли?
> Он должен быть с чем-то совместим что ли?Все ГПСЧ похожи на приготовление борща - если просто в кастрюлю с водой закинуть
немытые свеклу, картошку, капусту, ... и прокипятить, то свекла будет отдельно,
картошка тоже, ... Если всё провернуть через мясорубку, тогда получишь однообразную кашу.
А если грамотно порезать молоденькую картошку брусочками, свёколку - руками, соломкой,
капусту так же - не крупной соломкой, лучок обжарить до румяной корочки, а в бульон из
телячей голяшки добавить ложечку вина белого, специй свежемолотых, чесночка ядрёного,...
и скушать с пампушками... Эх... О чём тут тема, чёй-то я забыл?!
эк тебя торкнуло. похоже новогодний праздник удался :)
> эк тебя торкнуло. похоже новогодний праздник удался :)][эппи nЁw Йear!
>> эк тебя торкнуло. похоже новогодний праздник удался :)
> ][эппи nЁw Йear!u too )))
Всех с Новым Годом!!!
"обязательны для использования в неизменном виде при прохождении сертификатции по FIPS 140-2."
> И зачем алгоритму случайных чисел общепринятые константы? Он должен быть с чем-то
> совместим что ли?Да.
Насколько я понимаю, если говорить упрощённо, генератор псевдослучайных случайных чисел - это такая длинная формула, которая использует два опорных числа - "зерно" и своё предыдущее значение."Зерно" берётся из генераторов энтропии - то есть действительно случайных данных. Проблема в том, что эти действительно случайные данные очень медленно накапливаются, поэтому нельзя просто так взять и сгенерировать, например, мегабайт совершенно случайных данных. Потребуется много времени.
В качестве выхода из этой ситуации и были придуманы генераторы псевдослучайных чисел. Используя "зерно", они генерируют по длинной формуле большое количество с виду непредсказуемых данных, которые, однако, можно в точности воспроизвести, если знать "зерно".
Используемые в формуле коэффициенты могут делать генерируемую последовательность более или менее предсказуемой. В одном случае генерируемая последовательность может начать повторяться через миллиард сгенерированных чисел, а в другом - через какой-нибудь квинтиллион.
Стандартизуют обычно те коэффициенты, которые обеспечивают меньшую предсказуемость последовательности. В данном случае АНБ могло наоборот, намеренно стандартизировать те коэффициенты, которые способствуют генерации более предсказуемых последовательностей. Для точного предсказания результата может потребоваться какое-то число, парное константе указанной в стандарте. И это число известно только АНБ, которое и рекомендовало коэффициенты для принятия в стандарт.
> "Зерно" берётся из генераторов энтропии - то есть действительно случайных данных.Это уже борщ с майонезом, берётся в Пятёрочке, вот где настоящий источник диареи/энтропии.
> диареи/энтропии.Павлин только что придумал новый датчик случайных чисел...
> И зачем алгоритму случайных чисел общепринятые константы? Он должен быть с чем-то
> совместим что ли?Это очень зависит от того, что это за константы. Возьмем, например, самый простой для понимания его устройства и быстрый алгоритм - т.н. "xor-shift" (сразу предупреждаю - это НЕ криптостойкий ГПЧ!!!). Суть алгоритма - несколько раз повторяем над сгенерированными в предыдущих итерациях операции побитового xor и сдвиг вправо/влево на заданное количество бит. Если константа задает количество повторов базового блока xor-shift (качество "перемешивания", если в терминах борща ;) ), то от этой константы зависит период повторения псевдослучайной последовательности. Так, при одной итерации период составляет порядка 2^32-1 32-битных целых чисел, при 2 итерациях возрастает до 2^64-1, при трех - до 2^96-1 и так далее. Теоретически может быть до 2^160-1.
Или, например, в линейно-конгруентном методе (a*x+b) mod m - период не превышает 2^m и зависит от выбора a и b.
Подобные константы могут быть и в других алгоритмах
> зачем алгоритму случайных чисел общепринятые константыа зачем алгоритмам шифрования общепринятые S-матрицы? кстати, именно поэтому я предпочитаю рыбные алгоритмы, в которых S-матрицы генерятся каждый раз заново на основе ключа.
> а зачем алгоритмам шифрования общепринятые S-матрицы?Вот это тоже вызывает вопросы - а какой, собственно, алгоритм генерации S-box'ов?
т.е. если заменить одну константу на другую, то Dual_EC_DRBG станет вполне безопасным
Неа, точнее только относительно существующих бэкдоров, на весь код нужно доказывать заново.
Говорю ж - как борщ: капусты больше нормы положишь получатся Щи со свёклой, не доложишь - винегрет кипячёный.
свекольниккипяченый винегрет называется свекольник
Без констант безопаснее
Нашли применение Сноудену. Стоит к проблеме приписать его фамилию как на проблему обращают внимание. Наверно тем кто шифрует пора городить девайсы которые генерят числа на основе шума соседей и песен группы Гражданская оборона.
> девайсы которые генерят числа на основе шума соседей и песен группы Гражданская оборона.
Разработчики ГОСТ 28147-89 и его S-блоков кагбе взволнованы кражей идеи.
Наш большой брат мне как-то ближе и роднее.
> Наш большой брат мне как-то ближе и роднее.да-да, к вашим почкам он определённо ближе
Вот скажи мне как на духу, твои почки правда пострадали от большого брата?Вот мои, помнится, и правда пострадали (на самом деле нет, это было скорее символически) на манежной на концерте prodigy в 90-е, и то наверняка не было б беды, если б сам в первые ряды не лез и меня к сцене и ограждению не выдавили...
А ты-то где успел? Просто приходилось с тех пор и еще с ментами^Wнашей доблестной полицией общаться несколько раз, и на самом деле впечатление сложилось скорее положительное. И сколько с тех пор ни встречал людей, рассуждающих о почках и т.д., никто из них через это не прошел лично, и даже близко не бывал к дубинкам. Но рассуждать о почках, застенках и т.д. мастеров в последнее время слишком много...
>[оверквотинг удален]
> Вот мои, помнится, и правда пострадали (на самом деле нет, это было
> скорее символически) на манежной на концерте prodigy в 90-е, и то
> наверняка не было б беды, если б сам в первые ряды
> не лез и меня к сцене и ограждению не выдавили...
> А ты-то где успел? Просто приходилось с тех пор и еще с
> ментами^Wнашей доблестной полицией общаться несколько раз, и на самом деле впечатление
> сложилось скорее положительное. И сколько с тех пор ни встречал людей,
> рассуждающих о почках и т.д., никто из них через это не
> прошел лично, и даже близко не бывал к дубинкам. Но рассуждать
> о почках, застенках и т.д. мастеров в последнее время слишком много...Ты просто живешь за стеклом. За стеклом монитора. И с реальным миром соприкасаешься эпизодически.
Так это потому, что те кто о бесперебойной жизнедеятельности своих органов беспокоится, от органов госбезопасности предпочитает держаться подальше. Ну вот системами шифрования ихними не пользоваться, на отечественных интернет-ресурсах не регистрируется, электронную почту, если за бесплатно, на gmail.com, а не на mail.ru держать предпочитают. Вот и не страдают поэтому.
> А ты-то где успел?Повезло работать в фирме, которую рейдили.
Разработчики DES и Triple-DES волнуются что у них перехватят пальму первенства.
Они первые указали в стандарте рекомендованые S-Box. В 28147-89 нету стандартных S-Box, если бы аноним читал стандарт он бы прочитал "блоки замен являются долговременной ключевой информацией и выдаются органами уникальными каждому пользователю". То есть у двух организаций одинаковых S-Box не будет.
а правила подготовки их - в целом известны - кажись Олейник - лет 10-15 назад описывал требования к ним.
> В 28147-89 нету стандартных S-BoxСпасибо, не знал (правда, и не интересовался активно).
> Спасибо, не знал (правда, и не интересовался активно).Да, они выдаются "кем надо". Что вызывает дополнительные вопросы, ибо те кто их выдает - потенциально заинтересованные лица. И алгоритм генерации S-Box не опубликован, равно как и методика анализа того насколько то или иное содержимое S-box'ов влияет на криптостойкость. Алгоритмам с такими свойствами доверять как-то не хочется.
> Да, они выдаются "кем надо". Что вызывает дополнительные вопросы, ибо те кто их выдает - потенциально заинтересованные лица. И алгоритм генерации S-Box не опубликован, равно как и методика анализа того насколько то или иное содержимое S-box'ов влияет на криптостойкость. Алгоритмам с такими свойствами доверять как-то не хочется.Ты точно знаешь что нигде не описан? а я вот помню много публикаций в ru.crypt где ребята рассказывали как они генерятся. Может ты просто провокатор и не грамма не компетентен в этой области? Еще раз говорю - у DES те же s-box, и так же выдаются :) что не мешало быть стандарту которым пользовались.
Касабельно методики анализа - те кто в теме, знают как это анализировать - я лично помню (можно даже найти на старом CD) информацию как s-box анализируются и должны вырабатываться. Фамилию одного из ребят кто этим занимался (насколько я помню из ИнформЗащита) я написал выше. Желающий найти - найдет информацию.
> Да, они выдаются "кем надо". Что вызывает дополнительные вопросы, ибо те кто
> их выдает - потенциально заинтересованные лица.А что мешает одно в другое завернуть?
А толку - если идея в том, чтобы органы таки могли прочесть шифрованнуу переписку. Не то чтобы я от СССР (и правительственных структур вообще) чего-то другого ожидал, конечно...
> А толку - если идея в том, чтобы органы таки могли прочесть
> шифрованнуу переписку. Не то чтобы я от СССР (и правительственных структур
> вообще) чего-то другого ожидал, конечно...почитай вначале тематическую область - а потом задумайся почему Шнайдер считает ГОСТ одним из лучших алгоритмов.
> А толку - если идея в том, чтобы органы таки могли прочесть
> шифрованнуу переписку. Не то чтобы я от СССР (и правительственных структур
> вообще) чего-то другого ожидал, конечно...http://pnzzi.kpi.ua/3/03_p150.pdf,
http://archive.nbuv.gov.ua/portal/natural/Rks/2009_6/17Dolgo...
http://mia.univer.kharkov.ua/14/30140.pdfДарю. Фамилию Олейник - я вспомнил правильно.
> а правила подготовки их - в целом известны - кажись Олейник -
> лет 10-15 назад описывал требования к ним.Осталось к гадалке сходить - краты раскинуть на наличие уязвимостей и бэкдоров в:
* "в целом известны"
* в этих требованиях
* в сертифицированных реализациях
* в публично доступных реализацияхЧто откроет бабушка в цветасто юбке?!
>> а правила подготовки их - в целом известны - кажись Олейник -
>> лет 10-15 назад описывал требования к ним.
> Осталось к гадалке сходить - краты раскинуть на наличие уязвимостей и бэкдоров
> в:
> * "в целом известны"
> * в этих требованиях
> * в сертифицированных реализациях
> * в публично доступных реализациях
> Что откроет бабушка в цветасто юбке?!http://pnzzi.kpi.ua/3/03_p150.pdf - раздел "Литература". Я думаю вы просто некометентный человек в этой области. Иначе бы знали эту книгу.
а-у.. митрофанушка.. ты прочитал статьи которые я дал? все так же предпочитаешь гадать у бабки - а не пользоваться математикой? или ты ее осмыслить не можешь?
> а-у.. митрофанушка.. ты прочитал статьи которые я дал? все так же предпочитаешь
> гадать у бабки - а не пользоваться математикой? или ты ее
> осмыслить не можешь?О, я вижу ты хочешь об этом поговорить. Пока Сноуден не слил тебе, Великому Математику, закладку в позапрошлогодних алгоритмах им.RSA, ты со всеми своими статьями радостно ими пользовался (немедлеено опровергай! со сканом нотариально заверенной справки из первого отдла и паспорта). Так чем бабушка-цыганка худший криптоаналитик, чем камрад Эдвард?
а по теме сказать нету? я вижу что ты не в состоянии пользоваться гуглом и простейшей математикой.
А думать сам можешь? или только повторяешь как попугай за немытым хипи?Кстати мое выступление не конференции посвященное проблемам RSA было в 2001 году.. и причем тут Сноуден?
> Кстати мое выступление не конференции посвященное проблемам RSA было в 2001 году..Умыл, товарищ профессор. "Мои выступления". Убил. Ухожу в тину.
Последний вопрос: почему Рейтер про Сноудена писал, а про тебя не писал. Ты ж ещё в 2001-ом, да?
> и причем тут Сноуден?
""В декабре появились новые материалы, указывающие на заключение секретного контракта между АНБ и RSA
->>
""Documents leaked by former NSA contractor Edward Snowden show that the NSA created and promulgated a flawed formula for generating random numbers to create a "back door" in encryption products, the New York Times reported in September.
мои публикации были в материалах конференции технической. А сноуден в обычных СМИ растиражированных.
Хотя тебе не привыкать верить всякому бреду из СМИ :) за тебя и так подумали.Только в этой публикации говориться о backdoor в продуктах - а там проблема в самом алгоритме, и хорошо спрятаном бэкдоре там.
Хотя что говорить с некометентным и больным GNU головного мозга.
> мои публикации были в материалах конференции технической. А сноуден в обычных СМИ
> растиражированных.
> Хотя тебе не привыкать верить всякому бреду из СМИ :) за тебя
> и так подумали.
> Хотя что говорить с некометентным и больным GNU головного мозга.Да, победил же, я сказал уже.
Я понял, что Сноуден засветил спецслужбы, а ты на них работаешь.
Молодец. Победил.
Он-то её осмыслить не может, а ты, умник, не в состоянии осмыслить, что математику осмыслить тебе не по зубам.
Для реальных применений S-блоков вполне себе счетное количество. См. rfc4357.
> Для реальных применений S-блоков вполне себе счетное количество. См. rfc4357.см. ГОСТ 28147-89, страница 3 снизу. учитывая размер s-box - там очень много вариантов, от того что стандартизировали только счетное количество - не значит что использовать только их. Читаем ГОСТ - о том что s-box это долговременный ключевой элемент уникальный для каждой группы лиц.
> Разработчики DES и Triple-DES волнуются что у них перехватят пальму первенства.Про DES еще на момент разработки было ясно что он ломаемый от и до - его ключ можно брутфорсом перебрать и все кто хоть немного в курсе закона Мура знал что скоро DES будут ломать "на кухне". А triple DES просто крайне дурной алгоритм - медленный, костыльный, не факт что надежный вообще.
>> Разработчики DES и Triple-DES волнуются что у них перехватят пальму первенства.
> Про DES еще на момент разработки было ясно что он ломаемый от
> и до - его ключ можно брутфорсом перебрать и все кто
> хоть немного в курсе закона Мура знал что скоро DES будут
> ломать "на кухне". А triple DES просто крайне дурной алгоритм -
> медленный, костыльный, не факт что надежный вообще.Но криптоаналитики считали его достаточно сложным :) И на момент 56го года - это был достаточный прорыв.
Да и сейчас - достаточно чуть чуть поиграться с s-box, как результаты будут совсем другими :-)
В 56 году никакого DESа небыло, умник.
CryptoPro-A-ParamSet, который фактически везде и применяется, однозначно определяет конкретные S-блоки. То есть они одинаковы не просто у двух организаций.
мы обсуждаем проблемы конкретной реализации или проблемы алгоритма вообще?
если мы говорим о ГОСТ, то не понятно причем тут CryptoPro? или вы не можете представить что это их самодеятельность?
OK, давай еще добавим s-boxы описанные (если я не путаю) в Украинских и Белорусских стандартах. Плюс добавим s-ки, на которых шифруется взаимодействие со странными токенами имени разных криптофирм. А потом еще тот s-box, который я выписал соседу Васе "чтобы никто не догадался". По сути ты прав. S-box может выбираться/назначаться в зависимости от различных условий. Дальше "клиент" может анализировать s-box по различным критериям, начиная тупо от наличия коротких циклов. Для tls/smime/pki выбор все равно будет идти из s-ок, которые можно пересчитать по пальцам.P.S. на тему "долгосрочной ключевой информации". Когда-то читал статью, про восстановление s-box, если мы позволяем шифровать что-угодно и как угодно за разумное время (оценок сейчас не помню). Так что это просто параметр схемы, а не ключевая информация (ИМХО).