— Гость (01/03/2010 17:22)   

а также критерии, по которым принимать решение "открыто/зашифровано"

Вот библиотека распознающая кодировку, с помощью вероятностного метода
http://popoff.donetsk.ua/text/work/libs/a/charset/

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

— Гость (01/03/2010 18:55)   
Мне этот вопрос тоже интересен. Если такой софт существует, может ли он чисто по вероятностным характеристикам (т.е. считаем что заголовки файла вырезаны) различить кусок архива или хорошо сжатого видео (типа mp4) от куска криптоконтейнера.

— SATtva (01/03/2010 19:00)   

Существует, называется видеоплеером.

— Гость (01/03/2010 19:23)   

Существует, называется видеоплеером.

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

— SATtva (01/03/2010 19:40)   

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

Тогда Вам стоит освежить в памяти различия между кодированием и шифрованием.

— Гость (01/03/2010 19:56)   
SATtva, оба ваши ответа совсем не в тему. Я в курсе об отличии кодирования от шифрования. Речь идёт о том, что энтропия хорошего кодека может приблизиться и достичь той, которую дают криптоалгоритмы. Как в таком случае различать одно от другого по единичным образцам доступным для исследования, мне не ясно. В этом и состоял вопрос.

— Гость (01/03/2010 20:03)   

Тогда Вам стоит освежить в памяти различия между кодированием и шифрованием.

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

— SATtva (01/03/2010 20:04)   
КО спешит напомнить, что, независимо от энтропии образца, пространство и потенциальная энтропия ключа шифра несколько выше пространства и энтропии всех параметров кодека, что позволяет перебрать последние с куда меньшими затратами, нежели брутфорсить ключ.

— Гость (01/03/2010 20:09)   

Задача – определить с высокой вероятностью, является ли данный блок шифртекстом.

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

— Гость (01/03/2010 20:19)   

пространство и потенциальная энтропия ключа шифра несколько выше пространства и энтропии всех параметров кодека

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

алгоритм должен работать и против тех форматов, что будут созданы в будущем

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

— Гость (01/03/2010 20:22)   

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

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

— Гость (01/03/2010 20:27)   

если нужно определить, является массив сл. данных шифртекстом – для хороших алгоритмов [генерации случайных данных], это невозможно.

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

— Гость (01/03/2010 21:15)   

хороший архиватор может хорошо приблизиться к максимальной энтропии

И? Такой алгоритм будет криптостойким?
Как только он станет известен, то даже поврежденный архив можно будет отличить от случайных данных. Но поврежденный архив (если нет данных для востановления) будет просто ненужным мусором.
Если он будет не поврежден, тогда зная алгоритм – проблем с индентификацией не составит проблем.

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

— Гость (01/03/2010 22:18)   

Тогда Вам стоит освежить в памяти различия между кодированием и шифрованием.

А всегда ли грань между ними толста? Как пример:

1. Кодирование (архиватор) как функция, которая сопоставляет известному заданному паролю (он рассматривается как параметр) и зазипованному тексту в соответствие AES-шифротекст (шифруем зипованный текст с этим паролем). В такой модели перебрать все архиваторы = брутфорсить AES, т.е. имеем семейство архиваторов зависящих от ключа как от параметра. Такая штука формально архивтор, но по сути тут крипто. Если же ключ не известен, то "архив" сразу же превращается в "криптотом".
2. Есть сайт, на котором выложено n ключей шифрования, где n очень велико. Текст шифруется каким-то паролем с сайта, но номер пароля не известен. Является ли это шифрованием согласно определению? Это ведь можно интерпретировать и как кодирование для сверхбольших n.
3. Пусть (по определению) интерпретатор языка программирования есть криптоалгоритм, а ключ – программа. Текстовую выдачу такого интерпретатора для данной программы (применённой к некоторому открытому тексту) можно объявить шифротекстом. Как частный случай ключей-программ можно взять всевозможные алгоритмы, порождаемые AES'ом с заданным ключом. Мощность таких алгоритмов не меньше мощности самого симметричного шифра. Как бы при заданном ключе это кодирование, хотя по всем формам – шифрование :)

Если сравнивать часть файла в формате, скажем, jpg – то написать такую программу не составит труда

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

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

— Гость (02/03/2010 01:01)   

отличить куски файлов, сгенерированных уже известными программами (архивы, видео, музыка, картинки и прочие высокоэнтропийные данные) от кусков криптотомов можно

Вот насчёт именно кусков не уверен. Что там в середине 7zip, когда включено штатное AES-шифрование? И что там в середине зашифрованного современным стандартным копирайтным алгоритмом фильма?

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

— Гость (02/03/2010 02:34)   

Что там в середине 7zip, когда включено штатное AES-шифрование? И что там в середине зашифрованного современным стандартным копирайтным алгоритмом фильма?

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

— unknown (02/03/2010 09:21, исправлен 02/03/2010 09:36)   

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

Рассмотрим просто архиватор. На вход подаётся открытый текст, на выходе — сжатый текст. Это как-бы подстановка (замена) со сжатием, но мы договорились, что ключ не используется, ключ — это сам алгоритм, который неизвестен (кстати это нарушение принципа Керхгофа, перебрать миллионы возможных алгоритмов сжатия всяко реальнее, чем 2¹²⁸ ключей). С другой стороны — эта подстановка обратима (т.е. это не хэш), если речь об архивировании. Если речь о сжатии с потерями, то частично обратима — можно восстановить исходные данные, похожие на те, что были раньше.

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

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

Да, разработчики архиваторов и кодеков стремятся достичь предела энтропии по Шеннону. Да, между кодированием и шифрованием есть кое-что общее — некоторые элементы шифров (MDS-матрицы AES, Twofish построены на основе теории кодирования).

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

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

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

Diehard

— Гость (02/03/2010 10:18)   

перебрать миллионы возможных алгоритмов сжатия всяко реальнее, чем 2¹²⁸ ключей

Алгоритмов сжатия всяко больше, чем 2¹²⁸, хотя-бы потому, что некоторые из них имеют больше, чем на 128 бит параметров. ;)

— astramax (02/03/2010 10:59)   
Позволю себе немного приземлить сию дискуссию. Вот здесь^[link1] обсуждение моего эксперимента

— Гость (02/03/2010 16:45)   

Вот здесь обсуждение моего эксперимента

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

Третья группа файлов – шифрованные, сжатые (zip, 7z, rar, pgd без заголовка)

Лучше не жать шифрованные, а просто смотреть на шифрованный текст без сжатия, т.к. стандартные шифроалгоритмы типа gpg уже сжимают открытый текст перед сжатием. А двойное сжатие иногда приводит к увеличению объёма файла – т.е. к сторонним эффектам. Я бы рассматривал какие-то конвенциональные программы (gpg, mcrypt, pgp, openssl), а не архиваторы+шифрование для тестирования шифрования, т.к. фиг знает как там оно точно устроено.

