В информатике , алгоритм дактилоскопии является процедурой , которая отображает сколь угодно большой данные элемент (например, компьютерный файл ) в гораздо более короткую битовой строку, его отпечаток пальца , который однозначно идентифицирует исходные данные для всех практических целей [1] как человек отпечатки пальцев однозначно идентифицируют людей для практических целей. Этот отпечаток может использоваться для дедупликации данных . Это также называется отпечатком файла, отпечатком данных или отпечатком структурированных данных.
Отпечатки пальцев обычно используются, чтобы избежать сравнения и передачи объемных данных. Например, веб-браузер или прокси-сервер могут эффективно проверять, был ли изменен удаленный файл, путем получения только его отпечатка пальца и сравнения его с отпечатком ранее полученной копии. [2] [3] [4] [5] [6]
Функции отпечатков пальцев можно рассматривать как высокопроизводительные хэш-функции, используемые для уникальной идентификации существенных блоков данных, где криптографические хеш-функции могут быть ненужными. Алгоритмы звукового отпечатка пальца не следует путать с этим типом функции отпечатка пальца.
Свойства [ править ]
Виртуальная уникальность [ править ]
Чтобы служить своему прямому назначению, алгоритм снятия отпечатков пальцев должен иметь возможность фиксировать идентичность файла с виртуальной достоверностью. Другими словами, вероятность столкновения двух файлов с одним и тем же отпечатком пальца должна быть незначительной по сравнению с вероятностью других неизбежных причин фатальных ошибок (например, система, разрушенная войной или метеоритом ): скажем, 10 −20 или меньше.
Это требование в чем-то похоже на функцию контрольной суммы, но гораздо более жесткое. Чтобы обнаружить случайное повреждение данных или ошибки передачи, достаточно, чтобы контрольные суммы исходного файла и любой поврежденной версии почти наверняка различались, учитывая некоторую статистическую модель ошибок. В типичных ситуациях эта цель легко достигается с помощью 16- или 32-битных контрольных сумм. Напротив, отпечатки файлов должны быть не менее 64-битной длины, чтобы гарантировать виртуальную уникальность в больших файловых системах (см. « Атака по случаю дня рождения» ).
При доказательстве вышеуказанного требования необходимо учитывать, что файлы генерируются сильно неслучайными процессами, которые создают сложные зависимости между файлами. Например, в типичной бизнес-сети обычно можно найти много пар или кластеров документов, которые отличаются только незначительными правками или другими небольшими изменениями. Хороший алгоритм снятия отпечатков пальцев должен гарантировать, что такие «естественные» процессы генерируют четкие отпечатки пальцев с желаемым уровнем достоверности.
Составление [ править ]
Компьютерные файлы часто комбинироваться различными способами, такими как конкатенация (как в архивных файлах ) или символического включения (как с C препроцессор «s #include директивы). Некоторые алгоритмы снятия отпечатков позволяют вычислить отпечаток составного файла по отпечаткам его составных частей. Это свойство «сложения» может быть полезно в некоторых приложениях, например, для определения того, когда программа должна быть перекомпилирована.
Алгоритмы [ править ]
Алгоритм Рабина [ править ]
Алгоритм снятия отпечатков Рабина [7] является прототипом класса. Его легко и быстро внедрить, он позволяет производить компаундирование и дает математически точный анализ вероятности столкновения. А именно, вероятность того, что две строки r и s дадут один и тот же w- битный отпечаток, не превышает max (| r |, | s |) / 2 w -1 , где | г | обозначает длину r в битах. Алгоритм требует предварительного выбора w- битного внутреннего «ключа», и эта гарантия сохраняется до тех пор, пока строки r и s выбираются без знания ключа.
Метод Рабина не защищен от злонамеренных атак. Злоумышленник может легко обнаружить ключ и использовать его для изменения файлов без изменения своего отпечатка пальца.
Криптографические хеш-функции [ править ]
Обычные хэш-функции криптографического уровня обычно могут служить высококачественными функциями отпечатков пальцев, подлежат тщательной проверке со стороны криптоаналитиков и имеют то преимущество, что они считаются безопасными от злонамеренных атак.
Недостатком алгоритмов криптографического хеширования, таких как MD5 и SHA, является то, что они требуют значительно больше времени для выполнения, чем алгоритм отпечатка пальца Рабина. У них также нет проверенных гарантий вероятности столкновения. Некоторые из этих алгоритмов, особенно MD5 , больше не рекомендуются для безопасного снятия отпечатков пальцев. Они по-прежнему полезны для проверки ошибок, когда целенаправленная подделка данных не является основной проблемой.
Отпечатки пальцев и водяные знаки для реляционных баз данных [ править ]
Отпечатки пальцев и цифровые водяные знаки для реляционных баз данных появились в качестве возможных решений, обеспечивающих защиту авторских прав, обнаружение несанкционированного доступа, отслеживание предателей и поддержание целостности реляционных данных. В литературе было предложено множество методов для решения этих задач. Доступен обзор современного состояния и классификация различных подходов в зависимости от их намерений, способа выражения отпечатка пальца / водяного знака, типа обложки, уровня детализации и их проверяемости. [8]
Примеры применения [ править ]
NIST распространяет справочную библиотеку программного обеспечения, Американскую национальную справочную библиотеку программного обеспечения , которая использует криптографические хеш-функции для отпечатков файлов и сопоставления их с программными продуктами. База данных HashKeeper , поддерживаемая Национальным центром наркологической разведки , представляет собой хранилище отпечатков пальцев « заведомо исправных» и « заведомо плохих» компьютерных файлов для использования в приложениях правоохранительных органов (например, для анализа содержимого изъятых дисковых накопителей). .
См. Также [ править ]
- Акустическая дактилоскопия
- Автоматическое распознавание контента
- Снятие отпечатков пальцев на холсте
- Цифровое видео отпечатков пальцев
- Отпечатки стека TCP / IP
- Отпечаток устройства
- Код исправления ошибок
- Отпечаток открытого ключа
- Функция рандомизации
- Доля использования веб-браузеров
Ссылки [ править ]
 | Это включает в себя список общих ссылок , но он остается в значительной степени непроверенным, поскольку в нем отсутствует достаточное количество соответствующих встроенных ссылок . ( Февраль 2018 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) |
- ^ AZ Бродер. Некоторые применения метода дактилоскопии Рабина. В Последовательностях II: Методы связи, безопасности и информатики, страницы 143-152. Springer-Verlag, 1993 г.
- ^ Обнаружение повторяющихся и почти повторяющихся файлов. Патент США 6658423, выдан 2 декабря 2003 г.
- ^ AZ Бродер (1997). О сходстве и содержании документов . Труды сжатия и сложности последовательностей . Компьютерное общество IEEE. С. 21–27. CiteSeerX 10.1.1.24.779 . DOI : 10,1109 / SEQUEN.1997.666900 . ISBN 978-0-8186-8132-5. S2CID 11748509 .
- ^ Брин, S . и Дэвис, Дж. и Гарсия-Молина, Х. (1995) Механизмы обнаружения копирования для цифровых документов . В: Международная конференция ACM по управлению данными (SIGMOD 1995), 22-25 мая 1995 г., Сан-Хосе, Калифорния, с сайта stanford.edu . Архивировано 18.08.2016. Проверено 01.11.2019.
- ^ Л. Фан, П. Цао, Дж. Алмейда и А. Бродер, Summary Cache: Scalable Wide-Area Web Cache Sharing Protocol, IEEE / ACM Transactions on Networking, vol. 8, № 3 (2000)
- ^ У. Манбер, Поиск похожих файлов в большой файловой системе. Материалы зимней технической конференции USENIX. (1994)
- ^ М.О. Рабин Дактилоскопия случайными многочленами. Центр исследований в области вычислительной техники, отчет Гарвардского университета TR-15-81 (1981)
- ^ http://www.jucs.org/jucs_16_21/watermarking_techniques_for_relational/jucs_16_21_3164_3190_halder.pdf
