Winnie Cheng, Paul Kundarewich, Steve Wilton, Alan Hu, University of British Columbia
In a series of projects, we are investigating novel applications of FPGAs. Are primary interest are applications in which the unique programmability of FPGAs can be used in a novel way. Also, applications which make extensive use of FPGA memory resources are of interest.
In one project, we have developed an RC-4 cracking system. RC4 is a proprietary stream cipher developed by Ron Rivest for RSA Data Security, Inc. The scheme is very widely used; among other things, it is used to encrypt Web traffic under the SSL protocol. Although the encryption scheme is proprietary, details and source code were anonymously released to the public in 1994. This source code interoperates correctly with legally licensed versions of RC4, so it is widely believed to be a correct description of the RC4 algorithm. Our system cracks this published algorithm.
The system performs a brute-force, exhaustive search of the key space until the correct key is found. For each potential key, an encrypted string is generated using a hardware implementation of the RC4 algorithm. This encrypted string is compared to a known encrypted message; if they match, the correct key has been found. Our architecture consists of a control unit and a number of parallel functional units; each functional unit searches a separate portion of the key space. Our current implementation searches a 32-bit key space. Modifying the circuit to search larger key spaces is straightforward.
In a second project, we have developed a scheduler for a Wavelength Division Multiplexing (WDM) network. Message sequencing and channel assignment are two important aspects to consider in optimizing the performance of these networks. A scheduling technique, Multiple-Messages-per-Node with Shortest Job First priority (MMN-SJF), has been proposed to tackle these two areas simultaneously. We have developed a reconfigurable testbed consisting of several interconnected FPGAs for analyzing such scheduling algorithms. We have used this testbed to investigate the implementation and hardware complexity associated with MMN-SJF algorithm. We found that the MMN-SJF scheduling technique can be implemented cost effectively and with only simple logic blocks.