openPGP в России

— ressa (05/11/2013 11:11)   
Пока предмета для паники особой не вижу, т.к. на сколько мне известно он по-умолчанию не используется в ecdsa ключах в openssh. Но весть очень неприятная..

— SATtva (05/11/2013 11:19, исправлен 05/11/2013 11:22)   

Огромная просьба: не надо бездумно перепощивать сюда слоу"новости" с хабра. Мало того, что уровень некомпетентности просто зашкаливает, так ещё и писали у нас об этом без малого месяц назад.

P.S. Выкинул страницу в форум.

— unknown (05/11/2013 11:42)   
С коментами к новости^[link6] ознакомтесь.

— ressa (05/11/2013 11:48)   
Господа, извиняюсь, сносите топик.

— SATtva (05/11/2013 12:01)   

С коментами к новости ознакомтесь.

Да уж, надо было мне в поиске копнуть поглубже, раз на память бесполезно полагаться.

— unknown (05/11/2013 12:05)   
Может разбор полётов по Dual_EC_DRBG уже стоит включить в ФПП и посылать всех туда?

— Гость (05/11/2013 12:47)   

Да, добавлю.


Во-первых, unknown ссылался на ту новость ещё во времена, когда я панику по поводу ECC поднимал (года два назад), потом во время последних обсуждений по поводу АНБ и бэкдоров эта ссылка на 2007-ой год снова проскакивала, так что всё на слуху в общем-то.

— unknown (05/11/2013 13:10)   

Спасибо, я пока не рискую трогать там содержимое из-за специфического синтаксиса.

— ressa (05/11/2013 13:14)   
А что за ФПП, просветите будьте добры.

— SATtva (05/11/2013 13:15)   
Заходите^[link7] почаще в библиотеку.

— ressa (05/11/2013 13:45)   
Все, понял, Фонд Поддержки Предпринимателей Фонд Полезных Постов.
Спасибо, да. А так ты прав – я давно хочу все перечитать здесь, все никак не доберусь)

— ressa (05/11/2013 14:50)   
Процитирую интересный комментарий:

Я уже писал несколько раз в комментариях к подобным статьям на хабре, что тут open source не помощник. Ну прочитаете вы исходник, и что? Найти такую уязвимость в Dual_EC_DRBG программист не может, это может криптоаналитик. А хороших криптоаналитиков всего тысячи в мире, и я не буду удивлён, если большая часть из них прямо или косвенно работает на правительство США, а большая часть из оставшихся — на правительства своих стран.

Вот типичный пример, отлично иллюстрирующий мою мысль:
In order to keep a warning from being issued by the Valgrind analysis tool, a maintainer of the Debian distribution applied a patch to the Debian implementation of the OpenSSL suite, which inadvertently broke its random number generator in the process. The broken version was included in the Debian release of September 17, 2006 (version 0.9.8c-1). Any key generated with the broken random number generator, as well as data encrypted with such a key, was compromised. The error was reported by Debian on May 13, 2008.

— unknown (05/11/2013 15:03)   
Раз^[link8], два^[link9].

— Гость (05/11/2013 15:29)   

Я надеюсь всё же резгрестись с проблемами и продолжить коммит. Проблема не в синтаксисе, а в структурировании. Надо добавлять вопрос в нужное место. Список подразделов пока мал, они не всеобъемлющи, и их надо будет грамотно дорабатывать так, чтобы потом не приходилось всё переделывать. Ну, и добавка конкретного вопроса обычно всеобъемлющая: надо прогуглить основные ключевые слова, найти все топики с их упоминанием, всё это поднять, вспомнить, пересмотреть, перечитать, выделить ключевое, рассортировать его хронологически и только потом уже добавлять. Так, конечно, не обязательно делать, но если я знаю, что какой-то вопрос заведомо ранее обсуждался, я при его добавлении стараюсь учесть и всю старую информацию по нему, чтобы не возвращаться к вопросу вновь и держать структуру в виде «по уже добавленным вопросам все ссылки приведены», а то будет так, что внешне вроде всё есть, а реально почти всё недоделано. Из-за этого добавление каждого нового вопроса отнимает время.

— Гость (05/11/2013 15:31)   

Правильнее было бы назвать ВПК ФПК — фонд полезных комментариев, но назвали ФПП, более англоязычно.

— unknown (05/11/2013 15:35)   
Посты про эллиптику надо тогда как-то все вместе собирать, но я даже сам не могу решить, какие из них полезные. Этой темы касались часто, но в большинстве случаев только поверхностно: по принципу — пока можно обходиться без неё, то лучше её не использовать.

