The First Rule of Cryptography … You Don’t Talk About Zero
Not!
Okay, sorry for mis-quoting Fight Club! Overall, the title is a little bit tongue-in-cheek, as the zero value is often a major problem in cryptography, and where we often just don’t want it to happen. It can, too, be a blind spot for security architects and developers, and who implement calculations without checking for the zero value.
Why is zero such a problem? Well, to perform our cryptographic processing, we use mathemtical operations, such as with multiplication and division. As you should remember when we multiply by zero we get zero, and when we divide by it, we get infinity. These operations will reset the calculation, and no matter what we do we can never recover any previous information from our value. We might also use exponents, and where g⁰ gives us unity.
Within our secure computations we typically need to reverse an operation back to an original value. This often involves encrypting — performing a certain mathematical operation — and then decrypting — reversing the same mathematical operation.
For example, if we multiply a value of seven by four, and add three, we can compute:
Val = 7 * 4 + 3 = 31
and, to reverse, we just subtract 3 and divide by 4:
Res = (31 -3) /4 = 7
But, if I multiply by zero and then add three:
Val = 7 * 0+ 3 = 3
And reverse:
Val = (3–3)/0 = Infinity (or, who knows, as it is 0/0!)
And, so, we often want to avoid a value of zero, as it can short-circuit all our calculations and cause serious errors. Zero becomes are reset value, and where all previously computed values are lost. Thus, our computations should always check that we do not have a zero value, otherwise, all the answers we get are likely to be wrong. Even worse, we may continue to do our calculations, and get affirmative answers, such as incorrectly signing for data. In signatures, we often compare two values, but where a zero value for a public key could cause an invalid signature to be value.
Stopping zero values in discrete logs
In a finite field, we often use a (mod p) operation, and where p is a prime number. And so if we get a value which is a multiple of p we will also get a zero value. If p is 7, and if we have a message of 14, we will get:
Val = 14 (mod 7) = 0
This will equal zero, and where we will not be able to recover our value. For this, in discrete logs we have:
Val = g^x (mod p)
and where we pick g (the generator) so that we will never have a zero value. So it we have p=7, and can try different generator values [here]:
We can see that a value of g=2 does not work with p=7, as we do not output the full range of values (1 to 6), but g=3 works, as:
3¹ (mod 7) = 1
3² (mod 7) = 2
3³ (mod 7) = 6
and so on. We will then be able to map all these values back to the original values, and thus reverse the values. And, so, developers should check at important points that they are not getting zero values and that the base generator is correctly selected.
And, Eve, of course, doesn’t play by the rules and could trick Bob into short-circuiting his cryptography process.
Zero’s in elliptic curves
We have typically moved from discrete log methods into elliptic curve techniques, and where we deal with scalar values and elliptic curve points. If I have a private key of a, then my public key can be a.G, and where G is the base point on the curve. This is basically G+G+G … +G, and where the point G is added for a times. Overall, it is extremely difficult to determine a, if we have a.G and G.
But, elliptic curves have a zero problem, too. What happens if take a point p1, and then -p1, the addition of the points will be:
p = p1 — p1 = 𝑂
This is the zero point and is also defined as the point at infinity. In most elliptic curves, we basically just negate the y-coordinate value and keep the x co-ordinate value, the same. Eve could then trick Bob into using a weak generator value, that she can easily hack.
So now let’s look at a serious example of creating a zero point, and which can compromise an electronic wallet.
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 mainimport (
"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: 896c9dcfea9659ea00bfc1ddd97c98271febc873119babd25d25de4ac46968b8Public key 1: 01026c76c9a917726c83f8748301e39bb34553b59f1877281085cafae9e2ea9499837e91ef55b8f7657ce38bec5c343213f43b96385ad78fbcc298484d1f8aab3e3dbef72f2a43420435239aaca8f34557e616988413df15cf60cc12fc94b867824905b9d1d61c7bb51d593f149ffba192a84ecbc55624b6b6bb8120be579a081aSignature (sigma): 48385fd0e9f6b1a97ddc1a408bad6e806bae49b13121d84a0e07d5d4ec59fb8c325bb417ef4ca540488577ac061445dfb073ce4a698754e3d12c8801593be09fSignature verified!
Private key 2: 896c9dcfea9659ea00bfc1ddd97c98271febc873119babd25d25de4ac46968b8Public key 2: 01026c76c9a917726c83f8748301e39bb34553b59f1877281085cafae9e2ea9499837e91ef55b8f7657ce38bec5c343213f43b96385ad78fbcc298484d1f8aab3e51f60ab4206045f5754c520bb89196ca0844f04d0cd69fceb790996fc9502ee546af481174870c448d16ada3c1893a8f460cbd0bca90fee75cdb8bae066e8e4dSignature (sigma2): 48385fd0e9f6b1a97ddc1a408bad6e806bae49b13121d84a0e07d5d4ec59fb8c5d594dcb5b56e2b961ea750c5b7096423de7ba86b72e60ba4730246b04ccb5c8Signature aggregated: 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000Public key aggregated: 00Aggregated 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
The first rule of cryptography is that we need to talk about the zero value. Developers need to be trained to spot it within computations, as Eve doesn’t always play by the rules.
Here’s the Rogue Public Key attack:
