Following system colour scheme Selected dark colour scheme Selected light colour scheme

Python 개선 제안 한국어 번역

PEP 456 – 안전하고 교체 가능한 해시 알고리즘

Author:
Christian Heimes <christian at python.org>
BDFL-Delegate:
Alyssa Coghlan
Status:
Final
Type:
Standards Track
Created:
27-Sep-2013
Python-Version:
3.4
Post-History:
06-Oct-2013, 14-Nov-2013, 20-Nov-2013
Resolution:
Python-Dev message
Table of Contents

번역·라이선스 안내

이 비공식 한국어 번역은 원문 Copyright 절의 Public Domain 조건에 따라 제공합니다. 원저자와 공식 원문은 그대로 표시합니다. 수정되지 않은 기준 원문 · 공식 최신판

초록

이 PEP는 해시 무작위화 문제를 제대로, 그리고 완전히 해결하기 위해 SipHash를 문자열과 바이트열의 기본 해시 알고리즘으로 제안합니다. 또한 해시 코드를 통합하고 쉽게 교체할 수 있도록 Python의 C 코드를 수정할 것을 제안합니다.

근거

지난번 시도 [issue13703]에도 불구하고 CPython은 여전히 해시 충돌 DoS 공격 [29c3] [issue14621]에 취약합니다. 현재의 해시 알고리즘과 그 무작위화는 공격에 대한 내성이 없습니다. 적절한 암호학적 해시 함수만이 비밀 무작위화 키의 추출을 막을 수 있습니다. Python 기반 서비스에 대한 실제 공격은 아직 발견되지 않았지만, 이 약점은 반드시 수정되어야 합니다. Jean-Philippe Aumasson과 Daniel J. Bernstein은 현재 구현의 시드를 복구하는 방법을 이미 보였습니다 [poc].

게다가 현재의 해시 알고리즘은 하드 코딩되어 있으며, 바이트열과 세 가지 유니코드 표현인 UCS1, UCS2, UCS4에 대해 여러 번 중복 구현되어 있습니다. 이 때문에 임베딩하는 쪽에서는 인터프리터의 상당 부분을 패치하고 다시 컴파일하지 않고서는 이를 다른 구현으로 교체할 수 없습니다. 임베딩하는 쪽에서는 더 적합한 해시 함수를 선택하고 싶을 수 있습니다.

마지막으로, 현재 구현 코드는 성능이 좋지 않습니다. 일반적인 경우 한 사이클에 한두 바이트만 처리합니다. 최신 64비트 프로세서에서는 한 번에 8바이트를 처리하도록 코드를 쉽게 조정할 수 있습니다.

이 PEP는 문자열과 바이트열의 해시 코드에 대해 세 가지 주요 변경을 제안합니다.

  • SipHash [sip]가 기본 해시 알고리즘으로 도입됩니다. 암호학적 특성을 갖추고 있음에도 빠르고 작습니다. 잘 알려진 보안 및 암호 전문가들이 설계했으므로, 가까운 미래까지는 안전하다고 가정해도 무방합니다.
  • 64비트 데이터 타입이 없는 플랫폼을 위해 기존 FNV 코드는 유지됩니다. 이 알고리즘은 사이클당 더 큰 단위를 처리하도록 최적화됩니다.
  • 문자열과 바이트열의 해시 계산은 Objects/object.c와 Objects/unicodeobject.c에 있는 여러 개의 특수화된 구현 대신 하나의 API 함수로 옮겨집니다. 이 함수는 void 포인터와 길이를 받아 해당 데이터의 해시를 반환합니다.
  • 알고리즘은 컴파일 시점에 선택할 수 있습니다. FNV는 모든 플랫폼에 존재함이 보장됩니다. SipHash는 대부분의 최신 시스템에서 사용할 수 있습니다.

