Unkeyed Jam Resistance 300 Times Faster: The Inchworm Hash

An important problem is achieving jam resistance in omnidirectional radio communication without any shared secret or shared key. The only known algorithm that solves this problem is the BBC (Baird, Bahn, Collins) concurrent code. However, BBC requires the choice of a hash function. The choice of hash determines both the speed and security of BBC. Cryptographic hashes such as the standard SHA-1 hash are not well suited for this application. We propose the Inchworm hash, a new algorithm specifically designed for use in BBC. We show that this avoids a theoretical weakness for this application that is present in SHA-1 due to the Small Internal State Theorem, and that it passes a simple battery of empirical tests. When used in BBC, Inchworm is over 300 times faster than SHA-1. This speeds up encoding and decoding by orders of magnitude, with great benefits for practical implementations of unkeyed jam resistance, especially on small, cheap radios.

Unkeyed Jam Resistance 300 Times Faster: The Inchworm Hash Conference Paper