id: Гость   вход   регистрация
текущее время 13:53 28/03/2024
Автор темы: astramax, тема открыта 01/03/2010 16:29 Печать
Категории: криптография, криптоанализ, симметричное шифрование, случайные числа, атаки
http://www.pgpru.com/Форум/Криптография/ИнструментДляДетектированияШифртекста
создать
просмотр
ссылки

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


Доброго дня! Может кто подскажет...


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


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


Вопрос:
Нужны ссылки на алгоритмы (может быть opensource реализации) подсчета битовой статистики, а также критерии, по которым принимать решение "открыто/зашифровано".


Заранее спасибо


 
На страницу: 1, 2, 3, 4, 5 След.
Комментарии
— Гость (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)   профиль/связь   <#>
комментариев: 11558   документов: 1036   редакций: 4118

Существует, называется видеоплеером.
— Гость (01/03/2010 19:23)   <#>
Существует, называется видеоплеером.
Если плеер не знает формат файла и как кодировалось, он не проиграет файл. Можете отрезать заголовок и попытаться проиграть, если не верится. Либо надо будет в командной строке указать все характеристики видео явно. К тому же речь идёт не о переборе только среди известных (распространённых) форматов видео-файлов, а среди любых файлов, которые являются видео (алгоритм должен работать и против тех форматов, что будут созданы в будущем). unknown писал, что якобы можно отличить криптоконтейнер от куска видео/архива, но подробностей, к сожалению, не привёл. Я предполагаю, что видео немного отличается от крипто по энтропии, но не уверен. В конечном счёте, и видеокодек, и криптоалгоритм – какие-то алгоритмы, потому не ясно почему обязательно хороший видеокодек всегда будет давать меньшую энтропию чем любой кусок криптотома – ведь хорошее крипто определяется не только энтропией на каких-то образцах, но и различителями в модели случайного оракула.
— SATtva (01/03/2010 19:40)   профиль/связь   <#>
комментариев: 11558   документов: 1036   редакций: 4118
Я предполагаю, что видео немного отличается от крипто по энтропии, но не уверен. В конечном счёте, и видеокодек, и криптоалгоритм – какие-то алгоритмы, потому не ясно почему обязательно хороший видеокодек всегда будет давать меньшую энтропию чем любой кусок криптотома

Тогда Вам стоит освежить в памяти различия между кодированием и шифрованием.
— Гость (01/03/2010 19:56)   <#>
SATtva, оба ваши ответа совсем не в тему. Я в курсе об отличии кодирования от шифрования. Речь идёт о том, что энтропия хорошего кодека может приблизиться и достичь той, которую дают криптоалгоритмы. Как в таком случае различать одно от другого по единичным образцам доступным для исследования, мне не ясно. В этом и состоял вопрос.
— Гость (01/03/2010 20:03)   <#>
Тогда Вам стоит освежить в памяти различия между кодированием и шифрованием.
Для особо умных ещё так можно сказать: представьте, что вам дан пароль, а алгоритм шифрования не известен (причём известно что он стойкий; пока условно забудем что число известных стойких алгоритмов мало и их можно все перебрать для данного пароля). И дано много файлов, часть которых есть куски криптотома, зашифрованные каким-то криптоалгоритмом с вам данным паролем, а часть – просто куски видеофайлов или архиваторов. Задача: выяснить, какой файл – часть криптотома, а какой – часть другой субстанции. Если не понятно: я свёл оба случая к "кодированию", теперь уже никакого шифрования нет согласно определению.
— SATtva (01/03/2010 20:04)   профиль/связь   <#>
комментариев: 11558   документов: 1036   редакций: 4118
КО спешит напомнить, что, независимо от энтропии образца, пространство и потенциальная энтропия ключа шифра несколько выше пространства и энтропии всех параметров кодека, что позволяет перебрать последние с куда меньшими затратами, нежели брутфорсить ключ.
— Гость (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, чтобы зашифрованный раздел выглядел так, как будто там раньше лежали архивы и фильмы ;)
На страницу: 1, 2, 3, 4, 5 След.
Общая оценка документа [показать форму]
средний балл: +3респондентов: 4