NSA@home

> Overview

> Hardware

> FPGA design

  + Generator

  + Hash

  + Lookup

> Software

> Web interface

Since the hash block accepts only 2 bit updates per cycle, the generator has to be a bit more complex than a simple 384-bit counter (64 6-bit char selects) followed by a mapping RAM. It has to traverse the code space in such a way that the Hamming distance (number of different bits) between each 512-bit input word and its successor doesn't exceed 2.

As a first step, a simpler problem can be solved - guaranteeing that no more than one character changes at a time. This is quite easy: it is enough to make each character's counter reverse direction after it reaches the maximum value. This will result in a counting sequence - for 2-bit character counters - of:

    00 01 02 03 13 12 11 10 20 21 22 23 33 32 31 30

This scheme can be trivially extended to 64 6-bit counters.

Now all we need to guarantee that an increment of the 6-bit character select, sourced by the counter, doesn't result in flipping of more than 2 bits in the 8-bit ASCII code. To do that, it's enough to find a Hamiltonian path - one that passes through each vertex exactly once - in a graph, in which two vertices have an edge between them if the Hamming distance of their corresponding characters' ASCII codes does not exceed 2. The '.' on the picture below corresponds to ASCII code 00h. The picture shows a Hamiltonian cycle, even though a path would suffice.

Implementation note: the full 384-bit set of counters is not explicitly created. Instead, to save logic resources, 63 out of 64 6-bit counters were packed into Block RAM in the FPGA. Only the least significant counter is using the usual coding style, because it needs to change every cycle.