해시 충돌

Hash collision
John Smith와 Sandra Dee는 동일한 해시 값 02를 공유하여 해시 충돌을 일으킵니다.

컴퓨터 과학에서 해시 충돌 또는[citation needed] 충돌은 해시 테이블의 두 데이터가 동일한 해시 값을 공유하는 경우입니다.이 경우 해시 값은 데이터 입력을 받아 고정 길이의 [1]비트를 반환하는 해시 함수에서 파생됩니다.

해시 알고리즘은 충돌 방지 목적으로 작성되었지만 (피죤홀 원리에 따라) 동일한 해시에 다른 데이터를 매핑할 수 있습니다.악의적인 사용자는 이를 이용하여 데이터를 [2]모방, 액세스 또는 변경할 수 있습니다.

데이터 관리 및 컴퓨터 보안(특히 암호화 해시 함수)에서 해시 충돌의 부정적인 적용 가능성이 있기 때문에 충돌 회피는 컴퓨터 보안에서 중요한 주제가 되었습니다.

배경

해시 충돌은 집합 내의 개체 수와 매핑된 비트 문자열의 길이가 충분한지 여부에 따라 불가피할 수 있습니다.n개의 오브젝트 세트가 있는 경우 n이 R(이 경우 R이 해시 값 범위)보다 클 경우 해시 콜리전이 발생할 확률은 1이 됩니다.이는 해시 콜리전이 [3]발생할 가능성이 있음을 의미합니다.

해시 충돌이 어느 시점에 일어날 수 있는 또 다른 이유는 수학의 생일 역설에 대한 생각에서 비롯되었습니다.이 문제에서는 n명의 [4]사람 중 랜덤으로 선택된 두 사람이 같은 생일을 가질 확률을 살펴봅니다.이러한 생각은 이른바 생일 공격이라고 불리는 것으로 이어졌다.이 공격의 전제는 자신의 생일이나 특정 생일과 정확히 일치하는 생일을 찾는 것이 어렵지만, 생일이 일치하는 두 사람의 세트를 찾을 확률은 매우 높아진다.불량 행위자는 이 방법을 사용하여 특정 [5]값을 검색하는 대신 다른 해시 값과 충돌하는 해시 값을 쉽게 찾을 수 있습니다.

충돌의 영향은 응용 프로그램에 따라 달라집니다.해시함수와 핑거프린트가 상동 DNA 시퀀스나 유사한 오디오 파일과 같은 유사한 데이터를 식별하기 위해 사용되는 경우, 함수는 국소적으로 민감한 [6]해싱과 같은 기술을 사용하여 구별되지만 유사한 데이터 간의 충돌 가능성을 최대화하도록 설계됩니다.반면 체크섬은 매우 다른 [7]입력 간의 충돌을 고려하지 않고 유사한 입력 간의 충돌 가능성을 최소화하도록 설계되었다.불량 행위자가 해시 충돌을 만들거나 찾으려는 경우를 충돌 [8]공격이라고 합니다.

실제로 보안 관련 애플리케이션에서는 암호 해시 알고리즘을 사용합니다.암호 해시 알고리즘은 랜덤 일치가 거의 발생하지 않도록 설계되어 있어 어디에서나 사용할 수 있고 충돌을 [7]발견하기가 매우 어려울 정도로 안전합니다.

발생 확률

해시 충돌은 우연히 발생할 수 있으며 많은 해시 알고리즘에 대해 의도적으로 생성될 수 있습니다.따라서 해시 충돌의 확률은 알고리즘의 크기, 해시 값의 분포, 특정 충돌을 생성하는 것이 수학적으로 알려져 있고 계산적으로 가능한지 여부에 따라 달라집니다.

CRC-32, MD5 및 SHA-1의 해시 알고리즘을 고려합니다.이것들은 다양한 수준의 충돌 [9]위험을 가진 일반적인 해시 알고리즘입니다.

CRC-32

CRC-32는 해시 충돌 위험이 가장 높습니다.이 해시 함수는 일반적으로 사용하지 않는 것이 좋습니다.허브에 77,163개의 해시 값이 포함되어 있는 경우 해시 충돌이 발생할 확률은 50%로 다른 [10]방식에 비해 매우 높습니다.

MD5

MD5는 가장 일반적으로 사용되고 있으며 다른 2개의 해시 함수와 비교하면 해시 충돌 위험 측면에서 중간 수준을 나타냅니다.해시 충돌이 발생할 확률이 50%가 되려면 허브에[10] 50억 6천만 개 이상의 레코드가 있어야 합니다.

SHA-1

SHA-1은 해시 충돌 위험이 가장 낮습니다.SHA-1 함수가 해시 충돌이 발생할 확률이 50%가 되려면 허브에 1.42 × 10개의24 레코드가 있어야 합니다.이러한 예에 기재되어 있는 레코드의 수는,[10] 같은 허브에 있을 필요가 있습니다.

더 적은 수의 레코드를 가진 허브를 보유하면 이러한 모든 해시함수에서 해시 충돌 가능성이 낮아질 수 있습니다.단, 충돌 해결 기술을 사용하지 않는 한 반드시 경미한 위험이 존재합니다.

충돌 해결

주요 기사:해시 테이블 collision 충돌 해결

해시 충돌은 불가피하므로 해시 테이블에는 충돌 해결이라고 하는 처리 메커니즘이 있습니다.가장 일반적인 두 가지 전략은 오픈 어드레싱과 분리 체인입니다.캐시 인식 충돌 해결은 문자열 해시 테이블에 대해 과거에 논의된 또 다른 전략입니다.

