Security and Editorial Feedback on the TLOS Paper

[keewoolee]

1. I believe that, if we want this paper to be reviewed properly—both internally and later externally—the description needs to be much more concise, especially in Section 4.4. We should aim for a shorter yet more precise description.
2. Is “planted” in Section 4.4 public or secret? I assume it is intended to be public, since otherwise the party who knows the secret would also need to solve the puzzle, which the paper states would take approximately 2.5 million years using a GPU.
3. If “planted” is public, then I don’t think Layer 4 adds any security to the system. In fact, I believe it introduces additional attack surface. An adversary does not need to solve the puzzle by brute-forcing all ternary keys or by running BKW or other sophisticated attacks. (Given BKW attack, it is already incorrect to argue that the puzzle provides 2^{76} computational security; it is below 2^{40}.) Instead, an attacker can simply brute-force the space of low-entropy secrets, compute H("planted" | secret), and check whether it solves the puzzle. As a result, this construction effectively provides an easy way to recover the secret if it has low entropy, regardless of any other defenses in place.
4. Layer 2 uses H(secret) as the LWE secret, which results in a small key space when the secret has low entropy. This significantly simplifies attacks on the LWE instance. Consequently, the arguments presented in Section 6.2 do not hold.

[igor53627]

We have opened two PRs to address the cryptographic vulnerabilities identified in the review:

1. Fix Deterministic Noise (The Oracle): fix(security): decouple noise generation from public seeds #67 decouples noise generation from public seeds. The error terms e are now generated from secure entropy and discarded, preventing the linear algebra attacks (Point 2 of feedback).
2. Harden LWE Parameters: feat(security): increase LWE noise sigma to 25.0 #69 increases the LWE noise σ from 8.0 to 25.0, significantly increasing the hardness of the LWE instance against lattice reduction attacks.

Next Steps:
We are currently investigating the BKW attack feasibility on Layer 4 (Point 3 of feedback) and will adjust the puzzle parameters (, m, q$) if the security estimate is confirmed to be below our target floor.

[igor53627]

3. Harden Layer 4 Puzzle: feat(security): harden puzzle layer params (n=128, m=192) #74 increases the planted puzzle dimension from $n=48$ to $n=128$. This raises the brute-force floor to $3^{128} \approx 2^{203}$ and significantly mitigates the BKW/lattice reduction risks mentioned in the review (Point 3).

[keewoolee]

Elaboration on point 3 (a similar argument also applies to point 4): Increasing the LWE parameters does not improve security. Regardless of how hard the LWE instance is made through parameter selection, the puzzle remains easy to solve because an attacker can simply brute-force the space of low-entropy secrets, compute H("planted" | secret), and check whether it solves the puzzle, thereby recovering the secret.

[igor53627]

You're correct. We ran GPU benchmarks to quantify the dictionary attack cost for Layer 4.

Benchmark Results (A100)

Current Parameters (m=192, n=128)

Metric	Rate	Per-guess cost
CPU keccak derivation	13K/sec	75 µs
GPU keccak (estimated from hashcat)	222M/sec	0.005 µs
GPU matrix verification	5.8M/sec	0.17 µs
Effective GPU attack rate	5.8M/sec	0.17 µs

Dictionary Attack Times (1 GPU)

Entropy	Dictionary Size	Time
2^20	1M passwords	181 ms
2^30	1B entries	3.1 min
2^40	1T entries	2.2 days

Parameter Sweep: Can We Add More Overhead?

We tested whether increasing puzzle dimensions would help:

Config	Est. Gas	% Block	GPU Rate	2^20 time
m=192, n=128 (current)	8.6M	14%	3.5M/sec	300ms
m=384, n=128	17.2M	29%	29.4M/sec	36ms
m=512, n=128	22.9M	38%	22.6M/sec	46ms
m=768, n=128	34.4M	57%	15.3M/sec	68ms
m=1024, n=128	45.9M	76%	11.9M/sec	88ms

Counterintuitive finding: GPUs are optimized for larger matrix operations. Increasing m from 192→384 makes the attack 8x faster (3.5M → 29.4M/sec) due to better GPU utilization. The current m=192 is actually near a local minimum for attacker throughput.

Conclusion

Layer 4 provides ~0.17-0.29 µs per-guess overhead on GPU, which is insufficient to protect low-entropy secrets. The "3^128 brute-force floor" only applies to recovering s directly from (A,b) without guessing the secret—it does not change dictionary attack asymptotics.

For dictionary attacks:

AttackCost = |Dictionary| × 0.17µs (GPU)
AttackCost = |Dictionary| × 75µs (CPU)

Documentation Updates

We will update the documentation in PR #74 to:

