FPGAs in cryptanalysis: Key search engine 1 interface

Description

The interface allows the following operations to be performed:

retrieve the status of the board
retrieve potential keys
set the ciphertext, plaintext and IV to be used by all search units
access and detect all search units controlled by the machine
obtain the status of a single search unit
set or retrieve the next key that will be processed by a search unit

The controller provides a number of registers which allow the computer to access the machine’s resources.

Address	Name	Description	Read/write
0	STATUS	Status register	Read only
1	NEXTKEY	Retrieves the next potential key from the buffer	Read only
2	CTEXT	Sets the known ciphertext	Write only
3	PTEXT	Sets the known plaintext	Write only
4	SUSEL	Select a search unit	Write only
5	SUKEY	Set or retrieve the current value of the key generator	Read/write
6	IV	Sets the initialisation vector	Write only

Only the least significant 3 bits are decoded. All transfers are 64 bits wide. This makes supporting key lengths greater than 64 bits difficult.

When reading the STATUS register, the least significant word contains the following bits:

Bit	Name	Description
0–3	VERSION	Described below
4	BUFFER_FULL	Set when the key buffer is full
5	DVALID	Set when the machine is ready for a new command
6	SU_PRESENT	Set when the currently selected search unit exists
7	SU_RUNNING	Set when the currently selected search unit is running
8	BUFFER_EMPTY	Set when the key buffer is empty

VERSION specifies the version of the communication protocol. For this iteration of the design, the version is “0001”. It is also used to detect whether the board is programmed and operating properly. As such, it should never be “0000”. This catches the case where the FPGA has not been correctly programmed.

DVALID is set when the machine is ready for a new command, and cleared when a command is currently executing. Results from a write command should not be read until DVALID is set.

When written to, the SUSEL register selects a search unit. Any subsequent commands that operate on a specific search unit operate on the search unit specified in SUSEL. Writing to SUSEL also updates the value of the SUKEY register and the SU_PRESENT and SU_RUNNING bits in the STATUS register. The SUSEL register must be repeatedly written to in order to keep this data up to date.

SU_RUNNING is set when the last selected search unit is running, and cleared when the search unit is halted. A search unit might be halted if it has found a key and is waiting to have the key read, or if no initial key has been set.

Software checks presence and version of board by reading STATUS register
If VERSION is 0, program complains that FPGA has not been programmed
If VERSION is not 1, program complains that software version does not match or FPGA is incorrectly programmed
For each address where a search unit is believed to exist
1. Software writes the address to SUSEL
2. Software polls STATUS until DVALID goes high
3. If SU_PRESENT is 1, the search unit exists and can be used; if 0, search unit does not exist
Software writes CTEXT, PTEXT and IV registers
For each search unit:
1. Software waits for DVALID flag to go high
2. Software selects a search unit (sets SUSEL register)
3. Software writes initial key into search unit (writes SUKEY register)
Until correct key is located:
1. Software polls STATUS register to determine if any potential keys have been located
2. If there is a pending key, read it out of the buffer

The key that is written into the key buffer is always the key that was in the key generator at the time the search unit was halted, not the key that caused the search unit to halt. The software must be aware of the number of clock cycles required to process a single key, and subtract that value from the value stored in the key buffer. This value is algorithm dependent.

Ian Howson