Bordercrypt: plausible deniable sessions, V2

[damip]

bordercrypt: Snapshot-resistant plausibly deniable multi-session storage using pq-rerand

1. Overview

bordercrypt is an on-device storage scheme designed to:

• Support up to SESSION_COUNT = 5 independent sessions.
• Provide plausible deniability among existing sessions under a snapshot adversary.
• Resist attackers who take regular snapshots of device storage and compare diffs over time.

The design uses:

• A post-quantum public-key encryption primitive with public re-randomization (pq-rerand) to make ciphertexts efficiently refreshable without secret keys.
• An AEAD layer inside pq-rerand messages to provide authenticity and detect corruption/tampering.
• A password KDF and a general-purpose KDF to derive session-wrapping keys and per-block AEAD keys with domain separation.

AEAD, pq-rerand, and KDF are treated as abstract primitives with required APIs and security properties.

---

2. Threat model and security goals

2.1 Adversary capabilities

• Can take full snapshots of device storage at arbitrary times and compare snapshots.
• Has strong classical and quantum computation.
• May learn the password(s) for some sessions and decrypt them.
• May corrupt or delete stored data.

2.2 Goals

1. Plausible deniability among existing sessions
   If the adversary controls (can decrypt) some sessions, they should not be able to prove whether other sessions exist or are being used.

2. Snapshot-resistance for read/write patterns
   When one session is updated, observable storage changes should not identify which session was updated.

3. Integrity for unlocked sessions
   For the session whose password is known, data reads must authenticate; tampering/corruption is detected by AEAD.

2.3 Non-goals

• Preventing denial-of-service (an attacker can corrupt/delete data; bordercrypt focuses on confidentiality, deniability, and detection of corruption for unlocked sessions).
• Making creation of new sessions plausibly deniable (see below).

2.4 Important limitation: session creation is not plausibly deniable

Creating a new session changes its public key in the keypair file. Since the public key is stored in cleartext and must be valid for rerandomization, a snapshot adversary can detect that a session slot’s public key changed. Therefore:

• Using and modifying an already-existing session is plausibly deniable (within the scheme’s guarantees).
• Creating a new session is not plausibly deniable due to public key changes.

---

3. Cryptographic primitives (abstract)

3.1 pq-rerand

A post-quantum PKE supporting public re-randomization.

Required API:

• pq_rerand.encrypt(pk, message[MSG_SIZE]) -> ciphertext[CT_SIZE]
• pq_rerand.decrypt(sk, ciphertext[CT_SIZE]) -> message[MSG_SIZE] (fails only on invalid size)
• pq_rerand.rerand(pk, ciphertext[CT_SIZE]) -> ciphertext[CT_SIZE]

Required properties:

• Ciphertexts are computationally indistinguishable from random (IND$ / strong pseudorandom ciphertext distribution).
• Re-randomization produces a fresh-looking ciphertext encrypting the same message.

3.2 AEAD

Required API:

• AEAD.encrypt(key, nonce, plaintext, aad) -> ciphertext_with_tag
• AEAD.decrypt(key, nonce, ciphertext_with_tag, aad) -> plaintext OR fail

Requirements:

• Constant-time authentication check.
• Single generic failure (no distinguishable error types).

3.3 KDF and password KDF

• password_kdf(password_bytes, salt_bytes) -> root_key
• KDF.new(salt_bytes) with:
  • input_item(bytes_or_integer_canonically_encoded)
  • finalize()
  • expand(label_bytes, out_len) -> out_bytes[out_len]

---

4. Constants and sizes

SESSION_COUNT = 5

# pq-rerand fixed block sizes
PQ_CT_SIZE  = 65536   # ciphertext size per stored block
PQ_MSG_SIZE = 15872   # message size per encryption

# AEAD sizes (must match chosen AEAD)
AEAD_NONCE_SIZE = 16
AEAD_TAG_SIZE   = 16

# Application payload capacity per block after AEAD framing
PLAINTEXT_SIZE = PQ_MSG_SIZE - AEAD_NONCE_SIZE - AEAD_TAG_SIZE  # = 15840

