Randomness and authentication on short value outputs (48 bits)

Question

I want to implement a client that generates random 48-bit values and send them as broadcast messages. We assume also there is a legitimate receiver getting those values (so, there is some sort of pre-authentication that has already happened but it is not of importance here. We can also assume the client/receiver share a common key $K$). Since these are broadcast messages it means also that anyone can intercept those values. I would like those values to have two properties:

1. It is difficult for an attacker to guess the next random value in the sequence
2. The receiver should be able to verify that these values are indeed coming from the specific client

I was thinking of a simple scheme that does the following:

Client

1. $t$ = AES-CTR($K$, nonce||counter, random_plaintext)​

2. $r = t ⊕ K$ (keep last 48 bits)

3. Broadcast $t, r$

I use AES-CTR to generate a temporary random looking string $t$ and then XOR it with the key once again to generate my random value. I then keep the last 48 bits and broadcast both $t$ and $r$. Then the receiver can simply:

Receiver

1. $r' = t ⊕ K$ (keep last 48 bits)
2. Verify $r' == r$

If the check succeeds then he authenticates the client because only he knows the same key $K$. Also the value being an output of AES-CTR should be fairly random meaning it is very difficult for someone to guess the next one.

Does this scheme achieve my requirements? Does the truncation of the last 48 bits pose a security risk?

Answer 1

Does this scheme achieve my requirements? Does the truncation of the last 48 bits pose a security risk?

The scheme is broken by a passive adversary who gets a single pair $(t,r)$. Observe that the last 48 bits of the key can be recovered as $K[:48] = t \oplus r$. Therefore, the attacker can now send arbitrary $(t^*, r^*)$ values that the receiver will accept. Recalling that the verifier does the following

$r' = t' \oplus K$ (only keep last 48 bits); verify $r = r'$

We see that knowledge of the rest of the key is not needed.

Besides, 48 bits values offer low collision protection, but that may be fine for your application...

Replay: a more straightforward attack is to replay the pair $(r, t)$. The description doesn't say how the receiver checks for this.

Potential solution: From the initial description, it seems as if the receiver is fairly limited computationally speaking, and they can only compute xors are most and not the AES-CTR, for example. Which would be odd with the following

so, there is some sort of pre-authentication that has already happened but it is not of importance here

Anyway, a possible solution is using two pseudo-random functions if the receiver can do more than xors. ( I doubt it is secure...). Initially, expand $K$ into $K_1, K_2, K_3$ of appropriate length.

The sender does the following

1. $r =$ AES-CTR$(K_1, counter)$ (keep last 48 bits)
2. send $counter, r, \tau = HMAC(K_2, counter,r)$

The receiver does the following

1. Upon receiving $r, \tau$, verify $\tau$
2. Check counter has increased
3. Rederive $r$.

Some remarks:

• Broadcasting here is not even necessary if the sender and receiver are someone sharing a clock.
• The alternative has a few problems when it comes to robustness in case of a reboot, as pointed out in a comment by Paul.