— Гость (05/11/2013 18:00)   
Да, будет и подборка постов с критикой эллиптики. Цель — показать, где что обсуждалось, и где озвучивались нужные аргументы, не более того. Полезность — это скорее качество для характеризации связных текстов, а не подборок ссылок. ☻

Кстати, сходу даже не припомню: вопрос о бэкдоре в ECC (как асимметричное крипто с невнятными константами) и бэкдор в ГПСЧ на эллиптических кривых как-то связаны?

— SATtva (21/12/2013 11:01)   
Reuters^[link10] пишет тут, что использование Dual_EC_DRBG в качестве умолчального ГСЧ было продиктовано не преимуществами алгоритма (детерминизм при тестировании и пр.), а соглашением с АНБ, по которому RSA Security получила $10 млн. Сумма может показаться сравнительно скромной, однако она составляет треть от всего прошлогоднего дохода криптографического подразделения компании.

— unknown (21/12/2013 11:54, исправлен 21/12/2013 11:55)   

Есть ещё и косвенный моральный ущерб от таких бэкдоров: с теоретической точки зрения на основе ECC можно было бы разработать доверяемый ГПСЧ, но теперь всё направление в глазах пользователей будет казаться скомпрометированным.

— ntldr (21/12/2013 13:25)   
ГПСЧ на основе асимметрики – не дай бог.

— unknown (21/12/2013 16:45)   
Во-первых — никто не заставляет. Во-вторых, исследователи не только из АНБ занимаются разработкой ГПСЧ, потоковых шифров и хэшей на основе асимметрики.

При всём скепсисе к практической пользе таких изысканий, есть ли аргумент, который бы убедительно закрывал всё направление этой области исследований?

— ntldr (21/12/2013 20:59)   
Исследовать можно всё что угодно, но в практической криптографии есть два аргумента: 1 – симметрика как правило оказывается надежнее (эмпирический вывод), 2 – любой практический протокол в своей основе использует симметричное шифрование, поэтому не нужно лишних сущностей если задача решается уже используемыми примитивами. Трудно представить задачу которая решается без симметрики, но легко – без асимметрики.
Вышесказанное не претендует на истину, это просто взгляд практика, глубокое внутреннее убеждение.

— unknown (22/12/2013 15:33, исправлен 22/12/2013 15:36)   

Участник Spinore (даже если предположить, что это именно он постил под гостем) часто любил приводить обратное убеждение: дескать, асимметрика опирается на какую-никакую, но обоснованную математику, а симметрика — набор уловок и запутываний, пытающихся имитировать идеальный шифр, а этот набор запутываний всегда может быть распутан. С одной стороны я где-то подтверждал и это, но сдругой стороны приводил и доводы против асимметрики.

В частности, у меня был большой /comment63447^[link11], чтобы не искать по абзацам, приведу самоцитату:

Использовать именно такие фундаментальные матпроблемы в симметричных алгоритмах пытались. Давно известен потоковый шифр и криптостойкий ГПСЧ BBS^[link12]. Перед конкурсом SHA-3 был предложен VSH^[link13] — Very Smooth Hash. Кроме непрактичности его ещё и поломали, обойдя все нижележащие "трудные математические проблемы" и на конкурс он не попал, но теоретические исследования в этой области продолжаются.
Проблемы этих алгоритмов помимо непрактичности из-за сильной тормознутости и прочей ресурсоёмкости ещё и в неполноте симуляции RO. Они не просто имеют зазор стойкости, как симметричные, они симулируют только какие-то отдельные качества RO, но вообще не симулируют другие (или заведомо очень плохо — другой уровень неполноты) и из них не склеить протокол напрямую без промежуточных хэширований/шифрований обычными симметричными алгоритмами. Тогда, спрашивается, зачем они нужны на замену традиционной симметрики ценой такой дикой негибкости, непрактичности, переусложнения, сложности создания протоколов? Т.е. они тянут за собой все недостатки асимметричных алгоритмов, которые традиционно сглаживают симметричными. А здесь выверт наоборот. Пока интересный только с точки зрения теории.

Вот ещё интересная ссылка в wiki образовалась — Provably secure cryptographic hash function^[link14]

Также, Брюс Шнайер утверждал нечто вроде, что с симметрикой всё хорошо и даже у АНБ никакого секретного прогресса в криптоанализе якобы быть не может, а вот на счёт асимметрики он почему-то считает, что получить незаметный тайный прогресс в исследованиях во взломе в тайне от открытого сообщества — возможно.

— практика (29/12/2013 07:11)   

The earlier disclosures of RSA's entanglement with the NSA already had shocked some in the close-knit world of computer security experts.

it declined to discuss how the NSA entanglements have affected its relationships with customers.

