Хабр Курсы для всех
РЕКЛАМА
Большая витрина: от крупнейших школ до частных авторов. Сравнивайте по цене, длительности, формату и выбирайте самый подходящий курс!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 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 абстрактную модель и реальную реализацию, а заодно и уровни где они применяются. У Боба и Алисы нет случайных оракулов, у них есть только хеш-функция. И базовое требование к любой хеш-функции — это чтобы она при одних и тех же входных данных выдавала одни и те же выходные (иначе это не хеш-функция).
А к идеальной хеш-функции предъявляется еще одно требование — чтобы для тех входных данных, которые внешний наблюдатель еще не видел проходящими через хеш-функцию, никак нельзя было предугадать результат хеш-функции. Такой способностью обладает абстрактная модель «случайный оракул». Случайный оракул в свою очередь представляется абстрактной моделью «черный ящик». Абстрактный черный ящик нельзя «вскрыть» по определению (иначе это не черный ящик). Это как бесконечность — сколько на пальцах не считай, до нее не досчитаешь, а она все равно существует.
Ну и наконец, идеальных хеш-функций нет, но чем ближе конкретная реальная функция подбирается к абстрактному идеалу — тем лучше.
А к идеальной хеш-функции предъявляется еще одно требование — чтобы для тех входных данных, которые внешний наблюдатель еще не видел проходящими через хеш-функцию, никак нельзя было предугадать результат хеш-функции. Такой способностью обладает абстрактная модель «случайный оракул». Случайный оракул в свою очередь представляется абстрактной моделью «черный ящик». Абстрактный черный ящик нельзя «вскрыть» по определению (иначе это не черный ящик). Это как бесконечность — сколько на пальцах не считай, до нее не досчитаешь, а она все равно существует.
Ну и наконец, идеальных хеш-функций нет, но чем ближе конкретная реальная функция подбирается к абстрактному идеалу — тем лучше.
И пока что никто не доказал, что можно построить функцию сжатия, устойчивую к коллизиям.
еще бы: отразить счетное множество в конечное без коллизий.
псевдослучайные перестановки, в которых коллизий не может быть по определению
ого.
будут стоять истинно случайным образом
вы употребляете выражение «истинная случайность» так, будто это не абстракция
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Почему Keccak настолько крут и почему его выбрали в качестве нового SHA-3