# FeistelCipher
Unpredictable integer IDs - no UUIDs needed
## Why?
**Problem**: Sequential IDs (1, 2, 3...) leak business information:
- Competitors can estimate your growth rate
- Users can enumerate resources (`/posts/1`, `/posts/2`...)
- Total record counts are exposed
**Common Solutions & Issues**:
- UUIDs: Fixed 36 chars for everything - overkill for most columns
- Random integers: Collision risks, complex generation logic
**This Library's Approach**:
- Store sequential integers internally (fast, efficient indexing)
- Expose encrypted integers externally (non-sequential, unpredictable)
- **Adjustable bit size per column**: user_id = 40 bits (12 digits), post_id = 52 bits (16 digits)
- Automatic encryption via database trigger
## How It Works
The Feistel cipher is a symmetric structure used in the construction of block ciphers. This library implements a configurable Feistel network that transforms sequential integers into non-sequential encrypted integers with one-to-one mapping.
<p align="center">
<img src="assets/feistel-diagram.png" alt="Feistel Cipher Diagram" width="66%">
</p>
> **Note**: The diagram above illustrates a 2-round Feistel cipher for simplicity. By default, this library uses **16 rounds** for better security. The number of rounds is configurable (see [Trigger Options](#trigger-options)).
### Self-Inverse Property
The Feistel cipher is **self-inverse**: applying the same function twice returns the original value. This means encryption and decryption use the exact same algorithm.
**Mathematical Proof:**
Let's denote the input as $(L_1, R_1)$ and the round function as $F(x)$.
**First application (Encryption):**
$$
\begin{aligned}
L_2 &= R_1, & R_2 &= L_1 \oplus F(R_1) \\
L_3 &= R_2, & R_3 &= L_2 \oplus F(R_2) \\
\text{Output} &= (R_3, L_3)
\end{aligned}
$$
**Second application (Decryption) - Starting with $(R_3, L_3)$:**
$$
\begin{aligned}
L_2' &= L_3, & R_2' &= R_3 \oplus F(L_3) \\
&= L_3, & &= R_3 \oplus F(R_2) \\
&= L_3, & &= (L_2 \oplus F(R_2)) \oplus F(R_2) \\
&= L_3, & &= L_2 = R_1 \quad \text{(XOR cancellation)} \\
\\
L_3' &= R_2' = R_1, & R_3' &= L_2' \oplus F(R_2') \\
&= R_1, & &= L_3 \oplus F(R_1) \\
&= R_1, & &= R_2 \oplus F(R_1) \\
&= R_1, & &= (L_1 \oplus F(R_1)) \oplus F(R_1) \\
&= R_1, & &= L_1 \quad \text{(XOR cancellation)} \\
\\
\text{Output} &= (R_3', L_3') = (L_1, R_1) \quad \checkmark
\end{aligned}
$$
**Key Insight:** The XOR operation's property $a \oplus b \oplus b = a$ ensures that each transformation is reversed when applied twice.
**Database Implementation:**
In the database trigger implementation, this means:
```sql
-- Encryption: seq → id
id = feistel_encrypt(seq, bits, key)
-- Decryption: id → seq (using the same function!)
seq = feistel_encrypt(id, bits, key)
```
### Key Properties
- **Deterministic**: Same input always produces same output
- **Non-sequential**: Sequential inputs produce seemingly random outputs
- **Collision-free**: One-to-one mapping within the bit range
## Installation
> **Using Ash Framework?**
>
> If you're using [Ash Framework](https://ash-hq.org/), use [`ash_feistel_cipher`](https://github.com/devall-org/ash_feistel_cipher) instead! It provides a declarative DSL to configure Feistel cipher encryption directly in your Ash resources.
>
> ```elixir
> use Ash.Resource,
> extensions: [AshFeistelCipher]
>
> feistel_cipher do
> source :seq
> target :id
> bits 52
> rounds 16
> end
> ```
>
> For plain Ecto users, continue below.
### Using igniter (Recommended)
```bash
mix igniter.install feistel_cipher
```
### Manual Installation
```elixir
# mix.exs
def deps do
[{:feistel_cipher, "~> 0.9.3"}]
end
```
Then run:
```bash
mix deps.get
mix feistel_cipher.install
```
### Installation Options
Both methods support the following options:
* `--repo` or `-r`: Specify an Ecto repo (required for manual installation)
* `--functions-prefix` or `-p`: PostgreSQL schema prefix (default: `public`)
* `--functions-salt` or `-s`: Cipher salt constant, max 2^31-1 (default: `1_076_943_109`)
> **Fun Fact**: Notice the timestamp `19730501000000` in the migration file generated during installation? That's May 1, 1973 - the day [Horst Feistel published his groundbreaking paper](https://en.wikipedia.org/wiki/Feistel_cipher#History) at IBM, introducing the cipher structure that powers this library. We thought it deserved a permanent timestamp in your database history! 🎂
## Usage Example
### 1. Create Migration
```elixir
defmodule MyApp.Repo.Migrations.CreatePosts do
use Ecto.Migration
def up do
create table(:posts, primary_key: false) do
add :seq, :bigserial
add :id, :bigint, primary_key: true
add :title, :string
timestamps()
end
execute FeistelCipher.up_for_trigger("public", "posts", "seq", "id")
end
def down do
execute FeistelCipher.down_for_trigger("public", "posts", "seq", "id")
drop table(:posts)
end
end
```
### 2. Define Schema
```elixir
defmodule MyApp.Post do
use Ecto.Schema
@primary_key {:id, :id, autogenerate: true}
schema "posts" do
field :seq, :id, autogenerate: true
field :title, :string
timestamps()
end
# Use @derive to control JSON serialization
@derive {Jason.Encoder, except: [:seq]} # Hide seq in API responses
end
```
Now when you insert a record, `seq` auto-increments and the trigger automatically sets `id = feistel_encrypt(seq)`:
```elixir
%Post{title: "Hello"} |> Repo.insert()
# => %Post{id: 8234567, seq: 1, title: "Hello"}
# In API responses, only id is exposed (seq is hidden)
```
**Security Note**: Keep `seq` internal. Only expose `id` in APIs to prevent enumeration attacks.
## Trigger Options
The `up_for_trigger/5` function accepts these options:
- `prefix`, `table`, `source`, `target`: Table and column names (required)
- `bits`: Cipher bit size (default: 52, max: 62, must be even) - **Cannot be changed after creation**
- **Choose different sizes per column**: Unlike UUIDs (fixed 36 chars), tailor each column's ID length
- Example: user_id = 40 bits (12 digits, 1T values), post_id = 52 bits (16 digits, 4.5Q values)
- Default 52 ensures JavaScript compatibility (`Number.MAX_SAFE_INTEGER = 2^53 - 1`)
- Use 62 for maximum range if no browser/JS interaction needed
- `rounds`: Number of Feistel rounds (default: 16, min: 1, max: 32)
- **Default 16** provides good security/performance balance
- **Note**: Diagrams and proofs in this README use 2 rounds for simplicity
- More rounds = more secure but slower
- Odd rounds (1, 3, 5...) and even rounds (2, 4, 6...) are both supported
- `key`: Encryption key (auto-generated if not specified)
- `functions_prefix`: Schema where cipher functions reside (default: `public`)
Example with custom options:
```elixir
execute FeistelCipher.up_for_trigger(
"public", "posts", "seq", "id",
bits: 40,
key: 123456789,
rounds: 8,
functions_prefix: "crypto"
)
```
## Performance
Benchmark results encrypting 100,000 sequential values:
| Rounds | Total Time | Per Encryption | Use Case |
|--------|------------|----------------|----------|
| 1 | 103 ms | ~1.0μs | Minimal obfuscation |
| 2 | 131 ms | ~1.3μs | Illustration (diagrams/proofs) |
| 4 | 178 ms | ~1.8μs | Light security |
| 8 | 278 ms | ~2.8μs | Moderate security |
| **16** | **444 ms** | **~4.4μs** | **Default (recommended)** |
| 32 | 867 ms | ~8.7μs | Maximum security |
The overhead per INSERT is negligible (microseconds) even with 16 rounds.
### Benchmark Environment
- **CPU**: Apple M3 Pro (12 cores)
- **Database**: PostgreSQL 17 (Postgres.app)
- **OS**: macOS 15.6
- **Elixir**: 1.18.3 / OTP 27
### Running Benchmarks
```bash
MIX_ENV=test mix run benchmark/rounds_benchmark.exs
```
The benchmark encrypts 100,000 sequential values (1 to 100,000) using a SQL batch function to minimize overhead and measure pure encryption performance.
## License
MIT
