Oddly enough, I just left a talk at the '96 Genetic Programming conference on developing adaptable hardware and silicon evolution. One of the speakers at this particular session was the Product Line Manager from Xilinx and one of the goodies he handed out was pre-release data sheets for the new XC6200 series of FPGAs they are producing (the chips are already out in limited quantities) so here is a little update on the state of the art in this area. Tim May writes:
Bill Frantz wrote:
o As more and more chips are added to a machine, two effects occur:
o Interconnections increase and increase running time; o Heat from the chips eventually limit [sic] the size of a machine. Fast machines produce a lot of heat.
But, as many have pointed out, this is not a realistic limit.
One can also use reversible logic to get arond the heat problem if mechanical means are not enough. This is a necessity for molecular-scale computing and during the post-session BS at another talk we speced out a system that could probably evolve a reversible logic compiler. Heat will not be a "wall" at any scale, it may add to the cost a little bit but the problem is solvable. The interconnection problem has also been solved in this chip series. [A long-standing problem with FPGAs is that there were generally a limited amount of "wires" running between the logic elements and thus a lot of cells were wasted because there were no interconnections left, I/O to the outside world was also a problem.] The chip has a really cool interconnection method which allows a much more efficient use of the chip real estate and which makes the entire chip directly addresable (like regular RAM) through an on-chip interface module. Given the relatively compact design in Ian and Dave's paper and the new chips one might even fit two or four cracking engines on a single FPGA. Either the NSA did not do thier homework in this area or they are lying.
Now I have no problem with believing NSA would invest $7 million. However, $700 million makes me wonder. With FPGAs, there is a significant risk that people will change the crypto system and make the investment worthless. (Which, I guess, is why they prefer general purpose computers.) However, if they can get the equivalent of a few bits of key back by cryptanalysis, then they knock the costs down to entirely reasonable (for them) levels.
An FPGA is field-programmable. (FPGA = Field Programmable Gate Arrays) The Xilynx and Altera lines of FPGAs could be reconfigured for other algorithms, surely. (I recall several preliminary designs discussed in various places.)
There are two types of FPGAs, one is based on anti-fuse technology which is essentially a big complicated PROM, but the Xilinx FPGAs use SRAM to configure the interconnections between logic elements. The newest line from Xilinx, the XC6000 series has the capability to be reconfigured either partially or completely from an on-chip cache in 5 ns. That is five nanoseconds and you have a completely different piece of virtual hardware. If the configuration is loaded through the slowest I/O port on the chip it only takes 200 microseconds. Even if the encryption algorithm is secret these chips open up interesting posiblities for developing general-purpose cryptanalysis machines. [Hmm, there may be a paper in there... "Evolving A General-Purpose Cryptanalysis Engine"...] What is even better from the perspective of the NSA accountants is that they only need to build the machine _once_, after that they just load up a new set of interconnections and now the DES cracker is an IDEA cracker. Add to this the fact that the XC6000 series were designed to be built cheaply in large quantities (the Xilinx rep figures the price will get down to $29/chip in 5K lots for the samples he was passing around and he is a wafer guy and not marketting droid so this may be reasonably accurate.) If anything, the Blaze, et many als. paper _underestimated_ the cost of a FPGA hardware cracking engine, particularly if you amortize the savings FPGAs give over the long term with thier almost limitless flexibility. jim