Re: Notes on packing serial cores into Xilinx devices

On 13 Aug, 2004, at 23:20, Dan Oetting wrote:

> Using some reasonable value for cracking rate and operating cost for 
> some piece of hardware, what is the break-even acquisition cost for 
> that hardware. [PS: this is trick question, what is the trick?]

'reasonable value'. And the acquisition cost will end up being negative.

In times like this, I like to work backwards from what you can reliably 
estimate (how heavy the nuke in Armageddon was, how much energy you can 
get in a nuclear reaction, the speed you need to give the asteroid to 
make it pass the Earth if it blew up on the moon, the density of the 
moon) to calculate a ridiculous requirement (the asteroid is only 2 km 
a side). An asteroid that big would actually cause a mass-extinction, 
but they have to claim it was the size of Texas. There's also a huge 
plot hole ("Why the hell do we have a bomb that can split Texas in 
half?").

Now, you win $10000. Assume electricity costs an insanely low 1 cent 
per kWh. Assume equipment is free. So you have 1 million kWh (== 3.6e12 
J) to spend cracking 2^71 keys (since, on average, you search half the 
keyspace to find the result). That's 1.5e-9 Joules per key.

Assume we have a low threshold voltage of 0.3V (either germanium or 
silicon, I forget). That means you have 5.1e-9 Coulombs per key. That's 
3.2e10 electrons.

Let's estimate the minimum number of transistor*clocks you need to do 
RC5. Assume you need no bits of storage (which you don't if you're not 
pipelining). Skip this if you don't feel like counting transistors.
Two adds per S round. 405 transistors per add [1], so 810 for an 
S-round, so 63180 total.
Two 32-bit adds per L-round, so 810 transistors. A 5-bit add, so 54 
transistors [2]. The rotate costs 32 5-bit hard-coded comparisons, 
which should average 1.5*5=7.5 transistors per comparison [1], negated 
(another transistor), and fed to 32 transistors to select the correct 
rotate amount. 40.5 transistors, 32 comparisons, so 1296 transistors. 
2160 per L-round, 168480 total.
A 32-bit XOR per E-round, 64 transistors. A rotate, 1296 transistors. 
An add, 405 transistors. 1765 per E-round, 45890 total.
A 64-bit hard-coded comparison with the ciphertext, which has 43 
on-bits, so 64+43=107 transistors.

107+45890+168480+63180=277657 transistors. About 11400 electrons per 
transistor. This kind of efficiency isn't likely to happen any time 
soon.

N.B. You can probably do ANDs in one transistor and ORs in two, if you 
use a different type. It's close enough for an order-of-magnitude 
estimate though.

Interestingly, the chance of having 43 or more on-bits in the first 64 
bits of ciphertext is roughly 4/1000.

- Purr

[1] A "half-adder" has a XOR, and an AND. The XOR takes two 
transistors, the AND takes three. Five per half-adder, 32+31=63 
half-adders, 315 bits. Add the 30 OR gates, 30*3=90 transistors. 405 
total.

[2] Similarly, 5+4=9 half-adders, 3 OR gates, so 9*5 + 3*3 = 54 
transistors.

[3] Comparing numbers is easy. You have a VCC fed through n FETs. If 
any of them are 'on', the VCC is blocked, thus we're comparing with n 
zeroes. To compare with one-bits first negate the corresponding input 
with a FET. So 1 FET per compare with 0, 2 FETs per compare with 1.

_______________________________________________
Hardware mailing list
Hardware-Ra3b/QYEcJ3d140v2zMXi0fjHoOT/h/[email protected]
http://lists.distributed.net/mailman/listinfo/hardware