Prefix-Preserving Encryption for URIs

1.1. Use Cases and Motivations

The main motivations include:¶

• Access Control in CDNs: Content Delivery Networks often use URI prefixes for routing and access control. URICrypt allows encrypting resource paths while preserving the prefix structure needed for CDN operations.¶

• Privacy-Preserving Logging: Systems can log encrypted URIs without exposing sensitive path information, while still enabling analysis based on URI structure.¶

• Confidential Data Sharing: When sharing links to sensitive resources, URICrypt prevents the path structure itself from revealing confidential information.¶

• Token-Based Access Systems: Systems that issue time-limited access tokens can use URICrypt to obfuscate the underlying resource location while maintaining routability.¶

• Multi-Tenant Systems: In systems where multiple tenants share infrastructure, URICrypt can isolate tenant data while allowing shared components to be processed efficiently.¶

• Privacy-Preserving Analytics: URICrypt can complement IPCrypt [I-D.draft-denis-ipcrypt]. Together, they enable systems to perform analytics on encrypted network flows and resource access patterns without exposing sensitive information about either the network endpoints or the specific resources being accessed.¶

3.1. URI Component Extraction

Before encryption, a URI must be split into its scheme and path components. The path is further divided into individual components for chained encryption.¶

Input:  "https://example.com/a/b/c"

Components:

- Scheme: "https://"
- Component 1: "example.com/"
- Component 2: "a/"
- Component 3: "b/"
- Component 4: "c"

Input:  "/a/b/c"

Components:

- Scheme: "" (empty)
- Component 1: "a/"
- Component 2: "b/"
- Component 3: "c"

3.2. Component Reconstruction

During decryption, components are joined to reconstruct the original path:¶

Components: ["example.com/", "a/", "b/", "c"]
Reconstructed Path: "example.com/a/b/c"

When combined with the scheme: "https://example.com/a/b/c"

4.1. Hasher Initialization

The base hasher is initialized with the secret key and context parameter using length-prefixed encoding to prevent ambiguities.¶

Two hashers are derived from the base hasher:¶

1. Components Hasher: Updated with each component’s plaintext to generate SIVs¶

2. Base Keystream Hasher: Used as the starting point for generating keystream for each component¶

The initialization process:¶

base_hasher = TurboSHAKE128()
base_hasher.update(len(secret_key))
base_hasher.update(secret_key)
base_hasher.update(len(context))
base_hasher.update(context)

components_hasher = base_hasher.clone()
components_hasher.update("IV")

base_keystream_hasher = base_hasher.clone()
base_keystream_hasher.update("KS")

4.2. Component Encryption

For each component, the encryption process is:¶

1. Update components_hasher with the component plaintext¶

2. Generate SIV from components_hasher (16 bytes)¶

3. Create keystream_hasher by cloning base_keystream_hasher and updating with SIV¶

4. Calculate padding needed for base64 encoding¶

5. Generate keystream of length (component_length + padding)¶

6. XOR padded component with keystream¶

7. Output SIV concatenated with encrypted_component¶

The padding length is calculated as: padding_len = (3 - (16 + component_len) % 3) % 3¶

4.3. Component Decryption

For each encrypted component, the decryption process is:¶

1. Read SIV from input (16 bytes)¶

2. Create keystream_hasher by cloning base_keystream_hasher and updating with SIV¶

3. Read encrypted component data (length determined from encoding)¶

4. Generate keystream and decrypt component¶

5. Remove padding to recover plaintext¶

6. Update components_hasher with plaintext¶

7. Generate expected SIV from components_hasher¶

8. Compare expected SIV with received SIV (constant-time)¶

9. If mismatch, return error¶

Any tampering with the encrypted data will cause the SIV comparison to fail.¶

4.4. Padding and Encoding

Each encrypted component (SIV || ciphertext) is padded to make its length a multiple of 3 bytes, enabling clean base64 encoding without padding characters.¶

The final output is encoded using URL-safe base64 [RFC4648] without padding.¶

5.1. Encryption Algorithm

Input: secret_key, context, uri_string¶

Output: encrypted_uri¶

Steps:¶

1. Split URI into scheme and components¶

2. Initialize hashers as described in Section 4.1¶

3. encrypted_output = empty byte array¶

4. For each component:¶

   • Update components_hasher with component¶

   • SIV = components_hasher.read(16)¶

   • keystream_hasher = base_keystream_hasher.clone()¶

   • keystream_hasher.update(SIV)¶

   • padding_len = (3 - (16 + len(component)) % 3) % 3¶

   • keystream = keystream_hasher.read(len(component) + padding_len)¶

   • padded_component = component concatenated with zeros(padding_len)¶

   • encrypted_part = padded_component XOR keystream¶

   • encrypted_output = encrypted_output concatenated with SIV concatenated with encrypted_part¶

