Fix poly1305-x86.pl.

Imported from patch attached to
https://rt.openssl.org/Ticket/Display.html?id=4439.

But with the extra vs $extra typo fixed.

The root problem appears to be that lazy_reduction tries to use paddd instead
of paddq when they believe the sum will not overflow a u32. In the final call
to lazy_reduction, this is not true. svaldez and I attempted to work through
the bounds, but the bounds derived from the cited paper imply paddd is always
fine. Empirically in a debugger, the bounds are exceeded in the test case.

I requested more comments from upstream on the bug. When upstream lands their
final fix (hopefully with comments), I will update this code. In the meantime,
let's stop carrying known-broken stuff.

(vlazy_reduction is probably something similar, but since we don't enable that
code, we haven't bothered analyzing it.)

Also add the smaller of the two test cases that catch the bug. (The other uses
an update pattern which isn't quite what poly1305_test does.)

Change-Id: I446ed47c21f10b41a0745de96ab119a3f6fd7801
Reviewed-on: https://boringssl-review.googlesource.com/7544
Reviewed-by: Steven Valdez <svaldez@google.com>
Reviewed-by: David Benjamin <davidben@google.com>

2 files changed, 14 insertions, 8 deletions

diff --git a/crypto/poly1305/asm/poly1305-x86.pl b/crypto/poly1305/asm/poly1305-x86.pl
index 75f66467..4ad2289e 100755
--- a/crypto/poly1305/asm/poly1305-x86.pl
+++ b/crypto/poly1305/asm/poly1305-x86.pl
@@ -527,6 +527,7 @@ my $base = shift; $base = "esp" if (!defined($base));
 
 sub lazy_reduction {
 my $extra = shift;
+my $paddx = defined($extra) ? paddq : paddd;
 
 	################################################################
 	# lazy reduction as discussed in "NEON crypto" by D.J. Bernstein
@@ -550,12 +551,12 @@ my $extra = shift;
 							# possible, because
 							# paddq is "broken"
 							# on Atom
-	&pand		($D1,$MASK);
-	&paddq		($T1,$D2);			# h1 -> h2
 	 &psllq		($T0,2);
+	&paddq		($T1,$D2);			# h1 -> h2
+	 &$paddx	($T0,$D0);			# h4 -> h0
+	&pand		($D1,$MASK);
 	&movdqa		($D2,$T1);
 	&psrlq		($T1,26);
-	 &paddd		($T0,$D0);			# h4 -> h0
 	&pand		($D2,$MASK);
 	&paddd		($T1,$D3);			# h2 -> h3
 	 &movdqa	($D0,$T0);
@@ -1695,18 +1696,18 @@ sub vlazy_reduction {
 	&vpsrlq		($T1,$D1,26);
 	&vpand		($D1,$D1,$MASK);
 	&vpaddq		($D2,$D2,$T1);			# h1 -> h2
-	 &vpaddd	($D0,$D0,$T0);
+	 &vpaddq	($D0,$D0,$T0);
 	 &vpsllq	($T0,$T0,2);
 	&vpsrlq		($T1,$D2,26);
 	&vpand		($D2,$D2,$MASK);
-	 &vpaddd	($D0,$D0,$T0);			# h4 -> h0
-	&vpaddd		($D3,$D3,$T1);			# h2 -> h3
+	 &vpaddq	($D0,$D0,$T0);			# h4 -> h0
+	&vpaddq		($D3,$D3,$T1);			# h2 -> h3
 	&vpsrlq		($T1,$D3,26);
 	 &vpsrlq	($T0,$D0,26);
 	 &vpand		($D0,$D0,$MASK);
 	&vpand		($D3,$D3,$MASK);
-	 &vpaddd	($D1,$D1,$T0);			# h0 -> h1
-	&vpaddd		($D4,$D4,$T1);			# h3 -> h4
+	 &vpaddq	($D1,$D1,$T0);			# h0 -> h1
+	&vpaddq		($D4,$D4,$T1);			# h3 -> h4
 }
 	&vlazy_reduction();
 
diff --git a/crypto/poly1305/poly1305_test.txt b/crypto/poly1305/poly1305_test.txt
index 7e988678..0bbf51d0 100644
--- a/crypto/poly1305/poly1305_test.txt
+++ b/crypto/poly1305/poly1305_test.txt
@@ -134,3 +134,8 @@ MAC = c6e5d1810fd878ac6b844c66cef36a22
 Key = 000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f
 Input = 248ac31085b6c2adaaa38259a0d7192c5c35d1bb4ef39ad94c38d1c82479e2dd2159a077024b0589bc8a20101b506f0a1ad0bbab76e83a83f1b94be6beae74e874cab692c5963a75436b776121ec9f62399a3e66b2d22707dae81933b6277f3c8516bcbe26dbbd86f373103d7cf4cad1888c952118fbfbd0d7b4bedc4ae4936aff91157e7aa47c54442ea78d6ac251d324a0fbe49d89cc3521b66d16e9c66a3709894e4eb0a4eedc4ae19468e66b81f271351b1d921ea551047abcc6b87a901fde7db79fa1818c11336dbc07244a40eb14cf77bde35e78ae9ad7d3f57ed7e7f23926c9172f82d77684ea5ed7d74ebc6f142b997036bcb7cce8df1bbc0d5b35a46509c954fc9469d214d6238f166cbf872156b4c41d7aac5942cffb175023078252a3f36e315c5d4ce0e39928a018252862becacef96a19f03bdcf46d75584299d1f8b03c0169e9e407d937145b5e5024139e7022a1978f114f24cdfa23780a119735c41da8fb759bbb3f025c6ec30e6c6e9bce8615be68e392fce59fd26a8e6a6cc5c606e3848116e4d01d29565a1facfb524b6d29643b826eee1e42869fc76df229dd79b39a2b1df28bb335c3a5f15a855d0121e4a6da34b5e4d5b7b5d5746a03ecff70811e1516fcec1bf7462e8876a2d21710aa168c78f45a6a15015950e221da85d3ec822ad6d0a6931b25a06b7bb5f3c10bb36cd4d647f9561982fde9818de5d4bf8db7f86c53b4ff14928ac15f79023b61861e73e44216540bb302153770da2533de9795252ab5fb77ad924c9338c8144c23d4c90dab9a18feac1a1574d4545e1435eb405e6c4c439fc724fce992ae85badf345bad16d85fbd338f04433703614754d0e7e54c4ccde2670587d52ecfb5a70a14a501bacc727722649931d8515b13d020a78e511fe136d45fbf97f9c7f689fcc677cfb3683723878350ffe9d08130cc6e567b6179e01b7eb2b3bbcf0873e1308eec018edeb8cce946338e15d5bf68c71916a83a99358039ef071e009546a2df936879dffbba397a93925d229a469fd17d71b7f524e03a30da6ee927542f8b369bed4734fe25dbd63d24ffd2a222f5f84f75d858ab989be925af570ad6d45bd28ce61b5139e1dd2f0b7795fe072e6e83acbb5e7b777a70c641e4cab2af40eed69abc334cd2703c3273204fac580c6a3d6680427e5f7d051e8380a53f93a180f4556ecea4530b9a2d5948dad63d415b6874f6b90e767d6d265be86351b53ba690780bb57c21b57418c5b97559e840c68257f839e7583a4bf7c7645c5987d40cc1ba79a218c35edfacdabe581d950e4bb7a481ebe64d61d00e75b1f25f1ce5f5462334a5b9038a697aa0937a3f8017e05d2c9c05dcb05c0b02508dea619b137f5444b6f088eb3cb2c66788f88afdfbba8faa1c490485624c88ae11e57347a676902e7553f056188493209bdbb30acc63c9e41e16a9d6c009416b520a76ba38f57628170c43626b5cb46179dc5bf65de865085f84bf741c223fbe474d2d19d8f43914fbd6586351089e73babf344f988b7963fe44528457d7aad3c564f6bcbd0d772a4c9fd328e6022d1c7c9f86726f8d5a23797d309c0f653ab1ac687833eb2700f156296062a8b377078f45f6b68c3d07cae1913ba8d5a6f9bf7525a3439eb932d4cefc4bf8e1b07b48ca13ece366cbc3e0388915915d1757475103a9e9454e7e6355de2d6acbf4710f9a63e4f6d3cd70c2d6fca88dd8a14448fdb63ce9350fdaafbe0b8bd1c5d307dae76dfed799aef2d8f23d5608d37d1330dd38b94860905dbeebf78d7b7318b7d42aed40d3f9899e9f420cbd92a6eeae3026f7725694e0e4bee016ba346fed2c21172bdb4a461cebe0cfe38e76645226ac127a259c193264d735ce8c8a57e17dd3f0579e2e86dc295ad1f45ba2d85db35044da61f7d401274b31eefbeb34e8d2ae596e9b4541aae117bdac5ed0b324c20539c27c07a411d5288b0b5f6fa16e9a7df85dc319fa6b71cd08a859c06a3f7b0289e1750adbf182f9750fea96fea5ab7aa3473340607cd7ed2c626f5382491c26d5d5bea61401dee7319c94d418f297e61ceac8f258ee8c23831bda081591f5a918e96855774ddedffc51e5b180f1971806d42fc333020b734aeb45adb0bc47325d0cea5f6713a786558022afc39d573892aa3635efbfd8bcb11c57f306c72146afe8b45388125cb7bf9ecf965a7ba4f768c77be366470dcdcf214b7f6a5a9460ed4fe44ae559d85e2fdc2094de83fff12ea8804db1215c4ca865871bdd7f8ef32ab799bf923ffb02c1ded7d129beadad46c5eda31ab1a6f43da05ea08bff7ffa88d8966353d01830558c39b930b01d175e437124d8edd0d2698fd8932f2b2c9b14746e52879c57a395538150f390264f00e60d470711202f4194499ff79037ca9885dc8d695f7d917a3086ca88e8f8d0243efee09302cf39e039eb7cc8dd19d28120d5fe533b5727cd39133181c729ca6f90a015ed30be7668d5cb5ecc33a53ee69bf7d1a5ecbdb153803743c6adaaabd36bf84e5be38d3f04a5d5dbfd67bdcd3b176e65bd1391ade775cc32ce43a847fb6c672a3fe97a5d4081c4986959ec5fb898f42a9397ba2b3ec2c1018f8d76d057f2366bd0e4465514ad6560c599664fb85621fe771e00f43d39b591b2a6a321100f4d1ef23a376d5ae3eeedbfe23da73dff0ee4d16b34ebddd8f5f053db9824105fc7300dbee7ea6af56b112319e3e215a0fc79ae946f6b5227453ec7fcaf17cf7651f71499a50d81221404d5f129ac50ea7528ff0e0069ec4ab8acb7919d81749ab37a870c5ef2cc5a15cf96709d3c65b4addc77e7416847160bcabb94ea36377e0ef71be80b5cc53effd5444888044a353574c72c924bba2a8b4e8354188ebfedc852f59073f4347a8c8a28c99e21df
 MAC = f6eaae369c3cb5c05748e8d919178e00
+
+# Regression test for https://rt.openssl.org/Ticket/Display.html?id=4439
+Key = 2d773be37adb1e4d683bf0075e79c4ee037918535a7f99ccb7040fb5f5f43aea
+Input = 89dab80b7717c1db5db437860a3f70218e93e1b8f461fb677f16f35f6f87e2a91c99bc3a47ace47640cc95c345be5ecca5a3523c35cc01893af0b64a620334270372ec12482d1b1e363561698a578b359803495bb4e2ef1930b17a5190b580f141300df30adbeca28f6427a8bc1a999fd51c554a017d095d8c3e3127daf9f595
+MAC = c85d15ed44c378d6b00e23064c7bcd51