Инструмент для детектирования шифртекста

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

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

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

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

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

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

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

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

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

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

Diehard

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

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

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

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

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

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

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

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

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

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

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

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

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

Мое упущение, я не указал что речь идет только о симметричных шифрах

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

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

Тут пишут, что

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.

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

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.

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

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

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

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

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

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

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

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

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

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

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

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


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


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

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

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

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

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

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

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

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

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

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