Хейз, Говард

Говард Хейз
Howard Heys
Страна:	Канада
Научная сфера:	Криптография
Место работы:	Университет Ньюфаундленда (англ.)русск.
Учёная степень:	бакалавр (Университет Западной Онтарио, 1984) кандидат наук (Университет Куинс, 1994)
Альма-матер:	Университет Западной Онтарио, Университет Куинс
Сайт:	www.engr.mun.ca

Го́вард М. Хейз (англ. Howard M. Heys) — канадский криптограф, профессор, заведующий кафедры электро- и вычислительной инженерии университета Ньюфаундленда (англ.)русск.. Его исследования включают в себя разработку и анализ поточных и блочных шифров, а также их эффективной аппаратной реализации; участвовал в проектировании блочного алгоритма симметричного шифрования CAST-256 и опубликовал криптоанализ таких блочных шифров, как RC5 и CIKS-1 (англ.)русск.. Он дважды занимал пост сопредседателя на симпозиумах^[1], посвященных избранным разделам криптографии, вместе с Карлайлом Адамсом (англ.)русск. в 1999 году^[2] и с Кайсой Ниберг (англ.)русск. в 2002 году^[3]. Его преподавательская деятельность включает курсы по коммуникационным технологиям, компьютерным сетям и алгоритмам, а также руководство рядом бакалаврских работ.

Биография

После получения степени бакалавра в области электротехники в Университете Западной Онтарио в Лондоне, Хейз работал в течение нескольких лет разработчиком программного обеспечения в Bell Northern Research (в настоящее время Nortel). После шести лет в промышленности, он вернулся в университет и защитил докторскую диссертацию в электро- и компьютерной инженерии в Университете Куинс в Кингстоне, Онтарио. На сегодняшний день Говард Хейз живёт в Сент-Джонс, Ньюфаундленд вместе со своей семьёй: женой и двумя детьми, и преподаёт в Мемориальном Университете Ньюфаундленда на факультете инженерии и прикладных наук.

Научные исследования

Принципиальное внимание его исследований уделено проектированию, анализу и реализации криптографических алгоритмов или шифров, а также рассмотрение вопроса о применении криптографии для сетей связи. Целью его работ является создание основополагающих принципов построения эффективных, безопасных шифров, которые могут быть легко приспособлены к особенностям ряда прикладных сред. В частности, последние исследования концентрируются на аппаратном дизайне и реализации простых симметричных шифров, устойчивых к атакам по сторонним (или побочным) каналам и другим видам криптоанализа. Кроме того, исследования криптографических схем применительно к различным сетям связи, начиная от беспроводных сенсорных сетей и заканчивая широкополосными сетями, также описаны в его работах. Исследования проводятся совместно с доктором Р. Венкатесан, доктором Ченгом Ли, доктором Тео Норвеллом, доктором Лихонгом Чжаном и доктором Сесилии Молони.

В добавок к криптографическим теориям, большая часть его работ включает в себя аппаратную реализацию шифров, проведённых совместно с Центром исследования приложений для цифрового оборудования (CDHAR^[4]), являющимся одной из лабораторий компьютерной инженерии в университете Ньюфаундленда.

Шифр CAST

Г.М. Хейз совместно с С.Е. Таваресом^[5] исследовал стойкость шифра CAST по отношению к линейному криптоанализу. Они заключили, что достаточно легко подобрать S-блоки, чтобы при этом эффективная реализация алгоритма CAST была явно к нему устойчива. Г.М. Хейз и С.Е. Таварес определили теоретическую границу стойкости к этому анализу, дававшую минимальную нелинейность используемых S-блоков. Результаты выявили, что 64-разрядный шифр CAST с 64-битным ключом на основе 8х32 S-блоков стоек к линейному криптоанализу с умеренным количеством раундов. Дальнейший их анализ показал, что достаточное количество нелинейных S-блоков легко найти простой случайной генерацией. Они получили, что создание эффективных блочных шифров, устойчивых к линейному криптоанализу, является прямым использованием процедуры проектирования алгоритмов шифрования CAST.

Хейз также исследовал аспекты^[6] безопасности блочного шифра CAST-256 с акцентом именно на диффузионных свойствах и сопротивляемости шифра к линейному и дифференциальному криптоанализу. Выводы из его анализа показывают, что в отношении этих свойств, шифр является безопасным, хотя это и не позволяет утверждать, что любой шифр имеет гарантированную стойкость. Чтобы более удостовериться в безопасности CAST-256, его можно проанализировать на другие особенности, а также на других методах криптоанализа. Сюда могут включаться такие особенности, как информационно-теоретические характеристики шифров и атак, например, на основе подобранного ключа, дифференциальные атаки более высокого порядка и линейно-дифференциальные атаки. Кроме того, в анализ можно включить более точный учёт влияния комбинирования операций сложения и вычитания. Тем не менее, такой полный анализ, скорее всего, выявит другие трудноразрешимые задачи.

Анализ CAST-подобных шифров

