In view of the recent BN_FLG_CONSTTIME vulnerabilities in OpenSSL,

carefully document constant time vs. non-constant time operation
of BN_div(3), BN_mod_exp(3), and BN_mod_inverse(3).

Until the work that is required on the ill-designed BN_exp(3) and
BN_gcd(3) interfaces can be undertaken, also document the imperfections
in their behaviour, for now.  Finally, mention BN_mod_exp(3) behaviour
for even moduli.

Delete the vague statement about some functions automatically
setting BN_FLG_CONSTTIME.  It created a false sense of security.
Do not rely on it: not all relevant functions do that.

Topic brought up by beck@, significant feedback and OK jsing@.

4 files changed, 104 insertions, 28 deletions

diff --git a/lib/libcrypto/man/BN_add.3 b/lib/libcrypto/man/BN_add.3
index 6001a9a4bdb..8a11d7c0804 100644
--- a/lib/libcrypto/man/BN_add.3
+++ b/lib/libcrypto/man/BN_add.3
@@ -1,4 +1,4 @@
-.\"	$OpenBSD: BN_add.3,v 1.12 2018/03/27 17:35:50 schwarze Exp $
+.\"	$OpenBSD: BN_add.3,v 1.13 2018/04/29 15:58:21 schwarze Exp $
 .\"	OpenSSL b97fdb57 Nov 11 09:33:09 2016 +0100
 .\"
 .\" This file was written by Ulf Moeller <ulf@openssl.org>
@@ -49,7 +49,7 @@
 .\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
 .\" OF THE POSSIBILITY OF SUCH DAMAGE.
 .\"
-.Dd $Mdocdate: March 27 2018 $
+.Dd $Mdocdate: April 29 2018 $
 .Dt BN_ADD 3
 .Os
 .Sh NAME
@@ -66,6 +66,13 @@
 .Nm BN_mod_sqr ,
 .Nm BN_exp ,
 .Nm BN_mod_exp ,
+.\" The following are public, but intentionally undocumented for now:
+.\" .Nm BN_mod_exp_mont_consttime ,
+.\" .Nm BN_mod_exp_mont ,
+.\" .Nm BN_mod_exp_mont_word ,
+.\" .Nm BN_mod_exp_recp ,
+.\" .Nm BN_mod_exp_simple ,
+.\" Maybe they should be deleted from <openssl/bn.h>.
 .Nm BN_gcd
 .Nd arithmetic operations on BIGNUMs
 .Sh SYNOPSIS
@@ -245,6 +252,13 @@ and places the result in
 and the remainder in
 .Fa rem
 .Pq Li dv=a/d , rem=a%d .
+If the flag
+.Dv BN_FLG_CONSTTIME
+is set on
+.Fa a
+or
+.Fa d ,
+it operates in constant time.
 Either of
 .Fa dv
 and
@@ -343,6 +357,11 @@ to the
 power modulo
 .Fa m
 .Pq Li r=(a^p)%m .
+If the flag
+.Dv BN_FLG_CONSTTIME
+is set on
+.Fa p ,
+it operates in constant time.
 This function uses less time and space than
 .Fn BN_exp .
 .Pp
@@ -417,3 +436,31 @@ and
 .Fn BN_mod_sqr
 first appeared in OpenSSL 0.9.7 and have been available since
 .Ox 3.2 .
+.Sh BUGS
+Even if the
+.Dv BN_FLG_CONSTTIME
+flag is set on
+.Fa a
+or
+.Fa b ,
+.Fn BN_gcd
+neither fails nor operates in constant time, potentially allowing
+timing side-channel attacks.
+.Pp
+Even if the
+.Dv BN_FLG_CONSTTIME
+flag is set on
+.Fa p ,
+if the modulus
+.Fa m
+is even,
+.Fn BN_mod_exp
+does not operate in constant time, potentially allowing
+timing side-channel attacks.
+.Pp
+If
+.Dv BN_FLG_CONSTTIME
+is set on
+.Fa p ,
+.Fn BN_exp
+fails instead of operating in constant time.
diff --git a/lib/libcrypto/man/BN_mod_inverse.3 b/lib/libcrypto/man/BN_mod_inverse.3
index ed6b6def4ef..aa509b1ab60 100644
--- a/lib/libcrypto/man/BN_mod_inverse.3
+++ b/lib/libcrypto/man/BN_mod_inverse.3
@@ -1,4 +1,4 @@
-.\"	$OpenBSD: BN_mod_inverse.3,v 1.9 2018/03/27 17:35:50 schwarze Exp $
+.\"	$OpenBSD: BN_mod_inverse.3,v 1.10 2018/04/29 15:58:21 schwarze Exp $
 .\"	OpenSSL b97fdb57 Nov 11 09:33:09 2016 +0100
 .\"
 .\" This file was written by Ulf Moeller <ulf@openssl.org>.
@@ -48,7 +48,7 @@
 .\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
 .\" OF THE POSSIBILITY OF SUCH DAMAGE.
 .\"
-.Dd $Mdocdate: March 27 2018 $
+.Dd $Mdocdate: April 29 2018 $
 .Dt BN_MOD_INVERSE 3
 .Os
 .Sh NAME