After Snowden has measured one part of this {R,N}SA entangled pair, the state of the other one became pure (that produces deterministic result after the measurements).

Martin Hellman, a former Stanford researcher who led the team that first invented the technique, said NSA experts tried to talk him and others into believing that the keys did not have to be as large as they planned.

— Хеллман, не надо генерировать такие длинные ключи! Ты что, сумасшедший параноик? Сделай покороче, этого и так достаточно.


Я могу чего-то не понимать, но вот взять если такой пример: маломощные чипы и смарткарты, где технически неоткуда взять достаточное количество рандома. В этом случае предзагруженный асимметричный ключ (или как оно там технически организовано) мог бы давать что-то полезное. По ссылке на VSH есть ещё аргумент компактности кода:

VSH can be useful in embedded environments where code space is limited.

The Zémor-Tillich hash function — A family of hash functions that rely on the arithmetic of the group of matrices SL2. Finding collisions is at least as difficult as finding factorization of certain elements in this group. This is supposed to be hard, at least PSPACE-complete. For this hash, an attack was eventually discovered with a time complexity close to 2^n/2. This beat by far the birthday bound and ideal pre-image complexities which are 2^3n/2 and 2³ⁿ for the Zémor-Tillich hash function. As the attacks include a birthday search in a reduced set of size 2n they indeed do not destroy the idea of provable security of invalidate the scheme but rather suggest that the initial parameters were too small.

Как тесен мир! Проверил по гуглу — и да, это тот тот самый^[link15] Zémor^[link16], про слайды которого было написано:

Тут — про конструирование квантовых LDPC-кодов. Попытка рассказать очень сложные вещи простыми словами. Есть много картинок с тайным смыслом, графами и пентограммами. Где-то там сбоку вылезает топология, а, значит, и её алгебраизация. Стр. 52 — гомологии и когомологий каких-то групп. Это всё к вопросу о том, чем занимаются современные математики, и зачем это нужно. Получается, что в теории квантовых кодов исправления ошибок оно пригождается. Докладчик — чистый математик без бэкграунда в физике, как это у многих в теме КТИ бывает. Он сказал, что нужно начинать изучение с топологии, где вводятся основные понятия, а без них гомологии понятны не будут.

Он^[link17] хоть и криптограф, но в PRA публиковаться не гнушается^[link18]. На официальном банкете я умудрился сесть слева от Видика и наискосок от Zémor'а, там с ними и поговорил, а то им всем вечно некогда на этих конференциях и рабочих встречах (meetings).


Очень точно и правильно сказано. С точки зрения практической реализации криптографии эти моменты, пожалуй, самые ключевые.

— теория (29/12/2013 07:12)   

Здесь было много обсуждений на эту тему, со временем они постепенно устаревали, понимание проблем эволюционировало, менялось... По правде сказать, даже то, что было не так давно написано в теме про KeccaK, я считаю содержащим изрядную долю бреда.

Наверно, тема ГПСЧ тесно связана с шифрующими примитивами, но мне проще думать в категории последних, т.к. о ГПСЧ я никогда глубоко не задумывался. Если же говорить о ГСЧ, то всё сказано тут^[link19], а ГПСЧ — это принципиального другого рода проблема. И не надо смешивать две проблемы: черпание энтропии из системных событий (аналог ГСЧ) и преобразование этой малой энтропии в энтропию большую (ГПСЧ). Мог неправильно понять, но, кажется, в некоторых методах ГПСЧ, основанных на асимметрике, пытаются сделать нечто третье: полностью детерминистичный ГПСЧ, которому вообще не нужна никакая случайность, и единственный секрет такого ГПСЧ — асимметричный (приватный?) ключ (возможно, ещё какой-то секретный seed). Если речь идёт не о третьем варианте, а о втором, то нестойкость ГПСЧ не так критична. Такой ГПСЧ мог бы быть и на симметрике и на асимметрике, у меня тут нет профессионального персонального пятого чувства, чтобы заявить, что мне какой-то из этих вариантов принципиально не нравится.

Допустим, мы пока забываем о деталях и частностях, открывая новую итерацию оффтопик-срача «симметрика vs асимметрика» (SATtva, перережь ленточку) безотносительно их применимости к конкретно ГПСЧ. Итак, я бы привёл следующие аргументы:

1. Что лучше, две толстых надёжных двери или 100 тонких?
   
   Примерно к такому вопросу сводится задание определить, что лучше: симметрика или асимметрика. Безопасность асимметрики лежит на двух тяжёлых проблемах и на латании дыр применения этих проблем (необходимость шифровать только случайные данные, заботиться о паддинге и т.д.). Безопасность симметрики лежит на куче утверждений (проблем) и натяжек, которых не две, а на порядки больше, но, с другой стороны, да, эти «проблемы» не имет статус великих, и взлом одной проблемы может означать, что ломать несколько других (но очень вряд ли все) не придётся.