— astramax (02/03/2010 17:30)   
В общем, эксперимент не совсем чистый, делался на скорую руку.

Да, заголовки оказывают влияние. В частности криптоконтейнер pgd выбивался из общей картины, пока я ему заголовок не отрезал.
Жать шифртекст – себе дороже, там избыточность ->0. Кстати, по-моему статистические свойства шифртекста не зависят от того, был открытый текст до шифрования сжат, или нет. Ведь хороший алгоритм+сильный ключ (а мы говорим здесь именно о таких) просто обязан убирать взаимное влияние битов друг на друга и выравнивать вероятность их появления. В противном случае криптостойкость напрямую зависит от свойств открытого текста

— Гость (02/03/2010 18:00)   

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

Для блочных шифров – видимо, да, а вот для асимметричных – нет:

Потому что сначала генерируется сеансовый случайный симметричный ключ (по умолчанию AES), им шифруется всё сообщение, а уже этот ключ (а не само сообщение) шифруется асимметрикой. Расшифровывается естественно в обратном порядке. Иначе шифрование происходило бы очень медленно (до 10000 раз), а алгоритмы типа RSA неустойчивы к атакам с подобранным открытым текстом – кто-нибудь попросил бы вас перешифровать текст вашим ключом и переслать ему шифртекст, а из результата смог бы вычислить закрытый ключ.

/comment25910^[link2] Насколько я помню, gpg ещё zip'ует открытый текст перед шифрованием... не знаю, связано ли это только с целью уменьшения размера, или же и для криптостойкости.

— astramax (03/03/2010 08:07)   
Мое упущение, я не указал что речь идет только о симметричных шифрах

— unknown (03/03/2010 09:08)   
[off]
Ну не работают ассиметричные алгоритмы в чистом виде вообще:
http://en.wikipedia.org/wiki/RSA#Padding_schemes
А дополнения типа OAEP^[link3] требуют и хэшей ещё.
Или требуют инкапсуляции ключей^[link4], завязанной также на хэши.

Кстати, раз уж привели комментарий, то интресно было бы вернуться к теме отрицаемости шифрования в переписке^[link5].
[/off]

— Гость (07/12/2012 05:49)   

Тут^[link6] пишут, что

Vulnerability to chi-squared randomness test has also been suggested: encrypted data, after each write operation, should be adjusted to fit a plausible randomness property.

где отсылка идёт к английскому хелпу^[link7] по вот этой^[link8] программе. Что они хотели этим сказать? В частности, вызывает вопрос «обеление» шифротекста:

Data is encrypted (1), scrambled (2) and whitened (3).

Layer 3 – CSPRNG based whitening: Scrambled data is always mixed with a high amount of noise. A new CSPRNG is seeded with a forth password (256bit) and data is bit-by-bit split according to a random permutation.

Если шифрованные данные не имеют сигнатур, а криптотом размещается на дисковом пространстве, предварительно заполненном случайными данными, как отличить, где шифрованные данные, а где случайные? Разве есть какой-то способ?

По той же ссылке^[link6] ещё про пластичное (malleable) шифрование пишут. Оно чем-то отличается от гомоморфного? Кажется, там заявляется постфактумная фальсифицируемость шифротекстов,^* что может быть полезным для отрицаемости шифрования типа jabber+OTR, но не понятно, применимо ли это для отрицаемости шифрования дискового.

^*Наверное, подобно тому, как это происходит с подписями Лампорта^[link9].

— unknown (07/12/2012 15:39, исправлен 11/12/2012 12:26)   

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

— Гость (08/12/2012 21:29)   

«Преобразовать» в каком смысле? Расшифровать? Что подразумевалось под «обладающий предопределёнными свойствами» мне тоже непонятно. Не могли бы вы поподробнее объяснить всю фразу?

— unknown (09/12/2012 19:59, исправлен 11/12/2012 12:25)   

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

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

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

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

«Преобразовать» в каком смысле? Расшифровать? Что подразумевалось под «обладающий предопределёнными свойствами» мне тоже непонятно.

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

— Гость (09/12/2012 21:41)   

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


Атаки с подобранными шифртекстами — тоже уязвимость режима использования, а не алгоритма шифрования? Разве так нельзя «далеко зайти»? Возьмём любой нестойкий (в современном понимании) любительский шифр, который нельзя взломать, если неизвестна ни одна пара {открытый текст, шифртекст}. И на все претензии к такому шифру (по паре {открытый текст, шифртекст} восстанавливается пароль) будем говорить, что открытый текст должен предварительно быть случайным набором данных (заархивированных, например), неизвестных противнику. С другой стороны, есть известный факт, что асимметричное шифрование стойкое, только если им шифруют случайный пароль для блочного шифра.


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

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

— unknown (09/12/2012 23:43, исправлен 11/12/2012 12:27)   

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

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

Если бы это было уязвимостью самого алгоритма, то его бы отбраковали и речь бы шла совсем о другом, а в режиме шифрования такое м.б. допустимо. Например AES-CTR — стойкий режим шифрования. Это просто XOR гаммы с открытым текстом, полученной шифрованием счётчика. Инвертируем бит в шифртексте — инвертируется бит в открытом тексте. В этом же месте. Предсказуемо, тривиально, не требует никаких вычислительных ресурсов и считается не атакой, а естественным ограничением. А это самый удобный во многих случаях режим использования из-за неограниченного распараллеливания и произвольного доступа к блокам. Например, используется в Tor. Подробности не помню, но в рассылке были примерно нижеследующие обсуждения в вольном пересказе.

Открытый текст разбивается на ячейки 512 бит, шифруется AES-CTR, а аутентификация всей группы ячеек происходит где-то в конце передачи. Поскольку промежуточные узлы не проверяют аутентификацию каждой ячейки (это было бы слишком накладно), они делают проверку или в конце передачи, или в конце большого блока из группы ячеек. Злоумышленник инвертирует определённый бит в ячейке и смотрит, как рвутся цепочки из-за переотправленных битых ячеек. Если бы на промежуточном узле сразу проверялась каждая ячейка и промежуточные узлы не отправляли бракованные ячейки дальше, то это избавило бы от некой уязвимости. Поэтому сейчас вяло обсуждается переход на более строгую аутентификацию и non-malleable encryption. Похожая проблема была и у ремейлеров.

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

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

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

Ряд заморочек решён в алгоритме SHA3/Keccak, где универсальный RO-симулирующий алгоритм, режим использования и протокол часто являются нераздельным целым, для которого всё уже доказано и напортачить что-либо сложно. Возможно грядущее упрощение всевозможных SSL, PGP и пр. на его основе.