# Session data length header stored in block 0 plaintext
LENGTH_HDR_SIZE = 8    # u64 big-endian

BLOCK_SIZE = PQ_CT_SIZE

All encrypted blocks on disk are exactly BLOCK_SIZE bytes. Blocks are not version-prefixed.

---

5. Storage layout

Each session slot i ∈ [0..SESSION_COUNT-1] has:

• A keypair file containing the session version, pq public key, and an AEAD-wrapped pq secret key.
• A blockstream file containing a concatenation of BLOCK_SIZE ciphertext blocks.

5.1 Keypair file format

Path: sessions/session_{i}.keypair

Binary format:

• version: u32 big-endian
• pq_pk: session pq-rerand public key (cleartext, syntactically valid)
• sk_nonce: AEAD_NONCE_SIZE bytes (cleartext)
• sk_ct: AEAD ciphertext+tag of pq_sk (length depends on pq secret key encoding and AEAD)

Notes:

• pq_pk must always be valid because cover traffic and cover writes use it.
• If a session is “unallocated”, its sk_nonce and sk_ct may be random bytes; decrypting with any password-derived key should fail.

5.2 Blockstream file format

Path: sessions/session_{i}.blocks

• Raw concatenation of blocks: N * BLOCK_SIZE bytes.
• Block b is the slice [b*BLOCK_SIZE, (b+1)*BLOCK_SIZE).

5.3 Plaintext layout inside decrypted blocks

After pq-rerand decryption and AEAD verification, each block yields exactly PLAINTEXT_SIZE bytes.

• Block 0 plaintext

  • [0..8): total_data_length as u64 big-endian
  • [8..PLAINTEXT_SIZE): session data bytes starting at logical offset 0

• Block b ≥ 1 plaintext

  • [0..PLAINTEXT_SIZE): continuation of session data

Any unused bytes in the last partially filled block are random padding.

5.4 Global invariants

• All session blockstream files must have identical length (same number of blocks). If inconsistent, extend shorter ones using cover blocks until all match.
• On any write to a block index b in one session, block index b is updated for all sessions (genuine for the target session, rerandomized or cover for others).

---

6. Domain separation

Let domain be a stable, installation-specific identifier (e.g., app namespace + storage namespace).

Define strings:

• ROOT = domain + ":bordercrypt"
• Session scope: S = ROOT + ":session:v{version}:i{session_i}"
• Block scope: B = S + ":b{block_index}"

Usage:

• Password KDF salt: ROOT + ":password_kdf"
• Root KDF salt: domain + ":kdf:salt"
• Keypair secret-key wrap AEAD AAD: S + ":pq_sk_wrap"
• Per-block KDF salt: B + ":kdf:salt"
• Per-block AEAD key label: B + ":kdf:block_aead_key"
• Block AEAD AAD: B + ":block_aead"

All domain strings are UTF-8 bytes.

---

7. Block encryption primitives

7.1 Genuine block encoding

A genuine block encrypts:

• nonce[AEAD_NONCE_SIZE] || AEAD.encrypt(aead_key, nonce, plaintext_15840, aad)[PLAINTEXT_SIZE + AEAD_TAG_SIZE]
  This is exactly PQ_MSG_SIZE bytes, then pq-rerand encrypted into BLOCK_SIZE bytes.

def encrypt_block(pq_rerand_pk, aead_sk, aad_root, plaintext):
    # plaintext must be exactly PLAINTEXT_SIZE bytes
    assert len(plaintext) == PLAINTEXT_SIZE

    nonce = rand(AEAD_NONCE_SIZE)

    aad = aad_root + ":block_aead"
    aead_ct = AEAD.encrypt(
        key=aead_sk,
        nonce=nonce,
        plaintext=plaintext,
        aad=aad
    )
    # aead_ct length must be PLAINTEXT_SIZE + AEAD_TAG_SIZE
    msg = nonce + aead_ct
    assert len(msg) == PQ_MSG_SIZE

    return pq_rerand.encrypt(pk=pq_rerand_pk, message=msg)


