using elliptic curve point multiplication as a key stretching method

Question

My friend came up with the following idea: assuming we agreed on curve parameters, use the following algorithm for key stretching/derivation from user-entered password.

1. Pad the ascii representation of the password to n bits or use any simple hash function, e.g. MD5 to allow passwords of arbitrary length
2. Compute the resulting key as a multiplication of the curve generator point by the number we got at step #1.

In other words, we consider the user-entered password to be the private key of ECDSA and use the public key derivation algorithm as a key stretching function.

Now this looks pretty simple and effective (my CPU only manages to do less than a couple thousand multiplications per second and it seems there is no way to get significant speedups using GPUs). Is this algorithm actually used anywhere? If not, what are some obvious flaws that I can point to for my friend and make fun of him?

EDIT: Thanks for answers! Can't upvote yet due to low rep. The idea was to use this method as a slow hash function for password hashing (as a replacement for bcrypt for example). IMPROVED VERSION: Assuming we use SHA256 in the first step to hash the entered password, then multiply with the generator point in the p256 curve and use the X coordinate of the resulting point as a 256-bit hash of the password. Is this hash good enough for this purpose?

This is a purely theoretical question of course, we are not going to actually use any homebrew cryptography in our app!

Answer 1

I'm assuming you work around the problems pointed out by minar (discrete logarithm) and poncho (output is not uniform) by applying a cheap hash $H$ (such as SHA-256) before and after your point multiplication, i.e. your final hash is something like $$KDF(p) = H( H(p) · P),$$ where $P$ is the base point of your curve, $·$ is point multiplication (the output of $H$ is somehow interpreted as a number) and $p$ is the password, and you chose a curve large enough so that solving discrete logarithms is hard.

You should somehow incorporate a salt $s$, too – maybe into the base point, or hash it together with $p$ first:

$$KDF(p,s) = H(H(p||s)·P)$$

Then you still have not a really good password based key derivation function – such one needs a way to add a work factor into the algorithm. You want your key derivation to be slow (so an attacker who brute-forces the password doesn't get easily to the key), and be able to adapt this slowness when the hardware gets faster.

Something like this might work:

$$\begin{align*} h_0 &= H(p || s) \\ h_{i+1} & = H(p || (h_{i} · P)) \\ KDF(p,s, n) & = h_n \end{align*}$$

$n$ is your work factor.

When using it, set $n$ so large that your users barely accept the waiting time.

This should be a KDF on par with PBKDF2 or maybe bcrypt (I'm not sure how much memory this needs). It is certainly not as good against attackers with custom hardware as scrypt, as you still can quite good parallelize multiple runs of this (with different passwords).

Answer 2

If I understand correctly is to hash your password $pw$ into a point using either $P=Pad(pw)\cdot P_0$ or $P=MD5(pw)\cdot P_0$ and then use $P$ for cryptographic purpose. The exact security of this proposal depends on what you want to do with $P$ exactly. But in some case, this is not secure. Typically, this mechanism is not a good way to hash a password (even if you add salt by varying $P_0$).

Indeed, in this application, you would know $P$ and $P_0$ and recovering the password $pw$ could be done using a discrete logarithm computation. Since $pw$ is generally quite short, $Pad(pw)$ belongs to a short interval of length $N$ (where $N$ is the number of possible padded passwords). In this case, using Pollard's lambda (i.e. The kangaroo method) allows to compute the discrete logarithm at a cost of $\sqrt{N}$. With $MD5$, $N$ is $2^{128}$ which would give a cost of $2^{64}$ to compute the logarithm, probably not enough.

On the other hand, if your application keeps $P$ secret, this is probably not going to apply. So could you tell more about the exact use of $P$ ?

Answer 3

In addition to the severe problem that minar has shown, using point multiplication has an additional problem; some of the output bits can be computed as a function of other output bits. This is a property that we generally do not expect from a key derivation function.

Here's how this works: an ECDSA public key consists of an "X" coordinate and a "Y" coordinate; with the "X" coordinate typically listed first. Each are N bit integers (where N depends on the curve you're using; N=256 if your using the curve P256). Now, the "X" coordinate can be viewed as a random N-bit integer (about half the bit patterns are not possible; however you can't say much more than that). However, if the attacker does recover the value of "X", it is easy to compute the possible values for the "Y" coordinate (there are two possibilities).

Hence, if the attacker somehow recovers the first half of the key derivation output, he can reconstruct the rest. That is probably not a good feature to have.