Введение
Потоковый шифр Py — это потоковый шифр, представленный в eSTREAM Эли Бихамом и Дженнифер Себерри. Он является одним из самых быстрых кандидатов в eSTREAM, демонстрируя скорость около 2,6 циклов на байт на некоторых платформах. Его структура немного напоминает RC4, но включает массив из 260 32-битных слов, индексируемых с помощью перестановки байтов, и генерирует 64 бита в каждом раунде. Авторы утверждают, что название следует произносить как "Roo", ссылаясь на австралийское происхождение шифра, читая буквы "Py" как кириллицу (Ру), а не как латинские символы. Это несколько причудливое произношение, как считается, является их шутливым ответом на сложное произношение имени 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 is a stream cipher submitted to eSTREAM by Eli Biham and Jennifer Seberry. It is one of the fastest eSTREAM candidates at around 2.6 cycles per byte on some platforms. It has a structure a little like RC4, but adds an array of 260 32 bit words which are indexed using a permutation of bytes, and produces 64 bits in each round. The authors assert that the name be pronounced "Roo", a reference to the cipher's Australian origin, by reading the letters "Py" as Cyrillic (Ру) rather than Latin characters. This somewhat perverse pronunciation is understood to be their answer, in jest, to the difficult to pronounce name Rijndael for the cipher which was adopted as the Advanced Encryption Standard. The original April 2005 proposal included the cipher Py, and a simplified version Py6. The latter reduces the size of some internal tables, providing greatly reduced key scheduling cost, at the expense of a shorter maximum output length. In June 2006, the authors described Pypy (even more confusingly, half Cyrillic Pyру and thus pronounced "Pyroo") as an optional stronger variant. This omits one of the output words from each iteration of Py, and thus operates at slightly over half the speed of Py. (Actually about 0.6×.) In January 2007, the key schedule algorithm was changed, producing "tweaked" variants TPy, TPypy and TPy6. To be precise, the first (key dependent) phase is unmodified, but the second (IV setup) phase has an error corrected. The round functions used to produce output are identical. At Indocrypt 2007, Gautham Sekar, Souradyuti Paul and Bart Preneel proposed two new ciphers RCR 32 and RCR 64 based on the design principles of Pypy and Py, respectively. These replace a variable rotate in Py with a fixed rotate, eliminating an attack and speeding up the cipher slightly. The TPy key schedule is used unmodified.
Нападения на семейство Py
На 2006 год лучшая криптоаналитическая атака на Py (Хунджун Ву и Барт Пренел) при определенных обстоятельствах (например, когда IV значительно длиннее ключа) может восстановить ключ, имея частичные ключевые потоки для 224 выбранных IV. В более сложном для атакующего сценарии, при наличии только известного открытого текста (а не выбранного), существует также различающая атака на ключевой поток (Пола Кроули), требующая около 272 байтов выходных данных и сопоставимого времени. Это улучшение по сравнению с атакой, представленной Гаутамом Секаром, Сурадьюти Полом и Бартом Пренелем, которая требует 288 байтов. Продолжаются споры о том, представляют ли эти атаки собой академический взлом Py. В то время как атакующие утверждают, что вышеуказанные атаки могут быть реализованы с меньшей вычислительной нагрузкой, чем полный перебор в соответствии с конструктивными спецификациями Py, и, следовательно, это явный теоретический взлом шифра, разработчики отвергают эти атаки, поскольку ограничения безопасности Py ограничивают любого атакующего общим объемом 264 байта выходных данных во всех ключевых потоках. Недавняя редакция статьи Пола, Пренеля и Секара содержит подробное обсуждение этого вопроса в разделе 9. Нет сомнений в обоснованности атаки Ву и Пренеля. Py был выбран в качестве кандидата на фазу 2 для профиля 1 (программного обеспечения) в проекте eSTREAM, но не перешел в фазу 3 из-за выбранной IV-атаки Ву и Пренеля. В январе 2007 года разработчики Py предложили три новых шифра: TPy, TPypy и TPy6, чтобы устранить вышеуказанные атаки. TPy все еще уязвим для вышеупомянутых различающих атак Paul et al. (сложность 288) и Кроули (сложность 272), которые не зависят от схемы генерации ключей. Лучшая на сегодняшний день атака на TPypy, который считается самым надежным из семейства шифров Py, принадлежит Sekar et al. и представляет собой различающую атаку со сложностью по объему данных 2281. Эта атака имеет смысл только в том случае, если размер ключа TPypy превышает 281 бит. Для устранения атак на TPy и TPypy, Секар, Пол и Пренел на Indocrypt 2007 представили предложения по двум новым шифрам: RCR 32 и RCR 64. На данный момент не существует атак на RCR 32 и RCR 64.
In a more difficult scenario from the point of view of attacker, given only known plaintext (rather than chosen plaintext), there is also a distinguishing attack on the keystream (by Paul Crowley) which requires around 272 bytes of output and comparable time. This is an improvement on an attack presented by Gautham Sekar, Souradyuti Paul and Bart Preneel which requires 288 bytes. There is a still a debate whether these attacks constitute an academic break of Py. When the attackers claim that the above attacks can be built with workload less than the exhaustive search under the design specifications of Py and therefore, it is clearly a theoretical break of the cipher, the designers rule out the attacks because Py's security bounds limit any attacker to a total of 264 bytes of output across all keystreams everywhere. A recent revision of the Paul, Preneel, and Sekar paper includes a detailed discussion of this issue in section 9. There are no doubts about the legitimacy of the Wu and Preneel attack. Py was selected as Phase 2 Focus Candidate for Profile 1 (software) by the eSTREAM project but did not advance to Phase 3 due to the Wu and Preneel chosen IV attack. In January 2007, three new ciphers namely TPy, TPypy and TPy6 have been proposed by the designers of Py to eliminate the above attacks. The TPy is still vulnerable against the above distinguishing attacks by Paul et al. (complexity 288) and Crowley (complexity 272), which do not depend on the key schedule. The best attack so far on the TPypy, which is conjectured to be the strongest of the Py family of ciphers, is by Sekar et al. which is a distinguishing attack with data complexity 2281. This attack is only meaningful if the key size of TPypy is longer than 281 bits. To remove attacks on TPy and TPypy, Sekar, Paul and Preneel at Indocrypt 2007 gave proposals for two new ciphers RCR 32 and RCR 64. So far there are no attacks against the RCR 32 and RCR 64.