# update-rc.d [servicename] defaults

# update-rc.d [servicename] remove

День сурка:

В Древнем Риме 2 февраля отмечался День ежа[1]. Метеорологический прогноз в этот день строился по поведению разбуженного ежа, который видел или не видел свою тень. Народы Западной Европы сохраняли эту традицию и в более поздние периоды. В северной Германии в это время пробуждался барсук. Там он служил как бы весенне-зимним барометром.

А в Бельгии по весне просыпается Keccak. Тут программа праздничных мероприятий на следующую среду, приуроченных к дню Кеччака, где перед публикой выступят 3/4 его авторов. Событие обещает быть интересным, многие собираются прийти с детьми, семьями и надувными шариками.

Кто не успеет, тот опоздает.

Действительно, примечательное событие.
Там ещё и вход свободный/бесплатный (по записи), в отличие от большинства подобных мероприятий.

Я не видел конференций, где на входе бы стоял охранник и проверял пропуск,^* хотя конференционный взнос есть всегда, это общепринятая практика. Тут, конечно, не конференция, но по формату похоже. Организатор — наш коллега с другого факультета, вовлечённый в классическую криптографическую деятельность близкую к хэш-функциям. В пятницу видели человека с его отдела, который сказал, что причина регистрации — нерезиновость аудитории. Мест всего 120, и 60 человек уже зарегистрировались. Изначально планировалось выступление для более-менее внутреннего семинара, но потом решили его существенно укрупнить и пригласить больше людей/докладчиков. Понятно, что люди такого масштаба, как авторы Rijndael/Keccak, достаточно занятые, и приглашают их выступить с докладом постоянно и многие, но, тем не менее, как-то удалось организовать, выбить финансирование с фондов и оплатить приезд всех этих звёзд.

P.S. Все подъезды двери обклеены вот такой наружной рекламой. :)

^*Это касается конференций по «открытой» науке. Любой может зайти в аудиторию, сидеть и слушать доклады, а в перерывах есть печенюшки с coffee break'ов и даже сходить на банкет. Цель регистрации и оплаты взносов — официально числиться в списках, просидингсах и т.д. Если же такой цели у кого-то нет, а работает он рядом с местом проведения мероприятия, он обычно просто приходит послушать (но на банкеты не идёт, совесть не позволяет). Это стандартная практика, многие ей следуют.

Странно, что NIST так до сих пор и не выпустил официальный Secure Hash Standard (SHS) для SHA-3. Т.е. алгоритм есть — стандарта нет. Rijndael, кажется тоже, где-то полгода утверждали. Интересно, есть ли у NIST какие-то планы по стандартизации расширенных возможностей Keccak, которые к требованиям SHS вообще не относятся? Хотя это надо у НИСТа спрашивать, а не у авторов.

Если докладчики что-то скажут на этот счёт, сообщу.

Ждём от вас эксклюзивный репортаж с места события!

