Project: a secure sensor packet

Pack a distance reading into fixed point bytes with flags and a checksum, encrypt it with a one-time pad and send it by radio.

A7.10Data representationA level40 min

A robot on a team reports its distance sensor to the others by radio. The message has to be small, so the reading is packed into bytes. It has to survive interference, so it carries a checksum. And it has to be private, because every robot on the mat hears every message, so it is encrypted. This project uses almost every idea in the module: fixed point, bit masks, character codes, hexadecimal, checksums and the Vernam cipher.

Designing the packet

The packet is four bytes. Each byte has one job, agreed in advance by the sender and receiver, because a bit pattern means nothing until you know how to read it (lesson A7.7).

The reading as fixed point

With one bit after the binary point, the place values of the reading byte are 64, 32, 16, 8, 4, 2, 1 and ½. Storing a distance this way is the same as doubling it and keeping the whole number part:

• range: 0 to 127.5 cm (the pattern 11111111)
• precision: 0.5 cm, the value of the smallest place

A reading of 23.7 cm doubles to 47.4 and is stored as 47, 0010111.1 with the point shown, which the receiver reads as 23.5 cm. The absolute error is 0.2 cm. More bits after the point would be more precise but would cut the range; a distance sensor on a 100 cm mat needs the range more.

The flags as a bit field

The flags byte packs two yes-or-no facts into one byte. Each fact is one bit, set with OR and a shifted 1, and tested with AND (lesson A7.5):

flags = 1 << 7                  # set bit 7: valid
print(format(flags, "08b"))
flags = flags | (1 << 0)        # set bit 0: close
print(format(flags, "08b"))
print("valid:", flags & (1 << 7) != 0)
print("close:", flags & 1 != 0)
flags = flags & ~(1 << 0)       # clear bit 0 again with AND and an inverted mask
print(format(flags, "08b"))

Run this in the simulator

The 23.7 cm reading gives the packet 44 2F 81 F4: type 68, reading 47, flags 129, and checksum (68 + 47 + 129) mod 256 = 244.

The receiver's checksum test, in OCR's reference language:

function checksumOK(packet)
    total = 0
    for i = 0 to 2
        total = total + packet[i]
    next i
    return total MOD 256 == packet[3]
endfunction

Encrypting it

The radio is a broadcast, so the four bytes are encrypted with a Vernam one-time pad of four key bytes, PAD, that both robots were given in advance. Byte i of the ciphertext is byte i of the packet XOR byte i of the pad. In AQA assembly language, encrypting the type byte stored at memory address 100 with the pad byte 58 (hex 3A) is:

LDR R0, 100      ; load the type byte, 01000100
EOR R0, R0, #58  ; XOR with the pad byte, 00111010
STR R0, 101      ; store the ciphertext byte, 01111110
HALT

The encrypted bytes are sent as text: PKT and a space, then each byte as two hex digits with no spaces, so four bytes become eight characters. The receiver splits the text into pairs of hex digits, turns each back into a byte, XORs with the same pad, and checks the checksum before trusting anything in the packet.

Be honest about the security. A pad this short is secure only if it is truly random and never used again. A robot that sends a reading every second needs four new pad bytes every second, which is exactly why the one-time pad is rarely practical and real systems use computationally secure ciphers instead.

Here is the receiver's side for a packet that has already been decrypted. Flipping one bit of the reading is caught by the checksum:

def read_packet(packet):
    if sum(packet[:3]) % 256 != packet[3]:
        return "checksum failed"
    if not packet[2] & (1 << 7):
        return "no valid reading"
    close = "close" if packet[2] & 1 else "clear"
    return chr(packet[0]) + " " + str(packet[1] / 2) + " cm " + close

good = [0x44, 0x2F, 0x81, 0xF4]
print(read_packet(good))
damaged = [0x44, 0x2F ^ 0b00000100, 0x81, 0xF4]
print(read_packet(damaged))

Run this in the simulator

Task: a secure sensor packet

The robot faces a wall. PAD is a list of four whole numbers from 0 to 255.

1. Read the sensor once with distance(), a reading in cm (a float, from 0 to 127.5 on this mat).
2. Build the four packet bytes as whole numbers from 0 to 255: the type byte ord("D"); the reading byte, the reading doubled with its fraction dropped (int); the flags byte with bit 7 always set and bit 0 set only when the reading is under 30 cm, built with shifts and OR; and the checksum, the sum of the first three bytes modulo 256.
3. Print packet: followed by the four bytes as two uppercase hex digits each, separated by single spaces.
4. Encrypt the packet by XORing each byte with the PAD byte in the same position, and print encrypted: followed by the four encrypted bytes in the same format.
5. Send PKT followed by the encrypted bytes as eight hex digits with no spaces, built by your program.
6. Now be the receiver, using only the text you sent: turn each pair of hex digits back into a byte, XOR with PAD, and check that the checksum matches and bit 7 of the flags is set. If both are true, print received: <cm> cm, checksum ok, where <cm> is the reading byte divided by 2 (for example 51.0), and set the LED to green. Otherwise print received: checksum failed and set the LED to red.

Build every byte from the reading; do not type any of the packet in.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

PAD = [0x3A, 0x91, 0x5C, 0xE7]

def hex_bytes(data, sep):
    return sep.join(format(b, "02X") for b in data)

d = distance()

Challenges

1. A reading of 140 cm does not fit. Clamp it to the largest value the byte can hold and set a new flag, bit 1, to say it was clamped.
2. Change the format to 6 bits before the point and 2 after. What are the new range and precision, and which suits this mat better?
3. Flip one bit of the encrypted bytes before the receiver reads them, and show that any single flipped bit is caught. Then find two flipped bits that the checksum misses.