Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I am building an open source hardware system that will be used to control things over the internet. The system consists of a Base Station and Modules which use wireless communication at 2.4GHz to exchange data.

Now I have come to the point where I need to protect the transmitted RF data against re-transmission and decryption. I also need to protect the system so that nobody can pose as a Base Station and send RF packets to some Module and for example turn on my lights or unlock the door.

Details about data that needs to be protected:

  1. Message is always 27 bytes long (this can be reduced to 20 bytes to leave room for proper MAC)
  2. Format of message (protocol) is known to public
  3. Message contents are sometimes known to public because it is usually a simple command such as "1" for turn-on command, and "0" for turn-off command. Other future Modules might contain data that should be kept secret from a potential eavesdropper
  4. Messages are transmitted rarely, there is no constant RF activity

Since this project is implemented on microcontrollers with limited amount of RAM (some 4kB for the entire thing) and FLASH memory for program (usually 32kB) there is not much room for state-of-the-art encryption algorithms and hash generation functions for MAC. There is also a limitation of data that is being transferred to 29 bytes in each packet. Data should not be split to multiple packets and re-assembled on the receiving side, so 29 bytes is all we have to work with.

These are the specifications of my current implementation:

  1. Messages are encrypted using ARC4
  2. Key for ARC4 is 27+1 bytes long
  3. Key is used for maximum of 256 transmissions or for 30 minutes of RF no-activity (whichever comes first). After that new key is generated inside the Module, encrypted and sent to Base Station so it can decrypt further data
  4. Key (27 bytes) is appended with 1 byte (SYNC) which is incremented after each encryption solving vulnerability of re-transmissions. After rollover this byte starts from 0 again (0-255). In the end this makes the key for ARC4 28 bytes long and different for each transmission

Encryption process

27 bytes of unencrypted data message is first padded with SYNC byte (the last byte of final ARC4 key), then this is padded with CRC-8 checksum calculated over the previous 28 bytes. These resulting 29 bytes are encrypted using current ARC4 key (27 bytes and the SYNC counter (1 byte)).

Encryption of data

The CRC-8 checksum in combination with the SYNC byte is used as a MAC on the decrypting side. The packet is decrypted using current KEY+SYNC and if the SYNC byte in the decrypted packet is the same as the one expected and used during the decryption, and if the CRC-8 is calculated over the entire decrypted package as the one received - all is good.

Questions

  1. I think this is not a very smart way to implement MAC. Is there something else that I could implement here that would take at most 9 bytes of my unencrypted data space? I could reduce the application data space from 27 to 20 bytes to make space for improved MAC.
  2. How safe is this current implementation of the system because I am worried that someone might inject their own RF packets that will be decrypted by Modules and matched the SYNC & CRC-8. Is there any way to analyze this?

I hope I didn't give too much irrelevant information in this post, this is my first time to implement some kind of encryption, and first post on SE.

UPDATE

I have decided to abandon this design as it is not safe. Thanks to poncho for suggesting the alternative. I have found CMAC AES implementation in AVR411 document which also targets the same hardware I am currently using. You can find this document by simply searching for AVR411 on Google.

share|improve this question
    
Many IEEE 802 standards requiring very small footprint use AES in CCM mode. AES-CCM implements both encryption and MAC and it only uses AES-encryption function, thus you can use much smaller AES implementation as decryption is not needed. (Poncho's answer is very good and points out why RC4 and CRC-8 are both misadvised in this context.) –  user4982 Mar 11 at 16:08

1 Answer 1

up vote 3 down vote accepted

There are a bunch of problems with this protocol.

First of all, the way you generate your RC4 key (concatenate a secret key with a public nonce) is known to be weak. The one thing that saves you is that you only do it 256 times before generating a fresh secret key; however it is known that if you were to do it, say, 2000 times with a secret key, you would have a small probability of leaking the secret key. In my opinion, that's close enough to be scary; I'd rethink this.

Now, on to your actual question:

I think this is not a very smart way to implement MAC

That's putting it mildly; it's a very bad way to implement it. The problem is that CRC-8 is perfectly linear; someone who intercepts a packet can flip bits in the ciphertext, and then predict which bits in the CRC-8 he would need to flip to compensate; the decrypted plaintext will have precisely those bits flipped. The only thing that can save you is you will reject the same message twice; an inventive attacker can get around this by causing the reception of the authentic message to fail.

It would appear that the main restriction you have is on memory (for the program and data), and not so much on execution speed. If so, I would suggest you look at small AES implementations, such as talked about in this stack exchange. They would appear to fit well within your budget, and can be used as the basis for a truly secure protocol.

share|improve this answer
    
Great information. I am currently looking at the AES implementations as you suggested, but I still do not know what method to use to protect the integrity of encrypted data (MAC). Some hashing function suggestions would be perfect but also the main question is: would 9 bytes for MAC (hash) be enough to protect the integrity of 20 bytes of encrypted data? –  traxonja Mar 12 at 14:35
    
You could use either AES-CMAC, or since your messages are fixed length, plain-old CBC-MAC would work. As for whether 9 bytes would be enough, that would mean that if someone without the key sent you forged messages, then they would need to send 4 trillion messages before they have 1 in a billion chance that one would get through; is that sufficient? –  poncho Mar 12 at 14:40
    
Yes, that is sufficient :-) I searched yesterday and today for the implementation of CBC-MAC and I seriously couldn't find it anywhere. Maybe I am searching with wrong keywords... I would implement it myself but I would probably make many serious mistakes in the process, especially because I don't really understand the encryption algorithms written in mathematical form. Could you please point me to the right direction here? I have read that CBC-MAC provides both encryption and authenticity but that sounds strange. I am unfortunately still tempted to continue using RC4 but with proper MAC. –  traxonja Mar 14 at 10:11
    
@traxonja: no, CBC-MAC provides integrity but not encryption. It's actually fairly simple, you act as if you are generating the CBC mode encryption of the message, but is discard everything except the last ciphertext; that's your tag (and you can use, say, 72 bits out of that as your tag). Now, both sides do this 'CBC mode encryption' in the encrypt direction (because both are generating tags -- the receiver compares what he generates with the tag in the message). –  poncho Mar 14 at 13:14
    
@traxonja: alternatively, you can generate tags using CMAC (RFC4493); that's pretty much CBC-MAC with a few tweaks to avoid weaknesses arising from variable length messages. –  poncho Mar 14 at 13:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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