BN256 Aggregated Signatures (The Rogue Public Key Attack)In this page, we will aggregate signatures with BN256, along with aggregating the public keys. With this, we will have two key pairs of (\(sk_1,pk_1\)) and (\(sk_2,pk_2\)) and which will produce signatures of \(\sigma_1\) and \(\sigma_2\), respectively. We can then aggregate the signatures with \(\sigma_a = \sigma_1 + \sigma_2\), and the equivalent public key will be \(pk_a = pk_1 + pk_2\). In this case, we will set \(pk_2=-pk_1\) and \(\sigma_2=-\sigma_1\), and which will set the aggregated public key at zero (or the point at infinity). |
Method
With BN256, we create the private key from a random number. This is a scalar value (\(sk_1\)) and a public key mapped to the G2 curve::
\(pub_1=sk_1.G_2\)
Next we create a hash of the message (\(h(M)\)) and then create the signature of:
\(\sigma_1 =sk_1.H(M)\)
Next we check the pair:
\( e(\sigma_1, G_2) == e(H(m), pk_1 )\)
This works because:
\( e(\sigma_1, G_2) == e(H(m), pk_1 )\)
is:
\( e(x.H(M), G_2) == e(H(m), pk_1 )\)
and:
\( e(H(M), x.G_2) == e(H(m), pk_1 )\)
which is:
\( e(H(M), pk_1) == e(H(m), pk_1 )\)
If lhs is equal to rhs, the pairing works, and the signature is verified.
Now we can aggregate the signatures. For a second set of keys, we now have a public key of:
\(pub_2=sk_2.G_2\)
and where the second signature will be:
\(\sigma_2 =sk_2.H(M)\)
Then the aggregated public key will be:
\(pk_a=pub_1+pub_2\)
Then the aggregated signature will be:
\(\sigma_a=\sigma_1+\sigma_2\)
The check is then:
\( e(\sigma_a, G_2) == e(H(m),pk_a )\)
Rogue Public Key Attack
In the Rogue Public Key Attack, Eve can pretend that she is signing the message by creating a public key of:
\(pub_2=-pub_1\)
and a signature of:
\(\sigma_2=-\sigma_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 \(pk_1\) and \(\sigma_1\), and Eve will create a negative value of these, and pass \(pk_2=-pk_1\) and \(\sigma_2=-\sigma_1\). When the public keys and signatures are aggregated, we will get a zero value. Thus:
\(pk_a=0\)
\(\sigma_a=0\)
The check on the aggregated signature will then be:
\( e(\sigma_a, G_2) == e(H(m), pk_a )\)
We be:
\( e([0].G_1, G_2) == e(H(m), [0].G_2 )\)
and which will be the same as:
\( e([0].G_1, G_2) == e([0].H(m), G_2 )\)
and which will be the same as:
\( e([0], G_2) == e([0], G_2 )\)
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:
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:
Message: abc Private key 1: 896c9dcfea9659ea00bfc1ddd97c98271febc873119babd25d25de4ac46968b8 Public key 1: 01026c76c9a917726c83f8748301e39bb34553b59f1877281085cafae9e2ea9499837e91ef55b8f7657ce38bec5c343213f43b96385ad78fbcc298484d1f8aab3e3dbef72f2a43420435239aaca8f34557e616988413df15cf60cc12fc94b867824905b9d1d61c7bb51d593f149ffba192a84ecbc55624b6b6bb8120be579a081a Signature (sigma): 48385fd0e9f6b1a97ddc1a408bad6e806bae49b13121d84a0e07d5d4ec59fb8c325bb417ef4ca540488577ac061445dfb073ce4a698754e3d12c8801593be09f Signature verified! Private key 2: 896c9dcfea9659ea00bfc1ddd97c98271febc873119babd25d25de4ac46968b8 Public key 2: 01026c76c9a917726c83f8748301e39bb34553b59f1877281085cafae9e2ea9499837e91ef55b8f7657ce38bec5c343213f43b96385ad78fbcc298484d1f8aab3e51f60ab4206045f5754c520bb89196ca0844f04d0cd69fceb790996fc9502ee546af481174870c448d16ada3c1893a8f460cbd0bca90fee75cdb8bae066e8e4d Signature (sigma2): 48385fd0e9f6b1a97ddc1a408bad6e806bae49b13121d84a0e07d5d4ec59fb8c5d594dcb5b56e2b961ea750c5b7096423de7ba86b72e60ba4730246b04ccb5c8 Signature aggregated: 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 Public key aggregated: 00 Aggregated Signature verified!