시프해시

SipHash

SipHash는 2011년 말 "해시 홍수" 서비스 거부 공격(HashDoS)이 급증한 [1]: 165 [2]데 대응하여 2012년 장필리프 아우마손과 다니엘 J. 번스타인이 만든 유사 함수의 ARX(Addd-rotate-xor) 기반 제품군이다.[3]

SipHash는 보안을 확보하기 위해 해시함수로 사용하도록 설계되었지만, 메시지 인증 코드인 HMAC와 같은 키 해시함수로만 적합하다는 점에서 SHA와 같은 암호 해시함수와 근본적으로 다르다. 즉, SHA는 공격자가 SHA(X)를 계산해도 SHA(X) = SHA(Y)와 같은 두 개의 메시지 X와 Y를 찾기 어렵게 설계되어 있다. 대신 SipHash는 X와i SipHash(Xi, k)를 본 적이 있는 공격자는 이전에 보지 못한 메시지 Y ∉ {Xi}에 대해 키 k에 대한 정보나 SipHash(Y, k)를 찾을 수 없다고 보장한다.

개요

SipHash는 가변 길이 메시지와 128비트 비밀 키에서 64비트 메시지 인증 코드를 계산한다. 짧은 입력에도 효율적이도록 설계되었으며,[4]: 496 [2] CityHash와 같이 비암호화 해시함수에 버금가는 성능으로 해시 테이블에 대한 서비스 거부 공격("해시 플러딩")[5]을 방지하거나 네트워크 패킷을 인증하는 데 사용할 수 있다. 나중에 128비트 결과를 생성하는 변종이 추가되었다.[6]

SHA와 같은 키 없는 해시함수는 전체 출력을 사용하는 경우에만 충돌에 강하다. 실제 크기의 해시 테이블로 인덱스와 같은 작은 출력을 생성하는 데 사용되는 경우, 어떤 알고리즘도 충돌을 방지할 수 없다. 공격자는 가능한 한 많은 출력의 시도만 하면 된다.

예를 들어, 네트워크 서버가 한 번에 최대 100만 개의 요청을 처리할 수 있도록 설계되었다고 가정해 보십시오. 해시 함수를 사용하여 각 요청의 식별 정보를 200만 개의 가능한 테이블 항목 중 하나에 매핑하여 200만 개의 항목이 있는 해시 테이블에서 들어오는 요청을 추적한다. 해시함수를 알고 있는 공격자는 임의의 입력만을 공급하면 된다. 200만개 중 1개는 특정 해시값을 가질 것이다. 만약 공격자가 현재 동일한 해시 값을 갖도록 선택된 모든 수백 개의 요청을 서버에 보낸다면, 그것은 많은 수의 해시 충돌을 야기할 것이고, 수백만 개의 요청의 패킷 홍수와 유사한 효과로 서버를 느리게 할 것이다(또는 정지시킬 수 있다).[7]

공격자에게 알려지지 않은 키를 사용함으로써 SipHash와 같은 키 해시함수는 이러한 종류의 공격을 방지한다. 키 없는 해시함수에 키를 추가할 수도 있지만(HMAC는 인기 있는 기법이다) SipHash는 훨씬 효율적이다.

SipHash 계열의 함수는 SipHash-c-d로 지정되며, 여기서 c는 메시지 블록당 라운드 수, d는 최종 라운드 수입니다. 권장 매개변수는 최상의 성능을 위해 SipHash-2-4, 보수적 안보를 위해 SipHash-4-8이다. 몇몇 언어는 Siphash-1-3을 아직 알려지지 않은 DoS 공격의 위험을 무릅쓰고 성능을 위해 사용한다.

참조 구현은 CC0에 따라 공용 도메인 소프트웨어로 출시되었다.[6]

사용법

SipHash는 다양한 소프트웨어의 해시 테이블 구현에 사용된다.[8]

다음 프로그램은 다른 방법으로 SipHash를 사용한다.

구현

참고 항목

참조

  1. ^ Dobraunig, Christoph; Mendel, Florian; Schläffer, Martin (29 November 2014). Differential Cryptanalysis of SipHash. International Workshop on Selected Areas in Cryptography. Lecture Notes in Computer Science. Vol. 8781. pp. 165–182. doi:10.1007/978-3-319-13051-4_10. ISBN 978-3-319-13050-7. Retrieved 28 February 2018.
  2. ^ a b Jean-Philippe Aumasson & Daniel J. Bernstein (2012-09-18). "SipHash: a fast short-input PRF".
  3. ^ Lennon, Mike (2011-12-28). "Hash Table Vulnerability Enables Wide-Scale DDoS Attacks". SecurityWeek.
  4. ^ So, Won; Narayanan, Ashok; Oran, David; Stapp, Mark (2013). Named data networking on a router: forwarding at 20gbps and beyond. Proceedings of the ACM SIGCOMM 2013 Conference on SIGCOMM. p. 495. doi:10.1145/2486001.2491699. ISBN 9781450320566. S2CID 1457918. Retrieved 28 February 2018. The recently proposed SipHash [1] offers a good balance as it provides collision resistance and comparable performance to non-crypto hashes
  5. ^ Aumasson, Jean-Philippe; Bernstein, Daniel J.; Boßlet, Martin (2012-11-08). Hash-flooding DoS reloaded: attacks and defenses (PDF). Application Security Forum – Western Switzerland 2012.
  6. ^ a b "SipHash: a fast short-input PRF". 2016-08-01. Retrieved 2017-01-21. Intellectual property: We aren't aware of any patents or patent applications relevant to SipHash, and we aren't planning to apply for any. The reference code of SipHash is released under CC0 license, a public domain-like license.
  7. ^ Crosby, Scott A.; Wallach, Dan S. (2003-08-06). Denial of Service via Algorithmic Complexity Attacks. Usenix Security Symposium. Washington, D.C.
  8. ^ Aumasson, Jean-Philippe; Bernstein, Daniel J. (2016-08-01). "SipHash: a fast short-input PRF, Users". Retrieved 2017-01-21.
  9. ^ Vagg, Rod (2019-02-28). "build: enable v8's SipHash for hash seed creation". Node.js. Retrieved 2021-10-21 – via GitHub.
  10. ^ "Perl security – Algorithmic Complexity Attacks". Perldoc Browser. 2016-05-16. Retrieved 2021-10-21.
  11. ^ Heimes, Christian (2013-09-27). "PEP 456 – Secure and interchangeable hash algorithm". Retrieved 2017-01-21.
  12. ^ McVey, Samantha (2018-07-16). "Implement SipHash, use as our hashing function w/ 64bit hashvals". MoarVM. Retrieved 2018-07-16 – via GitHub.
  13. ^ Hoare, Graydon (2012-07-24). "Add core::hash containing SipHash-2-4 implementation. Re: #1616 and #859". Rust. Retrieved 2017-01-21 – via GitHub.
  14. ^ Poettering, Lennart (2013-12-22). "shared: switch our hash table implementation over to SipHash". systemd. Retrieved 2017-01-21 – via freedesktop.org.
  15. ^ Guo, Yang (2019-01-09). "Optionally use halfsiphash for integer hashing". V8. Retrieved 2021-10-21.
  16. ^ "Compact Block Relay". GitHub. Retrieved 2018-09-27.
  17. ^ bslh_siphashalgorithm.h

외부 링크