Личностная криптография: рассказ об одной полезной уязвимости

  • Tutorial
image
Асимметричная криптография стала элегантным решением задачи распределения ключей. Но как это часто бывает, то что помогло устранить одну проблему, стало причиной возникновения другой.

Открытый ключ, в силу математических свойств асимметричных криптоалгоритмов является набором случайных бит, не содержащих никакой информации о владельце, поэтому он не может служить средством аутентификации. Этот недостаток стал причиной появления иерархической системы сертификации открытых ключей.
Рассмотрим каким образом происходит аутентификация пользователей в настоящее время:
  1. Алиса проходит процедуру проверки в удостоверяющем центре(УЦ) и получает сертификат
  2. Алиса посылает свой сертификат Бобу
  3. Боб получает сертификат УЦ
  4. С помощью полученных сертификатов Боб производит аутентификацию Алисы

Первым об упрощении этой схемы задумался Ади Шамир в 1984 году. Он предположил, что если бы появилась возможность использовать в качестве открытого ключа имя или почтовый адрес Алисы, то это лишило бы сложную процедуру аутентификации всякого смысла.
Долгое время идея Шамира оставалась всего лишь красивой криптографической головоломкой, но в 2000 году, благодаря одной известной уязвимости в эллиптической криптографии, идею удалось воплотить в жизнь.

Класс уязвимых эллиптических кривых


Эллиптическая криптография построена на предположении о сложности решения задачи дискретного логарифмирования над полем точек эллиптической кривой.
Основное преимущество «эллиптики» перед классической асимметричной криптографией заключается в гораздо меньших размерах ключей. Объясняется это тем, что для классической задачи дискретного логарифмирования существуют так называемые субэкспоненциальные алгоритмы решения, имеющие следующую вычислительную сложность image. Поэтому для достижения стойкости порядка 280 необходимо чтобы число p имело размер в 1024 бит.
Для задачи дискретного логарифмирования над точками эллиптической кривой субэкспоненциальных алгоритмов найдено не было. Наиболее быстрые алгоритмы для данного типа задач имеют сложность image. Это позволяет использовать числа размерами всего 160 бит для достижения того же самого порога стойкости в 280.

При этом существует особый класс эллиптических кривых для которых все вышесказанное не совсем верно. Такие кривые называются суперсингулярными. Для суперсингулярных эллиптических кривых найден способ свести задачу дискретного логарифма над точками эллиптической кривой к классической задаче дискретного логарифма. Соответственно, при использовании суперсингулярных кривых основное преимущество эллиптической криптографии, становится большим недостатком. Малый размер ключа, свойственный для «эллиптики», позволит с большой эффективность воспользоваться субэкспоненциальным алгоритмом и взломать всю систему.

Немного более подробно все это я описал в одном из своих недавних топиков Эллиптическая криптография: теория. Сегодня же я хочу рассказать о методе, делающем суперсингулярные кривые такими уязвимыми и о протоколе, превратившем этот недостаток в преимущество.

Спаривание Вейля


В 1983 году Менезес, Окамото и Ванстоун показали, что для суперсингулярных кривых существует эффективный способ отобразить пары точек кривой в невырожденный элемент конечного поля.
Изоморфизм использованный ими для этого называется спариванием Вейля. В соответствие двум точкам поля E(Fql) этот изоморфизм ставит элемент поля Fql. Другими словами, спаривание Вейля позволяет отразить множество точек эллиптической кривой в множество вычетов по модулю большого числа.

Пусть (G1,+) — группа точек эллиптической кривой. И (G2, *) — группа вычетов по модулю большого числа. И пусть две эти группы изоморфны относительно спаривания Вейля ex. Спаривание Вейля обладает следующими свойствами:
  1. Тождественность: для всех выполняется
  2. Билинейность: для всех выполняется
  3. Невырожденность: Для всех , таких что выполняется
  4. Практическая эффективность: для всех P и R числа допускают эффективное вычисление