2. Безопасность как симметрики, так и асимметрики — это вычислительная безопасность^[link20]
   
   Это так в полном формальном смысле этого слова, тут терминология из теории сложности^[link21] как раз кстати (и по ссылке на вики она, как и следовало ожидать, упомянута). IT-безопасности^[link22] у конвенциональной криптографии (сжимающей большие секреты в малые), как я понимаю, не может быть в принципе, и это доказано (см. ссылку, хоть это и полуочевидное утверждение).¹

3. Безусловность условна или безусловна?
   
   Что понимать под безусловностью (unconditional)? В гугле всё очень мутно на этот счёт, но многие считают безусловность синонимом IT. Я бы сказал, что да, действительно, IT-безопасность тривиально безусловна, а вот вычислительная — это вопрос. Одни могут назвать условной безопасностью только ограничение на вычислительные ресурсы атакующего, другие — только завязку на недоказанные утверждения в доказательстве безопасности, третьи — выполнение первого или второго. И это будут три разных понятия термина «условная безопасность». Для простоты я пока буду вкладывать в этот термин второй смысл из трёх: недоказанные строгим образом утверждения.

4. Если ICM и идеальный хэш определить правильным образом, то окажется, что они существуют
   
   Как гласит терминология п. 3, обычная классическая криптография является условно безопасной. Однако, принципиально ничто не мешает довести её до ума, переведя в категорию безусловной, если считать теорию сложности^[link23] математикой, а не профанацией.² Доказуемая безопасность — это переименованное и цельно тянутое понятие «hardness assumption»^[link24] из теории сложности. Собственно, на концептуальном уровне ничто не мешает строго доказать принадлежность (при каких-то условиях) взлома криптоалгоритма к определённому классу сложности, как и неравенство разных классов сложности друг другу (но этим уже теория сложности занимается, а не криптография).
   
   Под «каким-то условиями» можно понимать что-нибудь типа «атакующему доступно столько-то пар плейнтекст-шифтекст, столько-то вычислительных ресурсов в единицу времени и столько-то ресурсов памяти в единицу времени». Естественно, эти условия должны быть определены грамотным образом, иначе, если вы их сильно завысите (как это сделано для ICM), вы получите доказательство того, что ни одна реальная конструкция им не удовлетворяет. Т.е., я хочу сказать, что несуществование ICM — это парадокс определений, а не парадокс смысла понятия «безопасный блочный шифр». Unknown Кто-то может сейчас со мной не согласиться.

5. Практический криптоанализ симметрики стоит примерно на таком же нуле, как и асимметрики
   
   Яркий пример — DES. Этот алгоритм примерно столь же стар, сколь стара асимметричная криптография. Есть ли существенный прогресс в его криптоанализе? DES сейчас ломают не потому, что он криптографически слаб, а потому, что перебор 2⁶⁴ (ну, или сколько там нужно для DES) стал реальным на практике^[link25]. Выплачиваете стоимость квартиры в Мск (≈ 100k у.е.) и получаете железку, которая ломает DES за несколько минут. И это что-то типа верха достижений на текущий момент при всё том, что он был изобретён чёрти когда давно. Эти факты наталкивают на мысль, что концептуальное ускорение (не за счёт брутфорса) для взлома DES невозможно, т.е. эта задача имеет некую неуменьшаемую алгоритмическую сложность (вспоминаем п. 4).

6. Нужна ли симметрика асимметрике?
   
   Если не вдаваться в глубокие философские вопросы о практическом существовании асимметрики без симметрики^[link26], можно тоже сказать, что это спор о понятиях, как и всё остальное вышеизложенное. Можно естественным образом назвать асимметрикой криптографию, которая асимметрично шифрует случайную битовую строку, и поставить на этом точку, всё. Пусть это будет такой небольшой примитив, но его безопасноcть мы потребуем по полной. Мне кажется, что когда говорят о симметрике интуитивно, почти всегда неявно подразумевается именно этот смысл, а не асимметрика в смысле полного комбайна типа RSA+AES. В общем, взяв это определение за основу, можно отделить мух от котлет и сказать, что задачи асимметрики полностью параллельны задачам симметрики, и одна для другого в явном виде не нужна. И это обеспечит возможность честнее сравнивать одно с другим.

