Example: Real-time stock quotes

Consider a real-time stock quote broadcasting system. The main requirement is a low authentication delay for the real-time data, hence buffering on either the sender or receiver side is not an option. Another requirement is the robustness to packet loss, so receivers can instantly and efficiently authenticate each message they receive, despite previously lost packets. To the best of our knowledge, no previous protocol satisfactorily addresses these requirements.

We assume the following system requirements. Receivers are time synchronized with the sender, with a maximum time synchronization error of ten seconds ($\delta =\; 10$s). The sending rate is approximately $10$ packets per second ($\beta =\; 10$ p/s). The sender has $t=1024$ SEAL chains. We set the security parameter $1/P$_f=2⁵⁸ (the attacker needs to perform $258$ hash function computations within time $\delta$ to forge a signature). We set $\gamma =1/16$, so the adversary can know up to $r=t\gamma =64$ active SEALs.

For this example, we set $m$₁ = 128, m₂ = 64, k=16. We then compute $n$ to get $P$_S close to $50\%$ and compute the corresponding $P$_f assuming that the adversary knows $64$ SEALs. From Table 1 we pick $n\; =\; 136$, and the resulting forging probability is $P$_f=2^-58.03. The signature size is about $128$ bytes.

Each signature discloses $16$ SEALs, hence after $4$ packets an attacker knows at most $64$ SEALs. Each row of the SEAL chains is active for $400$ms ($10$ packets/s and $4$ packets sent per row). Because $\delta =10s$ is the maximum time synchronization error, we cannot disclose any SEALs of the next row for $10$ seconds. Otherwise we would disclose more SEALs of the previous rows which the adversary could use to forge a signature. This requires that we use $25$ instances of the BiBa scheme in parallel in a round-robin fashion.

The sender overhead to generate a signature is approximately $(1024T$_G + T_H)/P_S. On a $800$ MHz Pentium III the sender can compute $\approx 106$ MD5 hash function evaluations per second [19] (uniprocessor, software-based implementation of MD5). On this architecture, generating one BiBa signature takes approximately $2$ ms, about $5$ times faster than to generate a $1024$-bit RSA signature using the OpenSSL library. BiBa enjoys a linear speedup for multiple processors, which a hardware implementation can easily exploit. With maximum parallelization, generating a BiBa signature only requires two sequential hash function computations.

Signature verification (excluding the verification of the authenticity of the SEALs) only requires $17$ hash function evaluations. However, the SEAL verification is about $256$ PRF evaluations on average. This is because the $1024$ active SEALs of one time period are amortized only by $4$ packets. On a $800$ MHz Pentium III the sender can compute $\approx 5106$ RC5 function evaluations per second [20] (uniprocessor, software-based implementation of RC5). On this architecture, verification takes on the order of $50\; \mu$s, which is about $20$ times faster than verifying a $1024$-bit RSA signature.

Decreasing the security requirement and increasing the number of disclosed SEALs would greatly diminish this number (e.g. If we allow the adversary to know $128$ SEALs which would result in $P$_f = 2^-41.2, then the verifier only needs to perform $128$ PRF evaluations on average to authenticate the SEALs). Using either extension A or B would reduce the verification overhead to $17$ hash function and $16$ PRF computations, however with the tradeoffs we describe in Section 4.