Из билинейности следует, что . Таким образом, для решения задачи дискретного логарифмирования на эллиптических кривых с помощью спаривания Вейля необходимо вычислить пару и . Обладая двумя этими элементами группы G2 можно применить субэкспоненциальный алгоритм для поиска n.

Именно спаривание Вейля делает суперсингулярные кривые бесполезными в алгоритмах ЭЦП. С другой стороны, оно же помогло реализовать идею Шамира.

Задача принятия решения Диффи-Хеллмана


Основополагающими проблемами современной асимметричной криптографии на эллиптических кривых являются:
  • Задача дискретного логарифмирования. Даны две точки кривой P и Q. Необходимо найти число a, такое что Q=aP. На сложности этой задачи основан алгоритм цифровой подписи ECDSA.
  • Вычислительная задача Диффи-Хеллмана. Даны три точки кривой: P, aP, bP. Необходимо вычислить элемент abP. Эта задача лежит в основе алгоритма распределения ключей ECDH.

Помимо этого есть еще один тип задач, которые так же трудноразрешимы как и две предыдущие, но имеют эффективное решение для случая суперсингулярных кривых.

Задача принятия решения Диффи-Хеллмана.
Даны четыре точки кривой P, aP, bP, cP. Необходимо определить выполняется ли равенство a=bc.
Прежде чем описать как спаривание Вейля помогает решить данную задачу, замечу что свойство тождественности для точек P и Q, таких что Q=aP, приводит к довольно неудобному результату. Согласно этому правилу отображение пары P и Q равняется единице .
Чтобы исправить этот недостаток, необходимо найти другую точку такого же порядка, что и Q, но при этом линейно независимую от P.
Существует специальный метод, называемый деформирующем отображением, обозначаемым как F(P). При использовании деформирующего отображения спаривание Вейля записывается как: .
Выражение не будет равняться единице, т.к. точка F(P) линейно независима от P. Эта операция называется модифицированным спариванием Вейля.

Рассмотрим теперь задачу принятия решения Диффи-Хеллмана. Вычислим пару и . Учитывая, что , равенство будет выполнятся только при условии, что a=bc.

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

Личностная криптография. Неинтерактивная схема разделения ключей SOK


Вернемся теперь к основной теме этого топика. А именно, к проблеме аутентификации ключей.

В 2000 году группа исследователей Сакаи, Огиши, Касараха разработала метод разделения ключей, похожий на протокол Диффи-Хеллмана. Но отличающийся от последнего тем, что для получения единого ключа шифрования, пользователям Алисе и Бобу не нужно обмениваться открытыми ключами. Вместо этого, в качестве открытых ключей они используют имена друг друга. Из-за того, что протокол не предусматривает участия второй стороны для получения ключа, он получил определение неинтерактивный.

Неинтерактивный протокол SOK(в честь первых букв имен его создателей) состоит из следующих частей.

Установка параметров системы
В протоколе участвуют три стороны: Алиса, Боб и Трент(доверенный центр производящий генерацию ключей и удостоверяющий личность пользователей).

Первая часть протокола производится непосредственно Трентом. Он выполняет следующие операции.
  1. Генерирует две группы (G1,+) и (G2,*), для которых выполняется модифицированное спаривание Вейля e. А затем выбирает произвольный порождающий элемент image.
  2. Случайным образом выбирает число l и устанавливает параметр Ppub=l*P. Число l является главным секретным ключом системы.
  3. Выбирает стойкую криптографическую хэш функцию f. Функция f служит для отображения личной информации пользователя ID, в элемент группы G1.
  4. Оглашает системные параметры (G1, G2, e, P, Ppub, f).

Генерация ключей пользователя
Эта часть тоже выполняется Трентом. Пусть IDA — некий однозначно определяемый идентификатор Алисы. Это может быть полное ее имя или паспортные данные.
Проверив личность Алисы и убедившись, что IDA действительно принадлежит ей, Трент выполняет следующие действия.
  1. Вычисляет элемент группы G1 как PID = f(IDA ).
  2. Устанавливает закрытый ключ Алисы SIDa = l* PIDa