Вышеприведённые пункты намечают примерную дорожную карту того, что есть, и того, что можно ожидать в будущем. Из них чётко видно, что единственная финальная цель стандартной криптографии — встроить всю вычислительно стойкую криптографию в класс безусловно стойкой (в смысле использованной терминологии). На этом пути асимметричная криптография (в смысле п. 6) уже почти возле финиша, в то время как симметричная ещё только топчется на старте. Да, в силу введёных определений вы можете заявить, что сравнение не совсем честное: асимметрика — простой элемент общей схемы шифрования, а симметрика — независимая полноценная имплементация какого-то типа шифрования. Тем не менее, и то и другое — какие-то куски общей задачи по шифрованию, куски какого-то более сложного протокола, и я заявляю, что да, тот небольшой кусок, который есть асимметрика, проработан лучше, чем тот большой тяжёлый и сложный кусок, который мы называем симметрикой. Чем-то этот вывод повторяет ранее озвученный (и даже, возможно, делает его тривиальным при таких определениях/терминологии), но не во всём. Т.е., дело не в том, что

набор запутываний всегда может быть распутан,

а в том, что к задаче теории сложности одно сводится сравнительно легко (необходимо сделать, если забить на тонкости, только один пока недоказанный шаг), а другое — вообще непонятно, с какого конца начинать сводить, т.к. даже проработанной толком теории на этот счёт нет несмотря на успешную адаптацию терминологии (оракул, adversary^[link27], hardness asumpltion = provable security) и философии теории вычислительной сложности.

Не умею коротко, проще молчать. Тот случай, когда основная мысль и вывод кристаллизируется только при попытке её связно озвучить, а когда начинал писать, сам этого не понимал.

---

¹IT-безопасность требует безопасности против противника с неограниченными вычислительными ресурсами, в том числе, как я понимаю, даже неклассическими: всякими нерелятивистскими квантовыми, релятивистскими квантовыми^[link28], а также основанными на нефизических^[link29] вычислениях^[link30].
²Насколько мне известно, какие-то строгие результаты в теории сложности (не опирающиеся на гипотезы типа P≠NP) уже получены. И даже доказательство равенства классов P и NP, если оно случится, не убьёт теорию сложности, а лишь сделает это доказательство основопологающим результатом этой теории.

— фантазия (29/12/2013 07:38)   

В свете вышесказанного можно вообразить другую ситуацию: вдруг оказалось доказанным, что P=NP, и мы строго показали, что у взлома как асимметрики, так и симметрики низкий класс вычислительной сложности. Итак, то, что можно взломать легко и то и другое, доказано. Вопрос остаётся только в нахождении конкретного алгоритма, который превратит абстрактное доказательство в конструктивное.³ В этом случае «лёгкость и понятность» асимметрики могут с ней сыграть нежелательную роль, сильно упростив практическое нахождение такого алгоритма (в то время как в симметрике придётся долго распутывать концы с концами). Впрочем, любую криптографию обычно стараются делать как можно более простой⁴ при условии сохранения заявленных свойств, поэтому простота асимметрики — вполне естественное и полезное свойство, к которому стремяться и при конструировании симметричных шифров.

³Стоит отметить, что, в общем случае, это тоже непростая задача: в математике есть много теорем существования, к которым примеры не найдены до сих пор (или были найдены лишь спустя десятилетия), а также доказанных границ, к которым так и не построили алгоритмы, их достигающие. Пример последнего — найти конкретный код (метод кодирования), который достигает пропускную способность конкретного коммуникационного канала с шумом.
⁴Для упрощения доказательств и лучшей их убедительности.

— Гость (29/12/2013 11:27)   
@ressa,


Кажется, новость от 2007 и новость от 2013 разнятся, тем что, в документах Сноудена Шнаер нашёл доказательство того, что алгоритм с закладкой.

До этого, всего лишь был признан слабым. Теперь – проплачен NSA. Может новость всё таки оставить?

— unknown (29/12/2013 19:56, исправлен 29/12/2013 19:57)   

Строго говоря, там всю осень по капле выпускали эти документы. В одних утверждалось, что АНБ намеренно продвигало этот стандарт, но не было подробностей. А когда подробности появились, часть аудитории только заметила это как новость, другая часть, наоборот пропустила продолжение в духе «и так всё с ними уже ясно».

На самом деле — это примечательный момент. Компания RSA-security репутационно похоронена. Как в своё время швейцарская Crypto AG, которую, если не ошибаюсь, АНБ же и выкупило через свои подставные фирмы.

---

Полёт мыслей по поводу симметрики и асимметрики оценил, но даже особо сказать нечего.

Мелкие возражения.

