Cryptographic Foundations

This chapter establishes the mathematical foundations upon which every security guarantee in Zentalk rests. We specify the cryptographic primitives, explain the design decisions behind each choice, and state the security properties that subsequent chapters depend on. Readers already familiar with these primitives may proceed to Chapter 3.

Finite Field Arithmetic

Zentachain's cryptographic operations are performed over two finite fields: $\text{GF}(2^{255} - 19)$ for elliptic curve operations (chosen for efficient constant-time reduction and 128-bit security [Bernstein, 2006]) and $\text{GF}(2^8)$ for Reed-Solomon erasure coding. The mathematical properties of finite fields -- closure, associativity, and the existence of inverses -- guarantee that all cryptographic operations are well-defined and reversible where required.

Prime Field for Curve25519

Zentalk's primary key agreement and signature schemes operate over the prime field $\text{GF}(p)$ where:

$$p = 2^{255} - 19$$

This prime was chosen by Bernstein [8] for several specific properties:

Efficient Reduction

Since $p = 2^{255} - 19$ is close to a power of 2, modular reduction requires only a single multiplication by 19 — no expensive general-purpose reduction.

Constant-Time Arithmetic

The field fits in 256 bits, enabling constant-time operations on 64-bit processors. This prevents timing side-channel attacks.

Security Margin

