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

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

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

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

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

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


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

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

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

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


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

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

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

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

^*Это — если все трое друг с другом не связаны. Если же связаны, то ρ_total будет принадлежать тому же пространству, но не будет факторизованным по подсистемам.

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

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.: Смотрите, как тонко троллит 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)

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

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

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

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

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


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

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

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

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

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

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

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

В пику обсуждений одноразового блокнота попалась статья на эту тему и на тему вышеобсуждавшейся non-malleability: «Non-malleable encryption of quantum information». На 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 4ⁿ 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 d² .) 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-стойкости в пользу вычислительной (обоснованной вычислительной), может, что-то и можно сделать, не знаю.

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

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


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


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

Реннер — бог №1 в мире в области теории по квантовому крипто (в широком смысле этого слова), и Уэли Маурер — отец его его руководитель по диссертации, поэтому с ε-точностью, где ε→0, можете считать это мнение истиной в последней инстанции.

Ограниченное non-malleability возможно и при использовании обычного одноразового блокнота, если использовать две некоммутирующие гаммы: например, одну для обычного XOR, а вторую — для перестановок внутри отдельных блоков. А чем Вегман-Картер то не угодил?

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

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"», но кто сказал, что нельзя иначе? Берём любой базис и кодируем туда битовые строки как


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

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

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

А чем Вегман-Картер то не угодил?

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

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

Отсюда:

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 бит хватит для разовой аутентификации сообщений практически любой длины, встречающейся на практике.

Похоже, вот оно:

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] — та работа, которая здесь уже упоминалась). И вот слайды к этой работе (интересно, там ссылка на того самого Дамгарда, который DM?). К слову, слайды почти всех докладов с QIP-2014 доступны.


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

Про остальное позже.

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

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 и создание поточных квантовых шифров, прям с Реннером в соавторах:

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

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

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.

А эта работа является производной от ранней работы того же 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», идея которой была позднее развита в «On the foundations of quantitative information flow» от Smith'а, который из этого вырастил фактически целое направление со своей школой. Это всё про самое то, что нужно: privacy & leakage. Так вот, оказывается этот самый Массей отнюдь не случаен и по математической генеалогии приходится отцом Мауреру и дедом Реннеру, хотя до сего дня я думал, что они вообще из разных школ и никогда друг про друга не слышали. Таже с удивлением узнал, что Массей — соавтор шифра IDEA, и умер он от рака в прошлом году. ☹ На концептуальном уровне число Эрдёша как бы закрывает проблему (связность в исследовательском сообществе имеется):

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

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