Криптоанализ. Проконсультируйте

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

Злоумышленнику неизвестно:
1. Алгоритм получения шифрообразов из слова W;

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

Уточните задачу.

Бред... Постановка задачи равна сферическому алгоритму в вакууме :)

Да. Вообще в формировании шифрообразов может участвовать и несколько алгоритмов. Все или часть из них будет использовать "надежный" ключ, который злоумышленник НЕ МОЖЕТ (аксиома) узнать.


Согласен. Подразумевался конкретный алгоритм шифрования или цепь алгоритмов шифрования. Я имел в виду, что он может быть сколь угодно сложным и злоумышленнику не будет известен. Попытаюсь конкретизировать на простом примере.
Пусть существует слово, которое мы шифруем и это слово простое число 3.
Есть цепь из различных алгоритмов (например, один из них RC6), которые шифруют слово (наше число 3) с неким паролем (например, ключ размером 1024 байта).
Количество зашифрованных вариантов (я их назвал шифрообразами) слова (нашего числа 3) очень-очень велико и длина каждого произвольна (зависит от размера ключа и неких настроек в алгоритмах).
Злоумышленник знает наверняка лишь какую-то часть этих шифрообразов (например, 300 000 из неизвестно скольки). Также он знает наверняка, что ВСЕ эти шифрообразы соответствуют слову (т.е. числу 3) и знает само слово (т.е. число 3). Т.е., наверняка известно, что существует алгоритм, который способен декриптовать любой шифрообраз из списка и получить искомое слово (т.е. число 3). В споре некоторые утверждали, что сложность алгоритма не играет для злоумышленника особой роли и построить инвариант, цитирую, не теория, а простая задача по мат. статистике. Как мне кажется задачка отнюдь не простая и осуществима лишь теоретически. Что-то вроде: возможно, но потребуется 10^n лет. Т.к. доказать свое предположение я не могу, есть вероятность что я ошибаюсь. Потому и прошу проконсультировать.

Есть методология доказуемой безопасности, где в таком абстрактном виде вопросы и ставятся, по ней и нужно рассматривать. Только там нужно доказать что алгоритм неразличим от модели случайного оракула (ROM), если принять что его составные части — идеальны.

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

ROM модель уже не работает. Какой длины ключ не прикручивать, то стойкость (в ROM), не будет выше 2^8•b, где b — число байтов открытого текста.
Есть некая функция f(W, k,...), в которой есть несколько входов, и выход — шифртекст. Противник может перебирать любой из входов, значит он может перебирать и исходный текст.
Единственная защита для коротких открытых текстов — использовать большой (128-бит) блок и рэндомизацию через вектор инициализации. Нерандомизированное шифрование (stateful encryption) может использоваться только для больших сообщений, но оно имеет кучу ограничений и неисследовано до конца.

Из одного и того же шифртекста W получаются шифртексты разной длины?

Злоумышленнику неизвестно:
1. Алгоритм получения шифрообразов из слова W;

Принцип Керхгоффа нарушен? Это не открытая криптография? DRM?

Именно. Из одного и того же слова W получаются шифры разной длины. Т.е., число 3 (например) в алгоритме преобразуется тем или иным образом, а после забивается неким произвольным набором символов и преобразуется вновь и так может быть сделано несколько раз. Т.е. на выходе получим: в случае n+1 прохода строку с произвольными символами размера 568 байт; в случае n+2 размер строки может быть равен 732 байта, а в случае n+k размер строки будет равен 486 байт. Это просто примеры.



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

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

Принцип Кирхгофа (исходя из прочитанного определения,

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

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

Лучше скажите что Вы хотите в результате получить? Надежную систему?

т.к. я не очень разбираюсь в вопросе) соблюден.

Главные слова :)

Откуда это следует? Я лишь вижу что это вполне осуществимо. Более того, это уже сделано. Алгоритмы есть. Написана программа, которая их использует. Шифрую слово (то же число 3) 300 000 (например) раз с одним и тем же набором ключей и получаю 300 000 шифрообразов. А теперь злоумышленнику нужно создать на основе этих шифрообразов инвариант. Вполне конкретная задача.


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

Вдогонку. Одна из сторон как первый и единственный аргумент привела абстрактную машину Тьюринга. Что, мол, поставленная задача решаема и Тьюринг за нее получил всемирное признание.

Если попытаться объяснять Вашим языком:

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

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

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

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

Шифрую слово (то же число 3) 300 000 (например) раз с одним и тем же набором ключей и получаю 300 000 шифрообразов. А теперь злоумышленнику нужно создать на основе этих шифрообразов инвариант. Вполне конкретная задача.

Это невозможно, поскольку злоумышленнику неизвестен алгоритм, а в нём может, например, стоять:

If n>300000 then шифровать_другим_способом

;)

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

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

С учётом ваших уточнений, ответ – "в общем случае – нет". Контрпример: Миллиард сообщений, зашифрованных aes-128, все из которых используют длинные случайные пароли.
PS: Либо(!), ответ "да", если придерживаться мнения, что любой блочный шифр потенциально можно сломать в будущем, а большое число – научиться быстро разлагать на множители, однако, за прошедшие 50 лет превратить такую "теорию" в "практику" до сих пор не получилось. unknown, кажется, писал, что даже не все сообщения, зашифрованные энигмой времён ВОВ, сейчас смогли сломать, и это при том, что тогда криптография была несоизмеримо слабее сегодняшней.

2. Играет ли какую-либо роль при ТАКОМ подходе сложность алгоритма получения шифрообразов;

Очевидно, да. Пример: любой из достаточно слабых и прекрасно ломаемых "шифров".

3. Если такая задача практически осуществима, то как (или есть ли возможность) определить временные затраты (достаточно неких пределов в виде «минуты», «часы», «годы», «столетия», etc);

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

Ваши ответы понятны. Спасибо.

Спасибо. Сразу после сообщения от unknown я нашел, прочитал и попытался понять изложенное в статье.

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

З. Ы. Кстати, на просторах интернета как-то наткнулся на работу (по-моему чей-то диссер) с темой "Полиморфные криптоалгоритмы". Криптостойкость была так себе, но идея интересная :)

Зачем?!