Дослідження кубічних атак з малими степенями макстермів
| dc.contributor.author | Завадська, Людмила | |
| dc.contributor.author | Сергієнко, Віталій | |
| dc.contributor.author | Zavadska, Lyudmyla | |
| dc.contributor.author | Sergienko, Vitaliy | |
| dc.contributor.author | Завадская, Людмила | |
| dc.contributor.author | Сергиенко, Виталий | |
| dc.date.accessioned | 2016-11-03T13:05:41Z | |
| dc.date.available | 2016-11-03T13:05:41Z | |
| dc.date.issued | 2014 | |
| dc.description.abstracten | Cube attack is one of new promising cryptanalysis methods, which is now successfully applied to various types of modern cryptosystems, such as stream, block ciphers and hash functions. Cube attack is a kind of algebraic attack, where every bit of the cipher output sequence is interpreted as a value of some Boolean function (polynomial) f , that depends on bits of secret key and some public variables (bits of plaintext or initialization vector etc.). Key notions for the Cube attack are notion of maxterm and superpoly. Maxterm is such subset of the function f public variables set, that sum of f output values over all possible values of variables that belong to maxterm (over a binary “cube”) can result in a linear polynomial of secret variables. This polynomial in such case is called superpoly. On the final stage of the attack, system of linear equations is solved. This system is based on the linearly independent superpolies acquired on the previous attack stage. Right parts of equations can be calculated by summing function output values over all variables presented in a corresponding maxterm. Maxterm (cube) search for the linearity checking of corresponding superpolies is a time-consuming operation, so it requires effective implementation approach. One of such approaches is a degree limitation of maxterms under consideration. This limitation can be both upper and lower. As a limitation source, possible function degree assumption can be used. Alternatively, in more strict approach, function degree can be acquired using some appropriate tests, which are, however, more complex and hard to implement. Therefore, usage of low degree maxterms can significantly increase attack effectiveness. However, in such case a question of attack success rate can be raised, i.e. the probability of getting required quantity of linearly independent superpolies. In this paper, we consider question of Cube attack applicability using only low degree maxterms and, as a first step, only maxterms of degree 1. We introduce a notion of auspicious function – function, to which Cube attack can be applied successfully, using maxterms of degree 1 only. As a result of our research, we acquired a mathematical expression (formula) for the number of auspicious functions. It depends on the number of public and secret variables of the function. Values calculated using this formula were verified by comparison with the results of direct computer exhaustive search for some small numbers of arguments of function f . Additionally, success rates for the Cube attack with maxterms of degree 1 were calculated for various combinations of numbers of public and secret variables. Here all Boolean functions with specified numbers of arguments were considered equally probable, which is a natural assumption, taking into account complexity of functions representing real cryptographic systems. Of course, given that we used only low degree maxterms, attack success rate is very low for real numbers of public and secret variables. However, knowing this probability, one can evaluate maximal degree of maxterms that provides acceptable Cube attack success rate. Further development of our research is possible in lots of directions, related to consideration of bigger maxterm degrees, as well as to generalization of the superpoly notion (e.g. search of quadratic superpolies). It should be noted that studied problem is also of independent interest from the Boolean functions theory and combinatorics point of view. | uk |
| dc.description.abstractru | Кубические атаки – один из новых перспективных методов криптоанализа, ныне успешно применяемый к разным типам современных криптосистем, таким как поточные и блочные системы шифрования и хешфункции. Кубические атаки являются разновидностью алгебраических атак, где каждый бит выходной последовательности шифра интерпретируется как значение некоторой булевой функции (полинома) f, который зависит от битов секретного ключа и некоторых открытых переменных (битов открытого текста, вектора инициализации и т. п.). Ключевыми понятиями для кубической атаки являются понятия макстерма и суперполинома. Макстерм – такое подмножество множества открытых переменных функции f, что просуммировав выходы данной функции по всем значениям переменных, которые входят в макстерм (по двоичному «кубу»), можно получить линейный полином от секретных переменных. Этот полином в таком случае называется суперполиномом. На заключительной стадии атаки решается система линейных уравнений, полученных на основе найденных на предыдущей стадии линейно независимых суперполиномов. Правые части уравнений системы получаются как сумма выходов функции по всем значениям переменных, которые входят в соответствующий макстерм. Перебор макстермов (кубов) для проверки соответствующих суперполиномов на линейность является длительной операцией и посему требует эффективных подходов для её выполнения. Один из таких подходов – ограничение степени рассматриваемых макстермов. Такое ограничение можно делать как снизу, так и сверху, источником ограничений может выступать просто представление о возможной степени функции, описывающей выход шифра, либо, при более строгом подходе, нахождение степени нелинейной функции с помощью соответствующих тестов, которые, однако, являются очень сложными и трудными в реализации. Поэтому использование макстермов небольшой степени значительно повысило бы эффективность атаки. Однако при этом возникает вопрос вероятности успеха, то есть вероятности найти необходимое количество линейно независимых суперполиномов. В работе рассматривается вопрос применимости кубических атак при условии использования только макстермов малой степени и, как первый шаг в этом направлении, – только макстермов первой степени. Вводится понятие благоприятной функции – функции, к которой возможно успешное применение кубической атаки с макстермами только первой степени. В результате исследований получено математическое выражение для количества благоприятных функций в зависимости от количества открытых и секретных переменных. Рассчитанные по этим формулам значения проверены путем сравнения с результатами непосредственного компьютерного перебора для небольших значений количества аргументов функции f. Также были рассчитаны вероятности успеха кубической атаки с макстермами первой степени для разных комбинаций количеств открытых и секретных переменных. При этом все булевы функции с заданным количеством аргументов считались равновероятными, что является естественным допущением, учитывая сложность функций, описывающих криптографические системы. Разумеется, при условии использования макстермов малых степеней вероятность успешной атаки очень мала при реальных значениях количества открытых и секретных переменных. Однако, зная величину этой вероятности, можно оценить максимальную степень макстермов, обеспечивающую приемлемый уровень вероятности успеха кубической атаки. Дальнейшее развитие исследований возможно в разных направлениях, связанных как с рассмотрением больших степеней макстермов, так и с обобщением понятия суперполинома (например, поиск суперполиномов второй степени). Следует отметить, что рассматриваемая задача также представляет самостоятельный интерес с точки зрения теории булевых функций и комбинаторики. | uk |
| dc.description.abstractuk | Кубічні атаки – один з нових перспективних методів криптоаналізу, який нині успішно застосовується до різних типів сучасних криптосистем, таких як потокові і блокові системи шифрування та хеш-функції. Кубічні атаки є різновидом алгебраїчних атак, де кожен біт вихідної послідовності шифру інтерпретується як значення деякої булевої функції (поліному) f, що залежить від бітів секретного ключа та деяких відкритих змінних (бітів відкритого тексту, вектора ініціалізації тощо). Ключовими поняттями для кубічної атаки є поняття макcтерму та суперполіному. Макстерм – така підмножина множини відкритих змінних функції f, що просумувавши виходи даної функції по всіх значеннях змінних, які входять у макстерм (по двійковому кубу), можна отримати лінійний поліном від секретних змінних. Цей поліном в такому випадку називається суперполіномом. На заключній стадії атаки розв’язується система лінійних рівнянь, отриманих на основі знайдених на попередній стадії лінійно незалежних суперполіномів. Праві частини рівнянь системи отримуються як сума виходів функції за всіма значеннями змінних, що входять у відповідний макстерм. Перебір макстермів (кубів) для перевірки відповідних суперполіномів на лінійність є тривалою операцією і тому потребує ефективних підходів для її здійснення. Одним із таких підходів є обмеження степеня макстермів, що беруться до розгляду. Таке обмеження можна робити як знизу, так і зверху, джерелом обмежень може виступати просто уявлення про можливий степінь функції, що описує вихід шифру, або, при більш строгому підході, знаходження степеня нелінійної функції за допомогою відповідних тестів, які, однак, є досить складними і важкими для реалізації. Тому використання макстермів невеликого степеня значно підвищило б ефективність атаки. Проте при цьому постає питання ймовірності успіху, тобто ймовірності знайти необхідну кількість лінійно незалежних суперполіномів. У роботі розглядається питання застосовності кубічних атак за умови використання лише макстермів малого степеня і, як пеший крок у цьому напрямі, – лише макстермів першого степеня. Вводиться поняття сприятливої функції – функції, до якої можливе успішне застосування кубічної атаки з макстермами тільки першого степеня. В результаті досліджень отримано математичний вираз для кількості сприятливих функцій залежно від кількості відкритих і секретних змінних. Розраховані за цими формулами значення перевірено шляхом порівняння із результатами безпосереднього комп’ютерного перебору для невеликих значень кількості аргументів функції f. Також розраховані імовірності успіху кубічної атаки з макстермами першого степеня для різних комбінацій кількостей відкритих і секретних змінних. При цьому всі булеві функції з заданою кількістю аргументів вважаються рівноймовірними, що є природним припущенням з огляду на складність функцій, які описують криптографічні системи. Звісно, за умови використання макстермів малих степенів імовірність успішної атаки є дуже малою за реальних значень кількості відкритих та секретних змінних. Проте, знаючи величину цієї імовірності, можна оцінити максимальний степінь макстермів, що забезпечує прийнятний рівень імовірності успіху кубічної атаки. Подальший розвиток досліджень можливий у різних напрямках, пов’язаних як із розглядом більших степенів макстермів, так і узагальненням поняття суперполінома (наприклад, пошук суперполіномів другого степеня). Слід зазначити, що розглядувана задача також представляє самостійний інтерес з точки зору теорії булевих функцій та комбінаторики. | uk |
| dc.format.pagerange | С. 53-59 | uk |
| dc.identifier.citation | Завадська Л. Дослідження кубічних атак з малими степенями макстермів / Людмила Завадська, Віталій Сергієнко // Правове, нормативне та метрологічне забезпечення системи захисту інформації в Україні : науково-технічний збірник. – 2014. – Вип. 2(28). – С. 53-59. – Бібліогр.: 6 назв. | uk |
| dc.identifier.uri | https://ela.kpi.ua/handle/123456789/17984 | |
| dc.language.iso | uk | uk |
| dc.publisher | НТУУ "КПІ" | uk |
| dc.publisher.place | Київ | uk |
| dc.source.name | Правове, нормативне та метрологічне забезпечення системи захисту інформації в Україні: науково-технічний збірник | uk |
| dc.status.pub | published | uk |
| dc.subject | Криптоаналіз | uk |
| dc.subject | кубічні атаки | uk |
| dc.subject | макстерми | uk |
| dc.subject | булеві функції | uk |
| dc.subject.udc | 681.3.06:519.248.681 | uk |
| dc.title | Дослідження кубічних атак з малими степенями макстермів | uk |
| dc.title.alternative | Research of cube attacks with low degree maxterms | uk |
| dc.title.alternative | Исследование кубических атак с малыми степенями макстермов | uk |
| dc.type | Article | uk |
| thesis.degree.level | - | uk |
Файли
Контейнер файлів
1 - 1 з 1
Ліцензійна угода
1 - 1 з 1
Ескіз недоступний
- Назва:
- license.txt
- Розмір:
- 7.71 KB
- Формат:
- Item-specific license agreed upon to submission
- Опис: