tree d0003a1cfa2802a85ed2cab876bd8d0442294df4
parent ecf4ebf10054f70e51a0ce759b2ae91aa4febd1a
author Filippo Valsorda <filippo@golang.org> 1610074618 +0100
committer Roland Shoemaker <roland@golang.org> 1611255139 +0000

crypto/elliptic: fix P-224 field reduction

This patch fixes two independent bugs in p224Contract, the function that
performs the final complete reduction in the P-224 field. Incorrect
outputs due to these bugs were observable from a high-level
P224().ScalarMult() call.

The first bug was in the calculation of out3GT. That mask was supposed
to be all ones if the third limb of the value is greater than the third
limb of P (out[3] > 0xffff000). Instead, it was also set if they are
equal. That meant that if the third limb was equal, the value was always
considered greater than or equal to P, even when the three bottom limbs
were all zero. There is exactly one affected value, P - 1, which would
trigger the subtraction by P even if it's lower than P already.

The second bug was more easily hit, and is the one that caused the known
high-level incorrect output: after the conditional subtraction by P, a
potential underflow of the lowest limb was not handled. Any values that
trigger the subtraction by P (values between P and 2^224-1, and P - 1
due to the bug above) but have a zero lowest limb would produce invalid
outputs. Those conditions apply to the intermediate representation
before the subtraction, so they are hard to trace to precise inputs.

This patch also adds a test suite for the P-224 field arithmetic,
including a custom fuzzer that automatically explores potential edge
cases by combining limb values that have various meanings in the code.
contractMatchesBigInt in TestP224Contract finds the second bug in less
than a second without being tailored to it, and could eventually find
the first one too by combining 0, (1 << 28) - 1, and the difference of
(1 << 28) and (1 << 12).

The incorrect P224().ScalarMult() output was found by the
elliptic-curve-differential-fuzzer project running on OSS-Fuzz and
reported by Philippe Antoine (Catena cyber).

Fixes CVE-2021-3114
Fixes #43786

Change-Id: I50176602d544de3da854270d66a293bcaca57ad7
Reviewed-on: https://go-review.googlesource.com/c/go/+/284779
Run-TryBot: Roland Shoemaker <roland@golang.org>
TryBot-Result: Go Bot <gobot@golang.org>
Trust: Ian Lance Taylor <iant@golang.org>
Trust: Roland Shoemaker <roland@golang.org>
Reviewed-by: Filippo Valsorda <filippo@golang.org>