id: Гость   вход   регистрация
текущее время 13:00 28/03/2024
Автор темы: Гость, тема открыта 23/12/2014 00:28 Печать
Категории: криптография, алгоритмы
создать
просмотр
ссылки

Crypto How stuff Works


Бывает ли книга по криптографии, где бы детально обсуждались и сравнивались различные примитивы и конструкции низкого уровня; возможно безотносительно к реализациям конкретных шифров на их основе. Интересно посмотреть, почему cделали так, а не иначе, что и насколько сильнее/слабее, быстрее/медленнее и пр.


 
На страницу: 1, 2, 3 След.
Комментарии
— ZAS (10/01/2015 07:15)   <#>
>Не бывает идеальных блочных шифров (доказывается строго)



Наоборот. Если он задан истинно случайной большой таблицей, то он идеален как одноразовый блокнот идеальный блочный шифр. Случано сгенерированная таблица размером 2128 • 2128 = 2256 — это IBC, он же большой S-блок.


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

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


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

http://www.zas-comm.ru
— unknown (10/01/2015 14:33, исправлен 10/01/2015 15:06)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Конечно, перестановку, заданную таблицей.



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


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


Сама по себе постановка вопроса в перестраховочной криптографии — теоретически неинтересна.


Если мы может создать шифр с гарантированно 256-битной стойкостью, то зачем нам стойкость больше? Даже от квантовых компьютеров хватит 512 бит, если не появится специфических видов квантового криптоанализа симметрики. А появятся они или нет, и в каком виде, сложно даже предположить, хотя некоторые пытаются.


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


Вообще, тема уже неоднократно обсуждалась, например здесь.


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


Тот же HPC, как ни высмеивали его автора за маргинальный подход, стал прообразом tweak-шифрования, некоторых видов дискового шифрования, шифрования несцепляемых блоков меньше 64-128-256 для каких необычных протоколов, для полей в базах данных, для блочного шифрования в недвоичных системах счисления и др.

— Гость (10/01/2015 18:41)   <#>

с каскадами настойчиво предлагаю закончить ©


Вся суть в этих словах:

если построят все варианты моделей каскадов перестраховочных шифров, как у нас уже ранее обсуждалось, в рамках всех формальных моделей PRP/PRF-идеальной безопаности, то вместо каскада станет ясно, как создать очередной более стойкий шифр

Не забывайте, что ZAS — тролль. Если подзабыли, то почитайте первые страницы. Всё, что нужно, уже было произнесено.

Когда ZAS'у будет нечего ответить, он вам скажет, что вы переозвучиваете то, что где-то кем-то написано, а не пишете от себя (даже если вы переозвучиваете, что 2*2=4). А вот он, такой весь из себя умный, никого не слушает и идёт своей дорогой. Похоже на классический хрестоматийный случай любителя, который нахватался обрывочных знаний по вершкам и думает, что у него есть цельная картина и понимание, дескать, что Шамир придумывает шифры, что он — разницы нет.
— ZAS (10/01/2015 19:22)   <#>
>Возвращаясь к излюбленной теме построения легковесного блочного шифра с произвольно задаваемым размером блока и ключа.


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


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

Но затем решили, что лучше создавать режимы для обычных блочных шифров (один из интересных последних — OCFB),


Вы уже приводили ссылку на WCFB; спасибо; изучил. Некоторые действия и утверждения авторов сомнительны и странны, но как wide block режим без претензий на повышение стойкости – сойдет. Мне хотелось бы именно повышения стойкости. Для того, чтобы обьединить обычные блочные шифры в широкий блок, нужна более сильная схема перемешивания и/или большее количество раундов. Хорошие результаты были бы от перемешивания на MDS-полиномах, но непонятно как сделать такое перемешивание для блока произвольно задаваемого размера. Перемешивание на основе cетей Файстеля приводит к N^2 возрастанию числа операций. Самый слабый вариант перемешивания – с циклическим сдвигом на пол-блока между раундами.

Негласно считается, что с симметрикой всё хорошо, весь реальный криптоанализ строится поверх багов программных реализаций.


Это почти так для шифров; не совсем так для хеш функций; и еще специфические проблемы типа related key.

даже в конкурсе AES один такой маргинальный монстр HPC безуспешно участвовал


В HPC можно отметить сильное ключевое расписание, представляющее собой PRNG. Хорошо, но уж очень медленно и монструозно.

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


Мои идеи намного незатейливей, например: enrupt

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


Каскад решает вопрос с размером ключа, но не с размером cостояния. Кроме того, для каскада требуется генератор key schedule, который по уму опять-таки требует размера состояния с весь длинный ключ.

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


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

http://www.zas-comm.ru
— unknown (10/01/2015 20:21, исправлен 10/01/2015 20:38)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

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


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



