Plotkin Attacks! On the (Mis)use of Raptor Codes in Asynchronous Verifiable Information Dispersal
Some asynchronous verifiable information dispersal (AVID) and data-availability protocols certify that a disperser's message is available once $2f+1$ of $n=3f+1$ parties, at most $f$ of them Byzantine, attest that they hold their erasure-coded fragments, and defer reconstruction and validation of the encoding until later. We call this design pattern reconstruct-later AVID. If the $f$ Byzantine attesters later withhold their fragments, reconstruction must succeed from the $f+1$ honest fragments that remain, and a Byzantine disperser chooses which $f+1$ after seeing the encoding symbols assigned to the honest parties. We call a subset of fragments that does not determine the message bad. Raptor codes are a tempting choice here: with modest coding overhead they have very small decoding-failure probability under random erasures, and a preliminary Walrus design and an earlier Walrus testnet used RaptorQ in this way. We show that the pattern is insecure with the standardized Raptor codes R10 (RFC 5053) and RaptorQ (RFC 6330). For a message of $K$ input symbols, every assignment of R10 encoding symbols to the honest parties contains a bad $(f+1)$-subset whenever $K>\lfloor\log_2(2f+2)\rfloor$, and every RaptorQ assignment whenever $K>7H_{\mathrm{HDPC}}+\lfloor\log_2(2f+2)\rfloor$, where $H_{\mathrm{HDPC}}$ is RFC 6330's number of high-density parity-check symbols. Under slightly stronger conditions, randomized polynomial-time algorithms find such subsets, and an implementation of the RaptorQ attack defeats an RFC 6330 decoder on every adversarial subset tested. The key ingredient is the Plotkin bound, which forces a nonzero input whose encoded image has low Hamming weight. For RaptorQ at $n=3f+1$, an empirical attack over $\mathbb{F}_{256}$ succeeds at every tested $f$ from $9$ to $45$ with $K=f+1$, far below the $f=77$ at which the bound above first applies, and empirical attacks over $\mathbb{F}_4$, $\mathbb{F}_{16}$, and $\mathbb{F}_{256}$ succeed at values of $K$ well