— Гость (10/12/2012 00:16)   
unknown, спасибо! Очень хороший и доходчивый пост. Судя по тому, как вы описываете, оно звучит так: есть нормальные режимы шифрования (ну хотя бы тот же PGP с AES'ом и проверкой целостности), которые достаточно безопасны, и таких тривиальных сюрпризов, как

инвертируем бит в шифртексте — инвертируется бит в открытом тексте

там нет(?). И даже, наверное, вообще нет ничего и близко подобного по силе таким атакам. Когда же начинают биться за производительность протокола, режимы использования ослабляют, и ослабляют очень сильно. И вот тут как раз вылазит такая тонкость, что несмотря на некоторые существенные ослабления, весь протокол в целом иногда можно оставить достаточно безопасным, но не всегда. Часто это приводит к уязвимостям. — Это если я правильно мораль понял :)

— unknown (10/12/2012 00:38)   
Правильно :) И надеюсь, правильно дошло, почему такая казалась бы простая вещь, как SSH — это на самом деле гигантский навороченный протокол. На котором было набито немало шишек из-за ошибок, как и на PGP, и на випиэнах, про торы вообще можно не говорить.

И почему для того, чтобы сделать такую вроде простую вещь, как вменяемое дополнение для RSA-подписи, нужно нагородить дикую конструкцию в виде сети Файстеля из хэшей (сейчас это RSA-OAEP), потому что SHA-2 не проектировался как RO. А SHA3/Keccak решает многие из этих задач сам по себе, потому как максимально близок к RO.

— Гость (10/12/2012 06:10)   

[оффтопик]
[сопли]
[«помогите решить задачу»]

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

Например, реально ли без криптографического или CS образования разобраться с жизнерадостной^[link10] криптографией^[link11]? Пытался смотреть диссер^[link12] Евгения Додиса^[link13], которого вы упоминали здесь^[link14]. С первого нахрапа мало что ничего не получилось. Пока гуглил, заметил, что автор, в отличие от своего коллеги^[link15], старается не афишировать знание русского, но домашняя страница всё же содержит некоторые утечки, да и профиль на линкедине говорит о молдавском происхождении, хотя есть и иные мнения^[link16]. Метод огораживания от входящих писем заслуживает отдельной ссылки^[link17] — unknown, это у всех криптографов так, или просто сказывается студенческая специфика в штатах? Боязно писать таким людям, вдруг ещё неправильно поймут.

Лефтовер-хэш-лемма^[link18]1 гарантирует нам:

Imagine that you have a secret key X that has n uniform random bits, and you would like to use this secret key to encrypt a message. Unfortunately, you were a bit careless with the key, and know that an adversary was able to learn about t < n bits of that key, but you do not know which. Can you still use your key, or do you have to throw it away and choose a new key? The leftover hash lemma tells us that we can produce a key of almost n-t bits, over which the adversary has almost no knowledge. Since the adversary knows all but n-t bits, this is almost optimal.

Золотые слова, аж зачитываюсь! Но покажите мне один, хотя бы один алгоритм, который генерирует нам такой новый секретный ключ, когда к атакующему уже утекло 99% битов от старого ключа (исходный ключ может быть выбран произвольно большим). Все алгоритмы, что видел, работают либо только для фиксированного числа утекших бит, а не процентного, либо для малого процента утекших бит. Мои требования просты:

1. Экстрактор должен быть детерминистичным².
2. Безопасность — информационно-теоретическая³ ε-безопасность⁴.

Unknown, скажите, я хочу от криптографии невозможного?

Если я всё правильно понял, в криптографии эта проблема называется «(deterministic) bit/block/entropy/randomness extraction problem», а все ноги растут из двух работ: «The bit extraction problem or t-resilient functions^[link19]» с Голдрайхом в соавторах и «Experimental quantum cryptography^[link20]»⁵, позже доделанной до «Practical quantum oblivious transfer^[link21]», с Беннетом и Брассардом. Причём последние активно ссылаются на Голдрайха, а Голдрайх (вроде бы) на первых, но видно, что и те и те работали независимо. Позже к ним присоединился Маурер («Secret key agreement from public discussion from common information», Trans. Inf. Theory 1993), а Беннет с Брассардом формализовали, что хотели сказать, в «Generalized privacy amplification» (Trans. Inf. Theory 1995). Есть ещё одна из самых первых работ — «How to Reduce your Enemy’s Information^[link22]», но мне не удалось ни найти её в свободном доступе, ни скачать по подписке. Всё вышеперчисленное — классические работы, на которые все позже многократно ссылаются. Видимо, Додис и другие появились позже, вырастив из этих работ обширную область исследований, но уже применительно не к QKD, а скорее как метод защиты от side-channel-атак и для выполнения криптографических операций в физически плохо изолированных приборах, т.е. где атакующий может много чего подсмотреть касаемо информации о ключах, состояниях шифров и т.д.

В вышеупомянутой работе Голдрайха на стр. 3 написано

"A new shared key can be deterministically computed from the old one, by each party, without any communication between them. The new key is completely secret, as its bits are independent and unbiased with respect to eavesdropper who only knows t bits of the old key. It should be stated that the new key is shorter than the old one.

что, казалось бы, ровно то, что нужно, но дальше авторы приводят формулу для числа выводимых секретных бит: n – t log₂n, что для 99%-ой утечки ключа неприменимо. Там же на стр. 6 XOR-лемма есть (её почему-то очень любят во всяких таких работах по экстракторам), но в гугле по поводу XOR-леммы пишут что-то вообще сложное и многостраничное, хотя у Голдрайха она сформулирована как простое и полуочевидное утверждение.

Вышеупомянутая «Practical quantum oblivious transfer» повергает меня в шок и ужас. Авторы буквально издеваются над читателем. Я таких препринтов ещё не видел, а скачать оригинал возможности нет. Препринт начинается тихо и мирно, как любая формальная статья, но потом начинают отовсюду лезть сюрпризы:

• На 10ой стр. доказательство приведено «in sketch» и неполно.
• На стр. 13ой они пишут

  Of course it is simplified here but you understand...

  Охренеть! Да конечно же, я understand. Они не знают, как изложить своё доказательство, чтобы всем было понятно, а читатели конечно же будут understand — им-то деваться некуда.
• Дальше идёт параграф «for your eyes only», что символично.
• На 20ой стр. они не нашли ничего умнее, чем поставить ссылку [31], по которой написан на французском тот самый бородатый анекдот про Ферма «поля слишком узки, чтобы доказательство поместилось на них». Узость полей — классный аргумент.

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

Среди недавних работ есть «Key Derivation and Randomness Extraction»^[link23] от Chevassut'а, где обсуждается Лефтовер-хэш-лемма (стр. 3), универсальные хэш-фунции (стр. 8) и, самое интересное, «deterministic extractor» (стр. 11). И ещё есть интересный свежак «Non-Malleable Condensers for Arbitrary Min-Entropy and Almost Optimal Protocols for Privacy Amplification»^[link24], где обсуждаются всякие разные виды экстракторов.

Что касается диссера Додиса, меня внизу 31ой стр. смущает фраза

We wants to say "y gives no information about x"