Взлом DES самими криптографами на момент его создания оценивался в миллион долларов по деньгам и на спецтехнике того времени, но не для рядовых бизнес-контор, а для тех у кого уже есть доступ к разработке соответствующего оборудования. Короткую длину ключа DES, урезанную по прямому указанию АНБ, критиковали ещё в то время.

Шнайер и др. отмечают, что есть малоразвивающиеся области математики, в которых работает буквально несколько человек в мире. Считается, что в отличие от открытого сообщества, АНБ может нанимать кого-то на изучение этих областей, если сочтёт это перспективным и забежать немного вперёд. Якобы, это касается больше асимметрики.

— Гость (29/12/2013 22:30)   

Компания RSA-security репутационно похоронена

Мой цинизм подсказывает, что репутация – это миф. Вкинут деньги в больше пиара, пиарщики отпоют дифирамбы, компания получит требуемые заказы, бизнес не закроется. Через несколько лет никто, кроме кучки специалистов которые ничего не решают, и не вспомнит об эпичном провале.

— sentaus (29/12/2013 22:42)   

Через несколько лет никто, кроме кучки специалистов которые ничего не решают, и не вспомнит об эпичном провале.

Ага, кто сейчас помнит о мегаутечке с серверов SecurID...

А когда подробности появились, часть аудитории только заметила это как новость, другая часть, наоборот пропустила продолжение в духе «и так всё с ними уже ясно».

Я вот кстати увидел тут только политические новости. Если я всё правильно в 2007 году понял, тогда показали, что в стандарте существует техническая возможность бэкдора. В 2013 году появились сообщения, что АНБ этой возможностью воспользовалось. Мне как-то трудно считать АНБ полными идиотами, которые этим бы не воспользовались.

— Гость (30/12/2013 07:16)   

Интересно, как много людей при упоминании «RSA Security» думают «компания, созданная и управляемая Райвистом, Шамиром и Адельманом»? Кто-то ведь поди ещё задаёт им вопросы «ребята, создатели RSA, как же так получилось, что ваша компания — эээ...?». Я вот, например, эти вопросы тоже не знал и, когда стало интересно, лазил в вики проверить, есть ли реально какая-то связь.


По ссылке^[link32] про историю «RSA Security» написаны похожие вещи: компания не раз перепродавалась, криптографический бизнес сокращался, толковые инженеры и менеджеры из неё уходили, но какая-то остаточная репутация из-за того, что они очень давно на рынке, ещё была. И когда компания ослабла совсем, налетели птицы-падальщики (герб их помните?) и склевали полудохлый труп.


Что-то такое было, как вы писали, с алгебраическим криптоанализом^[link33], но, правда, вы позже писали и другое (цитату не нашёл) — что-то наподобие «прогресс в криптоанализе внутри АНБ может опережать на несколько лет то, что известно в открытом сообществе, но, как показывают примеры, даже то интересное, что недавно было обнаружено,^* по факту позже оказалось лишь ещё одной теоретической игрушкой, хотя когда-то на него возлагали надежды уровня "сейчас все шифры им переломаем"». Т.е. есть скептицизм по поводу того, что можно сильно оторваться от того, что уже известно в открытой науке.

История на многих примерах^** учит тому же: как правило, одно и то же приходит в голову не одному, а нескольким людям и почти одновременно, разница — пара лет, 5 лет, но не больше даже несмотря на то, что люди не знают друг друга и не читают работы коллег. Просто есть какой-то «общий фон совокупного понимания науки человечеством», и если прогресс превышает какой-то порог, достаточный для возникновения новых знаний, это увидит не один, а многие, кто внимательно к этому приглядывается. Уж, по крайней мере, в масштабах всего мира очень трудно найти что-то такое, что считалось бы трудным для всех, но лёгким для тех, кто «знает, как».

^*Тот же алгебраический криптоанализ, возможно, давно известный АНБ и лишь недавно ставший известным в открытом сообществе.
^**В том числе — история зарождения криптографии с открытым ключом.

— SATtva (30/12/2013 08:38)   

Через несколько лет никто, кроме кучки специалистов которые ничего не решают, и не вспомнит об эпичном провале.

Ага, кто сейчас помнит о мегаутечке с серверов SecurID...

А о разборках RSA Security^[link34] с Циммерманом^[link35] и о том, что в немалой мере благодаря их стараниям он попал под следствие?

— unknown (30/12/2013 10:22)   
/comment75228^[link36]:
Там всё ещё смешнее^[link37].

Сам бэкдор и защита от него были запатентованы^[link38] ещё в 2005 году. Типа, хотите использовать депонирование секрета для дешифровки трафика — вот вам способ навязать константы. Хотите избежать использование констант — вот как сделать чистый вариант без бэкдора.

Подробнее об устройстве бэкдора^[link39].

