crypto/elliptic: different ecdsa.Verify result between p256 amd64 and generic implementations with a zero hash

[tzneal]

What version of Go are you using (go version)?

tip

What operating system and processor architecture are you using (go env)?

GOARCH=386 and GOARCH=amd64

What did you do?

Code pulled from golang-nuts post https://groups.google.com/forum/#!topic/golang-nuts/M7tXCf8a4pk

$ GOARCH=386 go build -o cr32 && ./cr32
2017/05/02 21:10:00 Verification succeded
$ go build -o cr64 && ./cr64
2017/05/02 21:10:00 Failed

What did you expect to see?

I assume the verification should have failed in both cases.

What did you see instead?

Verification passed for the 32 bit binary.

Cause

The difference is in the path taken in ecdsa.Verify:

	var x, y *big.Int
	if opt, ok := c.(combinedMult); ok {
		x, y = opt.CombinedMult(pub.X, pub.Y, u1.Bytes(), u2.Bytes())
	} else {
		x1, y1 := c.ScalarBaseMult(u1.Bytes())
		x2, y2 := c.ScalarMult(pub.X, pub.Y, u2.Bytes())
		x, y = c.Add(x1, y1, x2, y2)
	}

The S390 and AMD64 versions of CombinedMult appear to always set the Z value to 1 regardless of X and Y.

(*curveParams).Add calls zForAffine which returns a Z value of 0 if X or Y are zero.

Modifying zForAffine to match the behavior of the optimized CombinedMults (Z=1 in all cases) causes TestInfinity to fail, but otherwise the generic and optimized CombinedMults give the same output for this case.

[bradfitz]

Saving others a click, code is:
https://gist.github.com/ivoras/32b2abd16b5984fa43c006486bfb7e2c

[bradfitz]

Verified the 386/amd64 difference is the same in Go 1.7, Go 1.8, and tip.

[gopherbot]

CL https://golang.org/cl/42590 mentions this issue.

[agl]

(I believe the verification should have passed in both cases, rather than failed. I.e. the referenced test case appears to be a valid signature of a zero hash. That means that we're rejecting a valid signature rather than accepting an invalid signature, which is less of a problem at least.)

[agl]

(For my own reference in the future: there's an incomplete fix in https://go-review.googlesource.com/c/42611, but it'll need assembly changes and I'm not going to attempt that today; I'll only mess it up.)

[gopherbot]

CL https://golang.org/cl/42611 mentions this issue.

[bradfitz]

@agl, do you want this in Go 1.8.2? If so, can we wrap up the review? If not, we can roll Go 1.8.2 already with just #20040 fix.

[bradfitz]

(I believe the verification should have passed in both cases, rather than failed. I.e. the referenced test case appears to be a valid signature of a zero hash. That means that we're rejecting a valid signature rather than accepting an invalid signature, which is less of a problem at least.)

Per that comment, I'm going to mark this as Go 1.9 material and not Go 1.8.2.

[bradfitz]

@agl, do you want this (your https://go-review.googlesource.com/c/42611/) in Go 1.9 or should we bump it to Go 1.10?

[AnomalRoil]

The question here should also be "what should we do if we have a zero hash in ECDSA, knowing that this may partly breaks ECDSA"...
If you have a null hash then the verification process goes as usual with correctly generated signature, excepted that you can trick it into validating your message simply by providing the signature (r,s)=(x,x) where (x,y) are the coordinates of the ECDSA public key !
Also, note that all dependency upon the secret material is removed when the hash value is congruent to 0 mod n.

A crafted signature would then validate since upon verification you compute:

• e = H(m) = 0.
• Let z be the L_n (the bit length of the group order n) leftmost bits of e, so it's zero.
• w = s^-1 = x^-1 (mod n) by my choice of s.
• u₁ = zw ≡ 0 (mod n) and u₂ = rw = xw ≡ 1 (mod n).
• the curve point computed in the verification becomes:
  (x₁, y₁) = u₁⋅ G + u₂ ⋅ Q = 0 ⋅ G + 1 ⋅ Q = Q = (x, y)
• The signature is valid if x₁ ≡ r (mod n), invalid otherwise, but this is the case by choice of the signature's value r = x.

Now, we should ask ourselves what we want to do when confronted to such a zero hash, or such a strange signature... So the zero hash does not permit us to ensure the authenticity of the signature since such forgeries are possible (note that there might be other less trivial forgeries).

So far, I've done a few tests on the topic to see how other are handling it and have found that:

• OpenSSL will gladly validate such signatures, both valid and crafted.
• mbedTLS answers with an error "MBEDTLS_ERR_ECP_INVALID_KEY" on zero values upon verification, but not upon signature as it generates valid signatures (which are validated on the Playground or by OpenSSL).
• CryptoPP will reject the signatures it generated using a zero hash, but while it accepts the crafted signatures or signatures made using Go, its signatures are rejected by other implementations because they are not valid.
• Go crypto currently rejects such signature on my computer (amd64) but accept them on the playground as proved by this playground example I just made: https://play.golang.org/p/WTic53IPm6 whose code returns twice false on my computer, but true on the playground. (which is exactly why this issue exists in the first place)

I must say that I'm not really sure what would be the best way around this issue. I believe that we should reject the signatures as soon as the values u₁ or u₂ are zero, or throw an error maybe. (This is fine since secret material is not involved in the verification process and signing the zero hash value does not leak secret material as long a the k value is secret and well randomly generated.)

I don't know what is your opinion on that topic @agl ?

[gopherbot]

Change https://golang.org/cl/62630 mentions this issue: crypto/elliptic: drop s390x assembly.

[gopherbot]

Change https://golang.org/cl/62292 mentions this issue: crypto/elliptic: temporarily disable s390x assembly

[gopherbot]

Change https://golang.org/cl/64290 mentions this issue: crypto/elliptic: fix incomplete addition used in CombinedMult on s390x