Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 41
Только одна мысль — «как они это делают?»
Это также просто, как сидеть в контакте. Нужно только захотеть.
В своё время мы обсуждали это с Димой Скляровым из элкомсофта и пришли к следующему мнению. Есть три функции — XOR, ADD и циклические сдвиги (wtf you name it), комбинация любых двух-трёх из которых вроде как не может быть обращена быстрее чем брутфорсом. Ну, попробуйте вычислить A, обратив формулу Y = ( (A ADD B) XOR C ) (n раз) по известным n, Y, B и C.
Суть всех современных гражданских алгоритмов в том, что пихаем побольше циклов над этими функциями и местами размазываем глубокомудрыми константами, и вот он — профит! Главное — нигде не облажаться (такое на самом деле очень часто бывает).
Однако, есть мнение (с), что всё-таки существует на порядки более эффективный, чем полный перебор, обратный алгоритм. Он не настолько эффективен, чтобы подделывать хэши и расшифровывать криптосообщения на обычном компе, но достаточно быстр, чтобы местная гэбня могла всё это сделать за почти-реальное время на топовом суперкомпьютере. Остюда, кстати, происходит и рост «разрядности» всех гражданских алгоритмов с относительно недавних 56 битов DES до вот уже 512 бит последних стандартов. Хотя полный перебор что 256, что тем более 2256 вариантов на обычном компьютере всё ещё в области фантастики.
Серьезные же организации (типа военных) используют алгоритмы на эллиптических кривых (здесь три раза «Ку» товарищу Колмогорову и его последователям). Но эскпорт этих алгоритмов до сих пор строжайше запрещен из всех стран, где эти самые последователи Колмогорова имеют место жить.
Суть всех современных гражданских алгоритмов в том, что пихаем побольше циклов над этими функциями и местами размазываем глубокомудрыми константами, и вот он — профит! Главное — нигде не облажаться (такое на самом деле очень часто бывает).
Однако, есть мнение (с), что всё-таки существует на порядки более эффективный, чем полный перебор, обратный алгоритм. Он не настолько эффективен, чтобы подделывать хэши и расшифровывать криптосообщения на обычном компе, но достаточно быстр, чтобы местная гэбня могла всё это сделать за почти-реальное время на топовом суперкомпьютере. Остюда, кстати, происходит и рост «разрядности» всех гражданских алгоритмов с относительно недавних 56 битов DES до вот уже 512 бит последних стандартов. Хотя полный перебор что 256, что тем более 2256 вариантов на обычном компьютере всё ещё в области фантастики.
Серьезные же организации (типа военных) используют алгоритмы на эллиптических кривых (здесь три раза «Ку» товарищу Колмогорову и его последователям). Но эскпорт этих алгоритмов до сих пор строжайше запрещен из всех стран, где эти самые последователи Колмогорова имеют место жить.
Но эскпорт этих алгоритмов до сих пор строжайше запрещен из всех стран, где эти самые последователи Колмогорова имеют место жить.
Поясните, что именно, откуда и куда запрещено экспортировать.
А то вот я тут в SSH ключик ecdsa уже года полтора успешно использую.
А, простите, в какой «серьезной» организации используется ecdsa?
То, что маркетологи от ИТ проехались по мозгам людей-не-в-теме и рассказали им про преимущества эллиптических кривых еще не значит, что эти самые маркетологи способны/им позволено эту самую эллиптику грамотно реализовать. Или что появятся какие-то математики-любители, которые смогут нигде не ошибиться и их при этом не вызовут на беседу.
По первой части вопроса — ну попробуйте «экспортировать» военную эллиптику из России или там США :) Ну ладно, даже не экспортировать, просто оформить форму допуска, чтобы узнать детали.
Ну или хотя бы импортировать циску с криптомодулем.
То, что маркетологи от ИТ проехались по мозгам людей-не-в-теме и рассказали им про преимущества эллиптических кривых еще не значит, что эти самые маркетологи способны/им позволено эту самую эллиптику грамотно реализовать. Или что появятся какие-то математики-любители, которые смогут нигде не ошибиться и их при этом не вызовут на беседу.
По первой части вопроса — ну попробуйте «экспортировать» военную эллиптику из России или там США :) Ну ладно, даже не экспортировать, просто оформить форму допуска, чтобы узнать детали.
Ну или хотя бы импортировать циску с криптомодулем.
Теория заговора? Я такое люблю!
Как объясните то, что на каждом углу нынче вон ЭЦП внедряется, вполне себе гражданское и очень даже на эллиптических кривых?
Как объясните то, что на каждом углу нынче вон ЭЦП внедряется, вполне себе гражданское и очень даже на эллиптических кривых?
ЭЦП на каждом углу? Это который по ГОСТу 34.10-2001? Так оно ж разработано гэбнёй из фапси на той самой эллиптике.
Там если и есть закладки, то это наши, правильные закладки!
Там если и есть закладки, то это наши, правильные закладки!
Ну я вот об этом вообще-то.
Циску нет, но товарищ вам правильно указал на ecdsa. То что вы не доверяете реализации вполне нормально, но это не делает ее автоматически хуже мифической «военной».
Или что появятся какие-то математики-любители, которые смогут нигде не ошибиться и их при этом не вызовут на беседу.
А как насчет нелюбителей?
То-то фбр позорится и у любителей помощи просит в расшифровке винчестеров преступников, а в Англиях законы принимают об обязанности сообщить пароль к своей зашифрованной информацией, это все чтоб к военным и к гэбне не ходить вестимо.
Что значит «экспорт алгоритмов»? В современном мире это понятие осталось в закостенелых умах генералов и законописцев. Нет больше никакого экспорта алгоритмов. Алгоритм либо общеизвестен (информация доступна), либо засекречен (информация недоступна). Передать сейчас информацию через границу в любое государство минуя все надзорные органы не проблема. Что запрещаем тогда?
А запрещаем экспорт/импорт устройств, реализующих алгоритмы, которые реализовывать нельзя (но они при этом общеизвестны). Это ограничение появилось в до-ЭВМ эпоху, когда шифровальные системы представляли из себя законченное аппаратное решение и только в этом смысле формулировка целесообразна.
Когда же появились вычислительные машины общего назначения, это ограничение попытались завязать и на них — это лишь вопрос идиотизма соответствующих ведомств, но никак не реального положения дел.
А запрещаем экспорт/импорт устройств, реализующих алгоритмы, которые реализовывать нельзя (но они при этом общеизвестны). Это ограничение появилось в до-ЭВМ эпоху, когда шифровальные системы представляли из себя законченное аппаратное решение и только в этом смысле формулировка целесообразна.
Когда же появились вычислительные машины общего назначения, это ограничение попытались завязать и на них — это лишь вопрос идиотизма соответствующих ведомств, но никак не реального положения дел.
Код на C# присутствует. Не Паскаль, но тоже вполне читаемый. Правда настораживает обилие конвертаций строка-число (в код не вчитывался, просто настораживает).
Я псевдокод слизал с сайта Keccak. Сейчас немного подправил, надеюсь стало понятнее.
>Или говоря по-русски, к сообщению дописывается единичный байт, необходимое количество нулей и весь этот ансамбль завершает байт со значением 0x80.
Если 2х байт не хватает, то дописать надо 0x01 и 0x80, верно?
А если одного байта не хватает, 0x01 или 0x80?
Если 2х байт не хватает, то дописать надо 0x01 и 0x80, верно?
А если одного байта не хватает, 0x01 или 0x80?
Видимо дополняется ещё 500 там с чем то (искать лень вверху) — 1 нулём. Т.е. 5xx-1
Судя по коду на C#
Всегда дописывается 0x01 к сообщению. А затем необходимое количество 0x00, чтобы (сообщение+1) стало кратным r и затем дописывается 0x80.
Таким образом, если не хватает одного байта, дописаны будут (r/8)+1 байт, если 2х то (r/8)+2 байт, а если сообщение уже кратно r то дописаны будут r/8 байт.
Всегда дописывается 0x01 к сообщению. А затем необходимое количество 0x00, чтобы (сообщение+1) стало кратным r и затем дописывается 0x80.
Таким образом, если не хватает одного байта, дописаны будут (r/8)+1 байт, если 2х то (r/8)+2 байт, а если сообщение уже кратно r то дописаны будут r/8 байт.
Минимальное количество добавляемых байт-2. Максимальное r+8. Т.е. если не хватает 2-ух байт будут добавлены 01 и 80.
Если не хватает одного байта будут дописаны 01, r-8 нулей и 80.
Если не хватает одного байта будут дописаны 01, r-8 нулей и 80.
надеюсь воскресный вечер у Вас будет более удачным ))
Статья то интересная. Но где инфа о равномерности распределения? Криптостойкости? Чем эта функция так хороша, что её приняли в качестве нового стандарта? Длинна хеша не удивила, значит вкусность в другом.
Да это несомненно интересно. Но я не ставил перед собой цель сделать полный анализ хеш-функции. Я просто хотел разобраться как она реализована.
Так что всех подробностей я не знаю, но если кратко основная вкусность в том, что Keccak не использует функцию сжатия, в отличие от Sha-2 или Sha-1. Вместо функции сжатия используется псевдослучайная перестановка, собственно Sponge.
Это позволяет свести скойкость Keccak к модели случайного оракула.Т.е. создателям удалось постоить даказательство неразличимости Keccak от случайного оракула. И это в свою очередь позволяет говорить о Keccak, не просто как о хеш-функции, но как об универсальном криптопримитиве. Т.е. Без всяких дополнительных костылей Keccak можно использовать и для генерации псевдослучайного потока, и для вычисления MAC и для генерации ключей.
Так что всех подробностей я не знаю, но если кратко основная вкусность в том, что Keccak не использует функцию сжатия, в отличие от Sha-2 или Sha-1. Вместо функции сжатия используется псевдослучайная перестановка, собственно Sponge.
Это позволяет свести скойкость Keccak к модели случайного оракула.Т.е. создателям удалось постоить даказательство неразличимости Keccak от случайного оракула. И это в свою очередь позволяет говорить о Keccak, не просто как о хеш-функции, но как об универсальном криптопримитиве. Т.е. Без всяких дополнительных костылей Keccak можно использовать и для генерации псевдослучайного потока, и для вычисления MAC и для генерации ключей.
Можно вот эту ссылку добавить.
А как это произносится?
«Кечак» читается. Некоторые умудряются писать «кетчак», не осознавая, что [tʃ] — это [ч], и никакого «т» там в помине нет.
Это не вполне так. Русское «ч» произносится как [t͡ɕ], то есть глухая переднеязычная аффриката, а [t͡ʃ] является глухой постальвеолярной аффрикатой, так что «т» там в помине, но есть, по крайней мере в русской транскрипции.
«Cc» в данном случае восходит к итальянскому орфо-фонетическому менталитету создателей алгоритма, а это как раз [t͡ʃ], и на русский долгое итальянское «ч» передаётся традиционно как «чч» (Мартуччи, Феруччо, Пуччини, Уччелини), так что было бы верно писать либо как «Кеччак», в пользу итальянской традиции, или «Кетчак», в пользу английской (Бутч, матч, скотч, и протч.)
«Cc» в данном случае восходит к итальянскому орфо-фонетическому менталитету создателей алгоритма, а это как раз [t͡ʃ], и на русский долгое итальянское «ч» передаётся традиционно как «чч» (Мартуччи, Феруччо, Пуччини, Уччелини), так что было бы верно писать либо как «Кеччак», в пользу итальянской традиции, или «Кетчак», в пользу английской (Бутч, матч, скотч, и протч.)
на РНР, я так понял, никто еще не написал реализацию? Даже на Питоне на сайте лежит реализация 3.0, хотя описана версия 3.2. Чё-то медленно взлетает.
Кто мешает? Деразайте!
Для php есть расширение: github.com/archwisp/php-keccak-hash
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Keccak, новый стандарт хеширования данных