Пи (шифр)

Py — это поточный шифр, представленный на eSTREAM и Эли Бихамом Дженнифер Себерри . Это один из самых быстрых кандидатов eSTREAM со скоростью около 2,6 тактов на байт на некоторых платформах. Он имеет структуру, немного похожую на RC4 , но добавляет массив из 260 32-битных слов, которые индексируются с использованием перестановки байтов, и производит 64 бита в каждом раунде.

Авторы утверждают, что имя произносится как «Ру», что является отсылкой к австралийскому происхождению шифра, если буквы «Пи» читать как кириллицу (Ру), а не латинские символы. Это несколько извращенное произношение понимается как шуточный ответ на труднопроизносимое имя Rijndael для шифра, который был принят в качестве расширенного стандарта шифрования .

• Первоначальное предложение от апреля 2005 года включало шифр Py и упрощенную версию Py6. Последнее уменьшает размер некоторых внутренних таблиц, обеспечивая значительное снижение затрат на планирование ключей за счет более короткой максимальной длины выходных данных.
• В июне 2006 года авторы описали Pypy (еще более запутанно: наполовину кириллический Pyру и, таким образом, произносится как «Pyroo») как необязательный, более сильный вариант. При этом одно из выходных слов исключается из каждой итерации Py и, таким образом, работает чуть более чем вдвое быстрее, чем Py. (На самом деле около 0,6 ×.)
• В январе 2007 года алгоритм расписания ключей был изменен, в результате чего были созданы «доработанные» варианты TPy, TPypy и TPy6. Точнее, первая (зависимая от ключа) фаза не изменяется, но во второй фазе (IV-настройка) исправлена ​​ошибка. Функции округления, используемые для получения вывода, идентичны.
• На Indocrypt 2007 Гаутам Секар , Сурадьюти Пол и Барт Пренил предложили два новых шифра RCR-32 и RCR-64, основанные на принципах проектирования Pypy и Py соответственно. Они заменяют переменное вращение в Py фиксированным вращением, устраняя атаку и немного ускоряя шифрование. Расписание ключей TPy используется без изменений.

Атаки на семейство Py

По состоянию на 2006 год , лучшая криптоаналитическая атака на Py ( Хунджун Ву и Барт Пренил ) может при некоторых обстоятельствах (например, когда IV намного длиннее ключа) восстановить ключ с учетом частичных потоков ключей для 2 ²⁴ выбранные IV [1] .

В более сложном сценарии с точки зрения злоумышленника, учитывая только известный открытый текст (а не выбранный открытый текст), существует также различительная атака на ключевой поток ( Пола Кроули ), которая требует около 2 ⁷² байт вывода и сопоставимое время. Это улучшение атаки, представленной Гаутамом Секаром , Сурадьюти Полом и Бартом Пренилом , для которого требуется 2 ⁸⁸ байты. До сих пор ведутся споры о том, являются ли эти атаки академическим прорывом Пая. Когда злоумышленники заявляют, что описанные выше атаки могут быть построены с рабочей нагрузкой меньшей, чем исчерпывающий поиск в соответствии со спецификациями проекта Py, и, следовательно, это явно теоретический взлом шифра, разработчики исключают атаки, поскольку границы безопасности Py ограничивают любого злоумышленника. в общей сложности 2 ⁶⁴ байт вывода по всем ключевым потокам повсюду. Недавняя редакция статьи Пола , Пренеля и Секара включает подробное обсуждение этого вопроса в разделе 9. Нет никаких сомнений в легитимности атаки Ву и Пренеля.

Py был выбран в качестве фокусного кандидата для фазы 2 для профиля 1 (программное обеспечение) проектом [ eSTREAM 2] , но не прошел в фазу 3 из-за атаки IV, выбранной Ву и Пренилом. [3] .

В январе 2007 года разработчики Py предложили три новых шифра, а именно TPy, TPypy и TPy6, для устранения вышеупомянутых атак. TPy по-прежнему уязвим перед вышеупомянутыми отличительными атаками Пола и др. (сложность 2 ⁸⁸ ) и Кроули (сложность 2 ⁷² ), которые не зависят от ключевого расписания. На данный момент лучшая атака на TPypy, который считается самым сильным из шифров семейства Py, принадлежит Sekar et al. это отличительная атака со сложностью данных 2 ²⁸¹ . Эта атака имеет смысл только в том случае, если размер ключа TPypy превышает 281 бит.

