О выработке неперебираемых ключей на основе перебираемых паролей

Криптографические протоколы — фундамент безопасного сетевого соединения и конфиденциального обмена информацией. На сегодняшний день существует большое количество самых разных протоколов для самых разных целей. Многие из этих протоколов (например, TLS, Kerberos) на слуху даже у людей, тесно не связанных с криптографией. Они распространены повсеместно и зачастую уже давно являются частью популярных информационных систем.

Однако существует тип протоколов, который последнее время набирает все большую популярность, но все еще не является широко известным — протоколы выработки общего ключа с аутентификацией на основе пароля. К таким протоколам относится российский протокол SESPAKE (Security Evaluated Standardized Password Authenticated Key Exchange), с появлением которого в России и возникла необходимость в рассмотрении особенностей протоколов подобного типа. Целью данной статьи является скорее не дать очередное формальное описание нового протокола, а помочь читателю уловить его основную идею и особенности и понять, почему в нём присутствуют те или иные шаги, почему они важны и чем подобный класс протоколов отличается от всего, что было известно ранее.

Немного истории

В 1976 году Уитфилд Диффи и Мартин Хеллман предложили простую, но гениальную идею выработки общего секретного ключа — небезызвестный протокол Диффи-Хеллмана.

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

Стойкость этого протокола по отношению к пассивному противнику основывается на так называемой задаче CDH, которая считается вычислительно «сложной» (если говорить неформально, то для такой задачи не существует эффективных алгоритмов решения). Формулировка этой задачи выглядит следующим образом: зная значения , , вычислить значение .

К сожалению, протокол Диффи-Хеллмана имеет один фундаментальный недостаток: он не является безопасным, если в канале передачи присутствует активный противник (см. атаку «Человек посередине» ). Причина этой уязвимости кроется в отсутствии механизма осуществления аутентификации, т.е. стороны не имеют возможности в ходе протокола каким-либо образом удостовериться, что общий ключ выработан совместно с честным абонентом.

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

Возникает вопрос, можем ли мы использовать в качестве секрета короткий и легко запоминающийся пароль? Как только возникает слово «пароль», многим чуть ли не рефлекторно хочется сказать, что высокой стойкости априори добиться нельзя, т.к. пароль можно быстро восстановить простым перебором или по словарю. Ниже будет показано, что это не всегда так.

Для начала, рассмотрим следующую схему выработки ключа, в которой к протоколу Диффи-Хеллмана добавляется этап аутентификации с использованием секретной величины:

Здесь — некоторая хэш-функция, – секретная предварительно согласованная величина, , — информация, используемая для аутентификации. Легко заметить, что секрет никак не используется на этапе выработки общего ключа.

Чем же плох этот пример в случае, когда величина является обычным паролем? Как правило, пароль — величина малоэнтропийная (т.е. состоит из 4–6 символов, например, PIN), следовательно, перебор всех возможных значений пароля является вполне выполнимой задачей для противника. Поэтому фундаментальным требованием к протоколам, использующим короткий пароль, является стойкость к так называемой offline dictionary атаке. Это свойство должно достигаться за счет того, что информация, которую может получить как пассивный, так и активный противник в ходе выполнения протокола, не дает критерия для отбраковки неверных паролей в режиме offline, т.е. для нас идеален вариант, когда противник не может найти пароль с помощью перебора всех возможных значений, количество которых невелико, без взаимодействия с пользователем. Возвращаясь к примеру, зададимся вопросом: решая проблему аутентификации, не даем ли мы противнику критерий отбраковки пароля? Чтобы на него ответить, рассмотрим следующую атаку:

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

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

Эта идея легла в основу нового подхода, а именно протоколов выработки общего ключа с аутентификацией на основе пароля (PAKE).

Протоколы PAKE

Первый протокол типа PAKE был предложен еще в 1992 году Стивеном Белловином и Майклом Мерритом. Этот протокол предполагал, что для решения проблемы аутентификации субъекты, желающие выработать общий ключ, используют некоторый легко запоминающийся пароль, известный только им. Главным отличием протоколов типа PAKE от рассматриваемого выше примера является тот факт, что пароль используется уже на этапе выработки общего ключа.

При этом основными требованиями, которые предъявляются к такому протоколу, являются:

• обеспечение аутентификации для участников протокола;
• отсутствие у противника возможности получить критерий для перебора пароля.

Попробуем понять, сложно ли построить подобный протокол и какими особенностями он должен обладать. Для этого рассмотрим простейший пример-прототип протокола PAKE:

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

Посмотрим, уязвима ли подобная схема к offline dictionary атаке. Пассивному противнику, прослушивающему канал передачи, доступны значения и – открытые ключи Диффи-Хеллмана, замаскированные значением , и аутентификационная информация и . Перебирая пароли, он может «снимать» маски со значений и , получая при этом предполагаемые значения и . Но противник может получить критерий для перебора паролей, только если он умеет решать вычислительно «сложную» задачу CDH для демаскированных значений и , то есть по значениям и получать ключ (критерием правильности пароля при этом будет получение верной аутентификационной информации на опробуемом ключе ).

