Юмор

АНБ опубликовало работу: The SIMON and SPECK Families of Lightweight Block Ciphers.

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

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

Believe us! We're here to protect you!

Обещанный ролик. Если у кого-то не смотрится, то можно скачать через savefrom.net (понадобится JS). Оригинал весит 4MB, версия с разрешением в 360p — около 2.1MB. Это 40-секундная видеозапись доклада с недавнего собрания по проекту, где выступает достаточно крутой приглашённый докладчик из очень солидного и хорошо известного в теме квантовой теории информации института.

Я убрал звук, чтобы не было совсем просто, но вы можете видеть слайды на проекторе. Догадайтесь, о чём он рассказывает, не пользуясь интернет-подсказками.^* Дам пока небольшую подсказку: тема очень серьёзная, глубокая и затрагивает самые основы представления о том, как устроен мир. Естественно, это имеет самое прямое отношение к квантовое механике, но вы всё же попытайтесь угадать тему более конкретно.

^*Особенно это unknown'а касается.

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

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

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

О петухах

Нет, это было бы сильно по-британски философским банальным. :-)

Там видно, что петух на рассвете. Что делают петухи на рассвете? Да и, вообще, что делает петух? Правильно, кукарекает. Любой учёный сразу же должен задать вопрос «почему кукарекает петух?». Можно подумать, что это из-за того, что наступает рассвет. А, может, наоборот, рассвет наступает потому, что кукарекает петух? Что будет, если взять и сделать ему тёмную? Закукарекает ли он в положенное время? А если перенести его на несколько часовых поясов, когда он будет кукарекать, по старому времени или по-новому? Что здесь причина, а что следствие? Что из чего следует?¹

На следующем слайде (в самом конце видео) изображён пожар и бегущие к нему пожарники. Соответственно, тоже возникает вопрос, что есть причина, а что следствие. Пожарники появляются, потому что пожар, или пожар появляется из-за того, что куда-то бегут пожарники? На практике-то мы знаем, что бегущих пожарников без огня не бывает: раз они бегут, значит, тому есть причины — пожар. Однако, если вдруг заставить пожарников побежать, ясно же, что пожар не появится.

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

Все помнят картинку про «correlation does not imply causation», но всё же методологически целесообразно считать при описании мира, что корреляций без каких-либо причин не бывает — принцип Райхенбаха: есть либо общая причина у событий, вызывающая их корреляцию, либо есть какие-то следствия одного из другого между событиями. Грубо говоря, для любых наблюдаемых явлений можно нарисовать казуальную (причинностную) структуру, соединив стрелками, что из чего следует.

Естетственный вопрос, который тут же возникает — совместимо ли нарушение неравенств Белла с какой-либо каузальной структурой? Оказыается, достаточно исключить циклические графы для каузальности,² принять на веру принцип Райхенбаха, отсутствие тонкой подстройки в моделях³ и невозможность построения каузальной структуры, то получится квантовая механика с нарушением неравенств Белла. Т.е., физические законы потенциально могут быть выведены из каких-то очень фундаментальных логических причинно-следственных связей. Более того, как подчёркивает автор, вывод не может порушить ни допущение скрытых параметров моделей, ни допущение сверхсветовой связи между причиной и следствием, ни допуск супердетерминизма, ни допуск возможности будущего вызать какие-либо изменения в прошлом. В общем, результат достаточно стабилен. Если совсем коротко, то главная мысль: теорема запрета каузальной структуры эквивалентна неравенствам Белла.

Докладчик — Роберт Спеккенс, PERIMETER Institute, какие-то из его наработок даже в вики попали. Сами слайды, на которых петух — тут:
https://dl.dropboxusercontent......kkens%20tutorial.pdf
а здесь — основная работа по теме.

Остальное

Полный список докладчиков и их слайды — тут. Создалось стойкое впечталение, что не попроси я организаторов их выложить на сайте, они бы об этом даже не подумали (типа «как-то не принято это»).

Краткие комментарии по некоторым другим докладам:

• В России жизни почти нет, а в Латвии — есть, причём очень серьёзно есть, теснят европейцев. Говорят, у них там уже человек 30 обретается.
• https://dl.dropboxusercontent......s/Colbeck%20Talk.pdf
  Колбек сказал, что в DI QKD наличие предрасшаренного безопасного ключа между Алисой и Бобом ломает весь протокол. Ещё один гвоздь в шумовое крипто?
• https://dl.dropboxusercontent......eBeaudrap%20Talk.pdf
  Тут на стр. 33 занимательная зоология в картинках, всё complexity zoo.
• https://dl.dropboxusercontent......a%20Torre%20Talk.pdf
  Об отличии наблюдаемой случайности от внутренней случайности в модели DI QKD (стр. 27).
