Цепочка хешей

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

Определение

Цепочка хешей — результат последовательного применения криптографической хеш-функции h ( x ) {displaystyle h(x)} к строке x {displaystyle x} .

Например,

h ( h ( h ( h ( x ) ) ) ) {displaystyle h(h(h(h(x))))}

дает цепочку хешей длины 4, что часто обозначается как h 4 ( x ) {displaystyle h^{4}(x)}

Применения

Лэмпорт предложил использовать цепочки хешей в качестве схемы защиты пароля в небезопасном окружении. Сервер, которому нужно предоставлять аутентификацию, может хранить цепочку хешей вместо незашифрованного пароля, предотвращая таким образом кражу пароля во время передачи на сервер либо непосредственно с сервера. Например, сервер начинает с хранения записи h 1000 ( p a s s w o r d ) {displaystyle h^{1000}(password)} , которая предоставляется пользователем. Когда пользователь желает аутентифицироваться, он посылает на сервер строку h 999 ( p a s s w o r d ) {displaystyle h^{999}(password)} . Сервер вычисляет строку h ( h 999 ( p a s s w o r d ) ) = h 1000 ( p a s s w o r d ) {displaystyle h(h^{999}(password))=h^{1000}(password)} и убеждается в совпадении с сохраненной на сервере записью. После этого сервер сохраняет запись h 999 ( p a s s w o r d ) {displaystyle h^{999}(password)} для последующей аутентификации.

Злоумышленник, перехвативший h 999 ( p a s s w o r d ) {displaystyle h^{999}(password)} , при обращении к серверу не сможет воспроизвести и передать на сервер начало цепочки, поскольку теперь сервер ожидает h 998 ( p a s s w o r d ) {displaystyle h^{998}(password)} . Благодаря свойству необратимости криптографических хеш-функций злоумышленник не сможет обратить хеш-функцию и получить начало цепочки. В этом примере пользователь может аутентифицироваться 1000 раз до того момента, когда цепочка будет исчерпана. Каждый раз значение передаваемого хеша разное, поэтому перехват одного хеша не позволит произвести повторную аутентификацию.

Бинарные цепочки хешей

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

На диаграмме изображено хеш-дерево, состоящее из 8 листовых узлов и цепочки хешей для третьего листа. Для того, чтобы восстановить хеш-цепочку, в дополнение к самим хеш-значениям требуется знать порядок конкатенации (справа или слева, 1 или 0).