Hashable
지난 포스팅에서 다뤘던 Hashable은 프로토콜 중 하나로,
Hasher에 해시되어 정수 해시 값을 생성할 수 있는 타입을 정의합니다.
(Hashable에 대한 더 자세한 내용은 여기에서 확인해주세요.)
오늘 포스팅은 Hasher가 어떤 해시 알고리즘을 사용하는지에 대한 내용입니다.
궁금해서 찾아봤는데 생각보다 흥미로워서 공유하기 위해 포스팅 작성합니다.
사설이 긴 편이니 바쁘신 분은 SipHash 문단부터 읽어주세요.
기존 방법
Swift 4.1부터 Equatable과 Hashable 프로토콜에 대한 적합성을 자동으로 합성해주기 시작했고,
지금의 Hasher를 이용한 해시 방법은 Swift 4.2부터 탄생했습니다.
이전에는 개발자가 직접 hash 함수를 만들어줬어야 했습니다.
찾아보니 이것도 국룰이 있더라고요.
바로 XOR 연산을 이용하는 방법입니다.
예를 들어 Color 타입이 있다고 할 때 R, G, B를 8비트 값으로 표현한다고 합시다.
struct Color {
let red: UInt8
let green: UInt8
let blue: UInt8
}
Hashable을 준수하기 위해서는 Equatable도 준수해야 하기 때문에
== 연산자도 구현해야 합니다.
extension Color: Equatable {
static func ==(lhs: Color, rhs: Color) -> Bool {
return lhs.red == rhs.red &&
lhs.green == rhs.green &&
lhs.blue == rhs.blue
}
}그리고 위에서 말한 뒤에 hash 값을 직접 설정해야 합니다.
extension Color: Hashable {
var hashValue: Int {
return self.red.hashValue ^
self.green.hashValue ^
self.blue.hashValue
}
}과거에는 이렇게 XOR를 적용하는게 국룰이었다고 합니다.
하지만 이 방법은 해시 충돌 비율이 높다는 문제가 있었습니다.
왜냐하면 순서에 상관 없이 결과가 동일하기 때문입니다.
let cyan = Color(red: 0x00, green: 0xFF, blue: 0xFF)
let yellow = Color(red: 0xFF, green: 0xFF, blue: 0x00)
cyan.hashValue == yellow.hashValue // true, collision위 두 개의 색은 아예 다른 색입니다.
왼쪽이 cyan, 오른쪽이 yellow 인데요. 아주 다르죠?
하지만 위의 해시 함수는 순서에 상관 없이 세 개의 색을 XOR로 합치기 때문에
같다고 판단되고 해시 충돌이 발생합니다.
해시 충돌
해시 충돌을 해결하는 방법에는 대표적으로 두 가지가 있습니다.
- 충돌하지 않는 해시 값이 있을 때까지 탐색한다.
- 링크드 리스트를 이용해 충돌값 뒤에 연결한다.
이때, 2번의 경우가 문제인데요.
해시 충돌을 악용하여 DDOS 공격이 발생할 수 있기 때문입니다.
아래는 이상적인 해시 테이블입니다.
모든 input이 각각 다른 output을 갖습니다.
해시 충돌이 전혀 없는 경우죠.
그럼 해시 충돌이 발생한 경우를 볼까요?
input 0에 대해 output이 겹친다고 생각해봅시다.
그러면,
이렇게 링크드 리스트가 생깁니다.
DDOS는 무수한 클라이언트를 이용해서 특정 사이트에 접속을 시도하거나 네트워크를 지나치게 사용하여
서비스를 하지 못하게 하는 공격입니다.
위 Hash는 input 0에 대해 항상 일정한 output이 발생하죠.
그렇다면 무수히 많은 0이 들어온다면 ...?
링크드 리스트가 무수히 많이 연결되겠죠??
결국에는 input 0에 대해서는 탐색에 무수히 많은 시간이 소요될 것입니다.
링크드 리스트가 아닌 1번 방법이었다면
테이블이 무수히 길어지거나 아예 값을 넣지 못했겠죠.
SipHash
이 문제를 해결하기 위한 방법으로 SipHash가 탄생했습니다.
SipHash는 오늘의 주제였던 "Hashable은 어떤 해시 알고리즘을 쓸까?"의 주인공이자
Redis에서도 사용 중인 해시 함수입니다.
SipHash를 알아보기 전에 먼저
위에서 알아본 문제는 어떤 이유로 발생한 것일까요?
바로 "모든" 클라이언트에 대해 input 0의 output이 동일하기 때문입니다.
SipHash는 Seed를 사용하여 클라이언트마다 output이 달라지도록 했습니다.
A 클라이언트의 input 0의 output과 B 클라이언트의 input 0의 output이 다른 곳이죠.
따라서 위 그림처럼 무수히 연결된 링크드 리스트가 생성되는 것을 방지합니다.
해시를 할 때 input에 더해서 seed라는 것을 입력받아 hash 값을 생성하는데
프로세스가 시작될 때 seed를 랜덤으로 생성하여 각 프로세스가 다른 해시 값을 가지도록 했습니다.
물론 같은 프로세스 내에서는 같은 해시 값을 같습니다.
Swift 살펴보기
공개된 Swift 코드에서도 Seed에 대한 코드를 볼 수 있었습니다.
먼저 Hasher 입니다.
자세한 내용은 모르겠지만!
State 구조체는 생성될 때 Seed 값을 매개변수로 받는다는 것을 알 수 있죠.
다른 init에서도
seed를 이용해 무언가를 진행 중이라는 것을 볼 수 있습니다.
아쉽게도 Hasher의 combine 메서드는 코드를 살펴볼 수 없었습니다.
공부하는 입장에서는 안타깝지만 보안에 관련된 내용이다 보니 그럴 수 있구나 했습니다 ㅎ..
combine()에 대해서는 얘가 알아서 해시값을 만들어주는구나로 받아들이면 될 듯 하네요!
마무리
글을 쓰다보니 SipHash에 대한 내용보다
SipHash가 사용된 이유가 더 길었는데요 ㅎ;;;
아무래도 Seed가 쓰이는 원인에 대한 설명을
피할 수도 없고 이게 핵심?이라고도 할 수 있기 때문에 설명이 길어진 것 같네요..
Swift가 사용 중인 SipHash과
Seed에 대해 알게 된 계기가 되었습니다.
틀린 내용은 댓글로 알려주시면 감사하겠습니다!
감사합니다.
참고
https://nshipster.co.kr/hashable/
https://github.com/apple/swift/blob/main/stdlib/public/core/SipHash.swift
https://en.wikipedia.org/wiki/SipHash
https://charsyam.wordpress.com/2018/02/04/입-개발-siphash의-사용-data-ddos를-방지해볼까/
아직은 초보 개발자입니다.
더 효율적인 코드 훈수 환영합니다!
공감과 댓글 부탁드립니다.