Remove quadratic complexity from openvpn_base64_decode()
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
@@ -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
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]...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