В случае активного противника данная схема всё-таки имеет определенные уязвимости. Рассмотрим следующую атаку на схему, где дискретные логарифмы одного порождающего элемента относительно другого известны. Для простоты рассмотрим случай, когда .

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

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

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

Вывод №1: При формировании эфемерного открытого ключа и парольной «маски» необходимо использовать разные порождающие элементы, причем дискретные логарифмы одного по основанию другого должны быть неизвестны.

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

1. Сгенерировать случайную строку .
2. Положить .
3. Проверить, что – порождающий элемент, иначе вернуться к шагу 1.

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

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

Рассмотрим атаку в такой модели противника, где:

• во взаимодействии участвуют обе стороны;
• противнику известны ключи и (к примеру, из-за несанкционированного доступа, использования их в уязвимых криптоалгоритмах и пр. ).

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

От этой уязвимости можно избавиться, если использовать в протоколе хэш-функцию:

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

Вывод №2: Хэшируем вырабатываемый ключ.

Итак, нам удалось построить простейший прототип протокола выработки неперебираемых ключей на основе перебираемых паролей. Конечно, рассмотрение конкретных атак и применение известных методов защиты от них не гарантируют, что разрабатываемый протокол будет стойким, так как не представляется возможным учесть все существующие, но пока неизвестные атаки. В этом случае на помощь приходят методы математической криптографии, которые позволяют получать оценки стойкости протоколов в определенных моделях безопасности. Если рассуждать неформально, для протоколов типа PAKE данные оценки должны строго доказывать, что самой лучшей тактикой для противника является опробование пароля в ходе попытки установить соединение, честно следуя протоколу. Подобные оценки и были получены для протокола SESPAKE.

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

На практике

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

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

Можно выделить два основных вида ключевых носителей, использующих пароль: пассивное хранилище и активный токен.

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

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

Схема работы ключевых носителей

Носитель-хранилище:

Активный токен:

Свойства ключевых носителей обоих описанных выше типов имеют достаточно строгие условия их применения, так как оба этих ключевых носителя нестойки, если злоумышленник находится в канале связи. В случае использования носителя-хранилища злоумышленник просто видит ключ, в случае же активного носителя он не сможет получить доступ к ключу, но сможет узнать пароль, а значит стать для носителя легитимным субъектом – кто знает пароль, тот и прав! В таком случае при краже устройства злоумышленник сможет воспользоваться токеном для совершения необходимых ему операций с ключом. В криптографии такая угроза называется селективной подделкой: злоумышленник может подписать нужные ему данные, не зная ключ.

ФКН или в игру вступает SESPAKE

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

Схема работы функционального ключевого носителя (ФКН)

Общая схема их работы ФКН выглядит так:

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

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

Протокол SESPAKE

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

Разработка протокола SESPAKE берет свое начало не от абстрактной математической модели, в которой уже давно существуют известные механизмы обоснования стойкости, а связана с конкретным практическим случаем: необходимостью защитить канал между ключевым носителем и провайдером. Таким образом, введенная его разработчиками новая модель противника позволила одновременно и в протоколе, и в его обосновании учесть все важные для практики технические аспекты (например, работу со счетчиками). Познакомиться подробнее с его обоснованием можно в отдельной статье, мы же попробуем понять суть работы протокола.

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

В представленной выше схеме работы протокола тремя цветами выделены его ключевые и уже знакомые нам моменты, аналогичные тем, что описаны в построенном выше прототипе:

1. Величины и аналогичны и , и выступают в роли «маски» (), величины , аналогичны значениям , .
2. В протоколе SESPAKE учитывается вывод №2, поэтому вырабатываемый общий ключ хэшируется.
3. Точно так же, как и в нашем прототипе, протокол состоит из двух этапов: выработки общего ключа и аутентификации. Здесь вместо хэширования ключа на этапе его подтверждения сторонами вычисляется код аутентификации сообщения на вырабатываемом ключе от сформированной определенным образом строки.

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

Выбор точки эллиптической кривой, заданной в форме Вейерштрасса (), может быть осуществлен следующим образом:

1. Сгенерировать случайную строку .
2. Положить .
3. Если значение не является квадратичным вычетом по модулю , перейти к пункту 1.
4. Положить .

Здесь — порядок поля, над которым строится группа точек эллиптической кривой, а в качестве может быть использована, например, хэш-функция ГОСТ Р 34.11-2012.

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

Заключение

В конце 2015 года техническим комитетом по стандартизации TK26 в качестве методических рекомендаций был принят протокол выработки общего ключа с аутентификацией на основе пароля — протокол SESPAKE. Примерно в то же время протокол начали рассматривать в исследовательской рабочей группе по криптографии CFRG (Crypto Forum Research Group), входящей в состав организации IETF/IRTF, занимающейся вопросами международной стандартизации. На данный момент в CFRG ведется обсуждение по стандартизации требований к протоколам типа PAKE, а также выбору протокола в качестве международной рекомендации по использованию. В числе трех основных кандидатов рассматривается протокол SESPAKE, драфт RFC которого сейчас активно разрабатывается российскими специалистами. Познакомившись с такими протоколами, теперь и вы можете предложить свои идеи, поучаствовав в подобных обсуждениях.

Автор: ru_crypt

Источник