В информатике алгоритм снятия отпечатков пальцев — это процедура, которая сопоставляет произвольно большой элемент данных (например, компьютерный файл ) с гораздо более короткой строкой битов , его отпечатком пальца , который однозначно идентифицирует исходные данные для всех практических целей, так же как человеческие отпечатки пальцев однозначно идентифицируют людей для практических целей. [1] Этот отпечаток пальца может использоваться для целей дедупликации данных . Это также называется снятием отпечатков пальцев файлов , снятием отпечатков пальцев данных или снятием отпечатков пальцев структурированных данных .
Отпечатки пальцев обычно используются для того, чтобы избежать сравнения и передачи объемных данных. Например, веб-браузер или прокси-сервер может эффективно проверить, был ли изменен удаленный файл, извлекая только его отпечаток и сравнивая его с отпечатком ранее извлеченной копии. [2] [3] [4] [5] [6]
Функции отпечатков пальцев можно рассматривать как высокопроизводительные хэш-функции, используемые для уникальной идентификации значительных блоков данных, где криптографические хэш-функции могут быть ненужными.
Существуют специальные алгоритмы для аудио- и видео- дактилоскопии .
Чтобы соответствовать своему назначению, алгоритм снятия отпечатков должен быть способен с виртуальной уверенностью фиксировать личность файла. Другими словами, вероятность столкновения — двух файлов, дающих одинаковый отпечаток — должна быть пренебрежимо мала по сравнению с вероятностью других неизбежных причин фатальных ошибок (таких как разрушение системы войной или метеоритом ) : скажем, 10 −20 или меньше.
Это требование в некоторой степени похоже на требование функции контрольной суммы , но гораздо более строгое. Для обнаружения случайного повреждения данных или ошибок передачи достаточно, чтобы контрольные суммы исходного файла и любой поврежденной версии различались с почти полной уверенностью, учитывая некоторую статистическую модель для ошибок. В типичных ситуациях эта цель легко достигается с помощью 16- или 32-битных контрольных сумм. Напротив, отпечатки файлов должны быть длиной не менее 64 бит, чтобы гарантировать виртуальную уникальность в больших файловых системах (см. атака на день рождения ).
При доказательстве вышеуказанного требования необходимо учитывать, что файлы генерируются в высшей степени неслучайными процессами, которые создают сложные зависимости между файлами. Например, в типичной бизнес-сети обычно можно найти много пар или кластеров документов, которые отличаются только незначительными правками или другими небольшими изменениями. Хороший алгоритм снятия отпечатков должен гарантировать, что такие «естественные» процессы генерируют различные отпечатки с желаемым уровнем уверенности.
Компьютерные файлы часто объединяются различными способами, такими как конкатенация (как в архивных файлах ) или символическое включение (как в директиве #include препроцессора C ). Некоторые алгоритмы снятия отпечатков позволяют вычислить отпечаток составного файла из отпечатков его составных частей. Это свойство «составного» может быть полезным в некоторых приложениях, например, для определения необходимости перекомпиляции программы.
Алгоритм снятия отпечатков Рабина является прототипом класса. [7] Он быстр и прост в реализации, допускает компаундирование и поставляется с математически точным анализом вероятности коллизии. А именно, вероятность того, что две строки r и s дадут один и тот же w -битный отпечаток, не превышает max(| r |,| s |)/2 w -1 , где | r | обозначает длину r в битах. Алгоритм требует предварительного выбора w -битного внутреннего «ключа», и эта гарантия сохраняется до тех пор, пока строки r и s выбираются без знания ключа.
Метод Рабина не защищен от вредоносных атак. Агент-соперник может легко обнаружить ключ и использовать его для изменения файлов, не меняя свой отпечаток.
Основные криптографические хеш-функции, как правило, могут служить высококачественными функциями отпечатков пальцев, подвергаются тщательному контролю со стороны криптоаналитиков и имеют то преимущество, что считаются защищенными от вредоносных атак.
Недостатком криптографических хэш-алгоритмов, таких как MD5 и SHA, является то, что они выполняются значительно дольше, чем алгоритм отпечатков пальцев Рабина. У них также нет проверенных гарантий вероятности коллизии. Некоторые из этих алгоритмов, в частности MD5 , больше не рекомендуются для безопасного снятия отпечатков пальцев. Они по-прежнему полезны для проверки ошибок, когда преднамеренное изменение данных не является основной проблемой.
NIST распространяет библиотеку справочного программного обеспечения, Американскую национальную библиотеку справочного программного обеспечения , которая использует криптографические хэш-функции для отпечатков файлов и сопоставления их с программными продуктами. База данных HashKeeper , поддерживаемая Национальным центром по борьбе с наркотиками , представляет собой хранилище отпечатков «известно хороших» и «известно плохих» компьютерных файлов для использования в правоохранительных органах (например, для анализа содержимого изъятых дисковых накопителей).
В настоящее время отпечатки пальцев являются наиболее широко применяемым подходом к обнаружению схожести контента. Этот метод формирует репрезентативные дайджесты документов, выбирая из них набор из нескольких подстрок ( n-грамм ). Наборы представляют отпечатки пальцев, а их элементы называются мелочами. [10] [11]
Подозрительный документ проверяется на плагиат путем вычисления его отпечатка и запроса мелочей с предварительно вычисленным индексом отпечатков для всех документов справочной коллекции. Совпадение мелочей с отпечатками других документов указывает на общие текстовые сегменты и предполагает потенциальный плагиат, если они превышают выбранный порог сходства. [12] Вычислительные ресурсы и время являются ограничивающими факторами для снятия отпечатков, поэтому этот метод обычно сравнивает только подмножество мелочей, чтобы ускорить вычисления и обеспечить проверку в очень больших коллекциях, таких как Интернет. [10]Инфраструктура бесключевых подписей (KSI) — это глобально распределенная система для предоставления услуг временной отметки и цифровой подписи с поддержкой сервера. Создаются глобальные деревья хэшей с посекундной частотой и публикуются их корневые хэш-значения. Мы обсуждаем некоторые проблемы качества обслуживания, возникающие при практической реализации сервиса, и представляем решения для избежания отдельных точек отказа и обеспечения обслуживания с разумной и стабильной задержкой. Guardtime AS эксплуатирует инфраструктуру KSI в течение 5 лет. Мы описываем, как построена инфраструктура KSI, и извлекаем уроки за период эксплуатации сервиса.
pHash — это библиотека программного обеспечения с открытым исходным кодом, выпущенная по лицензии GPLv3, которая реализует несколько алгоритмов перцептивного хэширования и предоставляет API-интерфейс на языке C для использования этих функций в ваших собственных программах. Сам pHash написан на C++.