• https://dl.dropboxusercontent......0Wolf%20tutorial.pdf
  https://dl.dropboxusercontent......cs/Santha%20Talk.pdf
  Туториал(ы) по коммуникационной сложности с попыткой объяснить сложные вещи простым языком. Рекомендуется к просмотру. Тут — доклад для специалистов с упоминанием оракулов и adversary-метода; буду удивлён, если кто-то его поймёт:
  https://dl.dropboxusercontent......De%20Wolf%20Talk.pdf
• Жизан подтвердил, что слабые измерения — частный случай POVM-измерений, так что да, вся шумиха по поводу того, что слабые измерения дадут что-то новое для оценок безопасности бессмыслена по определению (безопасность доказывают для произвольных измерений, т.е., POVM).
• https://dl.dropboxusercontent......s/Lee%20tutorial.pdf
  Туториал про теории сложности запросов (query). Для меня оно не очень вразумительно, но всё же понятность слайдов выше среднего.
• https://dl.dropboxusercontent......anaro%20tutorial.pdf
  Туториал по квантовым алгоритмам. Для тех троллей, которые думают, что квантовые вычисления дают ускорение всего для пары задач, была дана ссылка на сайт НИСТа со списком задач, для которых эффективнее квантовые алгоритмы, чем классические (из уже ивзестных).
• https://dl.dropboxusercontent......cs/Sikora%20Talk.pdf
  Квантовые игры, XOR-лемма, oblivious transfer — вот это всё.
• https://dl.dropboxusercontent......zemor%20tutorial.pdf
  Тут — про конструирование квантовых LDPC-кодов. Попытка рассказать очень сложные вещи простыми словами. Есть много картинок с тайным смыслом, графами и пентограммами. Где-то там сбоку вылезает топология, а, значит, и её алгебраизация. Стр. 52 — гомологии и когомологий каких-то групп. Это всё к вопросу о том, чем занимаются современные математики, и зачем это нужно. Получается, что в теории квантовых кодов исправления ошибок оно пригождается. Докладчик — чистый математик без бэкграунда в физике, как это у многих в теме КТИ бывает. Он сказал, что нужно начинать изучение с топологии, где вводятся основные понятия, а без них гомологии понятны не будут. Напомнило ссылку:

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

• Жизан взъелся на DI QKD, задав вопрос после доклада в духе «всё это ерунда; это невозможно; такого не может быть; это совершенно нормально, что доверие оборудованию и производителю имеется, иначе просто не о чем вести речь и т.д. и т.п.». Аудитория поперхнулась попкорном, докладчик тонко намекнул упомянул idQuantique... была небольшая драма. Событие записано на видео, позже выложу.
• Есть полный видик, он тоже позже будет выложен.

P.S. Интернет завлен жалобами на пробелы в ссылках. По современному стандарту %20 должен преобразовываться в пробел, а не в плюс, для последнего есть другой код. Никакого способа вставить ссылку с пробелом так, чтобы он открывалась на pgpru, нет. SATtva, это можно исправить?

The encoding used by default is based on a very early version of the general URI percent-encoding rules, with a number of modifications such as newline normalization and replacing spaces with "+" instead of "%20"

---

¹Припоминая свой деревенский опыт, должно быть так: если сделать полностью тёмную, то не закукарекает вовремя. При смене часовых поясов он собьётся с точного времени, но всё же будет стараться закукарекать, когда увидит рассвет.
²Т.е., графы типа A ⇒ B ⇒ C ⇒ A. Есть разновидности теорий, куда такие графы тоже пытаются включить, но данное рассмотрение их исключает, почему — не понял.
³Fine-tuning. Т.е., когда параметры моделей точно согласованы так, что наблюдается определённый граф, но при этом он «неустойчив»: при малейшем изменении параметра модели структура каузального графа становится невозможной.

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

Может, чего-то не хватает, но работа оформлена очень аккуратно. Они её собираются в журнал отправлять, интересно? Или это просто публикация внутреннего REPORT'а?

Принцип работы гебни (любой) — закрытость и секретность. Как они будут вам криптоанализ шифров делать, если весь их криптоанализ засекречен от начала и до конца? И книжки по нему секретны, Егоров-Бабаш там всякий, вам же сказали. Открытое общество раскрывает всё: лица, темы, методы, работы, успехи и неудачи, оно полностью прозрачно, закрытое же общество скрывает всё, у него сама идеология другая. Оно пытается выжать максимум преимуществ для себя из того, что какие-то детали знает только оно. Смысл его простой: не учите своего противника; гадьте ему везде, где можно; вредите; не помогайте ему ни в чём; не говорите ничего по существу; создавайте атмоферу непобедимой всесильной армии мира, о которой толком никто ничего не знает, но слагают целые легенды. По поведению гебни на форуме всё это видно сразу.

