Меню Главная Случайная статья Настройки Present (шифр) Материал из https://ru.wikipedia.org Present — блочный шифр с размером блока 64 бита, длиной ключа 80 или 128 бит и количеством раундов 32. Основное назначение данного шифра — использование в узкоспециализированных приборах, наподобие RFID-меток или сетей сенсоров. Является одним из самых компактных криптоалгоритмов: существует оценка, что для аппаратной реализации PRESENT требуется приблизительно в 2,5 раза меньше логических элементов чем для AES или CLEFIA[1][2]. Данный шифр был представлен на конференции CHES 2007. Авторы: Богданов, Кнудсен, Леандр, Паар, Пошманн, Робшо, Соа, Викельсоа. Авторы работают в Orange Labs, Рурском университете в Бохуме и Датском техническом университете. Содержание 1 Схема шифрования 1.1 S-layer 1.2 P-layer 1.3 Key schedule 2 Криптоустойчивость 2.1 Дифференциальный криптоанализ 2.2 Линейный криптоанализ 2.3 Другие методы 3 Сравнение с другими шифрами 4 Применение 5 Примечания 6 Ссылки Схема шифрования Основным критерием при разработке шифра была простота реализации при обеспечении средних показателей защищенности. Также важным моментом была возможность эффективной аппаратной реализации. Представляет собой SP-сеть с 31 раундом шифрования. Каждый раунд состоит из операции XOR с раундовым ключом ${\displaystyle K_{i}}$, состоящим из 64 бит, определяемых функцией обновления ключа. Далее производится рассеивающее преобразование — блок пропускается через 16 одинаковых 4-битных S-блоков. Затем блок подвергается перемешивающему преобразованию (перестановке бит)[3]. S-layer В шифре используются 16 одинаковых 4-битных S-блоков: x 0 1 2 3 4 5 6 7 8 9 A B C D E F S[x] C 5 6 B 9 0 A D 3 E F 8 4 7 1 2 S-box составлена таким образом, чтобы увеличить сопротивляемость линейному и дифференциальному криптоанализу. В частности: ${\displaystyle P(\forall x\in [0,F]:S(x)+S(x+\Delta _{i})=\Delta _{o})<=4}$, где ${\displaystyle \Delta _{i},\Delta _{o}}$ — любые возможные входные и выходные дифференциалы не равные 0. ${\displaystyle P(\forall x\in [0,F]:S(x)+S(x+\Delta _{i})=\Delta _{o})=0}$, где ${\displaystyle wt(\Delta _{i})=wt(\Delta _{o})=1}$. P-layer Блок, перемешивающий биты, задан следующей матрицей: i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 P(i) 0 16 32 48 1 17 33 49 2 18 34 50 3 19 35 51 i 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 P(i) 4 20 36 52 5 21 37 53 6 22 38 54 7 23 39 55 i 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 P(i) 8 24 40 56 9 25 41 57 10 26 42 58 11 27 43 59 i 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 P(i) 12 28 44 60 13 29 45 61 14 30 46 62 15 31 47 63 Key schedule В качестве раундового ключа ${\displaystyle K_{i}}$ используются 64 левых бит из регистра ${\displaystyle K}$, содержащего весь ключ. После получения раундового ключа регистр ${\displaystyle K}$ обновляется по следующему алгоритму: ${\displaystyle [k_{79}k_{78}...k_{1}k_{0}]=[k_{18}k_{17}...k_{20}k_{19}]}$ ${\displaystyle [k_{79}k_{78}k_{77}k_{76}]=S[k_{79}k_{78}k_{77}k_{76}]}$ ${\displaystyle [k_{19}k_{18}k_{17}k_{16}k_{15}]=[k_{19}k_{18}k_{17}k_{16}k_{15}]\oplus }$round_counter Криптоустойчивость Дифференциальный криптоанализ Данный шифр обладает свойством, что любая 5-раундовая дифференциальная характеристика затрагивает по меньшей мере 10 S-box`ов. Таким образом, например, для 25 раундов шифра будут задействованы как минимум 50 S-box, и вероятность характеристики не превышает ${\displaystyle 2^{-100}}$. Атака на версии шифра с 16 раундами шифрования требует ${\displaystyle 2^{64}}$ шифротекстов, ${\displaystyle 2^{64}}$ доступов к памяти, ${\displaystyle 2^{32}}$ 6-битных счетчиков и ${\displaystyle 2^{24}}$ ячеек памяти для хеш-таблицы. Вероятность нахождения ключа ${\displaystyle P\approx 0.999}$ Линейный криптоанализ Максимальный наклон аппроксимированной прямой для 4 раундов не превышает ${\displaystyle {\frac {1}{2^{7}}}}$. Таким образом, для 28 раундов максимальный наклон будет ${\displaystyle 2^{6}*{({\frac {1}{2^{7}}})^{7}}=2^{-43}}$. Поэтому, если учесть, что для взлома 31 раунда необходима аппроксимация для 28, то понадобится ${\displaystyle 2^{84}}$ известных пар текст-шифротекст, что превышает размер возможного теста для шифрования. Другие методы Алгебраическая атака с использованием дифференциальных характеристик. Основная идея — представить шифр системой уравнений низкого порядка. Далее, для нескольких пар текст-шифротекст соответствующие им системы уравнений объединяются. Если в качестве этих пар выбрать пары, соответствующие некоторой характеристике ${\displaystyle \delta }$ с вероятностью p, то система будет верна с этой вероятностью p и решения может быть найдено при использовании ${\displaystyle {\frac {1}{p}}}$ пар. Ожидается, что решение такой системы проще, чем изначальной, соответствующей одной паре текст-шифротекст. Для Present-80 с 16 раундами данная атака позволяет узнать 4 бита ключа за ${\displaystyle \approx 6*2^{12}}$ секунд. Метод статистического насыщения. В данной атаке используются недостатки блока перемешивания бит. Для взлома Present-80 с 24 раундами требуется пар текст-шифротекст ${\displaystyle \approx 2^{60}}$ вычислений ${\displaystyle \approx 2^{20}}$. Сравнение с другими шифрами В таблице ниже приведена сравнительная характеристика шифра Present-80[4] по отношению к другим блочным и потоковым шифрам[5]: Название Размер ключа Размер блока Пропускная способность(Kpbs) Площадь (в GE) Present-80 80 64 11.7 1075 AES-128 128 128 12.4 3400 Camelia 128 128 640 11350 DES 56 64 44.4 2309 DESXL 184 64 44.4 2168 Trivium 80 1 100 2599 Grain 80 1 100 1294 Применение В 2012 году организации ISO и IEC включили алгоритмы PRESENT и CLEFIA в международный стандарт облегченного шифрования ISO/IEC 29192-2:2012[1][6][7]. На базе PRESENT была создана компактная хеш-функция H-PRESENT-128[8][9]. Примечания 1 2 Katholieke Universiteit Leuven. Ultra-lightweight encryption method becomes international standard  (неопр.). Дата обращения: 28 февраля 2012. Архивировано из оригинала 6 апреля 2013 года. Masanobu Katagi, Shiho Moriai, Lightweight Cryptography for the Internet of Things Архивная копия от 23 июня 2018 на Wayback Machine, 2011 Панасенко, Смагин, Облегченные алгоритмы шифрования // 2011 Axel York Poschmann. Lightweight Cryptography: Cryptographic Engineering for a Pervasive World. — 2009. Архивировано 8 марта 2021 года. PRESENT: An Ultra-Lightweight Block Cipher, Table 2 ISO. ISO/IEC 29192-2:2012  (неопр.). Дата обращения: 28 февраля 2012. Архивировано из оригинала 5 апреля 2013 года. Алгоритм шифрования, предложенный как «более легкая» альтернатива AES, стал стандартом ISO Архивная копия от 27 апреля 2018 на Wayback Machine // Osp.ru, 02-2012 LW-КРИПТОГРАФИЯ: ШИФРЫ ДЛЯ RFID-СИСТЕМ Архивировано 28 июля 2013 года., С. С. Агафьин // Безопасность информационных технологий № 2011-4 Observations on H-PRESENT-128 Архивная копия от 17 мая 2017 на Wayback Machine, Niels Ferguson (Microsoft) Ссылки PRESENT: An Ultra-Lightweight Block Cipher Algebraic Techniques in Dierential Cryptanalysis Differential Cryptanalysis of Reduced-Round PRESENT (недоступная ссылка) Weak Keys of Reduced-Round PRESENT for Linear Cryptanalysis, Kenji Ohkuma // Lecture Notes in Computer Science Volume 5867, 2009, pp 249–265 doi:10.1007/978-3-642-05445-7 16 A Statistical Saturation Attack against the Block Cipher PRESENT (недоступная ссылка) Сергей Панасенко, Сергей Смагин, Облегченные алгоритмы шифрования // «Мир ПК», № 07, 2011