Fingeravtryck (dator)

Inom datavetenskap är en fingeravtrycksalgoritm en procedur som mappar ett godtyckligt stort dataobjekt (som en datorfil ) till en mycket kortare bitsträng , dess fingeravtryck , som unikt identifierar originaldata för alla praktiska ändamål precis som mänskliga fingeravtryck unikt identifierar människor för praktiska ändamål. Detta fingeravtryck kan användas för datadeduplicering . Detta kallas också filfingeravtryck, datafingeravtryck eller strukturerad datafingeravtryck.

Fingeravtryck används vanligtvis för att undvika jämförelse och överföring av skrymmande data. Till exempel kan en webbläsare eller proxyserver effektivt kontrollera om en fjärrfil har ändrats, genom att bara hämta dess fingeravtryck och jämföra det med det från den tidigare hämtade kopian.

Fingeravtrycksfunktioner kan ses som högpresterande hashfunktioner som används för att unikt identifiera betydande datablock där kryptografiska hashfunktioner kan vara onödiga. Ljudfingeravtrycksalgoritmer ska inte förväxlas med denna typ av fingeravtrycksfunktion.

En hashfunktion på jobbet

Egenskaper

Virtuell unikhet

För att tjäna sina avsedda syften måste en fingeravtrycksalgoritm kunna fånga identiteten på en fil med virtuell säkerhet. Med andra ord måste sannolikheten för en kollision - två filer som ger samma fingeravtryck - vara försumbar, jämfört med sannolikheten för andra oundvikliga orsaker till fatala fel (som att systemet förstörs av krig eller av en meteorit ): säg, 10 ^-20 eller mindre.

Detta krav påminner något om det för en kontrollsummafunktion , men är mycket strängare. För att upptäcka oavsiktlig datakorruption eller överföringsfel räcker det att kontrollsummorna för originalfilen och eventuell skadad version kommer att skilja sig med nästan säkerhet, givet någon statistisk modell för felen. I typiska situationer uppnås detta mål lätt med 16- eller 32-bitars kontrollsummor. Däremot måste filfingeravtryck vara minst 64-bitars långa för att garantera virtuell unikhet i stora filsystem (se födelsedagsattack ) .

När man bevisar ovanstående krav måste man ta hänsyn till att filer genereras av mycket icke-slumpmässiga processer som skapar komplicerade beroenden mellan filer. Till exempel, i ett typiskt affärsnätverk, hittar man vanligtvis många par eller kluster av dokument som endast skiljer sig åt genom mindre redigeringar eller andra små modifieringar. En bra fingeravtrycksalgoritm måste säkerställa att sådana "naturliga" processer genererar distinkta fingeravtryck, med önskad grad av säkerhet.

Sammansättning

Datorfiler kombineras ofta på olika sätt, såsom sammanlänkning (som i arkivfiler ) eller symbolisk inkludering (som med C-förprocessorns # include- direktiv). Vissa fingeravtrycksalgoritmer tillåter att fingeravtrycket för en sammansatt fil kan beräknas från fingeravtrycken från dess beståndsdelar. Den här "compounding"-egenskapen kan vara användbar i vissa applikationer, som att upptäcka när ett program behöver kompileras om.

Algoritmer

Rabins algoritm

Rabins fingeravtrycksalgoritm är klassens prototyp. Det är snabbt och enkelt att implementera, tillåter sammansättning och kommer med en matematiskt exakt analys av sannolikheten för kollision. Sannolikheten för att två strängar r och s ger samma w -bit fingeravtryck överstiger nämligen inte max(| r |,| s |)/2 ^{w -1} , där | r | anger längden på r i bitar. Algoritmen kräver det tidigare valet av en w -bit intern "nyckel", och denna garanti gäller så länge som strängarna r och s väljs utan kunskap om nyckeln.

Rabins metod är inte säker mot skadliga attacker. En kontradiktor kan enkelt upptäcka nyckeln och använda den för att ändra filer utan att ändra deras fingeravtryck.

Kryptografiska hashfunktioner

Vanliga kryptografiska hashfunktioner kan i allmänhet fungera som fingeravtrycksfunktioner av hög kvalitet, är föremål för intensiv granskning från kryptoanalytiker och har fördelen att de tros vara säkra mot skadliga attacker.

En nackdel med kryptografiska hashalgoritmer som MD5 och SHA är att de tar betydligt längre tid att exekvera än Rabins fingeravtrycksalgoritm. De saknar också bevisade garantier för kollisionssannolikheten. Vissa av dessa algoritmer, särskilt MD5 , rekommenderas inte längre för säker fingeravtryck. De är fortfarande användbara för felkontroll, där målmedveten datamanipulering inte är ett primärt problem.

Applikationsexempel

NIST distribuerar ett referensbibliotek för programvara, American National Software Reference Library , som använder kryptografiska hashfunktioner för att fingeravtrycka filer och mappa dem till mjukvaruprodukter. HashKeeper - databasen, som underhålls av National Drug Intelligence Center , är ett arkiv med fingeravtryck av "kända för att vara bra" och "kända för att vara dåliga" datorfiler, för användning i brottsbekämpande tillämpningar (t.ex. för att analysera innehållet i beslagtagna diskenheter) .

Se även