Постараюсь по возможности, но времени мало. К 1-ому апреля требуют черновую версию статьи на эту тему, и это не шутка. :( Времени остаётся очень мало. Возможно, отпишусь не сразу.

Тогда, конечно, занимайтесь в первую очередь подготовкой публикации. Продолжение этой темы тоже м.б. интересно для обсуждения здесь.

Советую обратить внимание на NLOS QC/QKD на UV-фотонах. Совсем нерабочая экзотика, но жутко интересно.

allow efficient secure implementations on Smart Cards applying techniques introduced in our paper Bitslice Ciphers and Power Analysis Attacks. ☭

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


Прежде, чем начинать репортаж, загадка: отгадайте, кто есть кто на картинке. Официальный репортаж висит на сайте. Для тех, у кого нет Flash-плеера, даю прямые ссылки:

• Рэйман и Даемен — авторы AES. Кто-то из них у нас когда-то давно выступал на внутреннем семинаре отдела.

• Елена Андреева, постдок из KU Лёвена. Родной язык — болгарский, но на русском с трудом изъясняется, что не может не заслуживать похвалы. Её руководитель по диссертации — Барт Пренель, бог вашего iacr'а:

  I am President of the International Association for Cryptologic Research (IACR) and Co-founder and chairman of LSEC vzw (Leuven Security Excellence Consortium).

• Жиль ван Аш и Michaël Peeters — авторы KeccaK. Первый оформил свою диссертацию как такую книгу¹, а последний со всеми любезно делится конфигом для vim'а (а говорили, что vim — не людей...).

• María Naya-Plasencia и Anne Canteaut — обе из INRIA. Анна — человек не простой:

  associate editor for the IEEE Transactions on Information Theory in "Cryptography and Complexity" (2005-2008).

  Зная, кто в этом журнале бывали редакторами по секции квантовой информации, смею предположить, что редакторы секции по криптографии — тоже современные столпы. Cудя по слайдам, она ещё и в Google работает.

• Динур и Дункельман — коллабораторы Шамира (он был соавтором их докладов).

• Christian Wenzel-Benner. Похож на BSD-шника? :)

• Башкиры на KeccaK'е. Говорить по-русски, делать диплом по KeccaK'у, администрировать FreeBSD и при этом оставаться девушкой — легко :)

• Ещё кто-то вопросы задаёт.

К счастью, на сайт выложили практически все слайды. Исключением оказалась только Андреева, поэтому я восполняю сей пробел. Кто зашёл в этот топик чисто поржать Кому лень качать и смотреть всё, можно скачать официальные смехучки² отдельно. Помимо неофициальных смехучек, я не удержался сделать ещё немного кустарных. Наконец, живое неофициальное видео никогда не заменит бездушных картинок. Порядок следования лиц на видео соответствует порядку программы за исключением того, что севшая батарейка не дала туда попасть Dinur'у, Peeters'у и Wenzel-Benner'у.

По поводу остального, что показалось интересным и запомнилось:

• Винцент Рэйман упомянул у нас уже упоминавшиеся tools. Программистам может быть интересно.

• Несколько раз произнесли во время докладов слово «матрёшка». К чему она там, правда, не понял, мозги были отключены. Вообще, доклады по криптоанализу тяжело слушать, хотя докладчики старались рассказывать понятно. Отметил для себя, что все очень часто говорили про Merkle-Damgård'а³ (MD). По-видимому, это одно из самых базовых понятий. В тексте новости про них unknown тоже упомянул.

• SHA-3 произносится не как «эс-эш-а три», а как «ша-три» (впрочем, оно логично), чему я был несколько удивлён.

• KeccaK не свалился внезапно на голову и ведёт свою историю ещё с идей 90-ых (Даемен?), потом был RadioGatún — якобы наследник тех идей, и только в финальном виде оно превратилось в то, что сейчас известно, как KeccaK. Об этом, кстати, есть в том куске видео, где Жиль рассказывает.

• Christian Wenzel-Benner в конце дня рассказывал про вопросы бенчмаркинга и имплементации KeccaK во всяких схемах. Местной публике может быть интересно, потому призываю полистать его слайды. Там сказано, что SHA-3 прекрасно работает на ASIC'ах и XBX (см. начиная со стр. 33). В частности, во время его доклада я услышал мельком упомянутую NetBSD⁴. Суть вот в чём: они делают имплементации и бенчмарки для хэш-функций на микроконтроллерах и специализированном железе. Полноценную ОС туда не поставить, поэтому код должен быть скомпилирован заранее на другой системе под эту платформу. Для кросскомпиляции использовали NetBSD. Код по бенчамаркам для XBX они выложили в открытый доступ, можно полистать сайт. Упоминания NetBSD, правда, там не нашёл, но FreeBSD один раз упомянута.

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

---

