Networking and Communications
Secret sharing is a way of splitting something up so that each piece is indecipherable, but they can combine to recreate the original something. Unlike other cryptographic protocols, (trivial) secret sharing is information-theoretic secure: it doesn't depend on any unproved assumptions like the discrete log problem or factoring or anything: each piece literally contains no information. "Efficient" secret sharing is more mathematically fun, but relies on traditional cryptographic primitives.
This week I wanted to make some secret sharing USBs: devices that you can chain together, write files to, physically split up, and read the file only if you assemble them all back together. I didn't have much time and the lab doesn't stock USB-A connectors, so I designed Version 1 to work over serial, with UART input and output ports, an ATtiny45, and a status LED - the simplest board I've ever had to lay out.
In the base case (when there is just one device), the node just stores the ciphertext it's given. Otherwise, as long as there is another node "downstream", it will generate a random bitstring the same length as the ciphertext, store that, and inductively pass on the bitwise XOR of the random string and the ciphertext to the next node, which repeats the process. Then, to recover the original ciphertext, we can just take the XOR of all of the stored bitstrings.
I wanted to make the interface as simple as possible - output ports on the opposite side of the input pins - and to be able to chain as many together as possible. But this was Version 1, so I only milled two boards to start. After I stuffed them, I realized that I had rotated one of the pin headers 180 degrees, so the devices actually had to be chained alternating upside-down. Oops.
Debugging at the edge of software and hardware is tricky, so to simplify things, just swear that if it turns out to be a hardware problem you'll eventually travel back in time to prevent it. Then proceed to confidently review your code. For induction, we need each node to be able to tell if it is the last in the chain. For debugging, we also needed each node to know if it was the first in the chain, so that it - and only it - can print debugging strings to serial (we want to see them on the computer but can't confuse other nodes who are expecting real data).
This is tricky, but we're helped by the fact that by default, serial pins float high. So when initializing, we first set "downstream output" to low, wait a few milliseconds, and then read "upstream input". If it's low, then an upstream node is setting it low (i.e. we're not first), and if it's high, then the upstream node is actually just a computer (i.e. we are first).
Similarily, during initialization, we set "upstream output" to low, then after a few milliseconds read "downstream input", and from that deduce if the node is last. It's critical to both these steps that the digital read pins are configured as INPUT_PULLUP or else unpredictable things will happen.
Once the first and last boolean variables are set (after two rounds of 500-millisecond delays), we enter the main loop.
The first node is responsible for prompting for input, and every node is responsible for echoing commands down the chain and relaying status messages back up.
Every single keystroke at the serial terminal gets bounced down through every node in the chain, and echoed back up (verifying matches at every step).
This means it's fail-safe (in the literal military sense, not in the "infallible" sense), but is guaranteed to work correctly if it works at all.
The serial API has two commands:
- "r" is for Read, and it just echoes the XOR of the entire chain (the last node returns its stored bitstring; the rest listen downstream for bitstring and propagate the XOR of their stored bitstring with that one).
- "w" is for Write, and it prompts for a string. Every character is sent down the chain in realtime - getting encrypted char by char, stored at indices offset by one (i.e. the first character gets written to EEPROM 1, the second to 2, etc). The newline character signals the end of the string, at which time the length of the bitstring gets written to EEPROM index 0.
Here's the full code for the project.
You need to include some libraries but if you're programming with the Arduino IDE you don't need to worry about.
Most of the serial functions (get_char, put_char, and put_string) are
taken from Neil's examples in hello.ftdi.44.echo.c,
and you need his term.py to interact with it.
#include <avr/io.h>
#include <util/delay.h>
#include <EEPROM.h>
#define output(directions,pin) (directions |= pin) // set port direction for output
#define set(port,pin) (port |= pin) // set port pin
#define clear(port,pin) (port &= (~pin)) // clear port pin
#define pin_test(pins,pin) (pins & pin) // test for port pin
#define bit_test(byte,bit) (byte & (1 << bit)) // test for bit set
#define bit_delay_time 8.5 // bit delay for 115200 with overhead
#define bit_delay() _delay_us(bit_delay_time) // RS232 bit delay
#define half_bit_delay() _delay_us(bit_delay_time/2) // RS232 half bit delay
#define char_delay() _delay_ms(10) // char delay
#define serial_port PORTB
#define serial_direction DDRB
#define serial_pins PINB
#define serial_pin_in (1 << PB4)
#define serial_pin_out (1 << PB3)
#define led_pin (1 << PB2)
#define serial_nip_in (1 << PB0)
#define serial_nip_out (1 << PB1)
void get_char(volatile unsigned char *pins, unsigned char pin, char *rxbyte) {
*rxbyte = 0;
while (pin_test(*pins,pin)) ;
half_bit_delay();
bit_delay();
if pin_test(*pins,pin)
*rxbyte |= (1 << 0);
else
*rxbyte |= (0 << 0);
bit_delay();
if pin_test(*pins,pin)
*rxbyte |= (1 << 1);
else
*rxbyte |= (0 << 1);
bit_delay();
if pin_test(*pins,pin)
*rxbyte |= (1 << 2);
else
*rxbyte |= (0 << 2);
bit_delay();
if pin_test(*pins,pin)
*rxbyte |= (1 << 3);
else
*rxbyte |= (0 << 3);
bit_delay();
if pin_test(*pins,pin)
*rxbyte |= (1 << 4);
else
*rxbyte |= (0 << 4);
bit_delay();
if pin_test(*pins,pin)
*rxbyte |= (1 << 5);
else
*rxbyte |= (0 << 5);
bit_delay();
if pin_test(*pins,pin)
*rxbyte |= (1 << 6);
else
*rxbyte |= (0 << 6);
bit_delay();
if pin_test(*pins,pin)
*rxbyte |= (1 << 7);
else
*rxbyte |= (0 << 7);
bit_delay();
half_bit_delay();
}
void put_char(volatile unsigned char *port, unsigned char pin, char txchar) {
clear(*port,pin);
bit_delay();
if bit_test(txchar,0)
set(*port,pin);
else
clear(*port,pin);
bit_delay();
if bit_test(txchar,1)
set(*port,pin);
else
clear(*port,pin);
bit_delay();
if bit_test(txchar,2)
set(*port,pin);
else
clear(*port,pin);
bit_delay();
if bit_test(txchar,3)
set(*port,pin);
else
clear(*port,pin);
bit_delay();
if bit_test(txchar,4)
set(*port,pin);
else
clear(*port,pin);
bit_delay();
if bit_test(txchar,5)
set(*port,pin);
else
clear(*port,pin);
bit_delay();
if bit_test(txchar,6)
set(*port,pin);
else
clear(*port,pin);
bit_delay();
if bit_test(txchar,7)
set(*port,pin);
else
clear(*port,pin);
bit_delay();
set(*port,pin);
bit_delay();
bit_delay();
}
void put_string(volatile unsigned char *port, unsigned char pin, char *str) {
static int index;
index = 0;
do {
put_char(port, pin, str[index]);
++index;
} while (str[index] != 0);
}
bool first = false;
bool last = false;
int main(void) {
static char chr;
static char rhc;
int count = 0;
int index = 0;
int max_count = 256;
CLKPR = (1 << CLKPCE);
CLKPR = (0 << CLKPS3) | (0 << CLKPS2) | (0 << CLKPS1) | (0 << CLKPS0);
pinMode(PB2, OUTPUT);
pinMode(PB4, INPUT_PULLUP);
pinMode(PB0, INPUT_PULLUP);
pinMode(PB3, OUTPUT);
pinMode(PB1, OUTPUT);
digitalWrite(PB3, LOW);
digitalWrite(PB1, LOW);
// wait a little bit for downstream nodes to initialize
_delay_ms(500);
// check both ways before crossing the street
first = digitalRead(PB4);
last = digitalRead(PB0);
_delay_ms(500);
// I have a theory
digitalWrite(PB3, HIGH);
digitalWrite(PB1, HIGH);
_delay_ms(500);
set(serial_port, serial_pin_out);
output(serial_direction, serial_pin_out);
if (last) {
digitalWrite(PB2, HIGH);
}
while (1) {
// get instruction
get_char(&serial_pins, serial_pin_in, &chr);
if (chr == 'r') {
if (last) {
char_delay();
if (first) put_string(&serial_port, serial_pin_out, "here's your secret: ");
else put_char(&serial_port, serial_pin_out, chr);
} else {
put_char(&serial_port, serial_nip_out, chr);
get_char(&serial_pins, serial_nip_in, &rhc);
if (chr == rhc) {
if (first) put_string(&serial_port, serial_pin_out, "here's your secret: ");
else put_char(&serial_port, serial_pin_out, chr);
} else {
return 1;
}
}
count = EEPROM.read(0);
for (index = 1; index < count; index++) {
chr = EEPROM.read(index);
if (last) {
char_delay();
put_char(&serial_port, serial_pin_out, chr);
} else {
get_char(&serial_pins, serial_nip_in, &rhc);
put_char(&serial_port, serial_pin_out, chr ^ rhc);
}
}
if (first) put_char(&serial_port, serial_pin_out, 10);
} else if (chr == 'w') {
if (last) {
char_delay();
if (first) put_string(&serial_port, serial_pin_out, "enter your secret: ");
else put_char(&serial_port, serial_pin_out, 'w');
} else {
put_char(&serial_port, serial_nip_out, 'w');
get_char(&serial_pins, serial_nip_in, &rhc);
if (rhc == 'w') {
if (first) put_string(&serial_port, serial_pin_out, "enter your secret: ");
else put_char(&serial_port, serial_pin_out, 'w');
} else {
if (first) {
put_string(&serial_port, serial_pin_out, "rhc was not 'w', instead: ");
put_char(&serial_port, serial_pin_out, rhc);
}
while(1) ;
}
}
count = 0;
while (count < max_count) {
count += 1;
get_char(&serial_pins, serial_pin_in, &chr);
if (chr == 10) {
if (last) {
char_delay();
put_char(&serial_port, serial_pin_out, 10);
if (first) {
put_string(&serial_port, serial_pin_out, "your secret is safe.");
put_char(&serial_port, serial_pin_out, 10);
}
EEPROM.write(0, count);
break;
} else {
put_char(&serial_port, serial_nip_out, 10);
get_char(&serial_pins, serial_nip_in, &rhc);
if (rhc == 10) {
put_char(&serial_port, serial_pin_out, 10);
if (first) {
put_string(&serial_port, serial_pin_out, "your secret is safe.");
put_char(&serial_port, serial_pin_out, 10);
}
EEPROM.write(0, count);
break;
} else {
if (first) {
put_string(&serial_port, serial_pin_out, "rhc was not 10, instead: ");
put_char(&serial_port, serial_pin_out, rhc);
}
while(1) ;
}
}
} else if (last) {
EEPROM.write(count, chr);
char_delay();
put_char(&serial_port, serial_pin_out, chr);
} else {
char r = random(256);
char c = r ^ chr;
EEPROM.write(count, r);
put_char(&serial_port, serial_nip_out, c);
get_char(&serial_pins, serial_nip_in, &rhc);
if (rhc == c) {
put_char(&serial_port, serial_pin_out, chr);
} else {
if (first) {
put_string(&serial_port, serial_pin_out, "rhc was not chr, instead: ");
put_char(&serial_port, serial_pin_out, chr);
put_char(&serial_port, serial_pin_out, rhc);
}
while(1) ;
}
}
}
} else if (first) {
put_string(&serial_port, serial_pin_out, "enter 'r' or 'w': ");
put_char(&serial_port, serial_pin_out, 10);
} else {
return 1;
}
}
}