> who's your enemy?  The NSA?  The SVR?  Or garden-variety cybercrooks?

"Enemy"?  We don't have to be the enemy for someone to crack our
security.  We merely have to be in the way of something they want;
or to be a convenient tool or foil in executing a strategy.

Given the prevalence of Chinese crypto researchers at the open crypto
conferences, I suspect that China is as much of a threat as the US's
National Security Agency, Russia's Sluzhba Vneshney Razvedki, India's
Research and Analysis Wing, Japan's Jōhōhonbu, Israel's
Mossad, or Brazil's AgŽÃŽªncia Brasileira de InteligŽÃŽªnc.  A small
country with a good economy -- there are dozens more -- could also be
such a threat, if they focused on this area.  The big ones can crack
RSA keys AND do all the other things big countries do.

Many people on this list provide significant civilian or military
infrastructures depended on by millions.  When we know at least ten
nations are grasping at having the power to take down arbitrary
civilian infrastructures via cyberspace, we had better assume that
somebody among them can spend tens of millions of dollars *per year*
on key cracking.  And how much work is it, really, for us to use
longer keys?

Not all of us are in the US.  Those of us in the US perhaps have come
to a complacency about being a superpower - we haven't fought a war on
our own land, in which significant numbers of our own civilians died,
in what, a century?  The US government's idiotic response to 9/11 has
made more enemies around the world every year, while simultaneously
destroying the value of our currency.  The best time for a foreign
"enemy" to stop funding our $0.X trillion dollar a year debt would be
right after taking down much of our civilian infrastructure.  And
perhaps it might be hard for Washington to raise a billion dollars a
day in international bond sales, even from friendly countries, when
the international financial networks had been subtly or completely
compromised?  Hell, half the people in this country would starve two
days after their ATM cards stopped working.  The whole point of the
trillion dollar Bush and Obama bailouts (which were done by moving a
few bits in a federal funds transfer network somewhere) was to avoid
the specter of long lines around the block at bank branches, full of
angry people failing to turn bits in bank accounting databases into
paper or gold money.  Such a spectre would be easy for a cracker to
create -- and then how much confidence will people have in either the
currency or the government?

What keys secure that funds transfer network?  Suppose an attacker
merely multipled a random 10% of the transfers by 1000?  Somebody
wires you a thousand dollars, you have a 10% chance of it becoming a
million.  Wire a million, it might come through as a billion.  Then
you look at strategy: should they pay themselves back immediately for
the cost of cracking the keys, then be quiet?  Or should they just
make everyone a billionaire and make the entire currency worthless?

Did you think Adi Shamir's work on TWINKLE and TWIRL was theoretical?
Israeli leadership is paranoid enough to regularly shoot their friends
as well as their enemies, and usually in advance, on the theory of
weakening them *before* they turn against Israel.  And Israel would
have a lot more geopolitical power in a world without superpowers.

Did you think nobody else was designing or building such things?
Thank Adi for publishing - but what he published might not have been
his very best design.  Why did this community wait until a DES
cracker cost only $250,000 to build before thinking, duuh, maybe we
should defend our infrastructure against DES crackers.  How many
countries had secret DES crackers before I built one publicly?
To this day, no country has admitted having one -- yet I have been
privately told that government experts were aware that the cost of
building one was in the $250K range.  Do you think they learned that
merely by twirling a pencil at their desk, in agencies with budgets
way over $100 million a year?

(A private industry expert also told me that they'd been hoping the
first public DES cracker would happen at least a year later than it
did, to give them more time to secure their networks, e.g. before
their bosses found out how vulnerable the previous design was.)

In 2003, Shamir's estimate was that TWIRL could factor a 1024-bit
number in a year at a cost of about $10M US dollars.  More recent
estimates are here:


Either that page hasn't been updated since 2006-7 or there's been no
published research since then.  I encourage others to post more
surveys of the cost of cracking RSA keys using dedicated hardware.

A typical academic analysis, such as 1996's "Minimal Key Lengths
for Symmetric Ciphers to Provide Adequate Security" said things like:

  Because ASICs require a far greater engineering investment than
  FPGAs and must be fabricated in quantity before they are economical,
  this approach is only available to serious, well-funded operations
  such as dedicated commercial (or criminal) enterprises and government
  intelligence agencies.

But that was bullshit.  Two years later, a team of about six guys
designed and built a 1-week DES cracker for much less than what it
costs to buy a condo in San Francisco.  Circuit layout and fabrication
services were readily available in the commercial market.

Anybody who builds and deploys one machine that can crack RSA-1024 in
a year will build more.  The design is paid for; and it's cheaper to
build them in quantity 10 than in quantity 1.  Every year the tech can
get better, too.  After they've built 50, which perhaps only take six
months to crack a key, will YOUR key be one of the 100 keys that they
crack this year?  How about next year?

Smart allied countries - or criminals - would split up the work,
attack different keys, and swap results, spreading the cost around --
two countries with banks of 50 6-mo machines could crack twice as deep
down into the infrastructure, rather than both of them wasting their
time cracking the same keys.

It wouldn't even take much coordination; they could offer a key
they've already cracked, to trade for another one.  If somebody burns
them and gets a cracked key while failing to provide one, big deal;
they get one freebie.  But if your partner keeps feeding you cracked
keys that were on your list but you hadn't gotten to, you'd keep doing
deals; it *halves* the cost of your cracking.

Who'll do the math to figure out how to crack ten thousand keys in
parallel in hardware?  Such a device might not crack any particular
key in a year, but it'll crack *some* of those keys in a year,
depending on luck.  Having such a machine would produce some
interesting results if you were in the cracked-key trading market.
You could probably trade some to people who value them more than you
do, in return for keys that you value more.

Now do you see why it's a bad idea that 90+% of keys are 1024 bits?
When that size became vulnerable, it brought market forces to bear on
the problem.  If in fixing that mistake we make another sharp focus at
some other size, as soon as that size becomes barely vulnerable,
another key-cracking market will appear.  It would be better if we had
a hundred small markets at different sizes.  There might be six
critial keys you really want to crack with your new, expensive, slow,
right-at-the-limit-of-viability 1200 bit cracker - but only six.  To
get the 1300-bit keys you'll need more years of design and
semiconductor evolution.


The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com

Reply via email to