Randomize (encrypted) data to hide the behaviour of the data source

Question

I'd like to transmit a small amount of data, typ. 4 - 16 Byte through a channel that can be eavesdropped at any time.

The behaviour, the way the data changes, should be protected too.

I could encrypt it using XOR with a 4 - 16 Bytes key like this:

c = m x k

This means c is the same for the same m. When observing the cipher, it's actually not interesting to decrypt the actual data because the cipher reveals enough information about the data source.

When observing the data - encrypted or not - it should ...

... NOT LOOK LIKE THIS:
t=0 12587200
t=1 12587200
t=2 12587200
t=3 97387419

... BUT LIKE THIS:
t=0 23443623
t=1 53453566
t=2 91372718
t=3 18347444

The data either

• lineary increases (with variable increment) or
• over a long time period, changes around a relatively fixed average value or
• does not not change at all over a long period of time or
• is guessable with not much effort

It's clear to me that, since the data might not or little change, it should be randomized before encryption.

Constraints

• No security by obscurity - the algorithm is known to an eavesdropper
• The data may be
  • broadcasted by the source (updated in a defined interval, during this time period an eavesdropper may see the same data) or
  • get actively read by one peer
• The receiver/reader may miss a message update so it should be able to sync
• Message loss is acceptable for the receiver
• Both peers cannot rely on a stable and tamper-free timebase
• CPU power and memory requirement is limited
• The data and the behaviour can be seen unconfidential after a while

I see one option, suitable for broadcasting and active read: combine the data with a pseudo random factor derived from a confidential IV known to both sides. That combination is then encrypted using the also confidential key.

It could look like this:

 T = 5 mins     # Update interval, e.g. 5 mins (unconfidential)
 K = 0x1BC07410 # Key (confidential)
IV = 0xB9EF72E5 # LFSR seed (confidential)
 r = 1000       # initial rounds (unconfidential)
 R = 0          # LFSR round counter
 n = IV         # pseudo noise from LFSR

def HIDE(m):
  n = LFSR(n)
  return m x n

def ENC(m):
  return m x K

# initialize once
while R < r:
  n = LFSR(n)
  R = R + 1

while True:
  R = R + 1
  m = READ_FOUR_BYTE_MESSAGE()
  Feed to broadcasting or store for retrieval: ( ENC(HIDE(m)), R )
  sleep(T)

It's clear to me that an eavesdropper might brute force probe IVs cycled R times through the LFSR and XOR it with the cipher to know that the message did not change between the update intervals.

My questions

• Have I missed other attacking vectors?

• Is there anything to improve the security but increasing IV and key lengths?

• Please guide me what basics I should learn

Answer 1

I assume that you meant to xor the message with the LSFR state, and not with the fixed key.

Even in that case, one problem that you don't cover is that if the attacker knows/guesses that the data between two different exchanges is the same, he can recover the LSFR state (and from that, he gets everything).

What he would do is xor the two ciphertexts $LFSR^k \oplus P$ and $LFSR^{k+n} \oplus P$; that gives him $LFSR^k \oplus LFSR^{k+n}$; if he knows how large $n$ is (the number of times you cycled the LFSR between the two messages), then recovering the original LFSR state is a simple exercise in linear algebra.

Designing such a system really isn't a task for amateurs; it's far too easy to come up with a system with subtle vulnerabilites such as above. Instead, I would suggest you use a system designed by an expert.

I was going to write some advice here about how to sketch out such a system; however I realized that I don't know enough about your system constraints and required security model to do it justice. However, someone needs to do it, and you're not the right person.

I'm not criticizing you; actually, your list of requirements ("the messages need to be randomized", "no security by obscurity", "no reliable timesync", "message loss may happen") shows you've thought about it. It's just that making an efficient and secure encryption system is a lot harder than it looks.

As for some of the constraints that would need to be considered by an expert:

• You mention potential evesdroppers; do you also need to worry about someone modifying the ciphertext (perhaps in hope of making predictable changes in the decrypted data)?

• How large can the ciphertexts be?

• You said that you had constraints in both time and memory; how tight are those constraints? Is the memory constaints on program size or data size? If you're on a CPU, is that an 8-bit CPU, or a 32-bit CPU?

• If someone recovers the key somehow, they can read all the data; are you OK with that?