У них фирменный стиль такой. Даже сам стиль изложения смахивает на старые рассекреченные работы по криптографии из их ведомства.

На счёт журнала:

1. Более полную версию могут отправить в свой журнал, у них вроде есть какая-то внутренняя периодика.
2. Могут предложить как спецификацию по типу стандарта (как в своё время они присылали НИСТу SHA-1/SHA-2), чем по сути статья и является.

Криптоанализ они традиционно не публикуют, чтобы не раскрывать методов. Они публикуют отдельные алгоритмы (SHA-1, SHA-2, Skipjack, фактически даже DES, который был непреднамеренной утечкой от контрактора IBM), затем смотрят на исследования со стороны открытого сообщества. Может они хотят посмотреть, насколько открытое сообщество знает больше/меньше в области какого-то вида криптоанализа. В данном случае, например, алгебраического.

Интересно, что легковесные шифры могут иметь нишу в таких интересных для АНБ направлениях, как подслушивающие устройства и миниатюрные беспилотники.

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

и обнаруживают эффект https://ru.wikipedia.org/wiki/Плацебо – статистически подтверждаемый пример влияния сознания на материю.

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

А вот если им платить сдельно – количество пожаров возрастёт.

А вот если им платить сдельно – количество пожаров возрастёт.

А если на окладе, то или успевать на пожар не будут или не будут успевать тушить.

Подозревал, что должно быть, что-то более специфичное с этим петухом, ну типа фотоны он там наблюдает :) Пожарников не разглядел, думал — это какие-то неандертальцы там промелькнули с примитивными орудиями труда :)

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

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

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

Интернет завлен жалобами на пробелы в ссылках. <...> SATtva, это можно исправить?

Исправил, ссылки в Вашем посте тоже сделал явными.

Интересно, а можно ли представить результаты криптоанализа таким образом, что не будут раскрыты методы, которыми уязвимости шифра были получены? Так сказать, можно ли ответить АНБ симметричным образом? Есть тривиальный случай — практический взлом, когда оппонент просит расшифровать им же зашифрованное сообщение, но здесь не тот случай. Хотелось бы доказательства знания уязвимости шифра без раскрытия деталей уязвимости.


Я выложил просто для общего развития. Мир так устроен, что 99.5% всех усилий по освоению наук уходит по сути в труху абстрактную «общую образованность», которую никуда напрямую не приложишь (школа, университет, рефераты, дипломы, статьи-отписки в вестниках и карманных журналах и т.д.), и только малая часть «инвестиций в образование» доходит до собственно отдачи — нахождению чего-то нового, чего раньше люди не знали. И именно ради этого 0.5% вся система функционирует с тем или иным КПД.

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


Там дело не в абстрактном созании, а в биохимии мозга, который выдаёт сигналы всему телу.

[offtop]
Судя по тому, как в наше время тушат пожары, это примерно так и есть. :-) В детстве в деревянных царствах Томской области я видел профессионалов, они прибывали за несколько минут, выпрыгивали из кабины уже с брандсбойтами и шлангами, всё было рассчитано по секундам. Время между прибытием пожарки и началом подачи струи в пламя, кажется, было где-то секунд 15. Больше я такого в мире не видел нигде, даже на роликах в youtube, где есть тушение пожаров в разных странах и обстоятельствах. Все приезжают, потом минут 5-10 собираются, и по пожарникам видно, что им наплевать, горит — и пусть горит, лишние несколько минут им ничего не значат, всё делается с прохладцей и не торопясь, действия нескоординированы, много лишней суеты.
[/offtop]


Вуглускра поставили на научную основу. :)


Спасибо.

Интересно, а можно ли представить результаты криптоанализа таким образом, что не будут раскрыты методы, которыми уязвимости шифра были получены?

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

В старых шифрах отбраковки явных дефектов происходили очевидным образом. В новых — часто достаточно найти уязвимую характеричтику раундовой функции (дифференциальную, линейную и др.) и показать вероятность её прохождения через множество раундов. Если в старых шифрах метод получения такой характеристики приводился в работе или легко восстанавливался по сравнительно простым алгоритмам и таблицам, то в новых — непонятно как их находят. Иногда брутфорсом по какой-то выделенной непонятно как области, иногда хитрым алгоритмом, который в работе описан туманно и невоспроизводим без дополнительных сведений. Особенно это всё касается межраундовых характеристик, как раз шифров типа ARX (как эти АНБ-шные), где таблицу характеристик так просто не составить перебором, нужна хитрая линеаризация или алгебраизация.

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

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

Театр безопасности :)

http://www.youtube.com/watch?v=cDnFB5JcKfE