해시 알고리즘

#

개요

본 포스트에서는 응용적 관점에서 해시 알고리즘에 대해 간단하게 정리해본다.

해시 알고리즘은 알고리즘과 자료구조 전반에 있어서 가장 기본이 되는 구성요소 중 하나다.

해시의 기본적인 원리는 그리 어렵지만은 않다.
키를 해시함수에 던지면, 함수는 일련의 해시값을 반환한다.

해시함수의 특징은 2가지가 있다.

  1. 같은 키를 넣었을 때의 반환값이 항상 같아야 한다.
  2. 다른 키를 넣었을 때의 반환값이 같을 수도 있다.



응용

해시함수의 사용처를 크게 정리해보면, 대략 2가지가 있다.

  1. 해시테이블등 자료구조에서의 빠른 해시-인덱싱을 구현하는 용도.
  2. 비밀번호 등을 단방향 암호화하는 용도.

용도에 따라서 요구되는 해시함수의 사양이나 성능이 많이 달라진다.

예를 들면

  1. 자료구조에 사용되는 해시 알고리즘은 성능도 빨라야 하며, 해시 충돌(Collision)이 적어야 한다.
  2. 비밀번호에 사용되는 해시 알고리즘은 성능이 너무 빨라서도, 너무 느려서도 안되며, 역방향의 분석이 어려워야한다. 그리고 이것도 해시 충돌이 적어야 한다.



MD5 (1991)

Message-Digest algorithm 5의 준말로, 오래된 레거시 해시 알고리즘 중 하나다.
128비트 크기의 해시를 생성하며, 비밀번호 해싱에 주로 사용했다.

근데 암호화용으로는 성능이 너무 빠르다는게 단점이고, 여러가지 취약점이 너무 많아서 현재는 사용을 권장하지 않는다.




SHA 시리즈 (1993~)

Secure Hash Algorithm.
미국 NSA가 제작하고 미국 국립표준기술연구소(NIST)에서 표준으로 채택한 해시 알고리즘이다.

시리즈가 많다.

SHA-1 (1993)
160비트 값을 반환. 충돌문제가 너무 심하고 취약점이 많아서 거의 사용중단된 상태다.

SHA-2 (2001)
현재 가장 많이 사용되는 해시 알고리즘이다.
224, 256, 384, 512비트 사이즈를 선택할 수 있고, SHA224, SHA256, SHA384, SHA512 등으로 불린다.
최적화가 잘먹혀서 성능이 좀 빠르다는게 단점이다.

SHA-3 (2012)
Keccak256이라는 알고리즘을 기반으로 표준으로 채택되었다. 아직 그리 널리 쓰이지는 않는다.



bcrypt (1999)

비밀번호 암호화용 해시 알고리즘이다.
크기는 184비트.

성능이 적당히 느리고, 브루트포스 등에도 대응이 어느정도 된다.

OpenBSD에서 쓰고있고, 일반적으로도 꽤 많이 쓰이는 편이다.

하지만 현재는 이것도 레거시 취급이다.




Scrypt (2009)

비밀번호 암호화용 해시 알고리즘이다.

Bcrypt와 비교해서 조금 더 보안적으로 강력하다고 할 수 있다.
CPU, 메모리 리소스를 꽤 많이 잡아먹는 편이다.

2023년부터 OWASP에서는 암호화 해시 알고리즘 중에서 scrypy를 2순위로 고려할 것을 권장한다.




pbkdf2

비밀번호 암호화용 해시 알고리즘이다.

NIST에서 표준으로 지정한 알고리즘이고, ISO-27001 보안 규정이나 FIPS-140 같은걸 준수해야한다면 이걸 써야한다.

표준이라고 해서 bcrypt보다 훨씬 안전하다거나 하는 것은 아니다. 그냥 최소기준일 뿐이다.




argon2id (2015)

현재 가장 인기가 많고 권장되는 암호화용 해시 알고리즘이다.

2023년부터 OWASP에서는 암호화 해시 알고리즘 중에서 argon2id를 최우선순위로 고려할 것을 권장한다.




Fowler–Noll–Vo hash function (1991)

해시테이블 구현용 해시 알고리즘이다.

SipHash가 나오기 전에 상당히 많이 사용되던 알고리즘이다.

C++의 해시알고리즘은 아직 이게 디폴트인게 꽤 많은거같다.




MurmurHash3 (2008)

해시테이블 구현용 해시 알고리즘이다.

GCC C++의 기본해시로 들어가있고, 이외에도 많은 오픈소스들이 사용했고, 사용하고 있다.




SipHash (2011)

해시테이블 구현용 해시 알고리즘이다.
64비트 크기의 해시를 반환한다.

기본적으로 Hash-Dos 문제를 막기 위한 목적에서 설계됐다.
보안적으로는 안전하나, 평균적인 성능은 조금 떨어지는게 단점이다.

꽤 많은 수의 해시테이블 구현체들이 이 알고리즘을 기반으로 작성된다.




wyhash

해시테이블 구현용 해시 알고리즘이다

hashdos 방어가 완벽히 되지는 않지만 가볍고 빠르면서 충돌 저항성도 괜찮아서 많이 쓰이는 편이다.

현대적인 많은 구현에서 siphash의 보안수준이 필요하지 않다면 이걸 쓴다.