В інформатиці алгоритм відбитків пальців або цифрового відбитку являє собою процедуру яка відображає відносно великий об

В інформатиці, алгоритм відбитків пальців або цифрового відбитку, являє собою процедуру, яка відображає відносно великий обсяг даних (комп'ютерний файл), в набагато коротший тип бітових рядків, відбиток пальця, який однозначно ідентифікує вихідні дані для всіх практичних цілей, так як відбитки пальців людини однозначно ідентифікуються лише тоді, коли мова заходить про практичні застосунки. Також, такі відбитки можуть бути використані для цілей дедуплікації даних.

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

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

Властивості відбитків пальців

Віртуальна унікальність

Для обслуговування своїх намічених цілей, алгоритм відбитків пальців повинен бути в змозі захопити унікальність файлу, що є ідеальним з точки зору віртуального зчитування. Іншими словами, імовірність знаходження двох файлів, що дають той же відбиток пальця повинна бути такою ж незначною, як ймовірність інших неминучих катастроф (наприклад, руйнування системи через війну або метеорит): імовірність яких складає — 10⁻²⁰ та менше.

Ця вимога дещо схожа на функцію контрольної суми, але є набагато жорсткішою. Для виявлення випадкового пошкодження даних або помилки передачі, достатньо, щоб контрольні суми вихідного файлу і пошкодженої версії відрізнялися, враховуючи деякі статистичні моделі помилок. У типових ситуаціях, ця мета легко досягається за допомогою 16- або 32-розрядних контрольних сум. На противагу цьому, файл з відбитками пальців повинен бути, принаймні, 64-розрядним, щоб гарантувати унікальність у віртуально-великих файлових системах (див. атака «днів народження»).

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

Компаундування

Комп'ютерні файли часто комбінуються різними способами, такими як об'єднання (як в архівних файлах) або символічне включення (як з директивою препроцесора С). Деякі алгоритми визначення відбитків пальців дозволяють робити зчитування пальців з його складових частин та їх запис до окремих файлів. Це «змішування» може бути корисне в деяких програмах, коли необхідно, наприклад, повторне компілювання.

Алгоритми відбитків пальців

Алгоритм Рабіна

Докладніше: Алгоритм Рабіна — Карпа

Алгоритм Рабіна відбитків пальців є прототипом всього класу. Це швидкий і простий у реалізації алгоритм, який підтримує компаундування та базований на математично-точному аналізі імовірності збігу. А саме, ймовірність двох рядків r та s поступитися w-бітному відбитку, що не перевищує максимум (|r|,|s|)/2^w-1, де |r| в бітах. Алгоритм вимагає попереднього вибору W-бітної внутрішнього «ключа», і результат є гарантованим до тих пір, доки рядки r та s обрані без знання ключа.

Метод Рабіна не захистить ваші данні від умисних атак. Зловмисник може легко виявити ключ і використовувати його для зміни файлів без звернення до відбитків пальців.

Криптографічні геш-функції

Докладніше: Криптографічна геш-функція

Головна геш-функція криптографічного типу в цілому може служити як високоякісна функція відбитків пальців. Вона може бути предметом пильної уваги спеціалістів з криптоаналітики, і має перевагу, в можливості захистити інформацію від умисних атак.

Недоліком криптографічних алгоритмів хешування, таких як MD5 і SHA є той факт, що вони витрачають значно більше часу на виконання, ніж алгоритм відбитків пальців Рабіна. Вони також мають перевірену ймовірність збігу. Деякі з цих алгоритмів, зокрема MD5, більше не рекомендується, як спосіб безпечного зняття відбитків пальців. Вони, як і раніше, корисні для перевірки помилок, де фальсифікація цілеспрямованих даних не є першорядним завданням.

Зняття відбитків пальців і водяних знаків для реляційних баз даних

Зняття відбитків пальців і цифрових водяних знаків для реляційних баз даних стало варіантом вирішення проблеми, яка може забезпечити захист авторських прав, виявлення підробок, відстеження зловмисника і підтримка цілісності реляційних даних. Багато методів було запропоновано в літературі для вирішення цих завдань. Зараз є можливість огляду поточного стану справ у сучасній класифікації різних підходів, відповідно до їх вимог, способу визначення відбитків пальців/водяного знаку, типу обкладинки, рівня деталізації, шляхом детальної перевірки.

Приклади застосування

NIST збільшує американську ^[en] програмним забезпеченням, яке використовує криптографічні геш-функції для файлів відбитків пальців і зіставляє їх з програмними продуктами. У базі даних ^[en], що підтримується ^[en], є база відбитків пальців «відомих, як добрі» і «відомих, як злі» комп'ютерні файли, потрібна для використання в правоохоронних органах та юридичних установах (наприклад, аналізуючи вміст вилучених дисків).

Див. також

Посилання

A. Z. Broder, "On the Resemblance and Containment of Documents, " Proceedings of Compression and Complexity of Sequences 1997, pp. 21-27, IEEE Computer Society (1988)
Detecting duplicate and near-duplicate files. US Patent 6658423 Issued on December 2, 2003
S. Brin et al., "Copy Detection Mechanisms for Digital Documents, " Proceedings of the ACM SIGMOD Annual Conference, San Jose 1995 (May 1995)
L. Fan, P. Cao, J. Almeida and A. Broder, Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol, IEEE/ACM Transactions on Networking, vol. 8, No. 3 (2000)
U. Manber, Finding Similar Files in a Large File System. Proceedings of the USENIX Winter Technical Conf. (1994)
M. O. Rabin (1981). Fingerprinting by random polynomials. Center for Research in Computing Technology Harvard University Report.
(PDF). Архів оригіналу (PDF) за 22 липня 2011. Процитовано 20 грудня 2015.{{}}: Обслуговування CS1: Сторінки з текстом «archived copy» як значення параметру title ()

[broder-1] A. Z. Broder, "On the Resemblance and Containment of Documents, " Proceedings of Compression and Complexity of Sequences 1997, pp. 21-27, IEEE Computer Society (1988)

[fingpat-2] Detecting duplicate and near-duplicate files. US Patent 6658423 Issued on December 2, 2003

[brin-3] S. Brin et al., "Copy Detection Mechanisms for Digital Documents, " Proceedings of the ACM SIGMOD Annual Conference, San Jose 1995 (May 1995)

[sumcach-4] L. Fan, P. Cao, J. Almeida and A. Broder, Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol, IEEE/ACM Transactions on Networking, vol. 8, No. 3 (2000)

[mnb-5] U. Manber, Finding Similar Files in a Large File System. Proceedings of the USENIX Winter Technical Conf. (1994)

[6] M. O. Rabin (1981). Fingerprinting by random polynomials. Center for Research in Computing Technology Harvard University Report.

[7] (PDF). Архів оригіналу (PDF) за 22 липня 2011. Процитовано 20 грудня 2015.{{}}: Обслуговування CS1: Сторінки з текстом «archived copy» як значення параметру title ()