Если 2128, 2256, 2512 — это мало, то тогда лучше вычислительно-стойкую криптографию вообще бросать, переходить на квантовую что-ли. Ну или отпозиционируйте свою идею, разрекламируйте, только так, чтобы увлечь специалистов, а не шифрпанков. Если ваша аудитория — шифрпанки, то нет проблем, увеличивайте стойкость как хотите. В качестве аргументации будет достаточно страшилок про сверхмогущее АНБ.


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

— ZAS (10/01/2015 21:44)   <#>
Для масштабируемых на произвольный блок сетей Файстеля, и вроде бы, IDEA, была даже какая-то диссертация, но вроде не особо авторитетная, я как-то пытался её найти, но не вспомнил.


Fibikova


Для IDEA предлагается схема с циклическим сдвигом на пол- малого блока в каждом раунде. Линейная диффузия; N^2 операций, малоэффективно. Если бы автор использовал, например, интерлив слов с сдвигом на половину всего большого блока, то диффузия была бы экспоненциальной (порядка N log(N) операций). Но тогда труднее обосновать нужное число раундов. Для Файстеля рассматривается SHA-подобная схема; тоже квадратичная.

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


Похоже на то. Доказуемая стойкость при квадратичной зависимости.

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


Обычные шифры – частные случаи с числом операций N log (N). Наверное, возможен и общий случай для блока произвольного размера и N log N операций.

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


Я учусь; мне интересны новые знания и обмен мнениями с опытными людьми. Хочется понимать, как работают криптографические примитивы, что и почему и как делается.

В качестве аргументации будет достаточно страшилок про сверхмогущее АНБ.


Видите ли. Обыватели плохо представляют, что такое спецслужбы. Отсюда наивная вера в Tor, TrueCrypt и пр. Дело отнюдь не в слабости крипто как такового.
— unknown (10/01/2015 22:07)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Т.е. вы не пытаетесь сформулировать никакой теоретической базы под свою задачу. Просто кидаете тролльские провокационные утверждения, что существующее крипто фуфловое плохо обосновано и можно якобы также необосновано предложить кучу других вариантов. А на самом деле вы просто хотите так поучиться, да ещё чтобы кто-то ваши учебно-тренировочные алгоритмы разобрал и разъяснил все ошибки.
— ZAS (11/01/2015 00:18)   <#>
Т.е. вы не пытаетесь сформулировать никакой теоретической базы под свою задачу.


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

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


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

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


Взаимный обмен идеями, решениями и упражнениями был бы всем полезен. Во всяком случае намного лучше споров ни о чем.
— unknown (11/01/2015 02:01)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Ну вот как так можно :) Если смотрю в книгу и вижу фигу, то может книга и фигОвая, но может в ней плохо разобрался?

Но если все публикации в какой-то теме воспринимаются как фиговые, то что-то фигово скорее в понимании темы. Хотя, даже если в самой теме так фигово, то тогда нет смысла этой темой темой заниматься, какой интерес разбираться во всякой фигне, если она для вас не более чем отфонарная фигня? Ну вместо чужой отфонарности — будет своего сочинения, тогда это просто NIH-синдром.
— Гость (11/01/2015 12:39)   <#>

Лол.


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

Метод огораживания от входящих писем заслуживает отдельной ссылки

Это ответ Додиса на «What to do if you are interested in working with me?». У Ааронсона ответ примерно такой же.
— unknown (11/01/2015 14:43, исправлен 11/01/2015 14:49)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Memo to the Amateur Cipher Designer:

A cryptographer friend tells the story of an amateur who kept bothering him with the cipher he invented. The cryptographer would break the cipher, the amateur would make a change to "fix" it, and the cryptographer would break it again. This exchange went on a few times until the cryptographer became fed up. When the amateur visited him to hear what the cryptographer thought, the cryptographer put three envelopes face down on the table. "In each of these envelopes is an attack against your cipher. Take one and read it. Don't come back until you've discovered the other two attacks." The amateur was never heard from again.

Это Шнайер, 1998 год. При том, что это всё настолько устарело, что сейчас новые шифры уже давно не нужны от любителей вообще, да и от большей части профессионалов тоже. Новый симметричный криптопримитив уже никто специально без повода разбирать не будет. Его публикация скорее пройдёт просто незамеченной. Даже тот же Twofish никто лишний раз не поковыряет, пока AES не сломан.

— Гость (11/01/2015 15:15)   <#>

Это супер! Надо будет запомнить. :-)

Там же:

Algorithms posted to Internet newsgroups by unknowns won't get a second glance.

unknowns can't get their ciphers published because they are unknowns, and hence no one will ever see their work.
— unknown (11/01/2015 15:36, исправлен 11/01/2015 15:39)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Unknowns can become knowns
by publishing cryptanalyses of existing ciphers


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

— unknown (12/01/2015 02:22, исправлен 12/01/2015 02:24)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

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

— Гость (12/01/2015 11:55)   <#>
По конвенции маркировка такая:


А у вас, unknown, всё наоборот в плане «>».
На страницу: 1, 2, 3 След.
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3