Present (шифр)
| Present | |
| Опубликован: |
CHES, 2007-08-23; |
|---|---|
| Размер ключа: |
80 бит (Present-80), 128 бит (Present-128) |
| Размер блока: |
64 бит |
| Число раундов: |
31 |
| Тип: | |
Present — блочный шифр с размером блока 64 бита, длиной ключа 80 или 128 бит и количеством раундов 32.
Основное назначение данного шифра — использование в узкоспециализированных приборах, наподобие RFID меток или сетей сенсоров.
Является одним из самых компактных криптоалгоритмов, существуют оценка, что для аппаратной реализации PRESENT требуется приблизительно в 2.5 раза меньше логических элементов чем для AES или CLEFIA.[1][2]
Данный шифр был представлен на конференции CHES 2007. Авторы: Богданов, Кнудсен, Леандр, Паар, Пошманн, Робшо, Соа, Викельсоа. Авторы работают в Orange Labs, Рурском университете в Бохуме и Датском техническом университете.
Содержание
Схема шифрования
Основным критерием при разработке шифра была простота реализации при обеспечении средних показателей защищенности. Также важным моментом была возможность эффективной аппаратной реализации.
Представляет собой SP-сеть с 31 раундом шифрования. Каждый раунд состоит из операции XOR с раундовым ключом <math>K_i</math>, состоящим из 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 составлена таким образом, чтобы увеличить сопротивляемость линейному и дифференциальному криптоанализу. В частности:
- <math> P(\forall x \in [0,F] : S(x) + S(x + \Delta_i ) = \Delta_o ) <= 4</math>, где <math>\Delta_i, \Delta_o</math> — любые возможные входные и выходные дифференциалы не равные 0.
- <math> P(\forall x \in [0,F] : S(x) + S(x + \Delta_i ) = \Delta_o ) = 0</math>, где <math>wt(\Delta_i) = wt(\Delta_o) = 1</math>.
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
В качестве раундового ключа <math>K_i</math> используются 64 левых бит из регистра <math>K</math>, содержащего весь ключ. После получения раундового ключа регистр <math>K</math> обновляется по следующему алгоритму:
- <math>[k_{79} k_{78} . . . k_1 k_0 ] = [k_{18} k_{17} . . . k_{20} k_{19} ]</math>
- <math>[k_{79} k_{78} k_{77} k_{76} ] = S[k_{79} k_{78} k_{77} k_{76} ]</math>
- <math>[k_{19} k_{18} k_{17} k_{16} k_{15} ] = [k_{19} k_{18} k_{17} k_{16} k_{15} ] \oplus </math>round_counter
Криптоустойчивость
Дифференциальный криптоанализ
Данный шифр обладает свойством, что любая 5-раундовая дифференциальная характеристика затрагивает по меньшей мере 10 S-box`ов. Таким образом, например, для 25 раундов шифра будут задействованы как минимум 50 S-box`ов, и вероятность характеристики не превышает <math>2^{-100}</math>. Атака на версии шифра с 16 раундами шифрования требует <math>2^{64}</math> шифротекстов, <math>2^{64}</math> доступов к памяти, <math>2^{32}</math> 6-битных счетчиков и <math>2^{24}</math> ячеек памяти для хэш таблицы. Вероятность нахождения ключа <math>P \approx 0.999</math>
Линейный криптоанализ
Максимальный наклон аппроксимированной прямой для 4 раундов не превышает <math> \frac{1}{2^7}</math>. Таким образом для 28 раундов максимальный наклон будет <math> 2^6 * {(\frac{1}{2^7})^7} = 2^{-43}</math>. Поэтому, если учесть, что для взлома 31 раунда необходима аппроксимация для 28, то понадобится <math>2^{84}</math> известных пар текст-шифротекст, что превышает размер возможного теста для шифрования.
Другие методы
- Алгебраическая атака с использованием дифференциальных характеристик. Основная идея — представить шифр системой уравнений низкого порядка. Далее, для нескольких пар текст-шифротекст соответствующие им системы уравнений объединяются. Если в качестве этих пар выбрать пары соответствующие некоторой характеристике <math>\delta</math> с вероятностью p, то система будет верна с этой вероятностью p и решения может быть найдено при использовании <math>\frac{1}{p}</math> пар. Ожидается, что решение такой системы проще, чем изначальной, соответствующей одной паре текст-шифротекст. Для Present-80 с 16 раундами данная атака позволяет узнать 4 бита ключа за <math>\approx 6*2^{12}</math> секунд.
- Метод статистического насыщения. В данной атаке используются недостатки блока перемешивания бит. Для взлома Present-80 с 24 раундами требуется пар текст-шифротекст <math>\approx 2^{60}</math> вычислений <math>\approx 2^{20}</math>.
Сравнение с другими шифрами
В таблице ниже приведена сравнительная характеристика шифра Present-80 по отношению к другим блочным и потоковым шифрам.[4]
| Название | Размер ключа | Размер блока | Пропускная способность(Kpbs) | Площадь (в GE) |
|---|---|---|---|---|
| Present-80 | 80 | 64 | 200 | 1570 |
| 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.[5][1][6]
На базе PRESENT была создана компактная хеш-функция H-PRESENT-128.[7][8]
Напишите отзыв о статье "Present (шифр)"
Примечания
- ↑ 1 2 Katholieke Universiteit Leuven. [www.kuleuven.be/english/news/ultra-lightweight-encryption-method-becomes-international-standard Ultra-lightweight encryption method becomes international standard]. Проверено 28 февраля 2012. [www.webcitation.org/6FfMFhvJ4 Архивировано из первоисточника 6 апреля 2013].
- ↑ Masanobu Katagi, Shiho Moriai, [www.iab.org/wp-content/IAB-uploads/2011/03/Kaftan.pdf Lightweight Cryptography for the Internet of Things], 2011
- ↑ Панасенко, Смагин, Облегченные алгоритмы шифрования // 2011
- ↑ PRESENT: An Ultra-Lightweight Block Cipher, Table 2
- ↑ ISO. [www.iso.org/iso/iso_catalogue/catalogue_tc/catalogue_detail.htm?csnumber=56552 ISO/IEC 29192-2:2012]. Проверено 28 февраля 2012. [www.webcitation.org/6Fe4bAgHy Архивировано из первоисточника 5 апреля 2013].
- ↑ [www.osp.ru/news/2012/0228/13011754/ Алгоритм шифрования, предложенный как «более легкая» альтернатива AES, стал стандартом ISO] // Osp.ru, 02-2012
- ↑ [www.pvti.ru/data/file/bit/bit_1_2011_6.pdf LW-КРИПТОГРАФИЯ: ШИФРЫ ДЛЯ RFID-СИСТЕМ], С. С. Агафьин // Безопасность информационных технологий № 2011-4
- ↑ [www.iacr.org/cryptodb/archive/2011/CRYPTO/video/rump/71040a68ec50a72283954e7d1f0a36ac.pdf Observations on H-PRESENT-128], Niels Ferguson (Microsoft)
Ссылки
- [www.ist-ubisecsens.org/publications/present_ches2007.pdf PRESENT: An Ultra-Lightweight Block Cipher]
- [www.ei.rub.de/media/ei/lehrmaterialien/Seminar_kryptanalyse_und_beweisbare_sicherheit/AlgDiffAttacks.pdf Algebraic Techniques in Differential Cryptanalysis]
- [www.springerlink.com/index/n6u0g6g6774w8888.pdf 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
- [www.springerlink.com/content/e62232827002n882/ A Statistical Saturation Attack against the Block Cipher PRESENT]
- Сергей Панасенко, Сергей Смагин, [www.osp.ru/pcworld/2011/07/13009487/ Облегченные алгоритмы шифрования] // «Мир ПК», № 07, 2011
Отрывок, характеризующий Present (шифр)
Что стоило еще оставаться два дни? По крайней мере, они бы сами ушли; ибо не имели воды напоить людей и лошадей. Он дал слово мне, что не отступит, но вдруг прислал диспозицию, что он в ночь уходит. Таким образом воевать не можно, и мы можем неприятеля скоро привести в Москву…Слух носится, что вы думаете о мире. Чтобы помириться, боже сохрани! После всех пожертвований и после таких сумасбродных отступлений – мириться: вы поставите всю Россию против себя, и всякий из нас за стыд поставит носить мундир. Ежели уже так пошло – надо драться, пока Россия может и пока люди на ногах…
Надо командовать одному, а не двум. Ваш министр, может, хороший по министерству; но генерал не то что плохой, но дрянной, и ему отдали судьбу всего нашего Отечества… Я, право, с ума схожу от досады; простите мне, что дерзко пишу. Видно, тот не любит государя и желает гибели нам всем, кто советует заключить мир и командовать армиею министру. Итак, я пишу вам правду: готовьте ополчение. Ибо министр самым мастерским образом ведет в столицу за собою гостя. Большое подозрение подает всей армии господин флигель адъютант Вольцоген. Он, говорят, более Наполеона, нежели наш, и он советует все министру. Я не токмо учтив против него, но повинуюсь, как капрал, хотя и старее его. Это больно; но, любя моего благодетеля и государя, – повинуюсь. Только жаль государя, что вверяет таким славную армию. Вообразите, что нашею ретирадою мы потеряли людей от усталости и в госпиталях более 15 тысяч; а ежели бы наступали, того бы не было. Скажите ради бога, что наша Россия – мать наша – скажет, что так страшимся и за что такое доброе и усердное Отечество отдаем сволочам и вселяем в каждого подданного ненависть и посрамление. Чего трусить и кого бояться?. Я не виноват, что министр нерешим, трус, бестолков, медлителен и все имеет худые качества. Вся армия плачет совершенно и ругают его насмерть…»
В числе бесчисленных подразделений, которые можно сделать в явлениях жизни, можно подразделить их все на такие, в которых преобладает содержание, другие – в которых преобладает форма. К числу таковых, в противоположность деревенской, земской, губернской, даже московской жизни, можно отнести жизнь петербургскую, в особенности салонную. Эта жизнь неизменна.
С 1805 года мы мирились и ссорились с Бонапартом, мы делали конституции и разделывали их, а салон Анны Павловны и салон Элен были точно такие же, какие они были один семь лет, другой пять лет тому назад. Точно так же у Анны Павловны говорили с недоумением об успехах Бонапарта и видели, как в его успехах, так и в потакании ему европейских государей, злостный заговор, имеющий единственной целью неприятность и беспокойство того придворного кружка, которого представительницей была Анна Павловна. Точно так же у Элен, которую сам Румянцев удостоивал своим посещением и считал замечательно умной женщиной, точно так же как в 1808, так и в 1812 году с восторгом говорили о великой нации и великом человеке и с сожалением смотрели на разрыв с Францией, который, по мнению людей, собиравшихся в салоне Элен, должен был кончиться миром.
В последнее время, после приезда государя из армии, произошло некоторое волнение в этих противоположных кружках салонах и произведены были некоторые демонстрации друг против друга, но направление кружков осталось то же. В кружок Анны Павловны принимались из французов только закоренелые легитимисты, и здесь выражалась патриотическая мысль о том, что не надо ездить во французский театр и что содержание труппы стоит столько же, сколько содержание целого корпуса. За военными событиями следилось жадно, и распускались самые выгодные для нашей армии слухи. В кружке Элен, румянцевском, французском, опровергались слухи о жестокости врага и войны и обсуживались все попытки Наполеона к примирению. В этом кружке упрекали тех, кто присоветывал слишком поспешные распоряжения о том, чтобы приготавливаться к отъезду в Казань придворным и женским учебным заведениям, находящимся под покровительством императрицы матери. Вообще все дело войны представлялось в салоне Элен пустыми демонстрациями, которые весьма скоро кончатся миром, и царствовало мнение Билибина, бывшего теперь в Петербурге и домашним у Элен (всякий умный человек должен был быть у нее), что не порох, а те, кто его выдумали, решат дело. В этом кружке иронически и весьма умно, хотя весьма осторожно, осмеивали московский восторг, известие о котором прибыло вместе с государем в Петербург.
В кружке Анны Павловны, напротив, восхищались этими восторгами и говорили о них, как говорит Плутарх о древних. Князь Василий, занимавший все те же важные должности, составлял звено соединения между двумя кружками. Он ездил к ma bonne amie [своему достойному другу] Анне Павловне и ездил dans le salon diplomatique de ma fille [в дипломатический салон своей дочери] и часто, при беспрестанных переездах из одного лагеря в другой, путался и говорил у Анны Павловны то, что надо было говорить у Элен, и наоборот.
Вскоре после приезда государя князь Василий разговорился у Анны Павловны о делах войны, жестоко осуждая Барклая де Толли и находясь в нерешительности, кого бы назначить главнокомандующим. Один из гостей, известный под именем un homme de beaucoup de merite [человек с большими достоинствами], рассказав о том, что он видел нынче выбранного начальником петербургского ополчения Кутузова, заседающего в казенной палате для приема ратников, позволил себе осторожно выразить предположение о том, что Кутузов был бы тот человек, который удовлетворил бы всем требованиям.
Анна Павловна грустно улыбнулась и заметила, что Кутузов, кроме неприятностей, ничего не дал государю.
– Я говорил и говорил в Дворянском собрании, – перебил князь Василий, – но меня не послушали. Я говорил, что избрание его в начальники ополчения не понравится государю. Они меня не послушали.
– Все какая то мания фрондировать, – продолжал он. – И пред кем? И все оттого, что мы хотим обезьянничать глупым московским восторгам, – сказал князь Василий, спутавшись на минуту и забыв то, что у Элен надо было подсмеиваться над московскими восторгами, а у Анны Павловны восхищаться ими. Но он тотчас же поправился. – Ну прилично ли графу Кутузову, самому старому генералу в России, заседать в палате, et il en restera pour sa peine! [хлопоты его пропадут даром!] Разве возможно назначить главнокомандующим человека, который не может верхом сесть, засыпает на совете, человека самых дурных нравов! Хорошо он себя зарекомендовал в Букарещте! Я уже не говорю о его качествах как генерала, но разве можно в такую минуту назначать человека дряхлого и слепого, просто слепого? Хорош будет генерал слепой! Он ничего не видит. В жмурки играть… ровно ничего не видит!
