FeistelCipher

Encrypted integer IDs using Feistel cipher

Database Support: PostgreSQL only (uses PostgreSQL triggers and functions)

Why?

Problem: Sequential IDs (1, 2, 3...) leak business information:

Common Solutions & Issues:

This Library's Approach:

If you need fully stable IDs across seed runs/environments, use time_bits: 0 so IDs are generated from the ciphered data component only.

Installation

Using Ash Framework?

If you're using Ash Framework, use ash_feistel_cipher instead! It provides a declarative DSL to configure Feistel cipher encryption directly in your Ash resources.

For plain Ecto users, continue below.

Using igniter (Recommended)

mix igniter.install feistel_cipher

Manual Installation

# mix.exs
def deps do
  [{:feistel_cipher, "~> 1.1"}]
end

Then run:

mix deps.get
mix feistel_cipher.install

⚠ïļ mix feistel_cipher.install is provided by Igniter. If your project does not use Igniter, create a migration manually and call FeistelCipher.up_v1_functions/1 in up and FeistelCipher.down_v1_functions/1 in down.

Installation Options

Both methods support the following options:

⚠ïļ Security Note: A cryptographically random salt is generated by default for each project. This ensures that encryption patterns cannot be analyzed across different projects. Never use the same salt across multiple production projects.

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 at IBM, introducing the cipher structure that powers this library. We thought it deserved a permanent timestamp in your database history! 🎂

Upgrading from v0.x

See UPGRADE.md for the migration guide.

Usage Example

1. Create Migration

defmodule MyApp.Repo.Migrations.CreatePosts do
  use Ecto.Migration

  def up do
    create table(:posts) do
      add :seq, :bigserial
      add :title, :string
    end

    # 1 day buckets
    execute FeistelCipher.up_for_v1_trigger("public", "posts", "seq", "id",
      time_bucket: 86400
    )
  end

  def down do
    execute FeistelCipher.down_for_v1_trigger("public", "posts", "seq", "id")
    drop table(:posts)
  end
end

2. Define Schema

defmodule MyApp.Post do
  use Ecto.Schema

  # Hide seq in API responses
  @derive {Jason.Encoder, except: [:seq]}

  schema "posts" do
    field :seq, :id, read_after_writes: true
    field :title, :string
  end
end

