Skip to contentSkip to conversation

lib: memcmp_nta: add timing-attack secure memcmp

PATCH In review Daniel Borkmann 6 participants 10 messages Feb 10, 2013 – Feb 12, 2013 1 message not in the archive

Subsystems (2)
lore
Share & tools
lore

A message that is not in the archive (sent off-list or not yet received): [email protected]

#1 lore raw

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
index ac889c5..cf42800 100644
@@ -107,6 +107,9 @@ extern void * memscan(void *,int,__kernel_size_t);
 #ifndef __HAVE_ARCH_MEMCMP
 extern 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_MEMCHR
 extern void * memchr(const void *,int,__kernel_size_t);
 #endif
lib/string.c +22 -0
index e5878de..d56e0cb 100644
@@ -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
#2 lore raw
Quoted 1 line · Daniel Borkmann

add memcmp_nta ({n}o {t}iming {a}ttacks)

Why should this be in the kernel?

#3 lore raw
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.

#4 lore raw
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

#5 lore raw
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.

#6 lore raw
In reply to Daniel Borkmann
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.

---

I read this as "compare memory with non-temporal access". Perhaps something like "memcpy_constant_time" would be less confusing.

--Andy

#7 lore raw
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

---

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.

#8 lore raw
In reply to Daniel Borkmann

* 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.

#9 lore raw
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 attacks

It'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);

#10 lore raw

* 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 attacks

It'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.