Чем лучше сжимать диски TrueCrypt под Linux и Windows ?


Может я многого хочу. Но раньше были какие-то утилиты для сжатия информации "на лету", возможно ли сегодня повесить такое на смонтированный диск TC? В доках написано, что для ОС это обычный диск с которым можно делать все тоже самое, что и с обычным логическим диском.
Какими утилитами можно их сжимать наиболее безопасно с точки зрения вероятности потери данных в томе TC ?
Интересуют все операционные системы.

Комментарии
— Гость (20/05/2013 03:54)   
Шифротекст — случайные данные, т.е. он почти несжимаем, если вдруг имелось в виду что-то такое.

Наверное, есть файловые системы (ФС), где сжатие встроено (TC'у всё равно, какая там ФС внутри будет, т.к. шифрование происходит на более низком уровне — уровне блочного устройства).
— unknown (20/05/2013 14:53, исправлен 20/05/2013 14:55)   

Понятно, что сжимать можно или в прослойке между криптотомом и ФС, или внутри самой ФС (которая лежит на криптотоме), или поверх неё. Какие-то решения есть для всех случаев.
Гуглите Transparent compression, например BTRfs[link1] его поддерживает.


Никакого отношения к самому шифрованию это не имеет.


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

— Гость (21/05/2013 00:00)   
мне например не очень понятна терминология "диски TrueCrypt". имеется ввиду контейнер или шифрованный диск (при полнодисковом шифровании) или шифрованный раздел?
— Гость (21/05/2013 19:19)   
Вообще, тот факт, что TrueCrypt шифрует избыточные данные, а не пожатые – это уже само по себе плохо для безопасности. Файловую систему располагающуюся на "диске TrueCrypt" надо выбирать именно из соображений прозрачного сжатия данных на лету.
И не волнует, что у англичан не получилось вскрыть диск шифрованный TrueCrypt'ом. Просто они тупо пароль брутфорсили, не занимаясь криптоанализом шифрованных данных.
Да и Масленников не совсем прав, когда пишет, что теперь мол оригинальные тексты шифрованных телеграмм якобы можно спокойно показывать в телекамеры.
— unknown (21/05/2013 20:43)   

Т.е. вы утверждаете, что если, например зашифровать 264 нулей алгоритмом (на данный момент) уровня AES, то существует атака, которая по получившемуся шифртексту восстановит ключ? Опубликуйте, будет сенсация.
— Гость (22/05/2013 03:00)   
unknown,
а есть доказательство обратного? Что при ключах длинной много меньше «открытого текста» стойкость шифра никак не зависит от энтропии «открытого текста»?

«Радужные таблицы» успешно используются для взлома не только из-за слабой энтропии ключей. А так же и в случаях генерации ключей достойным аппаратным ГСЧ, но когда «открытый текст» не был пожат перед шифрованием «блочным шифром». Само собой, что «режим шифрования» сказывается, но и не служит особым камнем преткновения.

А вот хамские манеры лучше приберечь для ЛОРа и т.п. сборищ разномастных оболтусов.
— Гость (22/05/2013 03:22)   
Гражданскую криптографию в РФ никто не запрещал и не давил благодаря сочетанию сразу нескольких факторов:
  • тотальные проблемы с генерацией качественных ключей из-за отсутствия у народа аппаратных ГСЧ
  • тотальное непонимание широких масс насколько важно как можно сильнее сжимать исходный текст
  • наличие в стране мощных вычислительных центров на момент развала СССР (последствия того, что в 70-ых Глушков все же "дошел" до Косыгина)
— unknown (22/05/2013 09:47, исправлен 22/05/2013 11:00)   

Что такое модель идеального шифра?[link2].


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


Могу даже подтвердить, что теоретически такие предпосылки есть, но может вы назовёте их сами и приведёте оценку их применимости?


Что при ключах длинной много меньше «открытого текста» стойкость шифра никак не зависит от энтропии «открытого текста»?

Открытого текста? Мы говорим вроде о блочном шифре. Для блочного шифра уместно говорить о соотношении размеров ключа и размера блока открытого текста. Вот иранские криптографы пишут[link3] (как обычно в Microsoft Word :), что в некоторых случаях сложность атаки равна O(max{2n, 2k-n}) для размера блока n и размера ключа k. Есть подозрение, что с дальнейшей возможностью увеличения ключа для блочно шифра больше оптимума n = k всё тоже не так гладко.


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


Опишите модель атаки, которую можно остановить сжатием (биективным, между прочим, преобразованием).


«Радужные таблицы» успешно используются для взлома не только из-за слабой энтропии ключей. А так же и в случаях генерации ключей достойным аппаратным ГСЧ, но когда «открытый текст» не был пожат перед шифрованием «блочным шифром».

Открытый текст становится закрытым после сжатия?


На основе того, что известно в современной криптографии — сжатие (как слабая перестраховка) может слегка усложнить атаки на шифр, который является нестойким. Стойким шифром можно шифровать всё: даже тексты, которые присылает противник; показывать ему результат расшифрования и пр. — иначе шифр нестойкий и его на помойку.



К вопросу о доверии к аппаратным ГСЧ[link5].


У более софтовых генераторов с малоэффективным сбором энтропии, особенно в некоторых ОС, действительно были проблемы: раз[link6], два[link7], три[link8].


Но есть: HAVEGE: альтернативный способ получения криптостойкой энтропии из процессоров[link9].
Есть ли подходы к взлому такого генератора? Ссылки на реальные исследования были бы интересны.


Первая оценка возможности практического взлома AES: 1.5 триллиона US$ и менее года вычислений[link10].
У вас есть что добавить к той новости и обсуждениям? Что-то более аргументированное и содержательное к вопросу о методике использования радужных таблиц и современных вычислительных мощностях?


Или оценки строятся на уровне рассказов про походы одних чиновников советской эпохи в кабинеты других чиновников?

— Гость (22/05/2013 14:17)   
«Идеальная модель»(Ideal Cipher Model) в отношении стойких блочных шифров работает лишь в том случае, когда короткий «открытый текст» был вначале полностью лишен избыточности и потом «рандомизирован». Поскольку все доказательства «стойкости» идут именно из предпосылки, что «открытый текст» неотличим от полностью случайной абракадабры.

А когда длинна «открытого текста» в разы превосходит длинну ключа и используется «режим шифрования» для работы с гигабайтами информации, то в игру вступает ещё и статистическая связанность. Так же, как и при отправки большого количества независимых сообщений шифрованных одним ключем. И для ухода от неё конечно же нужно сжатие и «рандомизация» перед каждый наложением гаммы.
— unknown (22/05/2013 14:50, исправлен 23/05/2013 11:16)   

Ваши высказывания противоречат Key-dependent-PRP на уровне самого базового определения понятий.


Из определений (CPA-PRP, CCA-PRP)-security следует, что стойкость не должна зависеть от типа подаваемых со входа на выход (и обратно, с выхода на вход), данных. Про атаки со связанными, известными и подобранными ключами, уже вообще можно промолчать.


А иначе это не ICM.

— Гость (22/05/2013 14:52)   
Вот иранские криптографы пишут (как обычно в Microsoft Word :)

Вообще-то там публикация в pdf.
Да и MS Word выигрывает в стабильности, производительности и качестве отрисовки у Writer'а входящего в тот же LibreOffice.
А формат документов word'а уже давно поддерживается опенсорсными поделками и компакнее pdf'ов.
— unknown (22/05/2013 15:06, исправлен 22/05/2013 15:06)   

Экспортированная из MS Word. По кривости текста сразу видно.


выигрывает в стабильности, производительности и качестве отрисовки у Writer'а входящего в тот же LibreOffice.
А формат документов word'а уже давно поддерживается опенсорсными поделками и компакнее pdf'ов.

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


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

Не удивлюсь, если такой костыль действительно где-то применяется для поддержки какого-то устаревшего шифра, режима шифрования, протокола ("чтобы не сильно проваливался"). Для соответствия каким-нибудь устаревшим внутриведомственным инструкциям, опять же.

— Гость (22/05/2013 17:14)   
Для pdf конечно же нужен другой софт.
В ряде стран научное сообщество представленно людьми далекими от "компьютерной грамотности". Привыкшими не заморачиваться по поводу пустяков и формальностей.
— Гость (22/05/2013 17:43)   
Шифротекст — случайные данные, т.е. он почти несжимаем, если вдруг имелось в виду что-то такое.


Вы внимательно читали вопрос? Речь шла не о сжатии контейнера а о сжатии информации ВНУТРИ контейнера.
Берем файл из "нулей" размером в 100 мб, архивируем, а лишь затем шифруем – так понятно?
— Гость (22/05/2013 17:46)   
мне например не очень понятна терминология "диски TrueCrypt". имеется ввиду контейнер или шифрованный диск (при полнодисковом шифровании) или шифрованный раздел?


Все что угодно смонтированное ТС в системе как логический диск
— Гость (22/05/2013 23:09)   
У вас есть что добавить к той новости и обсуждениям? Что-то более аргументированное и содержательное к вопросу о методике использования радужных таблиц и современных вычислительных мощностях?
Или оценки строятся на уровне рассказов про походы одних чиновников советской эпохи в кабинеты других чиновников?

unknown, хамство в уютненьких и безопасных интернетах — признак малодушия. Теперь понятно, на кого в плане манер равняется публика pgpru.
Будь у unknown действительно желание разговаривать серьезно, а не просто так выпячиваться, то вёл бы себя иначе. Например, чётко определил бы, что конкретно в данном треде имеется в виду под "взломом". Возможность ли прочитать текст зашифрованный алгоритмом или же поиск ключа, с которым этот текст зашифрован. Да какова длинна открытого текста — насколько больше длинны блока или же наоборот равна. А может быть вообще меньше расстояния уникальности?
Вместо этого, наш любитель строить из себя умника, никакой конкретики не выдает. Видать оставляет для себя пути "отхода", когда прижмут к стенке начнет съезжать с темы.
— unknown (22/05/2013 23:47, исправлен 22/05/2013 23:49)   

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


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


Вместо этого он никакой конкретики не выдаёт. Оставлять пути для "отхода" ему не надо. В тему он не въезжает или просто дурачится, или пытается дурачить остальных. Чтобы затем рассказывать про мнимое хамство или ещё из каких соображений.

— Гость (23/05/2013 00:04)   
Ваши высказывания противоречат Key-dependent-PRP на уровне самого базового определения понятий.

Из определений (PPA-PRP, CPA-PRP)-security следует, что стойкость не должна зависеть от типа подаваемых со входа на выход (и обратно, с выхода на вход), данных.

В чём именно и чему конкретно противоречат? Из какой части определений следует отсутствие зависимости стойкости от энтропии «открытого текста»?
Применимо к «блочным шифрам» с ключами по длине во много раз меньше «открытого текста». И статистической связанности — как в плане «режимов шифрования» при объёмах «открытого текста» в несколько гигабайт, так и в случае анализа большой череды независимых меж собой сообщений шифрованных одним и тем же ключом.
— Гость (23/05/2013 00:13)   
В тему он не въезжает или просто дурачится, или пытается дурачить остальных. Чтобы затем рассказывать про мнимое хамство или ещё из каких соображений.

Среди криптопанков полно самоучек, незнакомых с элементарными вещами, на которых собственно и зиждется, так называемая, «современная криптография». Именно таким образом рождаются мифы и заблуждения в их среде.
А стоит чуть качнуть, так сперва агрессия с отрицанием и хамством, потом осторожное приглядывание и лишь спустя продолжительное обсуждение апатия с растерянностью.
Цель качания — дабы учились смотреть вглубь. Вместо попыток нахвататься по верхушкам и потом секреты фиговыми листочками прикрывать.
— Гость (23/05/2013 01:10)   
GnuPG и PGP используют deflate для сжатия оригинального текста перед шифрованием.
— Гость (23/05/2013 07:04)   

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


Там жуткие проблемы с форматированием не из-за того, что это Word, а из-за того, что Word катастрофически плохо работает с формулами (во всех смыслах). Проще сказать, что он их вообще не переваривает.


Вы первый день в Интернете, раз называете это «хамством»? Может, unknown'у ещё расшаркиваться перед вами нужно и «ку» делать?


— Сертификационный взлом?[link11]
— Нет, не слышали.


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

Unknown представляет здесь не срез представлений шифрпанковского сообщества,* а скорее срез академического сообщества. Модель случайного оракула и т.п. представления о криптографии — современный мейнстрим, во многом восходящий к традициям израильской школы криптографии. На основе этих представлений работает всё современное криптографическое мировое научное сообщество, включая АНБ США и НИСТ[link12]. Соответственно, своей критикой вы намекаете, что все эти организации и всё мировое сообщество — безрамитные криптопанки, а вы один на всех советский д'Артаньян. Я поэтому вам предлагаю перестать упорствовать в своём бесплодном троллинге, а взять книжку, хотя бы того же Шнайера, просветиться и перестать здесь пороть чушь, если вам зачем-то вдруг так позарез понадобилась эта пресловутая криптография. Я доходчиво объяснил? И unknown здесь ни при чём, можете не читать его переизложения основ крипто, раз ему не доверяете, а напрямую вникать в статьи, публикуемые в IACR'е, которые он для нас переводит.

*Оное в избытке представлено на других сайтах уровня несколько порядков пониже местного форума.
— unknown (23/05/2013 09:53, исправлен 23/05/2013 09:59)   

Отбросим морализаторство, но:


  1. За известными цитатами не полезу, но элементарно считается, что стойкий алгоритм не должен предъявлять никаких требований к формату шифруемых данных. Иначе это опровергает принцип (CPA-PRP, CCA-PRP)-security, как минимум. Редкие исключения строго оговариваются в рамках модели: многие режимы не позволяют подавать ключ шифрования одновременно и на вход в качестве открытого текста.
  2. Если принять гипотезу о необходимости сжатия, то из неё следовала бы невозможность создания коллизионно стойких хэшей (даже для малых блоков): при хэшировании противник знает и исходный текст, и выход хэширования, и все промежуточные состояния на всех раундах преобразований. От него нечем закрываться. Значит, по вашей гипотезе, например, построенный на бесключевой перестановке Keccak — также нестоек, а вся теория, на которой строится современная криптография — несостоятельна.

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


«Радужные таблицы» успешно используются для взлома не только из-за слабой энтропии ключей.

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

Для TMTO атак (Time Memory Trade-Off) и их разновидности TMD (Time Memory Data) и TMK (Time Memory Key) на блочные шифры — также, только это больше интересовало теоретиков, а не ломателей паролей на сайты, поэтому и менее известно. И придумано даже было раньше, чем для хэшей.

— unknown (23/05/2013 10:52, исправлен 23/05/2013 12:04)   
«Идеальная модель»(Ideal Cipher Model) в отношении стойких блочных шифров работает лишь в том случае, когда короткий «открытый текст» был вначале полностью лишен избыточности и потом «рандомизирован». Поскольку все доказательства «стойкости» идут именно из предпосылки, что «открытый текст» неотличим от полностью случайной абракадабры.

Опровергатель ICM и теории случайного оракула в треде. Обратите внимание, что на самом деле должно быть случайным в данной теории, а что — нет.


Определения по Беллейру-Рогувею давать?


A — Adversary, противник, подставляемые им данные.
D — Область перестановки.
g — оракул, на основе которого строится функция, к которой имеет доступ противник.
K — ключ.
K — ключевое пространство.
F — выбор из семейства функций по ключу F: K x D → D для перестановки.
$ — истинно случайный выбор параметра, неизвестный противнику.
Perm — перестановка
Exp — вычислительный эксперимент.
PRP — псевдослучайная перестановка.
CPA — атака с подобранным открытым текстом
b — бит ответа для выхода функции


Цель: противник должен посылать данные оракулу и определить по его ответам (найти различитель), в каком мире он находится. В мире, управляемым случайным оракулом, или в мире, управляемом исследуемой функцией криптоалгоритма.


Рассмотрим самый тривиальный CPA-различитель.


Мир номер 0: g выбирается случайно из Perm(D), т.е. g ←$← Perm(D).
Мир номер 1: g выбирается случайно из F, g ←$← F, выбор происходит за счёт случайного выбора ключа: K ←$← K и затем использования FK в качестве g


Experiment ExpFprp-cpa-1(A): Experiment ExpFprp-cpa-0(A):
K ←$← K g ←$← Perm(D)
b ←$← AFK b ←$← Ag
Return b Return b

Различитель миров с оракулами (для реального алгоритма и для случайного оракула):


AdvFprp-cpa(A) = Pr [ExpFprp-cpa-1(A)=1] – Pr [ExpFprp-cpa-0(A)=1] < ε


Если количество запросов на получение различителя меньше, чем требуется при переборе грубой силой в соответствии с областью определения перестановки и размером ключа — то это взлом (с учётом допуска на неидеальность ε, который составляет доли бита для обычных порядков 2128 … 2256 операций). Зачем уточнять про бесключевое чтение, поиск ключа? Изучение начинается с более общей модели.


Если дополните такую общую модель доказательством необходимости сжатия — будет ценная теоретическая работа :)

— Гость (24/05/2013 02:46)   

Спасибо за напоминание про ICM, идеальный шифр теперь тоже пополнен[link13], поскольку он здесь имеет очень давнюю историю обсуждений.
— unknown (24/05/2013 09:49, исправлен 24/05/2013 11:13)   

Спасибо за внимательность к важным темам.


Да какова длинна открытого текста — насколько больше длинны блока или же наоборот равна. А может быть вообще меньше расстояния уникальности?

Из какой части определений следует отсутствие зависимости стойкости от энтропии «открытого текста»?
Применимо к «блочным шифрам» с ключами по длине во много раз меньше «открытого текста».

Зачем брать крайние случаи? Дисковое шифрование относится к вычислительно стойкой безопасности. Варианты, приведённые вами, уводят в область базовых определений безопасности в информационно-стойкой модели, которая здесь неприменима.



  1. Шифрпанковское прошлое PGP даёт о себе знать. В другом творении Циммермана, при всём к нему уважении и программерскому мастерству, наш Гость и участник gegel показал кучу наивных ошибок в части крипто[link14]. Ляпы и баги в OpenSSL — из той же области. При всём уважении к разработчикам, просто лучшего особо нет.
  2. От того, чтобы пожать, конечно, хуже не будет. Но и не особо лучше: есть надежда на слабую защиту при уязвимости шифра. Но он должен быть настолько уязвим, что и так будет совсем плохо.
  3. В OpenPGP архивируется всё сообщение целиком в один сжатый файл-архив. В файловых системах это делается поблочно. Алгоритм архивирования секретом не является. Теоретически, возможно построение моделей, наподобие марковских, которые позволят подобрать за небольшое число операций, места расположения известного открытого текста внутри блоков файловой системы и подобрать вид блоков на выходе из архива. Архиватор не маскирует статистику как блочный шифр. В начале архива есть аналог словаря и определённая структура ветвления. Да, это как-то затруднит атаку, но неизвестно, насколько эффективно, потому п.2.
  4. Модели анализа сжатых файловых систем из п.3 открыто не разрабатывают, потому как неинтересно. Лучше потратить силы на создание шифров, близких к ICM, стойких режимов, протоколов шифрования и их реализаций, а не костылей с надеждой на архивирование поэтому опять п.2.
  5. В OpenPGP часто (и это исторически сложилось) шифруются текстовые сообщения эл.почты или чатов. Сжатие — это эффективный способ уменьшения их размера. И это основное его назначение.
— Гость (24/05/2013 22:40)   

В чём отличие? Или информационная стойкость = информационно-теоретическая (безусловная) безопасность?
— unknown (24/05/2013 23:41)   
Информационно-теоретической, верное уточнение. Если гость (в теме про дисковое шифрование, что внезапно) пытается нас дурачить удивить разговорами о размерах ключа больше размера текста и о расстоянии уникальности. Видимо, вводные лекции с теоремами Шеннона пытается напомнить.
— Гость (25/05/2013 01:05)   

Если речь о безусловной безопасности, то имеем одноразовый блокнот и длину ключа, равную длине текста. Если же речь о блочных шифрах, то чем особо выделен случай «длина ключа равна длине блока» — не вижу. Впрочем, выше вы уже написали какие-то общие пояснения и оценки стойкости на этот счёт.
— gyhsal (25/05/2013 23:32)   
Если речь о безусловной безопасности, то имеем одноразовый блокнот и длину ключа, равную длине текста.

Безопасность упирается не в одинаковые длинны гаммы и «открытого текста», сколько в свойства накладываемой гаммы. Должна использоваться гамма с высокой степенью энтропии и распределением символов по симметричному закону. Например, если гамму представить в виде числа в двоичной форме исчисления, то количество нулей и единиц должно быть одинаковым. Только тогда шифрование посредством «одноразового блокнота» будет являться абсолютно стойким.

чем особо выделен случай «длина ключа равна длине блока»

Работа «блочных шифров» строится не столько на наложении гаммы, но и на подстановках с перестановками. Однако, фактически их тоже можно свести к наложению гаммы.
Например, если в результате перестановок «12345» превратился в «42531», то какие бы таблицы ни выбрал бы алгоритм, руководствуясь предоставленным ключом шифрования, но в конечном итоге это аналогично наложению гаммы «38426».
Потому любой «блочный шифр» фактически сводится к генерации и наложению гаммы. Что возвращает к «одноразовому блокноту» и оценке стойкости исходя из свойств накладываемой гаммы.
— Гость (26/05/2013 01:10)   
если гамму представить в виде числа в двоичной форме исчисления, то количество нулей и единиц должно быть одинаковым.

