Алгебраический ластик

Алгебраический ластик ( AE ) ^{[примечание 1]} анонимном соглашения об — это протокол ключе , который позволяет двум сторонам, каждая из которых имеет пару открытого и закрытого ключей AE, установить общий секрет по незащищенному каналу . ^[1] Этот общий секрет может использоваться непосредственно в качестве ключа или для получения другого ключа , который затем можно использовать для шифрования последующих сообщений с использованием шифра с симметричным ключом . Алгебраический ластик был разработан Ирис Аншель, Майклом Аншелем, Дорианом Голдфельдом и Стефаном Лемье. SecureRF владеет патентами на этот протокол. ^[2] и безуспешно пытались (по состоянию на июль 2019 г.) стандартизировать протокол как часть ISO/IEC 29167-20, ^[3] стандарт безопасности устройств радиочастотной идентификации и беспроводных сенсорных сетей .

Параметры набора ключей [ править ]

Прежде чем две стороны смогут установить ключ, они должны сначала согласовать набор параметров, называемый параметрами набора ключей. Эти параметры включают в себя:

$N$ , количество прядей в косе,
$q$ , размер конечного поля $\mathbb {F} _{q}$ ,
$M_{*}$ , исходная начальная матрица NxN в $\mathbb {F} _{q}$ ,
$\mathrm {T}$ , набор $N$ элементы в конечном поле $\mathbb {F} _{q}$ (также называемые Т-значениями) и
$A,B$ набор сопряженных элементов в группе кос, предназначенных для коммутации друг с другом.

Электронное умножение [ править ]

Основная операция Алгебраического ластика — это односторонняя функция, называемая E-умножением. Дана матрица, перестановка, генератор Артина. $\beta$ в группе кос и T-значениях применяется E-умножение путем преобразования генератора в цветную матрицу Бурау и перестановку кос, $(CB(\beta ),\sigma _{\beta })$ , применяя перестановку и T-значения, а затем умножая матрицы и перестановки. Результатом E-умножения является пара матрица и перестановка: $(M',\sigma ')=(M,\sigma _{0})*(CB(\beta ),\sigma _{\beta })$ .

Протокол установления ключа [ править ]

Следующий пример иллюстрирует, как создать ключевое учреждение. Предположим, Алиса хочет установить общий ключ с Бобом , но единственный доступный канал может быть подслушан третьей стороной. Первоначально Алиса и Боб должны согласовать параметры набора ключей, которые они будут использовать.

Каждая сторона должна иметь пару ключей, полученную из набора ключей, состоящую из закрытого ключа (например, в случае Алисы). $(m_{A},\mathrm {B} _{a})$ где $m_{A}$ представляет собой случайно выбранный полином исходной матрицы $m_{A}=\sum _{i=0}^{N-1}{a_{i}M_{*}^{i}}$ и коса, которая представляет собой случайно выбранный набор сопряженных и обратных чисел, выбранных из параметров набора ключей (A для Алисы и B для Боба, где (для Алисы) $\mathrm {B} _{a}=\prod _{i=1}^{k}A_{i}^{\pm 1}$ ).

На основе материала своего закрытого ключа Алиса и Боб вычисляют свой открытый ключ. $(Pub_{A},\sigma _{a})$ и $(Pub_{B},\sigma _{b})$ где, например, $(Pub_{A},\sigma _{a})=(m_{A},id)*b_{a}$ , то есть результат E-умножения частной матрицы и перестановки идентичности с частной косой.

Каждая сторона должна знать открытый ключ другой стороны до выполнения протокола.

Чтобы вычислить общий секрет, Алиса вычисляет $(S_{ab},\sigma _{ab})=(m_{A}Pub_{B},\sigma _{b})*\mathrm {B} _{a}$ и Боб вычисляет $(S_{ba},\sigma _{ba})=(m_{B}Pub_{A},\sigma _{a})*\mathrm {B} _{b}$ . Общий секрет — это пара матрица/перестановка. $(S_{ab},\sigma _{ab})$ , что равно $(S_{ba},\sigma _{ba})$ . Общие секреты равны, поскольку сопряженные множества $A$ и $B$ выбираются для поездок на работу, и Алиса и Боб используют одну и ту же начальную матрицу $M_{*}$ и Т-значения $\mathrm {T}$ .

