lib: memcmp_nta: add timing-attack secure memcmp
Subsystems (2)
A message that is not in the archive (sent off-list or not yet received): [email protected]
PATCH 1/1 lib: memcmp_nta: add timing-attack secure memcmp
If you need to compare a password or a hash value, the timing of the comparison function can give valuable clues to the attacker. Let's say the password is 123456 and the attacker tries abcdef. If the comparision function fails at the first byte without looking at the other bytes, then the attacker can measure the difference in runtime and deduce which byte was wrong, reducing the attack space from exponential to polynomial. [Daniel J. Bernstein]
Therefore add memcmp_nta ({n}o {t}iming {a}ttacks) in order to avoid such scenarios and to facilitate development by providing a generic function for (e.g.) the crypto and networking subsystems.
--- include/linux/string.h | 3 +++ lib/string.c | 22 ++++++++++++++++++++++ 2 files changed, 25 insertions(+)
include/linux/string.h +3 -0
@@ -107,6 +107,9 @@ extern void * memscan(void *,int,__kernel_size_t);#ifndef __HAVE_ARCH_MEMCMPextern int memcmp (const void *,const void *,__kernel_size_t );#endif +#ifndef __HAVE_ARCH_MEMCMP_NTA +extern int memcmp_nta (const void *,const void *,__kernel_size_t ); +#endif #ifndef __HAVE_ARCH_MEMCHRextern void *memchr (const void *,int ,__kernel_size_t );#endif
lib/string.c +22 -0
@@ -661,6 +661,28 @@ int memcmp(const void *cs, const void *ct, size_t count)EXPORT_SYMBOL (memcmp);#endif +#ifndef __HAVE_ARCH_MEMCMP_NTA +/** +* memcmp_nta - memcmp that is secure against timing attacks +* @cs: One area of memory +* @ct: Another area of memory +* @count: The size of the area. +* +* returns 0 if both areas are equal to each other, non-zero otherwise +*/ +int memcmp_nta (const void *cs,const void *ct,size_t count) +{ +const unsigned char *su1, *su2; +int res =0 ; + +for (su1 = cs, su2 = ct;0 < count; ++su1, ++su2, count--) + res |= (*su1 ^ *su2); + +return res; +} +EXPORT_SYMBOL (memcmp_nta); +#endif +#ifndef __HAVE_ARCH_MEMSCAN/** * memscan - Find a character in an area of memory.
Signature · 1 line
1.7.11.7
Quoted 1 line · Daniel Borkmann
add
memcmp_nta({n}o {t}iming {a}ttacks)
Why should this be in the kernel?
Quoted 4 lines · Joe Perches
Quoted 1 line · Daniel Borkmann
add
memcmp_nta({n}o {t}iming {a}ttacks)Why should this be in the kernel?
As the commit message already says, so that current or future (e.g.) network protocol code or modules can make use of this when dealing with cryptographic hash comparisons.
Quoted 9 lines · Daniel Borkmann
Quoted 4 lines · Joe Perches
Quoted 1 line · Daniel Borkmann
add
memcmp_nta({n}o {t}iming {a}ttacks)Why should this be in the kernel?
As the commit message already says, so that current or future (e.g.) network protocol code or modules can make use of this when dealing with cryptographic hash comparisons.
Do we have any in-kernel users that need this? If not, then don't add it now, but rather, add it when we actually have a user. We almost never add kernel functions that no one calls, that would be just wasteful.
sorry,
greg k-h
Quoted 7 lines · Greg KH
Quoted 6 lines · Daniel Borkmann
Quoted 4 lines · Joe Perches
Quoted 1 line · Daniel Borkmann
add
memcmp_nta({n}o {t}iming {a}ttacks)Why should this be in the kernel?
Quoted 8 lines
Quoted 3 lines
As the commit message already says, so that current or future (e.g.) network protocol code or modules can make use of this when dealing with cryptographic hash comparisons.
Do we have any in-kernel users that need this? If not, then don't add it now, but rather, add it when we actually have a user. We almost never add kernel functions that no one calls, that would be just wasteful.
Agreed, I think there are users for it. But I'll resend a set at a later point in time, after some more testing and verifying.
Thanks, Greg.
Quoted 8 lines · Daniel Borkmann
If you need to compare a password or a hash value, the timing of the comparison function can give valuable clues to the attacker. Let's say the password is 123456 and the attacker tries abcdef. If the comparision function fails at the first byte without looking at the other bytes, then the attacker can measure the difference in runtime and deduce which byte was wrong, reducing the attack space from exponential to polynomial. [Daniel J. Bernstein]
Quoted 6 lines
Therefore add
memcmp_nta({n}o {t}iming {a}ttacks) in order to avoid such scenarios and to facilitate development by providing a generic function for (e.g.) the crypto and networking subsystems.Signed-off-by Daniel Borkmann <[email protected]>---
I read this as "compare memory with non-temporal access". Perhaps something like "memcpy_constant_time" would be less confusing.
--Andy
Quoted 13 lines · Andy Lutomirski
Quoted 12 lines · Daniel Borkmann
If you need to compare a password or a hash value, the timing of the comparison function can give valuable clues to the attacker. Let's say the password is 123456 and the attacker tries abcdef. If the comparision function fails at the first byte without looking at the other bytes, then the attacker can measure the difference in runtime and deduce which byte was wrong, reducing the attack space from exponential to polynomial. [Daniel J. Bernstein]
Therefore add
memcmp_nta({n}o {t}iming {a}ttacks) in order to avoid such scenarios and to facilitate development by providing a generic function for (e.g.) the crypto and networking subsystems.
Quoted 5 lines
Quoted 2 lines
Signed-off-by Daniel Borkmann <[email protected]>---
I read this as "compare memory with non-temporal access". Perhaps something like "
memcpy_constant_time" would be less confusing.
You probably mean "memcmp_constant_time".
Well, this could probably be misinterpreted, that for every possible input it will take only O(1), which of course it doesn't. It's simply that for both results (``equals to'', ``does not equal to'') it will take the same amount of *operations* to achieve this in order to not leak any time information of a successful or not successful comparison, where the attacker could draw conclusions if he might have gotten parts of the hash/key/.. right or wrong.
* Daniel Borkmann:
Quoted 1 line
+ *
memcmp_nta- memcmp that is secure against timing attacks
It's not providing an ordering, so it should not have "cmp" in the name.
lib/string.c int memcmp(const void *cs, const void *ct, size_t count) · line 679
Quoted 2 lines
lib/string.c +2
-0+for (su1 = cs, su2 = ct;0 < count; ++su1, ++su2, count--) + res |= (*su1 ^ *su2);
The compiler could still short-circuit this loop. Unlikely at present, but this looks like a maintenance hazard.
Quoted 1 line · Florian Weimer
* Daniel Borkmann:
Thanks for your feedback, Florian!
Quoted 4 lines
Quoted 1 line
+ *
memcmp_nta- memcmp that is secure against timing attacksIt's not providing an ordering, so it should not have "cmp" in the name.
I agree. What would you suggest? Probably, it would make sense to integrate this into the Linux crypto API and name it sth like ...
crypto_mem_verify(const void *,const void *,__kernel_size_t)
... which returns:
== 0 - mem regions equal each other
!= 0 - mem regions do not equal each other
Quoted 5 lines
lib/string.c int memcmp(const void *cs, const void *ct, size_t count) · line 679
Quoted 2 lines
lib/string.c +2
-0+for (su1 = cs, su2 = ct;0 < count; ++su1, ++su2, count--) + res |= (*su1 ^ *su2);The compiler could still short-circuit this loop. Unlikely at present, but this looks like a maintenance hazard.
So then better we leave out '|' as a possible candidate and rewrite it as:
+ for (su1 = cs, su2 = ct; 0 < count; ++su1, ++su2, count--)
+ res += (*su1 ^ *su2);
* Daniel Borkmann:
Quoted 13 lines · Florian Weimer
Quoted 1 line
* Daniel Borkmann:
Thanks for your feedback, Florian!
Quoted 4 lines
Quoted 1 line
+ *
memcmp_nta- memcmp that is secure against timing attacksIt's not providing an ordering, so it should not have "cmp" in the name.
I agree. What would you suggest? Probably, it would make sense to integrate this into the Linux crypto API and name it sth like ...
Quoted 6 lines
crypto_mem_verify(const void *,const void *,__kernel_size_t)... which returns:
== 0 - mem regions equal each other
!= 0 - mem regions do not equal each other
crypto_mem_equal or crypto_mem_equals should be fine. Or anything else which matches an existing function name with similar function.
Review
Quoted 10 lines
Quoted 5 lines
lib/string.c int memcmp(const void *cs, const void *ct, size_t count) · line 679
Quoted 2 lines
lib/string.c +2
-0+for (su1 = cs, su2 = ct;0 < count; ++su1, ++su2, count--) + res |= (*su1 ^ *su2);The compiler could still short-circuit this loop. Unlikely at present, but this looks like a maintenance hazard.
So then better we leave out '|' as a possible candidate and rewrite it as:
(quoted diff) +2
-0+ for (su1 = cs, su2 = ct; 0 < count; ++su1, ++su2, count--) + res += (*su1 ^ *su2);
That will cause false matches for long inputs.
If we had only four platforms to support, I would write this function in assembler because it will be considerably easier to read.