The branch OpenSSL_1_1_1-stable has been updated via 580b8db8b4f1290ec879bfd0bb772012695ac370 (commit) via 08fb832377cd90c08a2d233b3230b95a9b9f6e24 (commit) via 46ac489a1369f6d938adda356accab83acf2987a (commit) via 419102400a2811582a7a3d4a4e317d72e5ce0a8f (commit) from 7a4d39f0d176f0d17f2de15672e1869b22f3e1d8 (commit)
- Log ----------------------------------------------------------------- commit 580b8db8b4f1290ec879bfd0bb772012695ac370 Author: Bernd Edlinger <bernd.edlin...@hotmail.de> Date: Thu Dec 5 01:20:14 2019 +0100 Add a CHANGES entry for CVE-2019-1551 Reviewed-by: Paul Dale <paul.d...@oracle.com> (Merged from https://github.com/openssl/openssl/pull/10575) commit 08fb832377cd90c08a2d233b3230b95a9b9f6e24 Author: Bernd Edlinger <bernd.edlin...@hotmail.de> Date: Wed Dec 4 22:38:19 2019 +0100 Add a test case for rsaz_512_sqr overflow handling [extended tests] Reviewed-by: Paul Dale <paul.d...@oracle.com> (Merged from https://github.com/openssl/openssl/pull/10575) commit 46ac489a1369f6d938adda356accab83acf2987a Author: Bernd Edlinger <bernd.edlin...@hotmail.de> Date: Wed Dec 4 12:57:41 2019 +0100 Improve the overflow handling in rsaz_512_sqr We have always a carry in %rcx or %rbx in range 0..2 from the previous stage, that is added to the result of the 64-bit square, but the low nibble of any square can only be 0, 1, 4, 9. Therefore one "adcq $0, %rdx" can be removed. Likewise in the ADX code we can remove one "adcx %rbp, $out" since %rbp is always 0, and carry is also zero, therefore that is a no-op. Reviewed-by: Paul Dale <paul.d...@oracle.com> (Merged from https://github.com/openssl/openssl/pull/10575) commit 419102400a2811582a7a3d4a4e317d72e5ce0a8f Author: Andy Polyakov <ap...@openssl.org> Date: Wed Dec 4 12:48:21 2019 +0100 Fix an overflow bug in rsaz_512_sqr There is an overflow bug in the x64_64 Montgomery squaring procedure used in exponentiation with 512-bit moduli. No EC algorithms are affected. Analysis suggests that attacks against 2-prime RSA1024, 3-prime RSA1536, and DSA1024 as a result of this defect would be very difficult to perform and are not believed likely. Attacks against DH512 are considered just feasible. However, for an attack the target would have to re-use the DH512 private key, which is not recommended anyway. Also applications directly using the low level API BN_mod_exp may be affected if they use BN_FLG_CONSTTIME. CVE-2019-1551 Reviewed-by: Paul Dale <paul.d...@oracle.com> Reviewed-by: Bernd Edlinger <bernd.edlin...@hotmail.de> (Merged from https://github.com/openssl/openssl/pull/10575) ----------------------------------------------------------------------- Summary of changes: CHANGES | 12 ++ crypto/bn/asm/rsaz-x86_64.pl | 383 ++++++++++++++++++++++--------------------- test/bntest.c | 284 ++++++++++++++++++++++++++++++++ 3 files changed, 494 insertions(+), 185 deletions(-) diff --git a/CHANGES b/CHANGES index 58e98dd391..42382fd031 100644 --- a/CHANGES +++ b/CHANGES @@ -9,6 +9,18 @@ Changes between 1.1.1d and 1.1.1e [xx XXX xxxx] + *) Fixed an an overflow bug in the x64_64 Montgomery squaring procedure + used in exponentiation with 512-bit moduli. No EC algorithms are + affected. Analysis suggests that attacks against 2-prime RSA1024, + 3-prime RSA1536, and DSA1024 as a result of this defect would be very + difficult to perform and are not believed likely. Attacks against DH512 + are considered just feasible. However, for an attack the target would + have to re-use the DH512 private key, which is not recommended anyway. + Also applications directly using the low level API BN_mod_exp may be + affected if they use BN_FLG_CONSTTIME. + (CVE-2019-1551) + [Andy Polyakov] + *) Added a new method to gather entropy on VMS, based on SYS$GET_ENTROPY. The presence of this system service is determined at run-time. [Richard Levitte] diff --git a/crypto/bn/asm/rsaz-x86_64.pl b/crypto/bn/asm/rsaz-x86_64.pl index b1797b649f..f4d9c9b129 100755 --- a/crypto/bn/asm/rsaz-x86_64.pl +++ b/crypto/bn/asm/rsaz-x86_64.pl @@ -116,7 +116,7 @@ rsaz_512_sqr: # 25-29% faster than rsaz_512_mul subq \$128+24, %rsp .cfi_adjust_cfa_offset 128+24 .Lsqr_body: - movq $mod, %rbp # common argument + movq $mod, %xmm1 # common off-load movq ($inp), %rdx movq 8($inp), %rax movq $n0, 128(%rsp) @@ -134,7 +134,8 @@ $code.=<<___; .Loop_sqr: movl $times,128+8(%rsp) #first iteration - movq %rdx, %rbx + movq %rdx, %rbx # 0($inp) + mov %rax, %rbp # 8($inp) mulq %rdx movq %rax, %r8 movq 16($inp), %rax @@ -173,31 +174,29 @@ $code.=<<___; mulq %rbx addq %rax, %r14 movq %rbx, %rax - movq %rdx, %r15 - adcq \$0, %r15 + adcq \$0, %rdx - addq %r8, %r8 #shlq \$1, %r8 - movq %r9, %rcx - adcq %r9, %r9 #shld \$1, %r8, %r9 + xorq %rcx,%rcx # rcx:r8 = r8 << 1 + addq %r8, %r8 + movq %rdx, %r15 + adcq \$0, %rcx mulq %rax - movq %rax, (%rsp) - addq %rdx, %r8 - adcq \$0, %r9 + addq %r8, %rdx + adcq \$0, %rcx - movq %r8, 8(%rsp) - shrq \$63, %rcx + movq %rax, (%rsp) + movq %rdx, 8(%rsp) #second iteration - movq 8($inp), %r8 movq 16($inp), %rax - mulq %r8 + mulq %rbp addq %rax, %r10 movq 24($inp), %rax movq %rdx, %rbx adcq \$0, %rbx - mulq %r8 + mulq %rbp addq %rax, %r11 movq 32($inp), %rax adcq \$0, %rdx @@ -205,7 +204,7 @@ $code.=<<___; movq %rdx, %rbx adcq \$0, %rbx - mulq %r8 + mulq %rbp addq %rax, %r12 movq 40($inp), %rax adcq \$0, %rdx @@ -213,7 +212,7 @@ $code.=<<___; movq %rdx, %rbx adcq \$0, %rbx - mulq %r8 + mulq %rbp addq %rax, %r13 movq 48($inp), %rax adcq \$0, %rdx @@ -221,7 +220,7 @@ $code.=<<___; movq %rdx, %rbx adcq \$0, %rbx - mulq %r8 + mulq %rbp addq %rax, %r14 movq 56($inp), %rax adcq \$0, %rdx @@ -229,39 +228,39 @@ $code.=<<___; movq %rdx, %rbx adcq \$0, %rbx - mulq %r8 + mulq %rbp addq %rax, %r15 - movq %r8, %rax + movq %rbp, %rax adcq \$0, %rdx addq %rbx, %r15 - movq %rdx, %r8 - movq %r10, %rdx - adcq \$0, %r8 + adcq \$0, %rdx - add %rdx, %rdx - lea (%rcx,%r10,2), %r10 #shld \$1, %rcx, %r10 - movq %r11, %rbx - adcq %r11, %r11 #shld \$1, %r10, %r11 + xorq %rbx, %rbx # rbx:r10:r9 = r10:r9 << 1 + addq %r9, %r9 + movq %rdx, %r8 + adcq %r10, %r10 + adcq \$0, %rbx mulq %rax + # rcx <= 2 and rax <= 0xFFFF..F9, so carry must be zero here + addq %rcx, %rax + movq 16($inp), %rbp addq %rax, %r9 + movq 24($inp), %rax adcq %rdx, %r10 - adcq \$0, %r11 + adcq \$0, %rbx movq %r9, 16(%rsp) movq %r10, 24(%rsp) - shrq \$63, %rbx #third iteration - movq 16($inp), %r9 - movq 24($inp), %rax - mulq %r9 + mulq %rbp addq %rax, %r12 movq 32($inp), %rax movq %rdx, %rcx adcq \$0, %rcx - mulq %r9 + mulq %rbp addq %rax, %r13 movq 40($inp), %rax adcq \$0, %rdx @@ -269,7 +268,7 @@ $code.=<<___; movq %rdx, %rcx adcq \$0, %rcx - mulq %r9 + mulq %rbp addq %rax, %r14 movq 48($inp), %rax adcq \$0, %rdx @@ -277,9 +276,7 @@ $code.=<<___; movq %rdx, %rcx adcq \$0, %rcx - mulq %r9 - movq %r12, %r10 - lea (%rbx,%r12,2), %r12 #shld \$1, %rbx, %r12 + mulq %rbp addq %rax, %r15 movq 56($inp), %rax adcq \$0, %rdx @@ -287,36 +284,40 @@ $code.=<<___; movq %rdx, %rcx adcq \$0, %rcx - mulq %r9 - shrq \$63, %r10 + mulq %rbp addq %rax, %r8 - movq %r9, %rax + movq %rbp, %rax adcq \$0, %rdx addq %rcx, %r8 - movq %rdx, %r9 - adcq \$0, %r9 + adcq \$0, %rdx - movq %r13, %rcx - leaq (%r10,%r13,2), %r13 #shld \$1, %r12, %r13 + xorq %rcx, %rcx # rcx:r12:r11 = r12:r11 << 1 + addq %r11, %r11 + movq %rdx, %r9 + adcq %r12, %r12 + adcq \$0, %rcx mulq %rax + # rbx <= 2 and rax <= 0xFFFF..F9, so carry must be zero here + addq %rbx, %rax + movq 24($inp), %r10 addq %rax, %r11 + movq 32($inp), %rax adcq %rdx, %r12 - adcq \$0, %r13 + adcq \$0, %rcx movq %r11, 32(%rsp) movq %r12, 40(%rsp) - shrq \$63, %rcx #fourth iteration - movq 24($inp), %r10 - movq 32($inp), %rax + mov %rax, %r11 # 32($inp) mulq %r10 addq %rax, %r14 movq 40($inp), %rax movq %rdx, %rbx adcq \$0, %rbx + mov %rax, %r12 # 40($inp) mulq %r10 addq %rax, %r15 movq 48($inp), %rax @@ -325,9 +326,8 @@ $code.=<<___; movq %rdx, %rbx adcq \$0, %rbx + mov %rax, %rbp # 48($inp) mulq %r10 - movq %r14, %r12 - leaq (%rcx,%r14,2), %r14 #shld \$1, %rcx, %r14 addq %rax, %r8 movq 56($inp), %rax adcq \$0, %rdx @@ -336,32 +336,33 @@ $code.=<<___; adcq \$0, %rbx mulq %r10 - shrq \$63, %r12 addq %rax, %r9 movq %r10, %rax adcq \$0, %rdx addq %rbx, %r9 - movq %rdx, %r10 - adcq \$0, %r10 + adcq \$0, %rdx - movq %r15, %rbx - leaq (%r12,%r15,2),%r15 #shld \$1, %r14, %r15 + xorq %rbx, %rbx # rbx:r13:r14 = r13:r14 << 1 + addq %r13, %r13 + movq %rdx, %r10 + adcq %r14, %r14 + adcq \$0, %rbx mulq %rax + # rcx <= 2 and rax <= 0xFFFF..F9, so carry must be zero here + addq %rcx, %rax addq %rax, %r13 + movq %r12, %rax # 40($inp) adcq %rdx, %r14 - adcq \$0, %r15 + adcq \$0, %rbx movq %r13, 48(%rsp) movq %r14, 56(%rsp) - shrq \$63, %rbx #fifth iteration - movq 32($inp), %r11 - movq 40($inp), %rax mulq %r11 addq %rax, %r8 - movq 48($inp), %rax + movq %rbp, %rax # 48($inp) movq %rdx, %rcx adcq \$0, %rcx @@ -369,97 +370,99 @@ $code.=<<___; addq %rax, %r9 movq 56($inp), %rax adcq \$0, %rdx - movq %r8, %r12 - leaq (%rbx,%r8,2), %r8 #shld \$1, %rbx, %r8 addq %rcx, %r9 movq %rdx, %rcx adcq \$0, %rcx + mov %rax, %r14 # 56($inp) mulq %r11 - shrq \$63, %r12 addq %rax, %r10 movq %r11, %rax adcq \$0, %rdx addq %rcx, %r10 - movq %rdx, %r11 - adcq \$0, %r11 + adcq \$0, %rdx - movq %r9, %rcx - leaq (%r12,%r9,2), %r9 #shld \$1, %r8, %r9 + xorq %rcx, %rcx # rcx:r8:r15 = r8:r15 << 1 + addq %r15, %r15 + movq %rdx, %r11 + adcq %r8, %r8 + adcq \$0, %rcx mulq %rax + # rbx <= 2 and rax <= 0xFFFF..F9, so carry must be zero here + addq %rbx, %rax addq %rax, %r15 + movq %rbp, %rax # 48($inp) adcq %rdx, %r8 - adcq \$0, %r9 + adcq \$0, %rcx movq %r15, 64(%rsp) movq %r8, 72(%rsp) - shrq \$63, %rcx #sixth iteration - movq 40($inp), %r12 - movq 48($inp), %rax mulq %r12 addq %rax, %r10 - movq 56($inp), %rax + movq %r14, %rax # 56($inp) movq %rdx, %rbx adcq \$0, %rbx mulq %r12 addq %rax, %r11 movq %r12, %rax - movq %r10, %r15 - leaq (%rcx,%r10,2), %r10 #shld \$1, %rcx, %r10 adcq \$0, %rdx - shrq \$63, %r15 addq %rbx, %r11 - movq %rdx, %r12 - adcq \$0, %r12 + adcq \$0, %rdx - movq %r11, %rbx - leaq (%r15,%r11,2), %r11 #shld \$1, %r10, %r11 + xorq %rbx, %rbx # rbx:r10:r9 = r10:r9 << 1 + addq %r9, %r9 + movq %rdx, %r12 + adcq %r10, %r10 + adcq \$0, %rbx mulq %rax + # rcx <= 2 and rax <= 0xFFFF..F9, so carry must be zero here + addq %rcx, %rax addq %rax, %r9 + movq %r14, %rax # 56($inp) adcq %rdx, %r10 - adcq \$0, %r11 + adcq \$0, %rbx movq %r9, 80(%rsp) movq %r10, 88(%rsp) #seventh iteration - movq 48($inp), %r13 - movq 56($inp), %rax - mulq %r13 + mulq %rbp addq %rax, %r12 - movq %r13, %rax - movq %rdx, %r13 - adcq \$0, %r13 + movq %rbp, %rax + adcq \$0, %rdx - xorq %r14, %r14 - shlq \$1, %rbx - adcq %r12, %r12 #shld \$1, %rbx, %r12 - adcq %r13, %r13 #shld \$1, %r12, %r13 - adcq %r14, %r14 #shld \$1, %r13, %r14 + xorq %rcx, %rcx # rcx:r12:r11 = r12:r11 << 1 + addq %r11, %r11 + movq %rdx, %r13 + adcq %r12, %r12 + adcq \$0, %rcx mulq %rax + # rbx <= 2 and rax <= 0xFFFF..F9, so carry must be zero here + addq %rbx, %rax addq %rax, %r11 + movq %r14, %rax # 56($inp) adcq %rdx, %r12 - adcq \$0, %r13 + adcq \$0, %rcx movq %r11, 96(%rsp) movq %r12, 104(%rsp) #eighth iteration - movq 56($inp), %rax - mulq %rax - addq %rax, %r13 - adcq \$0, %rdx - - addq %rdx, %r14 + xorq %rbx, %rbx # rbx:r13 = r13 << 1 + addq %r13, %r13 + adcq \$0, %rbx - movq %r13, 112(%rsp) - movq %r14, 120(%rsp) + mulq %rax + # rcx <= 2 and rax <= 0xFFFF..F9, so carry must be zero here + addq %rcx, %rax + addq %r13, %rax + adcq %rbx, %rdx movq (%rsp), %r8 movq 8(%rsp), %r9 @@ -469,6 +472,10 @@ $code.=<<___; movq 40(%rsp), %r13 movq 48(%rsp), %r14 movq 56(%rsp), %r15 + movq %xmm1, %rbp + + movq %rax, 112(%rsp) + movq %rdx, 120(%rsp) call __rsaz_512_reduce @@ -500,9 +507,9 @@ $code.=<<___; .Loop_sqrx: movl $times,128+8(%rsp) movq $out, %xmm0 # off-load - movq %rbp, %xmm1 # off-load #first iteration mulx %rax, %r8, %r9 + mov %rax, %rbx mulx 16($inp), %rcx, %r10 xor %rbp, %rbp # cf=0, of=0 @@ -510,40 +517,39 @@ $code.=<<___; mulx 24($inp), %rax, %r11 adcx %rcx, %r9 - mulx 32($inp), %rcx, %r12 + .byte 0xc4,0x62,0xf3,0xf6,0xa6,0x20,0x00,0x00,0x00 # mulx 32($inp), %rcx, %r12 adcx %rax, %r10 - mulx 40($inp), %rax, %r13 + .byte 0xc4,0x62,0xfb,0xf6,0xae,0x28,0x00,0x00,0x00 # mulx 40($inp), %rax, %r13 adcx %rcx, %r11 - .byte 0xc4,0x62,0xf3,0xf6,0xb6,0x30,0x00,0x00,0x00 # mulx 48($inp), %rcx, %r14 + mulx 48($inp), %rcx, %r14 adcx %rax, %r12 adcx %rcx, %r13 - .byte 0xc4,0x62,0xfb,0xf6,0xbe,0x38,0x00,0x00,0x00 # mulx 56($inp), %rax, %r15 + mulx 56($inp), %rax, %r15 adcx %rax, %r14 adcx %rbp, %r15 # %rbp is 0 - mov %r9, %rcx - shld \$1, %r8, %r9 - shl \$1, %r8 - - xor %ebp, %ebp - mulx %rdx, %rax, %rdx - adcx %rdx, %r8 - mov 8($inp), %rdx - adcx %rbp, %r9 + mulx %rdx, %rax, $out + mov %rbx, %rdx # 8($inp) + xor %rcx, %rcx + adox %r8, %r8 + adcx $out, %r8 + adox %rbp, %rcx + adcx %rbp, %rcx mov %rax, (%rsp) mov %r8, 8(%rsp) #second iteration - mulx 16($inp), %rax, %rbx + .byte 0xc4,0xe2,0xfb,0xf6,0x9e,0x10,0x00,0x00,0x00 # mulx 16($inp), %rax, %rbx adox %rax, %r10 adcx %rbx, %r11 - .byte 0xc4,0x62,0xc3,0xf6,0x86,0x18,0x00,0x00,0x00 # mulx 24($inp), $out, %r8 + mulx 24($inp), $out, %r8 adox $out, %r11 + .byte 0x66 adcx %r8, %r12 mulx 32($inp), %rax, %rbx @@ -561,24 +567,25 @@ $code.=<<___; .byte 0xc4,0x62,0xc3,0xf6,0x86,0x38,0x00,0x00,0x00 # mulx 56($inp), $out, %r8 adox $out, %r15 adcx %rbp, %r8 + mulx %rdx, %rax, $out adox %rbp, %r8 + .byte 0x48,0x8b,0x96,0x10,0x00,0x00,0x00 # mov 16($inp), %rdx - mov %r11, %rbx - shld \$1, %r10, %r11 - shld \$1, %rcx, %r10 - - xor %ebp,%ebp - mulx %rdx, %rax, %rcx - mov 16($inp), %rdx + xor %rbx, %rbx + adox %r9, %r9 + # rcx <= 2 and rax <= 0xFFFF..F9, so carry must be zero here + adcx %rcx, %rax + adox %r10, %r10 adcx %rax, %r9 - adcx %rcx, %r10 - adcx %rbp, %r11 + adox %rbp, %rbx + adcx $out, %r10 + adcx %rbp, %rbx mov %r9, 16(%rsp) .byte 0x4c,0x89,0x94,0x24,0x18,0x00,0x00,0x00 # mov %r10, 24(%rsp) #third iteration - .byte 0xc4,0x62,0xc3,0xf6,0x8e,0x18,0x00,0x00,0x00 # mulx 24($inp), $out, %r9 + mulx 24($inp), $out, %r9 adox $out, %r12 adcx %r9, %r13 @@ -586,7 +593,7 @@ $code.=<<___; adox %rax, %r13 adcx %rcx, %r14 - mulx 40($inp), $out, %r9 + .byte 0xc4,0x62,0xc3,0xf6,0x8e,0x28,0x00,0x00,0x00 # mulx 40($inp), $out, %r9 adox $out, %r14 adcx %r9, %r15 @@ -594,27 +601,28 @@ $code.=<<___; adox %rax, %r15 adcx %rcx, %r8 - .byte 0xc4,0x62,0xc3,0xf6,0x8e,0x38,0x00,0x00,0x00 # mulx 56($inp), $out, %r9 + mulx 56($inp), $out, %r9 adox $out, %r8 adcx %rbp, %r9 + mulx %rdx, %rax, $out adox %rbp, %r9 + mov 24($inp), %rdx - mov %r13, %rcx - shld \$1, %r12, %r13 - shld \$1, %rbx, %r12 - - xor %ebp, %ebp - mulx %rdx, %rax, %rdx + xor %rcx, %rcx + adox %r11, %r11 + # rbx <= 2 and rax <= 0xFFFF..F9, so carry must be zero here + adcx %rbx, %rax + adox %r12, %r12 adcx %rax, %r11 - adcx %rdx, %r12 - mov 24($inp), %rdx - adcx %rbp, %r13 + adox %rbp, %rcx + adcx $out, %r12 + adcx %rbp, %rcx mov %r11, 32(%rsp) - .byte 0x4c,0x89,0xa4,0x24,0x28,0x00,0x00,0x00 # mov %r12, 40(%rsp) + mov %r12, 40(%rsp) #fourth iteration - .byte 0xc4,0xe2,0xfb,0xf6,0x9e,0x20,0x00,0x00,0x00 # mulx 32($inp), %rax, %rbx + mulx 32($inp), %rax, %rbx adox %rax, %r14 adcx %rbx, %r15 @@ -629,25 +637,25 @@ $code.=<<___; mulx 56($inp), $out, %r10 adox $out, %r9 adcx %rbp, %r10 + mulx %rdx, %rax, $out adox %rbp, %r10 + mov 32($inp), %rdx - .byte 0x66 - mov %r15, %rbx - shld \$1, %r14, %r15 - shld \$1, %rcx, %r14 - - xor %ebp, %ebp - mulx %rdx, %rax, %rdx + xor %rbx, %rbx + adox %r13, %r13 + # rcx <= 2 and rax <= 0xFFFF..F9, so carry must be zero here + adcx %rcx, %rax + adox %r14, %r14 adcx %rax, %r13 - adcx %rdx, %r14 - mov 32($inp), %rdx - adcx %rbp, %r15 + adox %rbp, %rbx + adcx $out, %r14 + adcx %rbp, %rbx mov %r13, 48(%rsp) mov %r14, 56(%rsp) #fifth iteration - .byte 0xc4,0x62,0xc3,0xf6,0x9e,0x28,0x00,0x00,0x00 # mulx 40($inp), $out, %r11 + mulx 40($inp), $out, %r11 adox $out, %r8 adcx %r11, %r9 @@ -658,18 +666,19 @@ $code.=<<___; mulx 56($inp), $out, %r11 adox $out, %r10 adcx %rbp, %r11 + mulx %rdx, %rax, $out + mov 40($inp), %rdx adox %rbp, %r11 - mov %r9, %rcx - shld \$1, %r8, %r9 - shld \$1, %rbx, %r8 - - xor %ebp, %ebp - mulx %rdx, %rax, %rdx + xor %rcx, %rcx + adox %r15, %r15 + # rbx <= 2 and rax <= 0xFFFF..F9, so carry must be zero here + adcx %rbx, %rax + adox %r8, %r8 adcx %rax, %r15 - adcx %rdx, %r8 - mov 40($inp), %rdx - adcx %rbp, %r9 + adox %rbp, %rcx + adcx $out, %r8 + adcx %rbp, %rcx mov %r15, 64(%rsp) mov %r8, 72(%rsp) @@ -682,18 +691,19 @@ $code.=<<___; .byte 0xc4,0x62,0xc3,0xf6,0xa6,0x38,0x00,0x00,0x00 # mulx 56($inp), $out, %r12 adox $out, %r11 adcx %rbp, %r12 + mulx %rdx, %rax, $out adox %rbp, %r12 + mov 48($inp), %rdx - mov %r11, %rbx - shld \$1, %r10, %r11 - shld \$1, %rcx, %r10 - - xor %ebp, %ebp - mulx %rdx, %rax, %rdx + xor %rbx, %rbx + adox %r9, %r9 + # rcx <= 2 and rax <= 0xFFFF..F9, so carry must be zero here + adcx %rcx, %rax + adox %r10, %r10 adcx %rax, %r9 - adcx %rdx, %r10 - mov 48($inp), %rdx - adcx %rbp, %r11 + adcx $out, %r10 + adox %rbp, %rbx + adcx %rbp, %rbx mov %r9, 80(%rsp) mov %r10, 88(%rsp) @@ -703,31 +713,31 @@ $code.=<<___; adox %rax, %r12 adox %rbp, %r13 - xor %r14, %r14 - shld \$1, %r13, %r14 - shld \$1, %r12, %r13 - shld \$1, %rbx, %r12 - - xor %ebp, %ebp - mulx %rdx, %rax, %rdx - adcx %rax, %r11 - adcx %rdx, %r12 + mulx %rdx, %rax, $out + xor %rcx, %rcx mov 56($inp), %rdx - adcx %rbp, %r13 + adox %r11, %r11 + # rbx <= 2 and rax <= 0xFFFF..F9, so carry must be zero here + adcx %rbx, %rax + adox %r12, %r12 + adcx %rax, %r11 + adox %rbp, %rcx + adcx $out, %r12 + adcx %rbp, %rcx .byte 0x4c,0x89,0x9c,0x24,0x60,0x00,0x00,0x00 # mov %r11, 96(%rsp) .byte 0x4c,0x89,0xa4,0x24,0x68,0x00,0x00,0x00 # mov %r12, 104(%rsp) #eighth iteration mulx %rdx, %rax, %rdx - adox %rax, %r13 - adox %rbp, %rdx + xor %rbx, %rbx + adox %r13, %r13 + # rcx <= 2 and rax <= 0xFFFF..F9, so carry must be zero here + adcx %rcx, %rax + adox %rbp, %rbx + adcx %r13, %rax + adcx %rdx, %rbx - .byte 0x66 - add %rdx, %r14 - - movq %r13, 112(%rsp) - movq %r14, 120(%rsp) movq %xmm0, $out movq %xmm1, %rbp @@ -741,6 +751,9 @@ $code.=<<___; movq 48(%rsp), %r14 movq 56(%rsp), %r15 + movq %rax, 112(%rsp) + movq %rbx, 120(%rsp) + call __rsaz_512_reducex addq 64(%rsp), %r8 diff --git a/test/bntest.c b/test/bntest.c index 9f63ec121c..97d08ac0be 100644 --- a/test/bntest.c +++ b/test/bntest.c @@ -2404,6 +2404,288 @@ static int test_gcd_prime(void) return st; } +typedef struct mod_exp_test_st +{ + const char *base; + const char *exp; + const char *mod; + const char *res; +} MOD_EXP_TEST; + +static const MOD_EXP_TEST ModExpTests[] = { + /* original test vectors for rsaz_512_sqr bug, by OSS-Fuzz */ + { + "1166180238001879113042182292626169621106255558914000595999312084" + "4627946820899490684928760491249738643524880720584249698100907201" + "002086675047927600340800371", + "8000000000000000000000000000000000000000000000000000000000000000" + "0000000000000000000000000000000000000000000000000000000000000000" + "00000000", + "1340780792684523720980737645613191762604395855615117867483316354" + "3294276330515137663421134775482798690129946803802212663956180562" + "088664022929883876655300863", + "8243904058268085430037326628480645845409758077568738532059032482" + "8294114415890603594730158120426756266457928475330450251339773498" + "26758407619521544102068438" + }, + { + "4974270041410803822078866696159586946995877618987010219312844726" + "0284386121835740784990869050050504348861513337232530490826340663" + "197278031692737429054", + "4974270041410803822078866696159586946995877428188754995041148539" + "1663243362592271353668158565195557417149981094324650322556843202" + "946445882670777892608", + "1340780716511420227215592830971452482815377482627251725537099028" + "4429769497230131760206012644403029349547320953206103351725462999" + "947509743623340557059752191", + "5296244594780707015616522701706118082963369547253192207884519362" + "1767869984947542695665420219028522815539559194793619684334900442" + "49304558011362360473525933" + }, + /* test vectors for rsaz_512_srq bug, with rcx/rbx=1 */ + { /* between first and second iteration */ + "5148719036160389201525610950887605325980251964889646556085286545" + "3931548809178823413169359635978762036512397113080988070677858033" + "36463909753993540214027190", + "6703903964971298549787012499102923063739682910296196688861780721" + "8608820150367734884009371490834517138450159290932430254268769414" + "05973284973216824503042158", + "6703903964971298549787012499102923063739682910296196688861780721" + "8608820150367734884009371490834517138450159290932430254268769414" + "05973284973216824503042159", + "1" + }, + { /* between second and third iteration */ + "8908340854353752577419678771330460827942371434853054158622636544" + "8151360109722890949471912566649465436296659601091730745087014189" + "2672764191218875181826063", + "6703903964971298549787012499102923063739682910296196688861780721" + "8608820150367734884009371490834517138450159290932430254268769414" + "05973284973216824503042158", + "6703903964971298549787012499102923063739682910296196688861780721" + "8608820150367734884009371490834517138450159290932430254268769414" + "05973284973216824503042159", + "1" + }, + { /* between third and fourth iteration */ + "3427446396505596330634350984901719674479522569002785244080234738" + "4288743635435746136297299366444548736533053717416735379073185344" + "26985272974404612945608761", + "6703903964971298549787012499102923063739682910296196688861780721" + "8608820150367734884009371490834517138450159290932430254268769414" + "05973284973216824503042158", + "6703903964971298549787012499102923063739682910296196688861780721" + "8608820150367734884009371490834517138450159290932430254268769414" + "05973284973216824503042159", + "1" + }, + { /* between fourth and fifth iteration */ + "3472743044917564564078857826111874560045331237315597383869652985" + "6919870028890895988478351133601517365908445058405433832718206902" + "4088133164805266956353542", + "6703903964971298549787012499102923063739682910296196688861780721" + "8608820150367734884009371490834517138450159290932430254268769414" + "05973284973216824503042158", + "6703903964971298549787012499102923063739682910296196688861780721" + "8608820150367734884009371490834517138450159290932430254268769414" + "05973284973216824503042159", + "1" + }, + { /* between fifth and sixth iteration */ + "3608632990153469264412378349742339216742409743898601587274768025" + "0110772032985643555192767717344946174122842255204082586753499651" + "14483434992887431333675068", + "6703903964971298549787012499102923063739682910296196688861780721" + "8608820150367734884009371490834517138450159290932430254268769414" + "05973284973216824503042158", + "6703903964971298549787012499102923063739682910296196688861780721" + "8608820150367734884009371490834517138450159290932430254268769414" + "05973284973216824503042159", + "1" + }, + { /* between sixth and seventh iteration */ + "8455374370234070242910508226941981520235709767260723212165264877" + "8689064388017521524568434328264431772644802567028663962962025746" + "9283458217850119569539086", + "6703903964971298549787012499102923063739682910296196688861780721" + "8608820150367734884009371490834517138450159290932430254268769414" + "05973284973216824503042158", + "6703903964971298549787012499102923063739682910296196688861780721" + "8608820150367734884009371490834517138450159290932430254268769414" + "05973284973216824503042159", + "1" + }, + { /* between seventh and eighth iteration */ + "5155371529688532178421209781159131443543419764974688878527112131" + "7446518205609427412336183157918981038066636807317733319323257603" + "04416292040754017461076359", + "1005585594745694782468051874865438459560952436544429503329267108" + "2791323022555160232601405723625177570767523893639864538140315412" + "108959927459825236754563832", + "1005585594745694782468051874865438459560952436544429503329267108" + "2791323022555160232601405723625177570767523893639864538140315412" + "108959927459825236754563833", + "1" + }, + /* test vectors for rsaz_512_srq bug, with rcx/rbx=2 */ + { /* between first and second iteration */ + "3155666506033786929967309937640790361084670559125912405342594979" + "4345142818528956285490897841406338022378565972533508820577760065" + "58494345853302083699912572", + "6703903964971298549787012499102923063739682910296196688861780721" + "8608820150367734884009371490834517138450159290932430254268769414" + "05973284973216824503042158", + "6703903964971298549787012499102923063739682910296196688861780721" + "8608820150367734884009371490834517138450159290932430254268769414" + "05973284973216824503042159", + "1" + }, + { /* between second and third iteration */ + "3789819583801342198190405714582958759005991915505282362397087750" + "4213544724644823098843135685133927198668818185338794377239590049" + "41019388529192775771488319", + "6703903964971298549787012499102923063739682910296196688861780721" + "8608820150367734884009371490834517138450159290932430254268769414" + "05973284973216824503042158", + "6703903964971298549787012499102923063739682910296196688861780721" + "8608820150367734884009371490834517138450159290932430254268769414" + "05973284973216824503042159", + "1" + }, + { /* between third and forth iteration */ + "4695752552040706867080542538786056470322165281761525158189220280" + "4025547447667484759200742764246905647644662050122968912279199065" + "48065034299166336940507214", + "6703903964971298549787012499102923063739682910296196688861780721" + "8608820150367734884009371490834517138450159290932430254268769414" + "05973284973216824503042158", + "6703903964971298549787012499102923063739682910296196688861780721" + "8608820150367734884009371490834517138450159290932430254268769414" + "05973284973216824503042159", + "1" + }, + { /* between forth and fifth iteration */ + "2159140240970485794188159431017382878636879856244045329971239574" + "8919691133560661162828034323196457386059819832804593989740268964" + "74502911811812651475927076", + "6703903964971298549787012499102923063739682910296196688861780721" + "8608820150367734884009371490834517138450159290932430254268769414" + "05973284973216824503042158", + "6703903964971298549787012499102923063739682910296196688861780721" + "8608820150367734884009371490834517138450159290932430254268769414" + "05973284973216824503042159", + "1" + }, + { /* between fifth and sixth iteration */ + "5239312332984325668414624633307915097111691815000872662334695514" + "5436533521392362443557163429336808208137221322444780490437871903" + "99972784701334569424519255", + "6703903964971298549787012499102923063739682910296196688861780721" + "8608820150367734884009371490834517138450159290932430254268769414" + "05973284973216824503042158", + "6703903964971298549787012499102923063739682910296196688861780721" + "8608820150367734884009371490834517138450159290932430254268769414" + "05973284973216824503042159", + "1" + }, + { /* between sixth and seventh iteration */ + "1977953647322612860406858017869125467496941904523063466791308891" + "1172796739058531929470539758361774569875505293428856181093904091" + "33788264851714311303725089", + "6703903964971298549787012499102923063739682910296196688861780721" + "8608820150367734884009371490834517138450159290932430254268769414" + "05973284973216824503042158", + "6703903964971298549787012499102923063739682910296196688861780721" + "8608820150367734884009371490834517138450159290932430254268769414" + "05973284973216824503042159", + "1" + }, + { /* between seventh and eighth iteration */ + "6456987954117763835533395796948878140715006860263624787492985786" + "8514630216966738305923915688821526449499763719943997120302368211" + "04813318117996225041943964", + "1340780792994259709957402499820584612747936582059239337772356144" + "3721764030073546976801874298166903427690031858186486050853753882" + "811946551499689575296532556", + "1340780792994259709957402499820584612747936582059239337772356144" + "3721764030073546976801874298166903427690031858186486050853753882" + "811946551499689575296532557", + "1" + } +}; + +static int test_mod_exp(int i) +{ + const MOD_EXP_TEST *test = &ModExpTests[i]; + int res = 0; + BIGNUM* result = NULL; + BIGNUM *base = NULL, *exponent = NULL, *modulo = NULL; + char *s = NULL; + + if (!TEST_ptr(result = BN_new()) + || !TEST_true(BN_dec2bn(&base, test->base)) + || !TEST_true(BN_dec2bn(&exponent, test->exp)) + || !TEST_true(BN_dec2bn(&modulo, test->mod))) + goto err; + + if (!TEST_int_eq(BN_mod_exp(result, base, exponent, modulo, ctx), 1)) + goto err; + + if (!TEST_ptr(s = BN_bn2dec(result))) + goto err; + + if (!TEST_mem_eq(s, strlen(s), test->res, strlen(test->res))) + goto err; + + res = 1; + + err: + OPENSSL_free(s); + BN_free(result); + BN_free(base); + BN_free(exponent); + BN_free(modulo); + return res; +} + +static int test_mod_exp_consttime(int i) +{ + const MOD_EXP_TEST *test = &ModExpTests[i]; + int res = 0; + BIGNUM* result = NULL; + BIGNUM *base = NULL, *exponent = NULL, *modulo = NULL; + char *s = NULL; + + if (!TEST_ptr(result = BN_new()) + || !TEST_true(BN_dec2bn(&base, test->base)) + || !TEST_true(BN_dec2bn(&exponent, test->exp)) + || !TEST_true(BN_dec2bn(&modulo, test->mod))) + goto err; + + BN_set_flags(base, BN_FLG_CONSTTIME); + BN_set_flags(exponent, BN_FLG_CONSTTIME); + BN_set_flags(modulo, BN_FLG_CONSTTIME); + + if (!TEST_int_eq(BN_mod_exp(result, base, exponent, modulo, ctx), 1)) + goto err; + + if (!TEST_ptr(s = BN_bn2dec(result))) + goto err; + + if (!TEST_mem_eq(s, strlen(s), test->res, strlen(test->res))) + goto err; + + res = 1; + + err: + OPENSSL_free(s); + BN_free(result); + BN_free(base); + BN_free(exponent); + BN_free(modulo); + return res; +} + static int file_test_run(STANZA *s) { static const FILETEST filetests[] = { @@ -2508,6 +2790,8 @@ int setup_tests(void) ADD_ALL_TESTS(test_is_prime, (int)OSSL_NELEM(primes)); ADD_ALL_TESTS(test_not_prime, (int)OSSL_NELEM(not_primes)); ADD_TEST(test_gcd_prime); + ADD_ALL_TESTS(test_mod_exp, (int)OSSL_NELEM(ModExpTests)); + ADD_ALL_TESTS(test_mod_exp_consttime, (int)OSSL_NELEM(ModExpTests)); } else { ADD_ALL_TESTS(run_file_tests, n); }