지문(컴퓨팅)

Fingerprint (computing)
이 기사는 일반적인 지문 채취 알고리즘에 관한 것입니다.오디오 고유의 알고리즘에 대해서는, 음향 핑거 프린트를 참조해 주세요.비디오 고유의 알고리즘에 대해서는, 디지털 비디오 핑거 프린팅을 참조해 주세요.사람의 지문과 일치하는 알고리즘에 대해서는 지문-알고리즘을 참조해 주세요.브라우저 식별 방법은 브라우저 지문을 참조하십시오.그 외의 용도는, 디지털 지문을 참조해 주세요.

컴퓨터 과학에서 핑거프린트 알고리즘은 인간의 지문이 실제 목적을 위해 사람을 고유하게 식별하듯이 임의의 대용량 데이터 항목(컴퓨터 파일 등)을 훨씬[1] 짧은 비트 문자열인 지문에 매핑하는 절차입니다.이 지문은 데이터 중복 제거 목적으로 사용될 수 있습니다.이를 파일 핑거프린트, 데이터 핑거프린트 또는 구조화된 데이터 핑거프린트라고도 합니다.

지문은 일반적으로 대용량 데이터의 비교 및 전송을 방지하기 위해 사용됩니다.예를 들어 웹 브라우저나 프록시 서버는 지문만 가져와 이전에 가져온 [2][3][4][5][6][7]복사본과 비교하는 방식으로 원격 파일이 변경되었는지 여부를 효율적으로 확인할 수 있습니다.

지문 함수는 암호화 해시 함수가 불필요할 수 있는 상당한 데이터 블록을 고유하게 식별하기 위해 사용되는 고성능 해시 함수로 간주될 수 있습니다.오디오 지문 알고리즘은 이러한 유형의 지문 기능과 혼동하지 마십시오.

작업 중인 해시 함수

특성.

가상 고유성

의도된 목적을 달성하려면 지문 인증 알고리즘이 파일의 ID를 가상적으로 확실하게 캡처할 수 있어야 합니다.즉, 충돌의 확률(같은 지문을 생성하는 2개의 파일)은, 다른 피할 수 없는 에러(전쟁이나 운석에 의한 시스템 파괴 등)의 발생 확률에 비해, 무시할 수 있는 것이어야−20 합니다.

이 요건은 체크섬 함수와 다소 유사하지만 훨씬 더 엄격합니다.우발적인 데이터 파손 또는 전송 오류를 검출하기 위해서는 오류에 대한 통계 모델을 고려할 때 원본 파일과 손상된 버전의 체크섬이 거의 확실하게 달라지는 것으로 충분합니다.일반적인 상황에서는 16비트 또는 32비트 체크섬을 사용하면 이 목표를 쉽게 달성할 수 있습니다.반면 파일 지문 길이는 64비트 이상이어야 대규모 파일 시스템에서 가상 고유성을 보장할 수 있습니다(생일 공격 참조).

위의 요건을 증명할 때는 파일 간에 복잡한 의존관계를 만드는 매우 랜덤하지 않은 프로세스에 의해 파일이 생성된다는 점을 고려해야 합니다.예를 들어, 일반적인 비즈니스 네트워크에서는 일반적으로 사소한 편집이나 기타 약간의 수정만으로 다른 문서의 쌍 또는 클러스터를 많이 찾을 수 있습니다.적절한 핑거프린트 알고리즘은 이러한 "자연적인" 프로세스가 원하는 수준의 확실한 지문을 생성하도록 보장해야 합니다.

배합

컴퓨터 파일은 종종 연결(아카이브 파일처럼) 또는 기호 포함(C 프리프로세서처럼)과 같은 다양한 방법으로 결합됩니다.#diagnosting directive 。일부 핑거프린트 알고리즘에서는 컴포지트 파일의 지문을 구성 부품의 지문으로 계산할 수 있습니다.이 "합성" 속성은 프로그램을 다시 컴파일해야 하는 시기를 감지하는 등 일부 응용 프로그램에서 유용할 수 있습니다.

알고리즘

라빈 알고리즘

라빈의 지문 채취 알고리즘은[8] 이 클래스의 원형입니다.빠르고 쉽게 구현할 수 있으며 복합화가 가능하며 충돌 확률을 수학적으로 정밀하게 분석할 수 있습니다.즉, 2개의 문자열 r과 s가 같은 w비트 핑거프린트를 생성할 확률은 max(r , s )/2를w-1 넘지 않습니다.여기서 r은 비트 단위의 r 길이를 나타냅니다.이 알고리즘에서는 w비트 내부 "키"의 이전 선택이 필요하며, 이 보증은 스트링 r과 s가 키를 인식하지 않고 선택되는 한 유지됩니다.