The read_after_writes: true option tells Ecto to fetch the seq value after INSERT (since it's generated by the database).

Now when you insert a record, seq auto-increments and the trigger automatically sets id = [time_prefix | feistel_cipher_v1(seq)]:

%Post{title: "Hello"} |> Repo.insert!()
# => %Post{id: 8234567890123, 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.

Backfilling Existing Rows

When you add a new encrypted column to a table that already has data, use backfill_for_v1_column/5 to fill rows that were inserted before the trigger existed.

def up do
  alter table(:posts) do
    add :public_id, :bigint, default: -1
  end

  execute FeistelCipher.up_for_v1_trigger("public", "posts", "seq", "public_id",
    time_bits: 0,
    data_bits: 32
  )

  execute FeistelCipher.backfill_for_v1_column("public", "posts", "seq", "public_id",
    time_bits: 0,
    data_bits: 32
  )
end

Backfill uses an internal sentinel value of -1, which is safe because FeistelCipher only emits non-negative integers.

ID Structure

The generated ID has the structure [time_bits | data_bits]:

┌─────────────────┮──────────────────────────────────────────┐
│   time_bits     │              data_bits                   │
│   (15 bits)     │              (38 bits)                   │
│   time prefix   │     feistel_cipher_v1(seq)               │
└─────────────────â”ī──────────────────────────────────────────┘

Why Time Prefix?

PostgreSQL incremental backups (e.g., pg_basebackup with WAL, pgBackRest) back up entire pages (8KB blocks). Without a time prefix, Feistel cipher distributes IDs uniformly across all pages — meaning each new row touches a different page, and incremental backups become as large as full backups.

With a time prefix, rows from the same time bucket land on nearby pages, so incremental backups only need to capture the recently-modified pages.

When to Use Time Prefix (time_bits > 0)

Use a time prefix when you want write locality and smaller incremental backups on large/high-write tables.

When NOT to Use Time Prefix (time_bits: 0)

Disable time prefix when you only need opaque IDs and don't need backup/page-locality optimization.

Trigger Options

up_for_v1_trigger/5 takes 4 positional arguments and an options keyword list:

⚠ïļ Important: Parameter changes should be handled as explicit migrations. Some options (like time_bits/time_bucket/encrypt_time) can be changed technically, but old/new IDs will use different semantics. Core cipher options (data_bits/key/rounds) should be treated as immutable in-place.

Constraints:

⚠ïļ You cannot reliably compare IDs by time_bits alone to determine temporal order. Because time_value = floor(now / time_bucket) mod 2^time_bits, the prefix wraps after time_bucket * 2^time_bits seconds. This feature is intended to improve PostgreSQL incremental backup locality, not to provide UUIDv7-style global time ordering.

Why time_offset Exists

time_bucket alone uses UTC-based boundaries. For daily buckets, that means bucket changes at UTC midnight, which may split a local business day at awkward local times (for example, evening in the Americas or early morning in Europe).

time_offset lets you align bucket boundaries to your operational day (for example, 03:00 local cutover) without changing time_bucket size. This improves practical continuity for time-prefix clustering, especially when encrypt_time: true is enabled and the prefix itself is not human-readable.

In this library, time_offset is added to epoch before bucketing. That is why +21600 (not -21600) gives a 03:00 KST boundary for daily buckets.

Example with custom options:

execute FeistelCipher.up_for_v1_trigger(
  "public", "posts", "seq", "id",
  time_bits: 8,
  time_bucket: 86400,
  time_offset: 21600,
  data_bits: 32,
  key: 123456789,
  rounds: 8,
  functions_prefix: "crypto"
)

Example without time prefix:

execute FeistelCipher.up_for_v1_trigger(
  "public", "posts", "seq", "id",
  time_bits: 0
)

Advanced Usage

Column Rename

When renaming columns that have triggers, drop and recreate the trigger:

defmodule MyApp.Repo.Migrations.RenamePostsColumns do
  use Ecto.Migration

  def change do
    # 1. Drop the old trigger
    execute FeistelCipher.down_for_v1_trigger("public", "posts", "seq", "id")

    # 2. Rename columns
    rename table(:posts), :seq, to: :sequence
    rename table(:posts), :id, to: :external_id

    # 3. Recreate trigger with SAME encryption parameters
    # IMPORTANT: Generate key using OLD column names (seq, id)
    old_key = FeistelCipher.generate_key("public", "posts", "seq", "id")

    execute FeistelCipher.up_for_v1_trigger("public", "posts", "sequence", "external_id",
      time_bits: 15,               # Must match original
      time_bucket: 86400,          # Must match original
      data_bits: 38,               # Must match original
      key: old_key,                # Key from OLD column names
      rounds: 16,                  # Must match original
      functions_prefix: "public"   # Must match original
    )
  end
end

⚠ïļ Critical: When recreating triggers, ALL encryption parameters (time_bits, time_bucket, data_bits, key, rounds, functions_prefix) MUST match the original values. Otherwise:

⚠ïļ Warning: Dropping a trigger removes encryption for that column pair. Only use this when intentionally removing or recreating the trigger.

Alternative: Display-Only IDs

If you prefer to keep your sequential id as the primary key, you can use Feistel cipher for display-only columns. This approach is similar to using Hashids or other ID obfuscation libraries, but with database-native encryption.

# Migration
create table(:posts) do
  add :disp_id, :bigint    # Encrypted, for public APIs
  add :title, :string
end

create unique_index(:posts, [:disp_id])

execute FeistelCipher.up_for_v1_trigger("public", "posts", "id", "disp_id",
  time_bucket: 86400
)

# Schema
defmodule MyApp.Post do
  use Ecto.Schema

  # Hide internal id in API responses
  @derive {Jason.Encoder, except: [:id]}

  schema "posts" do
    field :disp_id, :id, read_after_writes: true
    field :title, :string
  end
end

Then only expose disp_id in your APIs while keeping id internal.

Advantages over Hashids: Database-native (no encoding/decoding).

Performance

Encrypting 100,000 sequential values:

Rounds Total Time Per Encryption
1 180 ms ~1.8Ξs
2 285 ms ~2.8Ξs
4 475 ms ~4.7Ξs
8 824 ms ~8.2Ξs
161709 ms~17.1Ξs
32 3171 ms ~31.7Ξs

Default is 16 rounds - provides good security/performance balance with cryptographic HMAC-SHA256. The overhead per INSERT/UPDATE is negligible for most applications.

Benchmark Environment

Running Benchmarks

MIX_ENV=test mix run benchmark/rounds_benchmark.exs

Prerequisites:

The benchmark encrypts 100,000 sequential values (1 to 100,000) using a SQL batch function to minimize overhead and measure pure encryption performance.

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.

Feistel Cipher Diagram

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).

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:

-- Encryption: seq → data part of id
data_component = feistel_cipher_v1(seq, data_bits, key, rounds)

-- Decryption: data part of id → seq (using the same function!)
seq = feistel_cipher_v1(data_component, data_bits, key, rounds)

Key Properties

License

MIT