Cracking Elliptic Curves with the MOV Attack

Cracking Elliptic Curves with the MOV Attack

Elliptic Curve Cryptography (ECC) is wiping the floor with other key exchange, signing and encryption methods. Overall it is well defined for a scale up in security, and where a 256-bit ECC key is equivalent in security to a 3,072-bit RSA key. But ECC still has one weakness: the MOV Attack, and which uses pairing-based cryptography.

With 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.

Coding

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

package main

import "fmt"

import "github.com/miracl/core/go/core"
import "github.com/miracl/core/go/core/BN254"
import "math/rand"
import "time"

func FP12toByte(F *BN254.FP12) []byte {

	const MFS int = int(BN254.MODBYTES)
	var t [12 * MFS]byte

	F.ToBytes(t[:])
	return(t[:])
}
func randval() *core.RAND {

    s1 := rand.NewSource(time.Now().UnixNano())
    r1 := rand.New(s1)

    rng := core.NewRAND()
    var raw [100]byte
    for i := 0; i < 100; i++ {
       raw[i] = byte(r1.Intn(255))
    }
    rng.Seed(100, raw[:])
    return rng
}

func main() {

    	q := BN254.NewBIGint(4096)

    	x := BN254.Randomnum(q,randval())
	fmt.Printf("Secret: %d\n",x)
    	P:= BN254.ECP_generator() // Generator point in G1
    	Q:= BN254.ECP2_generator() // Generator point in G2

    	xP := BN254.G1mul(P,x)

	RHS := BN254.Ate(Q,P);  RHS=BN254.Fexp(RHS)

	LHS:=BN254.Ate(Q,xP);  LHS=BN254.Fexp(LHS)

	fmt.Printf("Pairing e(Q,P) (first 20 bytes):\t0x%x\n",FP12toByte(RHS)[:20])
	fmt.Printf("Pairing e(Q,xP) (first 20 bytes):\t0x%x\n",FP12toByte(LHS)[:20])

	for i := 1; i <= 4096; i++ {
		pair2:=RHS.Pow(BN254.NewBIGint(i))
	
		if (LHS.Equals(pair2)) {
			fmt.Printf("Found it %d\n",i)
			break
		}
	}

}

A sample run [here]:

Secret: &{[2386 0 0 0 0]}
Pairing e(Q,P) (first 20 bytes):	0x0d8a793b0defaef46557b6694e97514cc17a5ef2
Pairing e(Q,xP) (first 20 bytes):	0x1b4ebad5fc54ff2a308c80c5ec2b68a9b9834f88
Found it 2386

So, here is a simple example: