HomeTechnical ArchitecturePhilosophyContactRequest access
All articles

Contact Discovery

Algorithm: Known-Answer Testing

8 min read

Every other article in this series makes a server prove something. This one is about what you do when proving is impossible — when the check you would need requires the very secret the protocol exists to keep from you. The answer is older than cryptography and slightly delightful: hide questions you already know the answer to among the real ones.

Prerequisites: none, really. It helps to have read The Verifiable OPRF for the attack this defends against, and Rounding by Oblivious Transfer for the second one.

1. Two attacks that proofs do not reach

The discovery server holds a secret key s and answers F_s(x) obliviously. Two ways it can misbehave keep coming up, and they have the same shape.

The per-victim key. Nothing forces the server to use the same s for everybody. If it answers you under a key s_you that it uses for no one else, every value you derive is stamped with a marker only you produce. You cannot see this: an OPRF output looks pseudorandom whatever key made it, and obliviousness protects your input, not the server's honesty.

The nudged rounding table. The final step of the OPRF rounds a shared value using a small lookup table the server builds. You open exactly one entry of 256. A server that builds that table from a slightly different number shifts your output — and, if it can observe whether your subsequent lookup succeeded, learns one bit about your secret input. Article 08 covers how much of this is closed by proofs and commitments; a sliver survives.

We do prove a great deal about the server. It proves it used the committed key for the linear part; it proves the rounding parameters came from the committed mask; it commits to the tables before it learns your choices. What is left over in both cases has the same awkward form:

To check the value in front of you, you would need the secret the protocol is specifically designed to withhold from you.

You cannot verify a single table entry without knowing the mask that hides the unrounded product. That is not an engineering oversight. It is the protocol working correctly.

2. The trick: ask a question you already know the answer to

Suppose you want to know whether a calculator is lying to you, but you cannot check its arithmetic — the numbers are too big. You can still slip in 2 + 2 occasionally.

That is the whole idea. A canary is an input whose value is public and whose correct output under the honest key is published in advance. Feed one through the exact same protocol as a real query and you get a value you can compare against the published one. A server answering under any other key produces a mismatch.

Three properties make it work, and all three matter:

  1. The canary is indistinguishable from a real query. This is the load-bearing one. Your inputs travel as lattice ciphertexts, so the server sees a random-looking blob whichever it is. It cannot answer canaries honestly and real queries dishonestly, because it cannot tell them apart.
  2. Its correct answer is public. A canary's input is a fixed, published constant, so F_s(canary) reveals nothing about s that the server has not already committed to — it is just a PRF output at a point everyone knows. Publishing it costs nothing.
  3. You choose where they go, secretly. The canaries are shuffled in among the real queries using a cryptographic random number generator. A predictable position would let the server step around them, which would defeat the entire mechanism. (In the implementation this is a one-line detail with a comment shouting about it, because it is exactly the kind of thing a later refactor "simplifies.")

3. How well does it work? A calculation worth doing yourself

Say you resolve n real contacts and hide c canaries among them, for B = n + c sessions total. A server wants to tamper with one particular contact's session — but it has no idea which slot that is. So it picks a slot and tampers.

Two things can happen:

  • The slot holds a canary. Probability c/B. It is caught.
  • The slot holds the contact it actually wanted. Probability 1/B. It learns something.

Take the ratio:

P(caught)          c/B
-----------  =  ---------  =  c
P(hit target)     1/B

For every successful probe, it expects c detections. With 32 canaries, a server that eventually lands on the contact it was after has been caught about 32 times getting there.

Two things about this result are worth sitting with. First, n cancelled — the guarantee does not weaken as the address book grows, which is not what most people guess. Second, the attacker cannot improve its odds by being greedy: tampering with many slots to raise the chance of hitting the target raises the chance of hitting a canary in exactly the same proportion. Tampering with all of them, which would guarantee hitting the target, guarantees hitting every canary too.

The strategy has no good version. That is the nicest thing you can say about a defence.

4. What it costs, and what it does not buy

A canary is a real query — the server does the same work, the wire carries the same bytes — so c canaries cost c extra evaluations. That makes the parameter a straightforward dial: more canaries, more certainty, more work.

The implementation uses a rate rather than a fixed count: roughly one canary per four real resolutions, with a floor of four and a cap. The floor matters because someone adding a single contact still deserves protection (four canaries among five sessions is an 80% chance of catching any tamper). The rate matters because a fixed count would dilute — 32 canaries among 32 contacts is strong, 32 among 5,000 is thin. And the ratio result from section 3 tells you what you are buying at each setting, which is why it is worth deriving rather than picking a number that feels safe.

Now the honest part, because this is where known-answer testing differs from everything else in this series.

It detects; it does not prevent. A server that gets lucky — tampers once, misses every canary — did learn its bit. What it cannot do is repeat. Sustained probing is caught with probability approaching one, and one-shot attacks are the only ones left. In this system that ceiling is lower than it sounds: a resolved contact is cached forever, so a phone number is resolved once per install. A reinstall or a new device does open another attempt — multi-device makes that a real path, worth naming — but those are rare, user-visible events the server cannot provoke. The pace of attempts is set by how often you add a device, not by the attacker's patience, and every attempt walks the same minefield.

A miss is not a bug report. When a canary comes back wrong, the client does not retry or degrade — it aborts the whole pass, writes nothing to its cache, and raises an alarm. This is the correct response to evidence of a cheating server, which is a different category from a network error. Treating it as transient would silently discard exactly the signal the mechanism exists to produce.

Everything or nothing. Because a tampered pass might have hit real slots too, a canary failure invalidates the entire batch, not just the canary. Results are staged and committed only when every canary has checked out.

5. Where else this shows up

The same mechanism guards the admission token mint, where the worry is a per-user issuer key turning the token's cleartext key identifier into a tracking tag. There the canary is one of three layers: the key set is committed to a transparency log so it cannot be equivocated, published in full so a per-user key would visibly bloat the list, and then a canary checks the server actually used the key it named.

That layering is the general lesson. A commitment says what the key is. Publication makes it the same for everyone. A known-answer test proves the server actually used it. They defend different things, and the third is the only one that survives when you cannot verify the answer directly.

6. Summary

  • Some server misbehaviour is out of reach of proofs, because checking the value would require the secret the protocol is built to withhold.
  • A canary is a public input with a published answer, run through the identical path and compared. Indistinguishability from real queries is what makes it work — the server cannot tell which sessions are safe to cheat on.
  • Hiding c canaries among n real queries yields c expected detections per successful probe, independent of n, and no tampering strategy improves that ratio.
  • The cost is c extra evaluations; the implementation uses a rate with a floor rather than a fixed count.
  • It detects rather than prevents, which is the right goal once the leak is one-shot: a failure aborts the pass, commits nothing, and raises an alarm rather than being retried away.

References

  • Known-answer tests are standard practice in cryptographic validation (NIST's KAT vectors for algorithm certification are the familiar example) — the twist here is hiding the test among live traffic so the party under test cannot recognise it.
  • Cut-and-choose in secure computation — the same "commit to many, open some at random" bargain, from which the probability accounting in section 3 is borrowed.
  • S. Dietz, S. Tessaro, "Fully Malicious Authenticated PIR," CRYPTO 2024 — validation queries indistinguishable from real ones, the closest formal treatment of this shape.
  • Wikipedia: Cut-and-choose, Known-answer test, Canary trap.

Back up to The Verifiable OPRF, where the per-victim-key attack starts, or to Contact Discovery.