…или введение в хэширование

Под таким неоднозначным заголовком я решил разместить всеголишь повествование о такой неотъемлимой части криптографии как hash-функции и алгоритмы.

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

Введение

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

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

Свойства

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

Устойчивость к коллизиям

Коллизия– пара различных прообразов, для которых значение хэша совпадает.

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

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

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

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

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

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

Однонаправленность

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

Кардинальное изменение хэша при незначительном изменении оригинала

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

Применение

На практике криптографические хэширующие функции имеет несколько вариантов применения, вот основные из них:

• Хранение аутентификационных данных пользователей сайтов или программных продуктов. В случае чисто теоретически возможной ошибки программистов или каких-либо других людей или просто имея доступ к базе данных на том или ином основании, потенциальный злоумышленник может получить доступ к закрытым компонентам того или иного проекта, в том числе и к базе данных пользователей. Если такого рода данные хранились бы в открытом виде, он получил бы полный доступ ко всем учетным записям пользователей. Для избежания возможности возникновения подобной ситуации принято хранить не сами логин и пароль пользователей, а их хэши. В этом случае для аутентификации введенные пользователем данные пропускаются через тот же алгоритм хэширования и полученный хэш сравнивается с хранящимся в БД.
• Проверка целостности копии данных. Чаще всего этот способ проверки соответствия копии оригиналу используется в отсутствии доступа к оригиналу. В качестве примера можно привести передачу больших объемов информации через ненадежное пространство (чаще всего Интернет), многие файловые серверы хранят рядом с большими файлами вычисленные от них хэши с использованием популярных алгоритмов, посетитель, скачав файл, может убедиться в его соответствии оригиналу, просто вычислив такой же хэш от копии и сравнив с доступным хэшем от оригинала. Но такой же принцип может использоваться и при доступном оригинале, например, многие программы для прожига образов на компакт-диски используют схожий принцип для проверки соответствия полученного диска образу.

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

Заключение

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