В. Р. Гинзбург Перевод с английского
жүктеу/скачать 2,74 Mb. Pdf көрінісі
|
практическая криптография
Глава 6. Функции хэширования тически невозможно. Поэтому необходимо исправить саму функцию хэширо- вания. Следует отметить, что это нестандартная точка зрения. Большинство криптографов вполне устраивают итеративные функции хэширования; опи- санные проблемы не устраняются даже в новых системах. Некоторые пользо- ватели функций хэширования предпринимают массу усилий, чтобы избежать проблем. Большинство же удачливых пользователей так и живут, оставаясь в счастливом неведении относительно того, какие неприятности могли с ними приключиться. Между тем неприятности все же случаются и довольно часто. Каждая из этих проблем может быть исправлена путем применения к систе- ме какого-нибудь специального метода, но нам кажется, что это неправильно и следует исправить саму функцию хэширования. 6.4.1 Полное исправление До сих пор нам не встречалась литература, посвященная исправлению недостатков функций хэширования. Здесь лишь изложены выводы, к кото- рым мы пришли в процессе написания этой книги. Все проблемы могут быть устранены, если использовать функцию хэширования дважды. Мы убежде- ны, что данное решение позволяет избавиться от всех упомянутых недостат- ков функций хэширования. Но разработка криптографических функций — дело сложное, поэтому дать стопроцентную гарантию пока нельзя. Наше ре- шение еще не было проанализировано другими экспертами, что обычно зани- мает долгие годы (если, конечно, им кто-то заинтересуется). Такова жизнь. Пусть h — одна из рассмотренных функций хэширования. Вместо того чтобы использовать в качестве функции хэширования m 7→ h ( m ) , будем ис- пользовать функцию m 7→ h ( h ( m ) k m ) 5 . Как видите, перед хэшированием сообщения m к его началу было дописано значение h ( m ) . Благодаря этому итеративное вычисление хэш-кода будет сразу же зависеть от всех битов сооб- щения, что сделает невозможными атаки, осуществляемые путем частичного хэширования или путем удлинения сообщений. Определение 6 Пусть h — итеративная функция хэширования. Тогда функция хэширования h DBL определяется выражением h DBL ( m ) := h ( h ( m ) k m ) . Если h является одной из рассмотренных ранее функций хэширования, то мы убеждены, что предложенная конструкция будет обладать уровнем безопасности в n бит, где n — размер результата функции хэширования. 5 Запись x 7→ f ( x ) — еще один способ обозначения функции. Его применяют тогда, когда не хотят присваивать функции имя. Например, x 7→ x 2 — это функция, которая возводит в квадрат свой аргумент. 6.4. Исправление недостатков 115 Недостатком этого подхода является низкая скорость работы. Сообщение приходится хэшировать дважды, что занимает в два раза больше времени по сравнению с обычным хэшированием. Лично нас это не огорчает, потому что мы всегда ставим безопасность выше скорости. В мире и так достаточно быстрых небезопасных систем, так зачем же разрабатывать еще одну? Тем не менее скорость хэширования является “узким местом” производительности некоторых приложений, поэтому нужно придумать что-нибудь более эффек- тивное. Еще одним недостатком этого подхода является необходимость буфериза- ции всего сообщения m . Мы больше не сможем подсчитывать хэш-код потока данных по мере их поступления. Некоторые приложения нуждаются в этой возможности, и функция h DBL для них просто не подойдет. 6.4.2 Более эффективное исправление Как же сохранить полную скорость исходной функции хэширования? Здесь можно немного схитрить. Вместо h ( m ) можно использовать функцию h ( h ( m )) и объявить, что ее уровень безопасности составляет всего n/ 2 бит. Хитрость состоит в том, что обычно от n -битовой функции хэширования ожи- дают обеспечения уровня безопасности n бит в тех ситуациях, где атака на основе коллизий невозможна 6 . Все атаки на основе коллизий при частичном хэшировании сообщений используют парадокс задачи о днях рождения, по- этому, если снизить уровень безопасности до n/ 2 бит, эти атаки больше не будут подпадать под заявленный уровень безопасности. В большинстве ситуаций подобное снижение уровня безопасности было бы неприемлемым, но нам повезло. Функции хэширования изначально раз- рабатывались с учетом возможности осуществления атак на основе коллизий, поэтому размеры результатов функций хэширования довольно велики. Если применить данный прием к функции SHA-256, то будет получена функция хэширования со 128-битовым уровнем безопасности, что в точности соответ- ствует нашим требованиям. Некоторые могут возразить, что все n -битовые функции хэширования и так обеспечивают только n/ 2 -битовый уровень безопасности. Это верная точка зрения. К сожалению, если не конкретизировать реальное положение вещей, функции хэширования будут неправильно эксплуатироваться и будет предполагаться, что они должны обеспечивать n -битовый уровень безопас- ности. Например, многие хотят использовать SHA-256 для хэширования 256- битовых ключей алгоритма AES, полагая, что это обеспечит 256-битовый уро- вень безопасности. Как уже отмечалось, мы используем 256-битовые ключи 6 Даже в документации к SHA-256 говорится, что n -битовая функция хэширования должна требовать выполнения 2 n шагов для обнаружения прообраза заданного значения. |