해시 함수에 대한 요구 사항

  • 1바이트부터 최대 ssize_t 값까지 임의로 큰 메모리 블록을 반드시 해시할 수 있어야 합니다.
  • 32비트 플랫폼에서는 최소 32비트, 64비트 플랫폼에서는 최소 64비트를 반드시 생성해야 합니다. (참고: 더 큰 출력은 예컨대 v ^ (v >> 32)로 압축할 수 있습니다.)
  • hash(memoryview)를 지원하기 위해 정렬되지 않은 메모리의 해시 계산을 반드시 지원해야 합니다.
  • 입력 길이가 결과에 영향을 주어 hash(b'\00') != hash(b'\x00\x00')가 성립하도록 할 것을 강력히 권장(RECOMMENDED)합니다.

해시 함수와 tp_hash 슬롯 사이의 내부 인터페이스 코드는 길이가 0인 입력과 반환값 -1에 대한 특수한 경우를 구현합니다. 길이가 0인 입력은 해시값 0으로 매핑됩니다. 출력 -1은 -2로 매핑됩니다.

수정된 FNV를 사용하는 현재 구현

CPython은 현재 Fowler-Noll-Vo 해시 함수 [fnv]의 변형을 사용합니다. 이 변형은 흔한 문자열에서 생기는 해시 충돌의 양과 비용을 줄이도록 수정되었습니다. 문자열의 첫 번째 문자는 두 번 더해지며, 첫 번째에는 7비트 시프트하여 더해집니다. 입력 문자열의 길이는 최종 값에 XOR 연산됩니다. 원래 FNV 알고리즘과 다른 이 두 가지 변경은 모두 짧은 문자열에서 생기는 해시 충돌의 양을 줄입니다.

최근 [issue13703]에서 해시값을 무작위화하려는 시도로 무작위 접두사와 접미사가 추가되었습니다. 해시 비밀값을 보호하기 위해 이 코드는 길이가 0인 입력에 대해 여전히 0을 반환합니다.

C 코드:

Py_uhash_t x;
Py_ssize_t len;
/* p is either 1, 2 or 4 byte type */
unsigned char *p;
Py_UCS2 *p;
Py_UCS4 *p;

if (len == 0)
    return 0;
x = (Py_uhash_t) _Py_HashSecret.prefix;
x ^= (Py_uhash_t) *p << 7;
for (i = 0; i < len; i++)
    x = (1000003 * x) ^ (Py_uhash_t) *p++;
x ^= (Py_uhash_t) len;
x ^= (Py_uhash_t) _Py_HashSecret.suffix;
return x;

이를 Python으로 대략 옮기면 다음과 같습니다.:

def fnv(p):
    if len(p) == 0:
        return 0

    # bit mask, 2**32-1 or 2**64-1
    mask = 2 * sys.maxsize + 1

    x = hashsecret.prefix
    x = (x ^ (ord(p[0]) << 7)) & mask
    for c in p:
        x = ((1000003 * x) ^ ord(c)) & mask
    x = (x ^ len(p)) & mask
    x = (x ^ hashsecret.suffix) & mask

    if x == -1:
        x = -2

    return x

FNV는 암호학적 특성이 없는 단순한 곱셈 및 XOR 알고리즘입니다. 무작위화는 초기 해시 코드에는 없었으나, oCERT-2011-003 [ocert]에서 설명된 해시 충돌 공격에 대한 대응책으로 추가되었습니다. FNV는 암호학적 해시 알고리즘이 아니며 dict 구현은 부채널 분석에 대비하여 강화되어 있지 않으므로, 원격 공격자가 무작위화 비밀값을 계산해 낼 수 있습니다. 이 PEP의 작성자는 비암호학적 해시 함수의 본질상 비밀값을 숨기는 것이 불가능하다고 강하게 확신합니다.

검토한 해싱 알고리즘

이 PEP의 작성자는 현대적이고 빠르며 최신 기술로 여겨지는 여러 해싱 알고리즘을 조사했습니다.

SipHash

