[Openvpn-devel,v2,1/3] Use crypto library functions for const time memcmp when possible

Message ID 20200416113930.15192-1-arne@rfc2549.org
State Superseded
Headers show
Series
  • [Openvpn-devel,v2,1/3] Use crypto library functions for const time memcmp when possible
Related show

Commit Message

Arne Schwabe April 16, 2020, 11:39 a.m.
Signed-off-by: Arne Schwabe <arne@rfc2549.org>
---
 src/openvpn/crypto.h         | 16 +---------------
 src/openvpn/crypto_mbedtls.c | 19 +++++++++++++++++++
 src/openvpn/crypto_openssl.c |  5 +++++
 3 files changed, 25 insertions(+), 15 deletions(-)

Comments

Antonio Quartulli April 16, 2020, 2:10 p.m. | #1
Hi,

On 16/04/2020 13:39, Arne Schwabe wrote:
> Signed-off-by: Arne Schwabe <arne@rfc2549.org>
> ---
>  src/openvpn/crypto.h         | 16 +---------------
>  src/openvpn/crypto_mbedtls.c | 19 +++++++++++++++++++
>  src/openvpn/crypto_openssl.c |  5 +++++
>  3 files changed, 25 insertions(+), 15 deletions(-)
> 
> diff --git a/src/openvpn/crypto.h b/src/openvpn/crypto.h
> index 18a86ceb..dadf0a90 100644
> --- a/src/openvpn/crypto.h
> +++ b/src/openvpn/crypto.h
> @@ -528,21 +528,7 @@ void crypto_read_openvpn_key(const struct key_type *key_type,
>   * As memcmp(), but constant-time.
>   * Returns 0 when data is equal, non-zero otherwise.
>   */
> -static inline int
> -memcmp_constant_time(const void *a, const void *b, size_t size)
> -{
> -    const uint8_t *a1 = a;
> -    const uint8_t *b1 = b;
> -    int ret = 0;
> -    size_t i;
> -
> -    for (i = 0; i < size; i++)
> -    {
> -        ret |= *a1++ ^ *b1++;
> -    }
> -
> -    return ret;
> -}
> +int memcmp_constant_time(const void *a, const void *b, size_t size);
>  
>  static inline bool
>  key_ctx_bi_defined(const struct key_ctx_bi *key)
> diff --git a/src/openvpn/crypto_mbedtls.c b/src/openvpn/crypto_mbedtls.c
> index 3e77fa9e..35072b73 100644
> --- a/src/openvpn/crypto_mbedtls.c
> +++ b/src/openvpn/crypto_mbedtls.c
> @@ -972,4 +972,23 @@ hmac_ctx_final(mbedtls_md_context_t *ctx, uint8_t *dst)
>      ASSERT(0 == mbedtls_md_hmac_finish(ctx, dst));
>  }
>  
> +int
> +memcmp_constant_time(const void *a, const void *b, size_t size)
> +{
> +    /* mbed TLS has a no const time memcmp function that it exposes
> +     * via its APIs like OpenSSL does with CRYPTO_memcmp

'.' missing at the end of the sentence.
Actually, I'd just chop the last part and stop after 'memcmp'.

> +     * Adapt the function that mbedtls itself uses in
> +     * mbedtls_safer_memcmp as it considers that to be safe */
> +    volatile const unsigned char *A = (volatile const unsigned char *) a;

                                                    no space after cast

> +    volatile const unsigned char *B = (volatile const unsigned char *) b;

                                                    same

> +    volatile unsigned char diff = 0;
> +
> +    for (size_t i = 0; i < size; i++)
> +    {
> +        unsigned char x = A[i], y = B[i];
> +        diff |= x ^ y;

After a discussion on IRC, it was noted that this conversion from
volatile to non-volatile was introduced by mbedTLS devs to avoid
warnings with the IAR compiler.

Since we don't want to change the function but use it as it is, we
should still add a comment to avoid somebody in the future from
"cleaning this up".

maybe something like:

/* this conversion was introduced by mbedTLS to suppress a IAR
 * compiler  warning. keep it as it is.
 */

> +    }
> +
> +    return diff;
> +}
>  #endif /* ENABLE_CRYPTO_MBEDTLS */
> diff --git a/src/openvpn/crypto_openssl.c b/src/openvpn/crypto_openssl.c
> index a81dcfd8..9e7ea0ff 100644
> --- a/src/openvpn/crypto_openssl.c
> +++ b/src/openvpn/crypto_openssl.c
> @@ -1066,4 +1066,9 @@ hmac_ctx_final(HMAC_CTX *ctx, uint8_t *dst)
>      HMAC_Final(ctx, dst, &in_hmac_len);
>  }
>  
> +int
> +memcmp_constant_time(const void *a, const void *b, size_t size)
> +{
> +    return CRYPTO_memcmp(a, b, size);
> +}
>  #endif /* ENABLE_CRYPTO_OPENSSL */
> 