def decrypt_block(pq_rerand_sk, aead_sk, aad_root, block_ct):
    assert len(block_ct) == BLOCK_SIZE

    msg = pq_rerand.decrypt(sk=pq_rerand_sk, ciphertext=block_ct)
    nonce = msg[:AEAD_NONCE_SIZE]
    aead_ct = msg[AEAD_NONCE_SIZE:]

    aad = aad_root + ":block_aead"
    plaintext = AEAD.decrypt(
        key=aead_sk,
        nonce=nonce,
        ciphertext_with_tag=aead_ct,
        aad=aad
    )
    # plaintext is PLAINTEXT_SIZE bytes
    return plaintext

7.2 Cover block encoding (structured and realistic)

Cover blocks should look like they contain a well-formed nonce || AEAD_ct frame. To do this, generate a temporary AEAD key (not stored), and produce a valid AEAD encryption of random plaintext under that temporary key. Then pq-rerand encrypt the resulting message using the session’s real pq_pk.

This yields a pq-rerand ciphertext that:

• Is syntactically indistinguishable from a genuine block ciphertext.
• Contains an inner AEAD frame that is well-formed and tag-valid under an unknown key, but will fail verification under the session-derived per-block AEAD key.

def create_cover_block(pq_rerand_pk, aad_root):
    # Create a realistic nonce+AEAD frame with a temporary key.
    tmp_aead_sk = rand(AEAD_KEY_SIZE)
    nonce = rand(AEAD_NONCE_SIZE)
    plaintext = rand(PLAINTEXT_SIZE)

    aad = aad_root + ":block_aead"
    aead_ct = AEAD.encrypt(
        key=tmp_aead_sk,
        nonce=nonce,
        plaintext=plaintext,
        aad=aad
    )
    msg = nonce + aead_ct
    assert len(msg) == PQ_MSG_SIZE

    return pq_rerand.encrypt(pk=pq_rerand_pk, message=msg)

7.3 Re-randomization

def rerandomize_block(pq_rerand_pk, block_ct):
    return pq_rerand.rerand(pk=pq_rerand_pk, ciphertext=block_ct)

---

8. Key derivation and session unlock

8.1 Unlocking a session

A password is used to derive:

• sk_wrap_key: AEAD key to decrypt the pq secret key in a keypair file.
• root_aead_key: root material used to derive per-block AEAD keys.

The unlock procedure attempts to decrypt each session slot’s wrapped secret key in randomized order.

def unlock_session(domain, password_bytes):
    ROOT = domain + ":bordercrypt"

    root_key = password_kdf(
        password_bytes,
        salt=ROOT + ":password_kdf"
    )

    kdf = KDF.new(salt=domain + ":kdf:salt")
    kdf.input_item(root_key)
    kdf.finalize()

    sk_wrap_key = kdf.expand(ROOT + ":kdf:sk_wrap_key", out_len=AEAD_KEY_SIZE)
    root_aead_key = kdf.expand(ROOT + ":kdf:root_aead_key", out_len=ROOT_BLOCK_KEY_SIZE)

    for session_i in shuffle(range(SESSION_COUNT)):
        version, pq_pk, sk_nonce, sk_ct = read_session_keypair_file(session_i)

        S = ROOT + f":session:v{version}:i{session_i}"
        aad = S + ":pq_sk_wrap"

        try:
            pq_sk = AEAD.decrypt(
                key=sk_wrap_key,
                nonce=sk_nonce,
                ciphertext_with_tag=sk_ct,
                aad=aad
            )
            session = {
                "session_version": version,
                "session_index": session_i,
                "pq_pk": pq_pk,
                "pq_sk": pq_sk,
                "root_aead_key": root_aead_key
            }
            # Cache total_data_length by reading block 0 header (section 10).
            session["total_data_length"] = read_total_length(domain, session)
            return session
        except:
            continue

    raise InvalidPassword()

8.2 Per-block AEAD key derivation