SipHash [sip]는 128비트 시드와 64비트 출력을 갖는 암호학적 의사 난수 함수입니다. 이 함수는 Jean-Philippe Aumasson과 Daniel J. Bernstein이 빠르고 안전한 키 기반 해시 알고리즘으로 설계했습니다. Ruby, Perl, OpenDNS, Rust, Redis, FreeBSD 등에서 사용됩니다. C 참조 구현은 CC0 라이선스(퍼블릭 도메인)로 공개되었습니다.

SipHash 사이트에서 인용합니다:

SipHash는 짧은 메시지에서의 속도에 최적화된 의사 난수 함수(키 기반 해시 함수라고도 함)의 계열입니다. 대상 응용 분야로는 네트워크 트래픽 인증과 해시 플러딩 DoS 공격에 대한 방어가 있습니다.

siphash24는 성능이 가장 뛰어난 권장 변형입니다. 메시지 블록당 2라운드, 종료 처리 라운드 4번을 사용합니다. 참조 구현 외에도 여러 다른 구현을 사용할 수 있습니다. 일부는 한 번의 호출로 끝나는 단일 함수이고, 다른 일부는 init, update, finalize 함수를 사용하는 Merkle–Damgård 구성과 유사한 방식을 사용합니다. Marek Majkowski의 C 구현인 csiphash [csiphash]가 함수의 프로토타입을 정의합니다. (참고: k는 두 개의 uint64_t로 나뉩니다):

uint64_t siphash24(const void *src, unsigned long src_sz, const char k[16])

SipHash는 64비트 데이터 타입이 필요하므로 순수 C89 플랫폼과 호환되지 않습니다.

MurmurHash

MurmurHash [murmur]는 Austin Appleby가 개발한 비암호학적 키 기반 해시 함수 계열입니다. Murmur3는 MurmurHash의 최신 고속 변형입니다. C++ 참조 구현은 퍼블릭 도메인으로 공개되었습니다. 32비트 시드를 사용하며 32비트 또는 128비트 출력을 제공합니다. (참고: out 매개변수는 1바이트 또는 4바이트 크기의 버퍼입니다.)

Murmur3의 함수 프로토타입은 다음과 같습니다:

void MurmurHash3_x86_32(const void *key, int len, uint32_t seed, void *out)

void MurmurHash3_x86_128(const void *key, int len, uint32_t seed, void *out)

void MurmurHash3_x64_128(const void *key, int len, uint32_t seed, void *out)

128비트 변형은 64비트 데이터 타입이 필요하므로 순수 C89 플랫폼과 호환되지 않습니다. 32비트 변형은 C89와 완전히 호환됩니다.

Aumasson, Bernstein, Boßlet은 Murmur3가 해시 충돌 공격에 견디지 못한다는 것을 보였습니다 [sip] [ocert-2012-001]. 따라서 Murmur3는 더 이상 안전한 알고리즘으로 간주할 수 없습니다. 해시 충돌 공격을 걱정할 필요가 없다면 여전히 대안이 될 수 있습니다.

CityHash

CityHash [city]는 Geoff Pike와 Jyrki Alakuijala가 Google을 위해 개발한 비암호학적 해시 함수 계열입니다. C++ 참조 구현은 MIT 라이선스로 공개되었습니다. 이 알고리즘은 부분적으로 MurmurHash를 기반으로 하며, 더 빠르다고 주장합니다. 128비트 시드를 사용하는 64비트 및 128비트 출력과 함께, 시드 없는 32비트 출력도 지원합니다.

128비트 시드를 사용하는 64비트 CityHash의 해당 함수 프로토타입은 다음과 같습니다:

uint64 CityHash64WithSeeds(const char *buf, size_t len, uint64 seed0,
                           uint64 seed1)

CityHash는 긴 입력을 위해 CRC32 인트린식을 활용하는 SSE 4.2 최적화도 제공합니다. CityHash32를 제외한 모든 변형은 64비트 데이터 타입이 필요합니다. CityHash32는 32비트 데이터 타입만 사용하지만 시드를 지원하지 않습니다.

