[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

CLAIMING CHUNKS OF KEYSPACE...



Date: Mon, 28 Aug 1995 23:02:01 -0700
To: [email protected]
From: [email protected] (Timothy C. May)
Subject: Claiming chunks of keyspace...


Looking at it from the outside, I thought the latest SSL challenge
experiences were highly instructive. Nothing to be ashamed of.

An interesting question: Is it a valid approach for J. Random User to
"claim" some chunk of keyspace to search?

If the "reward" of finding the gold buried in the keyspace (a key that
meets the  challenge) is high and the cost of claiming the keyspace is low
(or nil), then game theory tells us that some folks will be tempted to
claim a bigger chunk of keyspace than they can possibly process.

What can be done to reduce this effect?

On the negative side, ostracize or punish those who bite off more than they
can chew. This approach is fraught with dangers.

On the positive side, let everyone simply attack the keyspace as they see
fit, picking random parts to attack. This should not be "worse" than a
factor of several from a "perfectly coordinated" attack. (I haven't spent
time calculating this, but my intuition is that a random attack, with
overlapping keyspace, is not a lot less efficiently attacked than
attempting to arrange for no overlaps...just based on my mental picture of
dropping line segments randomly on some interval and figuring coverage of
the line segment.)

In between, market systems where itermediate agents subcontract out chunks
of keyspace. Mechanisms for this are lacking.

-Tim May

---------:---------:---------:---------:---------:---------:---------:----
Timothy C. May              | Crypto Anarchy: encryption, digital money,
[email protected]  408-728-0152 | anonymous networks, digital pseudonyms, zero
Corralitos, CA              | knowledge, reputations, information markets,
Higher Power: 2^756839      | black markets, collapse of governments.
"National borders are just speed bumps on the information superhighway."