▲

GN⁺: 자동화된 정수 해시 함수 탐색 기술

 (github.com/skeeto)
3P by neo 3달전 | favorite | 댓글 1개

Hash Function Prospector

이 도구는 자동화된 정수 해시 함수 탐색을 위한 작은 도구임. 9개의 가역 연산들 중에서 무작위로 선택하여 수십억 개의 정수 해시 함수들을 생성함. 생성된 함수들은 JIT 컴파일되고 Avalanche 동작이 평가됨. 현재 가장 좋은 함수가 C 문법으로 출력됨.

  • Avalanche 점수: 단일 입력 비트를 뒤집었을 때 평균적으로 고정된 상태로 유지되는 출력 비트 수. 점수가 낮을수록 좋음. 이상적으로는 점수가 0임. 즉, 단일 입력 비트를 뒤집으면 모든 출력 비트가 50% 확률로 뒤집힘.
  • Prospector는 32비트와 64비트 정수 해시 함수를 모두 생성할 수 있음. 전체 옵션은 사용법(-h)을 확인. JIT 컴파일러로 인해 x86-64만 지원되지만, 발견된 함수는 어디서나 사용 가능함.

발견된 해시 함수들

Prospector와 여기에 있는 다른 도우미 유틸리티들에 의해 발견된 두 가지 유용한 클래스의 해시 함수가 있음. 둘 다 xorshift-multiply-xorshift 구조를 사용하지만 라운드 수가 다름.

2라운드 함수

TheIronBorn이 이 구조에 대한 최고의 알려진 매개변수를 발견하기 위해 조합 최적화를 사용함.

  • 이 32비트 2라운드 순열은 특히 낮은 편향을 가지며 심지어 유명한 MurmurHash3 32비트 finalizer를 작은 차이로 이김.
  • 해시 함수 구조는 Prospector에 의해 발견되었고, 매개변수는 언덕 등반과 유전 알고리즘을 사용하여 튜닝됨.

더 많은 편향이 낮은 2라운드 상수들이 있으며, 그 중 일부는 lowbias32보다 더 좋음.

3라운드 함수

이 구조에서 multiply-xorshift를 한 라운드 더 추가하면 신중하게 선택한 매개변수로 이론적인 편향 한계에 도달할 수 있음. 예를 들어, 이 해시 함수는 완벽한 PRF와 구별할 수 없음.

  • triple32는 hash(0) = 0 이슈를 해결할 뿐만 아니라 편향을 더 낮춤.
  • 더 많은 편향이 낮은 3라운드 상수들이 있음.

정확한 편향 측정

-E 모드는 주어진 해시 함수(-p 또는 -l)의 편향을 평가함. 기본적으로 Prospector는 함수의 편향을 빠르게 평가하기 위해 추정치를 사용하지만, 비결정적이며 결과에 많은 노이즈가 있음. 정확한 편향을 소진적으로 측정하려면 -e 옵션을 사용함.

  • -p와 패턴을 사용하거나 hash()라는 함수가 포함된 공유 라이브러리와 -l을 사용하여 검사할 함수를 정의할 수 있음.
  • 64비트 해시 함수에 대한 정확하고 소진적인 테스트는 너무 오래 걸리기 때문에 없음.

가역 연산 선택

다음과 같은 가역 연산들을 사용:

  • x = ~x;
  • x ^= constant;
  • x *= constant | 1; (홀수 상수만)
  • x += constant;
  • x ^= x >> constant;
  • x ^= x << constant;
  • x += x << constant;
  • x -= x << constant;
  • x <<<= constant; (왼쪽 회전)
  • x = bswap(x) (높은 바이트와 낮은 바이트 교환)

기술적으로 x = ~x는 x ^= constant에 의해 커버됨. 그러나 ~x는 독특하게 특별하고 특히 유용함.

16비트 해시

16비트 해시에 대한 제약 조건이 다르기 때문에 이러한 해시를 생성하기 위한 별도의 도구인 hp16이 있음.

  • 32비트/64비트 Prospector와 달리 이 구현은 완전히 이식 가능하며 거의 모든 시스템에서 실행됨.
  • 128KiB S-box 생성 및 평가도 가능함.
  • 16비트 해시는 빠른 곱셈 명령이 없는 기계에서 더 필요할 가능성이 있으므로 탐색 중에 특정 연산을 생략할 수 있음(-m, -r).

몇 가지 흥미로운 결과들:

  • 2라운드 xorshift-multiply 해시
  • 3라운드 xorshift-multiply 해시
  • 곱셈이 없는 해시 (xorshift-add만 사용)

좋은 3라운드 xorshift 해시(hp16 -Xn3을 통한 짧은 검색)는 좋은 S-box(hp16 -S)에 근접함.

16비트 연산을 할 때는 C 정수 승격 규칙에 주의해야 함. 이 프로그램에서 출력하는 C 프로그램은 필요한 경우 16비트 연산을 "unsigned int"로 승격하는 데 주의를 기울임.