def derive_block_aead_key(domain, session_version, session_i, root_aead_key, block_index):
    ROOT = domain + ":bordercrypt"
    B = ROOT + f":session:v{session_version}:i{session_i}:b{block_index}"

    kdf = KDF.new(salt=B + ":kdf:salt")
    kdf.input_item(root_aead_key)
    kdf.input_item(u32_be(session_i))
    kdf.input_item(u64_be(block_index))
    kdf.finalize()

    aead_sk = kdf.expand(B + ":kdf:block_aead_key", out_len=AEAD_KEY_SIZE)
    return aead_sk, B

---

9. Reading and decrypting blocks

9.1 Decrypt a single session block

def decrypt_session_data_block(domain, session, block_index):
    version = session["session_version"]
    session_i = session["session_index"]

    if version != 0:
        raise UnsupportedVersion()

    block_ct = read_session_block(session_i, block_index)  # 65536 bytes

    aead_sk, aad_root = derive_block_aead_key(
        domain, version, session_i,
        session["root_aead_key"], block_index
    )

    return decrypt_block(
        pq_rerand_sk=session["pq_sk"],
        aead_sk=aead_sk,
        aad_root=aad_root,
        block_ct=block_ct
    )

9.2 Read total session length (cached in memory)

The total session data length is stored in the first 8 bytes of block 0 plaintext.

def read_total_length(domain, session):
    if get_global_block_count() == 0:
        return 0
    pt0 = decrypt_session_data_block(domain, session, block_index=0)
    return u64_from_be(pt0[0:LENGTH_HDR_SIZE])

---

10. Reading session data (byte ranges)

10.1 Logical addressing

Let:

• offset be the logical byte offset into the session data (0-based).
• length be the number of bytes requested.
• total = session["total_data_length"].

Session data is laid out starting at plaintext position LENGTH_HDR_SIZE within block 0.

Define virtual plaintext positions:

• start_pos = LENGTH_HDR_SIZE + offset
• end_pos_excl = LENGTH_HDR_SIZE + offset + length

Each block b contributes PLAINTEXT_SIZE plaintext bytes to the virtual stream:

• Block b covers [b*PLAINTEXT_SIZE, (b+1)*PLAINTEXT_SIZE).

10.2 Read algorithm

def read_session_data(domain, session, offset, length):
    total = session["total_data_length"]
    if offset + length > total:
        raise OutOfBounds()

    start_pos = LENGTH_HDR_SIZE + offset
    end_pos_excl = LENGTH_HDR_SIZE + offset + length

    first_block = start_pos // PLAINTEXT_SIZE
    last_block = (end_pos_excl - 1) // PLAINTEXT_SIZE

    out = bytearray()

    for b in range(first_block, last_block + 1):
        pt = decrypt_session_data_block(domain, session, b)

        block_start = b * PLAINTEXT_SIZE
        block_end = block_start + PLAINTEXT_SIZE

        take_start = max(start_pos, block_start) - block_start
        take_end = min(end_pos_excl, block_end) - block_start

        out += pt[take_start:take_end]

    return bytes(out)

---

11. Writing blocks with snapshot resistance

11.1 Rationale

When a genuine block is written for one session, the same block index must be updated for every session. This ensures snapshot diffs show that all sessions changed at that index, preventing an attacker from linking diffs to the active session.

Additionally, the order in which session files are updated must be randomized on each operation. If an attacker takes a snapshot while a multi-session update is in progress, randomized order reduces correlation between “which sessions have already been updated” and the target session.

11.2 Encrypt and store one block index (genuine for target, cover/rerand for others)