Cheers,
Gert Doering April 17, 2020, 8:51 a.m. | #2
Hi,

On Thu, Apr 16, 2020 at 01:39:28PM +0200, Arne Schwabe wrote:
> index 18a86ceb..dadf0a90 100644
> --- a/src/openvpn/crypto.h
> +++ b/src/openvpn/crypto.h
> @@ -528,21 +528,7 @@ void crypto_read_openvpn_key(const struct key_type *key_type,
>   * As memcmp(), but constant-time.
>   * Returns 0 when data is equal, non-zero otherwise.
>   */
> -static inline int
> -memcmp_constant_time(const void *a, const void *b, size_t size)
> -{

Not sure I understand the motivation for this change.  "Just so uncrustify
stops trying to change this" is not really strong.

Also, keeping the "inline" part would be good...  this is in the per-packet
path.

gert
Antonio Quartulli April 17, 2020, 1:42 p.m. | #3
On 17/04/2020 10:51, Gert Doering wrote:
> Hi,
> 
> On Thu, Apr 16, 2020 at 01:39:28PM +0200, Arne Schwabe wrote:
>> index 18a86ceb..dadf0a90 100644
>> --- a/src/openvpn/crypto.h
>> +++ b/src/openvpn/crypto.h
>> @@ -528,21 +528,7 @@ void crypto_read_openvpn_key(const struct key_type *key_type,
>>   * As memcmp(), but constant-time.
>>   * Returns 0 when data is equal, non-zero otherwise.
>>   */
>> -static inline int
>> -memcmp_constant_time(const void *a, const void *b, size_t size)
>> -{
> 
> Not sure I understand the motivation for this change.  "Just so uncrustify
> stops trying to change this" is not really strong.

well, sometimes to adhere to the codestyle, you have to re-arrange code :)

On top of that, this is basically allowing us to re-use an existing
openssl API when possible.

> 
> Also, keeping the "inline" part would be good...  this is in the per-packet
> path.

I am not sure it would work in this case, because the function is
defined in a .c file now - it's not inlineable anymore outside of the
mbedtls code.....

Regards,
Gert Doering April 17, 2020, 3:36 p.m. | #4
Hi,

On Fri, Apr 17, 2020 at 03:42:49PM +0200, Antonio Quartulli wrote:
> >> -static inline int
> >> -memcmp_constant_time(const void *a, const void *b, size_t size)
> >> -{
> > 
> > Not sure I understand the motivation for this change.  "Just so uncrustify
> > stops trying to change this" is not really strong.
> 
> well, sometimes to adhere to the codestyle, you have to re-arrange code :)

"rearrange" and "rewrite in a not easy to understand way" (which looks
a bit overthought to me, TBH - unlike "secure memzero" I cannot see an
obvious reason why all that volatile would be relevant).

> On top of that, this is basically allowing us to re-use an existing
> openssl API when possible.

True, but if that turns out to be a code complication and reduces
efficiency, I'm not convinced it's the right way to spend our cycles.

> > Also, keeping the "inline" part would be good...  this is in the per-packet
> > path.
> 
> I am not sure it would work in this case, because the function is
> defined in a .c file now - it's not inlineable anymore outside of the
> mbedtls code.....

This is why I'm not exactly happy with the change.

We could do it "openvpn style" all in header files, or we could just
leave the function alone.

gert
Steffan Karger April 26, 2020, 9:25 a.m. | #5
Hi,

On 17-04-2020 17:36, Gert Doering wrote:
> On Fri, Apr 17, 2020 at 03:42:49PM +0200, Antonio Quartulli wrote:
>>>> -static inline int
>>>> -memcmp_constant_time(const void *a, const void *b, size_t size)
>>>> -{
>>>
>>> Not sure I understand the motivation for this change.  "Just so uncrustify
>>> stops trying to change this" is not really strong.
>>
>> well, sometimes to adhere to the codestyle, you have to re-arrange code :)
> 
> "rearrange" and "rewrite in a not easy to understand way" (which looks
> a bit overthought to me, TBH - unlike "secure memzero" I cannot see an
> obvious reason why all that volatile would be relevant).

This secure memcmp is relevant to avoid timing side channels in e.g.
authentication tag compare. Think about the HMAC in our tls-auth/crypt
and the HMAC of (non-AEAD) data channel packets.

>> On top of that, this is basically allowing us to re-use an existing
>> openssl API when possible.
> 
> True, but if that turns out to be a code complication and reduces
> efficiency, I'm not convinced it's the right way to spend our cycles.
> 
>>> Also, keeping the "inline" part would be good...  this is in the per-packet
>>> path.
>>
>> I am not sure it would work in this case, because the function is
>> defined in a .c file now - it's not inlineable anymore outside of the
>> mbedtls code.....
> 
> This is why I'm not exactly happy with the change.
> 
> We could do it "openvpn style" all in header files, or we could just
> leave the function alone.

This kind of code is a tricky balance between "prevent the compiler from
optimizing it to a not-constant-time implementation" and "as much
performance as we can get". Moving this responsibility to the crypto
library seems like a good idea to me.

And because our recommended data channel ciphers are AEAD ciphers for
which the auth tag compare is handled internally by the crypto library,
I don't care so much for the performance aspect. Want best security? Use
AEAD! Want best performance? Use AEAD!

You get the point. Use AEAD ;-)

-Steffan
Gert Doering April 26, 2020, 9:34 a.m. | #6
Hi,

On Sun, Apr 26, 2020 at 11:25:49AM +0200, Steffan Karger wrote:
> >> well, sometimes to adhere to the codestyle, you have to re-arrange code :)
> > 
> > "rearrange" and "rewrite in a not easy to understand way" (which looks
> > a bit overthought to me, TBH - unlike "secure memzero" I cannot see an
> > obvious reason why all that volatile would be relevant).
> 
> This secure memcmp is relevant to avoid timing side channels in e.g.
> authentication tag compare. Think about the HMAC in our tls-auth/crypt
> and the HMAC of (non-AEAD) data channel packets.

I do understand why it has to be constant *time*, in regards to "do the
compared buffers differ or not".

I do not see how all this "volatile" and "copy from pointer to variables
to other stuff" handwaving is going to make any difference wrt constant
time comparison.

And it hurts my eyes.

[..]
> This kind of code is a tricky balance between "prevent the compiler from
> optimizing it to a not-constant-time implementation" 

How could the compiler optimize *this* code?  It has very explicit
instructions to build the xor of every single byte in the buffer and
or them all together, and return the result as an integer.

Unlike secure_memzero() whatever compiler optimization is chosen, it
still needs to do the actual math for *all bytes*.   It can not optimize 
out "if a string does not match early on, end comparisions more early".

(It could, if the result is already 0xff, but that optimization would
slow down the loop, so I would find very surprising)


> and "as much
> performance as we can get". Moving this responsibility to the crypto
> library seems like a good idea to me.
> 
> And because our recommended data channel ciphers are AEAD ciphers for
> which the auth tag compare is handled internally by the crypto library,
> I don't care so much for the performance aspect. Want best security? Use
> AEAD! Want best performance? Use AEAD!
> 
> You get the point. Use AEAD ;-)

