N-Hash — криптографическая хеш-функция на основе циклической функции FEAL. В настоящее время считается небезопасной.
Была разработана в 1990 году фирмой Nippon Telegraph and Telephone (также разработавшей FEAL).
Изначально, функция N-Hash была предназначена для того, чтобы решить проблему подмены информации на пути между двумя пользователями телефонной связи (Nippon Telegraph and Telephone — телекоммуникационная компания) и ускорить поиск данных. Например, если человек посылает смс-сообщение, то перед доставкой оно будет проверено на подлинность с помощью хеш-функции. А если пользователю продукции Nippon Telegraph and Telephone надо быстро найти в телефоне чей-либо контакт, то с помощью N-Hash можно упростить процесс поиска имени в списке. Это осуществляется благодаря тому, что хеш-кодом (маленькой по объёму определяющей частью контакта) имени объявляется первая буква контакта.
История возникновения В основе алгоритма N-Hash лежит блочный алгоритм шифрования FEAL. Крупнейшая телекоммуникационная компания Nippon Telegraph and Telephone создала FEAL на основе DES. Но хотя этот алгоритм и выигрывает в быстродействии у DES, он является очень ненадежным и легко уязвимым: криптоаналитику требовалось очень мало информации, чтобы взломать алгоритм. Именно взлом алгоритма FEAL повлек за собой появление хеш-функции N-Hash в 1990 году. N-Hash также выигрывает в скорости у DES: по сравнению с 9 Кбит/сек у DES, N-Hash работает со скоростью 24 Кбит/сек для 15-раундовой схемы и со скоростью 29 Кбит/сек для 12-раундовой. При этом Nippon Telegraph and Telephone добилась повышения надёжности по сравнению с FEAL.
В течение некоторого времени алгоритм N-Hash использовался фирмой Nippon Telegraph and Telephone в соответствии с целями данной функции, но через некоторое время был разработан метод дней рождения, который с лёгкостью взламывал этот алгоритм. В связи со взломом отказались не только от N-Hash, но и почти от всех функций, основанных на блочных шифрах, так как для всех них характерна одна и та же проблема: они легко уязвимы методом дней рождения. Вместо них теперь используют более надежные функции, основанные на MD — технологиях: MD5, SHA-1 и другие, приведенные в списке функций, которые на данный момент считаются надежными (согласно стандарту ISO/IEC 10118).
Использование Функция N-Hash использовалась в течение недолгого времени в начале 1990-х годов, пока не была взломана методом дней рождения. N-Hash предназначалась для решения проблемы подмены данных: Для современного человека эта проблема может легко быть описана на примере взаимодействия человека и интернет-магазина. Когда пользователь заказывает какой-нибудь товар в интернет-магазине, то магазин присылает ему номер заказа, сумму платежа и т. д. Далее, когда пользователь пытается оплатить заказ с помощью, например, Webmoney, то Webmoney вычисляет хеш-код полученного сообщения и сравнивает его с хеш-кодом, полученным от интернет-магазина. Если эти хеш-коды совпадают, то информация, присланная пользователем, правдива. Если не совпадают, то информация определяется как ложная и платеж не проходит. Другой вариант использования прост: упорядочивание контактов в мобильном телефоне по алфавиту и поиск контакта по первой букве. Хеш-кодом имени выбирается первая буква этого имени, следовательно, когда человек нажимает некоторую букву в своем телефоне, то ищется хеш-код, который совпадает с этой буквой и на экран выводятся контакты, начинающиеся с неё.
Особенности N-Hash
Однонаправленность Определение: Пусть — сообщение некоторой длины.
Функция называется однонаправленной, если из равенства
легко: найти хеш-код , зная сообщение очень трудоёмко: найти сообщение по известному хеш-коду (т. е. если хеш-код пароля стал известен хакеру, то пароль он по нему не найдет); найти отличное от сообщение , такое что их хеш-коды совпадают. Проще определение можно записать так:
Однонаправленность — это «отпечаток пальца»: Если дан конкретный человек, то можно взять у него отпечаток пальца; Невозможно найти человека по отпечатку его пальца (если нет базы данных с отпечатками пальцев всех людей, а её нет); Невозможно найти второго человека с таким же как у другого отпечатком пальца. Однонаправленность решает очень важную проблему. Рассмотрим её на примере. Алиса и Боб традиционно обозначают субъектов передачи информации.
Примеры Допустим, Алиса подписала контракт с известным Алисе и Бобу хеш-кодом . Если бы была неоднонаправленная, то Боб мог бы найти такой другой контракт , что и, значит, смог бы утверждать, что Алиса подписала . Допустим, Алиса имеет один и тот же отпечаток пальца h с каким-нибудь преступником, тогда Боб смог бы утверждать, что этот преступник — Алиса.
Устойчивость к столкновениям Чтобы предотвратить возможность Алисы использовать метод «дней рождения» для обмана Боба, очень удобно ввести ещё более сильное условие, чем условие однонаправленности. H такова, что трудно найти сообщения и , такие что их хеш-коды совпадают. То есть невозможно найти двух человек с одинаковыми отпечатками пальцев.
Данное условие называется устойчивостью к столкновениям и для хеш-функции N-Hash оно не выполняется.
По причине неустойчивости к столкновениям Алиса может обмануть Боба таким образом (метод «дней рождения»): Алиса пишет две версии контракта: одна из них выгодна для Боба, а другая нет; Внося небольшие изменения в каждый контракт (например, пробел заменяет на два пробела), она добьется того, что версий контрактов будет достаточно много для подбора и , для которых совпадают хеш-коды (версия выгодна Бобу, а — нет) (если в контракте 34 строки, то, внося или не внося изменения в каждую из строк, легко получить версий контрактов); Теперь Алиса сможет доказать, что Боб подписал . Для того, чтобы избежать подобной проблемы, достаточно вносить косметические изменения в подписываемый контракт. И хотя это действие никак не изменяет хеш-функцию H, а, значит, никак не влияет на её устойчивость к столкновениям, но человек этим действием получит новую версию контракта, хеш-код которого не совпадает с хеш-кодом версии контракта злоумышленника. То есть, если Боб в 5-й строке поставит в каком-нибудь месте запятую, или поставит две точки вместо одной, то Алиса не сможет доказать, что он подписал другой контракт (так как его хеш-код уже не совпадает с хеш-кодом контракта Алисы).
Можно рассмотреть жизненный пример: когда нотариус ставит печать в подписываемый контракт, он вносит туда косметические изменения.
Цели N-Hash Для того, чтобы понять как работает функция N-Hash, необходимо перейти на более научную речь. Ниже приведены цели данной функции не на примерах, а в соответствии с тем, как они осуществляются и с соответствующей терминологией. Обеспечение целостности информации:
Данное свойство необходимо для того, чтобы исключить возможность злоумышленника внедрить некоторую ложную информацию в исходное сообщение. Для обеспечения целостности должна быть возможность обнаружить любые изменения в тексте сообщения (замена, вставка, удаление). Целостность обеспечивается путём внедрения в исходное сообщение избыточной информации, которая будет являться проверочной комбинацией. Такая комбинация называется контрольной суммой и её можно вычислить с помощью специального алгоритма. Так как этот алгоритм зависит от секретного ключа, то внедрение ложной информации в сообщение маловероятно.
, где salt — избыточная информация, M — сообщение - контрольная сумма;
Из формулы следует, что если меняется salt, то меняется и S (контрольная сумма), а значит изменялось и и .
То есть можно сделать вывод, что была добавлена ложная информация. Сжатие документа: Функция N-Hash работает с сообщениями M произвольной длины. При этом на выходе получается хеш-код фиксированной длины в 128 бит. Это получается за счет того, что сообщение делится на блоки , размером 128 бит, и алгоритм работает последовательно с каждым из блоков. Обеспечение достоверности электронных данных:
Данное свойство выполняется для однонаправленных функций, какой и является N-Hash. Достоверность сообщения M проверяется путём нахождения конечного хеш-кода (дайджеста сообщения) дважды (отсылающая и принимающая стороны). Результаты сравниваются и, если они совпадают, то информация достоверна. Целостность не гарантирует достоверность. Обеспечение конфиденциальности: на сайтах, где нужно вводить логин и пароль, пароль после ввода переводится в хеш-код. То есть изначально пользователь вводит пароль M, но для входа в защищённую область используется хеш-код . По известному хеш-коду h и функции H вычислить M очень трудно, чем и обеспечивается конфиденциальность пароля. Аутентификация пользователей: Аутентификация — это процедура проверки подлинности пользователя или данных при помощи некоторого критерия.
Возникает вопрос, как хеш-функция обеспечивает правдивость аутентификации. Это легко показать на примере.
Когда пользователь вводит логин и пароль на каком-либо сайте, его пароль преобразуется в хеш-код и передается по сети для аутентификации. Очевидно, что для того чтобы войти под чужую учётную запись достаточно выяснить хеш-код пароля, а затем по формуле (h-хеш-код, M — пароль) найти пароль. Но N-Hash, являющаяся однонаправленной функцией, обеспечивает сохранность пароля, так как это уравнение для однонаправленных функций решается очень трудоёмко (не с помощью персонального компьютера).
Алгоритм Алгоритм N-Hash основан на циклическом повторении (12 или 15 раз — число раундов) операций. На входе имеется хеш-код и он может быть произвольным, на выходе получается хеш-код h сообщения M, которое необходимо хешировать. При этом размер выходящего хеш-кода фиксирован и равен 128 бит, тогда как размер M произволен.
Основные обозначения — сообщение, которое необходимо хешировать; — блок сообщения длиной 128 бит. Для того, чтобы хешировать сообщение необходимо поделить его на блоки ; — хеш-код i-го шага; — константа, длиной 128 бит; — конкатенация; , где , где k=1, 2, 3, 4; , длиной 24 бит; EXG — функция, которая меняет местами старшие и младшие разряды (64 младших и 64 старших); PS — преобразующая функция;
Описание алгоритма
На схеме справа представлены схематические обозначения операций, которые присутствуют на нижеследующих схемах. Покоординатное (попарное) суммирование означает сложение по модулю 2; Если x поступает на вход функции f, то на выходе получается f(x).
Один цикл работы N-Hash
Ниже представлен один цикл работы алгоритма N-Hash. На вход функции g подается хеш-код (i-1)-го шага и i-й блок сообщения . При этом выбирается произвольно: например, он может быть нулевым. А также подается на выход на операцию сложения по модулю 2, то есть результат (хеш-код следующего шага) будет выглядеть так: (нечто пока неизвестное). Из схемы видно, что подается не только на XOR, но и на выход на операцию сложения по модулю 2. То есть теперь в соответствии с первым пунктом результат выглядит таким образом: (оставшееся пока неизвестным нечто). Оставшееся пока неизвестным нечто находится после прохождения каскада из восьми преобразующих функций. Его получение может быть описано таким образом: Функция EXG меняет местами старшие и младшие разряды и прибавляет к результату , после чего результат складывает по модулю 2 с . Как видно из схемы, результат подается последовательно на входы j преобразующих функций, вторым аргументом которых является сумма , где j=1, … , 8. В результате получается хеш-код i-го шага : .
Преобразующая функция
Возникает вопрос, как действует преобразующая функция .
Рассмотрим верхнюю часть схемы до перекрестья.
Исходное сообщение разбивается на блоки по бита.
Будем считать промежуточными выходами входы в нижнюю часть схемы. и подаются на промежуточные выходы, а на два других выхода подаются операции и . Теперь можно результаты на промежуточных выходах переобозначить и через них, аналогично верхней части, найти результаты на выходе нижней части, то есть и всей схемы в целом.