5. base64_output = base64url_encode(encrypted_output)¶

6. Return scheme + base64_output¶

5.2. Decryption Algorithm

Input: secret_key, context, encrypted_uri¶

Output: decrypted_uri or error¶

Steps:¶

1. Split encrypted URI into scheme and base64 part¶

2. decoded = base64url_decode(base64_part). If decoding fails, return error¶

3. Initialize hashers as described in Section 4.1¶

4. decrypted_components = empty list¶

5. input_stream = Stream(decoded)¶

6. While input_stream is not empty:¶

   • SIV = input_stream.read(16). If not enough bytes, return error¶

   • keystream_hasher = base_keystream_hasher.clone()¶

   • keystream_hasher.update(SIV)¶

   • Determine component length from remaining data and padding¶

   • encrypted_part = input_stream.read(component_length)¶

   • keystream = keystream_hasher.read(len(encrypted_part))¶

   • padded_plaintext = encrypted_part XOR keystream¶

   • component = remove_padding(padded_plaintext)¶

   • Update components_hasher with component¶

   • expected_SIV = components_hasher.read(16)¶

   • If constant_time_compare(SIV, expected_SIV) == false: return error¶

   • decrypted_components.append(component)¶

7. decrypted_path = join(decrypted_components)¶

8. Return scheme + decrypted_path¶

6.1. TurboSHAKE128 Usage

Implementations MUST use TurboSHAKE128 with a domain separation parameter of 0x1F for all operations. The TurboSHAKE128 XOF is used for:¶

• Generating SIVs from the components hasher¶

• Generating keystream for encryption/decryption¶

• All hash operations in the initialization¶

TurboSHAKE128 is specified in [I-D.draft-irtf-cfrg-kangarootwelve] and provides the security properties needed for this construction.¶

6.2. Key and Context Handling

The secret key MUST be at least 16 bytes long. Keys shorter than 16 bytes MUST be rejected. Implementations SHOULD validate that the key does not consist of repeated patterns (e.g., identical first and second halves) as a best practice.¶

The context parameter is a string that provides domain separation. Different applications SHOULD use different context strings to prevent cross-application attacks. The context string MAY be empty.¶

Both key and context are length-prefixed when absorbed into the base hasher:¶

base_hasher.update(len(secret_key) as uint8)
base_hasher.update(secret_key)
base_hasher.update(len(context) as uint8)
base_hasher.update(context)

The length is encoded as a single byte, limiting keys and contexts to 255 bytes. This is sufficient for all practical use cases.¶

6.3. Error Handling

Implementations MUST NOT reveal the cause of decryption failures. All error conditions (invalid base64, incorrect padding, SIV mismatch, insufficient data) MUST result in identical, generic error messages.¶

SIV comparison MUST be performed in constant-time to prevent timing attacks.¶

7.1. Confidentiality

URICrypt achieves semantic security for URI path components through its use of TurboSHAKE128 as a pseudorandom function. Each component is encrypted using a unique keystream derived from:¶

• The secret key¶

• The application context¶

• A synthetic initialization vector (SIV) that depends on all preceding components¶

This construction ensures that:¶

• An attacker without the secret key cannot recover plaintext components from ciphertexts¶

• The keystream generation is computationally indistinguishable from random for each unique (key, context, path-prefix) tuple¶

• Components are protected by at least 128 bits of security against brute-force attacks¶

7.2. Authenticity and Integrity

Each URI component is authenticated through the SIV mechanism:¶

• The SIV acts as a Message Authentication Code (MAC) computed over the component and all preceding components¶

• Any modification to a component will cause the SIV verification to fail during decryption¶

• The chained construction ensures that reordering, insertion, or deletion of components is detected¶

• Authentication provides 128-bit security against forgery attempts¶

7.3. Prefix-Preserving Property

URICrypt maintains a controlled information leakage pattern: - URIs sharing a common prefix will produce ciphertexts with the same encrypted prefix - This property is deterministic and intentional, enabling systems to perform prefix-based operations - The leakage is limited to prefix structure only - no information about non-matching suffixes is revealed¶

7.4. Domain Separation

The context parameter provides cryptographic domain separation: - Different contexts with the same key produce completely independent ciphertexts - This prevents cross-context attacks where ciphertexts from one application could be used in another - Context binding is cryptographically enforced through the hasher initialization¶

7.5. Resistance to Common Attacks

URICrypt resists several categories of attacks:¶