MurmurHash와 마찬가지로, Aumasson, Bernstein, Boßlet은 CityHash에도 비슷한 약점이 있음을 보였습니다 [sip].

DJBX33A

DJBX33A는 Daniel J. Bernstein이 만든 매우 간단한 곱셈 및 덧셈 알고리즘입니다. 빠르고 초기 설정 비용이 낮지만 해시 충돌 공격에는 안전하지 않습니다. 이러한 특성 덕분에 짧은 문자열의 해싱 최적화에 쓸 만한 선택지가 됩니다.

기타

HMAC, MD5, SHA-1, SHA-2 같은 암호 알고리즘은 너무 느리며 설정 및 종료 처리 비용이 높습니다. 이러한 이유로 이 알고리즘들은 이 목적에 적합하지 않은 것으로 간주됩니다. 최신 AMD 및 Intel CPU에는 AES 암호화 속도를 높이기 위한 AES-NI(AES 명령어 집합) [aes-ni]가 있습니다. AES-NI를 사용하는 CMAC이 실행 가능한 선택지일 수도 있지만, 일상적인 운용에는 아마 너무 느릴 것입니다. (테스트 필요)

결론

SipHash는 속도와 보안의 가장 좋은 조합을 제공합니다. 다른 주요 프로젝트의 개발자들도 같은 결론에 도달했습니다.

짧은 문자열 최적화

SipHash24 같은 해시 함수는 초기화 및 종료 처리 코드의 비용이 커서 아주 짧은 문자열에서는 이 비용이 알고리즘 속도를 좌우할 수 있습니다. 반면에 Python은 짧은 문자열의 해시값을 꽤 자주 계산합니다. 특히 짧은 문자열의 해싱을 위한 간단하고 빠른 함수는 성능에 측정 가능한 영향을 줄 수 있습니다. 예를 들어, 다음 측정값은 Python의 회귀 테스트를 실행하는 동안 수집되었습니다. 다른 코드에 대한 추가 측정에서도 비슷한 배포 양상이 나타났습니다.

바이트 hash() 해시 호출 비율
1 18709 0.2%
2 737480 9.5%
3 636178 17.6%
4 1518313 36.7%
5 643022 44.9%
6 770478 54.6%
7 525150 61.2%
8 304873 65.1%
9 297272 68.8%
10 68191 69.7%
11 1388484 87.2%
12 480786 93.3%
13 52730 93.9%
14 65309 94.8%
15 44245 95.3%
16 85643 96.4%
합계 7921678

그러나 DJBX33A와 같은 빠른 함수는 SipHash24만큼 안전하지 않습니다. 약 5~7바이트 정도에서 컷오프를 두면 적절한 안전 여유를 확보하는 동시에 속도도 높일 수 있을 것입니다. 이 PEP의 참조 구현은 Py_HASH_CUTOFF로 이러한 컷오프를 제공합니다. 이 최적화는 여러 가지 이유로 기본적으로 비활성화되어 있습니다. 첫째로, 보안상의 영향이 아직 명확하지 않으므로 이 최적화를 기본적으로 활성화하기 전에 철저히 연구해야 합니다. 둘째로, 성능상의 이점이 일정하지 않습니다. Intel Core i7을 탑재한 64비트 Linux 시스템에서 Python 벤치마크 모음 [pybench]를 여러 번 실행한 결과, 컷오프를 7로 설정했을 때 django_v2, mako, etree와 같은 벤치마크에서 평균 3%에서 5%의 속도 향상을 보였습니다. 같은 머신에서 X86 바이너리와 Windows X86_64 빌드로 실행한 벤치마크는 작은 문자열 최적화를 적용하면 약간 더 느립니다.

작은 문자열 최적화의 상태는 Python 3.4의 베타 단계 동안 평가될 것입니다. 이 기능은 베타 2가 릴리스되기 전에 적절한 값으로 활성화되거나, 코드가 제거될 것입니다.

C API 추가 사항

모든 C API 확장 수정 사항은 안정 API에 포함되지 않습니다.

