Cracking Elliptic Curves Using Pairing and Kryptology

Cracking Elliptic Curves Using Pairing and Kryptology

Well, the title is not quite correct, as the method we will use will not crack elliptic curves, but will reduce their strength. And don’t worry about your Bitcoins, as we do not reduce it to the level where cracking a private key would be feasible, and would still take all the energy in the world — and much more — to even crack one Bitcoin wallet.

Introduction

Elliptic curves are protecting you online like no other method. They are likely to be at the core of the generation of the encryption key that you are using to keep the data on this Web page secure. This is done with the magic of ECDH (Elliptic Curve Diffie Hellman), and where your browser negotiate a shared symmetric key (normally with AES) and this key is used to encrypt the data that the Medium sends to you. Along with this, we can prove the identity of the server with a digital signature. This again can be done with elliptic curves using ECDSA or EdDSA. In Bitcoins and Ethereum we see extensive usage of the secp256k1 curve. This is used to both generate a public address, and to sign transactions.

How do they work?

Well, elliptic curve cryptography defines a base point (G) and then a secret value of a. We can then compute a point on the curve at P=aG. This is equivalent to G+G+…G, for a times. At present, it is an extremely difficult task to discover a given G and aG:

Cracking with MOV

Pairing-based cryptography is used in many areas such as zero-knowledge proofs, IBE, signcryption, oblivious transfer, CP-ABE (Cipher Policy Attribute-Based Encryption), short signatures, group signatures, and merged signatures. But, its first application was in reducing the strength of elliptic curves.

In a classic paper, Menezes and Vanstone [1] defined how we could reduce the strength of the elliptic curve method to a discrete logarithm problem [here]:

The method uses key pairing we have two cyclic groups (G1 and G2), and which are of an order of a prime number (n). A pairing on (G1,G2,GT) defines the function e:G1×G2→GT, and where g1 is the generator for G1 and g2 is the generator for G2. If we have the points of P on G1 and Q on G2, we get a pairing of:

e(P,Q)

Now if we select a private key value of x, and then the public key will become:

Ppub=xP

In order to find x, we would have to search the values of x to match P to x. In pairing, we can reduce the difficulty with:

e(xP,Q)=e(P,Q)^x

This now becomes a discrete logarithm problem within a finite field, and which makes it easier to find x.

Implementation

Let’s keep it simple by generating a value of x between 0 and 1000, and just uses brute force to find x. The outline coding using the library from the Kryptology library is [here]:

package main

import (
	"fmt"
	"math/big"
	"os"
	"strconv"

	bls12381 "github.com/coinbase/kryptology/pkg/core/curves/native/bls12-381"
)

func main() {

	val1 := int64(10)

	argCount := len(os.Args[1:])

	if argCount > 0 {
		val1, _ = strconv.ParseInt(os.Args[1], 10, 64)
	}

	fmt.Printf("Value to find: a=%d\n\n", val1)

	bls := bls12381.NewEngine()
	g1, g2 := bls.G1, bls.G2
	gt := bls.GT()

	a := big.NewInt(val1)

	G1, G2 := g1.One(), g2.One()
	P2 := g2.New()

	g2.MulScalar(P2, G2, a)

	e0, _ := bls.AddPair(G1, P2).Result()

	fmt.Printf("P1: %x\n", P2)

	for i := 1; i < 1000; i++ {

		ival := big.NewInt(int64(i))
		e1, _ := bls.AddPair(G1, G2).Result()

		gt.Exp(e1, e1, ival)

		if e0.Equal(e1) {
			// e(G1,aG2) = e(G1,G2)^a
			fmt.Printf("We have found the value at %d\n", i)
			break
		}

	}

}

In this case, we search on the G1 curve, and take and match the pairings of e(xG1,G2) to e(G1,G2)^x, and where G1 and G2 are the base points on the curves. A sample run [here]:

Value to find: a=100

We have found the value at 100
Time: 322 uS

We can see that it takes us 322 microseconds to just search 100 points, so to search for half the key space (2¹²⁸) is going to take an extremely long time. In fact, it will still take around:

3,580,000,000,000,000,000,000,000,000 years

Conclusions

As I said, don’t worry about your Bitcoins. They are still safe against the MOV attack. But, worry about quantum computers, as they will be able to crack elliptic curves in a reasonable amount of time. For this, we need to look to replace elliptic curve methods with quantum robust methods such as lattice-based encryption.

If you are interested in knowing more about Kryptology, try here:

https://asecuritysite.com/kryptology/

and for pairing-based cryptography here:

https://asecuritysite.com/pairing/

References

[1] Menezes, A. J., Okamoto, T., & Vanstone, S. A. (1993). Reducing elliptic curve logarithms to logarithms in a finite field. IEEE Transactions on Information Theory, 39(5), 1639–1646.