Следует отметить, что секретность закрытого ключа Алисы основана на задаче дискретного логарифмирования над точками эллиптической кривой. А так как мы используем слабый класс эллиптических кривых, размеры ключей должны соответствовать порядка 1024 бит, как и в случае с классической асимметричной криптографией.

Алгоритм разделения ключа
Идентификаторы Алисы и Боба IDA и IDB известны обоим партнерам. Следовательно они могут вычислить элементы группы G1 PA=f(IDA) и PB=f(IDB).
Для генерации общего ключа KAB Алиса вычисляет .
Боб в свою очередь для получения общего ключа с Алисой вычисляет .
Учитывая свойство билинейности независимо друг от друга они получают один и тот же элемент группы G2: .

Преимущества и недостатки личностной криптографии


Преимущества
Неинтерактивность присущая личностной криптографии дает им одно очень серьезное преимущество. Процедура обмена открытыми ключами полностью теряет свою актуальность.
Нет необходимости ждать получения сертификата другой стороны для установления связи. Достаточно использовать идентификационные данные партнера для генерации общего ключа.

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

Недостатки
Одним из них является то, что Трент участвующий в генерации закрытых ключей будет обладать возможностью расшифровки абсолютно всех сообщений в сети. Поэтому скорее всего использовать личностную криптографию можно будет только в небольших сетях, имеющих определенное доверенное лицо.

Второй недостаток заключается в том, что пока до сих пор неясно что делать в случае компрометации закрытого ключа пользователя. Задача неинтерактивного аннулирования ключей до сих пор открыта.

Однако несмотря на эти существенные недостатки личностная криптография выглядит весьма привлекательной технологией. И как знать, как бы все обернулось, если бы в 1984 году Шамир нашел такое интересное решение для своей головоломки.

