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라는 세 가지 서로 다른 유니코드 표현에 대해 여러 번 구현되어 있습니다. 따라서 인터프리터의 대규모 부분을 패치하고 재컴파일하지 않고서는 임베더가 이를 다른 구현으로 교체할 수 없습니다. 임베더는 더 적합한 해시 함수를 선택하려 할 수 있습니다.

마지막으로 현재 구현 코드는 성능이 좋지 않습니다. 일반적인 경우에는 사이클당 1바이트 또는 2바이트만 처리합니다. 최신 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')가 됩니다.

해시 함수와 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는 암호학적 해시 알고리즘이 아니며 딕셔너리 구현도 사이드 채널 분석에 대비되어 있지 않으므로, 원격 공격자가 무작위화 비밀값을 계산할 수 있습니다. 이 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은 [sip] [ocert-2012-001]에서 Murmur3가 해시 충돌 공격에 견고하지 않음을 보였습니다. 따라서 Murmur3는 더 이상 보안 알고리즘으로 간주할 수 없습니다. 해시 충돌 공격이 문제가 되지 않는다면 여전히 대안이 될 수 있습니다.

CityHash

CityHash [city]는 Google을 위해 Geoff Pike와 Jyrki Alakuijala가 개발한 비암호학적 해시 함수 제품군입니다. 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은 [sip]에서 CityHash에도 유사한 약점이 있음을 보였습니다.

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바이트로 보장되는 유니온으로 변경됩니다. 이 유니온은 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가 선택됩니다. 예를 들어 ./configure --with-hash-algorithm=fnv와 같은 autoconf 옵션으로 해시 알고리즘을 선택할 수 있습니다.

Py_HASH_EXTERNAL값은 제3자가 컴파일 시점에 자체 구현을 제공할 수 있도록 합니다.

구현:

#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는 유니코드 문자열의 길이를 반환하며 옥텟 단위 크기를 반환하지 않으므로, 길이에 내부 유니코드 종류의 크기를 곱해야 합니다.:

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에서 성능이 소폭 향상되는 것으로 나타났습니다. AMD Athlon X2와 같은 구형 CPU에서의 32비트 빌드 및 벤치마크는 SipHash24를 사용할 때 약간 더 느립니다. 성능의 증감 폭이 매우 작으므로 애플리케이션 코드에 영향을 주지 않을 것입니다.

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

해시 값 분포

해시 값의 양호한 분포는 dict 및 set 성능에 중요합니다. SipHash24와 FNV는 모두 입력 길이를 고려하므로 NULL 바이트로만 이루어진 문자열이 동일한 해시 값을 갖지 않습니다. 입력의 마지막 바이트도 해시 값의 최하위 비트에 영향을 주는 경향이 있습니다. 이 특성은 공통 접두사를 가진 문자열에서 해시 충돌의 수를 줄입니다.

일반적인 길이

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

그러나 [issue19183]의 통계에 따르면 일반적인 Python 프로그램과 Python 테스트 스위트 모두 1~6바이트인 짧은 문자열이 약 50%를 차지합니다. 문자열 중 5%만 16바이트보다 큽니다.

Grand Unified Python 벤치마크 스위트

실험적 구현과 Grand Unified Python 벤치마크 스위트를 사용한 초기 테스트에서 편차가 최소인 것으로 나타났습니다. 벤치마크의 요약된 총 실행 시간은 수정하지 않은 Python 3.4 바이너리의 실행 시간에서 1% 이내입니다. 테스트는 64비트 Linux가 설치된 Intel i7-2860QM 시스템에서 실행되었습니다. 인터프리터는 64비트 및 32비트용으로 GCC 4.7을 사용하여 컴파일되었습니다.

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

하위 호환성

변경 사항은 기존 API를 변경하지 않습니다.

문자열과 바이트에 대한 hash()의 출력은 달라집니다. ASCII 유니코드와 ASCII 바이트의 해시 값은 계속 동일합니다.

해시 충돌 DoS에 대한 대체 대응책

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

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

논의

플러그 가능

이 PEP의 첫 번째 초안에서는 해시 알고리즘을 런타임에 플러그 가능하게 만들었습니다. 하나의 바이너리에서 여러 해시 알고리즘을 지원하여 사용자가 시작할 때 해시 알고리즘을 선택할 수 있도록 했습니다. 여러 핵심 커미터는 이 접근 방식을 불필요한 복잡성으로 여겼습니다 [pluggable]. 이후 버전의 PEP에서는 컴파일 시간 구성을 목표로 합니다.

비정렬 메모리 접근

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

어쨌든 거의 모든 블록은 적절하게 정렬되어 있습니다. 현재 bytes와 str의 데이터는 항상 정렬되어 있습니다. 드문 상황에서 메모리뷰만 비정렬 블록을 가리킬 수 있습니다. PEP 구현은 일반적인 경우에 맞게 최적화되고 단순화되어 있습니다.

ASCII str / bytes 해시 충돌

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

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

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

참고 자료

  • 이슈 19183 [issue19183]에는 참조 구현이 포함되어 있습니다.