Comments 19
У случайной перестановки размера n средний размер цикла имеет порядок корня из n. Поэтому нет ничего плохого в периоде 49146 у перестановки размера 232.
Дополнение. Для понимания математического доказательства о неотличимости конкструкции sponge от случайного оракула имеет смысл послушать лекции class.coursera.org/crypto/lecture/. На русском аналогичные материалы в свободном доступе найти сложно, наши учебники содержат несколько иную тематику.
А разве в этом курсе про случайный оракул упоминается? Я что то пропустил такое.
И про доказательство криптостойкости губки — тоже, что-то не помню. Сам этот же курс сейчас, первую часть, прохожу.
А оракл — да, не используется эта терминология совсем. Dan использует другие способы определения, PRF, PRP, итп ;)
А оракл — да, не используется эта терминология совсем. Dan использует другие способы определения, PRF, PRP, итп ;)
Тут сам объект оракула не имеет значения, имхо. Тем более что он уж сильно абстрактен. Гораздо более важно понятие «неотличимости». Криптостойкость губки рассматривается как раз-таки в статьях товарщей, разрабатывавших Keccak (ну и другие исследователи в дальнейшем похожие конструкции рассматривали).
Идея конечно чертовски красивая. Коллизии в функции сжатия говорите, да кому они вообще нужны эти функции сжатия!
Ну и стоит отдать дань уважения модели случайного оракула без нее ничего бы этого не было. Точнее было бы конечно, но без особых причин отказываться от SHA2 в пользу SHA3. Ну только если вас смущают всякие левые S-блоки 32*32 :)
Ну и стоит отдать дань уважения модели случайного оракула без нее ничего бы этого не было. Точнее было бы конечно, но без особых причин отказываться от SHA2 в пользу SHA3. Ну только если вас смущают всякие левые S-блоки 32*32 :)
Модель типа оракула сама напрашивается когда начинаешь задумываться как может выглядеть идеальный хэш. Ну во всяком случае, так кажется, когда о ней узнаешь )
В принципе да, но насколько все-таки мощный инструмент. Универсальный практически для любой области криптографии.
Это явно большой шаг для криптографии, как самостоятельной науки.
Но с другой стороны мне тоже, как ни разу не криптографу, очень сложно принимать доказательства вида, «этот протокол безопасен, пока хэш-функция неотличима от RO». И то что благодаря Keccak, у этой формулировки появилось продолжение «а эта хэш-функция неотличима от RO, т.к....» это конечно вселяет оптимизм.
Это явно большой шаг для криптографии, как самостоятельной науки.
Но с другой стороны мне тоже, как ни разу не криптографу, очень сложно принимать доказательства вида, «этот протокол безопасен, пока хэш-функция неотличима от RO». И то что благодаря Keccak, у этой формулировки появилось продолжение «а эта хэш-функция неотличима от RO, т.к....» это конечно вселяет оптимизм.
Только одно но: шех в принципе не может не давать коллизий, т.к. размер простанство возможных сообщений — на много-много-много порядков больше размера пространства возможных хешей. (Ну и про birthday paradox забывать не стоит).
Стоит говорить пожалуй о том, что максимально минимизирована «алгоритмическая часть», которая могла бы увеличить шансы на коллизию.
Стоит говорить пожалуй о том, что максимально минимизирована «алгоритмическая часть», которая могла бы увеличить шансы на коллизию.
Насколько я понял, случайный оракул для практического применения не годится. Дело не в том, что на практике даже самый чёрный ящик можно вскрыть и заглянуть в его память. Предположим, что у Алисы есть случайный оракул, а у Боба другой случайный оракул. До 1 ноября оба оракула ни разу не получали на вход строку «Хабрахабр». А 1 ноября и Боб, и Алиса скормили эту строку своим оракулам. Где гарантия, что на выходе Алиса и Боб получат одно и то же? Получается, что для того, чтобы стать похожими на реальные хэш-функции, все случайные оракулы во Вселенной должны иметь связь с каким-то единым высшим разумом. Или я что-то неправильно понял?
Вы путаете тепл^H^H^H^H абстрактную модель и реальную реализацию, а заодно и уровни где они применяются. У Боба и Алисы нет случайных оракулов, у них есть только хеш-функция. И базовое требование к любой хеш-функции — это чтобы она при одних и тех же входных данных выдавала одни и те же выходные (иначе это не хеш-функция).
А к идеальной хеш-функции предъявляется еще одно требование — чтобы для тех входных данных, которые внешний наблюдатель еще не видел проходящими через хеш-функцию, никак нельзя было предугадать результат хеш-функции. Такой способностью обладает абстрактная модель «случайный оракул». Случайный оракул в свою очередь представляется абстрактной моделью «черный ящик». Абстрактный черный ящик нельзя «вскрыть» по определению (иначе это не черный ящик). Это как бесконечность — сколько на пальцах не считай, до нее не досчитаешь, а она все равно существует.
Ну и наконец, идеальных хеш-функций нет, но чем ближе конкретная реальная функция подбирается к абстрактному идеалу — тем лучше.
А к идеальной хеш-функции предъявляется еще одно требование — чтобы для тех входных данных, которые внешний наблюдатель еще не видел проходящими через хеш-функцию, никак нельзя было предугадать результат хеш-функции. Такой способностью обладает абстрактная модель «случайный оракул». Случайный оракул в свою очередь представляется абстрактной моделью «черный ящик». Абстрактный черный ящик нельзя «вскрыть» по определению (иначе это не черный ящик). Это как бесконечность — сколько на пальцах не считай, до нее не досчитаешь, а она все равно существует.
Ну и наконец, идеальных хеш-функций нет, но чем ближе конкретная реальная функция подбирается к абстрактному идеалу — тем лучше.
И пока что никто не доказал, что можно построить функцию сжатия, устойчивую к коллизиям.
еще бы: отразить счетное множество в конечное без коллизий.
псевдослучайные перестановки, в которых коллизий не может быть по определению
ого.
будут стоять истинно случайным образом
вы употребляете выражение «истинная случайность» так, будто это не абстракция
Sign up to leave a comment.
Почему Keccak настолько крут и почему его выбрали в качестве нового SHA-3