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

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

Параметры набора ключей

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

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

E-умножение

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

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

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

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

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

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

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

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

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

Безопасность

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

Известные атаки

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

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

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

Смотрите также

• Обмен ключами Аншель – Аншель – Гольдфельд
• Групповая криптография
• Некоммутативная криптография

Примечания

1. Также называется цветной протокол соглашения о ключах Burau (CBKAP), Протокол соглашения о ключах Аншеля – Аншеля – Гольдфельда – Лемье, Протокол согласования ключей алгебраического ластика (АЕКАП), и Алгебраический ластик Диффи – Хеллмана (AEDH).

Рекомендации

1. Аншель I, Аншель М, Гольдфельд Д., Лемье С. Ключевое соглашение, алгебраический ластик и облегченная криптография Алгебраические методы в криптографии, Contemp. Математика, т. 418, амер. Математика. Soc., Providence, RI, 2006, стр. 1–34.
2. Дэн Гудин (17 ноября 2015 г.). «Почему Algebraic Eraser может быть самой рискованной криптосистемой, о которой вы никогда не слышали». Ars Technica.
3. ISO / IEC AWI 29167-20 - Информационные технологии - Методы автоматической идентификации и сбора данных - Часть 20: Пакет криптографии Алгебраический ластик службы безопасности для радиоинтерфейса. Рабочий проект.
4. Gunnells PE. О криптоанализе обобщенной задачи одновременного поиска сопряженности и безопасности алгебраического ластика. 2011
5. Дехорной, Патрик (2004). «Криптография на основе кос». Теория групп, статистика и криптография. Современная математика. 360. Провиденс, Род-Айленд: Американское математическое общество. С. 5–33. CiteSeerX  10.1.1.10.1759. Дои:10.1090 / conm / 360/06566. ISBN  9780821834442. МИСТЕР  2105432.
6. Калка А, Тейхер М, Цабан Б (2012). "Краткие выражения перестановок как продукты и криптоанализ алгебраического ластика". Успехи в прикладной математике. 49 (1): 57–76. arXiv:0804.0629. Bibcode:2008arXiv0804.0629K. Дои:10.1016 / j.aam.2012.03.001.
7. Голдфилд D, Gunnels PE. Отражение атаки линейной алгебры Калка-Тейхера-Цабана на алгебраический ластик, 2012
8. Бен-Цви, А., Блэкберн, Саймон Р., Цабан Б. (arXiv: 1511.03870 [math.GR]) Практический криптоанализ алгебраического ластика, CRYPTO 2016.
9. Аншель I, Аткинс Д., Гольдфельд Д., Gunnels PE. (arXiv: 1601.04780 [cs.CR]) Отражение атаки Бен-Цви, Блэкберна и Цабана на алгебраический ластик, 2016
10. Мясников А.Д., Ушаков А. Криптоанализ протокола согласования ключей Аншеля-Аншеля-Голдфельда-Лемье, 2008
11. Саймон Р. Блэкберн; M.J.B. Робшоу (09.06.2016). «О безопасности протокола аутентификации тегов с алгебраическим стиранием». Прикладная криптография и сетевая безопасность. Конспект лекций по информатике. 9696. С. 3–17. arXiv:1602.00860. Дои:10.1007/978-3-319-39555-5_1. ISBN  978-3-319-39554-8. Международная конференция по прикладной криптографии и сетевой безопасности 2016. Том 9696 из серии Lecture Notes in Computer Science, стр. 3-17. (Препринт )
12. Дерек Аткинс; Дориан Гольдфельд (2016-02-25). "Обращение к протоколу Алгебраического ластика Диффи - Хеллмана по воздуху". МАКР Архив криптологии ePrint.

внешняя ссылка

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