В случайно сгенерированной битовой строке число единиц и нулей почти всегда будет разным. Если искуственно в качестве гаммы отбирать только те битовые строки, которые имеют строго одинаковое количество нулей и единиц, получим утечку информации. Можете ещё почитать про такое понятие как типичные последовательности[link15] битовых строк.
— gyhsal (26/05/2013 02:22)   
Если искуственно в качестве гаммы отбирать только те битовые строки, которые имеют строго одинаковое количество нулей и единиц, получим утечку информации.

Доказательство Шеннона абсолютной стойкости шифрования через «одноразовый блокнот» идет именно через тот факт, что гамма содержит равное количество нулей и единиц.
Только тогда в результате шифрования закон распределения окажется симметричным. Именно поэтому результат и не будет содержать вообще никакой информации из «открытого текста».
— Гость (26/05/2013 03:18)   
«Гамма содержит равное количество нулей и единиц» ≠ «закон распределения симметричный», причём ни первое не следует из второго, ни второе из первого. Возьмите монетку, киньте её 50 раз и посчитайте количество решек и орлов. Очень маловероятно, что получите ровно 25 для каждой. Аналогичным образом можете проверить и вывод ГСЧ на ПК.
— gyhsal (26/05/2013 03:55)   
А ну это то само собой, «равное» и «одинаковое» отнюдь не тоже самое, что «идентично» и «совпадать». Конечно отклонение может быть в несколько процентов. В современной истории задокументирован случай, когда человек играл в рулетку ставя на «красное» и «черное», удваивая ставку в случае проигрыша. Разорился из-за того, что «поймал» серию из семи или девяти совпадающих значений.
— Гость (26/05/2013 04:52)   
В современной истории задокументирован случай

Напомнило /comment32952[link16] и /comment33208[link17].
— unknown (27/05/2013 10:21)   
Работа «блочных шифров» строится не столько на наложении гаммы, но и на подстановках с перестановками. Однако, фактически их тоже можно свести к наложению гаммы.

Это исторически самое распространённое конструктивное решение, но само по себе не определяющее и не обязательное требование. Если посмотреть блочные шифры, основанные на смешении операций, такие как RC5[link18] или IDEA[link19], а также некоторую менее известную экзотику, то там нет раздельных слоёв подстановок-перестановок.

Потому любой «блочный шифр» фактически сводится к генерации и наложению гаммы. Что возвращает к «одноразовому блокноту» и оценке стойкости исходя из свойств накладываемой гаммы.

Это несколько упрощённо. Для описания уже давно (хотя и не в полной мере) разработаны теории PRF-PRP переходов и различителей с несколько другими ключевыми понятиями, терминологией, системой обозначений, привлекаемым матаппартом и методикой построения моделей и алгоритмов. Это не противоречит ранее использовавшемся методам, это небезуспешно пытается двинуть теорию и практику вперёд.
— Гость (27/05/2013 19:06)   
Если «блочный шифр» представить как генератор гаммы принимающий на вход ключ и «открытый текст», то чем больше будет энтропии в «открытом тексте», тем более качественная гамма получится на выходе.
Потому «открытый текст» подвергается «рандомизации» перед тем как будет использован «генератором гаммы». Это происходит с «открытым текстом» либо до начала подачи в «блочный шифр», либо уже внутри него.
Оно может происходить и в неявном виде. Например, за счет того, что алгоритм корректирует полученные результаты в конце каждого раунда. Фактически как бы подстраиваясь под неравномерность частот в «открытом тексте».

Вскрываю переписку ради того, чтобы понять содержимое «открытого текста» и для этого далеко не всегда надо заниматься поиском ключей которыми оно шифровалось.
Сжатие «открытого текста» полезно ради уменьшения объёма шифротекста доступного противнику для анализа. Одно дело вскрывать переписку, где в тексте встречается:
«Высокоуважаемый Генералисимус Верховный Главнокомандующий и Президент Первой Демократической Банановой Республики».
И совсем другое, когда содержимое «открытого текста» неизвестно. В лучшем случае можно ожидать лишь наличие нескольких служебных символов идентифицирующих формат потока, а всё остальное в этом потоке напоминает выдачу генератора случайных чисел.
— unknown (28/05/2013 12:03, исправлен 28/05/2013 12:06)   

Кажется созрело какое-то понимание разницы подходов.


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


Сжатие — самый простой, сравнительно практичный способ. Но не самый параноидальный. Как отмечено выше — это всё-таки не рэндомизация.


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


Более практично — не полурэндомизация, а преобразования "всё или ничего" All or nothing transform[link20]. Открытый текст превращается в аналог шифртекста, который можно легко расшифровать обратно всем желающим без знания ключа (он вычисляется по шифртексту). Но если хотя бы часть такого псевдошифртекста неизвестна, то обратное расшифрование невозможно (на уровне криптостойкости). Понятно, что если это преобразование ещё раз пошифровать, уже с секретным ключом, то криптоанализ крайне затруднится.


Возможна псевдорэндомизация: наложение гаммы потокового шифра и лишь затем блочное шифрование.


Второй этап понимания: почему это перестали активно изучать и внедрять?


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


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


Второй отрицаемый подход — "безопасность через перестраховки". Строят максимально возможную полную модель и алгоритм или протокол проектируют только в её рамках, не добавляя ничего лишнего поверх, ничего не предпринимая на случай, если модель не сработает, если шифр окажется нестойким (значит у вас слабый шифр, потенциально вы уже проиграли).


Так, блочные шифры проектируют в ICM-модели (допуски и оговорки включены в модель). Базовый принцип модели: CPA/CCA-security. Если противник может заставить вас зашифровать/расшифровать менее, чем 2128 подобранных открытых/шифртекстов для ключа 2128 бит и по этой информации не то что вычислить ключ, а хотя бы найти различитель от идеальной перестанвки, по которому ещё ничего нельзя взломать — то вы уже проиграли. В режимах шифрования есть утечка до 2b/2 по размеру блока и прочие тривиальные различители, учитываемые в модели. Так что, если вы пытаетесь перестраховаться за пределами принятой модели — это считается маргинальным и необоснованным.


Другой пример: традиционное асимметричное шифрование не обеспечивает CPA/CCA-security. Поэтому его используют совместно с симметричным в рамках обоснованной модели (а не только потому, что так в тысячи раз быстрее шифруется).


Такой подход позволил внедрить режим блочного шифра счётчик (CTR), где на вход шифра не нужно подавать открытого текста в явном виде вообще — сжимать открытый текст в нём не имеет смысла. Также это позволило создать универсальный криптопримив Keccak. Если Keccak не стоек как хэш, то он нестоек и как потоковый шифр, и предварительное сжатие спасать не будет. Зато избавились от этих перестраховочных костылей и переключились на более ясные и сильные модели.


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

— Гость (30/05/2013 00:44)   
Вскрываю переписку ради того, чтобы понять содержимое «открытого текста» и для этого далеко не всегда надо заниматься поиском ключей которыми оно шифровалось.

Криптоанализ любительских шифров? Продолжайте «вскрывать». Одно дело — криптография времён ВОВ, когда шифровали короткий текст типа вами прииведённого и при этом часто меняли ключи. Другое дело — криптография XXI-го века, когда одним ключом шифруют террабайты и при этом требуют криптостойкость при знании всей информации об открытом тексте. На фоне последней криптографии первая — детская безделушка, но кто-то продолжает упорно жить в мире киношных шпионов ВОВ.

All or nothing transform. Открытый текст превращается в аналог шифртекста, который можно легко расшифровать обратно всем желающим без знания ключа (он вычисляется по шифртексту). Но если хотя бы часть такого псевдошифртекста неизвестна, то обратное расшифрование невозможно (на уровне криптостойкости).

Интересная штука. Ровно то, что надо. С безусловной безопасностью можно это сделать? Что известно про максимальное количество информации, которое можно безопасно соообщить атакующему про «аналог шифртекста» и при этом не бояться взлома?

Такой подход позволил внедрить режим блочного шифра счётчик (CTR), где на вход шифра не нужно подавать открытого текста в явном виде вообще — сжимать открытый текст в нём не имеет смысла.

Грамматически и по смыслу звучит абсурдно. Как это «на вход шифра не подаётся открытый текст»? А куда ж он тогда подаётся-то? Можете пояснить эту фразу?
— Гость (30/05/2013 00:56)   
Вскрываю переписку ради того, чтобы понять содержимое «открытого текста» и для этого далеко не всегда надо заниматься поиском ключей которыми оно шифровалось.
На фоне последней криптографии первая — детская безделушка, но кто-то продолжает упорно жить в мире киношных шпионов ВОВ

Да, Гость, лучше про пытки нам расскажите, это у вас лучше получается[link21], и нам веселей послушать. А с криптографией у вас сразу не заладилось, оставьте её, не ваше это. Да и зачем вам TC со сжатием открытого текста? Всё равно ваши коллеги с паяльником, такие же как вы, выудят у вас всю информацию. Отказывайтесь от использования шифрования, пока ещё не поздно. Вы не понимаете, что кто-то использует вас втёмную, как пушечное мясо, чтобы потом вами прикрыться и подтереться. Он насоветовал вам спецсредств, трукрипты всякие, а реально они вас не защитят, только хуже сделают. Лучше работайте по-старинке: шифровки не длиннее телеграммы; шифр, проверенный десятилетиями; да про ампулу с цианидом, подшитую в воротник, не забудьте. И пребудет с вами счастье.
— Гость (30/05/2013 02:00)   
Есть разница между поиском ключа при известном открытом тексте и прочтении шифрованной переписки без поисков ключа.
— gyhsal (30/05/2013 04:20)   
Понятно, что если это преобразование ещё раз пошифровать, уже с секретным ключом, то криптоанализ крайне затруднится.

Именно это и является основной целью при расчете на долгосрочную перспективу. Какими бы хорошими ни были используемые алгоритмы «блочных шифров», а возможность лёгко и дёшево усложнить криптоанализ, отодвинув момент полной расшифровки — это вполне разумно.
Ведь никто же не пытается компенсировать недостатки системы генерации ключей или используемых алгоритмов.
Подход такой, что если увеличение степени энтропии «открытого текста» позволит выиграть лишний год-два, то игра стоит свеч. Потому как бывают ситуации, когда чем позднее будут дешифрованы перехваченные сообщения или утраченные носители информации, тем меньше людей пострадает. И тем меньше ресурсов потребуется привлекать для ликвидации последствий.
— SATtva (30/05/2013 08:24)   
Такой подход позволил внедрить режим блочного шифра счётчик (CTR), где на вход шифра не нужно подавать открытого текста в явном виде вообще — сжимать открытый текст в нём не имеет смысла.

Грамматически и по смыслу звучит абсурдно. Как это «на вход шифра не подаётся открытый текст»? А куда ж он тогда подаётся-то? Можете пояснить эту фразу?

CTR генерирует гамму, шифруя простой счётчик; гамма ксорится с открытым текстом уже отдельно. Так что, да, шифровальный алгоритм с открытым текстом в этом режиме непосредственно не взаимодействует.
— unknown (30/05/2013 10:08, исправлен 30/05/2013 13:55)   

Нет. В обычном сценарии только с вычислительной. Возможно как какую-то часть информационно-стойкого протокола можно прикрутить, но само по себе — точно нет.



При 128-битном ключе он не должен подобрать 128 неизвестных потерянных битов в тексте. Но проблема в том, что всё упирается в размер шифрующих (или преобразующих блоков). Как в губке Keccak: сначала безопасность растёт с ростом ключа, а затем остаётся константой (flat claim): за пределами 128-бит будут ломать поблочно, а не перебирать весь шифртекст. Другой вопрос, что есть много вариантов AONT, есть и более навороченные и экзотические, не все доступны моему пониманию, это малоизученное направление.



Совершенно верно. Практически, замена блочного шифра на потоковый. У Бернштейна с Беллейром (или Рогвеем, всё время их путаю :) был заочный спор: Бернштейн утверждал, что после изучения и обоснования стойкости всех режимов шифрования сообщений без аутентификации, никакой режим, кроме счётчика, не нужен якобы теперь вообще. За исключением протоколов, где нужно не просто шифрование, а именно зависящая от ключа перестановка.


Дисковое и аутентифицированное шифрование — отдельная тема. Также как non-mallebable encryption. С т.з. перестраховки на повышение стойкости есть ещё экстремальный вариант wide-block encryption: режим шифрования, при котором диффузия открытого текста происходит не в пределах блока, а по всему шифртексту (не путать с обычным CBC). Т.е. изменение одного бита в открытом тексте полностью меняет весь шифртекст и до, и после этого изменения в сообщении. Непрактично тем, что не годится для шифрования потоков — всё сообщение придётся держать в памяти или шифровать (как минимум, но не всё так просто) из начала в конец, а затем в обратном порядке. Но это для спец. протоколов, несвязанных с перестраховкой, скорее для того же non-malleable encryption, там где не впихнуть аутентификацию.


Опять же, при таком подходе, в единый блок открытого текста может быть вписан случайный IV, именно как часть открытого текста, которая будет отброшена при расшифровании, если это так надо.

— Гость (30/05/2013 18:15)   

Есть один предельный случай: половина текста — шифртекст (результат шифрования одноразовым блокнотом), а вторая половина — случайная гамма, которая использовалась при шифровании. Если знаете обе части текста, вы «расшифровываете» сообщение. Хотелось бы как-то перемешать гамму с шифртекстом, причём безусловно безопасно, так, чтобы было всё равно, какую часть битов мы раскрываем атакующему: первые n/2 из n штук или случайно выбранные n/2 из n штук, то есть, чтоб утечка информации о битах начиналась только при раскрытии n+1-го бита.

Насчёт «само по себе — точно нет» — где можно почитать доказательство невозможности?
— unknown (30/05/2013 21:39, исправлен 30/05/2013 21:49)   

Шифрование в традиционном AONT-режиме идёт поблочно, например, обычным блочным шифром. Если у вас нет целого сообщения, у вас есть обычные блоки шифртекста, соответствующие определённым блокам открытого текста, к которым вы просто не знаете ключа.


Хотелось бы как-то перемешать гамму с шифртекстом, причём безусловно безопасно, так, чтобы было всё равно, какую часть битов мы раскрываем атакующему: первые n/2 из n штук или случайно выбранные n/2 из n штук

Возможно Shamir's secret sharing[link22]? И вообще какой информационно-стойкий Secret sharing[link23]. Но как использовать это в режиме AONT, есть ли с соблюдением ваших требований какие-то подводные камни, я не знаю. На первый взгляд — нет, т.е. возможно это вам подходит. Смотря что вы ходите получить.

— Гость (30/05/2013 21:59)   
Да и Масленников не совсем прав, когда пишет, что теперь мол оригинальные тексты шифрованных телеграмм якобы можно спокойно показывать в телекамеры.

Это справедливо только для шифров конца 80-г начала 90-х гг. В аппаратуре того времени (она и сейчас используется) использовались балалайки, водка, медведи – шифры на регистрах сдвига (ЛРР/РСЛОС). И вообще, Масленников – кандидат наук, полковник ФАПСИ, а чего добился ты?и если он говорит, что нельзя шифртелеграммы раскрывать, значит так оно и есть.

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

Вот этому и придумали LaTeX.

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

идет именно через тот факт, что гамма содержит равное количество нулей и единиц

Вы путаете: вероятность появления единиц и нулей.

Потому любой «блочный шифр» фактически сводится к генерации и наложению гаммы. Что возвращает к «одноразовому блокноту» и оценке стойкости исходя из свойств накладываемой гаммы.

Опять же, вернемся к Масленникову. Помните, как он описывал балалайку? Она состоит из регистра сдвига (счетчика) и функции усложнения? Так вот, ГОСТ 28147-89 имеет ту же архитектуру (ВНЕЗАПНО): при режиме гаммирования сложение по модулю 2^32 с константами играет роль счетчика, а "зашифрование по 32 циклам" роль функции усложения. То же самое справедливо и для любого иного блочного шифра в режиме CTR.

«Высокоуважаемый Генералисимус Верховный Главнокомандующий и Президент Первой Демократической Банановой Республики».

Zendian Problem?)

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

А разве "другой ключ!=другой шифр"?. В модели идеального блочного шифра.

В качестве рандомизации можно использовать такой метод: сначала вычисляется MAC от всего открытого текста, а потом эта MAC используется в качестве IV для блочного шифра в режиме CFB/CBC. Итог: все биты текста зависят от всех битов.

Подход такой, что если увеличение степени энтропии «открытого текста» позволит выиграть лишний год-два, то игра стоит свеч

Обычно рассматриваются несколько большие порядки: сотни и тысячи лет.

Бернштейн утверждал, что после изучения и обоснования стойкости всех режимов шифрования сообщений без аутентификации, никакой режим, кроме счётчика, не нужен якобы теперь вообще

Ну почему же: представьте, что есть сообщение в несколько тысяч блоков и чтобы расшифровать одну часть, нам нужно начинать все сначала? Конечно, этот пример искусственный и на практике весь шифртекст можно разделять на логические структуры (например, записи в БД), но, все же, CBC/CFB нужны.
— unknown (30/05/2013 22:20, исправлен 30/05/2013 22:21)   

Стандартно используемый термин звучит как равномерное плоское распределение.



Верное замечание! Хорошо улавливаете суть. Но есть же ещё любители каскадов из неидеальных разных шифров. Вот они и могут перестраховывать этим свои каскады.



Итог: мы получим простейший вариант нерандомизированного шифрование (stateful encryption), если только не засунем ещё один IV в открытый текст. И не всё так просто с такими режимами: в реальности и сами такие режимы предлагаются обоснованно более сложные и их доказательства стойкости непросты.



CTR поблочно распараллеливается и считается с любого места хоть при зашифровании, хоть при расшифровании (в отличие от CBC, который можно только расшифровывать с любого места), не даёт утечек вида 2b/2 (в отличие от CBC и др.). А вообще, для недискового шифрования лучше всего скоро будет подходить Keccak или какое иное Duplex-Sponge-шифрование. Все эти CTR'ы могут уйти в историю.



Уже сейчас не нужны.

— Гость (30/05/2013 22:46)   
если только не засунем ещё один IV в открытый текст

Ну, это само собой подразумевается) Насколько мне известно, перед вычислением MAC всегда добавляется IV.

Все эти CTR'ы могут уйти в историю

Уже сейчас не нужны.

Пройдет еще несколько лет, прежде чем классические режимы шифрования уйдут из реальных приложений (openpgp, openssl). Тот же openpgp уже сколько лет тащит за собой в целях совместимости архаичный 3DES.
— Гость (31/05/2013 02:45)   

Дисковое шифрование считается номинально типом «non-mallebable»?

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

Secure: Information theoretic security.

The disadvantage of unconditionally secure secret sharing schemes is that the storage and transmission of the shares requires an amount of storage and bandwidth resources equivalent to the size of the secret times the number of shares. If the size of the secret were significant, say 1 GB, and the number of shares were 10, then 10 GB of data must be stored by the shareholders.

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


Камни всегда есть, главное — чтобы был дорабатываемый до нужной формы прототип, потому что, если даже в идеальном случае какую-то схему нельзя реализовать с безусловной безопасностью, то, тем более, глупо надеяться, что безусловная безопасность появится вдруг в комбайнере, эту схему использующем.
— unknown (31/05/2013 10:08, исправлен 31/05/2013 12:45)   

Для information-theoretic это, пожалуй, неотъемлемое свойство. Только вычислительная безопасность позволяет уменьшать размер секрета до небольшого ключа.


Более правильным решением, возможно, является генерация гаммы R1, больше размера сообщения. Затем эта гамма пропускается через Randomness Extractor[link24] типа "Stronge" в рамках конструкции Exposure-Resilient Function (ERF) или Almost-Perfect Resilient Functions (APRF) — вроде как она инф.-теор. стойкая.


Экстрактор (или ERF на его основе) сжимает исходную гамму Ext : R1 → R2. Открытый текст P ксорится с гаммой R2: C = P ⊕ R2


Если существует информационно-стойкая ERF, то достаточно опубликовать R1 и C.


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


К требованию стойкости добавляется, что если известна часть P и по ней можно вычислить часть R2, то это не должно приводить к утечке сведений о R1 так, чтобы была возможности получить сведения о каких-то других фрагментах R2. Но это вроде как входит в определение ERF.


Понятно, что такие ERF должны строиться не на обычных хэшах, а на специальных конструкциях.


Хотелось бы как-то перемешать гамму с шифртекстом, причём безусловно безопасно, так, чтобы было всё равно, какую часть битов мы раскрываем атакующему: первые n/2 из n штук или случайно выбранные n/2 из n штук

Чтобы на выходе не было явного разделения на C и R2?


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


Хотя, не силён в этой области, просто не знаю готового ответа. И подозреваю, что за этим стоит какая-то очень сложная задача.


Например[link25]:


The construction of the AONT, as suggested by Rivest in 1997, called the package transform, is only computationally secure. Stinson, in 2001, had provided the definition of an AONT having the property of information-theoretic security. He had also provided a construction of a linear (s, q) – AONT that is unconditionally secure. The linear implementation of AONT has a non-randomizing property that did not rule out known- and chosen- plaintext attacks against it. We have used a method of randomizing the input (following Stinson’s method) to prevent such attacks. Thus, by randomizing input, the linear (s, q) – AONT prevents cryptanalytic attacks.