Единственная информация о ее личном ключе, которую изначально раскрывает Алиса, — это ее открытый ключ. Таким образом, ни одна сторона, кроме Алисы, не может определить закрытый ключ Алисы, если только эта сторона не может решить проблему одновременного поиска разделения сопряженности в группе кос. Закрытый ключ Боба также безопасен. Ни одна сторона, кроме Алисы или Боба, не может вычислить общий секрет, если только эта сторона не может решить проблему Диффи-Хеллмана .

Открытые ключи являются либо статическими (и доверенными, скажем, посредством сертификата), либо эфемерными. Эфемерные ключи являются временными и не обязательно проходят проверку подлинности, поэтому, если требуется аутентификация, гарантии подлинности должны быть получены другими способами. Аутентификация необходима, чтобы избежать атак «человек посередине» . Если один из открытых ключей Алисы или Боба является статическим, то атаки «человек посередине» предотвращаются. Статические открытые ключи не обеспечивают ни прямой секретности , ни устойчивости к компрометации ключей, а также других расширенных свойств безопасности. Владельцы статических закрытых ключей должны проверить другой открытый ключ и применить функцию получения безопасного ключа к необработанному общему секрету Диффи-Хеллмана, чтобы избежать утечки информации о статическом закрытом ключе.

Безопасность [ править ]

Безопасность AE основана на обобщенной задаче одновременного поиска сопряжений (GSCSP). ^[4] внутри группы кос . Это отдельная и сложная задача, отличная от задачи поиска сопряженности (CSP), которая была центральной сложной проблемой в так называемой криптографии группы кос . ^[5] Даже если CSP будет повсеместно нарушен (чего до сих пор не было сделано), неизвестно, как это облегчит взлом GSCSP.

Известные атаки [ править ]

Первая атака Калки, Тейхера и Цабана демонстрирует класс слабых мест, когда $M_{*}$ или $m_{A}$ выбираются случайным образом. ^[6] Авторы Algebraic Eraser выпустили препринт о том, как выбирать параметры, не подверженные атакам. ^[7] Бен-Цви, Блэкберн и Цабан улучшили первую атаку до такой, которая, как утверждают авторы, может нарушить опубликованные параметры безопасности (заявлено, что она обеспечивает 128-битную безопасность), используя менее 8 часов процессора и менее 64 МБ памяти. ^[8] Аншель, Аткинс и Голдфельд отреагировали на эту атаку в январе 2016 года. ^[9]

Вторая атака Мясникова и Ушакова, опубликованная в виде препринта, показывает, что конъюгаты, выбранные с помощью слишком короткой конъюгаторной косы, могут быть разделены, нарушая систему. ^[10] Эта атака была опровергнута Ганнеллсом, показав, что конъюгаторные косы правильного размера не могут быть разделены. ^[4]

В 2016 году Саймон Р. Блэкберн и Мэтью Дж. Б. Робшоу опубликовали ряд практических атак на проект беспроводного протокола ISO / IEC 29167-20 от января 2016 года, включая олицетворение целевого тега с незначительным количеством времени и памяти. и полное восстановление закрытого ключа, требующее 2 ⁴⁹ время и 2 ⁴⁸ память. ^[11] Аткинс и Голдфельд ответили, что добавление хэша или кода аутентификации сообщения в проект протокола позволяет отразить эти атаки. ^[12]

См. также [ править ]

Примечания [ править ]

