Армия Алуа лаб№7. Методы практического использования блочных шифров Российского госта 2814789 и расчет его эцп
 Скачать 306.23 Kb.
|
Вариации на тему ГОСТаОчень часто для использования в системе криптографической защиты данных требуется алгоритм с большим, чем у ГОСТа быстродействием реализации, и при этом не требуется такая высокая криптостойкость. Типичным примером подобных задач являются различного рода электронные биржевые торговые системы, управляющие торговыми сессиями в реальном времени. Здесь от использованных алгоритмов шифрования требуется, чтобы было невозможно расшифровать оперативные данные системы в течение сессии (данные о выставленных заявках, о заключенных сделках и т.п.), по ее истечении же эти данные, как правило, уже бесполезны для злоумышленников. Другими словами, требуется гарантированная стойкость всего на несколько часов – такова типичная продолжительность торговой сессии. Ясно, что использование полновесного ГОСТа в этой ситуации было бы стрельбой из пушки по воробьям. Как поступить в этом и аналогичном ему случаях, чтобы увеличить быстродействие шифрования? Ответ лежит на поверхности – использовать модификацию шифра с меньшим количеством основных шагов (раундов) в базовых циклах. Во сколько раз мы уменьшаем число раундов шифрования, во столько же раз возрастает быстродействие. Указанного изменения можно достигнуть двумя путями, – уменьшением длины ключа и уменьшением числа «циклов просмотра» ключа. Вспомните, что число основных шагов в базовых циклах шифрования равно N=n·m, где n – число 32-битовых элементов в ключе, m – число циклов использования ключевых элементов, в стандарте n=8, m=4. Можно уменьшить любое из этих чисел, но простейший вариант – уменьшать длину ключа, не трогая схемы его использования. Понятно, что платой за ускорение работы будет снижение стойкости шифра. Основная трудность заключается в том, что достаточно сложно более или менее точно оценить величину этого снижения. Очевидно, единственно возможный способ сделать это – провести исследование вариантов шифра с редуцированными циклами криптографического преобразования «по полной программе». Понятно, что, во-первых, это требует использования закрытой информации, которой владеют только разработчики ГОСТа, и, во-вторых, очень трудоемко. Поэтому мы сейчас попытаемся дать оценку, очень и очень грубую, исходя лишь из общих закономерностей. Что касается устойчивости шифра к взлому «экстенсивными» методами, то есть к «переборной» атаке, тот тут все более или менее ясно: ключ размером 64 бита находится где-то на грани доступности этому виду атаки, шифр с ключом 96 бит и выше (помните, что ключ должен содержать целое число 32-битовых элементов) вполне устойчив против него. Действительно, несколько лет назад прежний стандарт шифрования США, DES, был неоднократно взломан переборным путем, – сначала его взломала вычислительная сеть, организованная на базе глобальной сети Интернет, а затем – специализированная, т.е. сконструированная специально для этого вычислительная машина. Примем, что стандартный вариант ГОСТа при программной реализации на современных процессорах работает вчетверо быстрее DES. Тогда 8-раундовый «редуцированный ГОСТ» будет работать в 16 раз быстрее DES. Примем также, что за прошедшее с момента взлома DES время производительность вычислительной техники согласно закону Мура возросла вчетверо. Получаем в итоге, что сейчас проверка одного 64-битового ключа для «редуцированного ГОСТа» с восемью циклами осуществляется в 64 раза быстрее, чем в свое время выполнялась проверка одного ключа DES. Таким образом, преимущество такого варианта ГОСТа перед DES по трудоемкости переборной атаки сокращается с 264–56 = 28 = 256 до 256/64 = 4 раз. Согласитесь, это весьма иллюзорное различие, почти что ничего. Гораздо сложнее оценить устойчивость ослабленных модификаций ГОСТа к «интенсивным» способам криптоанализа. Однако общую закономерность можно проследить и здесь. Дело в том, что «профильные» характеристики многих наиболее сильных на сегодняшний момент видов криптоанализа зависят экспоненциально от числа раундов шифрования. Так, для линейного криптоанализа (ЛКА) это будет характеристика линейности L:  ,где Cи  – константы, R – число раундов. Аналогичная зависимость существует и для дифференциального криптоанализа. По своему «физическому смыслу» все характеристики такого рода – вероятности. Обычно объем необходимых для криптоанализа исходных данных и его трудоемкость обратно пропорциональны подобным характеристикам. Отсюда следует, что эти показатели трудоемкости растут экспоненциально с ростом числа основных шагов шифрования. Поэтому при снижении числа раундов в несколько раз трудоемкость наиболее известных видов анализа изменится как, – очень приблизительно и грубо, – корень этой степени из первоначального количества. Это очень большое падение стойкости.С другой стороны, ГОСТ проектировался с большим запасом прочности и на сегодняшний день устойчив ко всем известным видам криптоанализа, включая дифференциальный и линейный. Применительно к ЛКА это означает, что для его успешного проведения требуется больше пар «открытый блок – зашифрованный блок», чем «существует в природе», то есть более 264. С учетом сказанного выше это означает, что для успешного ЛКА 16-раундового ГОСТа потребуется не менее  блоков или 235 байтов или 32 Гбайта данных, а для 8-раундового – не менее  блоков или 219 байтов или 0.5 Мбайт.Выводы из всего, сказанного выше, приведены в следующей таблице, обобщающей характеристики редуцированных вариантов ГОСТа.
Два последних варианта, с 12 и 8 раундами, способны обеспечить весьма и весьма ограниченную во времени защиту. Их использование оправдано лишь в задачах, где требуется лишь краткосрочная секретность закрываемых данных, порядка нескольких часов. Возможная область применения этих слабых вариантов шифра – закрытие UDP-трафика электронных биржевых торговых систем. В этом случае каждый пакет данных (datagram, средняя «D» из аббревиатуры UDP) шифруется на отдельном 64-битовом ключе, а сам ключ шифруется на сеансовом ключе (ключе, область действия которого – один сеанс связи между двумя компьютерами) и передается вместе с данными. Прежде чем закончить с редуцированными вариантами ГОСТа скажу, что все приведенные выше соображения носят в высшей степени спекулятивный характер. Стандарт обеспечивает стойкость только для одного, 32-раундового варианта. И никто не может дать вам гарантий, что устойчивость редуцированных вариантов шифра к взлому будет изменяться указанным выше образом. Если вы все же решились их использовать в своих разработках, помните, что вы ступили на весьма зыбкую почву, которая может в любой момент уйти из-под ваших ног. Коль скоро вопросы скорости шифрования являются для вас критическими, может, стоит подумать об использовании более быстрого шифра или более мощного компьютера? Еще одно соображение, по которому это стоит сделать, заключается в том, что ослабленные варианты ГОСТа будут максимально чувствительны к качеству используемых узлов замены. У рассматриваемого вопроса есть и обратная сторона. Что если скорость шифрования некритична, а требования к стойкости весьма жестки? Повысить стойкость ГОСТа можно двумя путями – условно назовем их «экстенсивный» и «интенсивный». Первый из них – это ни что иное, как простое увеличение числа раундов шифрования. Мне не совсем понятно, зачем это может реально понадобиться, ведь отечественный стандарт и без этого обеспечивает необходимую стойкость. Впрочем, если вы страдаете паранойей больше необходимого уровня (а все «защитники информации» просто обязаны ею страдать, это условие профпригодности такое, вопрос только в степени тяжеcти случая :), это поможет вам несколько успокоиться. Если вы не уверены в этом КГБ-шном шифре или используемой вами таблице замен, просто удвойте, учетверите, и т.д. число раундов – кратность выберите исходя из тяжести вашего случая. Указанный подход позволяет реально увеличить стойкость шифра, – если раньше криптоанализ был просто невозможным, то теперь он невозможен в квадрате! Более хитрым и интересным является вопрос, а можно ли увеличить стойкость шифра, не меняя количества и структуры основных шагов шифрования. Как ни удивительно, ответ на этот него положительный, хотя мы опять ступаем на зыбкую почву спекуляций. Дело в том, что в ГОСТе на основном шаге преобразования предполагается выполнение замены 4 на 4 бит, а на практике (речь об этом еще впереди) все программные реализации выполняют замену побайтно, т.е. 8 на 8 бит – так делается по соображениям эффективности. Если сразу спроектировать такую замену как 8-битовую, то мы существенно улучшим характеристики одного раунда. Во-первых, увеличится «диффузионная» характеристика или показатель «лавинности» – один бит исходных данных и/или ключа будет влиять на большее число бит результата. Во вторых, для больших по размеру узлов замены можно получить более низкие дифференциальную и линейную характеристики, уменьшив тем самым подверженность шифра одноименным видам криптоанализа. Особенно актуально это для редуцированных циклов ГОСТа, а для 8 и 12-раундовых вариантов такой шаг просто необходим. Это несколько скомпенсирует потерю стойкости в них от уменьшения числа раундов. Что затрудняет использование этого приема – так это то, что конструировать подобные «увеличенные» узлы замены вам придется самостоятельно. А также то, что более крупные узлы вообще конструировать заметно труднее, чем меньшие по размеру. Нестандартное использование стандарта.Безусловно, основное назначение криптоалгоритмов ГОСТ – это шифрование и имитозащита данных. Однако им можно найти и другие применения, связанные, естественно, с защитой информации. Коротко расскажем о них: 1. Для шифрования в режиме гаммирования ГОСТ предусматривает выработку криптографической гаммы – последовательности бит с хорошими статистическими характеристиками, обладающей высокой криптостойкостью. Далее эта гамма используется для модификации открытых данных, в результате чего получаются данные зашифрованные. Однако, это не единственное возможное применение криптографической гаммы. Дело в том, что алгоритм ее выработки – это генератор последовательности псевдослучайных чисел (ГППСЧ) с великолепными характеристиками. Конечно, использовать такой ГППСЧ там, где требуются только получение статистических характеристик вырабатываемой последовательности, а криптостойкость не нужна, не очень разумно – для этих случаев имеются гораздо более эффективные генераторы. Но для разных применений, связанных с защитой информации, такой источник будет весьма кстати: Как уже отмечалось выше, гамму можно использовать как «сырье» для выработки ключей. Для этого нужно лишь получить отрезок гаммы нужной длины – 32 байта. Таким способом ключи можно изготавливать по мере необходимости и их не надо будет хранить, – если такой ключ понадобится повторно, будет достаточно легко его выработать снова. Надо только будет вспомнить, на каком ключе он был выработан исходно, какая использовалась синхропосылка и с какого байта выработанной гаммы начинался ключ. Вся информация, кроме использованного ключа, несекретна. Данный подход позволит легко контролировать достаточно сложную и разветвленную систему ключей, используя всего лишь один «мастер-ключ». Аналогично предыдущему, гамму можно использовать в качестве исходного «сырья» для выработки паролей. Тут может возникнуть вопрос, зачем вообще нужно их генерировать, не проще ли по мере надобности их просто выдумывать. Несостоятельность такого подхода была наглядно продемонстрирована серией инцидентов в компьютерных сетях, самым крупным из которых был суточный паралич интернета в ноябре 1988 года, вызванный «червем Морриса». Одним из способов проникновения злоумышленной программы на компьютер был подбор паролей: программа пыталась войти в систему, последовательно перебирая пароли из своего внутреннего списка в несколько сотен, причем в значительной доле случаев ей это удавалось сделать. Фантазия человека по выдумыванию паролей оказалась весьма бедной. Именно поэтому в тех организациях, где безопасности уделяется должное внимание, пароли генерирует и раздает пользователям системный администратор по безопасности. Выработка паролей чуть сложнее, чем выработка ключей, так как при этом «сырую» двоичную гамму необходимо преобразовать к символьному виду, а не просто «нарезать» на куски. Кроме того, отдельные значения, возможно, придется отбросить, чтобы обеспечить равную вероятность появления всех символов алфавита в пароле. Еще один способ использования криптографической гаммы – гарантированное затирание данных на магнитных носителях. Дело в том, что даже при перезаписи информации на магнитном носителе остаются следы предыдущих данных, которые может восстановить соответствующая экспертиза. Для уничтожения этих следов такую перезапись надо выполнить многократно. Оказалось, что потребуется перезаписывать информацию на носитель меньшее количество раз, если при такой процедуре использовать случайные или псевдослучайные данные, которые останутся неизвестными экспертам, пытающимся восстановить затертую информацию. Гамма шифра здесь будет как нельзя кстати. 2. Не только криптографическая гамма, но и само криптографическое преобразование, может быть использовано для нужд, непосредственно не связанных с шифрованием: Мы знаем, что один из таких вариантов использования ГОСТа – выработка имитовставки для массивов данных. Однако на базе любого блочного шифра, и ГОСТа в том числе, достаточно легко построить схему вычисления односторонней хэш-функции, называемой также в литературе MDC, что в разных источниках расшифровывается как код обнаружения изменений/манипуляций(Modification/Manipulation Detection Code) или дайджест сообщения(Message Digest Code). Первая расшифровка появилась в литературе гораздо раньше, вторую, более короткую, я думаю, придумали те, кому оказалось не под силу запомнить первую :), – это была шутка. MDC может непосредственно использоваться в системах имитозащиты в качестве аналога имитовставки, не зависящего, однако, от секретного ключа. Кроме того, MDC широко используется в схемах электронно-цифровой подписи (ЭЦП), ведь большинство таких схем сконструированы таким способом, что подписывать удобно блок данных фиксированного размера. Как известно, на базе обсуждаемого стандарта ГОСТ 28147-89 построен стандарт Российской Федерации на вычисление односторонней хэш-функции ГОСТ Р34.11-94 [10]. Менее известно, что на базе любого блочного шифра, и ГОСТа в том числе, может быть построена вполне функциональная схема ЭЦП, с секретным ключом подписи и открытой проверочной комбинацией. По ряду причин эта схема не получила широкого практического распространения, однако в отдельных случаях до сих пор может рассматриваться как весьма привлекательная альтернатива доминирующим ныне в мире «математическим» схемам ЭЦП. |