Now that's definitely a strong argument against my "inline! performance!"
argument.

gert
Steffan Karger April 26, 2020, 9:49 a.m. | #7
Hi,

On 26-04-2020 11:34, Gert Doering wrote:
> On Sun, Apr 26, 2020 at 11:25:49AM +0200, Steffan Karger wrote:
>>>> well, sometimes to adhere to the codestyle, you have to re-arrange code :)
>>>
>>> "rearrange" and "rewrite in a not easy to understand way" (which looks
>>> a bit overthought to me, TBH - unlike "secure memzero" I cannot see an
>>> obvious reason why all that volatile would be relevant).
>>
>> This secure memcmp is relevant to avoid timing side channels in e.g.
>> authentication tag compare. Think about the HMAC in our tls-auth/crypt
>> and the HMAC of (non-AEAD) data channel packets.
> 
> I do understand why it has to be constant *time*, in regards to "do the
> compared buffers differ or not".
> 
> I do not see how all this "volatile" and "copy from pointer to variables
> to other stuff" handwaving is going to make any difference wrt constant
> time comparison.
> 
> And it hurts my eyes.

Pretty it is not. But "let's not try to outsmart the crypto library
folks" makes sense to me.

The copying stuff is probably just about making some annoying compiler
happy. We could probably leave that out, but that makes it harder to see
that we follow the mbed internal implementation.

