cfrg/draft-irtf-cfrg-vdaf

XofTurboShake128: Consider bumping SEED_SIZE from 16 to 32 bytes

Closed this issue · 3 comments

cjpatton commented

When thinking about Prio3 robustness (ia.cr/2023/130, Theorem 1) we (err, I, really) have been ignoring the term that depends on the size of the seed: $(q_\text{RG} + {q_{\text{Prep}}}^2) / 2^{\kappa -1}$

  • $q_\text{RG}$ - the number of random oracle queries (XofTurboShake128 is modeled as an RO)
  • $q_\text{Prep}$ - the number of (potentially malicious) reports consumed in a given DAP task
  • $\kappa$ - the seed size (16 bytes for XofTurboShake128)

As @albertpl pointed out in #318 (comment), the bound becomes vacuous after $q_\text{Prep}=2^{63.5}$ reports (since $(2^{63.5})^2 = 2^{\kappa -1}$).

While it's doubtful that we'd ever consume so many reports in a single task, it's not a bad idea to have a more conservative safety margin. 32 bytes seems like a reasonable choice.

cjpatton commented

Update: the term we're looking at here deals with the probability of two reports deriving the same joint randomness. While our main concern here was the number of online attacks against robustness (and whether a birthday attack is too close for comfort, given the current seed size), @bwesterb pointed out the possibility of an offline attacker finding pair of distinct reports that derive the same joint randomness seed. This is clearly a possibility: an offline attacker can try to find joint randomness hints that produce the same joint randomness seed, or two reports that produce the same joint randomness hints.

This points to a bug in the current proof. The ${q_\text{Prep}}^2/2^\kappa$ is actually more like $(q_\text{RG} + q_\text{Prep})^2/2^\kappa$. @hannahdaviscrypto and I are updating the paper and will put it on eprint soon.

Certainly ${q_\text{RO}}^2/2^\kappa$ is too weak, so we'll need to fix this. Rather than double the seed size for XofTurboShake128, we propose a more targeted fix: to double the size of the joint randomness seed only, and adjust the joint randomness derivation accordingly. See PR #407.

cjpatton commented

After pondering the previous PR, we decided it would be safer to also bump the joint randomness hints, at which point it's simpler to bump the seed size in all cases. See #407 (comment).