해시 시크릿

Python 2.6부터 3.3까지의 _Py_HashSecret_t 타입은 각각 32비트 또는 64비트 길이의 멤버 두 개를 가지고 있습니다. SipHash는 키로 64비트 부호 없는 정수 두 개를 필요로 합니다. 이 typedef는 모든 아키텍처에서 24바이트 크기가 보장되는 공용체(union)로 변경될 것입니다. 이 공용체는 SipHash24와 FNV를 위한 128비트 무작위 키와 함께, 선택적인 작은 문자열 최적화 및 pyexpat 시드를 위한 64비트 추가 값을 제공합니다. 추가 64비트 시드는 pyexpat이나 작은 문자열 최적화가 SipHash24 시드의 비트를 노출할 수 없도록 보장합니다.

64비트 시스템에서의 메모리 레이아웃:

cccccccc cccccccc cccccccc  uc -- unsigned char[24]
pppppppp ssssssss ........  fnv -- two Py_hash_t
k0k0k0k0 k1k1k1k1 ........  siphash -- two PY_UINT64_T
........ ........ ssssssss  djbx33a -- 16 bytes padding + one Py_hash_t
........ ........ eeeeeeee  pyexpat XML hash salt

32비트 시스템에서의 메모리 레이아웃:

cccccccc cccccccc cccccccc  uc -- unsigned char[24]
ppppssss ........ ........  fnv -- two Py_hash_t
k0k0k0k0 k1k1k1k1 ........  siphash -- two PY_UINT64_T (if available)
........ ........ ssss....  djbx33a -- 16 bytes padding + one Py_hash_t
........ ........ eeee....  pyexpat XML hash salt

새 타입 정의:

typedef union {
    /* ensure 24 bytes */
    unsigned char uc[24];
    /* two Py_hash_t for FNV */
    struct {
        Py_hash_t prefix;
        Py_hash_t suffix;
    } fnv;
#ifdef PY_UINT64_T
    /* two uint64 for SipHash24 */
    struct {
        PY_UINT64_T k0;
        PY_UINT64_T k1;
    } siphash;
#endif
    /* a different (!) Py_hash_t for small string optimization */
    struct {
        unsigned char padding[16];
        Py_hash_t suffix;
    } djbx33a;
    struct {
        unsigned char padding[16];
        Py_hash_t hashsalt;
    } expat;
} _Py_HashSecret_t;
PyAPI_DATA(_Py_HashSecret_t) _Py_HashSecret;

_Py_HashSecret_t는 시작 시 Python/random.c:_PyRandom_Init()에서 정확히 한 번 초기화됩니다.

해시 함수 정의

구현:

typedef struct {
    /* function pointer to hash function, e.g. fnv or siphash24 */
    Py_hash_t (*const hash)(const void *, Py_ssize_t);
    const char *name;       /* name of the hash algorithm and variant */
    const int hash_bits;    /* internal size of hash value */
    const int seed_bits;    /* size of seed input */
} PyHash_FuncDef;

PyAPI_FUNC(PyHash_FuncDef*) PyHash_GetFuncDef(void);

autoconf

configure 스크립트에 새로운 검사가 추가됩니다. 이 검사는 정수에 대해 정렬된 메모리 접근을 요구하는 플랫폼을 감지하면 HAVE_ALIGNED_REQUIRED를 설정합니다. X86, X86_64, 최신 ARM과 같은 현재 대부분의 플랫폼은 정렬된 데이터를 필요로 하지 않습니다.

새로운 --with-hash-algorithm 옵션을 사용하면 configure 단계에서 사용자가 해시 알고리즘을 선택할 수 있습니다.

해시 함수 선택