Собственно, вот работа[link26]. Осторожно! Индусы пишут в MS ворде.


Зато, работа[link27] японцев подтвердила мои догадки: информационно-стойкая AONT Стинсона на самом деле нестойка к атакам с известным и подобранным шифртекстом. А навешанная японцами конструкция на разделении секретов Шамира поверх схемы Стинсона непрактична из-за большого роста размера сообщений (экспоненциальный, а не линейный рост). Вот такой вот безусловно стойкий AONT. Зато предложенный ими вычислительно-стойкий AONT на линейных кодах (оказывается, с кодами не так всё сложно) приводит к увеличению размера сообщения всего на один блок.


Сомневаюсь, что результат арабов и индийцев из предыдущей работы по созданию безусловно стойкой AONT более доверяем или лучше на практике.


Вот где бы ещё найти работу по материалам этого коллоквиума[link28]? Там и ERF (in either an information-theoretic or computational sense) и AONT:

we give the first definitions and constructions of ERF's and AONT's (in the standard model, without "random oracles"). Moreover, we prove lower bounds showing that our constructions achieve nearly optimal parameters (in both the information-theoretic and computational settings).

До этого у них вышла работа "Exposure-Resilient Functions and All-Or-Nothing Transforms"[link29]. Но в ней нет инф.-теор. безопасности, скорее всего в других работах будут такие же пессимистичные оценки, как у японцев, которые вроде бы доказали размер минимальных затрат на накладные расходы.



В идеале. На практике — только невнедрённые Wide-block режимы. А для Narrow Block — не совсем полная модель «non-mallebable».

— gyhsal (31/05/2013 13:42)   
Более правильным решением, возможно, является генерация гаммы R1, больше размера сообщения.
Экстрактор (или ERF на его основе) сжимает исходную гамму Ext: R1 → R2. Открытый текст P ксорится с гаммой R2: C = P ⊕ R2
Если существует информационно-стойкая ERF, то достаточно опубликовать R1 и C.

Чтобы любой желающий мог сжать исходную гамму R1 получив R2, с которой потом поксорить шифротекст :)
На базе какого секрета в этой схеме гамма R1 сжимается экстрактором типа "Stronge"(Strong?) в рамках конструкции ERF или APRF?
— unknown (31/05/2013 14:36, исправлен 31/05/2013 15:41)   

Именно для этого. Чтобы таким путём получить AONT.



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


Собственно, разница между ERF(x) и AONT(x) в том, что ERF может безопасно выставлять напоказ часть результата для случайного x, а AONT(x) — для любого x.

— gyhsal (31/05/2013 16:21)   
Хотели "рэндомизацию", намертво связывающую все биты открытого текста максимально стойким способом — получайте. Не знаете части битов открытого текста — криптоанализ будет невозможен (затруднён).

Надо будет почитать про варианты оценки степени связанности. Понятно, что в случае повреждения нескольких бит упакованного «исходного текста» проведение распаковки затруднено тем, что множество вариантов будет иметь мощность больше единицы.
— Гость (01/06/2013 08:37)   

Интересное свойство. Трудно даже вообразить, как сделать так, чтобы потеря небольшого числа битов в R1 приводила к вами описанному.


Если P ∈ Un, то нет смысла считать, что атакующий что-то знает о P. Если же P неслучайно, то имеет смысл рассматривать только тот вариант, когда оно (предположительно) известно атакующему полностью, и он хочет лишь проверить гипотезу, что там действительно лежит P, наша же цель — не дать ему этого.


Нет, скорее «так должно получается из-за того (мы хотим этого добиться), что атакующий не должен знать, какие именно биты в R2 (ну, или в C) он в итоге угадал/вычислил правильно». Вы сами понимаете, что если у него есть полное знание о P, то совпадение значений нескольких битов в P с теми, что предполагал атакующий — взлом системы.


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


Ценой принципа косолапого, да. Мы знаем. Когда-нибудь вся вычислительно-стойкая криптография отправится на кладбище, где ей как раз самое место, а её место займёт формальная математика с формальными доказательствами и информационно-теоретической безопасностью без криптографических сюрпризов через каждые n лет «по вновь открывшимся обстоятельствам». Практическое применение на текущий период времени — единственное, что оправдывает существование криптографии, но ценности, как искусства и науки, я за ней не вижу. Доказательство того, что существование ICM и других идеальных примитивов противоречит математике — толстые гвозди в гроб криптографии.


И Леонид и Евгений говорят по-русски. Можно написать и спросить, если оно действительно того стоит.


Эту работу ранее уже просматривал, ещё после первых ваших постов в этом топике. Ощущения те же. Ну, и нет безусловной безопасности ⇒ в топку.


Narrow Block — то, что сейчас реально используется в дисковом шифровании? Т.е. всякие LUKS и тому подобные системы.


Эту концовку не понял. Зачем Алисе и Бобу согласовывать ошибки с атакующим? Какой-то абсурдный протокол бы получился.


Понятно. С первого прочтения смысл, правда, не улавливается, так как можно понять иначе: есть x ∈ X, и «случайный x» — это случайно выбранный аргумент из X, где само множество X может быть какими угодно, и совсем неслучайным. Реально же имелось в виду x ∈ Un в определении ERF. Смысл я понял, информация интересная. Можно сказать, что меня интересует скорее AONT, чем ERF, если перефразировать вышесказанное.
— Гость (01/06/2013 08:49)   

Кранты всем формулам в тексте, да.
— unknown (01/06/2013 14:58, исправлен 01/06/2013 15:01)   

А что в этом удивительного? Обычный хэш — это тоже разновидность экстрактора. Для него такое свойство естественно. Потеряйте 128 бит на входе и дайте противнику их подбирать, пока у него выход не совпадёт.



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



Верно. Конкретно XTS, LRW, CBC-ESSIV (и его близкий аналог в BSD).



Ну не по часу же мне каждую формулировку обдумывать для форума :) Здорово подмечаете неточности, хоть на публикацию вам отдавай.


Это отсылка к шумовой криптографии и каналам Винера. Если сторона A передаёт сообщение стороне B в канале с внешним (естественным, физическим, квантовым) шумом без кодов коррекции ошибок, то сторона B может затем по проверочным (но не корректирующим) кодам дать ответ стороне A, в каких битах (скорее блоках с битами) у B получились ошибки. A будет передавать повторно эти и только эти блоки, пока у A и B не получится общий массив. У прослушивающей стороны E сбойные блоки будут в других местах и запись сеанса согласования блоков ей не поможет. Затем A и B с помощью экстрактора выведут общий ключ из своих согласованных массивов и он будет одинаковым. Сторона E по частичному знанию исходного массива, по которому согласовывался ключ, не получит о нём никакой информации, если экстрактор инф.-теор. стойкий и параметры передачи в канали подобраны так, что собрать массив без согласования будет за пределами физической возможности измерительных приборов. С E, естественно, никто согласовывать нужные ей биты не будет, поэтому A и B должны быть между собой аутентифицированы.



А между ними есть переходы и построения одного на основе другого, поэтому их часто изучают в общих работах.

— Гость (02/06/2013 00:18)   

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


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


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

Взлом ε-безопасности напоминает аналогию между равномерной непрерывностью и просто непрерывностью. Когда непрерывность не является равномерной, как бы ε вы ни задали, найдётся такой аргумент, который обманет ваши оценки. Вот y = 1/x на (0,1) непрерывная, но не равномерно непрерывная: какой ε = | y(x2) – y(x1) | ни задашь, всегда найдутся такие близкие друг к другу x1 и x2, что будет | y(x2) – y(x1) | > ε.

Вы чем-то сверху лимитируете ресурсы атакующего, но это лимитирование трудно обосновать. Если в вычислительной безопасности лимитирование по числу операций и количеству памяти резонно, то ограничение других ресурсов (точность детекторов) трудно мотивировать (ранее уже обсуждалось тут). Казалось бы, на практике ограничения есть, но это скорее оттягивание момента взлома, чисто техническое усложнение. Сейчас оно безопасно, а послезавтра заинтересуются методом, сделают более умный детектор и методику, и всё на том. Если же вы хотите ограничить точность детекторов универсальной границей, вы вынужденно спускаетесь на квантовый уровень, тем самым превращая шумовое крипто в квантовое, где последнее оптимальней реализовать уже не по методам шумовой криптографии, а через совсем другой протокол, QKD. Кроме того, есть оценки на минимальное количество информации, которое A должно передать B, чтобы сгенерировать гамму для безопасного одноразового блокнота. Из этих оценок следует, что QKD оптимально с точностью до некоторой константы. В общем-то на этом всё, тупик.

Шумовым крипто, кажется, активно занимался Маурер, он же был руководителем Реннера по его диссертации, все работают в одном месте. Если бы шумовое крипто можно было бы грамотно довести до ума, то, пожалуй, там бы это сообразили раньше нас с вами. Работы на эту тему продолжают публиковаться, даже от серьёзных людей, но в чём мораль этих работ — я сейчас сказать не могу. Допускаю, что у методики шумового крипто могут быть и другие применения, косвенные. Например, вы не любите exposure-resilient-криптографию [1][link30], [2][link31], поскольку считается, что конструировать криптопримитивы, считая что часть ключа может утечь атакующему, неблагодарное и неперспективное занятие, и тут я с вами соглашусь. Тем не менее, у такого сорта криптографии, как и у экстракторов, есть другие применения, где без такого раздела криптографии было бы никуда — те же недетерминистичные экстракторы в QKD и обработка вывода ГСЧ, что, собственно, и оправдывает деятельность тех, кто exposure-resilient'ом занимается. Вот вам яркий[link32] пример мирного сосуществования и взаимообогащения. У того же Видика[link33] половина публикаций с классическими криптографами, другая половина — с квантовыми, и доклады по DI QKD и Беллу, и с Додисом он знаком лично, хотя ясно же, что чипы, незащищённые от утечек ключей из-за излучения его совсем не интересуют.


Знать похожий метод бывает полезно в любом случае, это пригождается если не напрямую, то косвенно, на уровне аналогий и полезных используемых идей.
— unknown (02/06/2013 11:00, исправлен 02/06/2013 11:01)   

Мне тоже кажется, что не всё так просто. Например, мой простейший пример перехода ERF → AONT через гамму одноразового блокнота явно не соответствует всем критериям. Неспроста у японцев получились очень громоздкие оценки затрат на инф.-теор. стойкий AONT.



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



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


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


Понятно, что инф.-теор. стойкое крипто тесно связано с квантовым и исследования ведутся на стыке этих наук.

— Гость (02/06/2013 20:54)   
Когда-нибудь вся вычислительно-стойкая криптография отправится на кладбище, где ей как раз самое место
Все там будем. Когда-нибудь. Каким еще дисциплинам там самое место?

а её место займёт формальная математика с формальными доказательствами и информационно-теоретической безопасностью без криптографических сюрпризов через каждые n лет «по вновь открывшимся обстоятельствам».
а её формальное место формально займёт формальная математика с формальными доказательствами и информационно-теоретической безопасностью без криптографических сюрпризов через каждые n лет «по вновь открывшимся обстоятельствам» зато с (не)формальными сюрпризами иного свойства.

Практическое применение на текущий период времени — единственное, что оправдывает существование криптографии, но ценности, как искусства и науки, я за ней не вижу.
И не видели? Практическое применение — это чуть ли не единственное оправдание существования всего. Уже не видели применения и кибернетике, и генетике и прочим "лженаукам". Разбавим криптографией?

Доказательство того, что существование ICM и других идеальных примитивов противоречит математике — толстые гвозди в гроб криптографии.
Это субъективная точка зрения? Или объективная реальность?
— Гость (03/06/2013 13:58)   

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


Неочевидно.

Можно ещё так пояснить. Надеяться, что у Евы будет что-то иное, чем у Боба, странно (слабо обоснованные предположения, при которых это может быть так, пока опустим). Раз так, всё в пределе сводится к тому, что все трое (A, B и E) имеют идентичный набор случайных данных. Да, Алиса и Боб могут из общего для них шума вывести другой (о котором Ева будет знать меньше или не знать ничего), ползуясь тем, что они друг перед другом аутентифицированы (для простоты можно считать, что оба знают какую-то общую для них строку битов). Но тогда объём секрета не увеличивается между Алисой и Бобом от использования шума. Если вы в систему связи/шифрования добавите детерминистичную часть всем трём (Алисе, Бобу и Еве), размер секрета между Алисой и Бобом останется тем же.

Вы описываете шумовое крипто так, как будто можно гнать шум через каналы связи вместо квантовых состояний, и всё будет оставаться хорошо (при том, что даже с QKD не всё так хорошо, если смотреть на её безопасность пристально). Иначе говоря, протокол для шумового крипто тот же самый, что и для QKD, но слаться будет классический шум. Очевидно, что шумовое не может быть безопаснее квантового, а про последнее мы знаем, какие ухищрения там нужны, чтобы всё было безопасно, и что даже эти ухищрения дают относительно пессимистичные оценки. Было бы всё так просто, как вы описываете, никто б не страдал ерундой с QKD. И отсутствие статьи в wiki про шумовое крипто как бы символизирует. Я вполне допускаю, что шумовое может работать при каких-то условиях и обеспечивать безопасность, но, знаете ли, часто можно передавать данные вообще без шифрования, если выполняется ряд условий IRL. Самое интересное же в том, когда они не выполняются.


Имелось в виду, что проблема — не практическое применение как таковое, а отсутствие лучшего решения на текущий момент. Если нет концептуального решения, набор костылей и подпорок оправдан до тех пор, пока решение не будет найдено. Сейчас есть чёткое понимание того, что решение есть, и что оно может быть воплощено в реальность, зачем тогда ориентироваться на костыли, которые приходится менять каждые 5-10 лет? Сейчас всё загнано в рамких идеальных моделей, а при сертификационном криптоанализе ищут отклонения от них. Одни запутывают алгоритм, другие его распутывают и взламывают. Есть много механизмов того, как сделать надёжное запутывание. Затем, как только намекается путь на распутывание (отличие от идеальной модели), шифр тут же меняют на другой. За счёт частой смены шифров можно добиться того, что за прошедший короткий срок никто не сможет разломать шифр, а про большие времена сказать «долговременная секретность в современной криптографии — не приоритет». То есть, практический взлом AES через 40 лет — это нормальная «проектная авария»* «плановая» ситуация. Как в самолёт при его изготовлении вписывают срок безопасной службы,** так же и в шифр вписывает условный срок его криптостойкости.


Какого?


Да[link34], объективная[link35].

*Бывают и «запроектные» — это когда случилось то, от чего хоть какая-то защита инженерами-конструкторами вообще не предусматривалось.
**Реально он может пролетать и больше него и меньше, или вообще в его конструкции могут найти фатальные недочёты сразу же после ввода в эксплуатацию.
— unknown (03/06/2013 15:48)   
Если Алиса посылает Бобу какой-то свой шум, а Боб его оцифровывает лучше, чем генерит с нуля, это же может делать и Ева.

Как это? Не понял смысла сказанного. Что значит "Боб его оцифровывает лучше, чем генерит с нуля"?

Если оба Алиса и Боб используют внешний источник шума (Солнце, Луна) и черпают оттуда случайные биты, после согласовывая их, это же может делать и Ева.

Не обязательно так. Это даже не изначальная идея, а уже одна из поздних вариаций и не самая основная. Чаще всего рассматривается как Алиса посылает Бобу сигнал в канале с шумами (радиопомехи). Просто сейчас все привыкли, в век цифровой техники, что сырой цифровой сигнал без кодов коррекции ошибок никто не посылает и о существовании шумов знают только проектировщики, рядовой пользователь с ними не сталкивается. Поэтому нужен такой канал, где принудительной коррекции ошибок нет: собственный радиоканал, к примеру. Хотя, оптический или проводной тоже подойдёт, главное иметь к нему доступ на физическом уровне: посылать сырые, нескорректированные (но дополненные проверочным кодом) блоки битов с TRNG, с последующей возможностью оцифровки аналогового сигнала на приёмной стороне.

Ограничения на объём носителей и точность оцифровки всегда могут быть понижены. Раз может Боб, сможет и Ева.

Объём носителей фигурирует в другом виде виде инф.-теор. крипто. Не в шумовых каналах Винера. Точность оцифровки опирается на предел измерений в области неустранимых тепловых шумов и внутренних шумов приборов. Даже охлаждение в жидком азоте гелии не поможет. По крайней мере ε сводят за пределы не технических и инженерных, а физических возможностей. Хотя такой чёткой границы, как в квантовом случае здесь нет. Privacy amplification сделает так, что Боб легко сможет сделать то, что не сможет никакая Ева, допустимая законами физики.

Да, Алиса и Боб могут из общего для них шума вывести другой (о котором Ева будет знать меньше или не знать ничего), ползуясь тем, что они друг перед другом аутентифицированы (для простоты можно считать, что оба знают какую-то общую для них строку битов).

Это очевидно для предотвращения атаки "человек посредине" со стороны Евы.

Но тогда объём секрета не увеличивается между Алисой и Бобом от использования шума. Если вы в систему связи/шифрования добавите детерминистичную часть всем трём (Алисе, Бобу и Еве), размер секрета между Алисой и Бобом останется тем же.

Ева то откуда узнает начальный секрет?
Используя инф.-стойкую аутентификацию (как в QKD) начальная строка разворачивается в бесконечно обновляемую при согласовании гамму, которая черпает случайность из наложения гаммы TRNG Алисы на шум внешней среды.

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

Практически так. Инф.-стойкая аутентификация использует единственный первоначальный расшаренный секрет, затем согласование, усиление приватности, экстрагирование общего ключа. Этот ключ используется одноразово для шифрования и для нового сеанса аутентификации (Information Theoretic Perfect Forward Security).

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

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

Было бы всё так просто, как вы описываете, никто б не страдал ерундой с QKD. И отсутствие статьи в wiki про шумовое крипто как бы символизирует.

Авторов, ведущих регулярные исследования, таких как Кирилл Морозов[link36], мало. Хотя в архиве достаточно публикаций на тему.

Может и стоило бы классическое шумовое крипто рассматривать как устаревшую или тупиковую идею, раз есть квантовое. Но важен ряд причин:

  1. Есть шанс построить систему на примитивном, портативном, рядовом железе. Т.е. в домашних условиях будет попроще, чем QKD.
  2. Упомянутый выше (полу)броадкастинг, невозможный в QKD. Точнее, ненаправленная беспроводная передача, связь с подвижным объектом или с таким, местоположение которого точно неизвестно.
  3. Больше вариантов канала передачи, в т.ч. беспроводного. Организовать квантовый канал со спутником сложновато, а радиоканал — без проблем. Также как и другую радиосвязь на дальние расстояния (хоть межпланетную) без ретрансляторов, зато с нужными для этого неустранимыми шумами внешней среды.
— Гость (03/06/2013 19:29)   

Имелось в виду, что Боб, получая сигнал от Алисы, может совершить ошибку при оцифровывании или не совершить. В предельном случае большой ошибки можно считать, что он вообще ничего не оцифровывает, а просто берёт какие-то случайные биты с потолка и считает, что они были посланы Алисой.


Хорошо. Т.е., вы считаете, что иногда Боб будет ошибаться, измеряя сигнал, а иногда Ева, так? И что потом Боб с Алисой по открытому, но аутентифицированному каналу выясняют, в каких битах Боб ошибся, а в каких нет, сравнивая синдромы. Далее, за счёт reconciliantion и privacy amplification Алиса и Боб могут выкинуть те битовые блоки, которые в которых ошибка есть, оставив только те, где её нет, т.е., совпадающие. У Евы же так хорошо не получится: если она в каком-то блоке сделала ошибку, никто её блок не выкинет, а какой блок должен быть правильным, она не знает. Соответственно, после этапа переговоров у Алисы и Боба появляется идентичный набор битов на обоих концах, а у Евы нет, у неё есть отличие. Далее Алиса и Боб могут применить экстрактор и сжать свои битовые строки в более короткий, окончательно выдавив ту часть информации, которая доступна Еве. — В этом ваша идея? Так работает QKD.

Отличие от шумового крипто в том, что в QKD наличие искажений при получении данных Бобом трактуется, как ошибка. Если канал идеальный, Боб совершит ошибку в определённом проценте случаев, и этот процент в квантовом канале можно строго оценить. Если же Ева вмешивается, Боб совершит ошибку в большем числе случаев, т.е., у Алисы с Бобом будет больше различающихся битов по окончании передачи. В QKD есть оценки, которые говорят о том, сколько максимум получила информации Ева, если отклонение от стандартного процента такое-то. В зависимости от этой информации, полученной Евой и оцененной по числу ошибок в канале, Алиса с Бобом по-разному делают privacy amplification. В частности, если уровень шума/искажений превосходит некоторый размер, шифрованый канал между Бобом и Алисой установить вообще нельзя.

Вопрос первый: как вы построете универсальную оценку на то число информации, которое утекло Еве? Вы же не знаете, в каком числе случаев она ошиблась.

