Honey Encryption

1. 등장 배경

1. Encryption 함수 Enc와 Decryption 함수 Dec을 갖는 Symmetric Cipher Model을 상정한다. SCM = [Enc, Dec]

2. Secret Key K를 통해 message M을 암호화 하면 ciphertext C를 얻을 수 있다. Enc(M, K) = C

3. Secret Key K를 안다면, C를 decode해 Message를 다시 복원할 수 있다. Dec(C, K) = M

4. 공격자가 Ciphertext C를 Brute-Force 한 방식으로 decode해가며 Key와 Message를 알아내려 한다고 가정하자.

5. Key가 현실의 Password 같은 Low-Entropy Distribution(일반적으로 Password를 Uniform Random하게 추출하지 않는다)에서 나왔다면, 가능하다고 생각되는 Key들을 모두 시도해 Message의 후보군을 구성할 수 있다.

6. 이 때, Message가 어떤 분포를 따른다면(특징이 있다면), 분포를 벗어나는 대부분의 경우를 제외하고, Plausible한 Message를 후보군에서 뽑아내기 쉬울 것이다.
   ex) ASCII로 인코딩(8bit를 사용하는 ASCII)된 16자리의 신용카드번호의 예시를 보자. 각 자리는 0~9의 digit이 나와야 하므로 $\frac{10}{2^8}^{16} < 2^{-74}$ 의 비율로 숫자로 구성된 Message가 된다. 또한 신용카드 번호는 Validation 규칙이 있으므로 그 중에서도 Valid한 후보는 더 적어져, Attacker가 공격에 성공할 확률이 높아진다.

7. 위와 같은 한계점을 극복하고자, Decrypt해서 얻어낸 Message의 후보들이 모두 '그럴싸'하도록 하는 Framework를 똑똑하신 선생님들께서 만드셨고 이를 Honey Encryption(이하 HE)이라고 한다.

8. Honey Encryption의 Honey는 Invalid한 Key로도 만들어지는 Valid한 Message들을 비유하며 사용되었다. 공격자는 달콤한 꿀을 바른 Fake Message에 속게 되는 것이다.

9. 이 재미있는 Framework가 어떻게 만들어지는지, paper를 읽고 노력해서(...) 읽고 이해한 바를 적어보았다.

2. Honey Encryption Framework 구성

1. 처음 위 아이디어를 들었을 때는 En/Decryption에 쓰이는 함수가 기깔난 Mapping을 갖고 있어서, 어떤 Key로 Decrypt해도 말이 되는 Plaintext를 뱉는다고 생각했다.

2. 핵심은 En/Decryption Algorithm이 아닌 Distribution Transforming Encoder(이하 DTE)에 있다. DTE는 Message가 따르는 Distribution $p_m$과 비슷한 $p_d$를 모사할 수 있도록 설계된다. 어떻게와 왜는 DTE가 HE에서 하는 역할을 보면 이해할 수 있다.

3. HE에서 나타낸 다음의 En/Decryption 과정을 보자.
   $DTE(Message) = Seed\newline Encrypt(Seed, Key) = Ciphertext$
   $Decrypt(Ciphertext, Key) = Seed\newline DTE(Seed)=Message$
   Encryption 과정에서 DTE는 Message를 Seed로 바꾸고(주로 n-bit binary string), 이를 Key와 Encrypt해서 Ciphertext를 만든다. Decryption은 Ciphertext와 Key를 통해 Decrypt해서 얻은 Seed를 DTE로 Message로 변환하며 이뤄진다.

4. 앞에서 언급했듯, DTE는 Message의 분포 $p_m$을 모사해야 한다. 그래야 공격자가 brute-force를 통해 얻은 다양한 Message 후보들(다양한 Seed를 DTE에 넣어서 얻은 Message들)을 보고도 무엇이 진짜인지 알 수가 없기 때문이다. DTE는 $p_m$과 비슷한 $p_d$를 구성하기 위해,

   1. 가능한 모든 Message가 있는 Message space M을 고려한다.
   2. 각 Message의 확률 분포에 비례하여 Seed space S(n bit binary로 구성, Cardinality가 M보다는 크거나 같아야함)의 Seed를 순서대로 Range 별로 Mapping한다.
   3. Encryption 과정에서 Message의 Seed는 Seed Range 내에서 임의로 추출된다.

   예시를 만들어 다시 풀어보자면
   M = {A, B, C}이고, P(A) = 0.25, P(B) = 0.5, P(C) = 0.25라고 하자. 2 bit Seed를 사용한다면, S = {00, 01, 10, 11}이 된다. 확률의 크기에 비례해서 Seed를 할당하면, A는 00, B는 01, 10, C는 11을 할당받을 것이다. B의 경우는 Seed가 01이 될 수도 10이 될 수도 있다.

5. Decryption의 경우 Seed를 받으면 DTE가 Deterministic하게 Message를 선택하게 된다. 그러나, 위의 간단한 예시에서는 Table을 만들어서 모든 정보와 Mapping을 저장해도 되었지만, 현실의 M과 S는 무척이나 크기에 이와 같은 구현은 매우 비효율 적이다. 가령 n bit string이 32bit만 되어도 2^32개의 Row를 갖는 Table을 만들어서 Mapping해야한다.
   비효율을 극복하기 위해, $p_m$을 통해 충분한 Message의 Sample을 추출해(inverse CDF 방식이나 rejection Sampling을 쓸 수 있다. 이는 확률 분포를 알고 있으나, Sampling이 어려운 경우 쓰이는 방식인데, 상세한 내용은 따로 지면을 할애해 작성하고자 한다. 왜냐하면 기가 막히게도 이번 학기에 다른 수업에서 배운 내용이기 때문이다.), CDF-Message(Sample) 쌍의 Table을 대신 만든다. Seed를 토대로 해당 Table에서 Binary Search하면 Seed가 속해있는 구간을 알 수 있고, 그 구간 내에서 linear search를 하며 Message를 찾는다. 이 구현 방식은 이 paper와 그 구현 코드에 멋지게 나와있다.

3. Honey Encryption 활용

1. 위 논문들에서 다루었듯, RSA Scheme이나 신용카드 등 다양한 영역에서 활용이 가능하다. Password에 기반한 Encryption System의 단점을 보완하기 위해 나온 만큼 확장성이 좋다. 사람이 주고받는 Text Message까지 활용 가능성이 있다.

2. 대표적인 Challenge로는 Text Message에 HE를 적용했을 때, Grammar가 맞는 Honey들이 많게끔 하는 것은 가능했으나, Context 정보에 있어서는 정확하지 않은 문장들이 많아 복잡도를 줄였다.

3. 결국 핵심은 각 Scheme 별로 Specific하게 DTE를 Design해야 한다는 것이고, DTE를 Design하기 위해서는 Message의 분포에 대한 좋은 정보를 가지고 있어야 한다는 것이다.

4. 기회가 된다면, 나도 주제를 잡아 간단히 구현해보면 좋지 않을까? 미래의 나의 의지력과 이번 학기 과제 및 공부들의 험난함에 Dependent하다.