def encrypt_session_data_block(domain, session, block_index, plaintext):
    version = session["session_version"]
    session_i = session["session_index"]

    if version != 0:
        raise UnsupportedVersion()
    assert len(plaintext) == PLAINTEXT_SIZE

    # Prepare the genuine ciphertext for the target session
    aead_sk, aad_root = derive_block_aead_key(
        domain, version, session_i,
        session["root_aead_key"], block_index
    )
    genuine_ct = encrypt_block(
        pq_rerand_pk=session["pq_pk"],
        aead_sk=aead_sk,
        aad_root=aad_root,
        plaintext=plaintext
    )

    # Update all sessions at this index in randomized order
    for cur_i in shuffle(range(SESSION_COUNT)):
        cur_version, cur_pk = read_session_version_and_pk(cur_i)

        # Deduce aad_root for cover generation realism
        cur_aad_root = (domain + ":bordercrypt" +
                        f":session:v{cur_version}:i{cur_i}:b{block_index}")

        if cur_i == session_i:
            write_session_block(cur_i, block_index, genuine_ct)
            fsync_session_blocks_file(cur_i)
        else:
            # Prefer rerandomization of existing ciphertext to keep continuity of "same message"
            # If the existing block is missing/corrupt, replace with a fresh cover block.
            try:
                cur_ct = read_session_block(cur_i, block_index)
                new_ct = rerandomize_block(cur_pk, cur_ct)
            except:
                new_ct = create_cover_block(cur_pk, cur_aad_root)

            write_session_block(cur_i, block_index, new_ct)
            fsync_session_blocks_file(cur_i)

Implementation note: write_session_block should be atomic at BLOCK_SIZE granularity, or implemented with a journal/rename strategy to avoid partial writes being observable in snapshots.

---

12. Extending the blockstream (allocate more space)

12.1 Requirements

All sessions’ blockstream files must remain the same length. When extending, append one block to every session:

• The active session receives a genuine block.
• Other sessions receive a cover block.

12.2 Ensure global blockstream length

