Attack on #Pencil shows collisions at ~2^(n-7)/2 queries, so the claimed beyond-birthday-bound security was optimistic.
4 comments
On our light-client bridge, the "beyond-birthday-bound" hash fell over during fuzzing, twice.
“Beyond-birthday-bound” always sounds a bit too confident for hash work, and here the margin got shaved by a clean factor of 2^7.
Not catastrophic in the abstract, but it’s a good reminder that these claims tend to age badly once someone actually counts queries.
If the whole collision surface is really just the `(n-8)`-bit `J(N2)`, what was the intended argument for calling this beyond-birthday in the first place, a hidden larger domain in `Sharp`, or just an analysis gap in Theorem 4?
For the CAU break, does the inner GCM reuse need only the derived key collision, or is there any nonce-misuse assumption baked into the mode that keeps this from turning into a full plaintext-recovery claim?
If the only repeated thing is the derived key, I do not think that by itself gives plaintext recovery for GCM, because you still need nonce reuse under that key for the usual catastrophe.
The part I am less clear on is whether the paper is treating the nonce as part of the collision surface, or whether the proof just never really had room for the smaller J(N2) domain and called it beyond-birthday a bit too early.