^ Также называется протоколом соглашения о цветных ключах Бурау ( CBKAP ), протоколом соглашения о ключах Аншеля-Аншеля-Гольдфельда-Лемье , протоколом соглашения о ключах алгебраического ластика ( AEKAP ) и алгебраическим ластиком Диффи-Хеллмана ( AEDH ).

Ссылки [ править ]

^ Аншель, И.; Аншель, М.; Голдфельд, Д .; Лемье, С. (2006). «Ключевое соглашение, алгебраический ластик и облегченная криптография» (PDF) . Алгебраические методы в криптографии . Том. 418. Презрение. Математика: Американское математическое общество. стр. 1–34. ISBN 978-0-8218-4037-5 .
^ Гудин, Дэн (17 ноября 2015 г.). «Почему Algebraic Eraser может оказаться самой рискованной криптосистемой, о которой вы никогда не слышали» . Арс Техника .
^ ISO / IEC AWI 29167-20 – Информационные технологии – Методы автоматической идентификации и сбора данных – Часть 20: Службы безопасности Crypto suite Algebraic Eraser для связи по радиоинтерфейсу. Рабочий проект.
^ Jump up to: ^а ^б Ганнеллс, ЧП (2011). «О криптоанализе обобщенной задачи одновременного поиска сопряжений и безопасности алгебраического ластика». arXiv : 1105.1141 [ cs.CR ].
^ Дехорной, Патрик (2004). «Криптография на основе кос». Теория групп, статистика и криптография . Современная математика. Том. 360. Американское математическое общество. стр. 5–33. CiteSeerX 10.1.1.10.1759 . дои : 10.1090/conm/360/06566 . ISBN 9780821834442 . МР 2105432 .
^ Калка А., Тейчер М. , Цабан Б. (2012). «Краткие выражения перестановок как продуктов и криптоанализ алгебраического ластика». Достижения прикладной математики . 49 (1): 57–76. arXiv : 0804.0629 . Бибкод : 2008arXiv0804.0629K . дои : 10.1016/j.aam.2012.03.001 . S2CID 10040122 .
^ Голдфилд, Д. ; Ганнелс, ЧП (2012). «Поражение атаки линейной алгебры Калки-Тейхера-Цабана на алгебраический ластик». arXiv : 1202.0598 [ cs.CR ].
^ Бен-Цви, А., Блэкберн, Саймон Р., Цабан Б. (2016). «Практический криптоанализ алгебраического ластика» . Достижения криптологии – CRYPTO 2016 . Конспекты лекций по информатике. Том. 9814. Спрингер. стр. 179–189. arXiv : 1511.03870 . CiteSeerX 10.1.1.738.4755 . дои : 10.1007/978-3-662-53018-4_7 . ISBN 978-3-662-53018-4 . S2CID 1277023 .
^ Аншель, И.; Аткинс, Д .; Голдфельд, Д .; Ганнелс, ЧП (2016). «Поражение атаки Бен-Цви, Блэкберна и Цабана на алгебраический ластик». arXiv : 1601.04780 [ cs.CR ].
^ Мясников А.Д., Ушаков А (2008). «Криптоанализ протокола соглашения о ключах Аншеля-Аншеля-Гольдфельда-Лемье». arXiv : 0801.4786 [ math.GR ].
^ Блэкберн, Саймон Р.; Робшоу, MJB (2016). «О безопасности протокола аутентификации алгебраического ластика» (PDF) . Прикладная криптография и сетевая безопасность . Конспекты лекций по информатике. Том. 9696. стр. 3–17. arXiv : 1602.00860 . дои : 10.1007/978-3-319-39555-5_1 . ISBN 978-3-319-39554-8 . S2CID 371335 .
^ Дерек Аткинс ; Дориан Голдфельд (25 февраля 2016 г.). «Решение проблемы беспроводного протокола Диффи-Хеллмана с алгебраическим ластиком» . Архив электронной печати по криптологии . МАКР.

Внешние ссылки [ править ]

Домашняя страница SecureRF

