[messaging] An Insecure Messaging Algorithm

[Michael Hamburg]

It’s an LFSR with feedback polynomial 0x8000 | stored_key2>>1, tapping out bits 0 and 5 every cycle.

— Mike

> On Oct 30, 2014, at 2:30 PM, Jason A. Donenfeld <Jason at zx2c4.com> wrote:
> 
> Hi folks,
> 
> Not sure the best place to ask about this, so I figure I'll give it a stab here. I've recently come across what appears to be a rather insecure ciphering system between a computer and a device. I've managed to figure out how the algorithm works, and my work with it has been successful. However, I have no idea what this algorithm is, or if it has a name, or where I can read more about it.
> 
> I'm inclined to think its a LFSR, but I'm really not sure.
> 
> I've translated it into C-psuedocode. Could anybody here identify it?
> 
> Thanks,
> Jason
> 
> 
> ==========
> Important parts involve cipher, which updates stored_key1, and the the updating of stored_key2 when receiving messages.
> ==========
> 
> uint16_t stored_key1;
> uint16_t stored_key2;
> 
> void cipher(uint8_t *buffer, size_t len)
> {
> 	uint16_t key1 = stored_key1;
> 	uint16_t key2 = stored_key2;
> 	uint8_t xor_byte, multiplier;
> 
> 	while (len--) {
> 		xor_byte = 0;
> 		for (int i = 0; i < 4; ++i) {
> 			multiplier = 2 * xor_byte;
> 			if (key1 & 1) {
> 				multiplier |= 1;
> 				key1 = ((key1 ^ key2) >> 1) | 0x8000;
> 			} else
> 				key1 >>= 1;
> 			xor_byte = 2 * multiplier;
> 			if (key1 & 0x80)
> 				xor_byte |= 1;
> 		}
> 		*(buffer++) ^= xor_byte;
> 	}
> 	stored_key1 = key1;
> }
> 
> void make_initial_connection_to_device(void)
> {
> 	stored_key1 = (uint16_t)rand();
> 	stored_key2 = 0xA0CB; // Fixed!
> 
> 	uint8_t buffer[] = { stored_key1 };
> 	somehow_send_it_to_the_device(buffer, 1);
> 	receive_message_from_device();
> }
> 
> 
> void send_message_to_device(uint8_t *buffer_to_send, size_t len)
> {
> 	cipher(buffer_to_send, len);
> 	somehow_send_it_to_the_device(buffer_to_send, len);
> }
> 
> void receive_message_from_device(void)
> {
> 	if (len < 2)
> 		return;
> 
> 	uint8_t *buffer_received;
> 	size_t len;
> 	somehow_receive_data_from_device(&buffer_received, &len);
> 
> 	cipher(buffer_received, len);
> 
> 	uint8_t mutation = *buffer_received;
> 	++buffer_received;
> 	--len;
> 
> 	stored_key2 = (stored_key2 & 0xFF) | (mutation << 8);
> 
> 	somehow_do_something_else_with_received_data(buffer_received, len);
> }
> _______________________________________________
> Messaging mailing list
> Messaging at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/messaging