One-way SEAL Chains

For our authentication protocol, we need a method such that the receiver can instantly authenticate the SEALs when it receives them, and that the SEALs are automatically replenished. We use one-way chains to achieve the self-authenticating property of SEALs and for replenishment. One-way chains are used in many schemes, for example by Lamport in a one-time password system [11], and the S/Key one-time password system [8]. We use the the PRF $F$ to generate the one-way SEAL chains, and the PRF $F\text{'}$ to generate a one-way salt chain. The sender first generates the one-way salt chain of length $l$, $\{K$_i}_1il, using the PRF $F\text{'}$ as follows: the sender randomly selects $K$_l (of length $m$₁ bits): $K$_l R ← {0,1}m₁, and then recursively computes all other salts: $K$_i = F'K_i+1(0) ().

The sender then generates a set of one-way SEAL chains, $\{S$_{i, j}}_{1it, 1jl}, where $S$_{i, _} forms a one-way chain as Figure 3 shows. The SEAL chains are constructed as follows. The sender first randomly selects all the seed SEAL values $S$_{_, l} of length $m$₂ bits: $S$_{i, l} R ← {0,1}⁸⁹⁹m₂ $(1\le i\le t)$. The sender then computes all other SEAL values recursively: $S$_{i, j} = F₉₀₁S_{i, j+1}(K_j+1) . Note the way we use the salts of the one-way salt chain to derive the SEAL values, such that an attacker first would need to find a pre-image of the salt of the one-way salt chain before it can try to find pre-images for the SEAL chains. We chose this specific construction to allow for relatively compact SEALs, while the longer salts mitigate attacks to find other pre-images for the SEALs by pre-computation. However, if the SEALs are long enough to prevent such attacks, the one-way salt chain may not be necessary.

   
Figure 4: Using one-way chains to construct SEAL

The sender divides the time up into time periods of equal duration $T$_d. In each time period $i$, the SEALs $S$_{_, i} and the salt $K$_i are active. Figure 3 shows the time periods and the corresponding active SEALs and active salt. As time advances an entire row of SEALs expires and a new row becomes active. The sender publishes each salt at the beginning of the time period when it becomes active, but the sender only discloses the active SEALs of a time period that are part of a BiBa signature.

To bootstrap a new receiver we assume for now that the sender sends it all the SEALs and the salt of a previous time period over an authenticated channel. We present extensions that provide more efficient receiver bootstrapping in Section 5. It is clear that a receiver who knows all the authenticated SEALs and salt of a time period can authenticate SEALs and salts of later time periods. For example, assume the receiver knows the authentic salt $K$_i of time period $i$. When the receiver receives $K$_i+1 of the following time period the receiver authenticates it by verifying $K$_i ? = F'K_i+1(0). The receiver authenticates SEALs by following the one-way SEAL chain back to a SEAL that it knows is authentic.