[1] Также называется протоколом соглашения о цветных ключах Бурау ( CBKAP ), протоколом соглашения о ключах Аншеля-Аншеля-Гольдфельда-Лемье , протоколом соглашения о ключах алгебраического ластика ( AEKAP ) и алгебраическим ластиком Диффи-Хеллмана ( AEDH ).

[2] Аншель, И.; Аншель, М.; Голдфельд, Д .; Лемье, С. (2006). «Ключевое соглашение, алгебраический ластик и облегченная криптография» (PDF) . Алгебраические методы в криптографии . Том. 418. Презрение. Математика: Американское математическое общество. стр. 1–34. ISBN 978-0-8218-4037-5 .

[arstechnica-3] Гудин, Дэн (17 ноября 2015 г.). «Почему Algebraic Eraser может оказаться самой рискованной криптосистемой, о которой вы никогда не слышали» . Арс Техника .

[4] ISO / IEC AWI 29167-20 – Информационные технологии – Методы автоматической идентификации и сбора данных – Часть 20: Службы безопасности Crypto suite Algebraic Eraser для связи по радиоинтерфейсу. Рабочий проект.

[gscsp-5] Jump up to: ^а ^б Ганнеллс, ЧП (2011). «О криптоанализе обобщенной задачи одновременного поиска сопряжений и безопасности алгебраического ластика». arXiv : 1105.1141 [ cs.CR ].

[6] Дехорной, Патрик (2004). «Криптография на основе кос». Теория групп, статистика и криптография . Современная математика. Том. 360. Американское математическое общество. стр. 5–33. CiteSeerX 10.1.1.10.1759 . дои : 10.1090/conm/360/06566 . ISBN 9780821834442 . МР 2105432 .

[7] Калка А., Тейчер М. , Цабан Б. (2012). «Краткие выражения перестановок как продуктов и криптоанализ алгебраического ластика». Достижения прикладной математики . 49 (1): 57–76. arXiv : 0804.0629 . Бибкод : 2008arXiv0804.0629K . дои : 10.1016/j.aam.2012.03.001 . S2CID 10040122 .

[8] Голдфилд, Д. ; Ганнелс, ЧП (2012). «Поражение атаки линейной алгебры Калки-Тейхера-Цабана на алгебраический ластик». arXiv : 1202.0598 [ cs.CR ].

[9] Бен-Цви, А., Блэкберн, Саймон Р., Цабан Б. (2016). «Практический криптоанализ алгебраического ластика» . Достижения криптологии – CRYPTO 2016 . Конспекты лекций по информатике. Том. 9814. Спрингер. стр. 179–189. arXiv : 1511.03870 . CiteSeerX 10.1.1.738.4755 . дои : 10.1007/978-3-662-53018-4_7 . ISBN 978-3-662-53018-4 . S2CID 1277023 .

[10] Аншель, И.; Аткинс, Д .; Голдфельд, Д .; Ганнелс, ЧП (2016). «Поражение атаки Бен-Цви, Блэкберна и Цабана на алгебраический ластик». arXiv : 1601.04780 [ cs.CR ].

[11] Мясников А.Д., Ушаков А (2008). «Криптоанализ протокола соглашения о ключах Аншеля-Аншеля-Гольдфельда-Лемье». arXiv : 0801.4786 [ math.GR ].

[12] Блэкберн, Саймон Р.; Робшоу, MJB (2016). «О безопасности протокола аутентификации алгебраического ластика» (PDF) . Прикладная криптография и сетевая безопасность . Конспекты лекций по информатике. Том. 9696. стр. 3–17. arXiv : 1602.00860 . дои : 10.1007/978-3-319-39555-5_1 . ISBN 978-3-319-39554-8 . S2CID 371335 .

[13] Дерек Аткинс ; Дориан Голдфельд (25 февраля 2016 г.). «Решение проблемы беспроводного протокола Диффи-Хеллмана с алгебраическим ластиком» . Архив электронной печати по криптологии . МАКР.

[примечание 1]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]