안녕하세요. 입개발자 charsyam 입니다. 아는 척, 있는 척 하기 위해서 예전에 만들었던 python 코드의 test 를 돌려봤는데… -_- 이게 웬일입니까… 테스트가 다 깨지는!!! 처음 만들었을 때는 분명히 돌아가는 테스트코드였는데… 이게 웬 일입니까…
일단 기본적으로 python 에는 hash 라는 built-in 함수가 존재합니다. 그런데 사실 이 hash 함수를 쓰는 것보다는, 명시적인 hashlib 함수를 사용하는 것을 권장합니다. 빌드에 따라 이 hash 함수가 바뀔 수도 있어서…
하여튼 편하게 가보겠다고 hash 함수를 사용했다가 버전이 2.7.x 에서 3.6.x를 쓰다가 피본 경험을 공유합니다. 먼저 증세를 살펴보면, 일단 프로세스가 기동된 상태에서는 결과는 항상 동일합니다. 그래서 항상 새로운 프로세스로 커맨드 라인에서 테스트를 진행합니다.
먼저 2.7.14의 결과입니다.
#2.7.14
python -c "print(hash('123'))"
163512108404620371
python -c "print(hash('123'))"
163512108404620371
python -c "print(hash('123'))"
163512108404620371
#3.6.x
python -c "print(hash('123'))"
8180009514858937698
python -c "print(hash('123'))"
-3358196339336188655
python -c "print(hash('123'))"
-5852881486981464238
일단 이것은 https://docs.python.org/3.3/using/cmdline.html 를 보면 Python 3.3.x 부터 기본적으로 다음과 같이 Hash Randomization 이라는 것이 들어갔다고 합니다. 이게 뭔지는 저는 몰라요, 며느리도 몰라요.
Kept for compatibility. On Python 3.3 and greater, hash randomization is turned on by default.
On previous versions of Python, this option turns on hash randomization, so that the __hash__() values of str, bytes and datetime are “salted” with an unpredictable random value. Although they remain constant within an individual Python process, they are not predictable between repeated invocations of Python.
Hash randomization is intended to provide protection against a denial-of-service caused by carefully-chosen inputs that exploit the worst case performance of a dict construction, O(n^2) complexity. See http://www.ocert.org/advisories/ocert-2011-003.html for details.
PYTHONHASHSEED allows you to set a fixed value for the hash seed secret.
보통 Hash의 값을 예상할 수 있으면, 특정 위치에만 데이터를 집어넣는 DDOS 공격이 가능한데, 이것을 막기 위한 것으로 보이고 그래서 보통 이런 것을 회피하기하기 위한 siphash를 3.x 부터 사용하는것으로 보입니다.(여담으로 Redis에서도 이런 DDOS를 막기위해서 siphash로 기존 hash 함수가 변경되었습니다.)
그럼 실제 어떻게 변화가 되었는지 2.7.14 기준으로 살펴보도록 하겠습니다.
2.7.14 분석
먼저 Python/bltinmodule.c 파일을 살펴보면 다음과 같은 builtin_methods 구조체를 발견할 수 있습니다. 이것은 python 에서 build-in(내장) 함수의 이름을 모아 놓는 것입니다.
static PyMethodDef builtin_methods[] = {
......
{"hash", builtin_hash, METH_O, hash_doc},
......
}
그리고 builtin_methods 의 PyMethodDef 는 Include/methodobject.h 에 다음과 같이 정의되어 있습니다.
struct PyMethodDef {
const char *ml_name; /* The name of the built-in function/method */
PyCFunction ml_meth; /* The C function that implements it */
int ml_flags; /* Combination of METH_xxx flags, which mostly
describe the args expected by the C func */
const char *ml_doc; /* The __doc__ attribute, or NULL */
};
typedef struct PyMethodDef PyMethodDef;
넵, 그렇습니다. 위에 있는 builtin_hash 라는 함수가 실제 hash 명령을 사용했을 때 실행되는 함수입니다. 이제 builtin_hash 함수를 찾아보도록 하겠습니다.(Python/bltinmodule.c)
static PyObject *
builtin_hash(PyObject *self, PyObject *v)
{
long x;
x = PyObject_Hash(v);
if (x == -1)
return NULL;
return PyInt_FromLong(x);
}
결론적으로는 PyObject_Hash 함수를 호출합니다. 구조체 안의 tp_hash 라는 것이 실제 hash 함수를 담고 있습니다.
long
PyObject_Hash(PyObject *v)
{
PyTypeObject *tp = v->ob_type;
if (tp->tp_hash != NULL) {
long r = (*tp->tp_hash)(v);
return r;
}
/* To keep to the general practice that inheriting
* solely from object in C code should work without
* an explicit call to PyType_Ready, we implicitly call
* PyType_Ready here and then check the tp_hash slot again
*/
if (tp->tp_dict == NULL) {
if (PyType_Ready(tp) < 0)
return -1;
if (tp->tp_hash != NULL)
return (*tp->tp_hash)(v);
}
if (tp->tp_compare == NULL && RICHCOMPARE(tp) == NULL) {
return _Py_HashPointer(v); /* Use address as hash value */
}
/* If there's a cmp but no hash defined, the object can't be hashed */
return PyObject_HashNotImplemented(v);
}
그리고 string type 의 경우에는 저기서 tp_hash 가 string_hash 를 호출하게 됩니다. 재미난건 여기서도 _Py_HashSecret 이라는 것을 사용하고 있다는 것!!!(제가 참고한 버전이 2.7.14라서 이런 부분이 있을 수도 있지만… 더 자세한건 마음속에 있는 걸로… 귀찮아요!!!)
static long
string_hash(PyStringObject *a)
{
register Py_ssize_t len;
register unsigned char *p;
register long x;
#ifdef Py_DEBUG
assert(_Py_HashSecret_Initialized);
#endif
if (a->ob_shash != -1)
return a->ob_shash;
len = Py_SIZE(a);
/*
We make the hash of the empty string be 0, rather than using
(prefix ^ suffix), since this slightly obfuscates the hash secret
*/
if (len == 0) {
a->ob_shash = 0;
return 0;
}
p = (unsigned char *) a->ob_sval;
x = _Py_HashSecret.prefix;
x ^= *p << 7;
while (--len >= 0)
x = (1000003*x) ^ *p++;
x ^= Py_SIZE(a);
x ^= _Py_HashSecret.suffix;
if (x == -1)
x = -2;
a->ob_shash = x;
return x;
}
저 _Py_HashSecret 은 다시 Python/random.c의 _PyRandom_Init() 에서 초기화 되게 됩니다. 이때 Py_HashRandomizationFlag 가 설정되어 있지 않아야 합니다. 코드는 간단하니… 알아서… PYTHONHASHSEED 가 설정되면 Py_HashRandomizationFlag 가 1로 셋팅됩니다.
void
_PyRandom_Init(void)
{
char *env;
void *secret = &_Py_HashSecret;
Py_ssize_t secret_size = sizeof(_Py_HashSecret_t);
if (_Py_HashSecret_Initialized)
return;
_Py_HashSecret_Initialized = 1;
/*
By default, hash randomization is disabled, and only
enabled if PYTHONHASHSEED is set to non-empty or if
"-R" is provided at the command line:
*/
if (!Py_HashRandomizationFlag) {
/* Disable the randomized hash: */
memset(secret, 0, secret_size);
return;
}
/*
Hash randomization is enabled. Generate a per-process secret,
using PYTHONHASHSEED if provided.
*/
env = Py_GETENV("PYTHONHASHSEED");
if (env && *env != '\0' && strcmp(env, "random") != 0) {
char *endptr = env;
unsigned long seed;
seed = strtoul(env, &endptr, 10);
if (*endptr != '\0'
|| seed > 4294967295UL
|| (errno == ERANGE && seed == ULONG_MAX))
{
Py_FatalError("PYTHONHASHSEED must be \"random\" or an integer "
"in range [0; 4294967295]");
}
if (seed == 0) {
/* disable the randomized hash */
memset(secret, 0, secret_size);
}
else {
lcg_urandom(seed, (unsigned char*)secret, secret_size);
}
}
else {
#ifdef MS_WINDOWS
(void)win32_urandom((unsigned char *)secret, secret_size, 0);
#elif __VMS
vms_urandom((unsigned char *)secret, secret_size, 0);
#elif defined(PY_GETENTROPY)
(void)py_getentropy(secret, secret_size, 1);
#else
dev_urandom_noraise(secret, secret_size);
#endif
}
}
하여튼 PYTHONHASHSEED 를 설정하지 않거나 0으로 설정해주면 Randomize가 적용이 되지 않습니다.
그럼 이제 3.6.x 에서는 어떻게 변했을까요? 전 이걸 github에서 땡긴거라… 정확한 버전은 잘 모르겠네요.(라고 하고 찾아보니 3.7.0a4+ 네요.)
3.7.0a4+ 분석
2.7.14 의 분석과 마찬가지로 함수 정의 부터 따라가 보도록 하겠습니다. 3.7.0 에서는 Python/bltinmodule.c 에 builtin_methods 에 builtin 함수들이 정의되어 있고 다시 Python/clinic/bltinmodule.c.h 에 BUILTIN_HASH_METHODDEF 이 다음과 같이 정의되어 있습니다.
#define BUILTIN_HASH_METHODDEF \
{"hash", (PyCFunction)builtin_hash, METH_O, builtin_hash__doc__},
여기서도 실제로 builtin_hash 와 연결되어 있으므로 해당 함수를 확인해 봅니다. builtin_hash 는 2.7.14와 크게 다르지 않습니다.
static PyObject *
builtin_hash(PyObject *module, PyObject *obj)
/*[clinic end generated code: output=237668e9d7688db7 input=58c48be822bf9c54]*/
{
Py_hash_t x;
x = PyObject_Hash(obj);
if (x == -1)
return NULL;
return PyLong_FromSsize_t(x);
}
친숙한 PyObject_Hash 가 보이네요. 코드도 거의 비슷하지만 사실은 아주 조금 줄어들었네요.
Py_hash_t
PyObject_Hash(PyObject *v)
{
PyTypeObject *tp = Py_TYPE(v);
if (tp->tp_hash != NULL)
return (*tp->tp_hash)(v);
/* To keep to the general practice that inheriting
* solely from object in C code should work without
* an explicit call to PyType_Ready, we implicitly call
* PyType_Ready here and then check the tp_hash slot again
*/
if (tp->tp_dict == NULL) {
if (PyType_Ready(tp) < 0)
return -1;
if (tp->tp_hash != NULL)
return (*tp->tp_hash)(v);
}
/* Otherwise, the object can't be hashed */
return PyObject_HashNotImplemented(v);
}
Python 2.7 과 3.x의 가장 큰 차이라면 string 이 unicode가 되는 것인데, 여기서 보면, 2.7에서는 string_hash, 3.x에서는 unicode_hash를 호출하게 됩니다.
static Py_hash_t
unicode_hash(PyObject *self)
{
Py_ssize_t len;
Py_uhash_t x; /* Unsigned for defined overflow behavior. */
#ifdef Py_DEBUG
assert(_Py_HashSecret_Initialized);
#endif
if (_PyUnicode_HASH(self) != -1)
return _PyUnicode_HASH(self);
if (PyUnicode_READY(self) == -1)
return -1;
len = PyUnicode_GET_LENGTH(self);
/*
We make the hash of the empty string be 0, rather than using
(prefix ^ suffix), since this slightly obfuscates the hash secret
*/
if (len == 0) {
_PyUnicode_HASH(self) = 0;
return 0;
}
x = _Py_HashBytes(PyUnicode_DATA(self),
PyUnicode_GET_LENGTH(self) * PyUnicode_KIND(self));
_PyUnicode_HASH(self) = x;
return x;
}
그리고 unicode_hash 는 조금 재미난 작업을 합니다. self 에 _PyUnicode_HASH 가 -1이 아니면 이미 자기 자신의 hash 값을 저장하고 있습니다. 그래서 값이 -1이 아니면 바로 전달하고, 그게 아니면 실제로 _Py_HashBytes 를 호출하게 됩니다.(PyUnicode_READY 는 뭔가 아주 복잡한 작업을 하지만… 패스…) 그리고 그 결과를 저장하게 됩니다.
Py_hash_t
_Py_HashBytes(const void *src, Py_ssize_t len)
{
Py_hash_t x;
/*
We make the hash of the empty string be 0, rather than using
(prefix ^ suffix), since this slightly obfuscates the hash secret
*/
if (len == 0) {
return 0;
}
#ifdef Py_HASH_STATS
hashstats[(len <= Py_HASH_STATS_MAX) ? len : 0]++;
#endif
#if Py_HASH_CUTOFF > 0
if (len < Py_HASH_CUTOFF) {
/* Optimize hashing of very small strings with inline DJBX33A. */
Py_uhash_t hash;
const unsigned char *p = src;
hash = 5381; /* DJBX33A starts with 5381 */
switch(len) {
/* ((hash << 5) + hash) + *p == hash * 33 + *p */
case 7: hash = ((hash << 5) + hash) + *p++; /* fallthrough */
case 6: hash = ((hash << 5) + hash) + *p++; /* fallthrough */
case 5: hash = ((hash << 5) + hash) + *p++; /* fallthrough */
case 4: hash = ((hash << 5) + hash) + *p++; /* fallthrough */
case 3: hash = ((hash << 5) + hash) + *p++; /* fallthrough */
case 2: hash = ((hash << 5) + hash) + *p++; /* fallthrough */
case 1: hash = ((hash << 5) + hash) + *p++; break;
default:
Py_UNREACHABLE();
}
hash ^= len;
hash ^= (Py_uhash_t) _Py_HashSecret.djbx33a.suffix;
x = (Py_hash_t)hash;
}
else
#endif /* Py_HASH_CUTOFF */
x = PyHash_Func.hash(src, len);
if (x == -1)
return -2;
return x;
}
중요한 부분만 보면 PyHash_Func.hash 이 코드가 됩니다. 그럼 PyHash_Func.hash는 어떻게 구성이 되는가?
다음과 같은 코드를 쉽게 찾을 수 있습니다. Py_HASH_ALGORITHM 가 무엇으로 설정되는가에 따라서 fnv 나 siphash24 로 설정이 되게 됩니다.(Python/pyhash.c)
typedef struct {
Py_hash_t (*const hash)(const void *, Py_ssize_t);
const char *name;
const int hash_bits;
const int seed_bits;
} PyHash_FuncDef;
#if Py_HASH_ALGORITHM == Py_HASH_FNV
static PyHash_FuncDef PyHash_Func = {fnv, "fnv", 8 * SIZEOF_PY_HASH_T,
16 * SIZEOF_PY_HASH_T};
#endif
#if Py_HASH_ALGORITHM == Py_HASH_SIPHASH24
static PyHash_FuncDef PyHash_Func = {pysiphash, "siphash24", 64, 128};
#endif
특별한 옵션을 주지 않으면 일단 Py_HASH_SIPHASH24 로 설정이 되게 됩니다. configure 파일을 보면
--with-hash-algorithm=[fnv|siphash24]
select hash algorithm
로 되어있고, 이게 명시되지 않으면, MEMORY ALIGN 이 필요한 CPU(또는 cross compile을 지정해야해서) 쪽에서는 fnv가, 그렇지 않은 저 같은 맥이나 일반 x86 계열에서는 siphash24 가 설정이 되게 됩니다.
PyHash_Func.hash 가 호출되면 pysiphash 가 실제로 불리게 됩니다. 파라매터를 잘 보면 _Py_HashSecret 에서 사용하는 siphash 관련 값들이 넘어가게 됩니다.
static Py_hash_t
pysiphash(const void *src, Py_ssize_t src_sz) {
return (Py_hash_t)siphash24(
_le64toh(_Py_HashSecret.siphash.k0), _le64toh(_Py_HashSecret.siphash.k1),
src, src_sz);
}
그럼 이제 마지막으로 3.x 에서 이 _Py_HashSecret 를 설정하는지 보면 됩니다. 먼저 _Py_HashSecret_t 는 다음과 같이 구성됩니다.
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;
/* two uint64 for SipHash24 */
struct {
uint64_t k0;
uint64_t k1;
} siphash;
/* 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;
실제 _Py_HashSecret 의 설정은 _Py_HashRandomization_Init 에서 이루어집니다. 제 맥에서는 _Py_HashRandomization_Init를 호출하는 call stack 은 다음과 같습니다. 이 이야기는 처음에 시작과 동시에 호출이 된다는 것입니다.
* frame #0: 0x000000010027de16 python`_Py_HashRandomization_Init(config=0x00007fff5fbff778) at bootstrap_hash.c:569
frame #1: 0x000000010026364f python`_Py_InitializeCore(core_config=0x00007fff5fbff778) at pylifecycle.c:649
frame #2: 0x00000001002abd05 python`pymain_main(pymain=0x00007fff5fbff720) at main.c:2647
frame #3: 0x00000001002abea7 python`_Py_UnixMain(argc=1, argv=0x00007fff5fbff8b8) at main.c:2695
frame #4: 0x0000000100000e62 python`main(argc=1, argv=0x00007fff5fbff8b8) at python.c:15
frame #5: 0x00007fffa8f62235 libdyld.dylib`start + 1
frame #6: 0x00007fffa8f62235 libdyld.dylib`start + 1
_Py_HashRandomization_Init 는 Python/bootstrap_hash.c 에 있습니다. 2.7.14와의 차이는 2.7.14에서는 PYTHONHASHSEED 가 없으면 randomize 작업이 없지만, 3.x 에서는 PYTHONHASHSEED 가 설정되어 있으면 그 값으로 seed를, 없으면 pyurandom 을 호출해서 randomize 가 일어나게 된다는 것입니다.
_PyInitError
_Py_HashRandomization_Init(const _PyCoreConfig *config)
{
void *secret = &_Py_HashSecret;
Py_ssize_t secret_size = sizeof(_Py_HashSecret_t);
if (_Py_HashSecret_Initialized) {
return _Py_INIT_OK();
}
_Py_HashSecret_Initialized = 1;
if (config->use_hash_seed) {
if (config->hash_seed == 0) {
/* disable the randomized hash */
memset(secret, 0, secret_size);
}
else {
/* use the specified hash seed */
lcg_urandom(config->hash_seed, secret, secret_size);
}
}
else {
/* use a random hash seed */
int res;
/* _PyRandom_Init() is called very early in the Python initialization
and so exceptions cannot be used (use raise=0).
_PyRandom_Init() must not block Python initialization: call
pyurandom() is non-blocking mode (blocking=0): see the PEP 524. */
res = pyurandom(secret, secret_size, 0, 0);
if (res < 0) {
return _Py_INIT_USER_ERR("failed to get random numbers "
"to initialize Python");
}
}
return _Py_INIT_OK();
}
python 에서 hash randomize를 끄고 싶다면, 양 버전 모두 PYTHONHASHSEED 을 0으로 설정하는 것입니다. 하지만, 권장하는 것은 python 의 built-in hash 함수를 쓰지말고, 명시적으로 알 수 있는 hash 함수를 사용하는 것이 훨씬 좋다는 것입니다.(결론은 마지막 한줄!!!)
Charsyam's Blog 