т.к. она кажется конфликтующей с той самой статьёй Реннера и Маурера³, т.е. такое вроде бы невозможно⁶. Или дело в том, что у Реннера ε-безопасность, а у Додиса — почти всюду вычислительная? У Додиса дан действительно неплохой обзор, но в основном он, как я понял, занимается конструированием вещей, которые лишь вычислительно безопасны⁷, но не более того.

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

Есть ещё работа «Security Amplification for Interactive Cryptographic Primitives^[link25]». Интересно, оно имеет какое-то отношение к privacy amplification? На мой поверхностный взгляд — вроде бы нет. Работа грузная, сходу смысл непонятен.

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

Для простоты можно сначала рассмотреть ситуацию, где атакующий не знает, какие именно биты в ключе им получены верно, но при этом знает общий процент битов, которые у него верны (типа 99% от общего числа). В более общем же случае можно рассмотреть ситуацию, при которой атакующий знает t «абстрактных» (т.е. в шенноновском смысле) бит информации о ключе длиной n бит.

Unknown, есть ли выход из положения?

---

¹Leftover в этом названии — фамилия или просто английское слово такое?
²Плакали все методы усиления конфиденциальности (privacy amplification), разработанные для QKD-протоколов и основанные на «универсальных хэш-функциях».
³Спасибо Реннеру и Мауреру, плакала горькими слезами^[link26] информационно-теоретическая безопасность. Но это не страшно, страшно — это если вдруг ε-безопасность обесценится до уровня вычислительной, вот тогда — да, лавры Визнера уже не видать никому и никогда :(
⁴Если я правильно понял ссылку^[link26], то это означает, что атакующий всегда будет знать какую-то долю информации о ключе, но её всегда можно будет сделать сколь угодно малой (хоть и конечной). Точнее, ключевая часть статьи вообще не понята, надо сидеть и вникать, а не фантазировать.
⁵J. of Crypt., 1992. Статья достаточно понятно написана, для людей и без зауми. Для уяснения основ QKD — самое то.
⁶Даже в QKD, где нет требования детерминистичности выводимого ключа.
⁷А это не то, что мне сейчас надо.

[/«помогите решить задачу»]
[/сопли]
[/оффтопик]

— Гость (10/12/2012 07:04)   

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

У Голдрайха в статье про t-жизнерадостные функции внизу стр. 4 есть «block extraction problem», которая обобщает такую идею, но не понятно, следует ли как-то оттуда (косвенно) решение для целевой задачи — случая произвольного процента (<100%) бит ключа, утекших атакующему. Голдрайх, видимо, просто присваивает каждому блоку некоторое значение бита некоторым способом и затем переформулировывает исходную проблему в терминах бит, соответствующих уже целым блокам.

— Гость (10/12/2012 11:06)   
"Гость (10/12/2012 06:10)" не курите больше той травы.
Большинство тех западных "авторов" и "британских ученых" выдают на гора такие "работы", что порой уже видится злой их умысел чтобы затормозить развитие науки в этой области в других странах, которые молятся на них: "вон на западе, а что мы тут, мы тут лохи, а вот они...". (когда же требуется сделать что-то стоящее – эти "авторы" вдруг начинают писать совсем понятным языком, и решают вполне адекватные задачи, вдруг :) )

— unknown (10/12/2012 11:26, исправлен 11/12/2012 12:29)   

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

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

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

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

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

Экстрактор должен быть детерминистичным

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

P.S. Я специально не занимался экстракторами, но когда то я их совсем не осилил и полностью завалил это направление.

Unknown, скажите, я хочу от криптографии невозможного?

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

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

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

Такие работы практически не читаю. Как-то не попадают в сферу интереса.

видится злой их умысел чтобы затормозить развитие науки в этой области в других странах

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

— Гость (10/12/2012 18:28)   

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

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


Хорошо, попробую.


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


Печально.


Неужели такая задача достаточно сложна даже для Вас? Есть ещё пара человек, которых можно спросить, но потом останется разве что письма слать :(


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

— Гость (10/12/2012 19:42)   
unknown, а в чём ключевое отличие экстрактора от хэша? Является ли один из них частным случаем другого?

— unknown (10/12/2012 20:29, исправлен 10/12/2012 20:39)   

Есть ли такие симметричные блочные шифры, куда на вход можно подать такой «небезопасный» пароль большой длины — намного больше, чем 512 бит?

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

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

в чём ключевое отличие экстрактора от хэша? Является ли один из них частным случаем другого?

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

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

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

— Гость (10/12/2012 23:22)   

Да, всё верно. Я хотел сказать, что есть тысячи протоколов, в которых имеется вычислительная безопасность, и которые никому не интересны кроме нескольких человек, которые их разработкой занимаются — взять хотя бы тот же неидеальный бит-коммитмент. И совсем другое дело — предъявить протокол, который даёт безусловную (unconditional) безопасность для какой-то задачи при том, что ни один чисто классический протокол не может быть безусловно безопасным. Как много есть вещей в криптографии с безусловной безопасностью? Я не могу припомнить ничего, кроме одноразового блокнота. Конечно, если совсем никак, то пусть лучше будет вычислительно безопасный протокол, чем вообще никакого.

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


Может быть, когда-нибудь мы доживём и до такого.

— Гость (11/12/2012 01:50)   

Вообще, я тут подумал, направление мысли кажется интересным. Более того, в «P=BPP unless E has sub-exponential circuits: Derandomizing the XOR Lemma»^[link27] (стр. 2) пишут

The source of our improvement is in the amplification of the hardness of a function. The idea of such an amplification was introduced in [30], and was used in [25]. One needs to convert a mildly hard function into one that is nearly unpredictable to circuits^* of a given size. The tool for such amplification was provided in Yao's paper, and became known as Yao's XOR-Lemma. The XOR Lemma can be paraphrased as follows: Fix a non-uniform model of computation (with certain closure properties) and a boolean function f : {0,1}ⁿ → {0,1}. Assume that any algorithm in the model of a certain complexity has a significant probability of failure when predicting f on a randomly chosen instance x. Then any algorithm (of a slightly smaller complexity) that tries to guess the XOR f(x₁)⊕f(x₂)⊕⋅⋅⋅⊕f(x_k) of k random instances x₁,⋅⋅⋅,x_k won't do significantly better than a random coin toss.

А в «On Yao's XOR-Lemma»^[link28] на стр. 1 пишут

Abstract. A fundamental lemma of Yao states that computational weak-unpredictability of Boolean predicates is amplified when the results of several independent instances are XOR together.

the lemma known as Yao's XOR Lemma asserts that if the predicate f is weakly-unpredictable (within some complexity bound), then for sufficiently large t (which depends on the bound) the predicate F(x₁,...,x_t) ≝ ⊕_i=1^t f(x_i) is almost unpredictable within a related complexity bound (i.e., algorithms of this complexity cannot do substantially better than flip a coin for the answer).

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

Исходя из вышеозвученных идей, можно на коленке сделать простой детерминистичный экстрактор:

Факт 1:

Факт 2:

Экстрактор:

Вопрос:

Unknown, как вам такой метод на ваш криптографический вкус? Вы заставили меня об очень многом подумать своими прогрессивными идеями. Или это первый блин экстрактор комом?^[link29]

---

^*Как правильно переводится circuit на русский язык? Повсюду встречаю это слово. Циклы? Раунды? Что это примерно значит?
^**Кто-нибудь киньте ссылку на википедию или статьи, где можно об этой задаче почитать. Наверняка ведь кто-то уже это решал лет 40 назад...

— SATtva (11/12/2012 09:06)   

Как правильно переводится circuit на русский язык?

Выбирайте. :)^[link30]