def get_global_block_count():
    counts = []
    for i in range(SESSION_COUNT):
        counts.append(file_size(session_blocks_path(i)) // BLOCK_SIZE)
    return max(counts)

def repair_blockstream_lengths(domain):
    # Extend shorter streams with cover blocks until all match the global max
    global_count = get_global_block_count()
    for i in range(SESSION_COUNT):
        while (file_size(session_blocks_path(i)) // BLOCK_SIZE) < global_count:
            version, pk = read_session_version_and_pk(i)
            block_index = file_size(session_blocks_path(i)) // BLOCK_SIZE
            aad_root = (domain + ":bordercrypt" +
                        f":session:v{version}:i{i}:b{block_index}")
            append_block(i, create_cover_block(pk, aad_root))
            fsync_session_blocks_file(i)

def ensure_block_count(domain, session, required_count):
    repair_blockstream_lengths(domain)
    while get_global_block_count() < required_count:
        extend_blockstream_with_session_block(domain, session)

12.3 Extend by one block index

def extend_blockstream_with_session_block(domain, session):
    # New block index equals current global block count (after repair)
    repair_blockstream_lengths(domain)
    block_index = get_global_block_count()

    for cur_i in shuffle(range(SESSION_COUNT)):
        cur_version, cur_pk = read_session_version_and_pk(cur_i)
        cur_aad_root = (domain + ":bordercrypt" +
                        f":session:v{cur_version}:i{cur_i}:b{block_index}")

        if cur_i == session["session_index"]:
            # Genuine block content is random padding; header is set only for block 0.
            pt = bytearray(rand(PLAINTEXT_SIZE))
            if block_index == 0:
                pt[0:LENGTH_HDR_SIZE] = u64_be(session["total_data_length"])

            aead_sk, aad_root = derive_block_aead_key(
                domain, session["session_version"], cur_i,
                session["root_aead_key"], block_index
            )
            ct = encrypt_block(
                pq_rerand_pk=session["pq_pk"],
                aead_sk=aead_sk,
                aad_root=aad_root,
                plaintext=bytes(pt)
            )
            append_block(cur_i, ct)
        else:
            ct = create_cover_block(cur_pk, cur_aad_root)
            append_block(cur_i, ct)

        fsync_session_blocks_file(cur_i)

---

13. Writing session data (byte ranges)

13.1 Behavior

• Writes may span multiple blocks.

• If a block is partially overwritten, the implementation first tries to decrypt it:

  • If decryption succeeds, modify the plaintext and re-encrypt.
  • If decryption fails, treat the prior plaintext as fresh random bytes and proceed.

• If a block is fully overwritten (and is not block 0), decryption can be skipped and a random base plaintext used.

• After any write that increases session length, the total length header in block 0 is updated.

13.2 Write algorithm

def write_session_data(domain, session, offset, data):
    version = session["session_version"]
    if version != 0:
        raise UnsupportedVersion()

    old_total = session["total_data_length"]
    new_total = max(old_total, offset + len(data))
    session["total_data_length"] = new_total

    # Ensure enough blocks exist to cover the new total length
    if new_total == 0:
        required_last_block = 0
    else:
        required_last_block = (LENGTH_HDR_SIZE + (new_total - 1)) // PLAINTEXT_SIZE

    ensure_block_count(domain, session, required_last_block + 1)

    # Determine affected blocks in the virtual plaintext stream
    start_pos = LENGTH_HDR_SIZE + offset
    end_pos_excl = LENGTH_HDR_SIZE + offset + len(data)

    first_block = start_pos // PLAINTEXT_SIZE
    last_block = (end_pos_excl - 1) // PLAINTEXT_SIZE

    for b in range(first_block, last_block + 1):
        block_start_pos = b * PLAINTEXT_SIZE
        block_end_pos = block_start_pos + PLAINTEXT_SIZE

        w_start = max(start_pos, block_start_pos)
        w_end = min(end_pos_excl, block_end_pos)
        assert w_start < w_end

        # Full overwrite optimization (skip decryption) for non-header blocks
        full_overwrite = (w_start == block_start_pos) and (w_end == block_end_pos) and (b != 0)

        if full_overwrite:
            pt = bytearray(rand(PLAINTEXT_SIZE))
        else:
            try:
                pt = bytearray(decrypt_session_data_block(domain, session, b))
            except:
                pt = bytearray(rand(PLAINTEXT_SIZE))

        src_off = w_start - start_pos
        src_len = w_end - w_start
        dst_off = w_start - block_start_pos
        pt[dst_off:dst_off + src_len] = data[src_off:src_off + src_len]

        if b == 0:
            pt[0:LENGTH_HDR_SIZE] = u64_be(new_total)

        encrypt_session_data_block(domain, session, b, bytes(pt))

---

14. Shrinking session data (space deallocation)

14.1 Motivation: allocation-size information leak

There is a subtle information leak inherent to allocation. If an adversary unlocks a session that uses only a fraction of the total blockstream (e.g., 50%), the remaining blocks — which that session cannot decipher — constitute unexplained allocated space. This is evidence that one or more other sessions exist and caused those blocks to be allocated.

This leak becomes especially dangerous across repeated snapshots. Consider a journalist who crosses the same border checkpoint twice within a short interval (e.g., outbound and return trips a week apart). If the device is snapshotted both times, the adversary can compare:

• Total blockstream length at snapshot 1 vs snapshot 2.
• Data length reported by any unlocked session at each snapshot.

If the unlocked session's data shrank between snapshots but the blockstream did not, the adversary learns the freed blocks must belong to another session — or at minimum that the storage dynamics are inconsistent with a single session.

14.2 Design principle: the blockstream never shrinks

To address this, the global blockstream length never decreases. When a session deletes data and requires fewer blocks, the freed blocks are converted back into cover blocks rather than being removed. This makes the storage indistinguishable from the case where another session originally caused the allocation and the unlocked session was always small.

Critical invariant: cross-session rerandomization in randomized order. As with all block-level operations in bordercrypt (§11.1), every block index touched during a shrink must be updated across all sessions, not just the session being shrunk, and the order in which session files are written must be randomized for each block index. The active session's freed blocks become cover blocks, while the same-index blocks in every other session are rerandomized. This is essential — if only the shrinking session's blocks changed at those indices, a snapshot diff would immediately reveal which session performed the deallocation. The randomized write order ensures that if a snapshot is taken mid-operation, the set of already-updated sessions does not correlate with the active session.

The deallocation procedure has two parts:

1. Partially freed blocks: If the session's data no longer fills its last used block completely, the unused tail bytes within that block are replaced with fresh randomness. The block is re-encrypted as a genuine block with the updated content and length header. The same block index in all other sessions is rerandomized in randomized session order (this is handled by encrypt_session_data_block per §11.2).

2. Fully freed blocks: Blocks beyond the session's new last block are entirely replaced with fresh cover blocks. These are structurally identical to blocks that any other session might have allocated (see §7.2), making them indistinguishable from pre-existing cover blocks. At the same time, the same block index in every other session is rerandomized, with session write order randomized per block index, so the snapshot diff at each freed index spans all sessions uniformly.

14.3 Shrink algorithm

def shrink_session_data(domain, session, new_total):
    version = session["session_version"]
    if version != 0:
        raise UnsupportedVersion()

    old_total = session["total_data_length"]
    if new_total >= old_total:
        return  # not a shrink
    if new_total < 0:
        raise InvalidLength()

    session["total_data_length"] = new_total

    # Determine old and new last block indices (in the virtual plaintext stream)
    if old_total == 0:
        old_last_block = 0
    else:
        old_last_block = (LENGTH_HDR_SIZE + (old_total - 1)) // PLAINTEXT_SIZE

    if new_total == 0:
        new_last_block = 0
    else:
        new_last_block = (LENGTH_HDR_SIZE + (new_total - 1)) // PLAINTEXT_SIZE

    # --- Step 1: Re-encrypt the new last block with updated content ---
    # The length header in block 0 must be updated, and any bytes beyond
    # the new data boundary in the new last block are replaced with fresh
    # randomness. This is done via a genuine re-encryption.
    # IMPORTANT: encrypt_session_data_block (§11.2) updates ALL sessions
    # at this block index — genuine for the active session, rerandomized
    # or cover for every other session.

    try:
        pt = bytearray(decrypt_session_data_block(domain, session, new_last_block))
    except:
        pt = bytearray(rand(PLAINTEXT_SIZE))

    # Update length header if this is block 0
    if new_last_block == 0:
        pt[0:LENGTH_HDR_SIZE] = u64_be(new_total)

    # Randomize the unused tail of this block
    new_data_end_pos = LENGTH_HDR_SIZE + new_total
    block_start_pos = new_last_block * PLAINTEXT_SIZE
    tail_start = new_data_end_pos - block_start_pos
    if tail_start < PLAINTEXT_SIZE:
        pt[tail_start:PLAINTEXT_SIZE] = rand(PLAINTEXT_SIZE - tail_start)

    encrypt_session_data_block(domain, session, new_last_block, bytes(pt))

    # If block 0 was not the new last block, also update block 0's length header
    if new_last_block != 0:
        try:
            pt0 = bytearray(decrypt_session_data_block(domain, session, 0))
        except:
            pt0 = bytearray(rand(PLAINTEXT_SIZE))
        pt0[0:LENGTH_HDR_SIZE] = u64_be(new_total)
        encrypt_session_data_block(domain, session, 0, bytes(pt0))

    # --- Step 2: Convert fully freed blocks into cover blocks ---
    # Blocks (new_last_block+1) through old_last_block are no longer needed
    # by this session. Replace them with fresh cover blocks so they are
    # indistinguishable from blocks allocated by any other session.
    # IMPORTANT: Every session's block at each freed index must be updated.
    # The active session gets a cover block; all other sessions get
    # rerandomized. This ensures snapshot diffs at freed indices look
    # identical to diffs from normal writes or cover traffic.

    for b in range(new_last_block + 1, old_last_block + 1):
        for cur_i in shuffle(range(SESSION_COUNT)):
            cur_version, cur_pk = read_session_version_and_pk(cur_i)
            cur_aad_root = (domain + ":bordercrypt" +
                            f":session:v{cur_version}:i{cur_i}:b{b}")

            if cur_i == session["session_index"]:
                # Replace with a cover block (no longer genuine for this session)
                new_ct = create_cover_block(cur_pk, cur_aad_root)
            else:
                # Rerandomize other sessions' blocks as usual
                try:
                    cur_ct = read_session_block(cur_i, b)
                    new_ct = rerandomize_block(cur_pk, cur_ct)
                except:
                    new_ct = create_cover_block(cur_pk, cur_aad_root)

            write_session_block(cur_i, b, new_ct)
            fsync_session_blocks_file(cur_i)

14.4 Interaction with writes

write_session_data (§13) may also implicitly shrink the session when combined with application-level truncation. Implementations should call shrink_session_data whenever the application reduces its logical data size, rather than only when explicitly deleting data. In particular, if write_session_data is called with a range that implies a smaller total, the caller should follow up with a shrink to reclaim the tail blocks.

14.5 Snapshot-resistance properties

After a shrink operation:

• The global blockstream length is unchanged — no blocks are removed from any session file.
• The freed blocks for the active session are now fresh cover blocks, cryptographically indistinguishable from cover blocks that might have been created during an allocation by a different session.
• Every block index touched during the shrink was updated across all sessions. The active session's freed blocks became cover blocks; every other session's blocks at those same indices were rerandomized. In a snapshot diff, each affected index shows changes in all session files — exactly as it would during a normal write, extension, or cover traffic tick. There is no per-session asymmetry in the diff that could identify the shrinking session.
• An adversary comparing two snapshots sees that some blocks changed (as expected from cover traffic, writes, or rerandomization) but cannot determine whether the change represents deallocation by the unlocked session or continued use by another session.
• The unlocked session's length header reflects the new, smaller size. From the adversary's perspective with knowledge of only that session's password, the extra blocks beyond the session's data are equally consistent with (a) the session having previously been larger, or (b) another session having allocated those blocks.

---

15. Cover traffic

At random intervals, perform public rerandomization of random block indices across all sessions.

Algorithm:

1. Choose block_index uniformly at random from [0, global_block_count).

2. For each session in randomized order:

   • Read current block ciphertext.
   • Replace it with pq_rerand.rerand(pk, ciphertext).
   • If rerandomization fails (missing/corrupt block), replace with a fresh cover block.

def cover_traffic_tick(domain):
    repair_blockstream_lengths(domain)
    global_count = get_global_block_count()
    if global_count == 0:
        return

    block_index = rand_u64() % global_count

    for cur_i in shuffle(range(SESSION_COUNT)):
        cur_version, cur_pk = read_session_version_and_pk(cur_i)
        cur_aad_root = (domain + ":bordercrypt" +
                        f":session:v{cur_version}:i{cur_i}:b{block_index}")

        try:
            cur_ct = read_session_block(cur_i, block_index)
            new_ct = rerandomize_block(cur_pk, cur_ct)
        except:
            new_ct = create_cover_block(cur_pk, cur_aad_root)

        write_session_block(cur_i, block_index, new_ct)
        fsync_session_blocks_file(cur_i)

---

16. Session lifecycle

16.1 Initial provisioning

For each session slot i:

• Generate a pq-rerand keypair (pk_i, sk_i) and store pk_i in cleartext in its keypair file.
• Store sk_nonce and sk_ct as random bytes (so the slot is not unlockable by any password).
• Create empty blockstream files (length 0) or a uniform initial length depending on product requirements.

16.2 Allocating (creating) a session

To create a session for a user password:

• Choose a free slot i.
• Write a new pq_pk for that slot and AEAD-wrap its pq_sk using the password-derived sk_wrap_key.
• This operation is not plausibly deniable due to the public key change in the keypair file.

16.3 Unlocking a session

Unlocking attempts to decrypt each slot’s wrapped pq_sk using the derived sk_wrap_key. Exactly one slot should succeed for a correct password.

---

17. Operational considerations

1. Atomicity and crash consistency
   write_session_block should be atomic at block granularity, or implemented with journaling. fsync (or platform equivalent) should be used to reduce the window in which snapshots can capture partially updated blocks.

2. Randomized multi-session update order
   All multi-session updates (writes, extensions, cover traffic) must update session files in a randomized order each time to reduce correlation if snapshots occur mid-operation.

3. Error handling

   • Reads for an unlocked session must fail on AEAD authentication failure (corruption detection).
   • Writes treat unreadable prior blocks as random bytes and proceed, maintaining indistinguishability and forward progress.
   • Rerandomization failures heal by writing fresh cover blocks.

4. Side-channel hygiene
   Ensure cryptographic operations do not expose distinguishable errors. Avoid timing side-channels in AEAD verification and key handling where possible.

5. Memory hygiene
   Zeroize derived keys and plaintext buffers when feasible.