Ключевые слова: шифрование, блочный алгоритм шифрования, легковесная криптография, раундовая функция, управляемые сдвиги, развертка ключа.
В связи с широким распространением в промышленных системах, системах управления и массовых бытовых устройствах потребительского рынка микроконтроллеров общего назначения они стали относительно дешевы и широко доступны. В то же время их возможности изменились настолько, что стало возможно говорить о реализации сложных криптографических преобразований [1, 2]. Однако реализация на микроконтроллерах стандартов шифрования не может обеспечить приемлемой скорости шифрования. Поэтому для достижения высокой скорости было предложено несколько специальных алгоритмов шифрования, получивших название «легковесных» [3, 4, 5]. Наиболее эффективными среди них следует признать алгоритмы SPECK и SIMON, разработанные АНБ [6, 7]. В них выражена идея алгоритма шифрования, состоящего из большого количестве простых преобразований, которая высказывалась в письмах 50-х годов в АНБ лауреатом нобелевской премии по экономике Джоном Нэшэм [9].
Мы поставили своей целью разработать легковесный алгоритм блочного шифрования, который не уступал бы по стойкости упомянутым алгоритмам АНБ, но позволял бы несколько сократить количество раундов, что делает его еще более быстрым. В честь Джона Нэша (John Nash) мы назвали алгоритм NASH.
Схема алгоритма
Схема алгоритма NASH выглядит следующим образом. Текст разбивается на полублоки по 2**n бит, блок шифруется r раундов на последовательности раундовых ключей k(i), получаемых из главного ключа по алгоритму «расширения ключа». Блок данных разбивается на левый и правый полублоки (L(i), R(i)) по 2**n бит каждый, с которыми на (i+1)-м раунде производятся следующие преобразования
Уравнения шифрования блока данных на (i+1)-м раунде выглядят так:
R(i+1)=L(i)
L(i+1)=((L(i)?k(i))?F(L(i),L(i)?k(i)))?R(i)
В последнем раунде шифрования блока не меняются местами полублоки L(i+1), R(i+1).
Детали раундового преобразования
Размер полублока равен 2**n, где n=5 или 6, соответственно размер полублока равен 32 или 64 бита. Соответственно предлагается размер блока 64 или 128 бит.
Смешивание с раундовым ключом k(i): ? – функция сложение двух целых чисел по модулю 2^n.
Управляемый циклический сдвиг:
- для размера блока 64 бита (полублока – 32 бита) — циклический сдвиг вправо на одно из 4 значений (11, 14, 10, 19).
- для размера блока 128 бит (размер полублока – 64 бита) — циклический сдвиг вправо на одно из 4 значений (37, 34, 38, 29).
Функция управления сдвигами
Интерпретируем полублок L(i) как вектор значений булевой функции от n переменных, и первый выходной бит F получаем как значение данной функции на наборе битов из L(i)?k(i) вида 2**i-1, где i=1, …, n, то есть как значение L(i) ((L(i)?k(i))[2**1-1,…,2**n-1]), нумерация битов полублока от 0 до 2**n-1.
Интерпретируем L(i)?k(i) как вектор значений булевой функции от n переменных, и второй выходной бит F получаем как значение данной функции на наборе битов из L(i) вида 2**i-1, где i=1,…, n, то есть как (L(i)?k(i))(L(i) [2**1-1,…,2**n-1]), нумерация битов полублока от 0 до 2^n-1.
Для размера блока 64 бита (соответственно, полублока – 32 бита):
00 соответствует циклическому сдвигу на 11;
01 соответствует циклическому сдвигу на 14;
10 соответствует циклическому сдвигу на 10;
11 соответствует циклическому сдвигу на 19.
Число раундов r:
для размера блока 64 (полублока — 32): r=24;
для размера блока 128 (полублока — 64): r=28.
Размер ключа: 128, 192 или 256 бит.
Функция выработки раундовых ключей
L(0)=с(0), R(0)=с(1), где значение константы с(i) получается следующим образом.
Ключ разбивается на L блоков длины 2^n, еще 8-L блоков получаем как значения квадратного корня из первых простых чисел (v2, v3, v5 и т. д., оставляем только мантиссу – дробную часть без порядка. C99 / C11 80-бит long double берем биты из последних 64 бит).
Данные блоки соответствуют с(0), с(1), …, с(7).
Далее при вычислении с(i) берем константу с(i) с индексом (i mod 6)+2 и складываем его по модулю 2 с номером раунда с(i)=i?с((i mod 6)+2).
В качестве раундового ключа берем k(i)=L(i+1).
2. Interenet of Things. 2016 URL: http:// www.gemalto.com / iot
3. McKay K., Bassham L., Turan M., Mouha N., DRAFT NISTIR 8114 Report on Lightweight Cryptography Computer Security Division Information Technology Laboratory NIST, 2016 URL: www.nist.gov
4. D. Dinu, Y. Le Corre, D. Khovratovich, L. Perrin, J. Gro?schadl, A. Biryukov, Triathlon of Lightweight Block Ciphers for the Internet of Things, Report on Lightweight Cryptography Lightweight Cryptography Workshop 2015, Computer Security Division Information Technology Laboratory NIST, 2015 URL: www.nist.gov
5. N. Mouha, B. Mennink, A. Van Herrewege, D. Watanabe, B. Preneel, I. Verbauwhede, Chaskey: a Lightweight MAC Algorithm for Microcontrollers, Lightweight Cryptography Workshop 2015, Cryptography Computer Security Division Information Technology Laboratory NIST, 2015 URL: www.nist.gov
6. H. Tschofenig, M. Pegourie-Gonnard, Performance of State-of-the-Art Cryptography on ARM-based Microprocessors, NIST Lightweight Cryptography Workshop 2015
7. R. Beaulieu, D. Shors, J. Smith, S. Treatman-Clark, B. Weeks, L. Wingers, Simon and Speck: Block Ciphers for the Internet of Things, National Security, Agency 9800 Savage Road, Fort Meade, MD, 20755, USA, Memo 9 July 2015
8. C. Shannon, Communication theory of secret systems, Bell Systems Techn. J. (1949) 656-715
9. J. Nash, Letter to NSA, 1955, URL: www.nsa.gov/public_info/press_room/2012/nash_exhibit_shtm
Комментарии (42)
iUser
07.09.2017 16:04+3Зависящий от ключа циклический сдвиг — это как-то чересчур оптимистично, по нынешним мерками.
lancrypto Автор
08.09.2017 09:51Можете доказать?
iUser
08.09.2017 15:56+1В аппаратной реализации или, как минимум, на процессоре без barrel shifter, циклический сдвиг на разное количество бит будет выполняться за разное время. Это — побочный канал для атаки.
Применительно к этому алгоритму, это означает что атакующий может узнать результат F, т.е. сфокусировать chosen plaintext attack непосредственно на X = F(L, L xor K) где X и L известны. Причем при известном L, пространство перебора K сразу же снижается до 2^(n-1) безо всяких дополнительных телодвижений.
Помимо этого, если поглядеть на схему раунда, то можно увидеть что при известных Li и Ri в Li+1 оказывается чистый раундовый ключ Ki, циклически сдвинутый на одно из 4х значений. Само по себе это не особо страшно, но говорит о том, что количество раундов в алгоритме желательно не менее 16.
Это не полноценный анализ, просто навскидку по написанному.
aaprelev
08.09.2017 18:42Полагаю, что все сдвиги можно осуществлять за постоянное время: либо простоем конвейера, либо сдвигами фиктивного регистра.
lancrypto Автор
08.09.2017 19:39Отправил ваш выпад молодым соавторам. Ждем ответа.
Пока суть, да дело: скажите, 2^255 — это действительно «взлом»?
«Если это так, Вы мой враг на всю жизнь.» (М. Булгаков «Собачье сердце»)
c0ba
07.09.2017 16:50+2> Предложен оригинальный новый алгоритм блочного шифрования
Новый!
А в литературе по теме:
> 9. J. Nash, Letter to NSA, 1955, URL: www.nsa.gov/public_info/press_room/2012/nash_exhibit_shtm
2012!
не находите странным?
akamensky
08.09.2017 07:29Точно так же как половина эллиптических кривых в ECDSA(ECDH) «одобрена» NSA (да и параметры кривых какие-то странные и ни разу никем не объяснены).
lancrypto Автор
08.09.2017 09:54Мы не АНБ, а скорей наоборот. Если Вы спросите, что такое lancrypto из 90-х, то старшее поколение может рассказать.
lancrypto Автор
08.09.2017 09:53Нет, посмотрите мое выступление на конференции EUROCRYPT 2016. Именно по поводу этого письма и гибели Джона Нэша в автокатастрофе, мы и назвали в его честь наш алгоритм.
Kolyuchkin
07.09.2017 16:56+4Та же «сеть Фейстеля», что и в старом добром ГОСТ 28147-89. Немного «припудренная» и ослабленная. Если нет математического доказательства стойкости, то это очередная забава — «поиграться в криптографа» — в качестве дипломного проекта и для домашних поделок сойдет.
Labunsky
07.09.2017 20:44А я DES вспомнил. На беглый взгляд, относительно стойкое, но только если у вас за окном ранние 80е
lancrypto Автор
08.09.2017 10:29Да, DES так и не был сломан. Просто устарел по причине короткого блока данных и коротких ключей. Стало возможно их тотально перебрать. Но у алгоритма NASH эти параметры несколько иные.
lancrypto Автор
08.09.2017 10:27Попробуйте.
Kolyuchkin
08.09.2017 10:50Да это я не для себя))) Я уже 14 лет назад защитил свой дипломный проект)
lancrypto Автор
08.09.2017 12:27Я с Вами согласен, именно кто-то из будущих дипломников и может предложить что-либо неординарное в области анализа. Ждем-с
lancrypto Автор
07.09.2017 18:28Не очень понятна ирония в слове «потреотичном».
Я пытаюсь с 94-го года на практике доказать, что у нас есть кому разработать достойные крипто. алгоритмы (и не только в спецслужбе). Американцы и европейцы в 90-х в это не очень верили, но за последние 20 лет кое-что общими усилиями (РусКрипто, CTCrypt, SibСrypto, etc.) удалось доказать. Денег на теоретические изыскания мало, потому и «потреотичных» алгоритмов немного. Но есть, как видите. Взломать слабо?
CodeRush
07.09.2017 21:14+7Дело в том, что криптография — это раздел математики, а не разработки ПО, так что еще до того, как написать первую строчку кода, нужен положительный результат криптоанализа предложенного алгоритма (лучше всего в виде статьи в нормальном журнале, чтобы собрать критику со специалистов), иначе весь этот код — поделка на коленке, а использование такой "потреотичных" реализации — хуже, чем отсутствие шифрования вообще, т.к. дает ложное чувство защищенности.
Бремя доказательства лежит на авторах утверждений вроде "позволяет при сохранении уровня стойкости ограничиваться меньшим числом раундов", так что это не нам всем тут слабо взломать, а вам слабо предоставить не только алгоритм, но и результаты его анализа.lancrypto Автор
08.09.2017 10:33+1Результаты нашего внутреннего мы обязательно опубликуем по мере их правильного (в смысле математики и русского языка) оформления. Наиболее сильная команда аналитиков, которая выразила желание его анализировать — аспиранты и студенты-дипломники моего старого знакомого Serge Vaudenay (он сейчас работает в Швейцарии). Если Вы готовы составить им конкуренцию, — вперед и вверх!
DFooz
09.09.2017 10:31CodeRush, Авторы не обязаны анализировать алгоритмы. Это вполне могут сделать и сторонние люди. Другое дело, с анализом приятнее и доверия больше, так сказать, впервое впечатление.
worldmind
07.09.2017 21:21+3криптография это математика, поэтому никто всерьёз не будет рассматривать без публикации научной статьи в серьёзном журнале.
DFooz
09.09.2017 10:33выше автор ответил, что представляли на EuroCrypt2016, одна из самых крутых конференций
habrahabr.ru/post/337388/#comment_10406440worldmind
09.09.2017 10:59Это никак не связано с тем, то я озвучил, я написал о научной (математической) статье в известном рецензируемом научном журнале.
AndrewTishkin
07.09.2017 18:46-1lancrypto Автор
08.09.2017 10:35+2Нет, это два аспиранта кафедры ИУ8 МГТУ, А. Карондеев, А. Козлов и доцент этой же кафедры А. Н. Лебедев- официальные соавторы алгоритма.
Greyushko
08.09.2017 13:46+1поставили своей целью разработать легковесный алгоритм блочного шифрования, который не уступал бы по стойкости упомянутым алгоритмам АНБ, но позволял бы несколько сократить количество раундов, что делает его еще более быстрым
1) Если вы модифицируете шифр и говорите, что получилась стойкость не ниже, чем у исходного, то нужно хорошее математическое доказательство. Речь не о том, чтобы давать шифр десяткам «зубров», чтобы они его потрогали. Пусть пробуют исходный алгоритм. А вы тогда сразу сможете на это опираться.
Вообще, конечно, уже писали, но повторю. Каждый день люди придумывают десятки, а может, и сотни разных алгоритмов. Конечно же, никто не будет тратить свое время на поиск слабостей в каждом из них, если нет мотивации. Она может быть двух вариантов:
— вы объявляете хороший денежный приз;
— вы делаете алгоритм, который потенциально лучше существующих, широко распространенных, по каким-то критериям и выкладываете, например, на eprint.iacr.org.
Причем, второй еще ничего не гарантирует, но является, как минимум, обязательным условием.
2) Легковесность. Вы уверены, что она получилась? Сколько логических вентилей потребуется на реализацию? А сколько у конкурентов?
3) Скорость. Тоже не увидел. Как по сравнению, хотя бы, с ГОСТ 28147-89?
У нас по университету, когда я учился, байка ходила. Пришла девочка защищать диплом.
— Я разработала свой новый шифр.
— Он стойкий?
— Конечно!
— А с чего вы взяли?
— Ну я зашифровала сообщение. Посмотрела на него — ничего не понятно. Значит, стойкий.
Вот ваша задача теперь состоит в том, чтобы убедить общественность, на суд которой представляете алгоритм, что вы чем-то отличаетесь от этой девочки :)
lancrypto Автор
11.09.2017 11:09-1Это как в том анекдоте: «Чукча — не читатель, чукча — писатель.»
Конечно, следует внимательно следить за разработками конкурентов, но Лев Толстой не комментировал романов Ф. М. Достоевского и наоборот. Это пусть делают критики.
lair
11.09.2017 11:48Лев Толстой не комментировал романов Ф. М. Достоевского и наоборот.
… зато как Вагнер отзывался о других композиторах — и наоборот.
Это, как всегда, к тому, что аналогии врут.
lancrypto Автор
11.09.2017 12:21Но и Вагнер и «другие композиторы» в истории музыке остались.
За нами тоже кое-что есть, например, математические результаты, на основе которых сделан национальный стандарт на электронную подпись Республики Беларусь 1999 года.
Кстати, алгоритм у них получился весьма неплохой.
vilgeforce
«при сохранении уровня стойкости» — без пруфов это голословное утверждение, которое влечет за собой известную фразу: «никогда не изобретайте собственную криптографию».
vesper-bot
Зато NASHa разработка! (/сарказм)
lancrypto Автор
«Пруфы» мы и пытаемся получить. Если Вы знакомы с криптографией, то должны знать, что единственный настоящий «пруф» сегодня можно озвучиь так: «Мы собрали много „головастых“ криптографов, заплатили им достаточно денег ( в университетском мире это может быть в виде грантов и конференций), чтобы они не работали на стороне, и ждем отчет с результатами криптоанализа. Если месяцев за 8-9 не понизили оценку стойкости, то можно еще лет 5 шифр использовать».
bihuf404
Я, мягко говоря, знаком с криптографией, и могу сказать следующее. Алгоритм шифрования представляет из себя совокупность описания блоков, обоснования выбора узлов и их параметров и первичный криптоанализ. Все что увидел в статье — голословные утверждения, представленные исключительно описанием алгоритма. При таком наборе данных ни один уважающий себя коллектив не возьмется это анализировать. Так что через 8-9 месяцев можете пользоваться на 5 лет
lancrypto Автор
А мне так называемые «уважающие себя коллективы» и не интересны совсем. В таковых еще никогда не рождались новые революционные идеи ( как в науке вообще, так и в криптоанализе, в частности). Поэтому мое обращение к молодым исследователям, которым это будет интересно. Когда Диффи, Хеллман, Ривест, Шамир и Эдлеман писали свои революционные работы по криптографии они ее вообще знали слабо.
bihuf404
Лет 7 назад пришел в «уважающий себя коллектив» тоже с революционной идеей (суть заключалась в построении алгоритма по аналогии с Rijndael, только не матрица, а куб, соответственно операции проводились над плоскостями). Так вот, опытные криптографы советской закалки буквально за час смогли понизить стойкость на несколько порядков. С тех пор мое мнение о них изменилось.
lancrypto Автор
Это приятно слышать, ибо первоначально я тоже 15 лет состоял в числе таких.
Но все же «прорывов» там практически не было. И технология проведения анализа ограниченным (пусть и очень квалифицированным) коллективом проигрывает мобилизации интеллектуальных сил через открытые конференции и конкурсы. Это показал убедительно весь опыт развития так называемой «открытой криптографии», начиная с 1969 года.