GN⁺의 의견

  • 해시 함수의 안전성은 암호학과 컴퓨터 보안에서 매우 중요한 역할을 하므로, 이런 탐색 도구는 연구에 큰 도움이 될 것 같음. 특히 무작위 탐색을 통해 편향이 낮은 해시 함수를 찾아내는 것이 흥미로움.

  • 그러나 단순히 통계적 특성만으로 해시 함수의 안전성이 보장되는 것은 아님. 암호학적 해시 함수는 PreImage Resistance, Second PreImage Resistance, Collision Resistance 등 다양한 공격에 대해 안전해야 하므로, 이에 대한 분석도 필요할 것 같음.

  • 16비트 해시 함수는 IoT나 임베디드 시스템 같은 제한된 환경에서 유용할 것 같음. 곱셈 명령이 없는 CPU에서도 사용할 수 있도록 ADD/XOR/SHIFT만 사용한 해시 함수를 만들 수 있다는 점이 인상적임.

  • 해시 함수 설계에 Hill Climbing이나 유전 알고리즘 같은 발견적 탐색 기법을 적용한 것도 신선한 아이디어임. 암호 알고리즘 설계에 AI 기술을 접목하려는 시도가 활발한데, 이런 최적화 기법들이 앞으로 더 중요한 역할을 할 것 같음.

  • 다만 Hash Function이 가진 한계로 인해 아무리 Avalanche 특성이 좋더라도 암호학적으로 안전하다고 말하긴 어려울 것 같고, 이는 이 프로젝트의 한계로 보임. 그래도 이런 도구를 통해 기존 해시 함수의 문제점을 분석하고 개선하는 데 도움이 될 수 있을 것임.

▲
neo 3달전  [-]
Hacker News 의견
  • 해당 개발자의 코드를 좋아하는 이유
    • JSON 라이브러리, 옵션 파싱 라이브러리, 분기 없는 UTF-8 디코더, lock-free 스택, trie 라이브러리 등이 마음에 듦
    • 위의 라이브러리들이 모두 Unlicense로 공개된 점이 마음에 듦
  • MurmurHash 개발자의 코멘트
    • multiply-shift-xor 연산이 오랫동안 잘 버텨온 것이 흥미로움을 표현
  • 자동 해시 함수 탐색에 대한 생각 공유
    • SMHasher3와 연동하여 출력을 자동으로 평가하는 것이 좋을 것 같음
      • 속도를 위해 일부 테스트만 사용하고 빠르게 실패할 수 있음
    • 64비트와 128비트 해시로 확장하는 것도 좋을 것 같음 (검색 공간이 더 크긴 함)
    • Rain 라이브러리에서 64비트 소수의 곱셈에 대한 눈사태 효과를 측정하는 NodeJS 코드를 만듦
  • 1brc 문제를 Go로 구현한 경험 공유
    • 각 역을 충돌 없이 자체 버킷에 넣는 커스텀 완전 해시 함수를 찾으려 했으나, 프로그램 시작 전에 데이터에 맞춰 해시 함수를 커스터마이징할 수 없다는 규칙 때문에 포기함
    • 무작위 상수를 확인하고 충돌하는 버킷 수와 충돌 수에 따라 지금까지 찾은 최상의 상수를 출력하는 테스트 도구를 만듦
      • 약 40%의 채우기 비율로 단 2개의 충돌 값만 있는 1개의 버킷으로 줄일 수 있었음
      • 다른 상수와 관계없이 이동할 위치 수에 대해 유사한 값이 최고 성능 상수에 포함되었다는 점이 흥미로웠음
  • 이 코드가 멋진 이유와 사용 용도에 대한 설명 요청
  • 정확히 무엇을 하는 코드인지, 최고의 해시 함수를 찾는 것인지, 그렇지 않다면 왜 매번 실행할 때마다 최고의 해시 함수가 바뀌는지에 대한 의문 제기
  • 특정 범위 내의 정수 값에 대해 좋은 해시 함수를 발견하는 메커니즘에 대한 정보 요청
    • 예를 들어 10,000에서 200,000 사이의 정수 값을 알고 있고, 이를 최적의 해시 버킷 수로 해싱하고 싶은 경우
  • 가역 연산으로 제한하면 수학적으로 좋은 점이 있지만 많은 것들이 배제된다는 의견
    • 입력 집합을 미리 알고 있는 완전 해싱에 대해 생각했음
    • 일반적으로 상수 배열을 사용하지만, 입력이 이미 작은 정수인 경우 더 압축할 수 있는지 알고 싶었음
    • 약 100개의 기본 연산 목록을 작성했지만 지루해져서 프로젝트를 진행하지 않았음
  • 두 곱셈에 동일한 상수를 사용하면 코드 크기가 줄어들어 계산 속도가 약간 빨라질 수 있다는 의견
  • 이 함수들이 암호화 연산에 적합하지 않다는 것을 인정하면서도, 측정된 "편향"이 암호 분석에 어떤 영향을 미치는지에 대한 질문
    • 차분 암호에 익숙한 사람이 설명해줄 수 있는지 궁금해함
    • 편향이 낮은 해시 함수가 더 적은 라운드 또는 계산으로 암호 분석을 무력화시킬 수 있는지 궁금해함
    • 이 도구가 더 나은 암호학적 해시 함수를 찾는 데 도움이 될 것인지 궁금해함
  • 비슷한 프로젝트 소개
    • 속도는 느리지만(인터프리터 사용) 함수의 품질이 더 좋음
    • 그러나 기존의 해시 함수보다 나은 것은 찾지 못했음
답변달기