Приветствую, Хабр! Одной из интереснейших тем для обсуждения из современной криптографии, на мой взгляд, является тема эволюции криптографических ключей и связанных с ними протоколов, обеспечивающих наличие ряда дополнительных полезных свойств систем, основанных на асимметричных криптоалгоритмах.
Различные методы эволюции ключей (терминология не устоялась, предпочитаю использовать такой перевод словосочетания «key-evolving techniques») асимметричных криптоалгоритмов позволяют защититься от компрометации секретных ключей путем периодической модификации ключевых пар. Подобная защита направлена не на предотвращение компрометации секретного ключа, а на минимизацию последствий такой компрометации: поскольку ключи периодически модифицируются, эволюционируют, данные методы позволяют ограничиться отрицательным воздействием компрометации ключа на свойство целостности или конфиденциальности сообщений, зашифрованных или подписанных только в течение определенного, относительно короткого периода, оставляя защиту сообщений других периодов ненарушенной.
Большинство протоколов с эволюцией ключей подразумевает достаточно активный обмен сообщениями между сторонами защищенного обмена данными. При этом бывают сценарии, когда возможности для интерактивного взаимодействия у сторон отсутствуют.
Далее предлагаю обсудить различные известные методы эволюции ключей (обеспечивающие различные полезные свойства криптосхем: от секретности в будущем до устойчивости к вторжениям), после чего описать возможный вариант протокола модификации ключевых пар для неинтерактивных применений.
Компрометация секретного ключа: чем опасна и как бороться
Безопасность применения любой криптографической системы обычно напрямую зависит от соблюдения конфиденциальности секретных ключей в течение всего времени использования таких систем (компрометация секретного ключа недопустима даже после окончания срока его действия, поскольку она нарушит конфиденциальность сообщений, защищенных с использованием этого ключа ранее). Такая безопасность обычно обеспечивается как различными техническими мерами, предотвращающими компрометацию ключа, так и инструктированием пользователей о необходимости держать секретные ключи в строгом соответствии с их статусом, обеспечивая отсутствие возможностей несанкционированного доступа к ключу.
Тем не менее, компрометация секретных ключей при их практическом применении происходит регулярно, в т. ч. по следующим причинам:
хранение ключей без адекватной защиты в памяти различных устройств общего назначения, к которым возможен доступ напрямую или по сети (что становится всё более актуально при использовании мобильных телефонов и прочих беспроводных средств связи);
использование ключей в многопользовательских средах без строгой изоляции пользовательских данных;
активный взлом криптографических средств или используемых ими криптоалгоритмов (отметим, что успешный взлом именно криптографических алгоритмов происходит несравнимо реже, чем взлом их реализаций в различных криптосредствах);
прямое воздействие на пользователей-владельцев секретных ключей: от методов социальной инженерии до шантажа или принуждения (как было сказано в докладе [1] (перечень литературы приведен в конце статьи), обычно значительно легче получить секретный ключ у наивного пользователя, чем взламывать используемый криптоалгоритм).
Поскольку секретный ключ является важнейшим элементом обеспечения безопасности функционирования криптосистемы, его компрометация может привести к критическому нарушению работы такой системы (в части конкретного пользователя, допустившего компрометацию своего ключа), безопасность которой в целом может быть поставлена под сомнение после данного события. Следовательно, при разработке любой криптосистемы нельзя полагаться на обязательное сохранение конфиденциальности секретных ключей; вместо этого необходимо явным образом разрабатывать меры по восстановлению работы системы после компрометации ключа. В известной работе [2] рекомендуется при разработке криптосистемы обеспечить следующие ее свойства:
сделать получение секретного ключа злоумышленником настолько трудоемким и дорогостоящим, насколько это возможно;
когда произойдет компрометация секретного ключа, ее последствия должны быть минимальными (при разработке необходимо исходить из предположения, что компрометация секретного ключа рано или поздно обязательно произойдет);
обеспечить возможность восстановления работы системы после компрометации.
Проблема восстановления работы после компрометации секретного ключа в асимметричных криптосистемах традиционно решается путем выполнения следующих шагов:
Отзыв сертификата соответствующего открытого ключа.
Генерация новой ключевой пары вместо скомпрометированного секретного и отозванного открытого ключей.
Повторная сертификация открытого ключа и распространение/публикация сертификата.
Данная последовательность восстановления имеет три ярко выраженных недостатка:
она включает в себя относительно сложные и достаточно затратные по времени действия;
она инициируется только после обнаружения факта компрометации секретного ключа (а ее не всегда удается обнаружить);
она позволяет восстановить работу системы, но не дает явного ответа на вопрос, можно ли считать доверенными все подписи, сгенерированные до момента компрометации секретного ключа, с помощью которого они были вычислены.
Немного подробнее о доверии после компрометации секретного ключа
Если строго подходить к вопросу доверия при использовании электронной подписи, то после обнаружения факта компрометации секретного ключа все подписи, сгенерированные с использованием этого ключа до его компрометации, нельзя считать доверенными. Видимо, за исключением только одного случая: когда возможно доказать точное время события компрометации ключа (и это время – позже времени генерации обсуждаемых подписей) и отсутствие событий компрометации этого же ключа ранее. Согласитесь, что такое доказательство не является простым.
В связи с таким подходом, нечестный пользователь может допустить намеренную компрометацию своего секретного ключа с целью поставить под сомнение свои предыдущие подписи (т. е. отказаться от них). Это уже явное нарушение одного из базовых свойств электронной подписи – неотказуемости.
Ситуация с шифрованием может трактоваться значительно проще: если допущена компрометация секретного ключа, то конфиденциальность всех данных, которые можно с его помощью расшифровать, можно уверенно считать нарушенной.
Таким образом, выглядит весьма желательным наличие у криптосистем следующих свойств:
отсутствие влияния факта компрометации секретного ключа на целостность и конфиденциальность сообщений, подписанных/зашифрованных в прошлом;
простая процедура восстановления работоспособности системы;
независимость инициирования такой процедуры от обнаружения факта компрометации секретного ключа.
Рассмотрим известные подходы к обеспечению данных свойств.
Известные методы эволюции ключей
Несмотря на то, что предложенная Адамом Бэком (Adam Back) в 1997 г. криптосхема NIFS (Non-Interactive Forward Secrecy – «неинтерактивная секретность в будущем»), описанная в публикации [3], строго говоря, не реализует какой-либо метод эволюции ключей, именно его считают основоположником данного направления.
NIFS подразумевает использование последовательности пар ключей, каждая из которых предназначена для применения только в течение определенного интервала времени, по окончании которого секретный ключ использованной пары гарантированно уничтожается (securely erased). При этом секретные ключи генерируются таким образом, чтобы было невозможно вычислить любой из предыдущих ключей, имея текущий.
NIFS позволяет достичь секретности в будущем (forward secrecy/security); под данным термином подразумевается наличие упомянутого выше полезного свойства, когда компрометация какого-либо из секретных ключей не влияет на целостность и конфиденциальность сообщений, защищенных в прошлом, до наступления периода использования того ключа, компрометация которого произошла. Отмечу, что концепция секретности в будущем широко известна (в том числе, неоднократно обсуждалась на Хабре) и использование эфемерных ключей, лежащих в ее основе, стало стандартом де-факто для многих применений.
Практически сразу криптосистема NIFS была улучшена Россом Андерсоном (Ross Anderson), который предложил использовать единый открытый ключ вместо необходимой в NIFS последовательности открытых ключей (это было опубликовано значительно позже, в 2002 г., в работе [4]), что значительно упростило работу с такой криптосистемой.
Наконец, в работе [5] было формализовано расширение для произвольного алгоритма электронной подписи, позволяющее достичь свойства секретности в будущем за счет эволюции секретных ключей.
Напомню, что классическая схема электронной подписи состоит из трех процедур: генерации ключей, вычисления и проверки подписи
Процедура генерации ключей KG (Key Generation), в результате работы которой создается пара ключей: секретный SK и открытый PK.
Процедура вычисления подписи Sgn (Signing), принимающая на вход подписываемое сообщение M и секретный ключ SK и вычисляющая подпись S входного сообщения на данном секретном ключе.
Процедура проверки подписи Vf (Verification), принимающая на вход сообщение M, его подпись S и открытый ключ для проверки подписи PK и в результате формирующая битовое значение, показывающее, действительно ли S является верной подписью сообщения M при ее проверке с помощью открытого ключа PK.
Предложенное расширение дополняет существующие процедуры рядом новых параметров, а схему электронной подписи в целом – дополнительной процедурой модификации секретного ключа. Результирующий набор процедур такой схемы электронной подписи выглядит следующим образом:
Процедура генерации ключей KG (Key Generation), которая в качестве входного параметра принимает общее количество периодов времени использования генерируемой ключевой пары T, а в результате своей работы формирует пару ключей: базовый секретный ключ SK0 и соответствующий открытый ключ PK.
Процедура модификации секретного ключа Upd (Update), которая выполняется в начале каждого i-го периода времени, принимает в качестве входного параметра значение секретного ключа предыдущего периода SKi-1 и возвращает секретный ключ текущего периода времени SKi
Процедура вычисления подписи Sgn (Signing), принимающая в качестве входных параметров подписываемое сообщение M, номер текущего периода времени i и секретный ключ текущего периода SKi; в качестве выходного процедура Sgn возвращает значение подписи S сообщения M, вычисленной на секретном ключе SKi, при этом значение i рассматривается как неотрывная часть подписи.
Процедура проверки подписи Vf (Verification), принимающая на вход сообщение M, подпись которого подлежит проверке, саму подпись, представляющую собой пару значений S и i, и открытый ключ PK для проверки подписи; выходным является битовое значение, показывающее, действительно ли S является верной подписью сообщения M (при ее проверке с помощью открытого ключа PK), сгенерированной в течение периода времени i на валидном для того периода секретном ключе.
Что интересно, несколько позже вышла работа, похожим образом распространяющая парадигму эволюции ключей на алгоритмы симметричного шифрования. Однако симметричное шифрование находится за рамками настоящей статьи, поэтому позволю себе порекомендовать читателям самостоятельно найти подробности в находящемся в открытом доступе первоисточнике [6].
Схемы с эволюцией ключей (и электронной подписи, и шифрования) в дальнейшем неоднократно были усилены с целью улучшения их эксплуатационных характеристик. Основными направлениями улучшения были следующие:
улучшение быстродействия;
снятие ограничений на количество периодов времени T;
уменьшение размерности основных параметров (секретных/открытых ключей, подписи, шифртекста), устранение или уменьшение зависимости размерности данных параметров от T.
Тем не менее, следующие основные недостатки всё равно оставались у подобных схем:
они обеспечивают защиту только сообщений, подписанных и/или зашифрованных в прошлом, но не в будущем;
следовательно, сложные и относительно длительные процедуры восстановления работоспособности (отзыв сертификата открытого ключа, выпуск новой пары ключей, сертификация и распространение нового открытого ключа) всё равно остаются востребованными в случае компрометации секретного ключа;
для запуска процедуры восстановления необходимо детектировать компрометацию секретного ключа.
Эти недостатки сподвигли криптологов к поиску новых вариантов схем эволюции ключей, в которых перечисленные проблемы были бы решены.
Одним из таких вариантов является схема с «изоляцией ключа» (key-insulated scheme), предложенная в работе [1]. Данная схема подразумевает использование двух устройств следующим образом:
вычислительное устройство общего назначение (компьютер, смартфон и т. п.), на котором фактически выполняется какая-либо схема электронной подписи с модификацией секретного ключа (существует и аналогичная схема для шифрования [7]);
выделенное устройство, защищенное от несанкционированного доступа (но при этом оно может обладать ограниченными вычислительными ресурсами), хранящее мастер-ключ и принимающее участие в процедуре модификации секретного ключа (в этой процедуре должен также вычислительно участвовать мастер-ключ); второе устройство может подключаться к первому только при необходимости проведения процедуры модификации секретного ключа.
Эта схема несколько напоминает известные схемы шифрования данных с помощью двух устройств: производительного и доверенного (данная идея была сформулирована Мэтом Блейзом (Matt Blaze) еще в 1995 г. в работе [8]). Но при этом такое решение действительно позволяет (при условии сохранения конфиденциальности мастер-ключа и некомпрометации устройства, хранящего мастер-ключ) минимизировать вред от компрометации секретного ключа и обеспечить защиту целостности и/или конфиденциальности сообщений не только в прошлом, но и в будущем – в любое время, исключая тот самый период времени, в котором была допущена компрометация секретного ключа.
Криптосистемы с изоляцией ключа были значительно усилены в работах [9] и [10], в которых были описаны, соответственно, «устойчивые к вторжениям» (intrusion-resilient) схемы электронной подписи и асимметричного шифрования. В данном случае под устойчивостью к вторжениям подразумевается аналогичное схемам с изоляцией ключа свойство сохранения целостности и конфиденциальности сообщений, защищенных как в прошлом, так и в будущем, даже в том случае, если оба из участвующих в вычислениях устройств взломаны (но не одновременно). Если же устройства взломаны одновременно, то криптографические свойства обеспечиваются только для сообщений, защищенных в прошлом, что аналогично свойству секретности в будущем.
Небольшое отвлечение на вопросы терминологии
Каждый раз, рассуждая или читая на эти темы, я удивляюсь, насколько неудачно выбран термин «forward security», а также его относительно устоявшийся перевод на русский язык – «секретность в будущем» (в Википедии предлагается другой перевод – «прямая секретность», но это словосочетание, во-первых, употребляется несравнимо реже, а во-вторых, при его применении первоначальный смысл, на мой взгляд, теряется совсем) – в применении к свойству, когда целостность и конфиденциальность сохраняются для сообщений, защищенных в прошлом. Конечно, имеется в виду, что зашифрованные/подписанные сейчас сообщения будут оставаться защищенными в будущем, даже если когда-нибудь произойдет компрометация используемого в будущем тем же пользователем текущего секретного ключа. Но из самого термина, без «погружения» в тему, это никоим образом не следует.
И аналогичное впечатление производит термин «intrusion-resilient» в применении к описанным чуть ранее криптосистемам, поскольку явной связи со свойством, которое этот термин обозначает, термин не имеет; вместо этого начинаются ошибочные в данном случае параллели с системами IPS (Intrusion Prevention Systems), которые в современной информационной безопасности как раз и принято считать обеспечивающими защищенность от вторжений.
И наоборот, словосочетание «key-insulated scheme» применено абсолютно по делу, поскольку действительно описывает некий механизм изоляции мастер-ключа, позволяющий достичь определенных криптографических свойств.
Также не могу не отметить большую и явно полезную работу по унификации криптографической терминологии, которую недавно провел технический комитет по стандартизации № 26 «Криптографическая защита информации» совместно с Академией криптографии и рядом компаний, работающих в данной отрасли, выпустив предварительный национальный стандарт «Криптографическая защита информации. Термины и определения». В данном стандарте, кстати, «forward secrecy» переводится как «защищенность от чтения назад», что, в принципе, верно отражает смысл данного термина, но пока несколько непривычно.
Еще одно направление развития криптосистем с эволюцией ключей – обеспечение восстановления работы системы после раскрытия секретного ключа под принуждением. В частности, в работе [9] была предложена схема «монотонной подписи» (monotone signature). Суть данной схемы состоит в том, что в случае принуждения пользователь может раскрыть некую часть своего секретного ключа, подпись которым какого-либо сообщения в момент раскрытия будет верной. Но когда пользователь окажется в безопасности, он сможет запустить процедуру модификации своего открытого ключа, которая впоследствии позволит отличать подписи, вычисленные пользователем после модификации, от подписей, вычисленных злоумышленником с помощью той самой части секретного ключа, которая была им получена с помощью силы.
Данная концепция имеет некоторое сходство с системами защиты (в частности, от несанкционированного доступа), имеющими опцию наличия «пароля под принуждением»: находясь под принуждением, пользователь таких систем может выдать ложный пароль, с которым злоумышленник сможет произвести якобы успешный вход в систему, войдя на самом деле в специально подготовленную для такого входа версию, причем такой вход должен вызвать событие информационной безопасности с соответствующей сигнализацией.
Ну и, конечно, монотонные подписи вызывают некоторые сомнения относительно сохранения свойства неотказуемости от подписи: в данном случае пользователь может намеренно создать подписанные документы, подпись которых будет действительна в течение некоторого времени (заранее выбранного пользователем), после чего, выполнив модификацию ключа, пользователь сможет успешно объявить все такие подписи невалидными, поскольку они были сделаны якобы под принуждением.
Отметим, что схемы монотонной подписи не обеспечивают секретность в будущем.
Впоследствии в работе [10] была также предложена универсальная схема электронной подписи, включающая в себя процедуры модификации как секретных, так и открытых ключей и обеспечивающая защиту как от случайной, так и от вынужденной компрометации секретных ключей.
Схемы с эволюцией ключей (прежде всего, обеспечивающие секретность в будущем) активно применяются и в протоколах обмена ключами. В данном случае их использование направлено на то, чтобы компрометация долговременного секретного ключа в будущем не привела к раскрытию сессионных ключей, вычисленных с использованием данного долговременного ключа в прошлом. При этом обеспечение секретности в будущем обычно требует достаточно активного обмена данными между сторонами, хотя бывают и исключения: в частности, в работе [11] был предложен протокол обмена ключами, обеспечивающий секретность в будущем и не требующий какого-либо дополнительного обмена данными, за исключением обмена открытыми ключами.
Свойство устойчивости к вторжениям также оказалось востребовано в протоколах обмена ключами. Например, в докладе [12] был описан протокол обмена ключами, обладающий данным свойством, но при условии наличия у атакующего только узкого канала связи с атакуемыми устройствами, не позволяющего получать достаточную для успешного проведения атаки информацию.
Опишу далее протокол эволюции ключей, обеспечивающий секретность в будущем (а также свойство устойчивости к вторжениям при выполнении ряда условий), но предназначенный для применений, где отсутствует прямой канал связи между сторонами обмена данными.
Протокол эволюции ключей для неинтерактивных применений
Сформулируем основную цель протокола: обеспечение секретности в будущем, а при соблюдении дополнительных условий/ограничений – сохранение целостности и/или конфиденциальности сообщений, подписанных и/или зашифрованных в любые периоды времени (до и после), за исключением тех периодов, где произошла компрометация текущего секретного ключа. Судя по опыту предыдущих исследований в данном направлении, достичь этого можно путем периодической недетерминированной модификации секретных ключей или ключевых пар в целом.
При этом протокол предназначен для применений, где невозможен интерактивный обмен данными. В качестве примера можно рассмотреть приложение электронной почты, в котором передаются защищенные вложения, причем вложения формируются заранее в изолированном контуре, а защита вкладываемого файла (для определенности) представляет собой его подписание и зашифрование симметричным алгоритмом на общем ключе, полученном с помощью секретного ключа отправителя и открытого ключа получателя, скажем, с помощью какого-либо из вариантов алгоритма Диффи-Хеллмана.
При отсутствии прямого канала связи мы не можем синхронно выполнять модификацию ключевых пар на стороне отправителя и получателя, но имеем возможность выполнять такую модификацию поочередно, например:
Обновлять секретный ключ на стороне отправителя каждый раз после его применения для защиты очередного сообщения.
Обновлять открытый ключ на стороне получателя каждый раз после использования текущего открытого ключа для расшифрования полученного сообщения и проверки его подписи.
Для того, чтобы данная схема была работоспособной, необходимо сформулировать следующие основные условия/ограничения ее применения:
для каждой пары пользователей, обменивающихся сообщениями, у каждого из пользователей такой пары должна существовать отдельная пара ключей для связи со вторым пользователем;
обмен сообщениями производится относительно редко.
На первый взгляд, ограничения являются очень серьезными; первое из них вообще приводит к квадратичной зависимости количества ключевых пар от количества пользователей. Однако в реальности количество получателей сообщений электронной почты у каждого из отправителей невелико по сравнению с общим числом пользователей подобных систем; если ввести следующее дополнительное ограничение: «каждый отправитель имеет относительно небольшое количество получателей», – то видно, что применимость системы с таким ограничением остается вполне реальной.
По второму ограничению напомню, что речь идет о подготовке сообщений в изолированном контуре, что подразумевает отсутствие полностью автоматической подготовки/отправки сообщений, выполнение же данных действий преимущественно в ручном режиме приведет как раз к относительно редкому обмену сообщениями.
Опишем протокол эволюции ключей для неинтерактивных применений следующим образом:
I. Подготовительный этап:
1. Процедура генерации ключевой пары GK (отдельной для каждого направления передачи данных каждой парой «отправитель-получатель»), результатом работы которой является секретный ключ SK1 и соответствующий ему открытый ключ PK1.
Открытые ключи впоследствии могут быть сертифицированы и должны быть переданы получателям с помощью какого-либо альтернативного канала связи (отметим, что каждому получателю достаточно иметь открытые ключи только из тех ключевых пар, которые имеют отношение к нему).
II. Действия на стороне отправителя при подготовке каждого сообщения:
2. Защита отправляемого вложения перед отправкой, включающая в себя следующие действия:
генерацию случайного числа R (которое впоследствии будет применено для модификации ключей; о размерности данного числа будет сказано далее) и его включение во вложение;
подписание вложения;
вычисление общего ключа на основе текущего секретного ключа отправителя SKt и открытого ключа получателя PKx (отметим, что нумерация периодов времени у отправителя и получателя может не совпадать, что будет ясно далее) и зашифрование вложения на вычисленном ключе.
3. Модификация секретного ключа отправителя SKt с использованием сгенерированного ранее значения R применением процедуры модификации секретного ключа SUpd (примеры данной процедуры будут приведены далее), в результате чего получается следующая версия секретного ключа SKt+1; гарантированное удаление предыдущей версии секретного ключа.
4. Передача сообщения в контур, подключенный к Интернету, для отправки получателю электронной почтой.
III. Действия на стороне получателя при получении каждого сообщения:
5. Получение сообщения и его передача в изолированный контур.
6. Расшифрование сообщения и проверка его подписи, получение из сообщения значения R.
Вычисление общего ключа для расшифрования сообщения, а также проверка подписи выполняются с использованием текущей версии открытого ключа отправителя PKt.
Отметим, что для шифрования (т. е. в данном случае – вычисления общего ключа) и выполнения процедур электронной подписи могут использоваться различные ключевые пары (это безопаснее), что удваивает общее число ключевых пар. В этом случае модификация сначала секретных, а потом открытых ключей этих ключевых пар выполняется параллельно, дублированием вызовов функций модификации ключей.
7. Модификация открытого ключа отправителя PKt с получением его новой версии PKt+1 (соответствующей новой версии его секретного ключа SKt+1) с помощью процедуры модификации открытого ключа PUpd, на вход которой также подается значение R.
Данный протокол является общим и применимым для различных используемых схем электронной подписи и вычисления общего ключа. Конкретизируем далее его применение для некоторых часто используемых вариантов нижележащих криптоалгоритмов.
Модификация ключей в криптосхемах, основанных на проблеме дискретных логарифмов
Для асимметричных криптографических алгоритмов, основанных на проблеме дискретных логарифмов, в которых открытый ключ PK вычисляется из секретного ключа SK как PK = aSK mod p, где a и p – глобальные параметры криптосхемы, процедуры модификации ключей могут быть определены следующим образом:
SUpd – процедура модификации секретного ключа, принимающая на вход текущее значение секретного ключа SKt и сгенерированное случайное число R и вычисляющая новую версию секретного ключа SKt+1 следующим образом:
SKt+1 = SKt + R.
PUpd – процедура модификации открытого ключа, принимающая на вход текущее значение открытого ключа PKt и значение R, использованное ранее для модификации парного секретного ключа, и вычисляющая новую версию открытого ключа PKt+1 следующим образом:
PKt+1 = PKt * aR mod p.
Если открытый ключ до его модификации PKt соответствовал секретному ключу SKt и при их модификации использовалось одно и то же значение R, то модифицированный ключ PKt+1 продолжает быть парным модифицированному ключу SKt+1, поскольку:
Число R в данном случае должно обладать размерностью, эквивалентной размерности секретного ключа.
Модификация ключей в криптосхемах, основанных на эллиптических кривых
Для асимметричных криптосхем, основанных на использовании эллиптических кривых, в которых открытый ключ PK представляет собой точку на нижележащей эллиптической кривой и вычисляется из секретного ключа SK и базовой точки эллиптической кривой P как PK = SK * P, аналогичные по своему назначению и набору параметров процедуры модификации ключей могут быть определены следующим образом:
· SUpd: SKt+1 = SKt * R.
· PUpd: PKt+1 = PKt * R.
В данном случае, при условии исходного соответствия ключа PKt ключу SKt и использования при модификации одного и того же значения R, соответствие между модифицированными ключами также сохраняется, поскольку:
PKt+1 = SKt+1 * P = SKt * R * P = PKt * R.
Размерность числа R также должна соответствовать размерности секретного ключа.
Обсудим далее преимущества предложенного протокола, а также его недостатки и ограничения.
Недостатки и ограничения предложенного протокола
Ни один из обсуждавшихся ранее методов эволюции ключей не требует модификации ключей каждый раз при формировании зашифрованного и/или подписанного сообщения. Похожая идея – модификация секретного ключа получателя каждый раз после расшифрования зашифрованного сообщения – предлагалась (в числе прочего) в работе [13], но не получила дальнейшего распространения, поскольку для реализации предложенного метода требовалось наличие сложного многостороннего протокола, без которого данная идея была неприменима на практике.
С другой стороны, выполнение модификации ключей после подготовки/обработки каждого сообщения, интуитивно, должно положительно сказаться на безопасности такой криптосхемы за счет уменьшения времени использования каждой версии секретного ключа – действительно, каждая из них используется лишь однократно. Однако такая частота модификации приводит к новым проблемам, требующим решения:
Проблема с эффективностью, поскольку модификацию ключевой пары требуется производить после каждого сообщения.
Необходимость гарантированной доставки каждого сообщения для обеспечения обновления открытого ключа – в противном случае возникает рассинхронизация ключевой пары.
Требуется решение вопроса подтверждения целостности открытых ключей в условиях их постоянной модификации.
Попробую описать возможные решения приведенных проблем.
Предложенный протокол не подразумевает значительной сетевой активности и не предназначен для подобных применений. Наоборот, как было сказано выше, он предназначается для использования в условиях с незначительной активностью сторон обмена данными (выше приводился пример приложений электронной почты, еще один пример – это файлообмен при схожем сценарии). Также предполагается, что инициирование обмена данными (например, отправка сообщения электронной почты или файла) производится пользователем вручную, что, по крайней мере, не может выполняться так же часто, как в случае автоматически инициируемого обмена данными.
Ресурсоемкость же самих операций модификации ключей можно считать незначительной по сравнению с прочими процедурами обеспечения защиты сообщений/файлов: вычисления/проверки подписи, вычисления общего ключа, зашифрования и расшифрования. Следовательно, с учетом вышесказанного, можно утверждать, что существенных потерь в эффективности данный протокол не вносит.
Гарантированная доставка каждого сообщения требуется по той причине, что каждое значение R (передаваемое в составе зашифрованного вложения) должно быть доставлено получателю сообщения для использования в процедуре модификации открытого ключа отправителя (а факт получения защищенного сообщения необходим для инициации такой процедуры). Такие нарушения доставки сообщений, как их потеря или изменение порядка получения относительно порядка отправки, при использовании данного протокола приводят к невосстановимому нарушению обмена защищенными данными для конкретной пары пользователей.
В известных работах для решения схожих проблем предложенных криптосхем требуется наличие следующих нижележащих протоколов (подобные требования необходимо рассматривать как ограничения применения криптосхем, поскольку при отсутствии требуемого протокола криптосхема неработоспособна):
в работе [13] предполагается наличие протокола, обеспечивающего «атомарную доставку» (atomic delivery), где подобное предположение названо «нестандартным, но теоретически приемлемым» (non-standard, but theoretically acceptable); такой протокол позволяет не рассматривать далее любые проблемы, связанные с доставкой сообщений, поскольку они, предположительно, решены на уровне протокола атомарной доставки;
в работе [14] делается менее строгое предположение – что каждое зашифрованное сообщение доставляется получателю «быстро» (in a short time) – по крайней мере, в течение того же промежутка времени, когда оно было отправлено; в противном случае сообщение придет уже после модификации ключей, поэтому оно не может быть расшифровано и должно быть переотправлено.
Вместо атомарной доставки я бы предложил для использования описанного здесь протокола ограничиться более гибкими требованиями:
доставка должна быть гарантированной;
сообщения для одного и того же получателя должны доставляться в том же порядке, в каком они были отправлены (но время доставки при этом не имеет значения).
Следовательно, для работы предложенного протокола необходимо наличие некоего транспортного протокола, обеспечивающего соответствие данным двум требованиям.
Проблемы подтверждения аутентичности и целостности открытых ключей обычно решаются их сертификацией, например, в рамках инфраструктуры открытых ключей. В случае эволюции ключей, как было сказано выше, процесс сертификации открытых ключей становится серьезной проблемой; попытка решить ее классическим путем, т. е. поочередной сертификацией каждой версии открытого ключа с помощью третьей доверенной стороны (например, сертификационного центра), приводит к нежизнеспособности таких схем, поэтому здесь требуется особый подход.
Рассмотрим примеры решения данной проблемы в некоторых из известных схем с эволюцией ключей:
в ряде криптосхем (например, описанных в работах [5] и [14]) модификациям подвержен только секретный ключ, а единый открытый ключ соответствует любой из версий секретного ключа; это позволяет сертифицировать и распространять такой открытый ключ обычным образом – как в схемах без эволюции ключей;
сертификация каждой из версий открытого ключа после модификации с использованием предыдущей версии собственного секретного ключа до ее гарантированного удаления предложена в работе [10];
в работе [15] с той же целью предлагается использовать базовую версию секретного ключа, которая не удаляется.
В случае применения описанного здесь протокола предлагается обеспечить аутентичность и целостность открытых ключей следующим образом:
Сертифицировать изначально распространяемые открытые ключи обычным образом (с помощью сертификационного центра).
Каждую новую версию открытого ключа помещать в память с однократной записью (WORM – Write Once Read Many), где целостность будет обеспечена свойствами памяти.
Предположения о наличии в системе подобной памяти, не допускающей модификации записанных туда данных, считаются приемлемыми и относительно легко реализуемыми на практике. Пример подобного требования о наличии памяти с определенными свойствами для реализации системы с эволюцией ключей можно найти, в частности, в работе [16]. Возможно также, что при работе на доверенном компьютере в изолированном контуре требование о наличии WORM-памяти является чрезмерным.
Еще раз явно сформулируем все ограничения и предположения описанного протокола
обмен сообщениями производится относительно редко;
каждый пользователь каждой пары «отправитель-получатель» должен иметь отдельную пару ключей для связи со вторым пользователем пары;
значения R должны быть получены с помощью качественного генератора случайных чисел; для достижения защищенности, сравнимой с устойчивостью к вторжениям, значения R должны держаться в секрете и гарантированно уничтожаться после использования;
наличие нижележащего транспортного протокола, обеспечивающего гарантированную доставку сообщений в порядке их отправления (относительно других сообщений конкретной пары «отправитель-получатель»);
наличие WORM-памяти;
наличие какого-либо системного механизма, позволяющего гарантированно уничтожать данные (наличие такого механизма является обычным предположением для систем с эволюцией ключей [2]); гарантированное удаление каждой версии секретного ключа после ее модификации.
Преимущества предложенного протокола
Одним из основных недостатков ряда схем с эволюцией ключей является требование о заранее известном и ограниченном количестве периодов времени T. Хотя были предложены и варианты схем с неограниченным количеством периодов, например, схема электронной подписи, описанная в работе [16].
Еще одной известной особенностью таких схем является наличие некоторого подготовительного этапа, на котором, как минимум, генерируется пара ключей. При этом во многих из существующих схем подготовительный этап является сложным и трудоемким (например, по причине генерации на подготовительном этапе ключевых пар для всех периодов времени, а также сертификации всех вариантов открытых ключей – как в схеме, описанной в работе [3]). В результате в подобных схемах время выполнения подготовительного этапа и/или требуемый для него объем памяти может зависеть линейно или, по крайней мере, логарифмически от T [15], что уже можно рассматривать как явный недостаток.
В схемах, предполагающих генерацию отдельных ключевых пар для каждого из периодов времени, например, описанных в работах [4], [5] и [15], и представляющих собой простые надстройки над классическими алгоритмами электронной подписи, упрощена модификация ключей, которая выполняется просто путем переключения между их версиями. В этом случае требуемый для хранения ключей объем памяти линейно зависит от T. А в обобщенной схеме электронной подписи с секретностью в будущем, описанной в [4], максимальный размер подписи также линейно зависит от T.
Впоследствии было предложено достаточно много улучшений схем с эволюцией ключей, но для вариантов как с предопределенным заранее, так и с неограниченным количеством периодов времени, схем с отсутствием зависимости трудоемкости подготовительного этапа и требуемой памяти от T описано не было.
Еще одним требованием схем с эволюцией ключей (например, описанных в [6] и [14]) обычно является наличие требований к синхронизации времени между пользователями (для одновременного переключения периодов времени) или предположений, что такая синхронизация каким-либо образом обеспечена. Это требует наличия дополнительного канала связи для синхронизации пользователей, причем защищенного от воздействий злоумышленника, поскольку такой канал может быть дополнительной мишенью для атаки с целью, как минимум, отказа в обслуживании; злоумышленник может также попытаться воздействием на данный канал связи расширить период времени, в течение которого произошла компрометация секретного ключа.
Предлагаемый протокол не базируется на использовании периодов времени; вместо модификации ключей по истечении каждого периода времени он предполагает их модификацию после подготовки/обработки каждого сообщения. В результате такого подхода к протоколу неприменимы многие из описанных выше недостатков/ограничений, т. е. следующие свойства описанного здесь протокола можно считать его преимуществами:
нет ограничения на количество периодов времени;
нет необходимости знать заранее количество периодов времени;
простой подготовительный этап;
отсутствует зависимость трудоемкости подготовительного этапа, требуемого объема памяти, размеров ключей (как секретных, так и открытых), подписей и шифртекстов от T;
не требуется синхронизация времени между пользователями – протокол позволяет системе оставаться работоспособной при рассинхронизации – значительной, но остающейся в пределах сроков действия долговременных ключей;
наконец, в случае отсутствия обмена данными между парой пользователей в определенном направлении соответствующую пару ключей не нужно модифицировать, какого-либо переключения между периодами времени не требуется.
Кроме того, как схемы с изоляцией ключа, так и схемы, устойчивые к вторжениям, требуют наличия какого-либо дополнительного вспомогательного устройства (auxiliary helper), а также, во многих случаях, еще и защищенного канала связи между основным и вспомогательным устройствами (в частности, такие схемы описаны в работах [1], [17] и [18]). Предложенный мной протокол не выдвигает подобных требований, но его применение имеет смысл только при наличии изолированного контура, в котором выполняются все криптографические операции, поэтому формальное отсутствие требования о наличии вспомогательного устройства нельзя рассматривать как преимущество данного протокола.
Заключение
Описанный здесь протокол эволюции ключей для неинтерактивных применений позволяет достичь ряда дополнительных свойств по обеспечению безопасности сообщений, защищенных как в прошлом, так и в будущем, относительно периодов времени, в которых произошла компрометация секретных ключей, что сравнимо со свойствами схем, устойчивых к вторжениям.
По сравнению с подобными схемами, предложенными в известных работах, у данного протокола есть ряд преимуществ, но он имеет и определенные недостатки и ограничения. Основными из них, на мой взгляд, являются следующие:
невосстановимое нарушение защищенного обмена сообщениями в случае потери сообщений или нарушения порядка их получения;
требования об относительно небольшом количестве получателей у каждого отправителя и относительно неактивном обмене сообщениями.
Хотелось бы минимизировать ограничения предложенного протокола, поскольку они значительно сужают область его использования. Буду благодарен за комментарии по данной статье и мысли о возможных улучшениях протокола, позволяющих преодолеть существующие ограничения и недостатки.
Литература по теме
1. Y. Dodis, J. Kats, S. Xu, M. Yung. Key-insulated public-key cryptosystems. EUROCRYPT’2002.
2. G. Itkis. Forward security. Adaptive cryptography: time evolution. Глава книги “Handbook of Information Security”, т. 2, 2006.
3. A. Back. Non-interactive forward secrecy. http://www.cypherspace.org/adam/nifs, 1997
4. R. Anderson. Two remarks on public key cryptology. http://www.cl.cam.ac.uk/TechReports/UCAM-CL-TR-549.pdf, 2002.
5. M. Bellare, S. Miner. A forward-secure digital signature scheme. CRYPTO’99.
6. M. Bellare, B. Yee. Forward-security in private-key cryptography. http://eprint.iacr.org/2001/035, 2001.
7. Y. Dodis, W. Luo, S. Xu, M. Yung. Key-insulated symmetric key cryptography and mitigating attacks against cryptographic cloud software. 7th ACM symposium on Information, Computer and Communications Security, 2012.
8. M. Blaze. High-Bandwidth Encryption with Low-Bandwidth Smartcards, 1995.
9. D. Naccache, D. Pointcheval, C. Tymen. Monotone signatures. Financial Cryptography, 2001.
10. G. Itkis, P. Xie. Generalized key-evolving signature schemes or How to foil an armed adversary. Applied Cryptography and Network Security, 2003.
11. D. Pointcheval, O. Sanders. Forward secure non-interactive key exchange. 9th International Conference on Security and Cryptography for Networks, 2014.
12. D. Cash, Y. Z. Ding, Y. Dodis, W. Lee, R. Lipton, S. Walfish. Intrusion-resilient key exchange in the bounded retrieval model. Theory of Cryptography, 2007.
13. R. Canetti, S. Halevi, J. Katz. A forward-secure public-key encryption scheme. EUROCRYPT’2003.
14. W.-G. Tzeng, Z.-J. Tzeng. Robust key-evolving public key encryption schemes. http://eprint.iacr.org/2001/009, 2001.
15. H. Krawczyk. Simple forward-secure signatures from any signature scheme. 7th ACM conference on Computer and Communications Security, 2000.
16. T. Malkin, D. Micciancio, S. Miner. Efficient generic forward-secure signatures with an unbounded number of time periods. EUROCRYPT’2002.
17. G. Itkis, L. Reyzin. SiBIR: signer-base intrusion-resilient signatures. http://eprint.iacr.org/2002/054, 2002.
18. M. Bellare, S. Duan, A. Palacio. Key insulation and intrusion resilience over a public channel. Topics in Cryptology – CT-RSA’2009.