매크로 Py_HASH_ALGORITHM의 값은 내부적으로 어떤 해시 알고리즘을 사용할지 정의합니다. 이 값은 Py_HASH_SIPHASH24, Py_HASH_FNV, Py_HASH_EXTERNAL 세 값 중 하나로 설정할 수 있습니다. Py_HASH_ALGORITHM이 아예 정의되지 않은 경우에는 사용 가능한 가장 좋은 알고리즘이 선택됩니다. 정렬된 메모리 접근을 요구하지 않고(HAVE_ALIGNED_REQUIRED가 정의되지 않음) 부호 없는 64비트 정수 타입 PY_UINT64_T가 있는 플랫폼에서는 SipHash24가 사용됩니다. 64비트 데이터 타입이 없는 엄격한 C89 플랫폼이나 SPARC 같은 아키텍처에서는 대체 수단으로 FNV가 선택됩니다. 해시 알고리즘은 autoconf 옵션으로 선택할 수 있습니다. 예를 들면 ./configure --with-hash-algorithm=fnv와 같습니다.

Py_HASH_EXTERNAL 값을 사용하면 서드파티가 컴파일 시점에 자체 구현을 제공할 수 있습니다.

구현:

#if Py_HASH_ALGORITHM == Py_HASH_EXTERNAL
extern PyHash_FuncDef PyHash_Func;
#elif Py_HASH_ALGORITHM == Py_HASH_SIPHASH24
static PyHash_FuncDef PyHash_Func = {siphash24, "siphash24", 64, 128};
#elif Py_HASH_ALGORITHM == Py_HASH_FNV
static PyHash_FuncDef PyHash_Func = {fnv, "fnv", 8 * sizeof(Py_hash_t),
                                     16 * sizeof(Py_hash_t)};
#endif

Python API 추가 사항

sys 모듈

sys 모듈에는 이미 hash_info 구조체 시퀀스가 있습니다. 활성 해시 알고리즘과 그 속성을 반영하기 위해 이 객체에 필드가 더 추가됩니다.

sys.hash_info(width=64,
              modulus=2305843009213693951,
              inf=314159,
              nan=0,
              imag=1000003,
              # new fields:
              algorithm='siphash24',
              hash_bits=64,
              seed_bits=128,
              cutoff=0)

C 코드에 필요한 수정 사항

_Py_HashBytes() (Objects/object.c)

_Py_HashBytes는 bytes, memoryview, datetime 클래스에 해싱 코드를 제공하는 내부 헬퍼 함수입니다. 현재 이 함수는 unsigned char *에 대해 FNV를 구현합니다.

이 함수는 Python/pyhash.c로 옮겨지고, PyHash_Func.hash()를 통해 해시 함수를 사용하도록 수정됩니다. 함수 시그니처는 첫 번째 인자로 const void *를 받도록 변경됩니다. _Py_HashBytes는 특수한 경우도 처리합니다. 길이가 0인 입력은 0으로, 반환값 -1은 -2로 매핑합니다.

bytes_hash() (Objects/bytesobject.c)

bytes_hash는 _Py_HashBytes를 사용하여 bytes 객체의 tp_hash 슬롯 함수를 제공합니다. 이 함수는 계속 _Py_HashBytes를 사용하지만, 타입 캐스트는 하지 않습니다.

memory_hash() (Objects/memoryobject.c)

memory_hash는 원본 객체도 해시 가능한 경우에 읽기 전용 메모리 뷰의 tp_hash 슬롯 함수를 제공합니다. 이 함수는 앞으로 정렬되지 않은 메모리 세그먼트의 해싱을 지원해야 하는 유일한 함수입니다. 이 함수는 계속 _Py_HashBytes를 사용하지만, 타입 캐스트는 하지 않습니다.

unicode_hash() (Objects/unicodeobject.c)

unicode_hash는 유니코드의 tp_hash 슬롯 함수를 제공합니다. 현재 이 함수는 unsigned char*, Py_UCS2, Py_UCS4에 대해 FNV 알고리즘을 세 번 구현합니다. 이 함수를 다시 구현할 때는 올바른 길이를 사용하도록 주의해야 합니다. 매크로 PyUnicode_GET_LENGTH는 옥텟 단위의 크기가 아니라 유니코드 문자열의 길이를 반환하므로, 이 길이에 내부 유니코드 종류(kind)의 크기를 곱해야 합니다:

