PGS - Pepperword Generation Standard

Revision 1.6.0 · Stable · 2026-07-06

Published by: Pepperword License: CC BY 4.0; patent rights reserved (see Copyright and License)

Abstract

The Pepperword Generation Standard (PGS) specifies a deterministic password derivation protocol. Given an entropy source, a passphrase, and per-site metadata, PGS deterministically derives a credential string. No passwords are stored. The same credential is always recoverable from the same inputs.

This document is the normative specification for PGS v1.6.0. It is intended for security researchers and auditors reviewing the protocol design, and for implementors who have licensed the patent.

Terminology

Min-entropy. The min-entropy of a random variable X is H∞(X) = −log₂(max_x P(X = x)). It measures worst-case predictability: an adversary who optimally guesses X succeeds with probability 2^(−H∞(X)).

NE_SIZE. The named constant NE_SIZE = 4128, the number of 32-byte blocks in NE for this version. Versioning rules in §4.2.

Entropy Source (ES). The byte string supplied by the user as the secret entropy input, typically the contents of a single file (combining multiple files into one byte string is the caller's responsibility, §1.2). Must be strictly greater than NE_SIZE × 32 bytes (132,096 bytes). See §4.1 for selection guidance.

Normalized Entropy (NE). The array of NE_SIZE 32-byte blocks produced by Normalize from the entropy source, denoted NE[0..NE_SIZE-1]. Never stored.

Pepper. A 32-byte value derived from NE and a target identifier. Serves as the HMAC key in pepperword generation. Target-specific within a user's NE.

Pepper Pool. Blocks NE[0] through NE[4095]: the first 4096 blocks of NE. A pepper is selected from this pool by hash-based index lookup.

Target Identifier (targetId). A canonical string identifying a relying application, derived from its URL by the normalization algorithm in §5.1. Format: the registrable domain for PSL-known domain names; otherwise an IPv4 literal or the normalized host name.

App URL (appURL). The canonical URL identifying the relying app; the default input to §5.1 targetId derivation (a caller may instead derive from a synthetic derivation URL, see §5.1).

Passphrase. The user's secret string.

Creation Timestamp (creationTimestamp). A uint64 Unix timestamp in milliseconds. Set when an app entry is first created; updated on each password rotation.

Human Passphrase Material (HPM). The byte string constructed as:

HPM = uint64_be(creationTimestamp) || UTF8(NFC(passphrase))

Pepperword. The derived credential string produced for a specific (user, target, creationTimestamp, policy) tuple. Satisfies the app's password policy. Never stored by PGS.

Entropy ID (entropyID). A 24-character lowercase base32 identifier derived from NE[4098] (the identity block). Uniquely identifies a PGS entropy instance. See §7.

Profile ID (profileID). A 6-character human-readable label: the first 6 characters of entropyID. See §7.

1. Introduction

1.1 Background

PGS addresses a specific problem: users need strong, unique passwords per site, but cannot remember dozens of them. A password manager solves this by storage. PGS solves it by derivation: the password is recomputed on demand from a secret the user already holds (a personal file and a passphrase), never stored anywhere.

The derivation is deterministic and site-specific. Compromise of one derived credential does not expose credentials for other sites.

Recovery requires the two user-held secrets plus per-site metadata that cannot be memorized and must be stored. See §8.11 for custody requirements.

1.2 Scope

This document specifies:

• The three-phase derivation pipeline (Normalize, GeneratePepper, GeneratePepperword)
• The HPM construction and password rotation mechanism
• The password policy representation (composition, compositionPattern, prefix, postfix)
• The Entropy ID derivation algorithm (§7) and the NE block assignments it depends on
• Security properties and threat model
• Test vectors sufficient to verify any conforming implementation

This document does not specify:

• How the entropy source is selected, stored, or transported
• How multiple files are combined into a single entropy source byte string (caller's responsibility)
• How the target identifier is presented to users
• Cloud synchronization or any persistence layer

1.3 Protocol Stability and Versioning

Version Format

PGS versions follow MAJOR.MINOR.PATCH. The current version is 1.6.0.

Callers persist the MAJOR.MINOR string (e.g. "1.6") as the protocol-version axis for an entry. PATCH changes do not update this stored value; they are transparent to all clients.

What Is Frozen (MAJOR boundary)

Any change that produces different output for existing inputs requires a MAJOR bump. The non-obvious boundaries:

• NE block contents or assignments at indices 0..NE_SIZE-1, or a decrease in NE_SIZE
• The target identifier normalization algorithm (§5.1)
• The Entropy ID derivation algorithm (§7)

Major bump warning (non-normative). A PGS major bump invalidates the derivation namespace for every stored credential. Even if old metadata is retained, the same entropy source, passphrase, targetId, creationTimestamp, and policy can no longer be assumed to reproduce the user's existing passwords under the new major. For a production password manager, this is effectively product-ending unless paired with an explicit per-entry migration in which every relying service password is changed. PGS v2 SHOULD be treated as an exceptional last resort, not a routine upgrade path.

What Is Additive (MINOR bump)

A MINOR bump is used for:

• New optional policy fields, provided absent fields have a fully-specified default that preserves existing output
• New reserved NE block assignments beyond the current layout
• New normative test vectors
• New formally-specified derivation algorithms that use previously-reserved NE blocks (as in this version for Entropy ID)

Any new optional field in a PGS minor revision that affects derivation MUST define absent-field semantics that are identical to the previous minor revision. An older client that does not know the field and therefore omits it from the derivation MUST produce the same output that a newer client produces when the field is absent. A new field MUST NOT reinterpret an absent value as "use the new behavior."

Derivation-Affecting MINOR Pattern

Some MINOR revisions affect only future entries, not existing stored entries, because the calling system stores the exact derivation inputs for each credential. A future MINOR revision may change how new target identifiers or other derivation inputs are constructed, but only when the constructed value is stored before it is used for derivation. Existing entries continue to derive from their frozen stored inputs.

A future MINOR revision that changes how new derivation inputs are constructed MUST follow the same pattern:

• The constructed value used for derivation MUST be stored per entry or per history record before it is used.
• Existing stored values MUST NOT be recomputed, rewritten, or reinterpreted by the new minor.
• Opting into the new behavior MUST be explicit at the calling system / app layer, normally by creating a new entry or rotating in a way that stores a complete new derivation snapshot.
• Deriving an existing entry MUST use the frozen stored inputs, not the current client's preferred construction algorithm.

Client Compatibility

PGS defines derivation behavior, not file mutability or version-compatibility policy. How a calling system handles entries that advertise a PGS major or minor version higher than the client supports is a custody-layer concern outside PGS scope.

PATCH differences are transparent. PATCH changes never update the persisted MAJOR.MINOR string and never change derivation output.

Implementations conforming to v1.6.0 are guaranteed to produce identical pepperwords for any inputs whose fields are defined in v1.6.0. A future v1.x.y minor revision MAY add new optional derivation-affecting fields, but per the absent-field rule in "What Is Additive" above, an absent field MUST keep the v1.6.0 derivation behavior, so v1.6.0 implementations remain forward-compatible for inputs that do not exercise the new fields.

2. Conventions

2.1 Key Words

The key words MUST, MUST NOT, REQUIRED, SHALL, SHALL NOT, SHOULD, SHOULD NOT, RECOMMENDED, NOT RECOMMENDED, MAY, and OPTIONAL in this document are to be interpreted as described in [RFC 2119] when they appear in all capitals.

2.2 Notation

|| denotes byte string concatenation.

x[i:j] denotes the bytes of x at indices i (inclusive) through j (exclusive).

0xNN denotes a single byte with the given hexadecimal value.

len(x) denotes the length of byte string x in bytes.

All integers are unsigned unless otherwise noted.

Strings are encoded as UTF-8 bytes unless otherwise noted.

2.3 Cryptographic Primitives

2.4 BigInteger Encoding

A byte string b of length n encodes an unsigned integer in big-endian byte order:

BigInt(b) = b[0]·256^(n-1) + b[1]·256^(n-2) + ... + b[n-1]·256⁰

b[0] is the most significant byte; b[n-1] is the least significant byte. This is the standard convention used by all major big-integer libraries (int.from_bytes(b, 'big') in Python, new BigInteger(1, b) in Java, new(big.Int).SetBytes(b) in Go). Java's single-argument constructor new BigInteger(b) interprets the byte string as signed two's-complement and produces a different value when the high bit of b[0] is set; implementations MUST NOT use it.

2.5 Base32 Encoding

base32_lowercase(x) denotes RFC 4648 base32 encoding with the lowercase alphabet (a–z, 2–7). No padding characters are emitted. GenerateEntropyID in §7 uses this encoding.

2.6 String Normalization

All Unicode strings used as derivation inputs MUST be normalized to Unicode Normalization Form C (NFC) before any further processing (UTF-8 encoding, len(...) computation, character indexing, or regex matching). This rule applies to:

• passphrase in HPM construction (§6.1).
• Each charSet C in a composition unit (§6.2).
• prefix and postfix strings (§6.2).
• The compositionPattern regular expression source (§6.2).
• Any literal string carried in caller-supplied policies that PGS treats as a derivation input.

After NFC normalization, strings are interpreted as sequences of Unicode scalar values. len(s) is the number of Unicode scalars in s. s[i] is the i-th scalar (0-indexed). Concatenation operates on scalars. UTF-8 encoding (where required) operates on the post-NFC scalar sequence. Implementations MUST NOT use UTF-16 code units, byte indexing, or grapheme clusters for derivation-input length and indexing.

targetId is exempt from this rule because it is an output of §5.1 normalization, which already produces a canonical lowercase ASCII (or IDNA-encoded ASCII) string. entropyID is also exempt for the same reason (base32 lowercase ASCII).

NFC itself has a living input: the implementation's Unicode database, the same drift shape as the [PSL] in §5.1 and category assignment in §6.2. Unicode's normalization stability policy guarantees that the NFC output of a string containing only assigned scalars never changes in later Unicode versions, so this drift can affect only strings containing unassigned (Cn) scalars. Composition charSets already reject unassigned scalars at construction (§6.2). Passphrases have no such gate; implementations MAY reject unassigned scalars in passphrases at entry time to close this residual drift.

The string-normalization rule is part of the major-frozen surface (§1.3): changing it would silently break all existing pepperwords for non-ASCII inputs.

3. Protocol Overview

  Entropy Source (> NE_SIZE × 32 bytes = 132,096 bytes)
          │
          ▼
  ┌───────────────┐
  │  Normalize()  │
  └───────┬───────┘
          │  NE: NE_SIZE × 32-byte blocks
          │
          ├──── NE[4098] ──────▶ ┌────────────────────┐
          │                      │  GenerateEntropyID │  ──▶  entropyID (24-char)
          │                      └────────────────────┘
          │
          │                       targetId (external)
          │                              │
          ▼                              ▼
  ┌─────────────────────────────────────────┐
  │             GeneratePepper()            │
  └────────────────────┬────────────────────┘
                       │  pepper (32 bytes)
                       │
                       │       HPM (external)   policy (external)
                       │              │                 │
                       ▼              ▼                 ▼
  ┌─────────────────────────────────────────┐
  │           GeneratePepperword()          │
  └────────────────────┬────────────────────┘
                       ▼
               pepperword (string)

Phase 1 (Normalize): The entropy source is passed through SHAKE-256. The output is sliced into NE_SIZE 32-byte blocks.

Phase 2 (GeneratePepper): A target-specific 32-byte pepper is derived from NE using two fixed-index seed blocks (eb1 = NE[4096], eb2 = NE[4097]) and a hash-based index lookup over a 4096-slot pool.

Phase 3 (GeneratePepperword): The pepper is combined with the user's HPM via HMAC-SHA-512. The output drives a composition encoder and a Fisher-Yates permutation loop to produce a credential string satisfying the policy.

Entropy ID (GenerateEntropyID): entropyID (24-character) is derived from NE[4098] (the identity block). It identifies the entropy source instance and is usable independently of the pepperword derivation pipeline.

4. Phase 1: Entropy Normalization

4.1 Normalize

Assumption (ES-min-entropy). H∞(ES) ≥ NE_SIZE × 256 bits. This assumption holds when two conditions are jointly satisfied:

1. High entropy density. The file contains sufficient unpredictable content that its min-entropy meets the threshold.

1. Secrecy. The specific file is known only to the user. An attacker who knows the protocol and the size of ES cannot concentrate probability mass on any particular ES value.

Neither condition alone is sufficient. A publicly known file satisfies (1) but not (2); H∞(ES) ≈ 0 from the attacker's view. A secret but highly compressible file satisfies (2) but not (1); H∞(ES) may fall below the threshold.

Goal. Given Assumption ES-min-entropy, deterministically expand ES into NE such that each NE[i], and any tuple of NE blocks, is computationally indistinguishable from a uniform random string of the same length to a feasible attacker for whom ES remains unpredictable. A file of exactly NE_SIZE × 32 bytes is rejected: no real file achieves min-entropy rate 1.0, so the exact floor cannot satisfy the assumption. Files must strictly exceed this size; it does not independently certify entropy content.

Recommendation (non-normative). A photo captured by the user's own camera (JPEG, HEIC, or similar) is a suitable entropy source. What qualifies it is provenance, not format or size. A genuine capture contains per-pixel sensor noise that survives compression; that noise is physically random at capture time and cannot be reconstructed by an attacker, even one holding a visually identical photo of the same scene. This satisfies condition (1). A downloaded, screenshotted, or generated image may be equally large and equally incompressible, yet have no min-entropy at all if the attacker can locate the same bytes; size and format never substitute for condition (2). A typical smartphone photo is 2–10 MB, far above the 132 KB floor; the floor is an eligibility rule, not evidence that Assumption ES-min-entropy holds (see §8.3). Callers MAY enforce a larger minimum; PGS enforces only the floor.

Normalize(ES) -> NE[0..4127]

  Inputs:
    ES       byte string (entropy source)

  Output:
    NE       array of NE_SIZE 32-byte blocks

  Steps:
    MUST abort if len(ES) <= NE_SIZE × 32       // protocol size floor for Assumption ES-min-entropy;
                                                // not a SHAKE-256 constraint (SHAKE-256 accepts any
                                                // input size). callers MAY enforce a higher minimum.
                                                // see §4.1 recommendation for guidance on file selection.

    output = SHAKE-256(ES, NE_SIZE * 32)

    For i in 0..NE_SIZE-1:
      NE[i] = output[i*32 : (i+1)*32]

SHAKE-256 is an eXtendable Output Function (XOF): it absorbs all of ES before squeezing an arbitrary-length pseudorandom output. Each output block is a deterministic function of the final Keccak state, so no single region of the source is responsible for any single NE[i]. Under Assumption ES-min-entropy, and modeling SHAKE-256 as a random oracle up to the usual Keccak query bounds, the output is computationally indistinguishable from a uniform string of the same length to any feasible attacker for whom ES remains unpredictable. Any individual 32-byte block, or tuple of blocks, is correspondingly pseudorandom to such an attacker. This is a computational, ROM-style claim, not a leftover-hash-lemma extractor claim and not a statistical one: the blocks are deterministic functions of ES and are not independent entropy sources, and an attacker who knows ES learns the entire NE.

4.2 NE Block Layout

NE_SIZE is a named constant. Protocol versioning is not stored in NE; NE is recomputed on demand from the entropy source, and the algorithm version is determined by the implementation. Version information is stored by the calling system.

eb3 and eb4. v1.6 formally names and assigns these two blocks. eb3 (NE[4098]) is the sole input to Entropy ID derivation. eb4 (NE[4099]) is assigned to the custody layer for encryption-key derivation; its exact use is specified outside this document. Neither assignment affects existing pepperword derivation: the pepper pipeline uses only blocks 0–4097.

Future extensibility. Because SHAKE-256 produces a sequential byte stream, SHAKE-256(ES, N*32)[0:NE_SIZE*32] is identical regardless of N. A future protocol version that defines blocks beyond index NE_SIZE-1 can generate a larger output without affecting any existing block indices. The 28 reserved blocks (4100–4127) are a layout declaration for this version only, not a capacity limit.

5. Phase 2: Pepper Derivation

5.1 Target Identifier

The target identifier is a canonical string derived from the URL the credential authenticates against. It MUST be identical across all derivations for the same credential (see persist-and-freeze later in this section for one specific source of drift).

Credential URL selection. Callers SHOULD choose the URL for the account system that validates the credential, not necessarily the product page or the first URL in the login flow. For example, if signing in to https://www.youtube.com/ uses the Google Account credential at https://accounts.google.com/, derive targetId from https://accounts.google.com/. Once selected, the resulting targetId MUST remain stable across every derivation for that credential. How a caller persists that value is outside this document's scope.

Normalization algorithm: The DeriveTargetId(url) function below produces the canonical targetId for a URL. Every targetId MUST be the output of DeriveTargetId for some URL chosen by the caller at credential creation (the derivation URL, normally the credential URL above); there is no other way to construct one. A caller that needs a custom identifier chooses a custom derivation URL (see the single-label discussion below). Afterward, the stored value is what governs derivation.

DeriveTargetId(url) -> targetId

  This algorithm is self-contained: it relies on no external URL or
  internationalized-domain standard, only on the Public Suffix List [PSL] as a
  data input (see Persist-and-freeze). Hosts are restricted to ASCII; an
  internationalized domain MUST be supplied in its A-label ("xn--") form
  [RFC 5890].

  Accepted shape (the scheme is matched case-insensitively) [RFC 5234]:

       input      = scheme "://" authority [ "/" *char ] [ "?" *char ] [ "#" *char ]
       scheme     = "http" / "https"
       authority  = host [ ":" port ]
       port       = 1*DIGIT

  The shape is descriptive; the numbered steps are normative wherever the
  two could be read to differ: "char" is any code point (path, query, and
  fragment are read and discarded unvalidated); step 1's quoted scheme
  literals are matched case-insensitively; the port-0 check compares the
  port's numeric value (":000" aborts); and the [RFC 1035] citation in
  step 5b imports label character syntax only, not any label-length limit.

  1. MUST abort if the input does not begin with "http://" or "https://".
     Let authority be the characters after "://" up to the first "/", "?", or
     "#" (or end of input). MUST abort if authority is empty or contains "@"
     (userinfo unsupported) or "[" or "]" (IP-literal hosts, including IPv6,
     unsupported). The path, query, and fragment are read and discarded, with
     no percent-decoding.

  2. Split authority at its first ":" into host and port; if there is no ":",
     host = authority and there is no port. If a port is present it MUST be a
     non-empty run of ASCII digits (else abort) and MUST NOT be 0 (else abort);
     the port is otherwise discarded.

  3. Map each ASCII uppercase letter in host (U+0041..U+005A) to lowercase.
     MUST abort if host contains any code point outside U+0021..U+007E (this
     rejects non-ASCII hosts, control characters, and spaces).

  4. If host ends with U+002E ("."), strip exactly one trailing dot. MUST abort
     if host is then empty.

  5. Compute hostOut:

     a. IPv4 literal. If host is an IPv4address [RFC 3986], i.e. exactly four
        decimal octets each 0..255 separated by ".", then hostOut = host. The
        PSL lookup does not apply; IP addresses have no registrable domain.

     b. Domain name. Otherwise host MUST be a sequence of "."-separated labels
        in which every label is non-empty, contains only ASCII letters, digits,
        and hyphen, and neither begins nor ends with a hyphen (preferred name
        syntax, [RFC 1035] §2.3.1 as updated by [RFC 1123] §2.1); MUST abort
        otherwise. Look up the registrable domain via the [PSL] algorithm,
        treating public (ICANN) and private entries identically. The [PSL]
        algorithm's implicit default rule ("*") is not used: only explicit
        list entries match (including their wildcard and exception rules), so
        a host under an unknown TLD matches no public suffix. Three cases:
          - host is exactly a public suffix (e.g. "com"): MUST abort.
          - a public suffix matches: hostOut = registrable domain (the matched
            suffix plus one more label).
          - no public suffix matches (single-label host or unknown TLD):
            hostOut = host.

  6. Return hostOut.

The scheme (beyond the http/https check) and the port (beyond the port-0 check) are not otherwise used. A-labels pass through as opaque ASCII labels and are not validated as Punycode, so an unknown or malformed xn-- label becomes its own namespace rather than an error.

Single-label and IP hosts. A single-label host such as localhost or intranet matches no public suffix and passes through unchanged (step 5b), so all scheme and port variants share one credential: http://localhost:3000 and http://localhost:8080 both yield localhost. An IPv4 host collapses the same way: http://192.168.1.1 and https://192.168.1.1:8443 both yield 192.168.1.1. If distinct local applications need distinct credentials, the caller derives them from distinct synthetic hosts: http://service-a.localhost and http://service-b.localhost yield the distinct identifiers service-a.localhost and service-b.localhost. How a caller surfaces this choice is a custody-layer concern.

Credential namespace. Because scheme and port are discarded, http://example.com, https://example.com, and https://example.com:8080 all normalize to example.com and share the same credential. This is by design: a user expects the same password across scheme and port variants of the same site. See §8.1 for the full security discussion.

Examples:

Inputs that MUST abort:

Implementation note (non-normative). This algorithm is platform-independent and uses no platform URL parser or IDNA library. Implement it directly with string operations over the input. Because the accepted input is a small, fully specified grammar and everything outside it aborts, the §9.5 vectors fully pin the parser behavior and the specific registrable-domain reductions they list; reduction of other hosts depends on the PSL snapshot (see Persist-and-freeze). Implementations MUST NOT delegate parsing to a general-purpose URL library such as Foundation.URL or a WHATWG URL parser, whose edge-case handling is neither identical across platforms nor guaranteed to match this algorithm.

When a caller constructs a new identifier and needs to validate a candidate targetId directly (for example, a custom identifier typed as a string rather than derived from a URL), the check is: v is a possible targetId iff DeriveTargetId("https://" || v) returns exactly v. The function's outputs are precisely its fixed points under a given PSL snapshot, so this accepts every derivable identifier and rejects everything else (non-ASCII, uppercase, trailing dots, ports, subdomains of PSL-known registrable domains). The check applies only when creating a new identifier. A stored targetId is never re-validated: the fixed-point set varies with the PSL snapshot, so a frozen value can fail the check under a later snapshot while remaining the correct derivation input (see Persist-and-freeze).

Changing this normalization rule is a breaking change: it produces different peppers and therefore different pepperwords for all existing users.

Persist-and-freeze. DeriveTargetId has one living external input: the Public Suffix List [PSL], which evolves over time. Two implementations bundling different PSL snapshots, or one implementation before and after a PSL update, may compute different registrable domains for the same host (for example when a new public suffix is added). To prevent silent cross-device divergence:

• Callers MUST persist the DeriveTargetId output (computed from the chosen derivation URL) at the moment the entry is created (or its first password derivation, whichever is earlier) and use that stored value for every subsequent derivation, including all rotation history records.
• Callers MUST NOT recompute or re-validate targetId for an existing record, even if appURL changes or a newer PSL snapshot becomes available. The stored value is treated as opaque from that point forward.
• A minor revision MAY change how new targetId values are constructed (per §1.3 "Derivation-Affecting MINOR Pattern"), but MUST NOT redefine existing stored values.

This drift cannot affect recovery. Deriving any pepperword requires the persisted creationTimestamp, policy, and targetId (§8.11), so every recoverable entry already carries its frozen targetId; a differing PSL snapshot never re-enters the derivation for such an entry. The only path the PSL is a living input on is the one-time construction of a targetId for a new entry. Two implementations that independently create an entry for the same URL under different snapshots may therefore disagree on that first value, but once either value is stored it is authoritative. This standard does not guarantee that independent implementations compute identical targetId values at creation without sharing the stored metadata.

5.2 GeneratePepper

GeneratePepper(NE, targetId) -> pepper

  Inputs:
    NE        array of NE_SIZE × 32-byte blocks (normalized entropy)
    targetId  string (canonical target identifier, UTF-8 encoded)

  Output:
    pepper    32 bytes

  Steps:
    eb1 = NE[4096]
    eb2 = NE[4097]

    h   = SHA-256(UTF8(targetId) || eb1)
    idx = BigInt(h) mod 4096         // result in [0, 4095]

    pepper = SHA-256(NE[idx] || eb2)

Index computation. BigInt(h) mod 4096 uses standard big-endian byte order. 2^256 is exactly divisible by 4096 (= 2^12), so the distribution over [0, 4095] is perfectly uniform with zero modular bias.

Role of seed blocks. eb1 functions as a per-user salt for the index computation: two users with the same targetId produce different indices because their eb1 values differ. eb2 functions as a per-user salt for the final pepper hash. Knowledge of eb1 or eb2 alone yields no pepper: eb1 reveals only the slot index for a given targetId, and deriving that target's pepper additionally requires the selected pool block NE[idx] (see §8.2).

Design rationale. PGS does not derive pepper directly from targetId. Instead, targetId selects one block from a per-user pepper pool derived independently of any target. This is deliberate. It keeps the underlying pepper inventory target-agnostic, so implementations can reason about pepper material without embedding the relying app identifier into the pepper derivation itself. The tradeoff is that distinct targets can collide onto the same pool slot. PGS accepts that tradeoff to preserve this separation: target-specificity enters at slot selection, while the underlying pepper material remains independent of any one app.

6. Phase 3: Pepperword Generation

6.1 HPM Construction

Human Passphrase Material (HPM) binds the user's passphrase to an app-specific timestamp:

HPM = uint64_be(creationTimestamp) || UTF8(NFC(passphrase))

creationTimestamp MUST be the Unix timestamp in milliseconds at which this app entry was created, or at which the password was last rotated, encoded as an unsigned 64-bit big-endian integer. Encoding creationTimestamp as an 8-byte big-endian integer makes HPM an injective function of (creationTimestamp, passphrase): distinct input pairs always produce distinct byte strings. The passphrase is normalized to NFC before UTF-8 encoding (§2.6).

creationTimestamp is not secret; it is stored in app metadata and contributes no entropy to HPM. The entropy in HPM comes entirely from passphrase. Within a single app entry, every rotation MUST advance creationTimestamp so that two rotation events of the same entry can never share a timestamp. Across distinct entries, two entries that happen to share (targetId, passphrase, policy, creationTimestamp) produce identical pepperwords. That is the deterministic-protocol outcome of identical inputs, not a security flaw: the two entries denote the same credential under the same name. Interactive entry creation is unlikely to produce two entries in the same millisecond; bulk-import code paths SHOULD preserve original creation times and avoid clamping to a low-resolution clock.

Example. passphrase = "hunter2", creationTimestamp = 1700000000000:

HPM = uint64_be(1700000000000) || UTF8("hunter2")
    = 0x0000018BCFE56800 68756E74657232

Rotation. When a user rotates the password for a specific app, creationTimestamp is set to a new value (e.g., current time). This changes HPM for that app only, producing a fresh derivation for that app while all other apps remain unchanged (in a small output space such as a PIN, the new value can occasionally equal the old one). Recovering a previous pepperword requires the old creationTimestamp, along with the policy and targetId in effect at that generation (see §8.11). Implementations MAY retain the derivation metadata from each rotation to support recovery of past pepperwords.

6.2 Password Policy

A password policy (policy) is a tuple <composition, compositionPattern, prefix, postfix> that constrains the pepperword output. Each component is defined below.

A composition is an ordered list of units [<C₁, m₁>, ..., <Cₙ, mₙ>]. A composition MUST contain at least one unit. Each unit <C, m> specifies m Unicode scalars drawn from character multiset C. C MUST be non-empty and is an ordered NFC-normalized string interpreted as a sequence of Unicode scalars (§2.6). m MUST be a positive integer. Duplicate scalars increase the probability of that scalar being selected. The total output length is m₁ + ... + mₙ scalars and MUST be no greater than 98 scalars (§6.4). In practice the §6.3 entropy budget binds first for large alphabets: the composition space may not exceed 2^256, which caps effective length around 38 scalars over the 95-character printable-ASCII range.

Examples.

A typical 14-character policy with mixed character classes:

[<"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ", 10>,
 <"0123456789", 2>,
 <"!@#$%^&*", 2>]

The composition-encoded string is 10 letters, 2 digits, and 2 special characters in that order; the final pepperword permutes them (§6.4).

A digit-only PIN of length 6:

[<"0123456789", 6>]

A contrived example of multiset weighting (8 characters drawn from "aaab"):

[<"aaab", 8>]

Because 'a' appears 3 times in C, each position selects 'a' with probability ¾ and 'b' with probability ¼.

A compositionPattern is a regular expression using a normative subset of RE2 syntax [RE2] matched against the permuted core returned by Permute (§6.4). A match is an unanchored substring match: the pattern succeeds if it matches anywhere within the core string. To require a full-string match, use ^ and $ anchors explicitly. To impose no positional constraint, use .*. An absent compositionPattern defaults to .*.

Grammar (normative). After NFC normalization (§2.6), the pattern source MUST match the pattern rule below ([RFC 5234], interpreted over Unicode scalars rather than octets). A pattern that does not match this grammar, or that violates any constraint that follows it, MUST be rejected at policy construction time. The grammar is a strict subset of RE2 syntax [RE2], chosen so that every construct it admits behaves identically in every conforming regex engine.

pattern       = alternation
alternation   = concat *( "|" concat )
concat        = *piece                    ; empty concat matches the empty string
piece         = anchor / ( atom [ quantifier ] )
anchor        = "^" / "$"                 ; anchors take no quantifier
atom          = literal / escape / "." / class / group
group         = "(" alternation ")"
literal       = <any Unicode scalar except reserved>
reserved      = "\" / "." / "[" / "]" / "(" / ")" / "{" / "}"
              / "*" / "+" / "?" / "|" / "^" / "$"
escape        = "\" punct                 ; denotes punct literally
punct         = %x21-2F / %x3A-40 / %x5B-60 / %x7B-7E    ; ASCII punctuation
quantifier    = "*" / "+" / "?" / counted
counted       = "{" count [ "," [ count ] ] "}"     ; {n}, {n,}, {n,m}
count         = "0" / ( %x31-39 [ DIGIT ] )         ; canonical decimal
class         = "[" [ "^" ] class-items "]"
class-items   = "-" *class-item [ "-" ]   ; "-" at a class edge is a literal
              / 1*class-item [ "-" ]
class-item    = class-atom [ "-" class-atom ]       ; scalar or inclusive range
class-atom    = escape / class-literal
class-literal = <any Unicode scalar except "\" / "[" / "]" / "-">

Constraints. Each of the following MUST hold, checked at policy construction:

• Every count value is at most 98 (the maximum core length, §6.4), and in {n,m} form n ≤ m. Counts are canonical decimal with no leading zeros (the count rule): a{01} is rejected, a{0} is not. The 98 bound also stays far below the repetition limits where engines diverge (RE2 rejects counts above 1000; ICU accepts them).
• In a range class-atom "-" class-atom, the first atom's scalar value is less than or equal to the second's: [z-a] is rejected.
• A class MUST NOT contain two adjacent unescaped - scalars. Together with the grammar this rejects every set-subtraction spelling, including [a--b].
• A class MUST NOT contain two adjacent unescaped & scalars (&& is ICU set intersection). A single & is a literal, so [!@#$%^&*] remains valid.

Semantics. A literal, class-literal, or escape matches exactly its scalar (an escape denotes the escaped punctuation scalar itself). . matches any single scalar except U+000A. A class matches one scalar contained in the union of its atoms and ranges, where a range lo-hi denotes all scalars from lo through hi inclusive by scalar value; a negated class [^...] matches one scalar not in that union. A ^ outside a class matches at the start of the core and $ at its end (the alphabet rule below makes line-mode ambiguity unreachable); a ^ inside a class is negation only as the first scalar after [, and a literal elsewhere. Quantifiers bind to the immediately preceding atom: * is zero or more, + one or more, ? zero or one, {n} exactly n, {n,} at least n, {n,m} between n and m inclusive. | is alternation; (...) groups. Quantifiers are greedy, but only match existence is observable (§6.4 tests whether a match exists, never where), so greediness cannot affect derivation. Matching operates over Unicode scalar positions; implementations MUST NOT match by UTF-16 code unit or by byte.

Everything outside this grammar MUST be rejected at policy construction. This excludes, among others: letter and digit escapes (\d, \w, \s, \n, and backreferences such as \1), Unicode property escapes (\p{...}), POSIX classes ([[:alpha:]]), nested classes, class set operations (&&, --), group modifiers and inline flags ((?:...), (?i), named groups), lazy and possessive quantifiers (a*?, a*+), word boundaries (\b), and quoting (\Q...\E).

Alphabet. Every scalar in every composition charSet (and therefore in the permuted core) MUST be an assigned Unicode scalar whose general category is not Cc (Control), Cf (Format), Zl (Line_Separator), or Zp (Paragraph_Separator); a charSet containing such a scalar, or an unassigned (Cn) scalar, MUST be rejected at policy construction. The Cc/Zl/Zp exclusion removes the only in-subset operators on which engines disagree: . (which excludes additional line terminators under ICU) and the anchors ^/$ (whose end-of-line behavior differs) become unambiguous because the core never contains a line terminator. The Cf and Cn exclusion makes "printable" precise: invisible format characters such as zero-width joiners and directional marks are not permitted. Category assignment is evaluated against the implementation's own Unicode database. A scalar that a newer Unicode version assigns may therefore be accepted by an up-to-date implementation and rejected (as Cn) by an older one. This affects only whether such a charSet is accepted at construction, not the match semantics or derived password of an accepted policy: matching in this subset never consults the category database (there is no \p{...}), and the line-terminator scalars on which ./^/$ depend have fixed categories across all Unicode versions. This is the same shape of living-input drift as the [PSL] in §5.1, resolved the same way: documented, not pinned.

Within this subset and over this alphabet, every conforming engine produces identical match results, so compositionPattern matching is reproducible across independent implementations. There is no out-of-subset behavior left to be implementation-defined: implementations MUST reject anything outside the subset at construction. This reproducibility comes from the engine-agnostic subset, not from persistence: the stored compositionPattern is pattern text that is re-matched on every derivation, so freezing it does not by itself freeze the matching semantics — only the subset restriction does.

Pattern vectors (normative). Implementations MUST accept each of these patterns at policy construction:

One further accepted vector is stated outside the table to avoid the table's column delimiter: the pattern ^([0-9]|[a-f]){2,14}$ — grouping, alternation, and counted repetition — MUST be accepted. (The | here is the alternation metacharacter, not an escaped literal.)

Implementations MUST reject each of these patterns at policy construction:

A prefix is a fixed string prepended to the permuted core. A postfix is a fixed string appended to it. Both default to "". The final pepperword is prefix || core || postfix. Prefix and postfix are NFC-normalized (§2.6); they are caller-supplied literals, not permuted and not matched by compositionPattern. A compositionPattern therefore matches the core only.

6.3 CompositionEncode

CompositionEncode consumes 256 bits of input entropy and produces a fixed-length string whose characters are drawn from the policy's composition. Its output is the pre-permutation core of the pepperword (see §6.4 for permutation and §6.5 for the full pipeline).

CompositionEncode(comp, h) -> string

  Inputs:
    comp   ordered list of units [<C₁,m₁>, ..., <Cₙ,mₙ>]
    h      32 bytes

  Output:
    string of length m₁ + m₂ + ... + mₙ satisfying the composition

  Steps:
    // bits_needed = ceil(m₁·log₂|C₁| + m₂·log₂|C₂| + ... + mₙ·log₂|Cₙ|)
    // Conceptually: abort if bits_needed > 256.
    // Written in integer form below to avoid floating-point divergence:
    MUST abort if |C₁|^m₁ · |C₂|^m₂ · ... · |Cₙ|^mₙ > 2^256

    q      = BigInt(h)
    result = ""

    For i = 1 to n:
      unit_str, q = CompositionUnitEncode(Cᵢ, mᵢ, q)
      result = unit_str || result    // prepend: iterating forward but prepending means
                                     // unit n's characters occupy the first positions in output,
                                     // unit 1's characters occupy the last positions.

    Return result

CompositionEncode treats h as a base-|Cᵢ| big-integer digit stream, drawing one character per output position from the corresponding unit's multiset. The abort check ensures h carries enough entropy to address the composition space; if the composition demands more (e.g., a very long output over a large alphabet), the function aborts. Each unit's characters are prepended to the result, so unit n occupies the leading positions and unit 1 the trailing positions.

CompositionUnitEncode(C, m, q) -> (string, q_remainder)

  Inputs:
    C    character multiset (ordered string, |C| ≥ 1)
    m    positive integer
    q    BigInteger

  Output:
    string of length m; q_remainder is the remaining BigInteger after encoding

  Steps:
    result = ""
    For i = 0 to m-1:
      r      = q mod |C|
      q      = q / |C|      // integer division, truncating toward zero
      result = C[r] || result
    Return (result, q)

6.4 Permute

Permute deterministically shuffles its input string until the result matches compositionPattern. It is the second half of pepperword generation, complementing §6.3 CompositionEncode: that function determines which characters appear; Permute determines where they appear. The shuffle is a Fisher-Yates permutation seeded by ba; if the first permutation does not match, a hash chain reseeds and retries, up to MAX_TRIALS trials in total.

Permute(st, compositionPattern, ba, MAX_TRIALS) -> string

  Inputs:
    st                  string; MUST have len(st) ≤ 98
    compositionPattern  compiled regular expression (matched against the permuted candidate only)
    ba                  32 bytes (permutation entropy)
    MAX_TRIALS          positive integer (fixed at 5000 by §6.5; not caller-tunable)

  Output:
    permuted string matching compositionPattern

  Steps:
    h   = SHA-512(ba)       // 64 bytes
    sum = 0

    While sum < MAX_TRIALS:
      P  = GeneratePermutation(len(st), h)
      s  = string where s[i] = st[P[i]] for i in 0..len(st)-1
      h  = SHA-512(h || UTF8(s))
      sum = sum + 1
      If s matches compositionPattern (unanchored RE2 match): return s

    MUST abort with error "maximum permutation trials exceeded"

The initial SHA-512(ba) step widens the 32-byte (256-bit) input into a 64-byte seed for GeneratePermutation. This is a deterministic expansion, not an entropy increase: the permutation is seeded by the 256 bits of ba, which is the relevant permutation entropy regardless of the 512-bit seed width.

The len(st) ≤ 98 cap follows from the 512-bit seed width: log₂(98!) ≈ 511.5 ≤ 512 < 518.1 ≈ log₂(99!). The cap ensures the 512-bit seed integer can represent every permutation index; it does not make the distribution uniform. The seed carries only 256 bits of entropy, so at most 2^256 of the 98! permutations are reachable, and the modular reduction adds further bias. See §8.8.

MAX_TRIALS rationale. For any reasonable policy, permutations converge quickly: a pattern requiring one character class to appear anywhere succeeds on the first trial; a pattern constraining the first two positions to specific classes has ~3% success probability, converging within ~100 trials on average. MAX_TRIALS = 5000 provides extreme headroom above all realistic policies while still defining a hard failure bound. A higher value would not help a reasonable policy and would only delay failure for a misconfigured or unsatisfiable one. MAX_TRIALS is a fixed protocol constant, not an implementation knob: two implementations with different limits would diverge (password vs abort) on a pattern needing more trials than the lower limit. For given inputs the outcome is deterministic, but a pattern whose per-trial match probability is near 1/MAX_TRIALS can succeed for one entry and abort for another; an abort therefore indicates a defective policy, not a transient error to retry.

GeneratePermutation(n, ba) -> P[0..n-1]

  Inputs:
    n    positive integer (number of elements)
    ba   byte string (≥ ceil(log₂(n!)) bits)

  Output:
    permutation P — a list where {P[0],...,P[n-1]} = {0,...,n-1}

  Steps:
    // bits_needed = log₂(n!) = log₂(n·(n-1)·...·2)
    // Conceptually: abort if bits_needed > len(ba)·8.
    // Written in integer form below to avoid floating-point divergence:
    MUST abort if n! > 2^(len(ba)·8)

    q = BigInt(ba)
    P = [0, 1, 2, ..., n-1]

    For i = n-1 down to 1:
      r    = q mod (i+1)
      q    = q / (i+1)
      swap P[i] and P[r]

    Return P

6.5 GeneratePepperword

GeneratePepperword is the top-level pepperword derivation function. It combines the target-specific pepper (§5.2) with the user's HPM (§6.1) under HMAC-SHA-512, then splits the 64-byte output: 256 bits drive CompositionEncode (§6.3) to fix which characters appear, and 256 bits drive Permute (§6.4) to fix where they appear. The result is wrapped with prefix and postfix to produce the final pepperword.

GeneratePepperword(pepper, passphrase, creationTimestamp, policy) -> pepperword

  Inputs:
    pepper       32 bytes (from GeneratePepper)
    passphrase   string (no algorithmic length limit; HMAC-SHA-512 accepts arbitrary message length)
    creationTimestamp    uint64 (Unix timestamp in milliseconds; MUST be unique among the rotation events of one app entry (see §6.1))
    policy       <composition, compositionPattern, prefix, postfix>

  Constants:
    MAX_TRIALS = 5000

  Output:
    pepperword   string satisfying policy
    error        if no permutation satisfies compositionPattern after MAX_TRIALS unsuccessful attempts

  Steps:
    HPM = uint64_be(creationTimestamp) || UTF8(NFC(passphrase))

    h  = HMAC-SHA-512(key=pepper, message=HPM)
    h1 = h[0:32]      // 256 bits — composition entropy
    h2 = h[32:64]     // 256 bits — permutation entropy

    encoded    = CompositionEncode(policy.composition, h1)
    core       = Permute(encoded, policy.compositionPattern, h2, MAX_TRIALS)
    pepperword = policy.prefix || core || policy.postfix

7. Entropy ID Derivation

7.1 Purpose

entropyID is a 24-character collision-resistant system identifier for a PGS entropy instance, derived deterministically from NE[4098] (the identity block, eb3). See §8.6 for security properties (preimage resistance, fingerprint risk against candidate-file corpora, two-factor implications).

A 6-character display alias, profileID = entropyID[0:6], is defined in §7.3 for human-readable contexts.

7.2 GenerateEntropyID

GenerateEntropyID(NE) -> entropyID

  Inputs:
    NE         array of NE_SIZE × 32-byte blocks (normalized entropy)

  Output:
    entropyID  string (24 characters, lowercase base32)

  Steps:
    eb3       = NE[4098]
    data      = eb3 || UTF8("pgs-entropy-id")
    h         = SHA-256(data)
    entropyID = base32_lowercase(h[0:15])    // 15 bytes → 24 base32 characters (no padding)

Output format. The 15-byte truncated SHA-256 output encodes to exactly 24 lowercase base32 characters (RFC 4648 alphabet lowercased: a–z, 2–7; no padding). Example: l33vfvfx47ihsoworovvd5o6 (see §9.6 for the derivation vector).

Domain separation. The label "pgs-entropy-id" is appended to eb3 before hashing. This prevents any block assigned to a different purpose from accidentally producing the same hash output, even in future protocol revisions that assign additional derivations to eb3.

Stability. entropyID is frozen within the PGS v1.x series. Any change to the derivation (label string, truncation length, or encoding) requires a MAJOR bump.

7.3 ProfileID

profileID = entropyID[0:6]    // first 6 characters of entropyID

profileID inherits the lowercase base32 alphabet from entropyID. No additional hashing or encoding step is required.

Purpose. profileID may replace entropyID in human-facing contexts where a 6-character lowercase base32 prefix (30 bits, with birthday-bound collision risk) is sufficient. Use the full entropyID where global uniqueness or durable keying is required.

8. Security Considerations

8.1 Security Goals

PGS is designed to achieve the following properties:

Deterministic recovery. Given the same entropy source, targetId, passphrase, creationTimestamp, and policy, any compliant implementation produces the same pepperword.

Target isolation. The pepperword for one (user, target) pair is computationally independent from the pepperword for any other pair. The targetId is a registrable-domain credential namespace: isolation is per registrable domain, not per subdomain, scheme, port, or application. This means the following URL variants all produce the same targetId and therefore the same credential:

• http://example.com and https://example.com → example.com
• https://example.com and https://example.com:8080 → example.com
• https://app.example.com and https://example.com → example.com

This is intentional. A user expects the same password to work at http:// and https:// of the same site, and at non-default ports serving the same application. Collapsing scheme and port into the registrable domain produces a single credential per site rather than one per URL variant. The tradeoff is that a server running distinct applications on different ports of the same domain will share a PGS credential; if this is undesirable, the caller derives distinct targetId values from distinct synthetic derivation URLs such as http://service-a.localhost (§5.1). A subdomain of the domain itself cannot serve: no URL yields app1.example.com, because PSL reduction collapses every host under a PSL-known registrable domain to that domain. A .localhost host escapes this because no PSL entry matches it, so the whole host passes through (§5.1).

An attacker who controls a non-canonical variant of a target (e.g., http://example.com via DNS hijacking or TLS stripping, or a hostile service on https://example.com:8080) can phish the credential shared with the canonical https://example.com, since all variants produce the same targetId. Modern HTTPS enforcement (HSTS, browser warnings) makes the http-strip case rare in practice, but the risk remains inherent to the scheme- and port-agnostic credential namespace.

The primary mechanism for isolation across different registrable domains is pepper separation: each app derives a 32-byte HMAC key via the hash-based index lookup. These keys are usually, but not always, distinct — the pepper pool has 4096 slots, so two targets collide with probability ≈ 1-in-4096 (see §5.2). creationTimestamp provides a secondary layer: distinct timestamps make HPMs differ across app entries even if a pepper collision occurs. creationTimestamp collisions are unlikely in ordinary use (see §6.1); even if a collision occurred, a security consequence additionally requires a pepper collision (~1-in-4096), making the joint probability negligible.

Two-factor protection. Neither the entropy source alone nor the passphrase alone is sufficient to derive a pepperword. An attacker must compromise both. (The entropy source alone is sufficient to derive all peppers; the passphrase is required to complete derivation.)

No forward secrecy. PGS makes no forward secrecy guarantees. If both secrets (entropy source and passphrase) are simultaneously compromised, all past and future pepperwords are exposed. This is a fundamental property of deterministic derivation: it is a design constraint, not a flaw.

No authentication. PGS does not authenticate the identity of the user to a relying application. It produces a credential string that must be submitted through the relying application's normal authentication channel.

8.2 Threat Model

8.3 Entropy Source Security

The security of every derived pepperword depends entirely on the entropy source being secret. An attacker who can reconstruct the entropy source (for example, because the "keepsafe photo" was posted publicly), combined with the passphrase and per-entry metadata (creationTimestamp, policy, targetId), can derive all pepperwords.

Most social platforms re-encode images on upload and strip metadata, so a publicly posted version typically differs byte-for-byte from the original. The attack therefore requires a byte-exact copy of the file (e.g., a lossless backup or cloud-sync leak), not merely a visually identical copy.

The entropy source MUST be:

• Not publicly available or shared as the byte-exact original (re-encoded copies, e.g. social-media uploads, typically differ)
• Not reproducible from public information (not a downloaded wallpaper, not a screenshot of a public page)

The entropy source must strictly exceed NE_SIZE × 32 bytes (132,096 bytes); files at exactly this size are rejected. This is a necessary but not sufficient condition for Assumption ES-min-entropy. Size alone does not guarantee security: a 132 KB file of all-zero bytes provides no entropy. The security requirement is that the entropy source be unguessable, not merely large.

Byte-identity across devices and over time. Every derivation from a given entropy source requires byte-identical input. Normalize (§4.1) is a pure function of its input, so any change to the bytes produces a different NE, and therefore a different entropyID and a different pepper and pepperword for every target. The failure mode is silent: drifted bytes are still a valid entropy source, just a different one, so no step in the pipeline raises an error. A client that reads drifted bytes derives a self-consistent but entirely separate identity. Any record keyed by the original entropyID is simply not found, indistinguishable from a fresh account; any credential re-derived for an existing target no longer matches, indistinguishable from a wrong entropy source. No surfaced error points at byte drift as the cause.

The hazard usually arises on the read path, not the storage or transport layer. Media-library APIs commonly expose several versions of the same asset (original, post-edit, compatibility-format) and return different bytes depending on which version is requested. A user-initiated edit in a photo manager produces a post-edit version that differs from the original; share or export workflows often re-encode; platform-version upgrades may change which version a given API returns by default; and an asset round-tripped through a third-party app is almost always re-encoded.

Implementations SHOULD capture the entropy source bytes at registration and persist those captured bytes for all subsequent derivations, rather than re-reading from a media-library reference (asset identifier, file path, cloud handle) that may return different bytes later. An implementation that does re-read from such a reference MUST request the original-asset bytes explicitly, not a derived, re-encoded, or post-edit version, and MUST verify the returned bytes are byte-identical to those used at registration before performing any derivation. Surfacing an explicit "entropy source has changed" error is preferable to silently deriving against new bytes.

8.4 Passphrase Security

The passphrase is the second factor. If the entropy source is compromised, the passphrase is the sole remaining protection for all pepperwords. Users SHOULD choose a passphrase that is strong, memorable, and not reused elsewhere.

No key stretching is applied during pepperword derivation. HMAC-SHA-512(key=pepper, message=HPM) is a single hash evaluation (~1–2 µs on a mobile SoC). This is a deliberate choice. PGS derives pepperwords on demand; every derivation is user-facing and battery-visible. A memory-hard KDF such as Argon2id (m=65536, t=3) would require ~100–200 ms and sustained memory-bandwidth activity per derivation, measurably impacting energy consumption on mobile devices. This cost is not justified by the security gain, for the reasons below.

Threat model: mass/scalable attacks. PGS is designed to resist attacks that are scalable: where compromising one resource exposes many users. A service database breach is one operation exposing millions of credentials. Compromising millions of individual devices is not one operation; it is millions of individually costly, detectable operations. The two-compromise precondition (service breach + device access) therefore provides strong resistance against mass attacks even if the compromises are not simultaneous.

Why cloud storage does not collapse this barrier. Cloud-account compromise is described by the data it yields: candidate entropy-source files (the photo library) and, when synced metadata is co-located in the same account, per-entry metadata including a stored entropyID or profileID. It yields no pepperword, because PGS stores no passwords; the account contains no offline verifier. Without a verifier, a passphrase candidate can only be checked by submitting the derived pepperword to a live relying service, an online attack subject to rate limiting and lockout. The size of the search depends on what was obtained. Without a stored identifier, the attacker faces a two-dimensional search: N candidate files × passphrase space. With a stored identifier (for example, the photo library and the synced metadata both in iCloud), the file-identification dimension collapses to an O(N_files) fingerprint match and only the passphrase dimension remains (§8.6). Either way, verification stays online; cloud-account compromise alone does not enable offline search.

Offline search requires a verifier: a known pepperword, or a relying service's stored verifier of one (a breached password hash suffices; each guess then also pays that service's hashing cost). An attacker who holds the cloud data above plus such a verifier can brute-force the passphrase offline, at HMAC-SHA-512 speed in the worst case (§8.2). The remaining defense is the passphrase strength this section opens with. Scaling this across users would require correlating two provider-scale breaches: credential databases leak routinely, but byte-exact private photo libraries are petabyte-scale stores with no history of provider-scale exfiltration. The conclusion's "not achievable at scale" rests on that asymmetry.

Targeted attacks are out of scope. An attacker who has physically compromised a specific device can keylog the passphrase directly, read app memory, or extract data without any brute-force. For such an attacker, the offline path (ES + pepperword → brute-force HPM) is the harder route, not the easier one. Password confidentiality is not the binding constraint in a targeted device compromise, and PGS makes no claim to protect against it.

Conclusion. If the entropy source is secret, key stretching provides no benefit: the attacker cannot compute the pepper. If the entropy source is compromised but no pepperword is known, verification requires submitting candidates to live services, an online attack subject to rate limiting and lockout. If both are known, offline search becomes possible, but this precondition is not achievable at scale. Key stretching adds real, user-visible cost on every derivation against an attack surface that does not justify it.

8.5 Per-App Isolation

Peppers are derived via a hash-based index lookup over the 4096-block pool. The probability of two distinct targets mapping to the same index (and therefore the same pepper) is:

P(collision | N apps) = 1 - (4096 · 4095 · ... · (4096 - N + 1)) / 4096^N

For N = 10 apps: ≈ 1.1%. For N = 20 apps: ≈ 4.5%.

Apps that share a pepper still produce independent derivations when their HPMs differ, which is the case when creationTimestamps differ. This separation is conditional, not guaranteed. First, creationTimestamp is a caller-supplied value with no uniqueness requirement across entries (§6.1); HPM separation holds only when the stored values actually differ, though collisions are unlikely in ordinary use (interactive entry creation rarely lands two entries on the same millisecond). Second, distinct HPMs yield independent HMAC outputs, not guaranteed-distinct pepperwords: the policy mapping compresses 512 bits into the policy's output space, so two independent derivations collide with probability roughly 1/|space| (more if the composition is skewed by duplicate characters) — negligible for typical policies, appreciable for small spaces such as a six-digit PIN. A pepper collision alone is therefore unlikely to break app isolation at the pepperword level. It does mean that knowledge of NE[idx] exposes the pepper for two apps simultaneously, which is a second-order risk only if NE is partially compromised.

8.6 Entropy ID Security

entropyID is derived from eb3 (NE[4098]) via SHA-256 with a domain-separation label and 15-byte truncation. Its security properties depend on what else the attacker holds.

Attacker with entropyID only. No path to eb3, NE, or any pepperword. SHA-256 preimage resistance ensures the 15-byte truncated hash leaks no information about the entropy source's content. entropyID is safe to expose in this scenario.

Attacker with entropyID and a candidate-file corpus. entropyID functions as a deterministic fingerprint: the attacker computes GenerateEntropyID(Normalize(candidate)) for each file and matches against the target entropyID. Whichever file matches is the entropy source. This is not a preimage attack; preimage resistance is irrelevant when the search space is small and known.

Implication for two-factor protection. Under device or cloud-account compromise (attacker has both the user's files and a stored entropyID), the attacker reduces the search from O(N_files × N_passphrases) to O(N_files) fingerprint matches followed by O(N_passphrases) pepperword derivations; whether those derivations can be verified offline still depends on holding a verifier for some pepperword (§8.4). Implementations SHOULD treat entropyID as sensitive metadata rather than freely loggable, especially in storage paths that may be synced or backed up alongside the user's file corpus.

profileID as a fingerprint. The 6-character profileID is the 30-bit prefix of entropyID, and 30 bits is enough to fingerprint the entropy source within a personal-scale corpus: against N candidate files the expected false-match rate is ≈ N / 2^30 (≈ 10^(−5) for a 10,000-file library). Wherever profileID appears in stored or synced metadata — for example embedded in a cloud record name — it carries the same oracle risk as entropyID under the same preconditions (the attacker holds the value and a candidate corpus), differing only in collision rate, not in fingerprinting power at personal scale. Treat profileID as sensitive metadata accordingly.

Uniqueness. Two distinct entropy sources produce the same entropyID with probability bounded by the collision probability of SHA-256 truncated to 15 bytes (≈ 2^(−120)). profileID, the 6-character prefix, carries ~30 bits of collision resistance: negligible for the expected number of profiles per user, but not globally unique. Callers that require a globally collision-free key SHOULD use the full entropyID rather than profileID.

8.7 Hash Construction

HMAC-SHA-512(key=pepper, message=HPM) is the standard keyed-hash construction. HMAC has a formal security reduction (pseudorandomness under the assumption that the underlying compression function is a PRF) and is the community standard for keyed hashing.

8.8 Permutation Distribution

GeneratePermutation uses standard Fisher-Yates with divisor i+1 at step i. Two effects make the distribution over all n! permutations non-uniform. Bounded reachability (dominant at large n): the permutation is seeded by ba, which carries 256 bits of entropy (the 32-byte h2); the initial SHA-512(ba) widens it to a 512-bit seed but adds no entropy, so at most 2^256 of the n! permutations are reachable. For small n this is moot (at n = 12, 12! ≈ 2^28.8 ≪ 2^256, so the seed width excludes no permutation); at the maximum n = 98, 98! ≈ 2^511.5, so at most a ≈ 2^(-255.5) fraction of the permutations are reachable. Modular bias: even modeling the 512-bit seed as uniform, the modular reduction leaves a statistical distance from uniform bounded by n! / 2^512 (≈ 2^(-483) at n = 12, ≈ 2^(-0.5) ≈ 71% at n = 98); this bound is loose. Both effects mean the permutation distribution at large n is far from uniform over all n!.

This non-uniformity is acceptable under the threat model that sets attacker cost: search over entropy-source and passphrase candidates (§8.2, §8.4). An attacker holding a verifier searches the passphrase space if the entropy source is known, or candidate files × passphrases if only a candidate corpus is held (§8.4). Verification is deterministic per candidate: a given (entropy source, passphrase) candidate produces exactly one pepperword, which either matches the verifier or does not. The distribution over pepperwords therefore does not change per-candidate cost, and gives the attacker no way to prioritize candidates; every candidate must still be evaluated through the full pipeline. The permutation's own contribution is bounded by log₂(n!) and is not the dominant entropy source, so its shape does not affect this search.

A separate attack model is direct output guessing: an attacker who lacks the entropy source and passphrase guesses pepperword strings directly, either online against a live relying service or offline against a breached verifier. Output non-uniformity is in principle relevant here: it would let the attacker order guesses by descending probability, lowering the effective guessing entropy of the permutation component below log₂(n!). The defense in this model is the pepperword's total output entropy, and the weight of the permutation bias within it depends on the policy: under typical policies the permutation is one component among several and the residual effect is minor, while a degenerate composition that fixes the character multiset (every unit a single scalar) makes the permutation the sole entropy component, bounded even then by the seed's 256 bits. Rejection sampling would remove the modular bias (it cannot widen bounded reachability, which is inherent to the 256-bit seed) but provides no benefit under the candidate-search model that sets attacker cost, and is not adopted.

8.9 Target Identifier Stability

The target identifier MUST remain stable per app across all client implementations and versions. A change to the normalization rules, or inconsistency between the main app and an AutoFill extension, changes the derived pepper and produces a different pepperword, silently locking the user out of their account with no error indication. This is among the highest-severity implementation risks in PGS.

All code paths that call GeneratePepper MUST use identical targetId derivation logic. The normalization test vectors in §9.5 are normative for this purpose and MUST be used to validate every implementation and every platform port.

8.10 Timing Analysis

Permute executes a variable number of trials until the generated string matches compositionPattern. Trial count depends on the compositionPattern's specificity. For common policies (e.g., must contain a digit), the expected number of trials is under 5. For highly restrictive patterns, it may be higher.

The trial count is observable only to an attacker who can time the derivation, and the derivation runs on the user's device. That is the targeted device compromise §8.4 places out of scope: an attacker positioned to time derivations can keylog the passphrase or read the pepperword directly, and needs no timing channel. Where the output is visible anyway (the pepperword is submitted to the relying application), trial count reveals nothing the pepperword itself does not.

The retry hash chain h = SHA-512(h || UTF8(s)) ensures each trial uses fresh entropy derived from the previous permutation, preventing an attacker who observes the pepperword from predicting earlier rejected candidates.

8.11 Metadata Custody

PGS has five recovery inputs: entropy source, passphrase, creationTimestamp, policy, and target identifier. The first two are user-held secrets. The latter three are opaque metadata: they cannot be memorized, cannot be reconstructed on demand, and have no meaningful default. Loss of any one of them makes the pepperword permanently unrecoverable regardless of whether both secrets are intact.

targetId deserves special emphasis: although it can be derived from a URL via the normalization algorithm in §5.1, that derivation is only correct for the URL in effect at credential creation. If the URL later changes, the original targetId used at password generation time becomes unrecoverable unless it was explicitly stored at that time. Storing only the current URL and re-deriving targetId on the fly is therefore insufficient for rotation history recovery.

To derive any pepperword, an implementation needs the creationTimestamp, policy, and targetId in effect at that pepperword's generation. How those values are persisted, synchronized across devices, or backed up is an implementation concern. A user whose only device loses this metadata, with no backup, loses access to all credentials whose metadata was lost, even with the correct entropy source and passphrase.

The three recovery fields contain no secret: knowledge of creationTimestamp, policy, and targetId reveals nothing about any pepperword without the entropy source and passphrase, and they may be stored and synced in plaintext. This plaintext claim is scoped to those three fields. Other per-entry metadata is not automatically in the same class: entropyID and profileID are sensitive fingerprinting metadata per §8.6.

9. Test Vectors

9.1 Test Entropy Source

All test vectors use the following entropy source, constructed deterministically from a 256-bit seed by stretching with SHAKE-256:

seed = SHA-256("PGS v1.3 test vector seed")   = 0d7d201fedfaa4d8b98260f39376f8fd249f12c489a61a4d9ba7ab5812faa2fb
ES   = SHAKE-256(seed, NE_SIZE × 32 + 32)                  (132128 bytes)

The seed is a "nothing up my sleeve" number, derived from a fixed ASCII string via SHA-256 and verifiable by anyone. The seed string intentionally retains "v1.3"; the NE derivation algorithm has been identical since v1.3. ES satisfies the size requirement (len(ES) > NE_SIZE × 32). Both primitives are defined in §2.3.

SHA-256(ES) = 35c81f2cb9070deba98a9c1e484a1b1ee50186b5c8bc76b548ee3f75731311bd

NE is derived from ES per §4.1:

NE   = SHAKE-256(ES, NE_SIZE × 32)                          (132096 bytes)
SHA-256(NE) = 7284c8242c2591ceeacf5638f1959bf90ed525ba8fee5caee702497e74dea1f1

9.2 Test Policies

Policy "default":
  composition: [
    <"abcdefghijklmnopqrstuvwxyz", 8>,
    <"ABCDEFGHIJKLMNOPQRSTUVWXYZ", 2>,
    <"0123456789", 2>
  ]
  compositionPattern: .*    (any string)
  prefix:  ""
  postfix: ""

Policy "special":
  composition: [
    <"abcdefghijklmnopqrstuvwxyz", 8>,
    <"0123456789", 2>,
    <"!@#$%^&*", 1>
  ]
  compositionPattern: .*[!@#$%^&*].*
  prefix:  ""
  postfix: ""

Policy "emoji":
  composition: [
    <"a🔑b", 6>           (charSet of three scalars: U+0061, U+1F511, U+0062)
  ]
  compositionPattern: .*
  prefix:  ""
  postfix: ""

Policy "wrapped":
  composition: same as policy "default"
  compositionPattern: ^[a-z].*[a-z]$
  prefix:  "9-"
  postfix: "-Z"

Policy "digitfirst":
  composition: same as policy "default"
  compositionPattern: ^[0-9]
  prefix:  ""
  postfix: ""

9.3 Intermediate Values for Vector #1

NE seed blocks are unchanged from v1.5 (NE derivation is identical).

9.4 Test Vectors

Vector #2 MUST differ from #1 (rotation produces a different pepperword). Vector #3 MUST differ from #1 (different target produces a different pepperword). Vector #5 MUST contain a character from !@#$%^&*. Vector #6's passphrase is the five-scalar NFD sequence U+0063 U+0061 U+0066 U+0065 U+0301 (cafe plus COMBINING ACUTE ACCENT). NFC (§2.6) maps it to the four-scalar precomposed café (ending U+00E9), so the same pepperword MUST result from supplying either form. An implementation that skips NFC hashes different HPM bytes and fails this vector on the NFD form. Vector #7's passphrase begins with U+1F511 (🔑), a supplementary-plane scalar (UTF-8 f0 9f 94 91, two UTF-16 code units). It pins correct UTF-8 encoding of astral scalars in HPM; a CESU-8 or surrogate-splitting encoder fails it. Vector #8's charSet has |C| = 3 Unicode scalars but 4 UTF-16 code units, so both the modulus and the indexing C[r] in CompositionUnitEncode (§6.3) diverge under the UTF-16 code-unit indexing that §2.6 forbids. Vector #9 pins prefix || core || postfix assembly and that compositionPattern matches the core only (§6.2): the prefix begins with a digit and the postfix ends with an uppercase letter, so an implementation that matches the pattern against the assembled string can never satisfy ^[a-z].*[a-z]$ and aborts at MAX_TRIALS instead of producing the expected output. Vector #10 requires 4 permutation trials under ^[0-9]; the retry chain below is normative for the §6.4 construction.

Intermediate values for Vector #10 (Permute retry chain). Vector #9 shares every derivation input with #10 except the policy's pattern and affixes, so pepper, h1, h2, and encoded below apply to it as well; its pattern ^[a-z].*[a-z]$ accepts the trial-1 candidate, which is why #9's core is tg1fXyGe9yiz. The encoded value shows the §6.3 unit order: unit n (digits) occupies the leading positions. Trial 4's post-trial hash update is computed per the §6.4 pseudocode but does not affect the output and is omitted.

9.5 targetId Normalization Vectors

These vectors are normative. Any compliant implementation MUST produce the exact output shown. Because targetId divergence silently produces a different pepper, these vectors are the primary conformance check for §5.1. Every registrable-domain reduction here uses a stable ICANN public suffix (.com, .co.uk), and the invalid TLD is reserved by [RFC 6761] and can never enter the list, so no expected output depends on the PSL snapshot. Wildcard and exception entries (such as *.ck/!www.ck) are deliberately not exercised: registry policy changes can rewrite them, and a vector relying on one would fail a conforming implementation under a later snapshot. Reductions that rely on a PSL private-section entry are snapshot-dependent and are therefore excluded from the normative set; the app.github.io row in the §5.1 examples table is illustrative only.

Success cases:

Abort cases (implementation MUST abort, not silently produce output):

9.6 Entropy ID Vectors

These vectors are normative. Any compliant implementation MUST produce the exact output shown.

10. References

10.1 Normative References

• [RFC 1035] Mockapetris, P., "Domain Names - Implementation and Specification," STD 13, RFC 1035, November 1987. https://tools.ietf.org/html/rfc1035
• [RFC 1123] Braden, R., Ed., "Requirements for Internet Hosts - Application and Support," STD 3, RFC 1123, October 1989. https://tools.ietf.org/html/rfc1123
• [RFC 2104] Krawczyk, H., Bellare, M., and Canetti, R., "HMAC: Keyed-Hashing for Message Authentication," RFC 2104, February 1997. https://tools.ietf.org/html/rfc2104
• [RFC 2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels," BCP 14, RFC 2119, March 1997. https://tools.ietf.org/html/rfc2119
• [RFC 3986] Berners-Lee, T., Fielding, R., and Masinter, L., "Uniform Resource Identifier (URI): Generic Syntax," STD 66, RFC 3986, January 2005. https://tools.ietf.org/html/rfc3986
• [RFC 4648] Josefsson, S., "The Base16, Base32, and Base64 Data Encodings," RFC 4648, October 2006. https://tools.ietf.org/html/rfc4648
• [RFC 5234] Crocker, D., Ed., and Overell, P., "Augmented BNF for Syntax Specifications: ABNF," STD 68, RFC 5234, January 2008. https://tools.ietf.org/html/rfc5234
• [RFC 5890] Klensin, J., "Internationalized Domain Names for Applications (IDNA): Definitions and Document Framework," RFC 5890, August 2010. https://tools.ietf.org/html/rfc5890
• [FIPS 180-4] NIST, "Secure Hash Standard (SHS)," FIPS PUB 180-4, August 2015. https://csrc.nist.gov/publications/detail/fips/180/4/final
• [FIPS 202] NIST, "SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions," FIPS PUB 202, August 2015. https://csrc.nist.gov/publications/detail/fips/202/final
• [PSL] Mozilla Foundation, "Public Suffix List." https://publicsuffix.org/

10.2 Informative References

Cited for provenance or rationale; the algorithms and grammars they describe are fully specified inline where this document uses them, so conformance does not require consulting these references.

• [Fisher-Yates] Fisher, R.A. and Yates, F., "Statistical Tables for Biological, Agricultural and Medical Research," 1938. https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
• [RE2] Google, "RE2 Syntax Reference." https://github.com/google/re2/wiki/Syntax
• [RFC 6761] Cheshire, S. and Krochmal, M., "Special-Use Domain Names," RFC 6761, February 2013. https://tools.ietf.org/html/rfc6761

Appendix A: Implementor Pitfalls (Non-Normative)

Not referenced from the normative text; retained as practical notes.

A.1 BigInteger Byte Order

BigInt(b) uses standard big-endian byte order: b[0] is the most significant byte. This matches all standard big-integer libraries:

• Python: int.from_bytes(b, 'big')
• Go: new(big.Int).SetBytes(b)
• Java: new BigInteger(1, b) (the unsigned constructor; never new BigInteger(b), which is signed two's-complement)

For SHA-256 output h, BigInt(h) mod 4096 is determined by the lowest 12 bits of the integer, i.e. the low 4 bits of h[30] and all 8 bits of h[31].

Test vector for endianness: For the 32-byte hash h with h[0] = 0x03, h[31] = 0x01, and all other bytes 0x00 (the low nibble of h[30] also feeds idx, so it must be stated), big-endian gives idx = 1. Any implementation producing idx = 3 is interpreting the bytes little-endian and is incorrect.

A.2 String Encoding

All string-to-bytes conversions use UTF-8:

• targetId in GeneratePepper
• passphrase (NFC-normalized) in GeneratePepperword HPM construction
• The permuted string s in the Permute retry hash chain
• The domain-separation label "pgs-entropy-id" in GenerateEntropyID

A.3 compositionPattern Matching

Python implementor note. Python's re module has three match functions with different anchoring behavior. Only re.search() performs an unanchored match as required by this spec:

# WRONG — re.match() anchors at the start of the string
if re.match(compositionPattern, s):  # "[A-Z]" only matches if s[0] is uppercase

# WRONG — re.fullmatch() requires the pattern to span the entire string
if re.fullmatch(compositionPattern, s):  # "[A-Z]" only matches a single uppercase letter

# CORRECT — re.search() matches anywhere within the string
if re.search(compositionPattern, s):  # "[A-Z]" matches if s contains any uppercase letter

Copyright and License

© 2026 Pepperword

This specification is published for transparency and independent review. The document text is licensed under the Creative Commons Attribution 4.0 International License (CC BY 4.0): you may copy, redistribute, translate, and annotate it in any medium or format, including commercially, provided you give appropriate credit. This license covers the document only and grants no patent rights (see Patent below).

"Pepperword" and "PGS" identify the protocol and its specification; this license grants no trademark rights. Only the unmodified specification published by Pepperword may be called "PGS"; adapted or translated copies must not present themselves as the official PGS specification or imply endorsement by Pepperword.

Patent

This specification describes methods covered by U.S. Patent 10,423,776. This document is published for transparency and independent review. It grants no license, express or implied, to practice that patent; all patent rights are reserved. To license the patent or implement PGS, reach out at licensing@pepperword.app.