Вопрос второй: как вы защититесь от MITM? Я имею в виду intercept & resend. В QKD, если Ева тупо начнёт делать I&R-атаку, число ошибок у Боба превысит критический предел, и Алиса с Бобом поймут, что установить шифрованный канал нельзя. В шумовой же криптографии что мешает Еве просто прочитать все данные, посланные Алисой, разорвать канал, а затем передать их Бобу без ошибок? В QKD вы доверяете, условно говоря, только ящикам, но не проводу, в них воткнутому. Если считать так же в шумовой криптографии, то Ева всегда сможет сделать так, контролируя канал, что прибор Боба получит именно такие биты, какие она будет знать дословно и без ошибок. В итоге биты у Боба и Евы будут идентичными и похожими на те, что у Алисы. Следовательно, Ева, слушая открытый (хотя и аутентифицированный) канал между Алисой и Бобом, выяснит, какие блокие будут использоваться для генерации ключа, и получит весь ключ целиком. Вы именно эту проблему и имели в виду, когда писали «нужен безопасный пространственный периметр»? Ну, помните же, сколько ругали QKD за разного рода MITM'ы? А тут мы заранее выносим MITM за рамки модели? Ну, это круто: шифрованный канал, который не защищён от MITM. :)


Разрабатывались устройства QKD по воздуху, работающие между ATM и чем-то типа кардридера. На SECOQC в 2008-ом был даже прототип размером с небольшой ящик (размеры не знаю, может, 20cm x 20cm). Идея: вы подходите к банкомату и производите операции на своей портативной машинке-кардридере. Соединение между машиной и банкоматом шифруется с помощью QKD. Вы же вроде как FSO QKD интересовались. Вот статья на эту тему[link37] от 2006-го, в разработке устройства HP постарался[link38]. Тут[link39] фотографии живого прибора есть, но он на стенде.
— Гость (03/06/2013 19:36)   
P.S. «Low cost QKD» (заголовок статьи) автоматически ассоциируется с китайским г-ном, который будут пытаться всем впарить. Не знаю даже, почему.
— unknown (04/06/2013 10:41, исправлен 04/06/2013 12:43)   
В предельном случае большой ошибки можно считать, что он вообще ничего не оцифровывает, а просто берёт какие-то случайные биты с потолка и считает, что они были посланы Алисой.

Такой случай должен быть явно выведен из протокола. Нельзя получить инф.-стойкую случайность "из ничего".



В общем виде, я так себе это представляю. Допускаю, что какие-то тонкости, отличающие от QKD, имеют место. Не разбирался настолько подробно.



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



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



Нет конечно, я не разбирал все варианты этих экзотических протоколов столь подробно, но такой тривиальный момент явно дожен быть предусмотрен. Хотя, возможно, его реализация не так тривиальна, как кажется.



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


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


Всё это в работах описано, как ключевые проблемы, отмечено вами в целом верно, методы преодоления этого тоже описаны, но в их эффективности и обоснованности я не разбирался.


До сих пор проходят конференции по инф.-теоретической безопасности, где помимо квантовых, продолжают рассматриваются и классические шумовые каналы, Wyner channels, wiretap channels[link40] и пр. Вот ещё пример исследовательского проекта[link41]. Или они там просто гранты пилят?


Вот интересная подборка публикаций[link42]. Оказывается, есть инф.-теор. стойкие подписи. Точнее, псевдоподписи, т.к. они нетрансферабельны (в общих случаях не могут быть переданы третьим сторонам для проверки). Кстати, автор занимается одновременно и квантовой криптографией и шумовой.


Шумы в каналах и файлах важны не только для обычной стеганографии, но и инф.-теор. стойкой[link43].


А вот что-то похожее на информационно-стойкое усиление (дискового?) шифрования: Information-Theoretic Forward-Secure Storage Schemes[link44].

Informally, FSS is an encryption scheme (Encr, Decr) that has the following non-standard property: if the adversary has only partial information about the ciphertext C = Encr(K, M), he should have essentially no information on the corresponding
plaintext M, even if he learns the key K.

А то, сжимать диск перед шифрованием кто-то там хотел :)


Эту модель развивает департамент атомной энергетики и лаборатория Sandia (та самая, где разрабатывают ядерное оружие, УТС и пр.), Key Management and Encryption under the Bounded Storage Model[link45] — здесь как раз используется ограниченность противника в ресурсах памяти, а не вычислений. (Bounded storage model, оцифровка данных радиотелескопов, но это не шумовая криптография Винера, а скорее Маурера). То, что вами раскритиковано выше.


А в вики много каких статей нет, про крипткодинг и шифрование на квазигруппах, к примеру. Хотя, да — это косвенный показатель, что направление близко к маргинальному и упорно "не взлетает".


Вот ещё диссертация в копилку ссылок: http://www.is.titech.ac.jp/~ch.....t/Por_Phd-thesis.pdf[link46] — Information-Theoretic Security
beyond the One-Time Pad. В частности:

In particular, we show that information-theoretic perfect non-malleability is equivalent to perfect secrecy of two different messages. This implies that for n-bit messages a shared secret key of length roughly 2n is necessary to achieve non-malleability, which meets the previously known upper bound.

— Гость (05/06/2013 01:54)   

Из этих ваших цитат следует, что шумовая криптография требует ещё и предрасшаренного секрета между Алисой и Бобом. Насколько мне известно, в QKD это не требуется. Вы можете хоть по телефону диктовать друг другу, какие базисы у вас были выбраны и совпали / не совпали. Т.е., аутентифицированный канал между A и B — это не то же самое, что предрасшаренный секрет между A и B.


Во-первых, не понятно, откуда возьмутся проверочные коды, если предрасшаренного секрета нет (как в QKD). Во-вторых, если Ева хочет гарантировать доставку Бобу незашумлённых сообщений, ей не нужно переклеивать проверочные коды:

В QKD вы доверяете, условно говоря, только ящикам, но не проводу, в них воткнутому. Если считать так же в шумовой криптографии, то Ева всегда сможет сделать так, контролируя канал, что прибор Боба получит именно такие биты, какие она будет знать дословно и без ошибок. В итоге биты у Боба и Евы будут идентичными и похожими на те, что у Алисы. Следовательно, Ева, слушая открытый (хотя и аутентифицированный) канал между Алисой и Бобом, выяснит, какие блокие будут использоваться для генерации ключа, и получит весь ключ целиком.

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

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

Но тогда объём секрета не увеличивается между Алисой и Бобом от использования шума. Если вы в систему связи/шифрования добавите детерминистичную часть всем трём (Алисе, Бобу и Еве), размер секрета между Алисой и Бобом останется тем же.

Или ещё так можно сказать: вы записали случайные данные на диск, сделали три его копии и раздали всем трём. У Алисы с Бобом ещё есть небольшой предрасшаренный секрет друг с другом, которого нет у Евы — таковы условия задачи. Вопрос: как, использя этот секрет, Алиса с Бобом получат длинную гамму для одноразового блокнота?


«Не видно причин, которые принципиально бы этому мешали» — в таком темпе можно быстро дойти до аргументов, которые потребовали написать что-то такое[link47]. Из отсутствия принципиальных причин небезопасности безопасность не следует. Между общими идеями и протоколом с доказанной безопасностью — каньон с горой трупов. На примере QKD: Визнер предложил идею в в 1960-ых[link48], послал креатив в IEEE Trans. Inf. Theory, его там, естественно, завернули. О том, как анализировать безопасность QKD в самом общем случае, тогда никто не знал, не говоря уже о самом доказательстве. Безопасность от коллективных и индивидуальных атак, а также вывод границы на скорость передачи сообщений по QKD, так называемый Devetak-Winter rate, — 2003[link49]-ий год. До 2003-его не было обоснованных оценок на безопасность против даже простейших атак, не было даже самых тухлых оценок на то, сколько информации можно безопасно передать, если в канале содержится определённая доля шума (я так понимаю, в шумовой криптографии и этого нет?). Безопасность против когерентных атак — это 2005-ый[link50] год. Но и то и другое — это оценка асимптотическая. Вдруг, чтобы её достичь, Алиса и Боб должны использовать свой QKD-канал миллион лет? Оценка безопасности при конечном числе использований канала — 2008-ой[link51] год. И это не всё, это были только общие энтропийные оценки. Как я понимаю, Ева может оптимизировать свою атаку в зависимости от того, как Алиса с Бобом будут обрабатывать свои сырые данные по классическому протоколу, это породило ещё кучу работ, начиная с типа таких[link52], т.е., даже скорость Деветака-Винтера — это не конец, это ещё только начало. Перефразируя Раадта[link53], «глупо думать, что тысячи людей, которые за 50 лет не могут довести до ума QKD, вдруг внезапно соберутся и сделают безопасное шумовое крипто при том, что там изначально куда больше ограничений, условий и шире вектор атак». Безопасность QKD потому и unconditional, что никаких условий на Еву QKD не налагает вообще, Ева вольна делать в канале всё, что хочет. Да, криптографы под словом «unconditional» понимают нечто другое. :)

Или вот ещё другой пример слегка троллинговый, но всё же: посмотрите на RC4. Вам кто-то может с пеной у рта утверждать, что там всё ОК, просто его надо «правильно готовить»; не нарушать те требования к использованию на практике, которые делают шифр слабым; гарантировать отсутствие ряда ситуаций с выкачкой большого трафика клиентов и т.д. Я не исключаю, что всё так и есть: при соблюдении всех до одного из сотни условий практический взлом RC4 сомнителен, поэтому скорость — важное преимущество, а не высоконагруженных серверах он по заслугам составляет конкуренцию AES. Тем не менее, вы же понимаете, что место RC4 — только на помойке не таких серверах?

Когда вы собираете из кирпичиков протокол, кажется, что его всегда можно собрать, если каждый кирпич неплохой, но на самом деле (в общем случае) это не так. Может получиться так, что оценки на безопасность потребуют сделать то, что сделать невозможно, используя неидеальные кирпичи — это один случай. Например, в QKD невозможно создать гамму для одноразового блокнота, о которой бы атакующий не знал ничего, остаётся довольствоваться только ε-безопасностью. Кроме того, есть достаточно пессимистичные оценки на безопасность гаммы при конечном числе посылок информации через канал. Может так получиться, что это тоже фундаментальное ограничение (медленная сходимость к той безопасности, которая достижима на бесконечном числе использований канала). Ну, или оценки таковы, что если Алиса и Боб имеют n бит общей информации, атакующему утечёт n+ε бит информации об исходном n. Если совсем петросянить, то «не каждый ряд с убывающими членами сходится», поэтому тот факт, что Ева знает меньше, или тот, что «информацию Евы можно универсально ограничить сверху» остаются общими словами, пока нет строгих оценок в рамках конкретного протокола, тем более, что все эти оценки зависят от параметров протокола, которые можно варьировать. Т.е., вопрос не в числе, вопрос в том, какая там зависимость.


Есть ли обзоры, где перечислены все условия? Бывает, что берут протокол, доказывают его безопасность при условии чего-то там, публикуют. Потом предлагают другой протокол, доказывают про него что-то в каких-то других рамках, тоже публикуют. Через n лет мы имеем сотни десятки работ по какой-то теме, но ни для одного протокола так полностью и не выписан список всех условий, когда он работает. А если и выписан, то безопасность доказана не при таком списке условий, а при более коротком. Исследователи всегда могут сказать «мы надкусили яблоко сделали первые шаги». А кто будет делать завершающие шаги? Вас не удивляет, что доказательства безопасности для кучи QKD-протоколов нет? Что безопасность CV QKD — это такая тумманность, что вообще не понятно, что там происходит? Что безопасность всяких там двусторонних QKD и прочих модификаций тоже недоказана? Есть доказательство безопасности от конкретных атак, но всё равно никто не заявляет «я поставил точку в вопросе доказательства безопасности протокола».


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

Я видел статьи, постеры по гибридам чего-то типа шумовой криптографии и квантовой, Y-00 протоколы, вот это всё. Надо бы закинуть их ссылками на форум. Попытка чего-то допытаться от авторов к успеху не приводит. Впечатление такое, что «мы сделали, оно работает, не спрашивайте, почему оно безопасно». Неаккуратно оформленные статьи, где одно бла-бла-бла, ну и журналы, где оно публикуется, тоже большого доверия не внушают. Одно дело — предложить идею, другое — доказать безопасность. Конечно, ряд ссылок из тех, что вы привели (и тех, которые приводили ранее) внушают какое-то доверие, но без вникания в детали трудно что-то сказать помимо спекуляций как бабки на лавочке («не видел, но осуждаю»).


В моём случае всё так же[link54]:

ссылки годные, интересные, надо теперь читать и думать

Не зная конкретно, что утверждается и при каких условиях, к сожалению, из общих соображений рождается только пустой флуд.


Я не разбирался с направлением, мне сказать нечего. Даже то, что говорю — это работа gw'ем между вами и тем, кто статьи по шумовому крипто всё же читал и разбираться с ними пытался. Мне интуитивно кажется, что если бы оно было столь хорошо, как пропагандируют авторы, оно бы уже давно было повсеместно. В чём его ключевой затык — мне трудно сказать. Это могут быть и требования, которые редко когда в реальности выполняются, и отсутствие полного анализа безопасности для конкретных реализаций протокола.


Надо же, как много знакомых лиц упоминается. Израиль Истина должна быть где-то рядом. :)


Это про шумовое крипто или про что? Нужно предрасшарить 2n-битовый ключ, чтобы потом через шумовой канал выработть n бит ключа?! Так Боб с Алисой быстро в минуса уйдут.
— unknown (05/06/2013 10:21, исправлен 05/06/2013 11:49)   
Из этих ваших цитат следует, что шумовая криптография требует ещё и предрасшаренного секрета между Алисой и Бобом. Насколько мне известно, в QKD это не требуется.

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


Доводы в пользу квантового распределения ключей[link55]:


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

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

6.1 Симметричная аутентификация ключей
Стороны, у которых уже есть совместно используемый закрытый ключ могут использовать безусловно стойкие коды аутентификации для своих сообщений. Первый такой метод был описан Вегманом и Картером и был усовершенствоваан для использования в QKD. Это одна из причин, по которой квантовое распределение ключей называют квантовым расширением ключа: можно взять короткий совместно используемый ключ и расширить его до информационно-теоретически безопасного большого совместно используемого ключа.


Их не может не быть. М.б. вы просто не рассматривали полное описание инф.-теор. стойкого QKD на аутентификации Вегмана-Картера или аналогах? Симм. ключ должен быть хотя бы один раз предзагружен (расшарен) на обе стороны. Что в квантовые девайсы, что в шумовые. В отличие от шифрования (одноразовый блокнот), размер ключа для инф.-стойкой аутентификации по Вегману-Картеру меньше размера сообщения.


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


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

Нет! речь об аутентификации, а не шифровании. Для инф.-стойкой аутентификации размер ключа не должен быть равен или больше размера сообщения. Он м.б. короткий. См. Authentication in quantum key growing[link56].


Инф.-теор. (IT)-стойкое QKD выращивает предрасшаренный ключ (quantum key growing) в бесконечную гамму в ходе QKD-сеансов. Также как и шумовое.


Как можно получить IT-стойкую аутентификацию вообще с нуля, без предрасшаренного ключа, я не знаю. Это противоречит моим представлениям о мире. Асимметричное QKD и IT-стойкие подписи теоретически есть, но насколько это осуществимо на практике — не знаю. Иначе (на уровне осторожного дилетантского предположения), легко бы можно было строить квантовые сети без репитеров, ретранслирующих квантовые состояния.


Хотя, японцы предлагают асимметричное шифрование Unconditionally Secure Anonymous Encryption and Group Authentication[link57] с вполне приемлемыми параметрами:

For example, in our model, required memory sizes for ciphertext, encryption key and decryption key are at least log2|M| + log2|S| bits, log2|M| + log2|S| bits and (k + 1) log2|M| bits respectively, where M is the message space, S is the set of all senders and k is the maximum number of dishonest senders.

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


Since no computational difficulty is assumed in USAE, it is impossible for a sender to secretly transmit a message using only the public information. This means that in order to construct a USAE, a different assumption (rather than computational assumptions) will be required, e.g. existence of a noisy channel, that of a quantum channel, bounds of memory or threshold of the number of malicious users.

Или ещё так можно сказать: вы записали случайные данные на диск, сделали три его копии и раздали всем трём. У Алисы с Бобом ещё есть небольшой предрасшаренный секрет друг с другом, которого нет у Евы — таковы условия задачи. Вопрос: как, использя этот секрет, Алиса с Бобом получат длинную гамму для одноразового блокнота?

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



Это к наивной схеме /comment65238[link58]. У неё (также как и одноразового блокнота) абсолютно нет свойства non-malleability. Стоит инвертировать результат ксора с гаммой, как инвертируется открытый текст. Теперь понятно, почему их надо ещё стойко перемешать, а это даст не линейный, а экспоненциальный рост. IT-стойкое усиление дискового шифрования практически невозможно.


В целом со скептическими замечаниями согласен, хотя мы оба ловим друг друга на элементарном незнании матчасти, так что я бы был более осторожен в выводах как за, так и против.


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


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

— Гость (06/06/2013 02:45)   

Welcome to new brave world! Переворачиваю. Если бы квантовый мир был почти как классический, но со своими тонкостями, у людей втечение 100 лет не срывало бы башню, и не переворачивалось бы представление о том, что есть реальность. Выделяю ключевые слова:

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

«Может быть» ≠ «обязана» или «должна быть».

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

Она — да, «может обеспечить». Кто сказал, что нельзя обеспечить аутентификацию иным образом?

6.1 Симметричная аутентификация ключей
Стороны, у которых уже есть совместно используемый закрытый ключ могут использовать безусловно стойкие коды аутентификации для своих сообщений. Первый такой метод был описан Вегманом и Картером и был усовершенствоваан для использования в QKD. Это одна из причин, по которой квантовое распределение ключей называют квантовым расширением ключа: можно взять короткий совместно используемый ключ и расширить его до информационно-теоретически безопасного большого совместно используемого ключа.

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

Так что в статье с Люткенхаусом всё верно. Впрочем, это неудивительно, Люткенхаус всё-таки один из самых известных теоретиков QKD, мне его даже Макаров рекомендовал по поводу выяснения истины в QKD-вопросах.


Специально задал вопрос коллегам, они поклялись на крови заверили, что это ЛПП не соответствует действительности.


Ваш мир классический, а должен быть квантовым, когда рассуждаете о QKD. :) На самом деле, никакого чуда нет, всё просто. Надо с самого начала фиксировать словарь понятий, чтобы не было недопонимания.

Для QKD нужен аутентификацированный канал. Как вы его сделаете — вопрос третий. Представьте, что Алиса, Боб и Ева сидят в одной комнате и все друг друга слышат. Ева может делать всё, что угодно, кроме как лезть внутрь ящиков Алисы и Боба (DI QKD пока оставим в стороне). Ева слышит абсолютно всё, что говорит Алиса Бобу, а Боб Алисе. Никакого предрасшаренного секрета между Алисой и Бобом нет. Так вот, QKD в этих условиях будет работать. Будет ли работать шумовая криптография?

На примере BB84 можно пояснить так: Алиса случайно выбирает базисы (прямой/косой) и кодирует в них биты (0/1). Боб мерит полученные кубиты, случайно выбирая базис для каждого. Если канал между Алисой и Бобом идеальный, и в него никто не вмешивается, Боб угадает базисы только в половине случаев. Далее Боб говорит Алисе, какие базисы он выбрал. И по публичному, аутентифицированному, но нешифрованному каналу они выясняют, когда Боб угадал базис, а когда нет. Раскрывая базис, заметьте, они не раскрывают бит, который был в этом базисе. Ева их слушает и даже может узнать, какие базисы ей были угаданы верно, если она делала соответствующую атаку.

Затем Алиса и Боб из пересланных кубитов отбирают только те, которые соответствуют одинаковым базисам. На этом этапе половина кубитов и им соответствующих битов эффективно выкидываются в мусорку. Если Ева не вмешивалась в канал, то все полученные таким образом биты должны быть идентичны. Так ли это или нет — можно выяснить опять же по публичному аутентифицированному каналу, не раскрывая сами биты. Это и есть процедура исправления ошибок, reconciliation. И вот теперь начинается самое интересное: сколько обнаружено ошибок по окончании «реконсиляции»? Теоретически должно быть 0. Практически — всегда больше нуля, потому что приборы неидеальны, есть непреднамеренные какие-то ошибки, а иногда даже прослушивающая сторона. В QKD консервативно считается, что любая ошибка в канале происходит из-за Евы, и протокол действует, исходя из этого. Важно, что можно доказать наличие однозначной связи между числом ошибок после реконсиляции и объёмом той информации, которая утекла Еве (см. вышеупомянутого Деветака-Винтера). Таким образом, по окончании процедуры Алиса и Боб знают точно, насколько в их канал вмешивалась Ева. В зависимости от степени её вмешательства они исправляют ошибки и урезают свои итоговые строки до более коротких.

Чем больше вмешательство Евы, тем более короткий ключ им удастся вывести при той же степени его ε-безопасности. Кроме того, есть и такой порог, когда длина безопасного ключа становится равной нулю. С теоретической точки зрения пропускная способность QKD-канала определяется скоростью Деветака-Винтера, которая равна разности между взаимной информацией Алисы и Боба и взаимной информацией Боба и Евы (вроде так): I(A:B)) – I(B:E). В большинстве статей по QKD очень любят рисовать график этой скорости в зависимости от, например, степени шумов в канале. Кривые выглядят так: сначала монотонное и выпуклое вверх постепенное убывание, а потом очень резкое и быстрое убывание до нуля. Пересечение с нулём и есть тот уровень шума, когда безопасный QKD-канал установить невозможно.

Вопрос: зачем здесь нужен предрасшаренный секрет?