¹Там есть неплохое введение в QKD для классических криптографов.
²Что касается смехучек официальных, про танец (стр. 2) не мы первые заметили. На стр. 3 показано, кто откуда посылал заявки на приём своего алгоритма в качестве SHA-3. На стр. 4 стрелки показывано, как отправившие заявки исследователи начали ломать чужие хэши. Прям взрыв такой получился. :)
³Движок совсем не хочет вставлять ссылку на вики на MD-construction, ни один костыль не срабатывает. :(
⁴Подумал, что послышалось. Подошёл после доклада, уточнил. Нет, не послышалось.

На его вариантах построены предыдущие SHA, MD5 и куча всего. Хотя эту конструкцию в практическом смысле можно хоронить, она ещё имеет теоретическое значение как для сравнительного, так и для оценочного анализа новых хэшей и даже блочных шифров. Грубо говоря, можно не ломать какой-то новый блочный шифр непосредственно, а загнать в Дамгарда-Меркла и посмотреть по различителям, насколько кривой хэш из него получится.

Матрёшка упоминалась в работах про Keccak. Не помню, что это за понятие, надо будет пересмотреть.

SHA-3 произносится не как «эс-эш-а три», а как «ша-три» (впрочем, оно логично), чему я был несколько удивлён

Это потому что вам ещё «ша-уан» все уши не прожужжал :)

KeccaK не свалился внезапно на голову и ведёт свою историю ещё с идей 90-ых (Даемен?)

Также как и до Rijndael были сначала 3-Way и BaseKing, затем Square. Конструкцию Sponge вроде вообще, кажется, не эти авторы изобрели и многие её сначала критиковали, как неэффективный и непрактичный способ криптопреобразования (типа "не взлетит").

Сказали, что кеччак и саму функцию НИСТ стандартизирует независимо.

Круто. Они могут сделать стандарт на SHA-3 по условиям конкурса, а затем стандартизировать все дополнительные возможности по универсализации Keccak, как я и предполагал.

Суть вот в чём: они делают имплементации и бенчмарки для хэш-функций на микроконтроллерах и специализированном железе.

Для этой цели специально ещё наизобретали облегчённые варианты губчатых хэшей: QUARK, PHOTON, SPONGENT, облегчённый вариант самого KeccaK.

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

А также в анонимности, стеганографии, теоретической и прикладной математике… Причём те, у кого реально сильные и новаторские работы. Скоро придёться вводить слово "основоположница" :)

---

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

Присоединяюсь к благодарностям нашему внештатному корреспонденту (к слову, это не он ли там на заключительном фото задавал вопросы?). :)

аааа-ааа-а! :) ))

Спасибо, интересно очень.

Круто. Они могут сделать стандарт на SHA-3 по условиям конкурса, а затем стандартизировать все дополнительные возможности по универсализации Keccak, как я и предполагал.

Инетересно бы глянуть на производительность в режиме потокового шифра.

Производительность — как у медленных блочных шифров. Т.е. скорее всего — не очень. Например, медленнее, чем AES-CTR.

---

Range of 7 permutations, from small to large. Matryoshka structure

Matryoshka structure The analysis of small versions is relevant for larger versions (see Section 6.2).

6.2 The Matryoshka structure. With the exception of ι, all step mappings of the Keccak-f round function are translation-invariant in the direction of the z axis. This allows the introduction of a size parameter that can easily be varied without having to re-specify the step mappings. As in several types of analysis abstraction can be made of the addition of constants, this allows the re-use of structures for small width versions to symmetric structures for large width versions. We refer to Section 6.5.2 for an example. As the allowed lane lengths are all powers of two, every smaller lane length divides a larger lane length. So, as the propagation structures for smaller width version are embedded as symmetric structure in larger width versions, we call it Matryoshka, after the well-known Russian dolls.

© Keccak sponge function family main document. Guido Bertoni, Joan Daemen, MichaeЁl Peeters, Gilles Van Assche.

А матрёшка — это способ масштабирования (задания разных размеров) перестановок для внутреннего состояния.