Beware of The Rogue Public Key
Beware of The Rogue Public Key
With BN256, we create the private key from a random number. This is a scalar value (sk1) and a public key mapped to the G2 curve:
pub_1=sk_1.G2
Next, we create a hash of the message (H(M)) and then create the signature of:
σ_1=sk1.H(M)
Next, we check the pair:
e(σ1,G_2)==e(H(m),pk_1)
This works because:
e(σ_1,G_2)==e(H(m),pk_1)
is:
e(x.H(M),G2)==e(H(m),pk1)
and:
e(H(M),x.G2)==e(H(m),pk1)
which is:
e(H(M),pk1)==e(H(m),pk1)
If lhs is equal to rhs, the pairing works, and the signature is verified.
Now we can aggregate the signatures. For the second set of keys, we now have a public key of:
pub2=sk2.G2
and where the second signature will be:
σ2=sk2.H(M)
Then the aggregated public key will be:
pk_a=pub1+pub2
Then the aggregated signature will be:
σ_a=σ1+σ2
The check is then:
e(σa,G2)==e(H(m),pk_a)
In the Rogue Public Key Attack, Eve can pretend that she is signing the message by creating a public key of:
pub2=−pub1
and a signature of:
σ2=−σ1
A negative value is fairly easy to implement, as we just need to make the y-axis value negative, and can leave the x-axis value the same. If Bob and Eve are signing a message (M), Bob will pass pk1 and σ1, and Eve will create a negative value of these, and pass pk2=−pk1 and σ2=−σ1. When the public keys and signatures are aggregated, we will get a zero value. Thus:
pk_a=0
σ_a=0
The check on the aggregated signature will then be:
e(σa,G2)==e(H(m),pk_a)
And is:
e([0].G1,G2)==e(H(m),[0].G2)
and which will be the same as:
e([0].G1,G2)==e([0].H(m),G2)
and which will be the same as:
e([0],G2)==e([0],G2)
And so the test will pass if the zero aggregation is not checked. Eve has thus signed for a message that she does not know anything about its contents. We should thus always check for a zero value in the public key and/or in the signature, and reject them if they are zero.
Coding
An outline of the Go code is given next [here], and the aggregation part is highlighted:
package main
import (
"bytes"
"fmt"
"math/big"
"os"
"crypto/rand"
"github.com/cloudflare/bn256"
)
func main() {
salt := []byte{11, 12, 13, 14}
message:="Hello"
argCount := len(os.Args[1:])
if argCount > 0 {
message = os.Args[1]
}
msg := []byte(message)
G2 := new(bn256.G2).ScalarBaseMult(big.NewInt(1))
privKey, _, _ := bn256.RandomG2(rand.Reader)
pubKey := new(bn256.G2).ScalarBaseMult(privKey)
hash := bn256.HashG1(msg, salt)
sigma := new(bn256.G1).ScalarMult(hash, privKey)
rhs := bn256.Pair(hash, pubKey)
lhs := bn256.Pair(sigma, G2)
fmt.Printf("Message: %s\n", message)
fmt.Printf("Private key 1: %x\n", privKey)
fmt.Printf("\nPublic key 1: %x\n", pubKey.Marshal())
fmt.Printf("\nSignature (sigma): %x\n", sigma.Marshal())
if bytes.Equal(rhs.Marshal(), lhs.Marshal()) {
fmt.Printf("\nSignature verified!\n")
}
betapubKey:= new(bn256.G2).ScalarBaseMult(privKey)
betapubKey.Neg(betapubKey)
pub_aggr := pubKey.Add(pubKey, betapubKey)
sigma2 := new(bn256.G1).ScalarMult(hash, privKey)
sigma2.Neg(sigma2)
sigma_aggr :=sigma.Add(sigma, sigma2)
fmt.Printf("Private key 2: %x\n", privKey)
fmt.Printf("\nPublic key 2: %x\n", betapubKey.Marshal())
fmt.Printf("\nSignature (sigma2): %x\n", sigma2.Marshal())
fmt.Printf("\nSignature aggregated: %x\n", sigma_aggr.Marshal())
fmt.Printf("\nPublic key aggregated: %x\n", pub_aggr.Marshal())
rhs = bn256.Pair(hash, pub_aggr)
lhs = bn256.Pair(sigma_aggr, G2)
if bytes.Equal(rhs.Marshal(), lhs.Marshal()) {
fmt.Printf("\nAggregated Signature verified!")
}
}
A sample run is [here]. Notice that the aggregated public key and signature values have been set of zero:
Message: abc
Private key 1: 27534a44b6084b6c16be955dfaf6a268b579de5d7371ff624908fc8854958c4
Public key 1: 0159a5a54d15a9fc3d62d931117d4bc55a99f70c111bead20e2654fa0bc08cdbb065a897ef675f628cd4a1c5ed00fae8bc8f475196524ded55719374b28707f612258f55e2dd206c3bed3259d89f59c142d6d6f4b7cfccda06f6cb9da77cbeaec88b2c59f0e2bbf4ef26db0e5c443d7761b9a7c72eb19bdefc071cca5867902fcb
Signature (sigma): 439e90c858cf2b4b17eb9ad3141d40a7475d6415389dd15247c12d1e314367d15dc5c863c98631b61be630c30c63392fe1de1dd575eb4fa25066a067b570f34f
Signature verified!
Private key 2: 27534a44b6084b6c16be955dfaf6a268b579de5d7371ff624908fc8854958c4
Public key 2: 0159a5a54d15a9fc3d62d931117d4bc55a99f70c111bead20e2654fa0bc08cdbb065a897ef675f628cd4a1c5ed00fae8bc8f475196524ded55719374b28707f6126a25ac006d831bbdbd3d92dfc22b1adf1784941950e8db9721910ec4e149e79f0488a7f267e7930a8394de5c1d4764c034b3c1a26f19d6a2113fe213f678669c
Signature (sigma2): 439e90c858cf2b4b17eb9ad3141d40a7475d6415389dd15247c12d1e314367d131ef397f811d56438e89bbf55521a2f20c7d6afbaaca65fbc7f60c04a897a318
Signature aggregated: 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
Public key aggregated: 00
Aggregated Signature verified!
We can see that Eve has taken Bob’s public key, and has no idea about the message she is signing. She then creates a negative value of his value and passes that with the negative value of the signature. When Trent checks the signature, it looks like both Bob and Eve have signed for the message. Perhaps this might be to transfer some cryptocurrency from Bob to Eve?
Conclusions
Developers need to be trained to spot zero values within computations, as Eve doesn’t always play by the rules.
Here’s the Rogue Public Key attack: