Page MenuHome GnuPG

buf_eq_const() function in cipher/bufhelp.h may get wrong result
Open, HighPublic

Description

This issue is related to a GCC bug(https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102124), which may cause wrong calculation, causing buf_eq_const() function give positive result on different buffers.

362 /* Constant-time compare of two buffers.  Returns 1 if buffers are equal,
363    and 0 if buffers differ.  */
364 static inline int
365 buf_eq_const(const void *_a, const void *_b, size_t len)
366 {
367   const byte *a = _a;
368   const byte *b = _b;
369   int ab, ba;
370   size_t i;
371 
372   /* Constant-time compare. */
373   for (i = 0, ab = 0, ba = 0; i < len; i++)
374     {
375       /* If a[i] != b[i], either ab or ba will be negative. */
376       ab |= a[i] - b[i];
377       ba |= b[i] - a[i];
378     }
379 
380   /* 'ab | ba' is negative when buffers are not equal. */
382   return (ab | ba) >= 0;
383 }

On line 382, I think it should be return (ab | ba) == 0;
Because if 2 buffers equal to each other, the difference between any value of the buffer should be 0.
If 2 buffers do not equal to each other, the difference between any value of the buffer should be non-zero.
Non-zero value is either positive or negative value.

Because the GCC's bug, 2 different buffer's diff value got a "positive" data, however, positive data still means 2 buffers are different, only if the diff value of 2 buffers are 0, means they are equal, in this case return (ab | ba) >= 0; is apparently wrong.

Details

Event Timeline

werner triaged this task as High priority.Aug 31 2021, 7:58 AM
werner added projects: libgcrypt, toolchain.

(ab | ba) >= 0 is used to make optimization analysis for compiler more difficult. I see that with (ab | ba) == 0, it would be much easier for compiler to conclude than loop could exit early as soon as first a[i] != b[i] is seen.

GCC bug happens inside the loop and workaround (if we want) should be in there. For example, adding memory barrier in loop for specific GCC version would prevent autovectorization and block the bug.

Based on GCC bugzilla, affected released GCC versions are 11.1 and 11.2.