When inlining this without volatile keywords, a compiler might at some
point become smart enough to realize "hey, this caller only cares about
zero/nonzero, not the actual value. And this code will only return zero
if *all* bytes are equal, so I can stop comparing as soon as soon as
I've found a difference".

Up to now, it seems compilers have not gotten this smart. But it's not
like we're keeping a close eye on that. So I would love to get rid of
the responsibility :-)

-Steffan
Arne Schwabe April 26, 2020, 10:38 p.m. | #8
Am 26.04.20 um 11:34 schrieb Gert Doering:
> Hi,
> 
> On Sun, Apr 26, 2020 at 11:25:49AM +0200, Steffan Karger wrote:
>>>> well, sometimes to adhere to the codestyle, you have to re-arrange code :)
>>>
>>> "rearrange" and "rewrite in a not easy to understand way" (which looks
>>> a bit overthought to me, TBH - unlike "secure memzero" I cannot see an
>>> obvious reason why all that volatile would be relevant).
>>
>> This secure memcmp is relevant to avoid timing side channels in e.g.
>> authentication tag compare. Think about the HMAC in our tls-auth/crypt
>> and the HMAC of (non-AEAD) data channel packets.
> 
> I do understand why it has to be constant *time*, in regards to "do the
> compared buffers differ or not".
> 
> I do not see how all this "volatile" and "copy from pointer to variables
> to other stuff" handwaving is going to make any difference wrt constant
> time comparison.
> 
> And it hurts my eyes.

Yeah the goal is basically do what the crypto library is doing. And if
you play with godbolt. So we don't need to go down this path of having
to come up with our own version.

And if you care about speed then we should definitively go for OpenSSL's
memcmp function. Since it is implemented in assembler it does not try to
breaks the compiler compilation optimisation with volatile that might
trigger more memory loads than necessary but can be a small fast
constant time function.

If you play a bit with godbolt.org (https://godbolt.org/z/gXgcC9) you
will see that the code that is generated from our current version is not
yet optimised to non constant versions but especially the clang compiler
is getting close. It completely optimises away the function for compile
strings (main2 just becomes return 95), builds a version optimised for
one fixed string and vectorises the generic version. So I am not sure if
these variants still have their constant with modern processes and
speculative execution.

Arne
Gert Doering May 7, 2020, 1:21 p.m. | #9
Acked-by: Gert Doering <gert@greenie.muc.de>

I still feel it hurts my eyes, and is way overcomplicating things, but
if this is what mbedtls is using internally (why are they not exporting
it??!), it should be good enough for us.   Further, as it's not being
used for AEAD anyway, I withdraw my "performance" argument (Steffan 
could have just ACKed it... :-) ).