— Гость (11/12/2012 10:35)   
Это формальный криптографический термин. Если не знать заранее, как он правильно переводится, гадать бесполезно (особенно, если смысл термина тоже не понятен).

— unknown (11/12/2012 11:29, исправлен 11/12/2012 12:34)   

Вы там готовите смену парадигмы? Т.е. вот это^[link31] и это^[link32] всё внезапно устарело? И так больше аутентифицировать в квантовых каналах нельзя? Или канал какой-то особенный, не такой как у всех?

А вот это^[link33] не подходит?

Хотя вот ещё что-то такое^[link34] гуглится. Вместо квантового распределения ключей (QKD) возможна непосредственно прямая передача секретных сообщений по квантовому каналу со взаимной аутентификацией QDC^[link35] — Quantum Direct Communication.

P.S. Исправил во всех своих предыдущих комментах malleability на non-malleability. Вы поняли термин совершенно правильно, ещё в первом своём вопросе, а не заметили, что меня чего-то переклинило по названию в обратку.

— Гость (12/12/2012 01:10)   

А что, нельзя? Спасибо за ссылки, я их попозже посмотрю. Deterministic QKD — интересная мысль, надо поспрашивать народ, посмотреть ссылки, может оттуда какие-то детали будут полезны.


Встроенный пунто-свитчер метод коррекции ошибок делает шум в канале ненаблюдаемым, бывает такое. По той же причине возникает и слепота на собственные опечатки :)


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

Наконец, поскольку задача новая, и никто её раньше не ставил и не решал⁹, официального названия у неё тоже нет, а какие-то из мной желаемых названий уже недавно кто-то даже успел украсть для своих задач. Конечно, не стоит себя тешить иллюзиями: на уровне «озвучить идею, чтобы потом послать её в очередной говёный журнал с недодоказательством» могут тысячи людей, ничуть не более глупых, чем я. Тут вся соль — в самой постановке такой задачи, для чего надо иметь очень извращённое воображение и долго тусоваться на pgpru, слушая IRL-проблемы других :) Всё это можно будет потом отдельно обсудить, где-нибудь за закрытыми дверями и без прессы любопытных раньше времени глаз. Жаль, SATtva так и не сделал поддержку PGP-шифрования форумных сообщений.

Хотя порой кажется, что уже всё где-то решено, когда начинаешь смотреть близко, оказывается, что точь-в-точь то, что нужно, никто детально не анализировал и безопасность не доказывал. Например, захотел я узнать решение для оптимального bit value discrimination для стандартного BB84, но нигде не нашёл, хотя есть работа/диссер, где это рассматривают для BB84, сформированного когерентыми состояниями¹⁰. Может быть, для стандартного исходного BB84 эта задача где-то и решена, но я не дорылся.

Что ещё важно, на демонстрационном уровне мне не хочется заморачиваться запутанными состояниями, неравенствами Белла и прочим¹¹ — всё это намного менее технологично, чем обычные независимые кубиты. Потенциально можно обобщать на другие задачи и подходы, какие-то идеи уже имеются на этот счёт, но это на будущее. Пока хочется очертить задачу чем-то простым и минимальным и показать безопасность хотя бы для неё.

Ну и, если серьёзно, время поджимает. Не опубликуешь вовремя сам — до этого додумаются и опубликуют другие (если ещё не). В последних работах, в том числе по эксперименту, уже совсем вплотную подошли к тому, что нужно, им лишь немного не хватило додуматься до «идеи». И я рассчитывал, что отставание теории от эксперимента тут имеет запас хотя бы лет 5-10 минимум, но когда я прочитал про «время докогеренции — 1 секунда при комнатной температуре», очень серьёзно задумался¹². Понимаете, что такое 1 секунда? Это очень много на фоне того, как сейчас всякую экзотику¹³ делают — там времена порядка нескольких микро/наносекунд.

---

⁸Поначалу даже думал, что вообще не имеют.
⁹Мои поиски как по классической, так и по квантовой литературе успеха не потерпели.
¹⁰Т.е. де-юре это QKD в дискретных переменных, а де-факто там эти дискретные переменные модулируются непрерывными, т.е. название «BB84» там отражает только аналогию.
¹¹По вашим ссылкам всё это есть.
¹²И те, кто это делает, говорят в том числе на русском. Сильные русскоязычные (хотя многие этого не афишируют, работая в зарубежных группах) есть практически во всех квантовых тематиках. Они могут читать этот форум, но никогда не говорить об этом. Уши буквально повсюду.
¹³Типа квантовых подписей/аутентификации/вычислений с требованием слепоты.

— unknown (12/12/2012 11:07, исправлен 12/12/2012 12:18)   

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

Пусть мы хотим безопасно закодировать 128 бит, а информационный допуск для Евы — 10-3 бит информации обо всём 128-битном ключе вместе взятом. Чему равно n?

Главное, чтобы затраты на построения информационно-стойкого канала не превысили затраты на его взлом :)

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

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

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

1. Экстрактор должен быть детерминистичным

2. Безопасность — информационно-теоретическая ε-безопасность.

По поводу п.1:
Generalized Strong Extractors and Deterministic Privacy Amplification^[link36].
По поводу п.2:
Unconditional authenticity and privacy from an arbitrarily weak secret^[link37].

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

— SATtva (12/12/2012 12:04)   

Жаль, SATtva так и не сделал поддержку PGP-шифрования форумных сообщений.

Создать закрытое обсуждение ничто, однако, не мешает. :) Можете там и зашифрованные сообщения выкладывать, если считаете нужным.

— Гость (13/12/2012 09:03)   

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


Доктор unknown, откуда у вас такие картинки статьи?! Большое спасибо, я был очень впечатлён. Видимо, ранее я не по тем ключевым словам гуглил, или просто недогуглился до этого. Действительно, Реннер рассматривал похожие вещи, оттуда можно много что позаимствовать, но именно эту статью Реннера я не видел...


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


Вчерашний диалог с начальством в столовой:
— Я тут внезапно услышал про такую вещь, как детерминистичное QKD. Странно, что никто никогда про такое мне не рассказывал, это что-то интересное?
— Детерминистичное QKD? Нет, не слышали.
— Несколько статей есть на тему, какие-то китайцы, статья в Fisica Scripta...
— Китайцы в Fisica Scripta?^* А-ха-ха :) Нет, мы бы такое даже не стали читать.

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