@@ -80,6 +80,14 @@ a new
 .Vt BIGNUM
 is created.
 .Pp
+If the flag
+.Dv BN_FLG_CONSTTIME
+is set on
+.Fa a
+or
+.Fa n ,
+it operates in constant time.
+.Pp
 .Fa ctx
 is a previously allocated
 .Vt BN_CTX
diff --git a/lib/libcrypto/man/BN_new.3 b/lib/libcrypto/man/BN_new.3
index e27a83e0424..ed2910e645f 100644
--- a/lib/libcrypto/man/BN_new.3
+++ b/lib/libcrypto/man/BN_new.3
@@ -1,4 +1,4 @@
-.\" $OpenBSD: BN_new.3,v 1.13 2018/03/27 17:35:50 schwarze Exp $
+.\" $OpenBSD: BN_new.3,v 1.14 2018/04/29 15:58:21 schwarze Exp $
 .\" full merge up to: OpenSSL man3/BN_new 2457c19d Mar 6 08:43:36 2004 +0000
 .\" selective merge up to: man3/BN_new 681acb31 Sep 29 13:10:34 2017 +0200
 .\" full merge up to: OpenSSL man7/bn 05ea606a May 20 20:52:46 2016 -0400
@@ -50,7 +50,7 @@
 .\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
 .\" OF THE POSSIBILITY OF SUCH DAMAGE.
 .\"
-.Dd $Mdocdate: March 27 2018 $
+.Dd $Mdocdate: April 29 2018 $
 .Dt BN_NEW 3
 .Os
 .Sh NAME
@@ -102,7 +102,11 @@ or accessed directly.
 .Fn BN_new
 allocates and initializes a
 .Vt BIGNUM
-structure, in particular setting the value to zero.
+structure, in particular setting the value to zero and the flags to
+.Dv BN_FLG_MALLOCED .
+The security-relevant flag
+.Dv BN_FLG_CONSTTIME
+is not set by default.
 .Pp
 .Fn BN_init
 initializes an existing uninitialized
diff --git a/lib/libcrypto/man/BN_set_flags.3 b/lib/libcrypto/man/BN_set_flags.3
index a9980375348..9b1647cd312 100644
--- a/lib/libcrypto/man/BN_set_flags.3
+++ b/lib/libcrypto/man/BN_set_flags.3
@@ -1,4 +1,4 @@
-.\"	$OpenBSD: BN_set_flags.3,v 1.2 2018/03/21 09:03:49 schwarze Exp $
+.\"	$OpenBSD: BN_set_flags.3,v 1.3 2018/04/29 15:58:21 schwarze Exp $
 .\"
 .\" Copyright (c) 2017 Ingo Schwarze <schwarze@openbsd.org>
 .\"
@@ -14,7 +14,7 @@
 .\" ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 .\" OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 .\"
-.Dd $Mdocdate: March 21 2018 $
+.Dd $Mdocdate: April 29 2018 $
 .Dt BN_SET_FLAGS 3
 .Os
 .Sh NAME
@@ -47,6 +47,8 @@ together:
 .It Dv BN_FLG_CONSTTIME
 If this flag is set on the divident
 .Fa a
+or the divisor
+.Fa d
 in
 .Xr BN_div 3 ,
 on the exponent
@@ -59,27 +61,14 @@ or the modulus
 .Fa n
 in
 .Xr BN_mod_inverse 3 ,
-these functions prefer algorithms with an execution time independent
+these functions select algorithms with an execution time independent
 of the respective numbers, to avoid exposing sensitive information
-to timing attacks.
+to timing side-channel attacks.
 .Pp
-If this flag is set on the exponent
-.Fa p
-in
-.Xr BN_exp 3
-or if the modulus
-.Fa m
-is even for
-.Xr BN_mod_exp 3 ,
-an error occurs.
-.Pp
-Various functions automatically set this flag on sensitive data.
-For example, the default implementations of
-.Xr DH_generate_key 3 ,
-.Xr DSA_generate_key 3 ,
-and
-.Xr RSA_generate_key_ex 3
-set it on the generated private key.
+This flag is off by default for
+.Vt BIGNUM
+objects created with
+.Xr BN_new 3 .
 .It Dv BN_FLG_MALLOCED
 If this flag is set,
 .Xr BN_free 3
@@ -148,3 +137,31 @@ first appeared in SSLeay 0.9.1 and have been available since
 No public interface exists to clear a flag once it is set.
 So think twice before using
 .Fn BN_set_flags .
+.Sh BUGS
+Even if the
+.Dv BN_FLG_CONSTTIME
+flag is set on
+.Fa a
+or
+.Fa b ,
+.Fn BN_gcd
+neither fails nor operates in constant time, potentially allowing
+timing side-channel attacks.
+.Pp
+Even if the
+.Dv BN_FLG_CONSTTIME
+flag is set on
+.Fa p ,
+if the modulus
+.Fa m
+is even,
+.Xr BN_mod_exp 3
+does not operate in constant time, potentially allowing
+timing side-channel attacks.
+.Pp
+If
+.Dv BN_FLG_CONSTTIME
+is set on
+.Fa p ,
+.Fn BN_exp
+fails instead of operating in constant time.