Problem: I'm thinking about a lightweight solution to provide source authentication (only one source) to multiple receivers (multicast message).

Context: Taking the problem to ground, we can think of use cases like firmware update (one to many), or a command to turn on several lights 'on' (that command can be sent by one and only one source). In all cases I don't want to send many times the same message, but only once (multicast), and that the receivers can authenticate that comes from an authorised-trusted source (one-way authentication).

The scenario is similar to the one described on: https://tools.ietf.org/html/draft-somaraju-ace-multicast-00 But there they have many senders, they use symmetric crypto, any member of the security group (same symmetric key) can send message to the other members of the group.

I know that with asymmetric cryptography the problem can be easily solved: Digital Signatures.

But I was wondering:

Is there any established symmetric-cryptography-only solution to this problem?

To my (not extensive) knowledge I'm inclined to say No (due to the symmetric characteristics of.. symmetric crypto), but maybe there is a smart symmetric cryptosystem that can achieve source-authentication.

ps: this question is simmilar Digital Signature using symmetric key cryptography but not the same (and the answers do not provide a categoric answer)

  • $\begingroup$ I found another question that is more relevant to this one, and the accepted answer provides a categoric answer: Yes, it's possible to achieve source-authentication on a multicast/broadcast scenario with only symmetric cryptography (e.g.: multi-level uTESLA authentication-scheme ) However, is this multi-level uTESLA scheme secure (hast it been received cryptanalysis)? are there any other sym $\endgroup$
    – renzoe
    Oct 23 '15 at 15:56

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):

  1. we trust each receiving party to hold a common secret key secret, and not to use it nefariously;
  2. 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;
  3. 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).
  • $\begingroup$ Hi! thanks for your reply. This protocol you just proposed or is something deployed/studied? I found it privative have an overhead of one MAC-tag per node on the network. The frame maximum size on constrained environments we can say its about 150 bytes, a moderately secure MAC is about 8 bytes, so for 20 nodes on the network, with this proposal, we have already 160 bytes of MAC. I thinkg is not feasable/escalable. Threats: Lenght of M should be authenticated. Replay Attack feasible. Signature/Assymetric cryptography is privative for some constrained devices. Signature will be a nice solution. $\endgroup$
    – renzoe
    Nov 23 '15 at 16:43
  • $\begingroup$ In your answer you put that with only assumption 1 is possible to have multicast source-authentication? (or its 1 AND 2?). Thanks again for your time. $\endgroup$
    – renzoe
    Nov 23 '15 at 16:48
  • $\begingroup$ @renzoe: I have hopefully addressed some of your comments in an update to the answer. As of replay: the protocol that I present is protected against replay using a sequence number, that I take as being the software version (see .. checking the version number is higher than the current version ..). It is possible to solve the issue of small packets, including in the presence of transmission errors. $\endgroup$
    – fgrieu
    Nov 23 '15 at 17:31
  • $\begingroup$ Hi fgrieu, thanks for the repy/edit. As of solution nr 1, Is what I expect of the solution, but I does not solve the source authentication problem. any node in possession of the key can authenticate the messages because its a shared key between the members of the multicast group, hence source-authentication (identify a message coming from a specific node) cannot be resolved with a classical MAC. As of solution 2, I already commented, I agree that an authenticated sequence number can avoid replay attack for downlink; anyway the overhead of the solution is prohibitive for a real implementation. $\endgroup$
    – renzoe
    Nov 24 '15 at 14:09
  • $\begingroup$ @renzoe, look again at the proposal above, each client only has Kj and not K. The manufacturer keeps K secret. $\endgroup$ Nov 26 '15 at 1:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.