The Glowworm hash: Increased speed and security for BBC unkeyed jam resistance

Jam resistance for omnidirectional wireless networks is an important problem. Existing jam-resistant systems use a secret spreading sequence or secret hop sequence, or some other information that must be kept secret from the jammer. There is currently only one system for achieving such jam resistance without any shared secret: BBC coding. BBC requires the use of a hash function that is fast and secure, but ”secure” in a different sense than for standard cryptographic hashes. At MILCOM-2010, the Inchworm hash was presented [1], which is 300 times faster than SHA-1 for this application, and had no security flaws yet known. A variant of it, Inchworm-S, was also presented, that was intended to be more secure. We present an academic break of both Inchworm and Inchworm-S, and a practical break of the former. The advantage to the attacker is very small, but it is definitely detectable. We also present a new hash algorithm: Glowworm. Glowworm is simpler than Inchworm, and the same speed as Inchworm-S, while being more secure. We mathematically prove that it is immune to the theoretical attack we show for Inchworm and Inchworm-S. We also show empirically that it is immune to our empirical attack on Inchworm, even when the attack algorithm is run for much longer periods. In fact, we show that for our best attack software, it is indistinguishable from SHA-1, MD5, and all five SHA-3 candidates. We also mathematically prove that it has avalanche properties that prevent many other types of internal-state collisions and related attacks. We give a public domain, optimized, portable, C implementation of Glowworm. For incremental hashes as used in BBC codes, it can hash a string of arbitrary length in 11 clock cycles. That is not 11 cycles per bit or 11 cycles per byte. That is 11 cycles to hash the entire string, given that the current string being hashed differs from the last in only an addition or deletion of its last bit. Finally, we discuss our implementation of- Glowworm in a Field Programmable Gate Array (FPGA), where it runs in just one clock cycle per string, using only a modest amount of resources.¹