Во вторых, НИСТ как бы умывает руки, это не его стандарт, а публикация-рекомендация, на основе стандарта ANSI и пр., куда он был внедрён ранее, а авторами алгоритма было АНБ. Причём АНБ не изобрело бэкдор, оно взяло готовый патент от гражданских криптографов и опубликовало от имени своих разработчиков. Хотя, не совсем ясно, про даты с патентом и начало продвижения этого стандарта от АНБ ещё в начале 2000-х.

RSA Security была в комитете по стандартизации ANSI и вроде как была в курсе и этого патента, и того, что в стандарт можно встроить бэкдор и после его принятия включила в свою программную библиотеку.

Наконец, ANSI и ISO, стандартизировали аналогичный алгоритм Микалли-Шнора. В нём, как в чисто ассиметричном, самом по себе нет ничего плохого, но в стандарт внесены необъяснимые константы, которые также могут содержать бэкдор, основанный на знании факторизации. Пока даже теоретически неясно как это может в точности работать, но злонамеренный выбор констант с большой вероятностью может давать такую возможность. Правда, этот стандарт нигде не применяется.

— Гость (05/01/2014 18:14)   

R^[link40]on Rivest, Adi Shamir and Leonard Adleman developed the RSA encryption algorithm in 1977. They founded RSA Data Security in 1982.

R^[link34]SA Data Security (RSADS, ныне RSA Security, http://www.rsasecurity.com) – это американская компьютерная компания-разработчик, основанная в 1983 году авторами алгоритма RSA: Роном Райвестом, Ади Шамиром и Леном Адлманом.

К^[link42] несчастью, последний бит каждого байта в ключе является битом четности, так что эффективная длина ключа составляет только 56 бит.

С помощью дифференциального криптоанализа и атаки на основе подобранного открытого текста можно найти ключ DES, используя 2⁴⁷ открытых текстов.

Линейный криптоанализ еще более эффективен против DES. Это схожая техника, однако другая, открытая Мицуру Мациу в 1993 году, с помощью которой можно провести против DES атаку на основе 2⁴³ известных открытых текстов.

Но с 3DES там посложнее будет (см. ту же ссылку).


Спасибо. Интересный разбор. Тут ещё в тему из википедии^[link43]:

Berry Schoenmakers and Andrey Sidorenko publishes a Cryptanalysis of the Dual Elliptic Curve Pseudorandom Generator, showing that emperically the output from Dual_EC_DRBG can be distinguised from random bits, concluding that Dual_EC_DRBG is insecure as a CSPRNG. (note that this is a separate problem from the backdoor)

NIST SP 800-90A is published, includes Dual_EC_DRBG with the defects pointed out by Kristian Gjøsteen and Berry Schoenmakers and Andrey Sidorenko not having been fixed.

Не буду показывать пальцем Боюсь спросить, родственники читателей pgpru.com случаем криптографией не подрабатывают? :)


Его описания даже в вики нет (но есть упоминания), хотя в интернете есть много страниц по теме.

— unknown (05/01/2014 19:04)   

Это вы про открытие Коблица-Миллера^[link44]? :)

— Гость (05/01/2014 19:59)   
Нет, хотя это тоже интересное наблюдение. ☺ Я про ассоциативный ряд «Andrey Sidorenko (Dual_EC_DRBG) ↔ sentaus^[link45] ↔ https://vk.com/id2610335».

Тут кто-то недавно активно ругался на соцсети... Хотя если кому-то «ничто человеческое не чуждо», то чего бояться удивляться?

— Гость (05/01/2014 20:15)   

He is also the inventor of Miller's Algorithm which is of fundamental use in pairing-based cryptography. © V. Miller^[link47]

Такой молодой, а уже эпоним^[link48]!

— Гость (05/01/2014 20:22)   

Бывает и такое, но чаще СВЧ излучение используют для борьбы с муз.центрами соседей. Должно быть несколько сложней чем просто открытая дверца микроволновки, но так же беспощадно. Впрочем, никаких инопланетян.

— Гость (06/01/2014 02:10)   
Так значит права была Наталья Половко, не всегда это чека и не всегда пси, но облучают!

— Гость (07/01/2014 02:14)   

In general, Complexity Theory is related to cryptography, where the letter is broadly defined as the study of systems that are easy to use but hard to abuse. Typically, such systems involve secrets, randomness, and interaction as well as a complexity gap between the ease of proper usage and the infeasibility of causing the system to deviate from its prescribed behavior. Thus, much of cryptography is based on complexity theoretic assumptions and its results are typically transofrmations of relatively simple computational primitives (e.g., one-way functions) into more complex cryptographic applications (e.g., secure encryption schemes).