Rabin의 방법은 악의적인 공격으로부터 안전하지 않습니다.적대적 에이전트는 쉽게 키를 검색하여 지문을 변경하지 않고 파일을 수정하는 데 사용할 수 있습니다.

암호화 해시 함수

주요 기사: 암호화 해시 함수

주류 암호 등급 해시 함수는 일반적으로 고품질의 지문 함수로 기능할 수 있으며, 암호 분석가의 집중적인 조사를 받아야 하며 악의적인 공격으로부터 안전하다고 생각되는 이점을 가지고 있습니다.

MD5 및 SHA와 같은 암호화 해시 알고리즘의 단점은 Rabin의 지문 알고리즘보다 실행 시간이 상당히 오래 걸린다는 것입니다.또한 충돌 확률에 대한 입증된 보장도 없습니다.이러한 알고리즘의 일부, 특히 MD5는, 시큐어 핑거 프린트에 권장되지 않게 되었습니다.의도적인 데이터 조작이 주된 문제가 아닌 에러 체크에 도움이 됩니다.

관계형 데이터베이스의 지문 및 워터마크

관계형 데이터베이스의 지문 및 디지털 워터마킹은 저작권 보호, 변조 탐지, 배신자 추적 및 관계형 데이터의 무결성 유지를 위한 후보 솔루션으로 부상했습니다.이러한 목적을 다루기 위해 문헌에서 많은 기법이 제안되었다.현재 최신 기술과 그 의도에 따른 다양한 접근법의 분류, 지문/워터마크, 커버 유형, 입도 수준 및 검증 가능성에 대한 조사를 이용할 [9]수 있다.

응용 프로그램 예시

NIST는 암호화 해시 함수를 사용하여 파일에 지문을 찍어 소프트웨어 제품에 매핑하는 소프트웨어 참조 라이브러리인 American National Software Reference Library를 배포합니다.National Drug Intelligence Center가 관리하는 HashKeeper 데이터베이스는 법 집행 애플리케이션(예: 압수된 디스크 드라이브의 내용 분석)에서 사용하기 위해 "정상" 및 "불량" 컴퓨터 파일의 지문을 보관하는 저장소입니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ A. Z. 브로더Rabin의 지문 채취 방법의 일부 응용 프로그램.시퀀스 II: 통신, 보안 및 컴퓨터 과학의 방법, 143-152페이지.Springer-Verlag, 1993년
  2. ^ 중복 및 거의 중복된 파일을 탐지하고 있습니다.2003년 12월 2일 미국 특허 6658423 발표
  3. ^ A. Z. Broder (1997). On the Resemblance and Containment of Documents. Proceedings of Compression and Complexity of Sequences. IEEE Computer Society. pp. 21–27. CiteSeerX 10.1.1.24.779. doi:10.1109/SEQUEN.1997.666900. ISBN 978-0-8186-8132-5. S2CID 11748509.
  4. ^ Brin, S. and Davis, J. 및 Garcia-Molina, H.(1995년) 디지털 문서를 위한 복사 감지 메커니즘.인: ACM International Conference on Management of Data(SIGMOD 1995), 1995년 5월 22일부터 25일까지 캘리포니아주 새너제이(stanford.edu)에서.2016년 8월 18일 아카이브 완료.2019년 11월 1일 취득.
  5. ^ L. Fan, P. Cao, J. Almeida 및 A.Broder, Summary Cache: 스케일러블 Wide-Area Web Cache Sharing Protocol, IEEE/ACM Transactions on Networking, vol.8, No.3 (2000)
  6. ^ U. Manber, 대용량 파일 시스템에서 유사한 파일을 찾습니다.USENIX 윈터 테크니컬 컨퍼런스(1994년)
  7. ^ "Browser Fingerprinting Protection: How to Stay Private". RestorePrivacy. Retrieved 2022-01-13.
  8. ^ 랜덤 다항식에 의한 M.O. Rabin 지문 채취.컴퓨팅 테크놀로지 연구센터 보고서 TR-15-81(1981)
  9. ^ http://www.jucs.org/jucs_16_21/watermarking_techniques_for_relational/jucs_16_21_3164_3190_halder.pdf[베어 URL PDF]