if (PyUnicode_READY(u) == -1)
    return -1;
x = _Py_HashBytes(PyUnicode_DATA(u),
                  PyUnicode_GET_LENGTH(u) * PyUnicode_KIND(u));

generic_hash() (Modules/_datetimemodule.c)

generic_hash는 date, time, datetime 타입의 tp_hash 슬롯을 위해 _Py_HashBytes를 감싸는 래퍼 역할을 합니다. timedelta 객체는 상태(days, seconds, microseconds)를 기준으로 해시되며, tzinfo 객체는 해시할 수 없습니다. date, time, datetime 타입 구조체의 데이터 멤버는 void* 단위로 정렬되어 있지 않습니다. 이는 4~10바이트를 정렬된 버퍼로 memcpy()하여 쉽게 해결할 수 있습니다.

성능

일반적으로 SipHash24를 사용하는 PEP 456 코드는 FNV를 사용하는 기존 코드와 거의 같은 속도입니다. SipHash24는 최신 컴파일러, CPU, 큰 L1 캐시를 더 잘 활용하는 것으로 보입니다. 여러 벤치마크에서 Intel Core i5와 Intel Core i7 프로세서 같은 64비트 CPU에서는 속도가 약간 향상되는 것으로 나타났습니다. 32비트 빌드와 AMD Athlon X2 같은 구형 CPU에서의 벤치마크는 SipHash24를 사용할 때 약간 더 느립니다. 성능의 증감 폭이 매우 작으므로 어떤 애플리케이션 코드에도 영향을 주지 않을 것입니다.

벤치마크는 CPython default 브랜치 리비전 b08868fd5994와 PEP 저장소 [pep-456-repos]에서 수행되었습니다. 모든 업스트림 변경 사항은 pep-456 브랜치에 병합되었습니다. 벤치마크가 TurboBoost와 CPU 캐시를 최대한 활용할 수 있도록 “performance” CPU 거버너를 설정하고 거의 모든 프로그램을 중지했습니다. 여러 머신과 플랫폼의 원시 벤치마크 결과는 [benchmarks]에서 확인할 수 있습니다.

해시값 배포

해시값의 좋은 배포는 dict와 set의 성능에 중요합니다. SipHash24와 FNV 모두 입력의 길이를 고려하므로, NULL 바이트로만 이루어진 문자열들이 같은 해시 값을 갖지 않습니다. 또한 입력의 마지막 바이트들은 해시 값의 최하위 비트에 영향을 주는 경향이 있습니다. 이 속성은 공통 접두사를 가진 문자열 사이의 해시 충돌을 줄여 줍니다.

일반적인 길이

Serhiy Storchaka는 [issue16427]에서 사이클당 64비트를 처리하는 수정된 FNV 구현이 현재 FNV 구현보다 긴 문자열을 몇 배 더 빠르게 처리할 수 있음을 보였습니다.

그러나 통계 [issue19183]에 따르면 일반적인 Python 프로그램과 Python 테스트 스위트 모두 해시되는 문자열의 약 50%가 1~6바이트 사이의 짧은 문자열입니다. 16바이트보다 긴 문자열은 5%에 불과합니다.

Grand Unified Python 벤치마크 스위트

실험적 구현과 Grand Unified Python 벤치마크 스위트를 이용한 초기 테스트에서는 차이가 미미한 것으로 나타났습니다. 벤치마크 전체 런타임 합계는 수정하지 않은 Python 3.4 바이너리 런타임과 1% 이내로 차이가 납니다. 테스트는 64비트 Linux가 설치된 Intel i7-2860QM 머신에서 실행되었습니다. 인터프리터는 GCC 4.7로 64비트와 32비트용으로 컴파일되었습니다.

더 많은 벤치마크를 수행할 예정입니다.

하위 호환성

이 수정 사항은 기존 API를 전혀 변경하지 않습니다.

