난독화되어 비순차적인 긴 숫자 형식의 UID(Unique ID) 만들어 쓰기 (PHP, Python)

UUID, GUID

16진수(0-9, A-Z)를 사용해 고유한 ID 값을 만드는 방법은 이미 표준이다시피 한 방법이 존재한다.

Universally_unique_identifier from Wikipedia

이 값은 여러 시스템 안에서 ‘고유’하므로, MySQL에서도 GUID를 이용해 Replication 내의 시스템에서 트랜잭션을 구분하기도 한다.

Human Readable

다만, UUID 형식이 16진수로 되어있고 매우 길어, 시스템 내부에서 리소스를 다루기에는 적합하지만, 화면 상에 출력될 용도일 때 사람이 읽기에 아름답지(?) 못한 면이 있다.

Facebook 서비스도 내부적으로 숫자만을 사용해 콘텐츠 id를 부여하고 있다.  (아래 설명할 내용과 관련해,) 사용 추적에 대한 부분에는 해당 uid가 노출되거나 전달되지 않도록 하는 정책을 가지고 있는 것 같다.

Facebook UID에 관해 – 2010년 10월 19일

Sequential vs 난독화(Obfuscation)

MySQL DB의 table에 열을 기록할 때에 primary key를 지정하게 된다. 보통은 이 값은 고유하다는 것 외에 크게 의미가 없으므로 1부터 순차적으로 증가하는 값을 쓰게 된다.

하지만 이 순차적인 key 가 Web 접근이나 REST API 호출에서 URL을 통해 노출 될 경우, 해당 키의 앞 또는 뒤의 콘텐츠를 유추할 수 있게 된다. 예를 들어,  순차적인 key가 부여된 사전 데이터의 39485 key가 ‘우삼’이라면 39484 key 의 값은 ‘우산나물’, 39486 key의 값은 ‘우상’ 따위가 될 것임을 직감적으로 알 수 있다. 그리고 (별도의 인증 절차가 없다는 가정 하에) 악의적으로 1부터 순차적으로 증가하며 모든 데이터를 크롤링할 수 있을 것이다.

유추가 어려우면서도 읽기 편한 이상하고 까다로운(?) 조건을 만족시키기 위해서, 숫자로 구성되어 있으면서 순차적이지 않은 uid를 만들어야 할 필요성이 있다. 역시나 같은 고민을 다른 사람들은 훨씬 더 먼저 했고, 솔루션은 이미 있으므로 가져다 쓰면 된다.

Optimus id transformation

위 라이브러리는 소수를 이용해 ‘정수 범위’의 숫자를 난독화 하는 PHP 라이브러리이다.

난독화의 원리

특정 범위의 숫자에 그 범위의 가장 큰 수보다 더 큰 소수(Prime Number)를 곱하면, 범위의 가장 큰 수보다 큰 자리수를 떼어내더라도 해당 범위 내에서는 절대 겹치지 않는다. 수학이란, 소수란 참 신기하다.

0~15 범위의 숫자에 10 보다 더 큰 소수 23을 곱하고 max 값과 AND 연산한 결과이다.

0xF(0b1111, 0d15) 보다 큰 자리수를 떼어내었을 때 중복되지 않는다. 범위의 가장 큰 값 15가 넘어가면, 다시 중복되는 수가 나타나기 시작한다.

이러한 현상은 수의 크기가 커져도 동일하다. 양의 정수의 범위인 0 ~ 2,147,483,647(0x7FFFFFFF) 로 범위를 확장하더라도 2,147,483,647보다 큰 소수만 곱해준다면 범위 내에서 절대절대절대절대 중복되지 않는다.

미리 구해진 여러자리 소수 값은 다음을 참조.

Prime Curios!

xor은 난독화된 수가 순차적인 원수에 대해 경향성을 나타내는 것을 보완하기 위해 한 번 더 꼬아주는 역할을 하는 것으로 보인다.

 

이 수식의 위대함은 모듈러 역수를 이용해 원수를 구할 수 있다는 것이다.

모듈러 역수는 한 번의 연산으로 구해지지는 않고, 해당 범위의 수를 모두 대입해 조건을 만족하는하는 지 찾아야 하는 것 같다. 다행히 많은 언어에서 이미 구현된 함수가 주어진다. 또한, 이 값은 매번 구하지 않고 한 번만 계산해 상수로 박아 넣으면 된다.