To unknown: я ещё в августе почти написал этот внутренний креатив, но меня немного нехватило докончить, я отвлёкся и всё зависло. С тех пор текст устарел, появилось много нового и интересного. Старые протоколы были сломаны, новые придуманы. Первый протокол был вообще без экстракторов — это я только потом понял, что без них не получится. Сейчас кое-как взял себя в руки, потратил ночь и довёл до ума. Новое добавлялось поверх старого, могут быть повторения и неконситентности в тексте, но я старался в меру сил. Сразу извиняюсь за то, что там много букв. Если gpg не расшифрует, сообщите. Инструкция: gpg -d, результат — ps-файл. Ссылка^[link38]. Электронно подписано.

^*На самом деле, один из лучших трэшовых журналов. Из полного трэша это наименьший трэш, но у нас всем, что меньше PRA или PRA Rapid Communications, брезгуют, PRA — нижняя граница. Если результат нельзя пропиарить как очень существенный, то пойдёт в PRA, если можно — в PRL. Если очень круто и концептуально — в Nature-серию. Сейчас сделали очередную работу по каналам и гадаем, удастся ли её пропихнуть в PRL, и как её лучше пропиарить, чтоб повысить шансы на принятие (результат явно неубедителен на PRL, хотя и неплох). И когда смотришь, какую посредственность удаётся другим пропихнуть в PRL, желание отставать не возникает.

— unknown (13/12/2012 09:58, исправлен 13/12/2012 10:21)   

QDC, они просят не путать.

Нет, её там не было. Хотя wiki быстро пополняется всякой крипто-экзотикой, но там вроде до сих пор шумовое крипто отсутствует как класс.

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

Вот Information-Theoretic Key Agreement: From Weak to Strong Secrecy for Free^[link39] к примеру, сразу глядите в картинку, чем экстракторы отличаются от универсальных хэш-функций.

Аналогично.

— Гость (14/12/2012 05:35)   

Спасибо, тоже интересная работа. Внизу на стр. 4:

we propose a generic procedure for amplifying the secrecy of any information-theoretic key agreement, requiring an amount of communication which is negligible compared to the length of the resulting key.

И у Реннера-Вольфа¹ на стр. 12:

However, the use of extractors (see Section 3.2) instead of universal hashing for privacy amplification allows to keep the fraction of channel uses for communicating the error-correction and privacy-amplification messages arbitrarily small.

Т.е. экстракторы всё равно рассматриваются в контексте коммуникаций между Алисой и Бобом. Т.е. ключевая проблема всех этих работ — дистиллирование секрета между Алисой и Бобом посредством коммуникаций через канал с подслушивающей стороной и/или при знании ими какого-то изначального секрета. В моём же случае эффективно выходит так, как будто бы Алиса посылает сообщение Бобу, но Боб вообще свалил за пивом и не слушает её, но, тем не менее, её всё равно слушает Ева. И как тут адаптировать техники, разработанные для совсем других сценариев, надо думать. Например, можно ли провести стандартный reconciliation, а потом сделать детерминистичный privacy amplification / deterministic extractor на обоих сторонах (Алиса и Боб) без коммуникации между ними?

Вроде бы для протокола с (детерминистичными ли?) экстракторами где-то пишут, что они всё равно требуют доступа к какому-то небольшому количеству «true random bits» / «catalyst randomness», недоступных атакующему и при этом заранее известных Алисе и Бобу:

Another randomness-extraction technique, which has attracted a lot of attention recently in the context of derandomization of probabilistic algorithms, are extractors, which allow, by using only very few additional truly random bits, for extracting a weakly random source's complete min-entropy. © Стр. 11.¹

---

Roughly speaking, an extractor allows to efficiently isolate the randomness of some source into virtually-random bits, using a small additional number of perfectly-random bits as a catalyst, i.e., in such a way that these bits reappear as a part of the almost-uniform output. © Стр. 13.²

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


Интересный параллелизм со стр. 3-4¹, где тоже жалуются:

Note that all previously described protocols--interactive or one-way--for authentication with a partially secret key work only under the assumption that the key is more than "half secret" [24], [17].

In contrast to privacy amplification over an authenticated channel, privacy amplification secure against active adversaries has so far been known possible only for keys offering a relatively high secrecy level initially (at least two thirds of the key should be unknown to the adversary), and the length of the extractable secret was only a small fraction of the key's entropy [14], [24], [17].

Our results can alternatively be interpreted as realizing encryption and authentication using private keys generated by weak random sources--instead of highly compromised keys--as studied in [18], [7]. In [18] it was shown that weakly random keys from certain sources with substantial min-entropy do not allow for information-theoretically secure (one-way) encryption; in [7], it was proven that a weakly random key allows for (one-way) authentication only if its min-entropy exceeds half its length. Therefore, the results of [18] and [7] suggest that not all private keys with substantial randomness--i.e., min-entropy--are useful for basic cryptographic tasks. This is true, however, only in the one-way communication model: Our results add to this picture by showing that if two-way communication is allowed (and perfect randomness is available locally), then keys from all sources with non-negligible min-entropy allow for both authentication and encryption.

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

---

¹«Unconditional Authenticity and Privacy from an Arbitrarily Weak Secret».
²«Information-Theoretic Key Agreement: From Weak to Strong Secrecy for Free».

— unknown (14/12/2012 09:55)   
Опасаюсь, что наличие "true random bits catalyst" или "partially correlated random bits" и интерактивного двустороннего взаимодействия — принципиальное ограничение. Но надо перелопачивать тему.

— Гость (15/12/2012 01:30)   

Вопрос только в том, является ли мне нужная вещь экстрактором. Если нет, то не стоит экстраполировать на себя то, что известно про экстракторы. Если да, то опасаться нечего: кустарный экстрактор^[link40] уже приведён.

Пусть Алиса имеет 1 бит, а Ева может угадать её бит с вероятностью ½ + ε, где ε ∈ [0,½]. Можно посчитать,³ что при этом Ева знает I(ε) бит информации о бите Алисы, где


Естественно, что I(0)=0⁴ и I(0.5)=1⁵. Пусть XOR не используется, Ева угадывает бит в 80% случаев, а длина ключа составляет 128 бит, тогда Ева знает nI(ε) = 128 I(0.3) ≈ 35.6 бит. Таким образом, только 92.4 бит = (128 – 35.6) бит являются для Евы секретом. Чтобы их подобрать, Ева вынждена совершить в среднем 2^92.4-1 ≈ 2^91.4 операций про брутфорсу ключа.