Для устранения атак на TPy и TPypy Секар , Пол и Пренел на Indocrypt 2007 представили предложения по двум новым шифрам RCR-32 и RCR-64 . пока нет Нападений на RCR-32 и RCR-64 .

Раундовые функции

Py основан на идее «скользящих массивов»: массивы индексируются относительно начального указателя, который каждый раунд перемещается на одно слово. Там, где доступна индексация по модулю (аппаратное обеспечение и многие процессоры цифровых сигналов ), ее можно реализовать в виде кольцевых буферов . В программном обеспечении их проще всего реализовать в виде больших массивов. При достижении конца массива рабочие части копируются обратно в начало и операции продолжаются.

Массив P размером 256 байт содержит перестановку из 256 записей (каждый байт появляется ровно один раз), а массив Y содержит 260 32-битных слов.

#include <stdint.h>#define ROTL32(x, s) ((x)<<(s) | (x)>>(32-(s)))uint8_t  *P;    // P[0] through P[255] are activeuint32_t *Y;    // Y[-3] through Y[256] are activeuint32_t s;uint32_t *output;while (output_words--) {        int i = Y[185] % 256;        P[256] = P[i];     // This effectively swaps P[0] and P[i]        P[i] = P[0];       // Then copies P[0] to P[256]        P++;  // Prior P[1] is new P[0], just-written P[256] is new P[255]        s += Y[P[72]] - Y[P[239]];        s = ROTL32(s, (P[116] + 18) % 32);        *output++ = (ROTL32(s, 25) ^ Y[256]) + Y[P[26]];  // This line omitted from Pypy & TPypy        *output++ = (       s      ^ Y[-1] ) + Y[P[208]];        Y[257]    = (ROTL32(s, 14) ^ Y[-3] ) + Y[P[153]];        Y++;  // Prior P[-2] is new P[-3], just-written P[257] is new P[256]}

Когда требуется вывод байтов, Py указывает, что выходные слова преобразуются с прямым порядком байтов.

Строка 17 опущена в Pypy, Tpypy и RCR-32.

RCR-32 и RCR-64 идентичны описанным выше, за исключением того, что строка 15 заменена на фиксированный поворот влево на 19 бит.

Py6 имеет ту же структуру, но массивы P и Y сокращены до 64 байтов и 68 слов соответственно. Записи P имеют длину всего 6 бит, и эта экономия может быть использована на специализированном оборудовании. Различные смещения в P[] и Y[] конечно, изменяются, образуя внутренний цикл:

while (output_words--) {        int i = Y[43] % 64;        P[64] = P[i];        P[i] = P[0];        P++;        s += Y[P[18]] - Y[P[57]];        s = ROTL32(s, (P[26] + 18) % 32);        *output++ = (ROTL32(s, 25) ^ Y[64]) + Y[P[8]];        *output++ = (       s      ^ Y[-1]) + Y[P[21]];        Y[65]     = (ROTL32(s, 14) ^ Y[-3]) + Y[P[48]];        Y++;}

Внешние ссылки

• Эли Бихам , Дженнифер Себерри , спецификация Py ( PostScript )
• Эли Бихам , Дженнифер Себерри , Настройка IV семейства потоковых шифров Py — шифры TPy, TPypy и TPy6
• Страница eStream на Py
• Пол Кроули , Криптоанализ Py
• Сурадьюти Пол , Барт Пренил , Гаутам Секар , Отличительные атаки на поточный шифр Py , FSE 2006.
• Гаутам Секар , Сурадьюти Пол , Барт Пренил , Слабые стороны алгоритмов генерации псевдослучайных битов потоковых шифров TPypy и TPy , отчет IACR-ePrint.
• Сурадьюти Пол , Барт Пренил , О (не)безопасности потоковых шифров на основе массивов и модульного сложения (полная версия) , Asicrypt 2006.
• Гаутам Секар , Сурадьюти Пол , Барт Пренил , Атаки со связанными ключами на семейство шифров Py и подход к устранению слабых мест , Indocrypt 2007.
• Страница Rijndael — «Часто задаваемые вопросы о Rijndael» слегка пародируется в Приложении B спецификации Py.