There are lots of authentication functions which end by comparing two digests. The recent ccm_decrypt_message is typical, ending with
return (memcmp(tag, src + mlength, tlength) == 0);
This can leak information (via cache or timing) on the position of the first difference, which might cause problems in some situations. Would it be a good idea to add a side-channel silent memory comparison function? The hardest question is, as often, how it should be named. But it should be pretty easy to implement, I think
int mem_equal (const void *ap, const void *bp, size_t n) { volatile const unsigned char *a = ap; volatile const unsigned char *b = bp volatile unsigned char d; size_t i; for (i = d = 0; i < n; i++) d |= a[i] ^ b[i]; return d == 0; }
should do (even if maybe volatile const is an unusual combination of qualifiers). Is this a good name?
The nacl library (by djb et al) includes similar functions, see http://nacl.cr.yp.to/verify.html.
Regards, /Niels
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA256
Aloha!
Niels Möller wrote:
int mem_equal (const void *ap, const void *bp, size_t n) { volatile const unsigned char *a = ap; volatile const unsigned char *b = bp volatile unsigned char d; size_t i; for (i = d = 0; i < n; i++) d |= a[i] ^ b[i]; return d == 0; }
should do (even if maybe volatile const is an unusual combination of qualifiers). Is this a good name?
Yes, and a good function to add. One could think/hope that the OS provided side channel silent memory functions. But since that is not always (rarely) the case, providing one in nettle is a good thing.
AFAIK (browsing the docs) there aren't any specific functions for comparing digests. Instead the user has to implement thing themselves. Would it be an advantage to have mappings to either create a generic digest compare or specific for the different digests and MACs?
uint8_t compare_digests(uint8_t *digest0, uint8_t *digest1, uint8_t *DIGEST_SIZE);
or
uint8_t compare_md5_digests(uint8_t *digest0, uint8_t *digest1);
Or something like that. for MD5, SHA-digests, UMAC etc.
- -- Med vänlig hälsning, Yours
Joachim Strömbergson - Alltid i harmonisk svängning. ======================================================================== Joachim Strömbergson Secworks AB joachim@secworks.se ========================================================================
Joachim Strömbergson joachim@secworks.se writes:
Yes, and a good function to add. One could think/hope that the OS provided side channel silent memory functions.
Plain memcmp should be optimized for speed, I guess.
AFAIK (browsing the docs) there aren't any specific functions for comparing digests. Instead the user has to implement thing themselves.
I also did a search for memcmp, and it's used in very few places inside nettle (there are also bignum-comparisons, which may have similar issues).
But applications are expected to compare digests, produced by some of the mac or aead constructions, and they'd typically use plain memcmp. So a side-channel silent variant should definitely be documented and recom,ended for users.
I'm now thinking aloud, but maybe it would make sense to also change the various digest functions to return the pointer to the digest? So one could do, e.g.,
if (mem_equal (hmac_sha256_digest(...), expected, SHA1_DIGEST_SIZE)) ...;
or even
#define DIGEST_EQUAL(ctx, f, size, buf, expected) \ mem_equal(f(ctx, size, buf), expected, size)
(I'm not saying that macro is a good idea, but returning the pointer makes such things simpler).
Or one could add a corresponding _verify function for each _digest function, which takes the expected digest as input. Not sure that's a good idea. That would be a pretty large number of functions, but if it makes applications simpler, it could be worth the effort.
uint8_t compare_digests(uint8_t *digest0, uint8_t *digest1, uint8_t *DIGEST_SIZE);
That looks similar to the mem_equal I sketched, except that the third argument looks strange. Was that intentional?
Regards, /Niels
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA256
Aloha!
Niels Möller wrote:
That looks similar to the mem_equal I sketched, except that the third argument looks strange. Was that intentional?
Very much not so. ;-) A plain, unsigned integer was the atention. But my copy/paste fingers were a wee bit faster than the brain.
- -- Med vänlig hälsning, Yours
Joachim Strömbergson - Alltid i harmonisk svängning. ======================================================================== Joachim Strömbergson Secworks AB joachim@secworks.se ========================================================================
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA256
Aloha!
Niels Möller wrote:
Plain memcmp should be optimized for speed, I guess.
Maybe. I wouldn't be surprised if the OpenBSD folks would think it would be an acceptable performance cost to make it more side channel silent. Or at least provide a silent version om memcmp.
I'm actually gonna check - their fork of OpenSSL should probably be using something like that.
Nikos - What do you do in GnuTLS?
- -- Med vänlig hälsning, Yours
Joachim Strömbergson - Alltid i harmonisk svängning. ======================================================================== Joachim Strömbergson Secworks AB joachim@secworks.se ========================================================================
On Sun, Apr 27, 2014 at 10:39 PM, Niels Möller nisse@lysator.liu.se wrote:
should do (even if maybe volatile const is an unusual combination of qualifiers). Is this a good name?
Why not nettle memcmp? It would be good to export those functions as there are not typically available and each program re-invents them and it is not always easy to avoid compiler optimizations.
regards, Nikos
Nikos Mavrogiannopoulos n.mavrogiannopoulos@gmail.com writes:
Why not nettle memcmp?
I think "memcmp" should be avoided in the name, because (1) the memcmp return value distinguishes between > and <, while the side-channel silent comparison function should check only for equality, and (2) even if the link symbol should be nettle_something, it would be nice if the corresponding header file providea a name without any nettle prefix, and then it's not good to collide with the standard memcmp.
It would be good to export those functions as there are not typically available and each program re-invents them
Definitely.
Regards, /Niels
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA256
Aloha!
Niels Möller wrote:
There are lots of authentication functions which end by comparing two digests. The recent ccm_decrypt_message is typical, ending with
return (memcmp(tag, src + mlength, tlength) == 0);
int mem_equal (const void *ap, const void *bp, size_t n) { volatile const unsigned char *a = ap; volatile const unsigned char *b = bp
Missing semicolon for bp.
volatile unsigned char d; size_t i; for (i = d = 0; i < n; i++) d |= a[i] ^ b[i]; return d == 0;
You should return d here if you want the behaviour to match memcmp.
FWIW I implemented the function above (minus changes to stdint types) in my umactests. And for 100M messages, each 1024 Bytes I see something like a few second total increase in performance in comparison to using the memcmp provided in OSX. I can live with that.
- -- Med vänlig hälsning, Yours
Joachim Strömbergson - Alltid i harmonisk svängning. ======================================================================== Joachim Strömbergson Secworks AB joachim@secworks.se ========================================================================
nettle-bugs@lists.lysator.liu.se
-
Joachim Strömbergson -
Nikos Mavrogiannopoulos -
nisse＠lysator.liu.se