Yes, the problem of multicast one-way authentication can be solved using symmetric cryptography only, assuming (at least) one of the following applies (there might be other ways):
- we trust each receiving party to hold a common secret key secret, and not to use it nefariously;
- we accept overhead in the broadcasted message growing linearly with the number $n$ of recipients, in the order of $n\cdot b$ bits for $2^{-b}$ odds of forgery;
- the broadcaster and receivers share some time reference, and we can tolerate a delay (a small multiple of the time uncertainty) for the authentication of a message.
In all cases, the general idea is to include with the message a Message Authentication Code made with a key known to both the sender and receiver.
In 1 we assume a common secret key, and that's the most classic use of a MAC; but extracting the common secret key from any receiver breaks the whole security.
In 2, that problem is solved by using keys unique to each receiver, derived from a master key and a device identifier. That's a most common key management technique for Smart Cards. Something similar to the following illustrative example may have been used for software updates in the field of pay TV:
- At manufacturing, each receiver device gets a public consecutive serial number $j$, starting from $j_0$, and a (so-called diversified) secret key $K_j=\operatorname{HMAC-SHA-256}(K,j)$ where $K$ is a master secret key.
- Each message $M$ (firmware update) is hashed to $H=\operatorname{SHA-256}(M)$, and it is broadcast
- the length of $M$
- $M$ (perhaps with a version number at some fixed offset)
- the concatenation of all the $\operatorname{HMAC-SHA-256}(K_j,H)$ truncated to $b$ bits, in increasing order of $j$ (which can be computed from $K$, $j$, and $H$).
- Each receiver
- gets the length of $M$, and checks it is within allowable bounds
- gets $M$ (perhaps checking the version number is higher than the current version; this avoids replay)
- computes $H=\operatorname{SHA-256}(M)$
- skips $(j-j_0)\cdot b$ bits (where $j_0$ is the first serial number)
- gets the next $b$ bits
- checks that against $\operatorname{HMAC-SHA-256}(K_j,H)$ truncated to $b$ bits
- only then proceeds to use $M$.
Security trivially follows from the PRF properties of HMAC-SHA-256, and collision resistance of SHA-256; but a practical issue is the bandwidth used.
In 3, both security and bandwidth issues are solved, based on a shared time reference. A chain of keys is set up at initialization time, that is revealed link per link by the broadcaster, and verifiable by the receivers. A message is broadcast authenticated by a MAC per one of these keys. Receivers ensure the message is received soon enough that the key can be known only by the broadcaster, and authenticate the message later when that key is revealed.
Assume broadcaster and receivers know the number $t$ of time units (say minutes) elapsed since a reference, as an integer, with a cumulated uncertainty significantly below $\pm1$ unit between broadcaster and any receiver, accounting for their cumulated uncertainty and propagation delay.
- Setup (by the broadcaster)
- choose the initial time $t_0$ for first use of the system;
- choose a large parameter $n$; the system will be usable up to time $t_0+n-3$;
- randomly choose the master 256-bit secret $K_n$;
- compute $K_j=\operatorname{HMAC-SHA-256}(K_{j+1},0\|j)$ for $j$ going down from $n-1$ to $0$, and store some of the $K_j$ (say, for $j\equiv0\bmod2^{16}$, in order to be able to recompute any $K_j$ with less than $2^{16}$ HMAC);
- when a device is manufactured, and that's at $t_1\ge t_0$, compute $g=t_1-t_0$ and setup the device with the trusted pair $(K_g,g)$;
- Broadcast
- in order to broadcast message $M$, compute and broadcast $\operatorname{HMAC-SHA-256}(K_j,1\|M)\|j$ with $j=3+t_2-t_0$, where $t_2$ is the time of that broadcast, with $t_2\ge t_1\ge t_0$;
- broadcast the associated $M$ itself at any time, with something to link it to the $\operatorname{HMAC-SHA-256}(K_j,1\|M)\|j$ that has or will be broadcast;
- broadcast $K_j\|j$ in clear not earlier than time $t_0+j$ (and soon after that), perhaps for all $j$, or when use has been made of $K_j$ to authenticate a message, or/and at least once in a while (say, when $8$ time periods have elapsed since the last broadcast of $K_j\|j$);
- Reception
- when a receiver gets an alleged $\operatorname{HMAC-SHA-256}(K_j,1\|M)\|j$, it checks that $j+t_0-3$ is at least the current time; only if that check succeeds does the receiver accept that alleged $\operatorname{HMAC-SHA-256}(K_j,1\|M)\|j$ (and buffers it until the corresponding $K_j$, and $M$, are known);
- when a receiver gets an alleged $K_j\|j$, and $j>g$, the new alleged $K_j$ is checked against the trusted pair $(K_g,g)$ by way of $j-g$ iterations of the recurrence relation $K_i=\operatorname{HMAC-SHA-256}(K_{i+1},0\|i)$ with $i$ going down from $j-1$ to $g$; if and only if that checks succeeds, the trusted pair $(K_g,g)$ is atomically set to $(K_j,j)$;
- a received message $M$ is accepted by a receiver when and if
- an associated alleged $\operatorname{HMAC-SHA-256}(K_j,1\|M)\|j$ has been accepted;
- and $K_j$ is available and trusted; that is, $j\le g$ and $K_j$ can be computed from $(K_g,g)$ by way of $g-j$ iterations of the recurrence relation $K_i=\operatorname{HMAC-SHA-256}(K_{i+1},0\|i)$ with $i$ going down from $g-1$ to $j$;
- and the recomputed $\operatorname{HMAC-SHA-256}(K_j,1\|M)$ is as alleged.
Protection against replay, or playing messages out of order, can be easily added. That's very similar to: Perrig, Canetti, Briscoe, Tygar, Song, TESLA: Multicast Source Authentication Transform (Internet Draft, 2000), and perhaps earlier work that I failed to locate.
Drawbacks include:
- receivers must be able to maintain or obtain a trusted time reference, which is hard in practice;
- there's a latency a few time the uncertainty the receivers have on time, and that will increase over time if the trusted time is maintained my a local oscillator;
- a receiver will have to perform several HMAC computations before being able to authenticate messages after the the link (or its computation capacity) was interrupted, in proportion of the duration of the interruption.
All the aforementioned drawbacks are good reasons to use a signature scheme instead of symmetric cryptography:
- Virtually any 32-bit CPU for sale now, and many 8-bit CPUs, have enough resources to check an RSA or Rabin signature in time negligible compared to the duration of a software upgrade.
- Signature is intrinsically immune to side channel attacks on the receivers, which has the potential to leak any secret material like $K_j$.
- The size overhead is constant, and modest (crosspoint is just above 2 devices if we use signature with message recovery, like 24 if we do not).