Теперь вернёмся к статье и вашим цитатам. Очевидно, на практике аутентифицированный канал надо как-то делать и делать его удобным. Алиса с Бобом обычно сидят не в одной комнате, и базисы не будут другу другу вслух диктовать, т.е., нам нужна аутентификация какая-то более автоматическая. Вот здесь как раз и приходит помощь от Вегмана-Картера, основанная на том, что обе стороны имеют общий секрет. Однако, можно рассмотреть и любой другой способ: доверенный телефон, асимметричную криптографию с PGP. Плюсы и минусы каждого подхода, думаю, очевидны. Тем не менее, на уровне концептуальном, это всё же очень важный момент: предрасшаренный секрет используется исключительно для аутентификации, и ни для чего больше. Например, он никак не используется для «аутентификации» в смысле распознавания кубитов, которые были посланы Алисой (чувствуете тонкую разницу между двумя смыслами слова «аутентификация»?). Т.е., Бобу абсолютно всё равно, кем были посланы кубиты. Мерит их он одинаково, а выводы делает совсем постфактум. В других же протоколах (судя по вашему описанию шумовой криптографии) предрасшаренный секрет служит ещё для чего-то.


Да, вот этот шаг верный. Кончается один сеанс передачи данных, потом начинается другой, который нужно аутентифицировать данными с предыдущего. В этом смысле оно и становится key growing. Тем не менее, концептуально на предрасшаренный секрет ничего не завязано — этот момент важный, если вы хотите прояснить связь и отличие шумовой криптографии от квантовой. В QKD считается, что всё, что находится между Алисой и Бобом, «заполнено Евой». Ева может делать всё, что хочет: заменить оптоволокно на своё собственное, менять шумы, вбрасывать, слушать всё, что передаётся по аутентифицированному каналу, но ничего из этого ей не поможет: она либо сорвёт канал связи, либо не сможет повлиять на его безопасность. Все эти смыслы вкладываются в слово unconditional.

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


Можно, если бы QKD развивали так же, как шумовую криптографию с длинным перечнем того, что может и что не может делать Ева. Что такое «классичееский» рипитер? Это Ева в канале между Алисой и Бобом — с точки зрения изначального QKD-протокола и его идеологии это именно так. Если вы хотите померить кубиты и переизлучить их, вы вносите шум и можете узнать информацию о том, что в кубитах пересылалось. Если рипитер не сильно возмущает среду, то Алиса с Бобом, возможно, смогут установить безопасный QKD-канал связи, как и ранее (считая рипитер допустимым шумом в канале), только вот вопрос эффективности усиления сигнала таким усилителем будет под большим вопросом. По всей видимости, такие классические рипитеры, которые укладываются в допустимую долю шума в канале (т.е., когда QKD-канал установить ещё можно), малоэффективны, и поэтому про них ничего не слышно. Но опять же, мы могли бы завязаться на тот факт, что у нас оптоволокно имеет определённую длину, что там обязательно стоит по середине репитер, и мерить отклонения от этого уровня шума, приняв его за ноль, но кому нужна такая модель? Ева всегда может вместо используемого оптоволкна положить своё, залезть в рипитер или ещё как-то модифицировать канал так, чтобы «эффективно нулевой уровень шума» не был повышен. В общем, не взлетит.

Что касается настоящих рипитеров, «квантовых»,* то, во-первых, они работают поверх несколько других QKD-протоколов, как мне намекнули. Там скорее что-то типа E91 будет, чем BB84, поскольку необходимо нужна запутанность (никакой запутанности в BB84 нет). Во-вторых, условия на рипитеры остаются в точности теми же, что и ранее: никакого доверия к среде между Алисой и Бобом. Если там стоит идеальный квантовый рипитер, имеем всё ту же нулевую ошибку после процедуры согласования для идеального канала, а все ошибки списываем на атакующего. Для нас как бы всё равно, что было: ноль затухания или куча потерь в канале, но с наличием рипитера между Алисой и Бобом, этот шум компенсирующим, — с точки зрения протокола ситуации эквивалентны.


Я пролистал, но не вчитывался в работу. Сходу кажется, что ничему вышенаписанному это всё-таки не противоречит. Т.е., имеется квантовый канал в наличии ⇒ можно сделать USAE.


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


2n бит, чтобы затерять n бит, как утверждается в цитате — это уже неплохо, даже очень неплохо. Это ещё не экспоненциальный рост.


... если мир классический. :)


Трудно не согласиться. С другой стороны, не хочется сильно тратиться на ловлю рыбы там, где её нет. Конечно, всегда лучше разобраться со всем самому, но время — это тоже ресурс. В данном случае я «мечусь» между двух огней: меж вас, как сторонника шумового крипто, и коллег, которые его изучали в рамках знакомства с QKD и заявляют, что «безусловной безопасности там нет», и «доказать её принципиально не получится» (понятно, что в эти слова можно вкладывать совершенно разный смысл, но сейчас он более-менее выкристаллизовывается). Вот, очередной раз попытался выступить арбитром, чтобы выяснить, кто из вас прав, а кто виноват нет.**


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


Можно наклеить на прибор метку «он безопасен», но станет ли он безопасным только от нашей веры в это? Есть модели, а есть реальность. Для нужд теории важны, в том числе, и те модели, которые далеки от реальности; не всё имеет самое непосредственное применение. Когда мы начинаем говорить об условиях на Еву, сразу же возникают вопросы типа «насколько это уместные предположения?». В QKD есть надежда, что Еву выдавят окончательно, в том числе, и из экспериментальных имплементаций, а что делать с шумовым крипто, где надо сразу смиряться с тем, что влияние Евы неизбежно, и модель никогда не будет соответствовать тому, что происходит в реальности? Я немного утрирую, но смысл примерно в этом.


По ссылке[link56] unknown'а можно найти замечательную фразу:

It is impossible to construct an unbreakable cryptographically secure hash function. See e.g. [14] for definitions and proofs.

*Как бы получается, что есть «классические квантовые рипитеры» и «квантовые квантовые рипитеры» :). Впрочем, можно назвать квантово-квантовыми по аналогии с водно-водяными реакторами (это те, где вода — и теплоноситель и замедлитель).
**Правильнее было бы сказать «в чём суть аргументов обеих сторон», если быть точным, поскольку истина тут слишком относительна. :)
— Гость (06/06/2013 03:19)   

К слову, сейчас активно развивают такое понятие, как бесшумные усилители в CV QKD, преобразующие когерентные состояния как
| α 〉 → | Gα 〉,
где G — коэффициент усиления. Идеальный бесшумный усилитель сделать невозможно, поскольку его существование противоречит квантовой механике, но можно собрать недетрминистичный усилитель, который будет срабатывать в каком-то проценте случаев. Предполагается, что его вставка в CV QKD-канал может как-то увеличить дистанцию, на которой сможет работать протокол. Тем не менее, никакого убедительного пруфа пока нет, одни идеи. Бесшумный усилитель — пример концепта, который можно вставить в канал, и который, возможно, даст больше пользы от усиления, чем внесёт в него шумов. Заметьте, что подход к трактовке безопасности QKD здесь остаётся стандартным. К слову, было показано, что дополнительный шум в QKD-канале бывает полезен: информация между Алисой и Бобом I(A:B) уменьшается, но не так сильно, как информация Евы I(B:E), поэтому разность (Деветак-Винтер) становится выше. Иными словами говоря, Алиса с Бобом страдают от ухудшения пропускной способности, но Ева страдает непропорционально больше, поэтому итоговая скорость расшаривания ключа между Алисой и Бобом увеличивается.

О бесшумном усилителе уже упомналось[link59], но кратко и искажённо:

Операция, позволяющая увеличить α при как можно меньшем увеличении тепловых фотонов, называется бесшумным усилителем («noiseless amplifier»). Предполагается, что новые протоколы QKD в непрерывных переменных с использованием «бесшумного усилителя» позволят увеличить дистанцию передачи информации

В этом тексте немного перемешано тёплое с мягким. Amplification channel — это как раз обычный усилитель, с шумом, но он был бы бесполезен для QKD, так как тепловые фотоны растут вместе с α-ой. Бесшумный же усилитель — это нечто совсем другое, да ещё и недетерминистичное. Какая-то аналогия между ними есть, но путаться не надо, хотя слово «усиление» используется в обоих случаях.
— Гость (06/06/2013 03:39)   

Кстати, можно придумать простой жизненный пример. Представьте, что вы прекрасно знаете SATtva'у по голосу, но не успели с ним обменяться каким-либо ключевым материалом и разъехались в разные концы света. Если вы захотите установить связь, можно было бы позвонить SATtva'е и попросить продиктовать его отпечаток PGP-ключа — это работает, если мы верим в вычислительно-стойкую безопасность, отсутствие эффективных КК и невозможность противника подменять ваш разговор в реальном времени. Но допустим, что первые 2 требования уже не выполняются, но выполняется третье. Напоминаю, что никакого предрасшаренного секрета между вами нет, а противник прослушивает все ваши каналы связи. Так вот, если между вами есть QKD, этого достаточно, чтобы установить шифрованный канал связи с SATtva'ой. Заметьте, что в чисто классическом мире эта задача не имеет решения.
— Гость (06/06/2013 03:54)   

Эх, опять не туда. Не сработало бы, поскольку SATtva предпочитает[link60] бронетанковые колонны и автоматичиков классику. По QKD он с вами общатьтся не стал бы, вместо этого он предпочитает убить Еву при попытке подслушать канал. Хотя... кому я это объясняю, вы и сам такой[link61]. Это вы только в интернете все добрые, а в жизни при передаче секретов ведёте себя в соответствии с active secret protection.
— Гость (06/06/2013 05:31)   

sentaus тоже[link62]. Весь коллектив такой. :(
— unknown (06/06/2013 11:24, исправлен 06/06/2013 12:29)   

N. Ferguson and B. Schneier. Practical Cryptography. Wiley Publishing, Inc., 2003.


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



Специально задал вопрос коллегам, они поклялись на крови заверили, что это ЛПП не соответствует действительности.

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


Представьте, что вы прекрасно знаете SATtva'у по голосу, но не успели с ним обменяться каким-либо ключевым материалом и разъехались в разные концы света.

Так вот, если между вами есть QKD, этого достаточно, чтобы установить шифрованный канал связи с SATtva'ой.


  1. unknown — SATtv'e: посылает n блоков по шумовому каналу: B{0…255}, B{256…511} … B{n•256…n•256+255}
  2. Sattva — unknown'u: диктует суммы на основе экстракторов принятых блоков H0 (B{0…255}), H1 (B{256…511}), … Hn (B{n•256…n•256+255}).
  3. unknown — SATtv'e: диктует список неверно принятых кодов.
  4. Из совпавших блоков обе стороны экстрактором выводят общий ключ.

Заметьте, что в чисто классическом мире эта задача не имеет решения.

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


В чём разница между классическим и квантовым миром конкретно по этому пункту?


По поводу того, что в квантовом канале лучше обоснованы требования к среде — согласен.


Например, он никак не используется для «аутентификации» в смысле распознавания кубитов, которые были посланы Алисой (чувствуете тонкую разницу между двумя смыслами слова «аутентификация»?). Т.е., Бобу абсолютно всё равно, кем были посланы кубиты. Мерит их он одинаково, а выводы делает совсем постфактум. В других же протоколах (судя по вашему описанию шумовой криптографии) предрасшаренный секрет служит ещё для чего-то.

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


Кстати, этот диссер меня всё-таки удивил: http://www.is.titech.ac.jp/~ch.....t/Por_Phd-thesis.pdf[link46] Там и квантовое шифрование и квантовая асимметрика и аутентификация и различие между классическим и квантовым одноразовым блокнотом и прочими информационно-стойкими алгоритмами.



Вот этого я и не понял, если честно. Похоже, речь о разных задачах — может это недостаточное условие. Мне казалось, что для IT-AONT нужно что-то порядка 2nn или ( 2n )n (гамма на шифрование и на хранение XOR-результата и по гамме на IT-перемешивание каждого бита в шифртексте, чтобы не знать, где он находится), что близко к определению японцев по ранней ссылке. Так бы получился IT-AONT, который можно было бы пошифровать обычным алгоритмом с секретным ключом. Вот тогда знание открытого текста дало бы ничтожно мало информации для криптоанализа противником.

— SATtva (06/06/2013 15:06)   
SATtva предпочитает бронетанковые колонны и автоматичиков классику.

Это было давно и неправда. :Р
— Гость (06/06/2013 18:52)   

Вопрос на миллион долларов: и почему же это невозможно?
— Гость (06/06/2013 19:46)   

Из совпавших блоков все три стороны экстрактором выводят общий ключ.

Fxd. :) Работать будет.


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


Видимо, ни в чём.


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

нет независимого от сторон (и разного для них) шума внешней среды, который включается в совместно вырабатываемую гамму и делает её разной для всех троих.

А это, между прочим, ключевое требование. Нет этого требования — нет никакого доказательства безопасности вообще. Грубо говоря, Ева будет знать либо всё, что получил Боб, либо всё, что посылала Алиса.


Да.


Может, не только, но я пока вижу только это. Впрочем, это достаточная и существенная разница, почему — я выше уже пояснил.


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


С такой[link63] прягой группой поддержки было бы трудно[link64] не удивить: Реннер, Жизан, Видик, Дунько, Маурер (первых четырёх знаю лично). Кстати, символично, что в этом диссере я не вижу ничего про шумовую крипторафию. Вот как только хороший уровень работ и известные лица, так сразу молчок про шумовую. Может быть, я слеп? Всё, что нашёл — это косвенное упоминание на стр. 18:

In 1984 Bennett and Brassard [BB84] proposed a quantum key distribution protocol, which was shown in subsequent work to achieve perfect security [May96, SP00, Ren05].

Ссылка May96 — на что-то шумовое. Если они разработали столько полезным примитивов для шумовой криптографии, странно, почему они не говорят о применении их в ней.
— unknown (07/06/2013 00:04)   
Из совпавших блоков все три стороны экстрактором выводят общий ключ.

Fxd. :) Работать будет.

Если канал безшумовой или третья сторона имеет полный контроль над шумом.

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

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


Да нет, так и есть. А кому охота лезть в маргинальщину или в потенциальное болото?

Вот только тогда не говорите, что Беллейр[link65] — неизвестное лицо. В своей работе с соавторами он упоминает (правда всё равно расплывчато), почему шумовое крипто десятилетиями ничего породить не могло. В т.ч. потому что как раз никто из известных людей им не хотел заниматься.

Тэги: Information-theoretic security, entropy, keyless. Внезапно, грант от DARPA, много критики существующего "wiretap community", их слабых доказательств безопасности и указание на немалое число исследований в этой области.
— Гость (07/06/2013 01:19)   

Что вам дадут экстракторы? Хэши уникальны, но дают только вычислительную стойкость. Можно было бы диктовать синдромы, но синдромы ничего не гарантируют: они не хэши, они позволяют оценить только уровень ошибок в шумовом канале, но не сделать заключение об одинаковости блоков. Вы не можете IT-безопасно убедиться в идентичности двух битовых строк, не передав эти строки целиком, синдром даёт лишь косвенную информацию о совпадении.


Наверное, хотели сказать «известное»? Спасибо, статью посмотрю.

Может, действительно, шумовое крипто — это какая-то зона отчуждения: всего много, ничего не понятно, и никто не хочет рисковать туда вкладываться, потому что успех и признание работ не гарантированы.
— Гость (07/06/2013 01:56)   

Если под словом «конкретный канал» вы подразумеваете набор условий и предположений о среде между Алисой и Бобом, то да, в квантовом же случае среда банально отождествляется с Евой. Как только вы вышли за пределы лаборатории Боба или Алисы, так там сразу же появляется всевластная Ева, делающая всё, что только можно, в рамках физики (а потенциально можно многое). Т.е. банально состояние всей системы Алиса+Боб+Ева+Канал — это
ρtotal = ρA ⊗ ρB ⊗ ρE,*
с собственно каналом ничего отождествлять дополнительно не надо. Ева — сама среда. Хотите описать эволюцию открытой (т.е. неизолированной) системы — всегда можете считать, что есть более «широкая» система (в большем пространстве), включаящая в себя как целевую систему, так и среду (ancilla'у), и при этом описываемая неким оператором плотности ρtotal или вектором состояния | ψtotal 〉.

Можно спекулировать о том, где шум устарним, а где нет, где можно сыграть на неидеальности, а где нет, но был один знаменитый опыт[link66] с фуллеренами и Цайлингером во главе. Он как бы символизирует, что попытка спрятаться в чём-то классическом потенциально всегда может быть нивелирована, вопрос только в стоимости.

*Это — если все трое друг с другом не связаны. Если же связаны, то ρtotal будет принадлежать тому же пространству, но не будет факторизованным по подсистемам.
— Гость (07/06/2013 05:49)   

Просмотрел работу. Бросились в глаза цитаты:

Contrary to a view in the I&C community, compression does not render data random, as can be seen from the case of votes, where the message space has very low entropy.

In the wiretap literature it is sometimes argued that the assumption of uniformly distributed messages is tenable because messages are compressed before transmission. But compression does not result in uniformly distributed messages. Compression is a deterministic, injective function and does not change the entropy.

Это по поводу того, что кто-то хотел диски сжимать перед шифрованием. :)


Конкретно на этот счёт ничего не увидел. Может быть, просмотрел.

Как я понял, один из главных критицизмов — это

Moreover, both definitions only consider uniformly distributed messages.

Т.е., считалось без ограничений, что Алиса через шумовой канал передаёт Бобу только рандомные битовые строки? Казалось бы, если шумовая криптография, как и квантовая, используются только для генерации одноразового блокнота, который будет потом использоваться для шифрования по обычному каналу связи, то всё ОК.

That is, existence of secrecy capacity achieving schemes is proven via the probabilistic method, and the resulting scheme is neither explicitly given, nor it is guaranteed to be efficient. In fact, to date, only a handful of efficient schemes are known.

Этот критицизм тоже понятен, но он, на мой взгляд, несущественный. Если есть доказательство существования, схему, достигающую результат, всегда можно соорудить (криптография и теория информации — не ахти какая абстрактная математика), хотя это бывает и трудно (но с концептуальной точки зрения вопрос закрыт теоремой существования). Впрочем, достижение ёмкости — не такой простой вопрос. Например, в докладе Холево, который можно посмотреть на youtube, он утверждает, что лучше коды по достижению ёмкости — это турбо-коды, но и они дают всего лишь 70% от пропускной способности. Правда, там это может быть так только из-за того, что канал квантовый. Как оно обстоит с чисто классическими каналами — не в курсе.

Обзор Bellare'а основательный, но сразу видно, но он пишет для людей «в теме», поэтому многие его определения людям со стороны (и мне, в том числе) неясны.


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

P.S.: Смотрите, как тонко[link67] троллит Bellare линуксоидов:
Impact: Co-developer of HMAC authentication algorithm which is an IETF IPSEC Internet Standard and ANSI X.9 keyed hash standard, currently being used in numerous products including BSAFE (RSA Data Security Corp.), SSL (3.0 and 3.1), S-HTTP, NetBSD, CDSA (Hewlett-Packard)
— unknown (07/06/2013 14:43, исправлен 07/06/2013 14:49)   

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


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


Также каналы на переполнении памяти оцифровщиков (совместная оцифровка шума космических шумов).

— Гость (10/06/2013 02:50)   

Если считать, что канал каким-то образом аутентифицирован, то в QKD всё делается побитово и предельно просто, а Вегман-Картер — это сложно (хоть и неизбежно на практике), я с ним не разбирался. Там, наверное, берутся какие-то сложные функции от набора битов, поэтому так же легко и на пальцах, как про QKD, это не объяснить. В описании В-К тоже сказано, что он непрост, и что вообще про IT-аутентификацию мало кто знает почему-то.

Касаемо IT-аутентификации с В-К сразу же возникают вопросы, есть ли там защита от переотправки сообщений, от выкидывания части сообщений и т.д. Наверное, есть, но я с этим не разбирался.


При участии в сессии заверителей PGP вы получаете отпечатки ключа других лиц, не имея предрасшаренного секрета с ними. Считаете ли вы сессии заверителей для передачи отпечатков ключей информационно-стойкими способами передачи отпечатков? Не забывайте, что между людьми может ходить Ева в парике и подменять чьи-то записи отпечатков на бумаге, паспорта, лица.

Криптография решает задачу IT-аутентификации, когда предрасшаренный секрет уже есть. Вопрос: откуда он возьмётся? Чтобы он взялся, нужно уже иметь аутентифицированный канал, т.е., круг замкнулся. Имеем всё ту же проблему курицы и яйца: что было раньше, аутентифицированный канал или предрасшаренный секрет? Именно из-за этих соображений я считаю, что не надо мешать в одну кучу понятие аутентифицированного канала и конкретные способы создания таких каналов. Сам по себе аутентифицированный канал — это просто, по определению, такой канал, что Ева не может каким-либо образом модифицировать передаваемые данные, и всё (т.е., это некое идеализированное понятие). Каким образом этого добиться в реальной жизни или с помощью криптопримитивов — вопрос вторичный по отношению к самому определению. Например, как в вашем примере, Алиса может убить на планете всех, кроме Боба, и передать ему сообщение открытым текстом — это тоже валидный пример аутентифицированного канала.
— unknown (10/06/2013 09:46, исправлен 10/06/2013 09:46)   
а Вегман-Картер — это сложно (хоть и неизбежно на практике), я с ним не разбирался. Там, наверное, берутся какие-то сложные функции от набора битов, поэтому так же легко и на пальцах, как про QKD, это не объяснить.

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


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

