Record Details

Keyless hash functions of shift registers type

Наукові журнали Національного Авіаційного Університету

View Archive Info
 
 
Field Value
 
Title Keyless hash functions of shift registers type
Безключевые хэш-функции регистрового типа
Безключові геш-функції регістрового типу
 
Creator Олексійчук, Антон Миколайович; НТУУ «КПІ».
Король, Катерина Вікторівна; Донецький національний університет
 
Subject Information Security
keyless hash function; collision search attacks; finite state automaton; nonlinear shift register; system of automaton equations; MDx; SHA
UDK 621.391:519.7
Информационная безопастность
безключевая хэш-функция; поиск коллизий; конечный автомат; нелинейный регистр сдвига; система автоматных уравнений; MDx; SHA
УДК 621.391:519.7
Інформаційна безпека
безключова геш-функція; пошук колізій; скінченний автомат; нелінійний регістр зсуву; система автоматних рівнянь; МНх; SHA
УДК 621.391:519.7
 
Description Keyless hash functions are one of the most important cryptographic primitives and are used in modern encryp­tion, authentication, digital signature, keys generation systems, etc. Although conspicuous progress in develop­ing of various attacks on "specific" hash functions, under­standing of the principles underlying these attacks, deter­mining the conditions of their applicability, and develop­ment of methods for their performance estimating is an active subject of further research. The goal of this paper is to establish the general conditions of practical security for a broad class of hash functions based on shift registers against collision search attacks on their compression func­tions. It is shown that the problem of building of colli­sions can be reduced to solving some automaton equa­tions with binary unknowns satisfying certain constraints. Then the set of all solutions of these equations (without constraints) have simple algorithmic description that al­lows to enumerate these solutions in the real time-mode.
Безключевые хэш-функции относятся к наиболее важным криптографическим примитивам и приме­няются в современных системах шифрования, аутен­тификации, цифровой подписи, генерации ключей и т.д. Несмотря на заметный процесс в разработке раз­личных атак на “конкретные” хэш-функции, понима­ние закономерностей, лежащих в основе указанных атак, нахождение условий их применимости и разра­ботка методов оценивания их эффективности явля­ются предметом активных дальнейших исследований. Цель статьи состоит в установлении общих условий, определяющих практическую стойкость широкого класса хэш-функций, основанных на регистрах сдви­га, относительно атак, направленных на построение коллизий их сжимающих функций. Показано, что задача построения коллизий сводится к решению автоматных уравнений относительно двоичных неиз­вестных, удовлетворяющих определенным ограниче­ниям. При этом множества всех решений таких урав­нений (без учета ограничений) имеют простое алго­ритмическое описание, что позволяет перечислять эти решения в режиме реального времени
Безключові геш-функції відносяться до найважливіших криптографічних примітивів і застосовуються в сучасних сис­темах шифрування, автентифікації, цифрового підпису, генерації ключів тощо. Незважаючи на помітний прогрес у розробці різноманітних атак на “конкретні” геш-функції, розуміння закономірностей, що лежать в основі зазначених атак, визначення умов їх застосовності та розробка методів оцінювання їх ефективності є предметом активних по­дальших досліджень. Метою статті є встановлення загальних умов, що визначають практичну стійкість широкого класу геш-функцій, які базуються на регістрах зсуву, відносно атак, спрямованих на побудування колізій їх стискуваль­них функцій. Показано, що задача побудування колізій зводиться до розв’язання автоматних рівнянь відносно двійко­вих невідомих, які задовольняють певним обмеженням. При цьому множини всіх розв’язків таких рівнянь (без ураху­вання обмежень) мають простий алгоритмічний опис, що дозволяє перелічувати ці розв’язки в режимі реального часу.
 
Publisher National Aviation University
 
Contributor —
—
—
 
Date 2014-05-23
 
Type —
—
—
 
Format application/pdf
 
Identifier http://jrnl.nau.edu.ua/index.php/ZI/article/view/6277
10.18372/2410-7840.16.6277
 
Source Ukrainian Information Security Research Journal; Том 16, № 1 (2014); 33-40
Защита информации; Том 16, № 1 (2014); 33-40
Захист інформації; Том 16, № 1 (2014); 33-40
 
Language uk
 
Rights Authors who publish with this journal agree to the following terms: Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
Авторы, публикующие в данном журнале, соглашаются со следующим: Авторы сохраняют за собой авторские права на работу и предоставляют журналу право первой публикации работы на условиях лицензии Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным сохранением ссылок на авторов оригинальной работы и оригинальную публикацию в этом журнале.Авторы сохраняют право заключать отдельные контрактные договоронности, касающиеся не-эксклюзивного распространения версии работы в опубликованном здесь виде (например, размещение ее в институтском хранилище, публикацию в книге), со ссылкой на ее оригинальную публикацию в этом журнале.Авторы имеют право размещать их работу в сети Интернет (например в институтском хранилище или персональном сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению и большему количеству ссылок на данную работу (См. The Effect of Open Access).
Автори, які публікуються у цьому журналі, погоджуються з наступними умовами: Автори залишають за собою право на авторство своєї роботи та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons Attribution License, котра дозволяє іншим особам вільно розповсюджувати опубліковану роботу з обов'язковим посиланням на авторів оригінальної роботи та першу публікацію роботи у цьому журналі.Автори мають право укладати самостійні додаткові угоди щодо неексклюзивного розповсюдження роботи у тому вигляді, в якому вона була опублікована цим журналом (наприклад, розміщувати роботу в електронному сховищі установи або публікувати у складі монографії), за умови збереження посилання на першу публікацію роботи у цьому журналі.Політика журналу дозволяє і заохочує розміщення авторами в мережі Інтернет (наприклад, у сховищах установ або на особистих веб-сайтах) рукопису роботи, як до подання цього рукопису до редакції, так і під час його редакційного опрацювання, оскільки це сприяє виникненню продуктивної наукової дискусії та позитивно позначається на оперативності та динаміці цитування опублікованої роботи (див. The Effect of Open Access).
 

Технічна підтримка: НДІІТТ НАУ