# Cryptoanalysis challenge

*tomstdenis_at_gmail.com*

**Date:** 10/17/05

**Next message:**Kristian Gjøsteen: "Re: needed: reviewers for an implementaion of AES"**Previous message:**ddyer_at_real-me.net: "Re: needed: reviewers for an implementaion of AES"**Next in thread:**Ben Livengood: "Re: Cryptoanalysis challenge"**Reply:**Ben Livengood: "Re: Cryptoanalysis challenge"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]

Date: 17 Oct 2005 11:13:48 -0700

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.

**Next message:**Kristian Gjøsteen: "Re: needed: reviewers for an implementaion of AES"**Previous message:**ddyer_at_real-me.net: "Re: needed: reviewers for an implementaion of AES"**Next in thread:**Ben Livengood: "Re: Cryptoanalysis challenge"**Reply:**Ben Livengood: "Re: Cryptoanalysis challenge"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]