Комментарии 24

    +11
    Вроде бы и не совсем эльфийский… а всё-равно прочесть не удаётся…
    Можно как-то, в общих чертах, ближе к русскому объяснить, или показать на примере любого из ЯП (адекватных, разумеется, а не brainfuck'оподобных)?
      +3
      ИМХО, эльфийский гораздо проще прочитать, чем эту статью :) Думаю, это потому, что тут вникать приходится.
      +2
      Вот еще недостаток: эта схема требует однозначного идентификатора для пользователя, а что если имена у пользователей одинаковые? Или паспортные данные в двух разных странах одинаковые? Вводить централизованную систему выдающую идентификаторы? Ну так сейчас почти то же самое, только выдают сразу ключи :)

      Хотя чисто теоретически схема очень интересная.
        0
        Идентификаторы Алисы и Боба IDA и IDB известны обоим партнерам.

        А откуда они могут быть известны?
          0
          Предполагается что Боб хочет написать письмо человеку с именем Алиса. Он не заморачивается насчет ключей. Просто использует ее имя — ID.
            0
            Но тогда получается, что её имя должно быть уникальным, однако Алис много, поэтому ФИО в качестве ID не подходит. Как быть?
              0
              Добавлять к имени дату рождения например. Проблемы конечно есть но они решаемы. В теории очень красивая система получилась.
                0
                А на практике Трентом будет управлять АНБ (если использовать в глобальных масштабах)
                  +1
                  Ну если начать с того, что у человека может быть несколько имён в одно и то же время, имя может не иметь фиксированной длинны, иметь огромную длину или не подлежать записи, а может и не быть имени вовсе…
            +2
            Открытый ключ… не может служить средством аутентификации
            Эм… Вы перепутали понятия. Криптография как раз таки и решает задачу аутентификации. И в чистом виде (без PKI, например) не может решить задачу идентификации.
              –1
              Эм… это вы что то путаете. Сама по себе асимметриная криптография не решает ни ту ни другую проблему. А вот PKI да решает проблему аутентификации.
                0
                Ну так как, объясните каким образом криптография с открытым ключом решает проблему аутентификации без использования PKI?
                  0
                  Типичный пример, аутентификация по ключам в SSH.
                  Вообще процессы аутентификации и идентификации очень тяжело разделить, но всё же эта грань в теории существует, на практике же они слиты воедино.
                    +1
                    В этом случае либо была аутентификация по логину-паролю, либо админ/оператор (уполномоченное лицо) закинули публичный ключ на сервер, выполнив роль PKI.
                      0
                      Ну если так к делу подходить, то конечно. ИМХО, Вы как-то совсем до безумия объяснение довели.
                        0
                        Почему до безумия? Все правильно написали выше. Без pki ssh лишается смысла. Т.к. любой может прислать вам неизвестный открытый ключ и сказать что это ключ от сервера. Поэтому к асимметричной криптографии нужен дополнительный инструмент аутентификации. Сами по себе ключи не способны ни аутентифицировать вас ни идентифицировать.
                          0
                          Это всё равно, что рассуждать, что сам по себе карандаш писать не будет, ему нужно(ен) что-то(кто-то) что(кто) будет его применять.
                          PKI в контексте ssh аутентификации по ключам заменяет заранее известный fingerprint сервера (отнесённый ручками, прописанный в DNS, и т.п.), а не то что публичный ключ оказался на сервере. Должны же быть хоть какие-то начальные условия.
                            +1
                            То о чем мы сейчас говорим, это несомненно аутентификация с применением криптографического ключа. Тут я с вами согласен. Но вы упускаете то, что прежде чем использовать ключ для аутентификации пользователя, сперва необходимо выполнить аутентификацию самого ключа. В нашем случае, сверить fingerprint.

                            Не подумайте, что я докапываюсь. Просто есть такое понятие как аутентификация ключа, которую без PKI или дополнительного защищенного канала нельзя произвести. А без аутентификации ключа в свою очередь нельзя произвести аутентификацию пользователя.

                            Это подводит нас к началу нашей дискуссии. А именно к тому, что ключ не прошедший аутентификацию(PKI или другой метод) не может служить для аутентификации субьекта.
                +1
                Давно хотел спросить и топик подходящий: есть у меня идея использовать в ручной подписи числа в подписи. Допустим сначала пишу число в место «подписать здесь», а потом поверх него уже свой росчерк. Какой алгоритм подобрать без необходимости помнить число, написанное в предыдущем договоре и чтобы в уме достаточно просто считалось?
                  +1
                  Эммм, первое, что в голову пришло, с потолка — используйте контрольную сумму по алгоритму, известному только вам по дате или лучше номеру договора, либо по любому другому уникальному контенту в договоре…
                    0
                    Весьма сомнительна практическая часть такого действа, если во многих важных документах будут сравнивать подпись с подписью в паспорте.
                    Договор № 969\12 от 20.11.14 к примеру можно просто сложить в 3645.
                    Я вот не люблю ручную подпись тк она в очень редких случаях совпадает с нужным эталоном. За прошлый год мне пришлось поставить свою подпись более 30 000 раз и я помню, что далеко не всегда она была нормальной: сильно зависела от окружающего (настроения, скорости письма и тд).

                    Можно пойти дальше и к примеру использовать перьевую ручку добавляя в чернила вещества которые светятся в УФ. Осталось только решить проблему — что делать если забыл её дома или закончились чернила.
                    +1
                    Не понял, чем Трент отличается от удостоверяющего центра? Кроме того, что он знает еще больше, сами закрытые ключи, что делает всю систему бесполезной.
                      0
                      Почему сразу бесполезной? Можно использовать в корпоративных сетях, где сервер может выполнять роль Трента.
                      А про отличие от стандартной PKI с сертификатами. Оно налицо. Процедура аутентификации сокращается до одного шага. Остается только выдача ключа Алисе Трентом. Никаких пересылок сертификатов и их проверок.
                      0
                      А я работал с Ади Шамиром в одной фирме :) Действительно таких людей в мире не много.

                      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.