Cryptoanalysis challenge

Here's a challenge for the interested amateur. If you compete you'll
learn some new things and maybe get some cred.

In doing ECC point multiplications there is an algorithm known as the
Fixed Point [1] method (also known by other names, iirc, the "comb"
method). It computes a point multiplication in a constant and ideally
minimal amount of time using modest amounts of memory.

One of the flaws is that it isn't suitable for random point
multiplication because you have to generate the precomputed tables for
any base point you want to multiply.

The EC-DH protocol essentially works as follows [2]

You want to calculate a shared secret with Bob's public key Y

1. pick a random k
2. Compute Z = kG
3. Compute R = kY
4. Send kG to Bob
5. Use the x co-ordinate of R as the shared secret

The other side computes

Y = xG
1. Compute R = xZ
2. Use the x co-ordinate of R

For the computation in step 2 and 3 of the generation algorithm we know
G and Y in advance and hence can pre-compute those values. But we do
not know Z in advance.

To speed this up we could transmit the tables for Z along with kG.
Clearly this slows down the generation side but if we only care about
the receive side it doesn't matter.

What is the security flaw in this protocol? (Yes, it is seriously
flawed).

Tom

[1] and [2] are good things to use citeseer to look for.
Received on Mon Oct 17 20:48:42 2005