Это скорее извечный вопрос, что включать в протокол, а что выводить за его рамки и решать строго неформализуемыми организационными методами (проверка голосов и париков, будки с охранниками, БТРы с автоматчиками).

— Гость (10/06/2013 10:27)   

В общем, да. Даже при использовании IT-стойкой аутентификации/криптографии вы вынуждены доверять, например, ПК, собственным глазам и изображению на мониторе, хотя всё это потенциально можно подменить.
— Гость (10/06/2013 10:30)   
... чем занимается, например, социнженерия.
— Гость (02/12/2013 10:15)   

В пику обсуждений[link69] одноразового блокнота[link70] попалась статья на эту тему и на тему вышеобсуждавшейся non-malleability: «Non-malleable encryption of quantum information»[link71]. На 1-2 страницах:

The ordinary (and in terms of secret key length, optimal) encryption of quantum states on n qubits is by applying a randomly chosen tensor product of Pauli operators (including the identity). This requires 2n bits of shared secret randomness, corresponding to the 4n Pauli operators. (More generally, for states on a d-dimensional system, one can use the elements of the discrete Weyl group ­ up to global phases ­ of which there are d2 .) This is perfectly secure in the sense that the state the adversary can intercept is, without her knowing the key, always the maximally mixed state. For perfectly secure encryption with random unitaries, it was shown in [2] that 2n bits of secret key are also necessary for n qubits. The lower bound of 2 bits of key per qubit continues to hold even for ε-approximate encryption (up to expressions in ε), but there it becomes relevant how the approximation is defined -- whether it randomizes entangled states or not [see Eq. (2") and (2') below]. In [16] it was shown that in the latter case one gets away with n + o(n) key bits for arbitrary n-qubit states; their construction was derandomized later in [3] and [11].

However, even perfectly secure encryption allows for a different sort of intervention by the adversary: she can, without ever attempting to learn the message, change the plaintext by effecting certain dynamics on the encrypted state. Consider briefly the classical one-time pad, i.e. an n-bit message XORed with a random n-bit string: by flipping a bit of the ciphertext, an adversary can effectively flip any bit of the recovered plaintext. In the quantum case, due to the (anti-)commutation relations of the Pauli operators, by applying to the ciphertext (encrypted state) some Pauli, she forces that the decrypted state is the plaintext modified by that Pauli …

This is evidently an undesirable property of a encryption scheme, and can be classically addressed e.g. by authenticating the message as well as encrypting it. Interestingly, in the above quantum message case, it was shown in [4] that authenticating quantum messages is at least as expensive as encrypting them (it actually encrypts the message as well): one needs 2 bits of shared secret key for each qubit authenticated, even in the approximate setting considered in [4]. Classical non-malleable cryptosystems include both symmetric and asymmetric encryption schemes, bit commitment, zero knowledge proofs and others [12].

Here we will introduce a formal definition of perfect non-malleability of a quantum state encryption scheme (NMES), i.e. resistance against predictable modification of the plaintext, as well as of two notions of approximate encryption with approximate non-malleability. We show that a unitary non-malleable channel is equivalent to unitary 2-design in the sense of Dankert et al. [9]. We use this fact to design an exact ideal non-malleable encryption scheme requiring 5 log d bits of key.

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

Трюк с кличкой собаки[link72] IT-стойко не заработает в том смысле, что нельзя IT-стойко зашифровать большой массив данных коротким ключом, это не взлетит, понадобится вводить какие-то ограничения в духе bounded memory model или ещё какие-то ограничения на атакующего. Хорошо было бы иметь изящное доказательство этого факта, но мне пытались объяснить на пальцах. Я вникал, переспрашивал, но так и не осилил смысл, потому что он противоречил моей картине представлений в самых основах (например, невозможности извлечь информацию без возмущения системы). Присутствовавшие при разговоре свидетели, как и другие коллеги, неприсутствовавшие, тоже не смогли растолковать смысл этих заклинаний, поэтому, наверное, нет смысла их здесь пересказывать. Тем не менее, у меня закралась идея об альтернативном объяснении того, почему не взлетит: в криптографии требуется стойкость к знанию атакующим открытого текста, и это очень сильное требование, которое на больших массивах данных не может быть удовлетворено коротким паролем. Иными словами говоря, атакующий знает слишком много, и весь объём его знаний не нейтрализовать до нуля коротким паролем.

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


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


Беннет интересную вещь сказал про шифрование. Якобы в ранних работах Визнера была схема с кодированием двух битовых строк в набор кубитов таким избыточным образом (заранее закладывалась нужная система коррекции ошибок), что операции (измерения) по извлечению этих строк (Или сами состояния? Детали не понял) были почти ортогональны друг другу. Я так понимаю (а я могу ошибаться), что из этого следует, что атакующий до начала измерений должен был сразу определиться, какую из битовых строк он извлекает. И если он вдруг начал извлекать не ту, то будет уже «поздно» что-то исправлять, чтобы извлечь правильную (non-malleability?). Насколько это было реально безопасно и обоснованно — не знаю, работу пока даже не гуглил и не знаю, можно ли её нагуглить по такому общего описанию.

Реннер — бог №1 в мире в области теории по квантовому крипто (в широком смысле этого слова), и Уэли Маурер — отец его его руководитель по диссертации, поэтому с ε-точностью, где ε→0, можете считать это мнение истиной в последней инстанции.
— unknown (02/12/2013 10:54)   
Ограниченное non-malleability возможно и при использовании обычного одноразового блокнота, если использовать две некоммутирующие гаммы: например, одну для обычного XOR, а вторую — для перестановок внутри отдельных блоков. А чем Вегман-Картер то не угодил?
— Гость (02/12/2013 11:52)   

А какой у него битовый расход? Честно говоря, не знаю. Тут вопрос ещё ранее возникает, уже на фразе

For perfectly secure encryption with random unitaries, it was shown in [2] that 2n bits of secret key are also necessary for n qubits.

Номинально всё чисто, потому что они говорят «рассмотрим случай "encryption with random unitaries"», но кто сказал, что нельзя иначе? Берём любой базис и кодируем туда битовые строки как

00101100 → |0〉⊗|0〉⊗|1〉⊗|0〉⊗|1〉⊗|1〉⊗|0〉⊗|0〉 = [по определению] = |00101100〉,

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

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

Я, конечно, понимаю, что есть специальные задачи, в которых без шифрования на основе унитарных повротов никак, но ведь наверняка авторы не ими мотивировались... Кстати, при локинге информации вроде тоже унитарные преобразования используются, хотя там условия на безопасность очень слабые по сравнению с обычными криптографическими.
— unknown (02/12/2013 12:38, исправлен 02/12/2013 12:44)   
А чем Вегман-Картер то не угодил?

А какой у него битовый расход? Честно говоря, не знаю.

Разные оптимизации есть[link76], вот ещё публикация[link77] и внезапно, в продолжение предыдущей работы, Direct Proof of Security of Wegman-Carter Authentication with Partially Known Key[link78] — оценка стойкости при утечке сведений о ключе или его неидеальности.


Отсюда[link56]:


One round of hashing halves the length of the message, regardless of its size, but uses only one hash function, and only one small key to pick that hash function. The total key length needed therefore grows with approximately the logarithm of the message length. This means a QKG system can always be designed with large enough rounds to make the key used for authentication acceptably small in comparison to the created shared secret.

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

— Гость (11/02/2014 22:30)   

Похоже, вот оно[link79]:

One-time memories (OTM's) are a simple type of tamper-resistant cryptographic hardware. An OTM has the following behavior: a user Alice can write two messages s and t into the OTM, and then give the OTM to another user Bob; Bob can then choose to read either s or t from the OTM, but he can only learn one of the two messages, not both. A single OTM is not especially exciting by itself, but when many OTM's are combined in an appropriate way, they can be used to implement one-time programs, which are a powerful form of secure computation [2, 3, 4, 5]. (Roughly speaking, a one-time program is a program that can be run exactly once, on an input chosen by the user. After running once, the program "self-destructs," and it never reveals any information other than the output of the computation.)

These results use Wiesner's idea of conjugate coding, combined with error-correcting codes that approach the capacity of the q-ary symmetric channel, and a high-order entropic uncertainty relation, which was originally developed for cryptography in the bounded quantum storage model.

Ссылки [2-5] тоже стоит глянуть, но я пока не смотрел (кстати, ссылка [5] — та работа, которая здесь уже упоминалась[link80]). И вот слайды[link81] к этой работе (интересно, там ссылка на того самого Дамгарда, который DM?). К слову, слайды почти всех докладов с QIP[link82]-2014[link83] доступны[link84].


Оказывается, всё проще. Винтер, автор этой работы («Non-malleable encryption of quantum information»), сказал, что цель была создать квантовое шифрование в смысле шифрования, которое шифрует квантовую информацию, а не классическую. Т.е. идея в сокрытии самих состояний кубитов, а не классических битов, в них закодированных. И это получается quantum one time pad в смысле СQQ (или даже QQQ[link85]), а не в смысле CQC (по порядку: тип входа информации, тип её хранения, тип выхода). А если говорить о CQC, то Винтер подтвердил, что, да, можно иметь и n бит пароля для n бит текста, как в классике.

Про остальное позже.
— Гость (12/02/2014 09:55)   

Он самый[link86]. Если близко не приглядываться, то это самый обычный чисто классический криптограф:

He is known among other things for the Merkle–Damgård construction used in most modern cryptographic hash functions such as SHA-1 and MD5. He discovered the structure independently of Ralph Merkle and published it in 1989.

Но не зря на него Омар ссылается. Если кое-что знать, то можно обнаружить вовлечённость Damgård'а в квантовое шифрование, QKD и создание поточных квантовых шифров, прям с Реннером в соавторах:

I[link87]van Damgård, Serge Fehr, Renato Renner, Louis Salvail, Christian Schaffner: A Tight High-Order Entropic Quantum Uncertainty Relation with Applications. CRYPTO 2007: 360-378

Вот вам и классический криптограф... Вот сама работа[link88]. В аннотации:

Our uncertainty relation also yields a lower bound on the min-entropy key uncertainty against known-plaintext attacks when quantum ciphers are composed. Previously, the key uncertainty of these ciphers was only known with respect to Shannon entropy.

А эта работа является производной от ранней работы[link89] того же Damgård'а с Eucrocrypt'04:

We consider the scenario where Alice wants to send a secret (classical) n-bit message to Bob using a classical key, and where only one-way transmission from Alice to Bob is possible. In this case, quantum communication cannot help to obtain perfect secrecy with key length smaller then n. We study the question of whether there might still be fundamental differences between the case where quantum as opposed to classical communication is used. In this direction, we show that there exist ciphers with perfect security producing quantum ciphertext where, even if an adversary knows the plaintext and applies an optimal measurement on the ciphertext, his Shannon uncertainty about the key used is almost maximal. This is in contrast to the classical case where the adversary always learns n bits of information on the key in a known plaintext attack.
...
We suggest an application of our results in the case where only a short secret key is available and the message is much longer.

Во введении:

We study the question of whether there might still be some fundamental differences between the case where quantum as opposed to classical communication is used. In this direction, we present two examples of cryptosystems with perfect security producing n-bit quantum ciphertexts, and with key length m = n + 1, respectively m = 2n. We show that given plaintext and ciphertext, and even when applying an optimal measurement to the ciphertext, the adversary can learn no more than n/2, respectively 1 bit of Shannon information on the key. This should be compared to the fact that for a classical cipher with perfect security, the adversary always learns n bits of information on the key. // Стр. 2

Если перевести на человеческий язык, Damgård хочет сказать следующее:
  1. В классическом одноразовом блокноте n бит ключа нужно для шифрования n бит плейнтекста. Если плейнтекст известен, ключ восстанавливается полностью.
  2. В квантовом шифровании №1 требуется ключ длиной n+1 бит для шифрования n бит плейнтекста. Если плейнтекст известен, атакующий максимум узнает n/2 бит ключа.
  3. В квантовом шифровании №2 требуется ключ длиной 2n для шифрования n бит плейнтекста. Если последней известен, атакующий узнает максимум 1 бит информации о ключе.
Последние 2 пункта объясняют, в чём одно из преимуществ квантового одноразового блокнота перед классическим. Далее, на стр. 5, дано формальное определение того, что считается квантовым шифром для классической информации.

Судя по всему (чего и следовало ожидать), без завязки на вычислительную стойкость и дополнительные допущения (т.е. в рамках IT-безопасности) классический предел «n бит ключ на n бит текста» не побить, поэтому когда они переходят в квантовому поточному шифру (стр. 15), требуют следующее:
  1. ГПСЧ не может быть предсказан атакующим за полиномиальное время.
  2. Атакующий не может производить произвольные измерения (т.е. когерентные) над квантовой системой, состоящей более, чем из некоторого числа кубит. Грубо говоря, оперирование с n-частичными запутанными состояниями ему не под силу.
  3. Атакующий сначала производит полное измерение, не выходящее за пределы допущений в п.2, а потом выполняет только классическую часть протокола по взлому, требующую не более, чем полиномиальное время.
При этих предположениях квантовый поточный шифр оказывается вроде как лучше классического. И в заключении:

a resource-bounded adversary would be in a potentially much worse situation than with any classical stream-cipher with the same parameters. // Стр. 17

Реннера благодарят за нахождение ошибки в одном из доказательств. ☺

Интересно, что в этой работе поминается статья Маурера и Массея. Я раньше глубоко не интересовался, кто такой Массей, но отметил для себя, что у него есть замечательная работа «Guessing and entropy»[link90], идея которой была позднее развита в «On the foundations of quantitative information flow»[link91] от Smith[link92]'а, который из этого вырастил фактически целое направление со своей[link93] школой[link94]. Это всё про самое то, что нужно: privacy & leakage. Так вот, оказывается этот самый Массей отнюдь не случаен и по математической генеалогии приходится отцом Мауреру и дедом Реннеру[link95], хотя до сего дня я думал, что они вообще из разных школ и никогда друг про друга не слышали. Таже с удивлением узнал, что Массей[link96] — соавтор шифра IDEA, и умер он от рака в прошлом году. ☹ На концептуальном уровне число Эрдёша[link97] как бы закрывает проблему (связность в исследовательском сообществе имеется[link98]):

Существует гипотеза, гласящая, что число Эрдёша любого математика не превосходит десяти.

но всё равно удивляет порой, насколько все друг с другом связаны.
— unknown (12/02/2014 10:05)   
Возникает самый наивный вопрос о возможном протоколе:

  • Алиса кладёт в «квантовую коробочку» два сообщения s и t, связанные одноразовой памятью посредством conjugate coding или незнамо чего-там внутри под капотом в этом чёрном ящике.
  • Алиса посылает квантовую коробочку Бобу обычной почтой.
  • Боб открывает сообщение-строку на выбор s или t и посылает от него хэш Алисе. Хэш м.б. инф.-теор. стойкий, с аутентификацией по Вегману-Картеру.
  • Алиса определяет по хэшу, какое сообщение из двух открыл Боб и договаривается его использовать в кач-ве гаммы одноразового блокнота.
  • Ева в этой схеме вроде как не при делах, так что сообщение-ключ для одноразового блокнота в квантовой одноразовой памяти можно посылать хоть почтой России. Сетевой квантовый канал с волокном и фотонами не нужен. Нужна обычная почта с посылками без требований доверенных курьеров.
— unknown (12/02/2014 10:17, исправлен 12/02/2014 10:18)   

В теоретическом плане интереснее его своместная работа по сетям Лэя-Мэсси[link99]. Ну также, как Дамгард больше всего известен по хэшам Дамгарда-Меркла[link100].

— Гость (12/02/2014 11:46)   

Бобу же не нужен пароль на извлечение информации? Тогда MITM'им:

Алиса посылает квантовую коробочку Бобу обычной почтой.

А Ева осуществляет то же измерение, что и Боб мог бы, получает одну из строк (s или t). Далее она приготавлиает свой OTM, в котором одна из строк будет та, которую она получила при измерении перехваченного OTM. У Боба будет высокая вероятность получить при измерении тот же секрет, который готовила Ева (если не ещё хуже: Ева может, наверное, сделать так, чтобы Боб всегда получал именно то, что она ему закодировала, детерминистично, хотя Боб будет думать, что получает случайный результат). Соответственно, Боб полшёт обратно Алисе хэш сообщения, который Еве тоже будет известен. В итоге часть информации о ключе в ряде случаев будет утекать к Еве. Даже если предположение в скобках не может быть выполнено, и Алиса с Бобом смогут засекать наличие Евы на канале по ошибкам в нём, то чем это лучше исходного QKD, когда Алиса шлёт не OTM'ы, а кубиты с единичным битом, у которых тоже есть свойство «кто первый померил, тот и съел»? ИМХО, в таком случае это сведётся к тому, что вместо QKD на битах (кубитах) получим QKD на битовых строках (OTM'ах), а смысл будет тот же.

К тому же, на пратике обычно посылается не ящик с кубитами, а лучи света, которые Боб должен померить и вернуть потом какие-то результаты по классическому каналу. Раз это лучи света, там высоки потери и шумы. В традиционном QKD знают, как связан уровень шумов с максимально возможным влиянием Евы, а тут как делать? Выкидывать абсолютно всё, что пришло хотя бы с одной ошибкой? Так скорость вообще около нулевой может оказаться.
— unknown (12/02/2014 11:51, исправлен 12/02/2014 12:02)   

Тогда 128…256 ящиков с (ку)битами :) (ну, или с запасом против leakage), тогда только безопасность против перебора.



Тогда действительно хуже.



Тогда только экстрагировать конечный ключ и отказаться от инф.-теор. стойкости и OTP.


Фактически — это аналог шифрования с открытым ключом, головоломки Меркла[link101].


Да и идея физического ящика вместо канала связи была бы интересна сама по себе.

— SATtva (12/02/2014 12:37)   
если не ещё хуже: Ева может, наверное, сделать так, чтобы Боб всегда получал именно то, что она ему закодировала, детерминистично, хотя Боб будет думать, что получает случайный результат

Тогда 128…256 ящиков с (ку)битами :) (ну, или с запасом против leakage), тогда только безопасность против перебора.

Сообщения s и t обязаны быть неравны? Если нет, то, независимо от числа ящиков, Ева извлекает всё из ящиков Алисы и пересылает всё это Бобу в ящиках с парами идентичных сообщений. Установить факт их идентичности он ведь по условиям не может.
— unknown (12/02/2014 12:53, исправлен 12/02/2014 12:57)   

Ну, наверное, в ящике всё-таки не один (ку)бит, а строка кубитов s (в нашем случае с запасом на экстракцию или хэширование), инвертируя которую, нельзя получить вторую (t). В условиях сказано, что прочесть можно или s, или t. Тогда нужно 256 с запасом таких ящиков со спаренными взаимно-кодированными строками.

— Гость (25/07/2014 06:54)   

Есть вот такие работы, они чисто классические:


Считается, что у Алисы и Боба есть ящики с определёнными свойствами, которые в рамках модели нерушимы (как их создать — дело другое). Так вот, эти ребята поставили вопрос очень общо: что вообще интересного можно сделать в криптографии, обладая чёрными ящиками с такими свойствами? Оказалось, что практически всё. :-) Особенно вводная часть к «Founding» (второй работе) хорошо написана. Goldwasser на стр. 13 пишет про реализацию протоколов систем голосования, если б такие ящики существовали (см. также его обсуждение чёрных ящиков на стр. 16).

После этого аннтация к квантовой работе[link105] по созданию таких ящиков начинает играть другими красками:

Because software can, in principle, be copied, general one-time programs exists only in the hardware token model: it has been shown that any function admits a one-time program as long as we assume access to physical devices called one-time memories. Quantum information, with its well-known property of no-cloning, would, at first glance, prevent the basic copying attack for classical programs. We show that this intuition is false: one-time programs for both classical and quantum maps, based solely on quantum information, do not exist, even with computational assumptions. We complement this strong impossibility proof by an equally strong possibility result: assuming the same basic one-time memories as used for classical one-time programs, we show that every quantum map has a quantum one-time program that is secure in the universal composability framework.

Если нечто позволяет слишком много ништяков, значит, это нечто не может существовать? Интересно было бы понять CS-мораль этих басен.
— Гость (11/01/2015 23:14)   

Современные спекуляции на тему того, что так практичней, чем со светом пересылать:

F[link107]urthermore, by employing dynamic decoupling, a coherence time of 370 ± 60 minutes was achieved at 2 kelvin. It has been almost universally assumed that light is the best long-distance carrier for quantum information. However, the coherence time observed here is long enough that nuclear spins travelling at 9 kilometres per hour in a crystal would have a lower decoherence with distance than light in an optical fibre. This enables some very early approaches to entanglement distribution to be revisited, in particular those in which the spins are transported rather than the light.

Ну, и время когерентности уже 6 часов. Правда, при сверхнизких температурах. Пишут, что это всё для построения повторителей нужно.

В самой работе:

T[link108]he extension of this work to storage and retrieval of optical states would open up the possibility of remote entanglement distribution via the physical transport of memory crystals. A particularly attractive aspect of this idea is that it would allow entanglement distribution between remote locations with minimal permanent infrastructure.