Давайте посмотрим, как работает вышеприведённая схема, когда применяется тот самый XOR-экстратор, и используется 5 бит для записи одного секретного бита. Если Ева угадывает каждый бит с вероятностью 80%, то она угадывает значение XOR от этих 5ти бит с вероятностью P₅(0.8) ≈ 0.54. Таким образом, для так закодированного бита Ева узнаёт только I(0.54-½) ≈ 0.0046 бит информации о нём. Т.е. в этом случае для 128 битного ключа Ева узнает лишь 0.0046⋅128 = 0.5888 бит информации о нём. Теперь, при желании Евы сбрутфорсить ключ ей придётся в среднем совершить примерно 2^128-0.5888-1 ≈ 2^126.4 операций по брутфорсу. Как видим, уже даже пятикратный XOR даёт хорошее приближение к безопасности. Итак, исходный текст был длиной 128⋅5 = 640 бит, из которых мы извелкли 128 бит информации, безопасность которых от Евы составляет 0.5888 бит.

Остаётся важным вопрос, поставленный там же^[link40]: как оценить асимптотику P_n(p) при больших n? С ростом числа бит в XORе будет расти и число членов в обрезанном биноме, причём там коэффициенты — что-то типа C_n^k. К чему суммируются частичные суммы ряда, составленного из таких C_n^k, домноженных на степени p и ( 1 – p ), — не ясно. Решалась ли где-то такая «классическая» задача? Unknown, не могли бы вы её погуглить, когда у вас будет время, а то у вас намного плодотворней гуглёж получается по сравнению с моим.

---

³Используя, например, взаимную информацию между Алисой и Евой.
⁴Если Ева не знает ничего про бит Алисы и просто кидает монетку, пытаясь его угадать, то она не получает никакой информации.
⁵Т.е. если Ева угадывает бит с вероятностью 100%, то она знает 1 бит Алисы полностью.

— Гость (15/12/2012 02:15)   

Точнее говоря, было бы идеальным уметь обращать явную функцию x = P_n(p), т.е. находить по ней n = f ( x, p ) — число битов в XOR-строке, нужных для угадывания XOR-значения с вероятностью x, при условии, что противник угадывает каждый бит с вероятностью p. Что-нибудь известно про такую обратную функцию в комбинаторике/криптографии?

— unknown (17/12/2012 12:01, исправлен 17/12/2012 13:10)   

Вроде бы для протокола с (детерминистичными ли?) экстракторами где-то пишут, что они всё равно требуют доступа к какому-то небольшому количеству «true random bits» / «catalyst randomness», недоступных атакующему и при этом заранее известных Алисе и Бобу:

Нет, не требуется, есть seeded экстракторы, а есть полностью детерминированные.

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

Судя по приведённым ниже материалам есть экстракторы и под вашу задачу. Боб может идти за пивом.

Опасаюсь, что наличие "true random bits catalyst" или "partially correlated random bits" и интерактивного двустороннего взаимодействия — принципиальное ограничение. Но надо перелопачивать тему.

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

С ростом числа бит в XORе будет расти и число членов в обрезанном биноме, причём там коэффициенты — что-то типа C_n^k. К чему суммируются частичные суммы ряда, составленного из таких C_n^k

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

Yao's XOR Lemma^[link41]?

В любом случае, делать на ней экстракторы уже не модно^[link42].

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

Ну и весь препринт монографии теории псевдослучайности от этого автора тоже доступен^[link44].

А вот и пример экстрактора^[link45], который мог бы сгодиться хотя бы для изучения расчёта энтропии.

Условия существования детерминированных экстракторов^[link46]:

We observe that no deterministic extractor exists if the sampler is allowed to use more computational resources than the extractor. On the other hand, if the extractor is allowed (polynomially) more resources than the sampler, we show that deterministic extraction becomes possible. This is true unconditionally in the nonuniform setting (i.e., when the extractor can be computed by a small circuit), and (necessarily) relies on complexity assumptions in the uniform setting.

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

Отсюда выводятся и схемы разделения секрета^[link47], например гаммы R₁, R₂, … R_n могут быть перексорены для создания общей гаммы и розданы разным людям, а некий секрет зашифрован этой гаммой. Для расшифрования все гаммы должны быть снова собраны вместе и снова перексорены. Если хотя бы одной не хватает или кто-то её испортил, то секрет останется информационно-стойко зашифрованным.

Популярно также информационно-стойкое разделение секрета по Шамиру^[link48], которое позволяет выбрать сколько хранителей m из n могут собрать секрет. А кто-то предлагает и проактивное разделение^[link49], на случай, если противник будет охотиться за секретами.

Так что, информационно-теоретические протоколы существуют, но хорошего обзора всё никак не найти.

— Гость (17/12/2012 14:23)   
Unknown, огромное вам человеческое спасибо! Последняя информация от Вас послужила последней каплей и ключевые слова были найдены. Теперь у меня появилась почти полная уверенность в том, что я в курсе всего, что и кем было сделано в моём направлении, а что не рассматривалось. Как гласит народная мудрость, «сколько ни старайся, сколько ни пытайся быть оригинальным, учиться и думать нестандартно, всегда найдётся конкретный индюк^[link50], который сделает это раньше тебя, быстрее тебя и лучше тебя».

Что касается конкретно экстракторов... э-э-э, я недооценил масштаб катастрофы. Реальные экстракторы, используемые в проблемах такого класса, очень нетривиальны — теорема Дворецкого^[link51], геометрический/асимптотический функциональный анализ, в одном шаге от Гротендика и фундаментальной математики. Как Вам такой экстрактор?^[link52] Собственно, результат 2006-2007г.

Второй индюк, который всё это применил и решил целевую задачу, также локализован. Сейчас следствие разбирается, как далеко он зашёл (а зашёл он очень далеко). В частности, первая статья в этом направлении — 2004г, основные результаты — 2010г, адаптация под криптографию — 2011г. Диссер по этим результатам защищён 4 месяца назад, и сложность там впечатляет. Естественно, руководство всем этим делом, как и инициация идей шла от теоретиков, которые первые из первых в мире, их фамилии у всех на слуху. Короче, поздно я раскачался.

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

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

В общем, полчилось то, чего и следовало ожидать: если идея на поверхности, её моментально расковыряют. Я пока пребываю в глубоком трансе. Как соберусь с мыслями, напишу детали. Пока что есть небольшая надежда, что ещё не всё расковыряли, хотя обещанной «смены парадигмы», конечно, уже не будет 100%. Мировые новости молчат про смену парадигмы полиномиальный логарифм в применении его к криптографии, да? :)

— unknown (17/12/2012 16:18, исправлен 17/12/2012 16:19)   

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

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

— Гость (17/12/2012 17:28)   
Нет, с кличкой собаки вряд ли заработает — нужна тру рандомность :) И ещё поди наверняка нужна запутанность, технологичность которой в больших масштабах тоже под вопросом.

— unknown (02/12/2013 11:03, исправлен 02/12/2013 11:23)   

Где-то потерял ссылку, как этим летом в лабораторных условиях испытывали квантовую память. Сначала, как я понимаю, традиционно охлаждали материал до низких температур, а затем подняли до комнатной и при комнатной температуре память держалась около 40 мин. Причём, материал использовали какой-то доступный (кремний с фосфором?).

