Crypto-PAn

The mathematical outline of Crypto-PAn was developed by Jinliang Fan, Jun Xu, Mostafa H. Ammar (all of Georgia Tech) and Sue B. Moon. It was inspired by the IP address anonymization done by Greg Minshall's TCPdpriv program circa 1996.

Algorithm

Intuitively, Crypto-PAn encrypts a bit-string of length ${\displaystyle n}$ by descending a binary tree of depth ${\displaystyle n}$, one step for each bit in the string. Each of the binary tree's ${\displaystyle 2^n-1}$ non-leaf nodes has been given a value of "0" or "1", according to some pseudo-random function seeded by the encryption key. At each step ${\displaystyle i}$ of the descent, the algorithm computes the ${\displaystyle i}$th bit of the output by XORing the ${\displaystyle i}$th bit of the input with the value of the current node.

The reference implementation takes a 256-bit key. The first 128 bits of the key material are used to initialize an AES-128 cipher in ECB mode. The second 128 bits of the key material are encrypted with the cipher to produce a 128-bit padding block ${\displaystyle \mathit{p}\mathit{a}\mathit{d}}$.

Given a 32-bit IPv4 address ${\displaystyle x}$, the reference implementation performs the following operation for each bit ${\displaystyle x_i}$ of the input: Compose a 128-bit input block ${\displaystyle I_i=x_{[0,i)}{\mathit{p}\mathit{a}\mathit{d}}_{[i,128)}}$. Encrypt ${\displaystyle I_i}$ with the cipher to produce a 128-bit output block ${\displaystyle O_i}$. Finally, XOR the ${\displaystyle i}$th bit of that output block with the ${\displaystyle i}$th bit of ${\displaystyle x}$, and append the result — ${\displaystyle x_i\oplus O_{i,i}}$ — onto the output bitstring. Once all 32 bits of the output bitstring have been computed, the result is returned as the anonymized output ${\displaystyle E_k(x)}$ which corresponds to the original input ${\displaystyle x}$.

The reference implementation does not implement deanonymization; that is, it does not provide a function ${\displaystyle D_k}$ such that ${\displaystyle D_k(E_k(x))=x}$. However, decryption can be implemented almost identically to encryption, just making sure to compose each input block ${\displaystyle I_i=x_{[0,i)}{\mathit{p}\mathit{a}\mathit{d}}_{[i,128)}}$ using the plaintext bits of ${\displaystyle x}$ decrypted so far, rather than using the ciphertext bits: ${\displaystyle I_i\ne E_k(x{)}_{[0,i)}{\mathit{p}\mathit{a}\mathit{d}}_{[i,128)}}$.

The reference implementation does not implement encryption of bitstrings of lengths other than 32; for example, it does not support the anonymization of 128-bit IPv6 addresses. In practice, the 32-bit Crypto-PAn algorithm can be used in "ECB mode" itself, so that a 128-bit string ${\displaystyle x_{[0,128)}}$ might be anonymized as ${\displaystyle E_k(x_{[0,32)})E_k(x_{[32,64)})E_k(x_{[64,96)})E_k(x_{[96,128)})}$. This approach preserves the prefix structure of the 128-bit string, but does leak information about the lower-order chunks; for example, an anonymized IPv6 address consisting of the same 32-bit ciphertext repeated four times is likely the special address ::, which thus reveals the encryption of the 32-bit plaintext 0000:0000.

In principle, the reference implementation's approach (building 128-bit input blocks ${\displaystyle I_i}$) can be extended up to 128 bits. Beyond 128 bits, a different approach would have to be used; but the fundamental algorithm (descending a binary tree whose nodes are marked with a pseudo-random function of the key material) remains valid.