1. Remove misleading claims about low-entropy protection and "unless rate-limited" caveats (rate limiting doesn't apply to offline attacks)

2. State explicitly that Layer 4 adds per-guess computational overhead but does NOT provide entropy amplification

3. Clarify the 3^128 claim: This is the brute-force floor for recovering the planted solution s from public (A,b) without knowing the secret. For dictionary attacks where the attacker enumerates candidate secrets and derives s = H("planted" || secret), security equals |Dictionary| × verification_cost

4. Recommend high-entropy secrets for security against offline adversaries

Benchmark Script

The full benchmark is available at scripts/attacks/layer4-puzzle/modal_puzzle_benchmark.py. Run with:

modal run modal_puzzle_benchmark.py --gpu a100
modal run modal_puzzle_benchmark.py --sweep  # Parameter sweep

[keewoolee]

4. Recommend high-entropy secrets for security against offline adversaries

@igor53627 But then, what would TLOS be used for, given that the TLOS paper clearly says: "TLOS is not designed for: High-entropy secrets: Random 256-bit keys are already secure with keccak256."

[igor53627]

Thanks for the detailed review — we’ve addressed the points in the paper and docs. Summary of changes:

1. Section 4.4 length
   We shortened the “Protocol Flow” section in the long paper (compressed Deployment/Solving/Attack to 2–3 bullets each) and tightened the short paper’s Layer‑4 discussion accordingly.

2. “Planted” public or secret
   Clarified that the puzzle seed and (A, b) are public, while the planted solution (s^*) is sampled off‑chain and not stored on‑chain. This is now stated explicitly in the Layer‑4 construction and in the “Common Misunderstandings” appendix.

3. Layer‑4 behavior, dictionary attacks, and randomness binding
   We now state explicitly that Layer‑4 provides a one‑time floor for recovering the planted solution directly from ((A,b)), and is not a per‑guess KDF. Offline dictionary attacks on low‑entropy secrets remain dictionary‑bound.
   Commit‑time randomness binding prevents precomputation and forces per‑instance offline work (the effective input changes per commit), but it does not rate‑limit offline enumeration; PoW is the online throttle.

4. Layer‑2 key derivation / low‑entropy secrets
   We clarified the threat model: the LWE key is derived from input (and puzzle solution), but this does not change low‑entropy asymptotics. The papers now consistently say low‑entropy secrets remain dictionary‑bound, and the puzzle only adds a one‑time non‑enumerative floor.

If you’d like, I can point to specific sections/line numbers, but the changes are now reflected in both tlos.tex and tlos-paper.tex, plus the appendix clarification.

[igor53627]

Agreed — and we now state this explicitly. If the goal is purely offline security, the best recommendation is high‑entropy secrets, because keccak alone suffices for equality checks. TLOS is not meant to replace that.

Where TLOS adds value is when you can’t assume high entropy (human secrets, short ranges) or when you need to hide the predicate / logic itself, not just a value. In that regime, TLOS provides (i) per‑guess cost amplification, (ii) a one‑time puzzle floor for non‑enumerative recovery, and (iii) optional PoW for online throttling. But for offline adversaries with truly high‑entropy secrets, we recommend keccak (or standard hash‑commit) rather than TLOS.

We’ll make sure this recommendation is clear and prominent in the “when to use / when not to use” sections.

[keewoolee]

We shortened the “Protocol Flow” section in the long paper (compressed Deployment/Solving/Attack to 2–3 bullets each) and tightened the short paper’s Layer‑4 discussion accordingly.

I think the description should be not only short but also precise. The current version leaves too many things ambiguous. I strongly recommend writing it in a pseudo-code style, with an explicit specification of the inputs, outputs, and intermediate variables and whether each is public or private.

[keewoolee]

For instance, are the Layer-2 LWE ciphertexts public? If so, Layer 2 uses H(secret) as the LWE secret, which results in a small key space when the secret has low entropy. This significantly simplifies attacks on the LWE instance and, more problematically, provides a direct way to extract the secret in the low-entropy setting: an attacker can simply brute-force the space of low-entropy secrets, compute H(secret), and check whether it solves the puzzle, thereby recovering the secret. For this reason, the proof sketch given in Proposition 6.1 is incorrect.

Where TLOS adds value is when you can’t assume high entropy (human secrets, short ranges) ... (i) per‑guess cost amplification, (ii) a one‑time puzzle floor for non‑enumerative recovery, and (iii) optional PoW for online throttling

Under the current design, TLOS does not appear to provide any additional value when the secret is low-entropy.

or when you need to hide the predicate / logic itself, not just a value.

If we want to present it this way, we need to update the applications to match the narrative as well as the scheme APIs.

[keewoolee]

I’m also adding a comment here on the updated version: https://prism.openai.com/?u=9297363b-c24c-4298-b23b-cc1fa98b34a7&pg=1&m=tlos.tex&d=7

Switched Layer 4 puzzle to uniform-mod-q secret

But then the legitimate solver would need to solve this puzzle just like an attacker. Is this the intended behavior? If the puzzle is too hard, it imposes a significant cost on the legitimate solver; if it is too easy, it does not provide meaningful defense.