Check that Y is a root of Y^2 in point decompression routine

[bdonlan]

The point decompression routine at https://github.com/aws/aws-encryption-sdk-python/blob/master/src/aws_encryption_sdk/internal/crypto/elliptic_curve.py#L109 computes Y by taking the root of Y^2, but does not verify that the resulting Y does in fact give that original Y^2 upon squaring. In the general case, this check is necessary to avoid invalid point attacks, where the value of X^3 + A*X + B does not have a root in the field.

Fortunately, in our use case, because we're only using this for an ECDSA verify operation, an attacker with control of the public key point would already have the ability to construct a valid signature, so this is not a security issue with the code as it stands today. However, we should fix this to avoid problems if this function is someday reused for point decompression of ECDH shares, or some other similar operation.

Tagging @SalusaSecondus for visibility.

[bdonlan]

Note that alpha = Y^2; square root in a prime field where p % 4 = 3 is performed by doing Z^1/2 = Z^((p+1)/4), which happens on line 148

[mattsb42-aws]

Notes here for later reference:

Given alpha == y^2[1].

For p % 4 == 3, beta[2] and p - beta[3] are the square roots of alpha in modulo space p.

As such, regardless of y_order value, y is a square root of alpha in modulo space p.

We need to add a check that pow(y, 2, params.p) == alpha.

[1] https://github.com/aws/aws-encryption-sdk-python/blob/master/src/aws_encryption_sdk/internal/crypto/elliptic_curve.py#L140
[2] https://github.com/aws/aws-encryption-sdk-python/blob/master/src/aws_encryption_sdk/internal/crypto/elliptic_curve.py#L148
[3] https://github.com/aws/aws-encryption-sdk-python/blob/master/src/aws_encryption_sdk/internal/crypto/elliptic_curve.py#L154

[farleyb-amazon]

Resolving this in favor of the related issue on the spec repo. Our plan is to track compliance with the specification with a new mechanism.