물론, 소스에 박힌 소수와 역수에 대한 값을 알지 못하는 외부 사용자는 난독화된 값을 통해 원수를 추측할 수 없다.

최대값의 모순

이 알고리즘 안에서, 곱해진 수에서 최대값 max을 넘어가는 자릿수을 떼어내기 위해서는 오른쪽 bit가 모두 채워진 16진수 값을 사용해야한다.

예를 들어, 가운데 0이 포함된 0 ~ 9(0x9, 0b1001)범위를 사용하고 싶다고 하면, 이 값으로 and 연산을 했을 때 0이 되는 bit의 값이 누락되어 2(0b0010), 4(0b0100), 6(0b0110) 등에서 의도한 결과가 나오지 않는다.

그렇다 보니, 최대값을 모든 자리를 9로 채우는 10진수(예를 들어, 999999, 1000000 등)로 설정할 수 없다. 범위의 제약이 없는 알고리즘으로 개선해보는 것도 의미가 있을 듯 하다.

정수 이상으로 확장

위에 링크한 Optimus 라이브러리는, 정수를 대상으로 범위가 제한되어있는데, 다행히 PHP 외 여러 언어들은 정수 이상의 범위 숫자에 대한 산술 연산, bit 연산을 위한 라이브러리를 제공한다. 난독화 라이브러리의 핵심 로직만 이해한다면 충분히 범위를 확장할 수 있을 것이다.

주의해야할 점은, 계산에 사용될 소수가 범위의 최대값 보다 커야한다는 것 뿐이다.

Python의 경우, 기본 연산 자체가 int,  long 등의 제한이 없다.

Seed 범위 설정

이 문서에서는 16자리의 숫자 UID를 만들고, 16자리 정수로 오른쪽 bit를 모두 채우는 가장 큰 수를 max 값으로 지정했다.

안타깝지만 위에 설명한 최대값의 모순으로 9007 1992 5474 0992 ~ 9999 9999 9999 9999 에 대한 난독화는 불가능하다. 1 bit만 추가하더라도 2배로 커져 17자리수로 넘어가버린다.

위의 범위로는, 9천 조 개의 리소스를 생성하고 UID를 할당할 수 있다. 200년 동안 하루에 1,233억 개, 시간 당 51억 개, 초 당 1,428,082 개를 할당할 수 있는 양이다.

16자리의 난독화에는 역시 최대 16자리(물론 max 값 이하)의 원수가 필요하다. 최소한 원수인 seed 자체가 중복되지 않아야한다. 그러기 위해서는 microtime을 포함하는 시간 데이터가 적합해 보인다.

시스템의 처리시간을 감안하여 1/1,000,000 초 보다 더 자주 uid 가 발행되지는 않는다고 협상했을 때, 20자리의 원수가 필요하다. 16자리를 초과하므로 이 경우는 적용 불가.

위과 같이. microtime 자리를 줄여 1/100 초로 발행주기를 협상하면 가능하긴 하나 매우 빠른(?) 시스템에서 너무 위험해 보인다.

100년 이상은 고려하지 않고, 1/10,000 초보다 더 자주 발행되지 않는다고 협상하면 16자리로 원수를 맞출 수 있다.

 

unix timestamp는 1900년 부터 시작하는 대신, 비교적 유연하게 범위를 지정할 수 있다. 1/1,000,000초 발행주기를 가지며, 난독화를 적용할 경우, timestamp가 9007 1992 5474 0991 가 되는 2255-06-06 08:47:34 까지 대응이 가능하다.

 

물론 이 seed 의 규칙은 설정하고자 하는 uid의 자리수와 사용 조건에 따라 여러 변수가 있을 수 있을 것이다.

매우 단순하게 생각했을 때, DB상의 primary key를 순차적으로 저장하고, 표시할 때만 위 알고리즘을 이용해 난독화 하여 표시해줘도 된다.

여러 테이블에 같은 uid 규칙을 적용하고 구분하기 위해 난독화된 uid 에 임의의 prefix를 지정해 사용할 수도 있을 것이다. ( "12" + "1234 5678 9012 3456" )

소스

timestamp + microtime 을 원수(seed)로 해, 9007 1992 5474 0991 범위 내의 난독화 수를 만들고, 역계산을 통해 검증까지 하는 소스이다.

 

도큐멘트 에 올린 글 태그됨: , , , , , , , , , , , , ,

댓글 남기기