Stared at the code (awww!), test-built with openssl and mbedtls, passed
t_client tests.

We do not have a unit test for this, and crypto.c::test_crypto() actually
does the "compare bytes loop" manually (to be able to print differences).
Volunteers...?

Your patch has been applied to the master branch.

commit 4dddca52a8432095dd85ff652fae61a2aedb3785
Author: Arne Schwabe
Date:   Thu Apr 16 13:39:28 2020 +0200

     Use crypto library functions for const time memcmp when possible

     Signed-off-by: Arne Schwabe <arne@rfc2549.org>
     Acked-by: Gert Doering <gert@greenie.muc.de>
     Message-Id: <20200416113930.15192-1-arne@rfc2549.org>
     URL: https://www.mail-archive.com/openvpn-devel@lists.sourceforge.net/msg19749.html
     Signed-off-by: Gert Doering <gert@greenie.muc.de>


--
kind regards,

Gert Doering

Patch

diff --git a/src/openvpn/crypto.h b/src/openvpn/crypto.h
index 18a86ceb..dadf0a90 100644
--- a/src/openvpn/crypto.h
+++ b/src/openvpn/crypto.h
@@ -528,21 +528,7 @@  void crypto_read_openvpn_key(const struct key_type *key_type,
  * As memcmp(), but constant-time.
  * Returns 0 when data is equal, non-zero otherwise.
  */
-static inline int
-memcmp_constant_time(const void *a, const void *b, size_t size)
-{
-    const uint8_t *a1 = a;
-    const uint8_t *b1 = b;
-    int ret = 0;
-    size_t i;
-
-    for (i = 0; i < size; i++)
-    {
-        ret |= *a1++ ^ *b1++;
-    }
-
-    return ret;
-}
+int memcmp_constant_time(const void *a, const void *b, size_t size);
 
 static inline bool
 key_ctx_bi_defined(const struct key_ctx_bi *key)
diff --git a/src/openvpn/crypto_mbedtls.c b/src/openvpn/crypto_mbedtls.c
index 3e77fa9e..35072b73 100644
--- a/src/openvpn/crypto_mbedtls.c
+++ b/src/openvpn/crypto_mbedtls.c
@@ -972,4 +972,23 @@  hmac_ctx_final(mbedtls_md_context_t *ctx, uint8_t *dst)
     ASSERT(0 == mbedtls_md_hmac_finish(ctx, dst));
 }
 
+int
+memcmp_constant_time(const void *a, const void *b, size_t size)
+{
+    /* mbed TLS has a no const time memcmp function that it exposes
+     * via its APIs like OpenSSL does with CRYPTO_memcmp
+     * Adapt the function that mbedtls itself uses in
+     * mbedtls_safer_memcmp as it considers that to be safe */
+    volatile const unsigned char *A = (volatile const unsigned char *) a;
+    volatile const unsigned char *B = (volatile const unsigned char *) b;
+    volatile unsigned char diff = 0;
+
+    for (size_t i = 0; i < size; i++)
+    {
+        unsigned char x = A[i], y = B[i];
+        diff |= x ^ y;
+    }
+
+    return diff;
+}
 #endif /* ENABLE_CRYPTO_MBEDTLS */
diff --git a/src/openvpn/crypto_openssl.c b/src/openvpn/crypto_openssl.c
index a81dcfd8..9e7ea0ff 100644
--- a/src/openvpn/crypto_openssl.c
+++ b/src/openvpn/crypto_openssl.c
@@ -1066,4 +1066,9 @@  hmac_ctx_final(HMAC_CTX *ctx, uint8_t *dst)
     HMAC_Final(ctx, dst, &in_hmac_len);
 }
 
+int
+memcmp_constant_time(const void *a, const void *b, size_t size)
+{
+    return CRYPTO_memcmp(a, b, size);
+}
 #endif /* ENABLE_CRYPTO_OPENSSL */