Skip to contentSkip to conversation

Remove quadratic complexity from openvpn_base64_decode()

PATCH In review Steffan Karger 2 participants 3 messages Sep 4, 2014 – Sep 14, 2014

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 Remove quadratic complexity from openvpn_base64_decode()

Hi,

Attached a patch for a change suggested by Jann Horn, to remove the quadratic complexity from openvpn_base64_decode().

The suggestion was originally sent to the security list, because quadratic complexity can potentially lead to a denial-of-service attack vector. In the current OpenVPN codebase, this is however *not* the case.

OpenVPN doesn't use it's base64 encoding a lot. The only place where a denial of service could be interesting is when the server uses a management interface, and an authenticated client sends a malicious challenge response to the server. Those responses are sent over the TLS channel, and openvpn limits those messages to 2048 bytes (TLS_CHANNEL_BUF_SIZE). The old base64 decode code has a complexity of (n/8)^2 (one strlen over on average half the string length per 4-byte base64 token), which results in 65536 byte comparisons per message. That's not enough to be practical for an attack.

That said, I do like the suggestion to make the code constant time. I'd say it should be applied to both master and 2.3 branches as a bugfix.

-Steffan

From 488390691137e9a8ea4c2c63db930e2396049934 Mon Sep 17 00:00:00 2001
From: Jann Horn <[email protected]...>
Date: Wed, 16 Jul 2014 21:55:42 +0200
Subject: [PATCH] Remove quadratic complexity from openvpn_base64_decode()

Every four input characters, openvpn_base64_decode called token_decode, which in turn called strlen() on the remaining input. This means that base64 decoding in openvpn had quadratic complexity.

All we really need to know is whether the token is complete, so replace the check to check just that, and make the complexity linear wrt the input length.

---
 src/openvpn/base64.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
src/openvpn/base64.c +1 -1
index bb89aae..7dccec2 100644
@@ -110,7 +110,7 @@ token_decode(const char *token)
     int i;
     unsigned int val = 0;
     int marker = 0;
-    if (strlen(token) < 4)
+    if (!token[0] || !token[1] || !token[2] || !token[3])
 	return DECODE_ERROR;
     for (i = 0; i < 4; i++) {
 	val *= 64;
Signature · 1 line
1.9.1
#1 lore raw

Hi,

Quoted 2 lines · Steffan Karger

Attached a patch for a change suggested by Jann Horn, to remove the quadratic complexity from openvpn_base64_decode().

[..]

Quoted 2 lines

That said, I do like the suggestion to make the code constant time. I'd say it should be applied to both master and 2.3 branches as a bugfix.

ACK. Will merge to both branches ASAP.

gert

Signature · 4 lines
USENET is *not* the non-clickable part of WWW!
                                                           //www.muc.de/~gert/
Gert Doering - Munich, Germany                             [email protected]...
fax: +49-89-35655025                        [email protected]...
#2 lore raw
In reply to Steffan Karger

Your patch has been applied to the master and release/2.3 branches.

commit 25e1ec71dd150e803c0a25308c193fea124c7b7a (master) commit 72cbc106d95fb18892c739f128d29d4f54179771 (release/2.3)

Author: Jann Horn
Date:   Wed Jul 16 21:55:42 2014 +0200
     Remove quadratic complexity from openvpn_base64_decode()

     Signed-off-by: Steffan Karger <[email protected]...>
     Acked-by: Gert Doering <[email protected]...>
     Message-Id: <[email protected]...>
     URL: http://article.gmane.org/gmane.network.openvpn.devel/9016
     Signed-off-by: Gert Doering <[email protected]...>

--
kind regards,

Gert Doering