Chosen-Plaintext Attacks (CPA): While deterministic, URICrypt is CPA-secure for unique inputs. The determinism is a design requirement for prefix preservation.¶

Tampering Detection: Any bit flip, truncation, or modification in the ciphertext will be detected with overwhelming probability (1 - 2^-128).¶

Length Extension: The use of length-prefixed encoding and domain separation prevents length extension attacks.¶

Replay Attacks: Within a single (key, context) pair, replay is possible due to determinism. Applications requiring replay protection should incorporate timestamps or nonces in the context.¶

Key Recovery: TurboSHAKE128’s security properties ensure that observing ciphertexts does not leak information about the secret key.¶

7.6. Security Bounds

The security of URICrypt is bounded by:¶

• Key strength: Minimum 128-bit security with 16-byte keys¶

• Collision resistance: 2⁶⁴ birthday bound for SIV collisions¶

• Authentication security: 2^-128 probability of successful forgery¶

• Computational security: Based on TurboSHAKE128’s proven security as an XOF¶

7.7. Limitations and Trade-offs

URICrypt makes specific security trade-offs for functionality:¶

• Deterministic encryption: Same inputs produce same outputs, enabling certain traffic analysis¶

• Length preservation: Component lengths are not hidden, potentially revealing information patterns¶

• Prefix structure leakage: The hierarchical structure of URIs is preserved by design¶

These trade-offs are intentional and necessary for the prefix-preserving functionality. Applications requiring stronger privacy guarantees should evaluate whether URICrypt’s properties align with their threat model.¶

A.1. URI Component Extraction

function extract_components(uri_string):
  if uri_string contains "://":
     scheme = substring up to and including "://"
     path = substring after "://"
  else:
     scheme = ""
     path = uri_string

  if path starts with "/":
     path = substring after first "/"

  components = []
  while path is not empty:
     slash_pos = find("/", path)
     if slash_pos found:
        component = substring(0, slash_pos + 1)
        path = substring(slash_pos + 1)
        components.append(component)
     else:
        components.append(path)
        path = ""

  return (scheme, components)

A.2. Hasher Initialization

function initialize_hashers(secret_key, context):
  // Initialize base hasher
  base_hasher = TurboSHAKE128(0x1F)

  // Absorb key and context with length prefixes
  base_hasher.update(uint8(len(secret_key)))
  base_hasher.update(secret_key)
  base_hasher.update(uint8(len(context)))
  base_hasher.update(context)

  // Create components hasher
  components_hasher = base_hasher.clone()
  components_hasher.update("IV")

  // Create base keystream hasher
  base_keystream_hasher = base_hasher.clone()
  base_keystream_hasher.update("KS")

  return (components_hasher, base_keystream_hasher)

A.3. Encryption Algorithm

function uricrypt_encrypt(secret_key, context, uri_string):
  // Extract components
  (scheme, components) = extract_components(uri_string)

  // Initialize hashers with secret key and context
  (components_hasher, base_keystream_hasher) =
      initialize_hashers(secret_key, context)
  if error: return error

  encrypted_output = byte_array()

  // Process each component
  for component in components:
     // Update components hasher for SIV computation
     components_hasher.update(component)

     // Generate 16-byte Synthetic Initialization Vector (SIV)
     siv = components_hasher.squeeze(16)

     // Create keystream hasher for this component
     keystream_hasher = base_keystream_hasher.clone()
     keystream_hasher.update(siv)

     // Calculate padding for base64 encoding alignment
     component_len = len(component)
     padding_len = (3 - (16 + component_len) % 3) % 3

     // Generate keystream
     keystream = keystream_hasher.squeeze(component_len + padding_len)

     // Pad component to align with base64 encoding requirements
     padded_component = component + byte_array(padding_len)

     // Encrypt using XOR with keystream
     encrypted_part = xor_bytes(padded_component, keystream)

     // Append to output
     encrypted_output.extend(siv)
     encrypted_output.extend(encrypted_part)

  // Base64 encode with URL-safe characters and no padding
  base64_output = base64_urlsafe_no_pad_encode(encrypted_output)

  // Return with scheme
  return scheme + base64_output

A.4. Decryption Algorithm