Т.е. Алиса, чтобы расшарить запутанную пару между собой и Бобом, кладёт состояния в коробочку и отсылает её Бобу почтой России. :-)
— unknown (12/01/2015 02:17)   
Спасибо за информацию. Вот оно как интересно оказывается… Не прошло и года, как уже сделали прототип. Возможно, что даже сами авторы пока не вполне представляют, какое огромное число протоколов можно создать на основе таких коробочек. Может будет целый вал публикаций по новому направлению.
— Гость (12/01/2015 11:58)   
Это скорее форма удачного пиара. Просто на данный момент с переноской ядерных спинов научились делать лучше, чем со светом, но в перспективе всё может поменяться. Понятно, что послать луч света — это намного проще, чем таскать коробочки. Например, когда-то были очень популярны магнитные ловушки для одиночных частиц, а что теперь? Где они? Сейчас вместо них популярны, к примеру, токи в сверхпроводниках (так называемые «сверхпроводящие кубиты») или примеси в алмазах.
— unknown (28/03/2015 02:33)   
По поводу /comment74121[link109].

Меня особо не впечатлило non-malleability в одноразовом блокноте, ну разве что по цифрам в квантах. Можно же просто аутентификацию Вегмана-Картера прикрутить.

Но, во первых можно и сообщение в классике сделать таким же. Я намекнул об этом в /comment74125[link110]. Итак, для сообщения размером m нужно две гаммы, одна для подстановок (обычный XOR) размером m, а другая для перестановок всех битов между собой — размером m2. Итого, на обе одноразовые гаммы — m3. Для экономии гаммы при больших m сообщение можно разбить на блоки (их даже не надо между собой сцеплять, они рэндомизированные и одноразовые). Зная сообщение, противник не сможет вычислить гамму: подстановка и перестановка не образуют между собой группу. Легко подделать сообщение тоже не получится. Изменение одного бита в шифртексте приведёт к изменению одного бита в открытом тексте, но в непредсказуемом месте. Это конечно не полноценная non-malleability, но там наверное можно что-то классическое сверху прикрутить, наподобие AONT.

Теперь чуть менее тривиальная идея про IT-secure AONT[link58]. Упоминалась конструкция японцев. Её IT-стойкий вариант непрактичен, там сильно растёт размер сообщения. Но она ведь IT-стойкая? Обработаем ей сообщение M' = IT-AONT (M). Отрежем от M' 256 бит виде m0, так что M' = m0 ║ m1. Теперь m0 можно передать по IT-стойкому каналу (например квантовому), а m1 — по открытому. Ну по квантовому каналу что-то произвольное передать нельзя, можно просто согласовать 256 бит, которые поксорить с m0 и гнать это уже по открытому. Т.е. мы разменяли гамму крошечного размера на гигантский размер шифртекста. Представляете какие перспективы, с учётом того, что IT-стойкие каналы малопропускные и дорогие, а открытые каналы позволяют дёшево гнать данные с любым оверхэдом?

Тут возникает вопрос, что это какой-то информационный вечный двигатель. Так можно гамму одноразового блокнота любой длины уложить в 256 бит, что является полным абсурдом. Но тут нет никакого противоречия — так и надо делать! Просто это не явлется ни одноразовым блокнотом, ни IT-стойкой безопасностью. Это является строгой вычислительной безопасностью: противник должен подобрать 256 бит именно методом перебора и никаких других методов криптоанализа гарантированно не существует. У нас гарантированно стойкий идеальный потоковый шифр. К нему можно сбрутфорсить короткий ключ, но сокращённых методов криптоанализа быть не может — их существование противоречит IT-стойкой безопасности, они должны идти против теории информации (если абстракции нигде не протекают). Если передавать гамму размером m3, как в начальном примере, то можно соорудить и идеальный блочный шифр на таких IT-подпорках, только он никому нафиг не нужен. Хотя может для каких-то протоколов или для полутеоретических моделей и сгодится.

Теперь, казалось бы, причём тут Беннет, Реннер и кто там ещё был?

Они вам пытались объяснить, что:



Ну я вот это понял и показал на классическом примере, здесь чистая теория информация, квантЫ — это уже тонкости реализации, есть же совсем общие, фундаментальные принципы сохранения информации.


Я так понял, что они намекнули на возможности IT-стойких подпорок для построения доказуемой вычислительно-стойкой криптографии. Там ещё должен быть нюанс: с помощью 256 бит можно передать естественно только один классический OTP по классическому каналу за один сеанс, раздувая его до соответствующего размера через IT-AONT. Один короткий ключ не может повторяться, иначе стойкость всей схемы рухнет. И даже для ключа 256 бит из-за неидеальности всей схемы есть какой-то зазор, хорошо если только в один бит и неизвестно как он может меняться от размера m.

Но согласование OTR через IT-AONT с согласованием маленького кусочка по квантовому каналу и большого OTR по классическому — это уже частности. Можно и сами сообщения сразу гнать через IT-AONT. Большой OTR — это уже так, про запас, когда IT-стойкий канал редко доступен.
— Гость (30/03/2015 03:13)   

Я не понял, как у вас получилось, что количество перестановок всех битов сообщения m — это m2.


Information locking позволяет делать то же самое, насколько я помню, но там вместо классической гаммы надо пересылать квантовые состояния, да. По-моему, это как-то даже пытались доразвить до уровня чего-то типа QKD (quantum enigma machines с Ллойдом, я кидал ссылку).


Звучит достаточно революционно. Вы думаете, такая идея могла бы победить на следующем конкурсе AES и закрыть вопрос криптоанализа симметричных шифров раз и навсегда?


Почему не нужен?


Нет, это как раз то, что они отрицали, а под «остальным» во фразе «остальное взлетит» как раз подразумевалась NDA-задача. Мне было важно понять, не противоречит ли её создание чему-то уже известному, и они сказали, что не видят сходу, чтобы это чему-то противоречило, ну т.е. «задача интересная, реализуемая, работайте». Вопросы про безусловно стойкое вычислительное крипто я тоже задал, но они были скептичными, указав на необходимость ввода дополнительных ограничений на ресурсы атакующего.


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

Про AONT и ERF мне трудно прокомментировать. Я ещё тогда не въехал в тему (как и в Вегмана-Картера). Надо читать и осмыслять работы. Мне это кажется интересным, но некоторые работы по этой теме, на которые вы указывали, не внушают доверия. То ли это просто работы такие, то ли всё направление мутное. Мне порой кажется, что AONT — это такой вечный двигатель, который не может существовать (ну, по крайней мере, идеальный AONT). По ERF, правда, вроде было много работ от серьёзных людей.
— unknown (30/03/2015 10:22, исправлен 30/03/2015 12:50)   

Всё возможное количество перестановок — m!. Задание одной перестановки — m2. Да, у меня калькулятор[link111] глючит, циферки плохо копируются, уже разбирали в /comment89669[link112]: m⋅2m. Можно чуть короче — через номер перестановки в факториальной системе счисления, но это незначительная оптимизация через усложнение. В общем, ракета упала на старте две гаммы, чтобы вторая с перестановками — ничего реалистичного не выйдет.



А может и банально. Может это тупик, который исследовали и от которого негласно отказались.



Нет. Здесь другое:


  1. По выводу японцев: если я правильно понял, то Unconditionaly Secure AONT увеличивает размер сообщения в 65535 раз.
  2. Из-за отсутствия реального non-malleability нет стойкости к подобранному/известному открытому тексту. Это можно решить наворачиванием аутентификации Картера-Вегмана или даже с помощью какой-то нелинейной перестановки поверх, но это надо разбирать.
  3. Полноценный блочный шифр не получится из-за п.-п. 1 — 2.
  4. Из-за п.-п. 2 — 3 можно разве что передавать одноразовую гамму, вычислительно безусловно стойко залоченную коротким ключом. Или сразу само сообщение? Может зависеть от свойств IT-канала, но гамму — точно.
  5. Нужна пара каналов: IT-стойкий (можно согласование 256-бит по QKD) и открытый.


Оно как бы слишком амбициозно и требует множества неочевидных доказательств мелких тонкостей (например, 256-битный ключ может обеспечивать не 256-бит безусловной вычислительной безопасности, а, скажем, на пару бит меньше из-за каких-то протечек и зазоров), но сходу не опровергается. Так что — в идеале да. Есть шанс именно раз и навсегда доказать, что протокол связи ломается только брутфорсом, если IT-канал действительно обеспечивает IT-стойкость.



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



Я тоже напутал: согласованную таким путём гамму нельзя называть OTP. Здесь ещё два варианта:


  1. Через эти два канала гонится само сообщение IT-secure AONT(M).
  2. Через эти два канала согласовывается безусловно вычислительно-стойкая гамма в виде IT-Secure AONT(R) для последующего R ⊕ M.

В обоих случаях — это не OTP. Здесь может даже нужно очень аккуратно вводить свою терминологию.



Там их больше и терминология плавает. Я даже зачем-то когда-то поместил это в FAQ[link113], но подозреваю, что зря — непроработано и слишком отвлечённо.



Это примитивщина, поэтому я и японцам доверяю не в плане результатов, а в плане того, что это простая вещь, которую легко проверить. Их IT-secure AONT — это вариант IT-стойкого разделения секрета по Шамиру, которое известно с 70-хх годов. Ну ещё теория кодов там на это завязана. Да и они не первые — они оптимизировали IT-secure AONT Стинсона и показали якобы, что их вариант оптимален и является близким приближением к теоретическому пределу. Но поскольку цель их работы — не IT-secure AONT, а вычислительный, то IT-secure вариант рассмотрен мало.


Я не могу это распарсить. Какой там реально рост размера в итоге?


Unfortunately, Theorem 1 means that an unconditionally secure AONT is not practical. Let us consider the following example. Suppose that the total size of message blocks is 1 MBytes (= 8388608 bits). When the size of mi is 128 bits, the number of blocks, s is 65536, and the total size of pseudo-message blocks is 65536 MBytes. When the size of mi, is 2048 bits, the total size of pseudo-message blocks is 4096 MBytes.

— SATtva (30/03/2015 11:22)   

К сожалению, из Теоремы 1 следует непрактичность безусловно стойкого AONT. Давайте рассмотрим такой пример. Предположим, что общий размер блоков сообщения составляет 1 МБ (т.е. 8388608 бит). Если размер mi — 128 бит, количество блоков s будет составлять 65536, а общий размер блоков псевдо-сообщения — 65536 МБ. Если же размер mi составляет 2048 бит, то размер блоков псевдо-сообщения будет 4096 МБ.

ЯННП, но, вероятно, потому, что саму работу не читал.
— unknown (30/03/2015 11:33, исправлен 30/03/2015 13:43)   

8388608 бит = 223, 65536 = 216. У них там нет общей формулы, может там с увеличением длины сообщения растёт всё сразу: и размер блоков, и их количество, и показатель степени. А алгоритм я не разобрал, чтобы вывести это самостоятельно. Смотрю только пример. Но если слать не сообщение, а одноразовую гамму блоками по 1MБ, то можно ориентироваться на этот пример. Тогда на каждые 1MБ гаммы надо новое пересогласование ключа в 256 бит. Может есть какой-то оптимум, но по этому примеру вот такой вот компромиссный размен IT-стойкости на безусловную одноразовую вычислительную. Т.е. 256 бит позволяют зашифровать стойко 1МБ, без учёта накладных расходов на аутентификацию и за счёт передачи 65535 МБ по классическому каналу.


Вся идея может не иметь никакой ценности, если существуют другие, более признанные, более правильные, возможно более оптимальные протоколы преобразования Unconditionaly IT-Secure → Unconditionaly Computational Secure. И даже все оптимумы чудес не творят и перекладывают слишком много нагрузки на классический канал.


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


Навскидку, m > n. Передаём по открытому каналу R размером m у которого заксорено общим секретом k 256 бит после согласования в IT-канале. Ещё 256 бит — на аутентификацию самого R. Затем некоей функцией (экстрактором?) преобразуем Rm → Rn и это используем как одноразовую гамму, размером n > 256 бит. В отличие от обычного симметричного крипто все зазоры можно информационно-стойко посчитать и исключить сокращённые варианты криптоанализа.


Вариант {IT-secure-AONT (R) ⊕ k ║ R ⊕ M} требует очевидно в два раза больше расхода на классический канал, чем сразу {IT-secure-AONT (M) ⊕ k}. Вариант с экстрактором m → n {Rm ⊕ k ║ Rn ⊕ M} — вообще неочевиден по оптимальности. Вот если собрать все варианты, посчитать оптимизации и убедиться, что это так и есть, то какая-то новизна работы может и будет. И то, не уверен.


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

— Гость (31/03/2015 03:35, исправлен 31/03/2015 03:39)   

Здесь можно писать, не одевая китель с погонами?



У меня с комбинаторикой всегда было туго; думал, что мне это никогда не понадобится. Ошибся. По-моему, перестановка m элементов множества имеет мощность m!, а из-за того, что речь идёт о битах, и часть элементов (а потому и их перестановок) совпадает, получается 2m. В общем случае (строки k всевозможных элементов длиной m) — это сочетания/размещения. Cnk туда же относятся.



Хотел сразу написать острее, но предупредительно решил, что сам могу ошибаться, мало ли что там, я те работы так и не осилил пока.



Э, это как? Вообще вся идея рушится? Но вы же ниже пишете о чём-то, продолжаете, или то немного о другом?



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



Хорошо. Меня больше интересуют как раз случайные гаммы.



Когда такая модель не опирается на решение проблем, неограниченная вычислительная стойкость которых считается недоказанно стойкой, то говорят о безусловной модели безопасности.

Выделенное «не» лишнее? Если нет, то я вообще это тройное «не» не могу распарсить.


Информационно-теоретические протоколы и алгоритмы являются стойкими к созданию квантовых или каких-либо иных гипотетических компьютеров с потенциально неограниченными вычислительными возможностями

I[link114]t is well known that classical computationally-secure cryptosystems may be susceptible to quantum attacks, i.e., attacks by adversaries able to process quantum information. ... we review an argument which shows that a similar problem can arise even if a cryptosystem provides information-theoretic security. As long as its security analysis is carried out within classical information theory, attacks by quantum adversaries cannot in general be excluded.

Unknown vs Renner. Кто кого?



Это радует.



Для mi=128 бит имеем 65536 MBytes ≈ 65 гигов. Для mi=2048 бит имеем 4096 MBytes ≈ 4 гига. Там действительно именно обратно пропорциональная, а не прямая линейная зависимость от mi?



Алиса и Боб предварительно расшаривают общий секретный ключ на 256 бит, перегоняют друг другу 65GB данных, и всё это только для того, чтобы потом доказуемо стойко передать 1MB сообщения? Да, печально.



Извиняюсь за банальный и глупый вопрос, но вроде как размер поXORиваемых элементов разный. Это нормально? Или k расширяется дублированием до размера IT-secure-AONT(R)?



   Новый эвфемизм: «NDA-задача». ☺ Там новизны и ярких концептов хоть отбавляй, попробуй вот докажи что это безопасно — в этом вся загвоздка. Идея примнения AONT'а вместо экстракторов — интересная идея. Может быть, она даже всё упростит. На это стоит посмотреть...
   Я только так и не понял, какими свойствами обладает AONT. Могли бы вы их кратко изложить? AONT сам по себе требует ключа или нет? Это просто бесключевое преобразование текста сообщения в «нековкий» формат? Если да, то достижима ли там идеальная нековкость/непластичность? Можно ли сообщение преобразовать AONT'ом в такой формат, что изменение одного бита в этом формате полностью убивает возможность восстановления «зашифрованного» сообщения? («Шифрование» взято в кавычки, т.к., скорей всего, оно тут бесключевое.) Мне кажется это нереальным... ведь легко проверить, что получим, попрядку флипнув каждый бит в тексте, который результат AONT-преобразования... Или именно оттуда и идёт экспоненциальный рост длины результата AONT-преобразования, что проверять по одному биту будет не проще, чем брутфорсить оригинальное сообщение? Тогда для шифрования текста длиной 128 бит надо переслать AONT-текст длиной 2128 бит? В общем, ЯННП.
   Может быть, мы всё это уже обсуждали ранее, но я этот тред сейчас повторно не перечитывал, так что сразу извиняюсь за повторное спрашивание одного и того же, будь такое случилось. Идея AONT'а тесно связана с ERF, насколько я помню, но по ERF (и вообще по seeded-экстракторам) было много работ, где люди бились за те или иные параметры производительности [хотя какие-то теоретические пределы, кажется, были озвучены (не помню, откуда у меня такая информация, но вроде с каких-то слайдов типа Vidick'овских)]. В общем, ERF (и, вообще, exposure-resilience) — это далеко не так просто, как мне показалось.

— SATtva (31/03/2015 08:26)   
[offtopic, grammarnazi grammarmilitant]
Вещь надевают, человека одевают (если вы не рептилоид[link115], надевающий человека). ☺
[/offtopic, grammarmilitant]
— unknown (31/03/2015 09:47, исправлен 31/03/2015 11:21)   

Не в кителе дело.



Я не помню, что держал в уме. Сокращённое множество перестановок: сгенерировать m случайных чисел в диапазоне 0 … m, затем последовательно сделать m циклических битовых сдвигов. Преобразования Swap or Not[link116] на одноразовом материале — тоже, если и не идеальный шифр, то там можно как-то точно посчитать все зазоры и доказать, что сокращённого метода анализа нет. Хорошо, что я ракеты не считаю.



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



У меня было придумано несколько вариантов, в т.ч. и такой, но если взять блоки R0 ⊕ k ║ R1 ⊕ k, то можно вычислить R0 ⊕ R1, что вообще-то — утечка и не годится, но я рабочие варианты «какой функций испортить гамму коротким ключом» даже не записывал.



Не требует. Его можно присобачить поверх, поксорив любой его кусочек с рэндомом.



Да.



Возможно, там даже какие-то более сильные термины вводятся для этого случая.



Именно ради этого AONT и был придуман. Кроме как перебором всех битов сообщение не восстановить.



Естественно.



Не оттуда, IT-AONT — это пороговая схема, разделение секретов, теория кодов.



Вы же не один бит будете портить? Для 128 бит придёться испортить все 128, так что да — смысла не имеет. А вот в 512-битном сообщении уже можно поксорить первые 128-бит с рэндомом или отрезать кусочек размером в 128 бит.

— Гость (01/04/2015 00:20)   
РЛ, а космонавтам китель полагается?
— unknown (01/04/2015 14:09)   

Для них главное — скафандр.
— unknown (03/04/2015 10:28, исправлен 03/04/2015 12:47)   

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


Оказывается, существует такая частная разновидность случайного оракула как LOR-оракул[link117]:


We say that SKE is Left-or-Right (LOR) secure [2] if

It is known that the counter mode is LOR secure if the underlying block cipher (say, AES) is a pseudorandom permutation [2].

Понятно, кто это придумал:
[2] M. Bellare, A. Desai, E. Jokipii, P. Rogaway: A Concrete Security Treatment of Symmetric Encryption[link118]. FOCS 1997: pp.394–403 (1997)


Они там вывели отношения эквивалентности между LOR-ATK, ROR-ATK, FTG-ATK, SEM-ATK. LOR — это Left or Right; ROR — Real or Random; FTG — find than guess; SEM — semantic. ATK — атаки подобранным открытым и закрытым текстом.


Атака ЛОР-ом и атака «найди и угадай» — это не только интересно звучит, но и вообще штуки полезные. Особенно против любителей перестраховок в криптографии.


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


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


Остальное там более сложно и специфично. Это к ответу на вопрос, сжимать ли текст перед шифрованием: в модели дискового шифрования у нас или ROR-security, или нестойкое шифрование. Всякая предварительная псевдорэндомизация (а сжатие не тянет даже на это) — это такие костыли-припарки против плохого ROR. Т.е., или у нас есть полная формализованная безопасность из коробки, или у нас только перестраховки.

— Гость (04/04/2015 21:33)   

Да, этот вариант не исключён. Вы уже проговорились, что чувствуете себя вторым слева, рядом с unknown'ом. ☺ Спасибо за замечание, подправлю потом.


Я тоже. Это был просто наглядный пример, который приводят публике не для того, чтобы они потом всё утрировали, но были более аккуратными в повседневных некритичных расчётах.

Есть, как мне кажется, две конкурирующие идеи: экстракторы и AONT. AONT привлекателен тем, что там якобы уже всё сделано: можно взять и более-менее в лоб применить. Экстракторы хороши тем, что ещё более просты: там всё от начала и до конца можно перепроверить самому, не полагаясь на безошибочность чужих работ и выводов. К тому же, экстракторы очень популярны, ими многие занимаются, а другие, как минимум, наслышаны. Про AONT не слышал, судя по моему опыту, почти никто. Вы говорите, что там всё просто, и это элементарная надстройка над уже известным и хорошо проверенным. В общем, все минусы завязок на маргинальщину мне понятны.

Всюду применяются почему-то именно экстракторы (начиная с биометрической идентификации и заканчивая QKD), а не AONT, хотя я вот сейчас не вижу сразу, почему AONT там неприменим. Мне пока непонятно, как вообще эти два концепта соотносятся между собой. Является ли один частным случаем другого? И т.д.


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


Вот тогда и не надо поганить конвенции, записали бы:

ƒ(IT-secure-AONT(R),k) | ƒ : {0,1}n×m → {0,1}n

или как-то так, а словами бы поясили, что это чем-то похоже по смыслу на те-то операции.


Тут, похоже, уже я запутался в терминологии. Если оно IT, а не просто безусловное вычислительное, то да, всё так, ибо даже подобрав правильный ответ мы не поймём, правильный ли он. Однако, у меня есть NDA-оракул, который всегда скажет, угадали мы результат или нет, из-за чего любая IT-безопасность сводится до уровня, как минимум, безусловной вычислительной.


