РегистрацияПро Keccak и PRP
Приветствую!
Изучаю структуру Keccak, и там говорится о том, что внутри sponge функции используется PRP, т.е. псевдослучайная перестановка. Какая же эта перестановка, если после первого же раунда оно нулевое состояние отображает в ненулевое?
У Шнайера в практической криптографии перестановками называются комбинации всех пар открытый текст\шифротекст для блочного шифра при определенном ключе. И там это понятно, т.к. имеется биекция открытый текст:шифротекст. А тут? Тот же принцип или я чего то не понимаю? В некоторых текстах встречал значение permutation и как перестановка и как подстановка? В общем, в голове каша.
И еще, где то рядом видимо со всеми этими штуками лежит утверждение о том, что перестановки не содержат коллизий по умолчанию. Это типа гарант того, что sponge с хорошим f неотличим от RO. Эту мысль я тоже не до конца понял, но думаю она прояснится когда решится вопрос с перестановками.
комментариев: 9796 документов: 488 редакций: 5664
Перестановка по-английски, действительно, permutation. Например, в шифре DES есть P-блок для побитововй перестановки. А AES — это т.н. SP-сеть, в которой есть слой перестановки и слой подстановки.
Подстановка — это substitution. А теперь, внимание S-блок, размером 4x4 бита:
S-блок. Substitutuion, подстановка. А сдругой стороны — перестановка. естественно, если на вход подать одни нули, то на выходе будут в данном случае одни F.
Но блочный шифр — это многораундовая SP-сеть, да ещё с ключевым расписанием. Даже при фиксированном ключе (как в хэш-функциях) на выходе будет рэндом. Если размер входного блока PRP-шифра 128 бит, то можно взять все 2128 вариантов входа от {000 … 0} до {FFF … F}, а на выходе получатся все те же 2128 вариантов, но переставленных в псевдослучайном порядке (вот это и PRP).
У хэш-функции Keccak во встроенной PRP-функции размер больше (1600 бит, если не ошибаюсь). В отличие от функции сжатия в традиционных хэшах (обычно 2→1), в которой можно добиться внутренней коллизии, в PRP коллизия по определению невозможна.
Это не означает какого-то особого превосходства Keccak. Авторы просто элегантно избавились от ряда атак, сильно упростили доказательство стойкости и открыли путь к универсализации своей конструкции.
Сама PRP в губчатой конструкции м.б. неидеальна и также потенциально уязвима к любым видам криптоанализа. Да, в ней самой нельзя получить коллизию, но можно получить цикл, когда на при определённых данных, поглощаемых в фазе абсорбции между f-функциями на входе (кроме нулей в первом раунде), на выходе можно будет также получить нули или какие-то предопределённые значения, приводящие к появлению цикла. Цикл в таком случае будет также фатален как и внутренняя коллизия в традиционных функциях.
На выходе снимается только часть внутреннего состояния PRP. Если PRP идеальна, то эта часть на выходе будет давать коллизии с такой же вероятностью, как и идеальный случайный оракул (до предела размера внутреннего состояния, которое ограничено у PRP-функции Keccak и бесконечно велико у RO) — хэши вообще без коллизий не бывают, иначе это — не хэши. Итак, Sponge-конструкция доказуемо безопасна, если безопасна (идеальна) лежащая в её основе PRP. А может оказаться, что она и не идеальна, тем более её сильно оптимизировали и здорово на ней экономили.
комментариев: 9796 документов: 488 редакций: 5664
Как же м.б. неоднозначно? Это же биекция, обратимое преобразование. От неё просто отрезают кусок на выходе — получается необратимое преобразование, за счёт потери данных внутреннего состояния. И коллизии в отрезанных кусках естественно будут. Главное, чтобы не чаще, чем в идеальном случае. Но само внутренее состояние в полном виде никуда не девается и идёт на обработку последующих данных (смещивающихся с его частью на входе и выводящихся от его части на выходе).
Я даже предлагал авторам сделать из внутренней PRP-Keccak блочный шифр, приделав ключевое расписание из самого Sponge-Keccak, запущенного параллельного. Они ответили, что разумеется работать будет, т.к. PRP по определению обратима. Только они её проектировали так, что в одну сторону она работает быстро, а в обратную (расшифрование) — медленно, неоптимально и возможен класс атак на прогоне данных взад-вперёд, т.е. это просто неоптимальная для чисто блочного шифра конструкция.
И в обычных шифрах могут быть легче плучены циклы, если бы их использовали для хэширование в Sponge-режиме (или каком-либо ином), где противник может видеть массу промежуточных данных на всех раундах и подгонять вводимый на хэширование текст. При обычном хэшировании у противника же нет секретов — он всё видит.
Кое-что (поверхностно) разбиралось здесь.
Это я понял, просто я не нашел где указано, что функция f обратима. Это меня и смутило. С Фейстелем я разобрался, там просто делается a ^ b ^ c = d, а потом d ^ с ^ b = a, вот и обратимость. А тут она для меня не очивидна, в т.ч. из за путаницы с подстановками-перестановками (
То, что функция f обратима, где то доказывается? Потому что по ее этапам я этого, к сожалению, не вижу. И обратной ей функции в доках тоже не видел. Или только предполагается, что она обратима, потому что она визуально хорошо всё перемешивает, лавинный эффект там то сё (в курсе, что куски, из которой она состоит, изучены вроде бы хорошо, но это все равно ничего не объясняет)?
комментариев: 9796 документов: 488 редакций: 5664
Сейчас большинство криптоалгоритмов проектируются на функциях, которые обратимы сами по себе, безо всяких сетей Файстеля. Сконструировать их несложно.
Обратимость видна часто невооружённым глазом. Это такая самоочевидная тривиальщина, что доказательство м.б. даже опущено в работе. Или авторы от балды написали, что у них ключевая функция — PRP? Там же куда более сложные вещи доказываются — уровень алгебраической сложности и пр.