Danger of collision.

[esutko]

This is just here for the future. we should deal with this after the presentation, not before.

the HOTP code is three decimal digits in length meaning it is 10³ or 1000 possible states. the second three digits are determined by the first three digits and an unknown, the bike number. because of this if the first three digits are the same then all values of the last three digits are the same. this means there is a very small number of total states and a high likelihood of collision. due to the nature of the system even small errors can cause critical failures due to the assumptions that the rack and the server make being violated, causing the error to propagate. The solution is we use either a 5 or 7 digit HOTP key, and insert a single digit in a fixed place. this digit will be generated through as

f(counter) XOR bike_num

f takes counter and maps it, with an even distribution, to a number 0..9 in a deterministic and irreversible way. when the bike rack is given a key it removes the bike digit and matches it with an HOTP key, then with the counter, C, that associated with the key, next the algorithm calculates the f of C, and XORs the bike digit producing the bike number.

The way I would suggest implementing f is using a Mersenne Twister and a pool. I will avoid the details until a later date. if the pool implementation is too memory intensive we could also have f be a spigot algorithm for digits of pi, though this would be more CPU intensive.

NOTE: the algorithms here are designed for a number of bikes less than 10, we would need to tweak them if we had more.