А более точные оценки есть, сколько надо испортить? Ровно столько же, больше или меньше? Если больше/меньше, то какая там зависимость? Линейная? Полиномиальная? Логарифмическая?


Можно чуть поподробнее, о чём это? И дайте ссылку на страницу. PDF'ки какие-то нестандартные, не ищется в них этот текст у меня.


Тут наверно, скорее, «найди вместо того, чтобы угадывать» (если вы в цитате не ошиблись), а не «найди и угадай».
— unknown (04/04/2015 23:30)   

Я же упоминал, что это Secret sharing[link23], в частности японский IT-AONT — это Шамировская схема[link22] наизнанку, а Шамировская схема — это 1979 год и там всё вдоль и поперёк изучено. Из Secret Sharing можно сделать AONT, верно и обратное. Я подозреваю, почему AONT не в тренде, а остальное в тренде — потому что надо защищать всякие частичные утечки ключей. А разделение секретов, особенно IT-стойкое — не нашло особого практического применения. Хотя, дополнения подписи RSA-OAEP — это AONT, есть некоторые распределённые файловые системы и базы данных с шифрованием. Только это всё выч. стойкое.


Да мне плевать, что там у вас было.


Спасибо за откровение.


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


Она уже давно нарушена. Давайте не будем выяснять, кто в этом виноват в который раз уже?


Оговариваю возможность подставы лично вам во всех своих коментариях.


Не учите как мне жить, а?


Трёп в форуме не имеет никакого отношения по уровню ответственности к написанию научных статей. С некоего момента для некоторых участников это можно оговорить особо. В т.ч. для всех анонимов. К сожалению, из-за одного анонима-тролля разговаривать со всеми анонимами серьёзно теперь невозможно. Use at your own risk. Более того, в отличие от готовой статьи, программного продукта или патча, на мои коменты в форуме не распространяется репутационной или какой-либо иной ответственности. Особенно перед (псевдо)анонимами с форума.

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

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


Вообще не знаю ответа на вопрос: если скажем первые 128-бит R заксорить с k, то извлечение экстрактором меньшей гаммы насколько будет стойко против противника, не знающего k, но знающего «испорченную» R. Как это зависит от размера R? Должен ли экстрактор эмулировать нечто вроде неизвестного противнику внутреннего состояния размером с k и зависящего от этого k? Должен ли быть эктрактор какого-то особого вида? Вы понимаете, умалчивание об этом, это даже не подстава, это вылезает большой кусок теории, которую надо разбирать и простым обозначением здесь не отделаться. Вкуривайте всякие resilient exposure, leakage security и вот это всё.

В AONT так должно быть по определению. Может я изначально правильно вам написал? Понимаете? Может нормально взять малый k и поксорить с большим R. Это мысли вслух, идеи по весьма специфической области. Я не знаю и не собираюсь точно выводить ответ и докапываться как там и что. У меня полно своих задач, возможно и более интересных лично для меня, чем ваша.

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


Идеальный побитовый AONT должен обеспечивать равномерную стойкость в каждом бите. Хотите меня ловить на словах — сами ищите пруфы или антипруфы, за точность определений, оценок и пр. отвечать не собираюсь.
— Гость (05/04/2015 01:34)   

Это я понял и не опровергаю.


Казалось бы, и AONT и экстракторы решают вопросы с частичными утечками ключей, чем одна защита рыжее другой? В этом и был вопрос.


Я предполагал (и сейчас считаю так; может, зря), что раз AONT (квази)идеальный, то нам всё равно, какие именно биты в нём будут испорчены: первые 128, последние или выбранные случайно — стойкость будет одинаковой (ну, или не ниже той, которая даётся оценками стойкости AONT для заданного числа испорченных бит). Соответственно, мой вопрос был лишь о количестве бит, которые портим.


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


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


Я выше ответил, что имелось в виду. Если что, такие претензии я высказывал всем. И если б Шамир начал нести такую пургу в своих работах, я б и ему сделал аналогичное замечание (более того, подобные инциденты были).


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


Конечно, но незачем сознательной безолаберностью усложнять ему эту работу раскидыванием подводных камней во всех местах.


Ага, но почему-то вы очень горазды требовать этой самой ответственности от других — например, от меня.


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

if (не нашлось, что ответить & всё верно); then
объявить_тонким_манипулятором;
while (подставы_нет); do
искать_подставу;
done
fi


Ещё раз вам говорю: поксорить можно битовые строки одинаковой длины. Всех, кто складывает пироги с сапогами называет XOR'ом другую операцию, не оговаривая это явно, надо нещадно бить. Вам это скажет любой математик, и большинство прикладников (даже тех, кто зарамарался в подобном сленге по уши) всё равно с этим согласятся. Каждый вводит сленг, удобный для себя, но при этом проигрывает, разбирая сленг других. В итоге теряют все, всё общество в целом. Я бы коротко сказал, что надо ксорить не k, а расширение (от) k: всего одно лишнее слово, и сразу проблему как рукой сняло. Если вы аккуратен в мелочах, вы постараетесь и в форумных комментариях не допусать по возможности двусмысленностей и некорректностей, а если неаккуратен, то это везде так будет: и в коде и в статьях (в том, что вы делаете официально под своим именем).


Я не выискиваю специально чего-то в ваших словах. Обычное вдумчивое чтение ваших комментариев, экзаменуемое холодным разумом, сразу порождает вопросы. Я эти вопросы и задаю.
— Гость (08/04/2015 07:41)   
Про AONT vs экстракторы:

Возьмём простейший пример: нужно скрыть один бит y. Расширяем его до двух бит: {y⊕z,z}. Если один из них неизвестен, найти y нельзя. По сути это одноразовый блокнот. Получается идеальная пороговая AONT-схема, но в случае, когда атакующий может с какой-то вероятностью угадать как y, так и y⊕z, она не будет самой эффективной.

P.S. В сети появилась новая порция[link119] квантовых слайдов по темам, обсуждавшимся в этом и других топиках.
— unknown (08/04/2015 10:06, исправлен 08/04/2015 10:47)   

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


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



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

— Гость (08/04/2015 10:39)   
Пока не читал статьи, трудно говорить на тему. Заставлять вас пересказывать статьи — тоже нехорошо. То, что одноразовый блокнот — простейшая схема разделения секрета, я знаю.

Как определяется безопасность AONT? По количеству битов сообщения, которое может быть известно атакующему? Или по другой, более произвольной информации о битах?


Рандомизация, как и seeded-экстракторы, думаю, не годятся. Это всё сильно переусложнит, но вряд ли даст профит (строго говоря, всё это очень неочевидно). Если мы шифруем рандомную гамму, а потом придерживаемся принципа full exposure, чем дополнительная рандомность тут поможет? Её секретность гарантировать не получится.


Спасибо. Смысл примерно понятен.


Тут[link120] немножко упоминалось, кстати.
— unknown (08/04/2015 11:02)   
Мне это ничего не говорит:
Однако, у меня есть NDA-оракул, который всегда скажет, угадали мы результат или нет, из-за чего любая IT-безопасность сводится до уровня, как минимум, безусловной вычислительной.

Откуда эта цитата? Из какого-то NDA-документа? Реннер в кулуарах нашептал? Нечто IT-стойкое (кроме OTP) можно на квантовом компьютере перевести в выч.-стойкое?
— Гость (08/04/2015 12:04)   

   Наверно, по смыслу было так?


   Можно и так сказать. Раз вы все NDA-документы читали, я считаю (возможно, ошибочно), что намёков на то, что мне нужно, вам достаточно.
   Как вы помните, у нас есть оракул, который возвращает ответы вида «угадали / не угдали», а также зашифрованный AONT'ом или ещё чем-нибудь ключ. Противник лишь с очень малой вероятностью может получить все биты AONT-текста с нулевой ошибкой; т.е. более вероятно то, что он в большинстве бит ошибётся (а в каких-то нет). Однако, никакого строго порога на число ошибок здесь нет.
   Мы можем не разгадывать AONT, а напрямую брутфорсить самого оракула. Если ключ, к примеру, 256 бит, за ≈ 2255 запросов к оракулу мы его узнаем. AONT и прочие извраты нужны лишь для того, чтобы мы не узнали его существенно быстрее. Отсюда и следует, что безопасность в этой задаче вычислительная по самой сути её постановки.
   Если вы с помощью OTP зашифруете 256 бит, это шифрование будет информационно-теоретически стойким, а в случае с оракулом — нет, поскольку для любой 256-битной строки у вас есть возможность узнать, такая она или нет. Грубо говоря, имеется внешняя функция, которая на расшифрованную гамму/ключ/пароль возрвщает ответ 1, если она верная, и 0, если неверная. При такой постановке ничего информационно-теоретически стойкого существовать не может в принципе, а противник с неограниченными вычислительными возможностями всегда узнает секрет.
   Если что, во всех последних постах я ни о чём, кроме NDA-задачи, вроде речь не вёл. Т.е. квантовое симметричное крипто и т.п. вопросы (на которые, да, Реннер тоже отвечал) я пока не обсуждаю, и мне пока нечего по ним сказать.


   Нет.
— unknown (08/04/2015 13:36, исправлен 08/04/2015 13:36)   

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



Тогда для NDA-задачи достаточно OTP. С одной стороны, извраты с гипотетическим AONT-локингом классической информации не нужны. Но это так, только если у вас гамма 256 бит и секрет 256 бит. Тогда я ввёл аналогию с комбинацией каналов, чтобы не раскрывать суть NDA-задачи (по крайней мере, здесь я стараюсь формулировать и утверждения и вопросы так, чтобы не раскрыть задачу, пока она всё ещё NDA). Если нам доступна гамма только 256 бит, а нужно защитить секрет (причём заранее заданный, не рэндомный, а произвольный) хотя бы чуть больше 256-ти бит, тогда можно раздуть секрет в виде IT-AONT и заксорить уже в таком виде в нём 256-бит с гаммой (дополнив нулями и всё такое). Можно ли вместо AONT использовать экстракторы для сохранения в открытом виде гаммы большего размера и отжатия из неё меньшего и что там с чем ксорить — другой вопрос, более сложный. Я только упомянул идею, но даже сейчас не решаюсь её разобрать.


Кстати, ещё вот это[link121] меня тоже наводило на какие-то идеи применительно к вашей задаче, но никак не могу вспомнить, на какие.

— Гость (09/04/2015 06:01)   

Да, есть некоторая мысль в том, что информационно-теоретическая стойкость — это overkill, если уже есть безусловная вычислительная.


Спасибо.


Он заранее заданный, но полученный рандомно. Обобщить на произвольный секрет мне предложили почти сразу, но это было бы слишком сложным на данном этапе. Для начала надо хотя бы с рандомным разобраться.


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


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

На второй странице драфта есть 4 требования, которым должен удовлетворять «примитив». Обратите внимание на третье требование — устойчивость к апостериорному раскрытию. Оно ключевое. Именно из-за него, как я понимаю, идеальные схемы невозможны[link122], а замена экстрактора на AONT ничего концептуально не меняет. Никаких естественных «порогов» на число раскрываемых бит в задаче тоже нет, поэтому ожидать чего-то слишком эффективного именно от пороговых схем я бы тоже не стал. Они — просто как один из возможных вариантов.


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

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

В драфте в параграфе IV есть попытка формально описать протокол, там как раз что-то типа оракула и вводится. Над этим можно долго смеяться, не спорю, но даже такое примитивное описание — прогресс по сравнению с тем, что было раньше, и даже оно заняло не один день размышлений и обсуждений с коллегами. То, что результат обсуждений оформлен хотя бы в виде такого пошагового описания в pdf'ке, а не где-то зарыт на обрывках салфеток среди тонн черновиков — уже что-то, от чего можно идти дальше.

Там же:

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

Одноразово выполняемые программы как раз здесь выше по треду обсуждались.
— Гость (09/04/2015 06:03)   
P.S. Параллелизм с хардкором[link123] тоже напрашивается, но я его, хардкор, не понял.
— unknown (09/04/2015 10:10)   
Про хардкор[link124] я вам там ответил, это само по себе простое понятие.

Ссылки
[link1] https://en.wikipedia.org/wiki/Btrfs

[link2] https://www.pgpru.com/faq/kriptografijaobschievoprosy#h37247-9

[link3] http://arxiv.org/abs/1305.4229

[link4] https://www.pgpru.com/comment63437

[link5] https://www.pgpru.com/forum/prakticheskajabezopasnostj/apparatnyegschvcpuotintel

[link6] https://www.pgpru.com/novosti/2006/0325konceptualjnajanestojjkostjgpschvlinux

[link7] https://www.pgpru.com/novosti/2012/prakticheskieujazvimostiotkrytyhkljuchejjilipochemuronproigryvaetvitu

[link8] https://www.pgpru.com/novosti/2007/backdoorvellipticheskihkrivyh

[link9] https://www.pgpru.com/novosti/2013/havegealjternativnyjjsposobpoluchenijakriptostojjkojjentropiiizprocessorov

[link10] https://www.pgpru.com/novosti/2012/pervajaocenkavozmozhnostiprakticheskogovzlomaaes15trillionausimeneegodavychislenijj

[link11] https://www.pgpru.com/faq/kriptografijaobschievoprosy#h37247-13

[link12] https://ru.wikipedia.org/wiki/Национальный_институт_стандартов_и_технологий

[link13] https://www.pgpru.com/biblioteka/osnovy/fondpoleznyhpostov/kriptografija#fppA10I

[link14] https://www.pgpru.com/comment63135

[link15] https://en.wikipedia.org/wiki/Typical_set

[link16] https://www.pgpru.com/comment32952

[link17] https://www.pgpru.com/comment33208

[link18] https://en.wikipedia.org/wiki/RC5

[link19] https://en.wikipedia.org/wiki/International_Data_Encryption_Algorithm

[link20] https://en.wikipedia.org/wiki/All-or-nothing_transform

[link21] https://www.pgpru.com/comment65039

[link22] https://en.wikipedia.org/wiki/Shamir's_Secret_Sharing

[link23] https://en.wikipedia.org/wiki/Secret_sharing

[link24] https://en.wikipedia.org/wiki/Randomness_extractor

[link25] http://www.softcomputing.net/isda03/sugaabstract.html

[link26] http://www.tifr.res.in/~sanyal/papers/Ranga_SecuredDataTransfer.pdf

[link27] http://www.lib.kobe-u.ac.jp/repository/90001320.pdf

[link28] https://cs.nyu.edu/web/Calendar/colloquium/sp00/may09.html

[link29] http://www.iacr.org/archive/eurocrypt2000/1807/18070459-new.pdf

[link30] https://www.pgpru.com/comment42640

[link31] https://www.pgpru.com/comment49068

[link32] http://arxiv.org/abs/quant-ph/0612012

[link33] http://arxiv.org/find/quant-ph/1/au:+Vidick_T/0/1/0/all/0/1

[link34] https://www.pgpru.com/comment19007

[link35] https://www.pgpru.com/comment63447

[link36] http://imi.kyushu-u.ac.jp/~morozov/

[link37] http://iopscience.iop.org/1367-2630/8/10/249

[link38] http://www.hpl.hp.com/research/qip

[link39] http://www.secoqc.net/html/technology/quantum.html

[link40] https://en.wikipedia.org/wiki/Aaron_D._Wyner

[link41] http://www1.spms.ntu.edu.sg/~frederique/NRF-RF/

[link42] http://jurg.wulli.com/crypto/

[link43] http://www.ese.wustl.edu/~jao/Papers/JournalPublications/01184136.pdf

[link44] http://cacr.uwaterloo.ca/~dstinson/CS_858/Dzimbowski.pdf

[link45] http://www.osti.gov/bridge/purl.cover.jsp?purl=/877141-FM3vVM/

[link46] http://www.is.titech.ac.jp/~christo5/fulltext/Por_Phd-thesis.pdf

[link47] https://www.pgpru.com/comment64910

[link48] https://www.pgpru.com/comment36742

[link49] http://arxiv.org/abs/quant-ph/0306078v1

[link50] http://arxiv.org/abs/quant-ph/0502064v1

[link51] http://arxiv.org/abs/0708.0709

[link52] http://arxiv.org/abs/quant-ph/0512021

[link53] https://www.pgpru.com/comment32246

[link54] https://www.pgpru.com/comment51216

[link55] https://www.pgpru.com/biblioteka/statji/dovodyvpoljzuqkd

[link56] http://www.lysator.liu.se/~jc/mthesis/5_Unconditionally_secure_au.html

[link57] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.96.7529

[link58] https://www.pgpru.com/comment65238

[link59] https://www.pgpru.com/forum/kriptografija/voprosypokvantovymkanalamihmodelirovanieiprimenenie

[link60] https://www.pgpru.com/comment16410

[link61] https://www.pgpru.com/proekt/poljzovateli?profile=unknown

[link62] https://www.pgpru.com/comment18827

[link63] http://www.is.titech.ac.jp/~christo5

[link64] http://www.is.titech.ac.jp/~christo5/papers.html

[link65] http://eprint.iacr.org/2012/015

[link66] https://www.linux.org.ru/news/opensource/8330828/page1#comment-8347665

[link67] https://cseweb.ucsd.edu/users/mihir/short-cv.html

[link68] https://www.pgpru.com/comment65411

[link69] https://www.pgpru.com/comment73349

[link70] https://www.pgpru.com/biblioteka/rukovodstva/samodelkiipodruchnyesredstva/kakustroentradicionnyjjodnorazovyjjbloknot

[link71] http://arxiv.org/abs/0808.0353

[link72] https://www.pgpru.com/comment58997

[link73] https://www.pgpru.com/comment65550

[link74] https://www.pgpru.com/comment71179

[link75] https://www.pgpru.com/comment71190

[link76] http://pdf.aminer.org/000/120497universal_hashing_and_authentication_codes.pdf

[link77] http://www.diva-portal.org/smashget/diva2:324702/FULLTEXT01.pdf

[link78] http://eprint.iacr.org/2013/126

[link79] http://arxiv.org/abs/1402.0049

[link80] https://www.pgpru.com/comment65270

[link81] http://benasque.org/2014QIP/talks_contr/074_singleshot1public.pdf

[link82] https://www.pgpru.com/comment63998

[link83] https://www.pgpru.com/comment71197

[link84] http://benasque.org/2014QIP/cgi-bin/talks/allprint.pl

[link85] https://www.pgpru.com/comment57377

[link86] https://en.wikipedia.org/wiki/Ivan_Damgard

[link87] http://www.informatik.uni-trier.de/~ley/pers/hd/d/Damg=aring=rd:Ivan.html

[link88] http://arxiv.org/abs/quant-ph/0612014

[link89] http://arxiv.org/abs/quant-ph/0407066

[link90] http://www.isiweb.ee.ethz.ch/archive/massey_pub/pdf/BI633.pdf

[link91] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.151.5121&rep=rep1&type=pdf

[link92] http://users.cis.fiu.edu/~smithg/papers/

[link93] http://www.lix.polytechnique.fr/comete/Projects/Princess/events.html

[link94] http://pagesperso-systeme.lip6.fr/Beatrice.Berard/131203.html

[link95] http://www.genealogy.ams.org/id.php?id=54328

[link96] https://en.wikipedia.org/wiki/James_Massey

[link97] https://en.wikipedia.org/wiki/Erdos_number

[link98] https://ru.wikipedia.org/wiki/Число_Эрдёша

[link99] https://en.wikipedia.org/wiki/Lai-Massey_scheme

[link100] https://en.wikipedia.org/wiki/Merkle–Damgard_construction

[link101] https://en.wikipedia.org/wiki/Merkle_puzzle

[link102] http://link.springer.com/chapter/10.1007/978-3-540-85174-5_3

[link103] https://eprint.iacr.org/2010/153

[link104] https://eprint.iacr.org/2012/564

[link105] http://arxiv.org/abs/1211.1080

[link106] https://www.pgpru.com/comment76676

[link107] http://www.nature.com/nature/journal/v517/n7533/full/nature14025.html?WT.ec_id=NATURE-20150108

[link108] http://rghost.net/download/private/60296032/8a2b12247ed6239ed6b75f17516b02a8/b710ae9655151fd258791cf0f98f141c5dd82591/file.pdf.gpg

[link109] https://www.pgpru.com/comment74121

[link110] https://www.pgpru.com/comment74125

[link111] https://ru.wikipedia.org/wiki/Феликс_(арифмометр)

[link112] https://www.pgpru.com/comment89669

[link113] https://www.pgpru.com/faq/kriptografijaobschievoprosy#h37247-6

[link114] https://www.pgpru.com/comment66831

[link115] http://ic.pics.livejournal.com/merleblanc2014/73593204/685155/685155_original.jpg

[link116] https://www.pgpru.com/novosti/2012/swapornotprostejjshieblochnyeshifrypretendujutnastojjkostj

[link117] http://eprint.iacr.org/2015/251

[link118] http://www.cs.ucdavis.edu/~rogaway/papers/sym-enc.pdf

[link119] http://www.pcqc.fr/advances-in-quantum-cryptography.html

[link120] https://www.pgpru.com/comment82879

[link121] https://www.pgpru.com/novosti/2013/universaljnyjjvychisliteljnyjjekstraktorkakkonkretizacijasluchajjnogoorakula

[link122] https://www.pgpru.com/comment85450

[link123] https://www.pgpru.com/comment91569

[link124] https://www.pgpru.com/comment91583