function uricrypt_decrypt(secret_key, context, encrypted_uri):
  // Split scheme and base64
  if encrypted_uri contains "://":
     scheme = substring up to and including "://"
     base64_part = substring after "://"
  else:
     scheme = ""
     base64_part = encrypted_uri

  // Decode base64
  try:
     decoded = base64_urlsafe_no_pad_decode(base64_part)
  catch:
     return error("Decryption failed")

  // Initialize hashers with secret key and context
  (components_hasher, base_keystream_hasher) =
      initialize_hashers(secret_key, context)
  if error: return error

  decrypted_components = []
  input_stream = ByteStream(decoded)

  // Process each component
  while not input_stream.empty():
     // Read SIV
     siv = input_stream.read(16)
     if len(siv) != 16:
        return error("Decryption failed")

     // Create keystream hasher
     keystream_hasher = base_keystream_hasher.clone()
     keystream_hasher.update(siv)

     // Determine component length by checking padding constraints
     remaining = input_stream.remaining()
     if remaining == 0:
        return error("Decryption failed")

     // Find valid component length by checking padding alignment
     component_data = None
     for possible_len in range(1, remaining + 1):
        total_len = 16 + possible_len
        padding_len = (3 - total_len % 3) % 3
        if possible_len >= padding_len:
           component_data = input_stream.peek(possible_len)
           break

     if component_data is None:
        return error("Decryption failed")

     // Read encrypted data
     encrypted_part = input_stream.read(len(component_data))

     // Generate keystream and decrypt
     keystream = keystream_hasher.squeeze(len(encrypted_part))
     padded_plaintext = xor_bytes(encrypted_part, keystream)

     // Remove padding bytes added for base64 alignment
     padding_len = (3 - (16 + len(encrypted_part)) % 3) % 3
     component = padded_plaintext[:-padding_len] if padding_len > 0 else padded_plaintext

     // Update hasher with plaintext
     components_hasher.update(component)

     // Generate expected SIV
     expected_siv = components_hasher.squeeze(16)

     // Authenticate using constant-time comparison to prevent timing attacks
     if not constant_time_equal(siv, expected_siv):
        return error("Decryption failed")

     decrypted_components.append(component)

  // Reconstruct URI
  if scheme and decrypted_components:
     path = "".join(decrypted_components)
     return scheme + path
  elif decrypted_components:
     return "/" + "".join(decrypted_components)
  else:
     return ""

A.5. Padding and Encoding

function calculate_padding(component_len):
  // Calculate padding needed for base64 encoding alignment
  return (3 - (16 + component_len) % 3) % 3

function base64_urlsafe_no_pad_encode(data):
  // Use standard base64 encoding
  encoded = standard_base64_encode(data)
  // Make URL-safe and remove padding for URI compatibility
  encoded = encoded.replace('+', '-')
                   .replace('/', '_')
                   .rstrip('=')
  return encoded

function base64_urlsafe_no_pad_decode(encoded):
  // Add padding if needed for standard decoder
  padding = (4 - len(encoded) % 4) % 4
  if padding > 0:
     encoded = encoded + ('=' * padding)
  // Make standard base64
  encoded = encoded.replace('-', '+')
                   .replace('_', '/')
  // Decode
  return standard_base64_decode(encoded)

B.1. Test Vector 1: Full URI

Input: "https://example.com/a/b/c"
Output: "https://HOGo9vauZ3b3xsPNPQng5apSzL5V7QW94C7USgN8mHZJ337AKSWOucUwMuD-uUfF95SsSHCNgBkXUnH1uGll_YtBltXSqKEHNcYJJwbdFdhfWz19"

B.2. Test Vector 2: Path-Only URI

Input: "/a/b/c"
Output: "/b9bCOhqZsvU9XxGOMk6d8QFQhTIdI_xYKpds2lWXpZCms5-az9wtfUft3rec3d9YkUo0N7VcxO5MXfxE5UobvgTJX8UpRdNN"

B.3. Test Vector 3: Multi-Component Path

Input: "https://cdn.example.com/videos/2025/03/file.mp4"
Output: "https://hxUM2N3txwYjGxjvCpWn30SznxR0v0fDbkSQgCTXCUu7Rq8iSbWP40OvYxKs9zC3kw1JNzAc4Wuj7RZvRd0VUprJWLs5KJPnWsA9Kguxa_J7XviTS3GTqf-XZdPxYyq1Y1MXVE9_4ojHwm6jBDUkVthAkuNe5Cqk_h6d"

B.4. Test Vector 4: Root with Scheme

Input: "https://example.com/"
Output: "https://HOGo9vauZ3b3xsPNPQng5apSzL5V7QW94C7USgN8"

B.5. Test Vector 5: Simple Path

Input: "/path/to/resource"
Output: "/b9bCOhqZsvU9XxGOMk6d8QFQPTuMlsQKDBhAbc77JvsdRj0kxiFipunATQmmCkNhAe0BPP2EqQoxORElY_ukfUYSrr9mIMfiO9joa3Kn5RS7eSKr"