1
$\begingroup$

I am having a first look at the TLS key exchange using Diffie Hellman and try to understand the Elliptic Curve variant of it.

So if a client and a server agree on using ECDH for key exchange and they use the secp256r1 curve, it seems like the base point G is given and they take it from the standard (04 6B17D1F2 E12C4247 F8BCE6E5 63A440F2 77037D81 2DEB33A0F4A13945 D898C296 4FE342E2 FE1A7F9B 8EE7EB4A 7C0F9E16 2BCE33576B315ECE CBB64068 37BF51F5)

From my understanding, i could use an arbitrary base point G and obtain a group which i can use for my key-exchange. Whats the advantage of using a fixed one? Knowing the base point, wouldnt it be possible to create some kind of rainbow-table and thus crack some connections?

To me it seems more intuite that picking a new base point G every time would increase security. But as far as i understand it, it's not whats done in TLS. Can anyone tell why we pick a fixed base point instead of generating a new one for each key-exchange?

$\endgroup$
8
$\begingroup$

Knowing the base point, wouldnt it be possible to create some kind of rainbow-table and thus crack some connections?

If you could create such a rainbow table that allows you to compute discrete logs of random values to a base $G$ with nontrivial probability $p$, then you can solve the discrete log to any base (with work that takes an expected $O(1/p)$ time.

Here's how it works:

  • You're given the point $H$ and $J$, and want to compute the discrete log of $J$ to base have $H$, that is, the value $x$ s.t. $xH = J$

  • First step, compute the discrete log of $H$ to the base $G$, that is, the value $y$ s.t. $yG = H$. What you do is pick random values $r$, compute $rH$, and use your rainbow table to find try to find the discrete log $y'$ of $rH$. This takes an expected $1/p$ attempts (because $rH$ is a random point), and one we stumble on an $r$ that works, we have $y = r^{-1}y'$

  • Second step, use the same procedure to compute the discrete log $z$ of $J$ to the base $G$; again, this takes an expected $1/p$ attempts.

  • Third step is easy; $x = y^{-1}z$; we're done; that works because $yH=G$ hence $H = y^{-1}G$, and $J = zG$, hence $J = z(y^{-1})H$

On the other hand, for any curve we believe is secure, creating such a rainbow table is infeasible; if the order of the curve is $n$, then the creation would take at least $pn$ point multiplications; for all practical purposes, the standard discrete log algorithms that take $O(\sqrt{n})$ time are more feasible.

Knowing the base point, wouldnt it be possible to create some kind of rainbow-table and thus crack some connections?

In addition to having the same security, it turns out that, if we know $G$ in advance, we can compute $rG$ considerably faster; hence it makes the system faster for the honest parties, and just as secure.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Just to be sure: are you alluding to pre-computation (NAF) in that final sentence, right? $\endgroup$ – Maarten Bodewes Sep 13 at 18:22
  • 2
    $\begingroup$ @MaartenBodewes: there are a lot of various precomputation strategies $\endgroup$ – poncho Sep 14 at 6:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.