Что касаемо устойчивости CAST-подобных шифров к линейному криптоанализу, Дж. Ли, Г.М. Хейз, и С.Е. Таварес^[7] вывели границу вероятности удовлетворения линейной аппроксимации на основе минимальной нелинейности S-блоков, используемых в раундовой функции CAST-подобного шифра. Оказалось, что для случайно сгенерированных 8х32 S-блоков, 64-разрядный CAST-подобный шифр, состоящий из 12 раундов имеет, более высокую степень устойчивости к линейным атакам, чем DES с 16 раундами.

Количество раундов	Требуемое количество подобранных открытых текстов
	CAST	DES
8	234	222
12	250	234
16	266	247

В анализе стойкости CAST-подобных шифров к дифференциальному криптоанализу, они использовали метод прогнозирования записей в таблице XOR раундовой функции F CAST-подобных шифров с использованием случайно генерируемых S-блоков. На основе этого метода, Дж. Ли, Г.М. Хейз, и С.Е. Таварес показали, что при использовании случайно сгенерированные S-блоков и простой процесс отбора лучшая из доступных итеративных характеристик - 2-раундовая итеративная характеристика. Для 64-разрядных CAST-подобных алгоритмов с использованием 8х32 S-блоков, наилучшая 2-раундовая итеративная характеристика даёт вероятность 2⁻¹⁴ и это значение почти в 70 раз меньше, чем у наилучшей 2-раундовой итеративной характеристики в DES, которая даёт вероятность 1/234. В результате, восьмираундовая характеристика CAST-подобных шифров позволит снизить вероятность возникновения правильных пар до 2⁻⁵⁶ - значение, которое значительно лучше, чем в 15 раундовой версии DES.

Шифр CISK-1

Шифр CIKS-1 - быстрый, аппаратно-ориентированный шифр с основной защитной компонентой - перестановками, зависящими от данных. Это блочный шифр с размером блока 64-бит. Шифр состоит из 8 раундов, каждый из которых имеет 32-разрядный подключ из общего ключа размером 256-бит.

В оригинальной статье по CIKS-1, анализ авторов о возможности дифференциальных атак на шифр показал, что такая атака будет иметь сложность как минимум 2⁶⁴ (требуемое количество подобранных открытых текстов). Брайан Кидни, Говард Хейз и Теодор Норвелл^[8] предложили дифференциальную атаку со сложностью около 2⁵⁶. Чтобы доказать концепцию этой атаки, её осуществили на трёхраундовой версии шифра. Эта атака показала, что фактический ключ может быть определен по двум случайным ключам и ключам, отличающимся от них на один бит. Хотя предварительные испытания этой атаки на трёхраундовой версии шифра CIKS-1 выглядели весьма многообещающими, Брайан Кидни, Говард Хейз и Теодор Норвелл рассмотрели и расширенную атаку - на шестираундовую версию шифра - и обнаружили теоретическую сложность приблизительно 2³⁵.

Атаки по времени

Говард Хейз и Майкл Фёрлонг^[9] рассмотрели применение атак по времени к симметричному блочному шифру CIKS-1. Анализ мотивируется возможностью того, что достаточно простая используемая в CIKS-1 реализация перестановок, зависящих от данных, приведет к тому, что шифрование будет опираться на время, которое является функцией данных. Такие реализации возможны в программных средах, как правило, во встраиваемых системах, таких как смарт-карты.

Перестановки, зависящие от данных (ПЗД) - уязвимая компонента шифра. Существует прямая связь между числом замен, которые происходят в блоке ПЗД и весом Хэмминга контрольного вектора. Компонента ПЗД не меняет вес Хэмминга у данных, на которые она действует.

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

Атаки по времени полагаются на точные измерения времени, требуемого на отдельные процедуры шифрования. Эту информацию достаточно трудно получить в многопоточной среде, такой как большинство современных операционных систем общего назначения. Тем не менее, вполне возможно, что атака может быть модифицирована и осуществлена в среде, где измерения времени зашумлены. В любом случае, Говард Хейз и Майкл Фёрлонг показывали уязвимость, о которой проектировщики должны были быть осведомлены в ходе реализации CIKS-1, как, впрочем, и проектировщики любого шифра, использующего перестановки, зависящие от данных, как криптологически базисный элемент. К счастью, эта проблема может быть устранена путем использования перестановок, зависящих от данных, происходящих за постоянное время, таким образом защищая шифр от атак по времени.

Атаки, основанные на весе

Брайан Кидни, Говард Хейз и Теодор Норвелл^[10] показали, что из-за выбора базовых элементов с ограниченным влиянием на вес Хэмминга шифрованных данных, шифр CIKS-1 зависит от веса подключей, производя тем самым изменение веса данных. Это означает, что класс маловесных ключей следует считать классом уязвимых ключей для шифра. Эти ключи производят выходные данные, которые легко обнаружить с помощью двух тестов. Используя этот факт, предполагается, что атака будет различать первый подключ, резко уменьшая его энтропию. Предварительное тестирование было проведено на атаке, показавшей уменьшение области поиска для первого подключа с пределах расстояния Хэмминга равном двум от реального веса. На данный момент, атака не была расширена для полного нахождения фактического подключа. Кроме того, будет проведено больше исследований по расширению этой атаки для полной восьмираундовой версии шифра.