존 스미스와 샌드라 디는 둘 다 같은 감방으로 보내지고 있다.오픈 어드레싱에서는 해시 테이블이 Sandra Dee를 다른 셀로 리다이렉트 합니다.

오픈 어드레싱

주요 기사:오픈 어드레싱

해시 테이블 내의 셀에는 이 메서드의 3가지 상태(사용 중, 비어 있음, 삭제됨) 중 하나가 할당됩니다.해시 충돌이 발생하면 테이블이 검사되어 레코드를 비어 있는 대체 셀로 이동합니다.해시 충돌이 발생하여 이 메서드가 구현될 때 실행되는 다양한 유형의 프로빙이 있습니다.프로브 유형에는 선형 프로브, 이중 해시 및 2차 [11]프로빙이 있습니다.오픈 [12]어드레싱은 클로즈드해시라고도 합니다.

개별 체인

상세 정보:해시 테이블 separate 개별 체인

이 전략에서는 해시 테이블의 셀에 여러 레코드를 '체인'할 수 있습니다.2개의 레코드가 같은 셀로 전송되면 둘 다 링크 리스트로 그 셀에 들어갑니다.이렇게 하면 해시 값이 같은 레코드가 같은 셀에 들어갈 수 있기 때문에 해시 충돌을 효율적으로 방지할 수 있지만 단점이 있습니다.이렇게 많은 목록을 추적하는 것은 어렵기 때문에 어떤 도구를 사용하든 매우 [11]느려질 수 있습니다.개별 체인은 개방형 [13]해싱이라고도 합니다.

캐시 인식 충돌 해결

Askitis & Zobel(2005)은 이전 두 가지 방법보다 훨씬 덜 사용되었지만 2005년에 [14]캐시 인식 충돌 해결 방법을 제안했습니다.이것은 개별 체인 방식과 비슷하지만 기술적으로 체인 리스트는 관여하지 않습니다.이 경우 연결된 목록 대신 해시 값이 연속된 항목 목록으로 표시됩니다.이 방법은 문자열 해시 테이블에 더 적합하며 숫자 값의 용도는 [11]아직 알려지지 않았습니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Stapko, Timothy (2008), "Embedded Security", Practical Embedded Security, Elsevier, pp. 83–114, doi:10.1016/b978-075068215-2.50006-9, ISBN 9780750682152, retrieved 2021-12-08
  2. ^ Schneier, Bruce. "Cryptanalysis of MD5 and SHA: Time for a New Standard". Computerworld. Archived from the original on 2016-03-16. Retrieved 2016-04-20. Much more than encryption algorithms, one-way hash functions are the workhorses of modern cryptography.
  3. ^ Cybersecurity and Applied Mathematics. 2016. doi:10.1016/c2015-0-01807-x. ISBN 9780128044520.
  4. ^ Soltanian, Mohammad Reza Khalifeh (10 November 2015). Theoretical and Experimental Methods for Defending Against DDoS Attacks. ISBN 978-0-12-805399-7. OCLC 1162249290.
  5. ^ Conrad, Eric; Misenar, Seth; Feldman, Joshua (2016), "Domain 3: Security Engineering (Engineering and Management of Security)", CISSP Study Guide, Elsevier, pp. 103–217, doi:10.1016/b978-0-12-802437-9.00004-7, ISBN 9780128024379, retrieved 2021-12-08
  6. ^ Rajaraman, A.; Ullman, J. (2010). "Mining of Massive Datasets, Ch. 3".
  7. ^ a b Al-Kuwari, Saif; Davenport, James H.; Bradford, Russell J. (2011). Cryptographic Hash Functions: Recent Design Trends and Security Notions. Inscrypt '10.
  8. ^ Schema, Mike (2012). Hacking Web Apps.
  9. ^ Altheide, Cory; Carvey, Harlan (2011). "Digital Forensics with Open Source Tools". Digital Forensics with Open Source Tools. Elsevier. pp. 1–8. doi:10.1016/b978-1-59749-586-8.00001-7. ISBN 9781597495868. Retrieved 2021-12-08.
  10. ^ a b c Linstedt, Daniel; Olschimke, Michael (2016). "Scalable Data Warehouse Architecture". Building a Scalable Data Warehouse with Data Vault 2.0. Elsevier. pp. 17–32. doi:10.1016/b978-0-12-802510-9.00002-7. ISBN 9780128025109. Retrieved 2021-12-07.
  11. ^ a b c Nimbe, Peter; Ofori Frimpong, Samuel; Opoku, Michael (2014-08-20). "An Efficient Strategy for Collision Resolution in Hash Tables". International Journal of Computer Applications. 99 (10): 35–41. Bibcode:2014IJCA...99j..35N. doi:10.5120/17411-7990. ISSN 0975-8887.
  12. ^ Kline, Robert. "Closed Hashing". CSC241 Data Structures and Algorithms. West Chester University. Retrieved 2022-04-06.
  13. ^ "Open hashing or separate chaining". Log22.
  14. ^ Askitis, Nikolas; Zobel, Justin (2005). Consens, M.; Navarro, G. (eds.). Cache-Conscious Collision Resolution in String Hash Tables. International Symposium on String Processing and Information Retrieval. String Processing and Information Retrieval SPIRE 2005. Lecture Notes in Computer Science. Vol. 3772. Berlin, Heidelberg: Springer Berlin Heidelberg. pp. 91–102. doi:10.1007/11575832_11. ISBN 978-3-540-29740-6.