In view of the central role of randomness in complexity theory (as evident, say, in the study of pseudorandomness, probabilistic proof systems, and cryptography), one may wonder as to whether the randomness needed for the various applications can be obtained in real-life. One specific question, which received a lot of attention, is the possibility of ``purifying'' randomness (or ``extracting good randomness from bad sources''). That is, can we use ``defected'' sources of randomness in order to implement almost perfect sources of randomness. The answer depends, of course, on the model of such defected sources. This study turned out to be related to complexity theory, where the most tight connection is between some type of randomness extractors and some type of pseudorandom generators.

Indeed, modern cryptography is strongly coupled with Complexity Theory (in contrast to "classical" cryptography, which is strongly related to information theory).

© Oded Goldreich, «Computational complexity, а conceptual perspective». Cambridge University Press, 2008. Введение и часть цитат доступы здесь^[link50]. Замечательные эпиграфы из той же книги:

A good disguise should not reveal the person's height. © Shafi Goldwasser and Silvio Micali, 1982.

A good disguise should not allow a mother to distinguish her own children. © Shafi Goldwasser and Silvio Micali, 1982.

A world of a Gentleman is better than a proof, but since you are not a Gentleman — please provide a proof © Leonid A. Levin (1986).

Ещё там на глаза попались интересные теоремы (наверное, для специалистов они очевидны) о глубоких связях одних вещей с другими. Кажется (боюсь переврать), (a) существование односторонних (one-way) функций, (b) существование подписей, устойчивых к атакам с подобранным текстом, и (c) существование стойкой аутентификации(?) — эквивалентные друг другу утверждения.

Превосходная книжка, рекомендую. Годрайх как всегда на высоте. Очень интересно, глубоко, концептуально и доступно описано. Видно, что это «труд жизни» на сотни страниц, где выстрадано каждое слово. Тот случай, когда пишут так, чтобы потом можно было взять любую цитату из книги и сразу отлить её в граните.

---

Помимо Годрайха я посмотрел, что ещё сейчас хранят на своих полках большие люди, которые слишком много знают¹. Обнаружилось:

1. Китаев, Шень, Вялый. «Классические и квантовые вычисления». МЦНМО-ЧеРо, 1999.
2. Yves Vandriessche. «A foundation for quantum programming and its highly-parallel virtual execution». PhD thesis, VUB, 2012.
3. Robert Spalek. «Quantum algorithms, Lower Bounds, and Time-Space Tradeoffs». PhD thesis, Universiteit van Amsterdam, 2006.
4. Noson S. Yanofsky, Mirco A. Mannucci. «Quantum computing for computer scientists». Cambridge University Press, 2008.²
5. Philipp Kaye, Raymond Laflamme, Michele Mosca. «An introduction to Quantum Computing». Oxford University Press, 2010.
6. N. David Mermin. «Quantum computer science, an introduction». Cambridge University Press. 2007.
7. Willi-Hans Steeb, Yorick Hardy. «Problems and solutions in quantum computing and quantum information». World Scientific, 2006.
8. Sanjeev Arora, Boaz Barak. «Computational complexity, a modern approach». Cambridge University Press, 2009.

Сразу оговариваюсь, что я не проверял наличие этих книг хотя бы каком-то виде в сети. Помимо книги Голдрайха стоит отметить восьмую ссылку. Пожалуй, это самая современная книжка по теме. Её черновые версии доступны^[link51]. Обратите внимание на подбор тем и топиков: они существенно отличаются от тех, что описаны в стандартных книжках. В частности, некоторые главы по ссылке:
Напоминаю, что это книга — не какая-нибудь «Cryptography», а «Computational complexity, a modern approach». Ну, чтоб прочувствовать.

Помимо вышупомянутых были обнаружены следующие две чисто классических (не содержащих информацию про квантовые вычисления) книжки:

1. Christos H. Papadimitriou. «Computational complexity». Addison-Wesley, 1994.
2. Michael Sipser. «Introduction to the theory of Computation». Cengage Learning, 2013.

Последняя содержит какие-то параграфы по (классической) криптографии.

P.S. Это так, в качестве грубого ориентира на предмет того, что стоило бы в наше время читать.


Термины time/space complexity из теории сложности соответствуют расходам на брутфорс по памяти и по количеству операций в современной криптографии?

---

¹Тут ранее кто-то уже интересовался^[link56] ссылками на литературу.
²Цитата из книжки:

Computer science is no more about computers^[link57] than astronomy is about telescopes © E.W. Dijkstra^[link58].

³Эпиграф к главе:

Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin. © John von Neumann, quoted by Knuth, 1981.