Шифр RC5

Говард Хейз обнаружил^[11], что для некоторых ключей RC5 может быть значительно более уязвим к линейному криптоанализу, чем предполагалось ранее. Хотя этот анализ и не представляет практической угрозы безопасности номинальной реализации RC5 - или длина открытого текста требуется слишком большой, или вероятность выбора уязвимого ключа слишком мала - он подчеркивает важность алгоритма генерации ключей и их неэквивалентности в RC5.

Атаки по времени

Хелена Хандшу и Говард Хейз^[12] показали, в некоторых деталях, как получить расширенную таблицу секретных ключей RC5-32/12/16 применяя атаку по времени с использованием только около 2²⁰ операций шифрования, при этом создавая сложность по времени 2²⁸ в лучшем случае и 2⁴⁰ в худшем случае. Это подтверждает утверждение Кохера о том, что RC5 находится под некоторым риском на платформах, где циклический сдвиг происходит за переменное количество времени, и предполагает, что нужно быть очень осторожными при реализации RC5 на таких платформах. Добавление случайного времени к каждому шифрованию не поможет, так как не будет иметь большого влияния на дисперсию вычислений. Поэтому они предложили добавить нужное количество «пустых» циклических сдвигов, целью которых является достижение постоянного времени для каждого шифрования независимо от начального общего количества циклических сдвигов.

Примечания

1. ↑ Workshops on Selected Areas in Cryptography
2. ↑ Kaisa Nyberg and Howard Heys (eds.) Lecture Notes in Computer Science 2595: Selected Areas in Cryptography 9th Annual International Workshop, SAC 2002, St. John's, Newfoundland, Canada, August 2002, Revised Papers Springer-Verlag, 2003
3. ↑ Howard Heys and Carlisle Adams (eds.) Lecture Notes in Computer Science 1758: Selected Areas in Cryptography, 6th Annual International Workshop, SAC'99, Kingston, Ontario, Canada, August 1999 Proceedings, Springer-Verlag, 2000
4. ↑ Centre for Digital Hardware Applications Research
5. ↑ H.M. Heys and S.E. Tavares "On the Security of the CAST Encryption Algorithm", 1994, pp. 1-4
6. ↑ C. Adams, H.M. Heys, S.E. Tavares, and M. Wiener "An Analysis of the CAST-256 Cipher", 1999, pp. 1-6
7. ↑ J. Lee, H.M. Heys, and S.E. Tavares "Resistance of a CAST-like Encryption Algorithm to Linear and Differential Cryptanalysis", 1997
8. ↑ B.J. Kidney, H.M. Heys, and T.S. Norvell "A Differential Attack on the CIKS-1 Block Cipher", 2004, pp. 1-4
9. ↑ M. Furlong and H.M. Heys "A Timing Attack on the CIKS-1 Block Cipher", 2005, pp. 1-4
10. ↑ B.J. Kidney, H.M. Heys, and T.S. Norvell "A Weight Based Attack on the CIKS-1 Block Cipher", 2003, pp. 1-5
11. ↑ H.M. Heys "Linearly Weak Keys of RC5", 1997, pp. 1-7
12. ↑ H. Handschuh and H.M.Heys "A Timing Attack on RC5", 1999, pp. 1-13

Литература

• Adams C., Heys H. M., Tavares S. E., Wiener M. An Analysis of the CAST-256 Cipher (англ.). — Edmonton, Alberta: IEEE, 1999. — P. 6.
• Furlong M., Heys H. M. A Timing Attack on the CIKS-1 Block Cipher (англ.). — Saskatoon, Saskatchewan: IEEE, 2005. — P. 4.
• Handschuh H., Heys H. M. A Timing Attack on RC5 (англ.). — Springer-Verlag, 2003. — P. 13.

• Heys H. M. Linearly Weak Keys of RC5 (англ.). — IEEE, 1997. — P. 7.
• Heys H. M., Tavares S. E. On the Security of the CAST Encryption Algorithm (англ.). — Halifax, Nova Scotia: IEEE, 1994. — P. 4.
• Kidney B. J., Heys H. M., Norvell T. S. A Weight Based Attack on the CIKS-1 Block Cipher (англ.). — St. John's, Newfoundland, 2003. — P. 5.
• Kidney B. J., Heys H. M., Norvell T. S. A Differential Attack on the CIKS-1 Block Cipher (англ.). — Niagara Falls, Ontario: IEEE, 2004. — P. 4.
• Lee J., Heys H. M., Tavares S. E. Resistance of a CAST-like Encryption Algorithm to Linear and Differential Cryptanalysis (англ.). — Edmonton, Alberta: Kluwer Academic Publishers, 1997. — P. 26.

Внешние ссылки

1. Howard Heys's page at MUN