— Гость (02/12/2013 11:31)   

Оно много где было (например, здесь^[link53]). Всё бы ничего, но кубитов там «10 billions», и все в одинаковом состоянии ⇒ для спецзадач не годится (для квантовых вычислений и просто памяти, может, и подошло бы, не знаю). Декогеренция — 39 минут при комнатной температуре и 3 часа при криогенных температурах.

— unknown (26/02/2014 11:10, исправлен 26/02/2014 11:13)   

/comment58879^[link54]:

Вместо квантового распределения ключей (QKD) возможна непосредственно прямая передача секретных сообщений по квантовому каналу со взаимной аутентификацией QDC^[link35] — Quantum Direct Communication.

/comment58935^[link55]:

Deterministic QKD — интересная мысль, надо поспрашивать народ

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

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

/comment58938^[link56]

Детерминистичное QKD

QDC, они просят не путать.

И вот теперь египтяне: Quantum Secure Direct Communication using Entanglement and Super Dense Coding^[link57].

Quantum secure direct communication (QSDC) (Bostrцm, 2002, Deng, 2008) is another branch of quantum cryptography. Different from QKD, QSDC allows the sender to transmit directly the secret message (not a random key) to the receiver in a deterministic and secure manner. If it is designed carefully, a QSDC protocol can also attain unconditional security (Deng, 2003).

The main objective of our research is to introduce a new protocol that guarantees more security of the transmission than the QKD and also saves more time, cost and gives more efficiency for the transmission, as it is using the super dense coding technique that transmit two classical bits by sending one quantum bit. In our protocol of the quantum secure direct communication we use the maximally entangled Bell states to encode the message bits on the basis of the super dense coding theorem, and then transmitting them on two quantum channels to the other side with less probability of the eavesdropping, and with no need for a pre-shared key that in turn needs many rounds to distribute, and also a public discussions to verify the correctness of the key.

Тем более, кто-то ☺ здесь недавно ссылки на кодирование в квантовом канале приводил^[link58], а в QDC используется как раз "The super dence coding procedure".

Also, for efficiency purposes super dense coding is used, which is also based on entanglement, to double the transmission speed by sending two classical bits over one quantum channel. This protocol uses one step or one pass to end the message in a secure manner.

— Гость (26/02/2014 14:24)   

Имеем:

1. Египтяне.
2. M$ Word.
3. Неконвенциональное оформление.
4. Конференция, а не журнал.
5. Безобразный английский (предложение, простирающееся на весь §4.1, меня вообще вырубило).
6. Отсутствие доказательства безопасности.
7. У авторов это первая статья в архиве.
8. Плагиат:

   arXiv admin note: text overlap with

⇒ не взлетит, ноль шансов.


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


Кстати, обсуждали его ранее [1]^[link60], [2]^[link61].


Очень смешная фраза. Египтяне пытаются писать о небезопасности конвенционального QKD? А в чём их претензия? Может, у них своя безопасность, более сильная, чем IT? Писали бы сразу «more security of the transmission than the OTP», чего стесняться-то.


Они там случаем E91 не переизобретают?

T^[link62]he original Ekert protocol consist of using three possible states and testing Bell inequality violation for detecting eavesdropping.

Кажется, я слышал, что E91 эквивалентен BB84, но не помню в каком смысле. Возможно, в плане доказательства безопасности, а, возможно, и с точки зрения эффективности протокола (или даже и то и то вместе).

Идеи двухканальных QKD (см. Fig.2, стр.5 египетской статьи) действительно существуеют, их называют двусторонними. Они действительно должны давать лучшую эффективность. У Марко (см. [3]^[link63], [4]^[link64]) с Реннером недавно была работа на тему^[link65], но даже там:

we provide a strategy to prove security for two-way quantum key distribution protocols against the most general quantum attack possible by an eavesdropper.

Т.е. самого доказательства безопасности ещё нет.

P.S. Трэшак из cs.CR не читайте, практически всё достойное по теме квантового крипто проходит через его quant-ph-секцию.

— unknown (26/02/2014 14:35)   
А то, на что они ссылаются? И вообще, QDC имеет какие-то перспективы?

— Гость (26/02/2014 16:14)   

Во введении они ссылаются на классические признанные работы по теме QKD, а также на две работы по QDC: китайскую^[link66] в Phys. Lett. A^[link67]1 и немецкую^[link68] в PRL. Из первой работы выцепляется вся биография по теме, включая вторую работу немцев:

Recently, a novel branch of quantum communication, quantum secure direct communication (QSDC) was proposed and actively pursued by some groups [13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26].

Среди работ [13-26] есть ссылки на PRA, PRL^[link69] и нескольких др. журналов относительной приемлемости, хотя всяких Chin. Phys. тоже хватает. Родоначальник направления — статья^[link70] в каком-то польском журнале Acta Phys. Pol. A^[link71].² В общем, если хочется понять смысл, надо читать начиная с этих первых работ — там и язык нормальный, и оформление соответствующее, и смысл яснее излагается.


Раз там есть несколько работ в PRA, и даже не одна в PRL, то полным трешом это направление точно не является. Насколько оно перспективно — мне трудно судить. Мне показалось, что это а) не мейнстрим б) протокол релятивистский с) непонятно, как это дружит с неизбежными шумамами в канале. Чтобы сказать что-то более детально, надо вдумчиво читать работы и/или спрашивать у тех, кто более причастен к теме QKD.

Относительное сравнение журналов по импакт-фактору (см. вышеупомянутые ссылки [13-26]):
— Acta Physica Polonica A: 0.34^[link71]
— Chinese Physics Letters: 0.811^[link72]
— Optics Communications: 1.316^[link73]
— Physics Letters A: 1.632^[link67]
— Physical Review A: 3.042^[link74]
— Physical Review Letters: 7.943^[link75]
Например, китайский аналог американского/международного PRL'я, как видно, в 10 раз хуже оригинала. В респектабельных научных кругах считается^[link55], что публиковать что-либо в журналах ниже PRA смысла нет (по крайней мере, по теории, что там у экспериментаторов на уме дословно — не знаю, но, в целом, должно быть так же³).

---

¹Журнал средней паршивости, но, в принципе, с натяжкой приемлемый.
²См. стр. 14, что как бы символизирует о том, что не всё так просто.
³Экспериментаторам даже намного проще пролезть в самые престижные журналы (типа Nature-серии и Science), чем теоретикам.

— unknown (26/02/2014 16:57, исправлен 26/02/2014 16:59)   

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

Ваши гауссовы каналы^[link76] вроде как тоже недавно были не особо мэйнстримом:

Ещё одна проблема — узость профессиональных кругов. Если тема не ужас как популярна в сообществе

Пропускная способность (capacity) гауссовых квантовых каналов — пример таковой.

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