Approximately 128 bits of security against the best known classical algorithms (Pollard's rho), the standard target for symmetric-equivalent strength.

Extension Field for Reed-Solomon

Zentalk's erasure coding operates over the extension field $\text{GF}(2^8)$, which consists of 256 elements -- each mapping directly to a single byte. Addition in $\text{GF}(2^8)$ is bitwise XOR, and multiplication is polynomial multiplication modulo the irreducible polynomial $g(x) = x^8 + x^4 + x^3 + x + 1$. The key property for erasure coding: every nonzero element has a multiplicative inverse, so systems of linear equations can be solved exactly, enabling the Reed-Solomon decoder to reconstruct missing data shards from surviving shards (see Chapter 5).

Elliptic Curve Cryptography

ECDLP

An elliptic curve over a field $F$ is the set of points $(x, y)$ satisfying a defining equation, together with a point at infinity $\mathcal{O}$ that serves as the identity element. Points on an elliptic curve form an abelian group under a geometric addition operation. This group structure enables scalar multiplication $Q = nP$ -- the foundation of elliptic curve cryptography -- which can be computed efficiently in $O(\log n)$ steps but cannot be reversed without solving the Elliptic Curve Discrete Logarithm Problem (ECDLP).

$$\text{Given: } P, \; Q = nP \text{ on an elliptic curve. Find } n.$$

Best known classical algorithm: Pollard's rho. Complexity: $O(\sqrt{q})$ where $q$ is the order of the group. For a 256-bit curve: $O(2^{128})$ operations.

ECDLP Security Guarantee

The security of all elliptic curve cryptography rests on this asymmetry: scalar multiplication is efficient ($O(\log n)$ operations), while the reverse -- recovering the scalar from the result -- is computationally infeasible ($O(2^{128})$ operations for a 256-bit curve). No sub-exponential classical algorithm for ECDLP is known.

Curve Comparison

Zentalk employs two curve representations, each optimized for a specific purpose. The following table compares their properties:

Property	Weierstrass (short form)	Montgomery (Curve25519)	Twisted Edwards (Ed25519)
Equation	$y^2 = x^3 + ax + b$	$By^2 = x^3 + Ax^2 + x$	$-x^2 + y^2 = 1 + dx^2y^2$
Addition formula	Requires special cases	x-coordinate only (ladder)	Complete (no special cases)
Field multiplications per add	12	5 (differential)	10
Constant-time by design	No (requires careful impl.)	Yes (Montgomery ladder)	Yes (complete formula)
Primary use in Zentalk	--	X25519 key agreement	Ed25519 signatures
Security level	Curve-dependent	128-bit classical	128-bit classical

Curve25519

Zentalk uses Curve25519, defined by Bernstein in 2006 [8]. Curve25519 uses the Montgomery form:

$$By^2 = x^3 + Ax^2 + x$$

where $A = 486662$, $B = 1$, and the field is $\text{GF}(2^{255} - 19)$.

The Montgomery form has several advantages for cryptographic implementation:

I. Montgomery ladder. The x-coordinate-only scalar multiplication algorithm processes each bit in constant time, naturally preventing timing side-channel attacks.

II. No need for y-coordinate. For Diffie-Hellman key agreement, only the x-coordinate is needed. X25519 takes a 32-byte scalar and x-coordinate as input and produces a 32-byte x-coordinate as output.

III. Clamping. The scalar is "clamped" before use to ensure correct bit structure:

scalar[0] &= 248      // Clear the three lowest bits
scalar[31] &= 127     // Clear the highest bit
scalar[31] |= 64      // Set the second-highest bit

This clears cofactor issues, prevents small-subgroup attacks, and guarantees constant-time execution.

Base point. The standard base point has x-coordinate 9: $G = (9, \langle\text{computed } y\text{-coordinate}\rangle)$.

X25519 function:

$$\text{X25519}(\text{scalar}, u) = \text{x-coordinate of } (\text{scalar} \cdot \text{point with } x = u)$$ $$\begin{aligned} \text{Public key generation:} \quad & A_{\text{pub}} = \text{X25519}(a_{\text{priv}}, 9) \\ \text{Key agreement:} \quad & \text{shared} = \text{X25519}(a_{\text{priv}}, B_{\text{pub}}) = \text{X25519}(b_{\text{priv}}, A_{\text{pub}}) \end{aligned}$$

The last equality follows from the commutativity of scalar multiplication:

$$a \cdot (b \cdot G) = b \cdot (a \cdot G) = (a \cdot b) \cdot G$$

Ed25519

For digital signatures, Zentalk uses Ed25519, which is birationally equivalent to Curve25519 but expressed in twisted Edwards form:

$$-x^2 + y^2 = 1 + dx^2y^2$$

where $d = -\frac{121665}{121666}$ in $\text{GF}(2^{255} - 19)$.

Zentalk uses Ed25519 [Bernstein et al., 2012] for digital signatures. Ed25519 uses deterministic nonce generation, eliminating the catastrophic failure mode of ECDSA where nonce reuse reveals the private key. Signatures are 64 bytes, verification requires one scalar multiplication, and the security level is approximately $2^{128}$ operations.

Deterministic Nonces Prevent Catastrophic Failure

Unlike ECDSA, where a single reused or biased random nonce leaks the private key (as occurred in the 2010 PlayStation 3 signing key extraction), Ed25519 derives nonces deterministically from the private key and message. The same inputs always produce the same signature, and no external randomness is required. This eliminates an entire class of implementation vulnerabilities.

Security properties:

• Existential unforgeability under chosen-message attack (EU-CMA) under the ECDLP assumption
• Resilience against fault attacks (deterministic nonce)
• 128-bit security level (group order approximately $2^{252}$)

AES-256-GCM

AES-256

The Advanced Encryption Standard (AES) is a symmetric block cipher that encrypts 128-bit blocks using a key of 128, 192, or 256 bits. Zentalk exclusively uses AES-256 (256-bit key) for maximum security margin.

AES-256 applies 14 rounds of substitution and permutation to 128-bit blocks using a 256-bit key. The best known attack (biclique, Bogdanov et al. 2011) reduces complexity to $2^{254.4}$, which remains computationally infeasible. AES hardware acceleration (AES-NI) enables encryption at memory bandwidth speeds on modern processors.

GCM Mode

AES-GCM is an Authenticated Encryption with Associated Data (AEAD) scheme that simultaneously provides confidentiality, integrity, and authenticity. GCM combines AES in counter mode (for confidentiality) with a Galois field authentication function (for integrity), producing an authentication tag that detects any modification to the ciphertext or associated data. The critical requirement is nonce uniqueness: reusing a nonce with the same key completely breaks GCM's security guarantees -- the authentication tag becomes predictable and ciphertext becomes malleable.

Parameters in Zentalk:

Parameter	Value	Justification
Key length	256 bits (32 bytes)	Maximum AES security; 128-bit quantum resistance
Nonce (IV) length	96 bits (12 bytes)	NIST SP 800-38D recommended for GCM
Authentication tag	128 bits (16 bytes)	Full GCM tag length; forgery probability $2^{-128}$
Block size	128 bits (16 bytes)	AES fixed block size

Critical: AES-GCM Nonce Uniqueness

If the same nonce is ever reused with the same key, AES-GCM's security completely collapses: an attacker can recover the XOR of both plaintexts and forge arbitrary authentication tags. Nonce uniqueness is not a recommendation -- it is an absolute requirement for correctness.

Zentalk prevents nonce reuse through:

1. Random nonce generation: crypto.getRandomValues(new Uint8Array(12)) for each encryption operation
2. IV tracking: Used IVs are recorded in memory and IndexedDB with a 7-day TTL
3. Constant-time comparison: IV uniqueness checks use constant-time comparison to prevent timing side-channels

Hashing and Key Derivation

SHA Family

Property	SHA-256	SHA-512
Output size	256 bits (32 bytes)	512 bits (64 bytes)
Block size	512 bits (64 bytes)	1024 bits (128 bytes)
Rounds	64	80
Word size	32-bit	64-bit
Preimage resistance	$O(2^{256})$	$O(2^{512})$
Collision resistance	$O(2^{128})$ (birthday bound)	$O(2^{256})$ (birthday bound)
Performance on 64-bit CPUs	Baseline	Faster (native 64-bit ops)
Usage in Zentalk	Address hashing, HKDF, HMAC	Safety numbers, Ed25519 internal

Zentalk uses SHA-256 and SHA-512 from the SHA-2 family (FIPS 180-4). Both are cryptographic hash functions that produce fixed-length outputs from arbitrary-length inputs, providing preimage resistance, second preimage resistance, and collision resistance at the security levels listed above. SHA-512 is used where Ed25519 requires it internally and where 256-bit collision resistance is needed (safety numbers); SHA-256 is used for all general-purpose hashing and as the basis for HMAC and HKDF.

HMAC-SHA256

HMAC (Hash-based Message Authentication Code) constructs a keyed pseudorandom function from SHA-256, enabling message authentication and key derivation. HMAC-SHA256 is a PRF under the assumption that SHA-256's compression function is a PRF -- a stronger assumption than collision resistance that has held under decades of cryptanalytic scrutiny.

Zentalk uses HMAC-SHA256 in two critical contexts:

Chain Key Derivation

In the Double Ratchet: $\text{MK} = \text{HMAC}(\text{CK}, \texttt{0x01})$, $\text{CK}' = \text{HMAC}(\text{CK}, \texttt{0x02})$

Session Integrity

HMAC over serialized session state to detect tampering.

HKDF

HMAC-based Key Derivation Function (HKDF) converts arbitrary input key material into one or more cryptographically strong keys. It operates in two phases: Extract concentrates unevenly distributed entropy from input key material into a fixed-length pseudorandom key using a salt as domain separator; Expand generates output key material of arbitrary length using an info parameter for context binding -- different info strings ensure keys derived for one purpose cannot be used for another.

Usage in Zentalk:

Context	IKM	Salt	Info	Output Length
X3DH shared secret	$\text{DH1} \| \text{DH2} \| \text{DH3} [\| \text{DH4}]$	X3DH_SALT (32 bytes)	"Zentalk X3DH Key Agreement"	32 bytes
DH ratchet step	$\text{X25519}(dh_{\text{priv}}, dh_{\text{peer}})$	Previous root key (RK)	"Zentalk Double Ratchet Root"	64 bytes (split: 32 RK + 32 CK)
Hybrid X3DH	$\text{classical\_secret} \| \text{kyber\_secret}$	HYBRID_X3DH_SALT	"zentalk.hybrid-x3dh.v1"	64 bytes
Sealed sender key	ECDH shared secret	32 zero bytes	"zentalk.sealed-sender.v1"	32 bytes (AES-256 key)
Backup encryption	$\text{SHA-256}(dh_{\text{Private}})$	Random 16-byte salt	"zentalk-mesh-backup"	32 bytes (AES-256 key)
Group message key	Owner identity key seed	"group:{id}:messages "	"Zentalk Group Messages v1"	32 bytes

PBKDF2

For deriving keys from potentially low-entropy inputs (passwords, wallet signatures), Zentalk uses PBKDF2 with SHA-256. PBKDF2 applies HMAC-SHA256 iteratively to make brute-force attacks computationally expensive -- each guess requires the full iteration count to verify.

Iteration counts in Zentalk:

Context	Iterations	Justification
Mesh backup encryption	600,000	OWASP 2023 recommendation for PBKDF2-SHA256
Phone auth key derivation	600,000	Same standard, protects low-entropy passwords
Phone hash (v1, legacy)	100,000	Legacy accounts, backward compatibility
Phone hash (v2, current)	310,000	Upgraded for new accounts
IndexedDB master key	600,000	Protects stored E2EE sessions

The 600,000 iteration count provides approximately 200ms of computation on modern hardware (2024 MacBook Pro), which is imperceptible to users but makes brute-force attacks requiring billions of attempts computationally prohibitive.

Scrypt

Key Stretching: PBKDF2 vs Scrypt

PBKDF2 is CPU-bound: its cost scales linearly with iteration count but requires negligible memory, making it vulnerable to massively parallel GPU/ASIC attacks. Scrypt is memory-hard: it requires both CPU time and a large block of RAM (32 MB in Zentalk's configuration), making hardware-accelerated brute-force attacks orders of magnitude more expensive per guess.

Property	PBKDF2-SHA256	Scrypt
Hardness type	CPU-bound (iterative)	Memory-hard
Memory requirement	Negligible (~256 bytes)	$N \cdot r \cdot 128$ bytes (32 MB)
GPU attack resistance	Low (highly parallelizable)	High (memory bottleneck)
ASIC attack resistance	Low	Moderate-High
Configuration in Zentalk	600,000 iterations	$N=2^{15}$, $r=8$, $p=1$
Approximate time (2024 hardware)	~200 ms	~100 ms
Use case in Zentalk	General key derivation	E2EE key backup envelope

For the most security-critical key derivation -- the E2EE key backup envelope that protects the user's identity keys -- Zentalk uses Scrypt with memory-hard parameters: $N = 2^{15} = 32{,}768$ (CPU/memory cost), $r = 8$ (block size), $p = 1$ (parallelization), $\text{dkLen} = 32$ bytes. The computation requires approximately 32 MB of memory, making GPU and ASIC-based brute-force attacks significantly more expensive than for PBKDF2.

Security Levels

The following table maps each cryptographic primitive used in Zentalk to its key size, the classical security level (bits of security against the best known classical attack), and the post-quantum security level where applicable.

Primitive	Key / Parameter Size	Classical Security	Post-Quantum Security	Best Known Attack
X25519	256-bit scalar	128-bit	~64-bit (Grover + Shor)	Pollard's rho: $O(2^{128})$
Ed25519	256-bit scalar	128-bit	~64-bit (Grover + Shor)	Pollard's rho: $O(2^{128})$
AES-256-GCM	256-bit key	256-bit	128-bit (Grover)	Biclique: $O(2^{254.4})$
SHA-256	256-bit output	128-bit (collision)	85-bit (Grover for collision)	Birthday: $O(2^{128})$
SHA-512	512-bit output	256-bit (collision)	170-bit (Grover for collision)	Birthday: $O(2^{256})$
Kyber-768 (ML-KEM)	2400-byte public key	~183-bit	~161-bit quantum	Module-LWE lattice attacks
Dilithium3 (ML-DSA)	1952-byte public key	~183-bit	~161-bit quantum	Module-LWE/SIS lattice attacks

Post-Quantum Readiness

Zentalk's classical primitives (X25519, Ed25519) provide 128-bit security against today's computers but would be vulnerable to a sufficiently large quantum computer running Shor's algorithm. The hybrid X3DH protocol (Chapter 3) combines classical X25519 with post-quantum Kyber-768, ensuring that messages remain confidential even if quantum computers become practical -- an attacker must break both the classical and post-quantum schemes simultaneously.

Summary

Primitive	Algorithm	Security Level	Usage in Zentalk
Key Agreement	X25519 (Curve25519)	128-bit classical	DH in X3DH and Double Ratchet
Digital Signatures	Ed25519	128-bit classical	Prekey signing, message signing
Symmetric Encryption	AES-256-GCM	256-bit / 128-bit quantum	Message and chunk encryption
Hash Function	SHA-256	128-bit collision resistance	Address hashing, checksums
Hash Function	SHA-512	256-bit collision resistance	Safety numbers, Ed25519 internal
Key Derivation	HKDF-SHA256	PRF security	X3DH, Double Ratchet, sealed sender
Key Stretching	PBKDF2-SHA256	600K iterations	Passwords, backup encryption
Memory-Hard KDF	Scrypt	$N=2^{15}$, $r=8$	V3 key backup envelope
Post-Quantum KEM	Kyber-768 (ML-KEM)	NIST Level 3 (~183-bit classical)	Hybrid X3DH
Post-Quantum Sig	Dilithium3 (ML-DSA)	NIST Level 3 (~183-bit classical)	Hybrid authentication
Erasure Coding	Reed-Solomon over $\text{GF}(2^8)$	10+5 MDS	Mesh data redundancy