문자열과 바이트열에 대한 hash()의 출력은 달라집니다. ASCII 유니코드와 ASCII 바이트열의 해시 값은 서로 같게 유지됩니다.

해시 충돌 DoS에 대한 대안적 대응책

과거에 해시 충돌에 대한 세 가지 대안적 대응책이 논의되었지만, 이 PEP에서 다루는 내용은 아닙니다.

  1. Marc-Andre Lemburg는 딕셔너리가 해시 충돌 횟수를 세야 한다고 제안했습니다. 삽입 연산이 너무 많은 충돌을 일으키면 예외를 발생시켜야 합니다.
  2. 일부 애플리케이션(예: PHP)은 GET 및 POST HTTP 요청의 키 개수를 제한합니다. 이 방식은 해시 충돌 공격의 영향을 효과적으로 완화합니다. (XXX 인용 필요)
  3. 해시 맵에서 키 삽입과 조회는 최악의 경우 O(n)입니다. 이로 인해 해시 충돌 공격이 일어나면 런타임이 이차적으로 증가합니다. 최악의 경우에도 O(log n)으로 동작하는 새로운 자료 구조를 추가로 도입하면 근본 원인을 제거할 수 있습니다. 레드-블랙 트리나 접두사 트리(트라이 [trie]) 같은 자료 구조에는 다른 이점도 있습니다. 문자열 키를 사용하는 접두사 트리는 공통 접두사를 트리 구조 안에 저장하므로 메모리 사용량을 줄일 수 있습니다.

논의

교체 가능성

이 PEP의 첫 번째 초안에서는 해시 알고리즘을 런타임에 교체할 수 있도록 했습니다. 하나의 바이너리에서 여러 해시 알고리즘을 지원하여 사용자가 시작할 때 해시 알고리즘을 선택할 수 있게 했습니다. 여러 코어 커미터는 이 방식이 불필요하게 복잡하다고 보았습니다 [pluggable]. 이후 버전의 PEP는 컴파일 시간 설정을 목표로 합니다.

정렬되지 않은 메모리 접근

SipHash24 구현은 정렬되지 않은 메모리 문제를 무시하므로 정수 타입의 정렬이 필요한 아키텍처에서는 동작하지 않는다는 비판을 받았습니다. 이 PEP는 이 특수한 경우를 의도적으로 고려하지 않으며, 그러한 플랫폼에서는 SipHash24를 지원하지 않습니다. 달리 입증되기 전까지는 그만한 수고를 들일 가치가 없다고 판단할 뿐입니다. X86, X86_64, ARMv6+ 같은 모든 주요 플랫폼은 속도 저하가 거의 없거나 전혀 없이 정렬되지 않은 메모리를 처리할 수 있습니다. [alignmentmyth]

어차피 거의 모든 블록은 올바르게 정렬되어 있습니다. 현재 bytes와 str의 데이터는 항상 정렬되어 있습니다. 드문 상황에서 memoryview만이 정렬되지 않은 블록을 가리킬 수 있습니다. 이 PEP의 구현은 일반적인 경우에 맞춰 최적화되고 단순화되었습니다.

ASCII str / bytes 해시 충돌

PEP 393 구현 이후로 bytes와 ASCII 텍스트는 같은 메모리 레이아웃을 가집니다. 이 때문에 새 해싱 API는 다음 불변 조건을 유지합니다.:

hash("ascii string") == hash(b"ascii string")

ASCII 문자열과 ASCII bytes에 대해 유지합니다. 해시 값이 같으면 해시 충돌이 발생하므로, 키가 섞여 있는 딕셔너리와 집합에서 약간의 속도 저하가 생깁니다. 예를 들어 bytes의 해시 값에서 2를 빼면 충돌 원인을 제거할 수 있습니다. -2인 이유는 hash(b"") == 0이고 -1은 예약되어 있기 때문입니다. 이 PEP는 해시 값을 변경하지 않습니다.

참고 문헌

  • 이슈 19183 [issue19183]에 참조 구현이 있습니다.