[PATCH] MSLogon upgrade to use 64bit keys instead of 31bit

[llyzs]

Hi,

I think most people already aware that the current MSLogon only use 31bit key size for DH key exchange. This is extremely unsecure and scaring people using it.

Recently I checked the source codes and it turned out that in dh.c, the program calculating x^y%m is not good and causing this 31bit limitation.

I am willing to contribute my codes which works for full 64bit integer DH calculation, as long as you are willing to accept this change. It's simple to replace the old algorithm, pure C and portable.

Please let me know what you think. I can paste the code here for public domain.

[redge]

code is welcome if there backward compatibility ?

[llyzs]

I think backward compatibility can be maintained only if you keep the generator (the X in DH::XpowYmodN) at 31 bit, but this will probably decrease the security strength and a little more difficult to maintain.

My suggestion is to let user use a newer viewer if they are going to use the newer MSLogon, if we make that change to gain better security.

How do you think?

[llyzs]

Talking about compatibility, using new viewer to connect to old server shouldn't be any problem. it's just the problem when using an old viewer to connect to a new server.

[llyzs]

This patch will upgrade MSLogon to use 63 bits. I gave up 1 bit in order to avoid massive changing.

Test result:
o New viewer can connect to new server and old server without any problem.
o Old viewer will crash when connect to new server.

Code: Select all

Index: UltraVNC Project Root/UltraVNC/rfb/dh.h
===================================================================
--- UltraVNC Project Root/UltraVNC/rfb/dh.h	(revision 466)
+++ UltraVNC Project Root/UltraVNC/rfb/dh.h	(working copy)
@@ -30,7 +30,7 @@
 #include <math.h>
 #include <time.h>
 
-#define DH_MAX_BITS 31
+#define DH_MAX_BITS 63
 #define DH_RANGE 100
 
 #define DH_CLEAN_ALL_MEMORY				1
@@ -56,6 +56,7 @@
 	unsigned __int64 getValue(DWORD flags = DH_KEY);
 
 private:
+	unsigned __int64 XmulYmodN(unsigned __int64 x, unsigned __int64 y, unsigned __int64 N);
 	unsigned __int64 XpowYmodN(unsigned __int64 x, unsigned __int64 y, unsigned __int64 N);
 	unsigned __int64 generatePrime();
 	unsigned __int64 tryToGeneratePrime(unsigned __int64 start);
Index: UltraVNC Project Root/UltraVNC/rfb/dh.cpp
===================================================================
--- UltraVNC Project Root/UltraVNC/rfb/dh.cpp	(revision 466)
+++ UltraVNC Project Root/UltraVNC/rfb/dh.cpp	(working copy)
@@ -98,19 +98,31 @@
 	}
 	return (cnt >= DH_RANGE || prime >= maxNum) ? 0 : prime;
 }
- 
+
+//Multiply X by Y in modulus N
+//the values of X, Y and N are maximum 63 bits to simplify the process
+unsigned __int64 DH::XmulYmodN(unsigned __int64 x, unsigned __int64 y, unsigned __int64 N) {
+	unsigned __int64 result;
+
+	for (result = 0; x > 0; x >>= 1) {
+		if (x & 1)
+			result = (result + y) % N;
+		y = (y + y) % N;
+	}
+	return result;
+}
+
 //Raises X to the power Y in modulus N
 //the values of X, Y, and N can be massive, and this can be 
 //achieved by first calculating X to the power of 2 then 
 //using power chaining over modulus N
 unsigned __int64 DH::XpowYmodN(unsigned __int64 x, unsigned __int64 y, unsigned __int64 N) {
-	unsigned __int64 result = 1;
-	const unsigned __int64 oneShift63 = ((unsigned __int64) 1) << 63;
+	unsigned __int64 result;
 	
-	for (int i = 0; i < 64; y <<= 1, i++){
-		result = result * result % N;
-		if (y & oneShift63)
-			result = result * x % N;
+	for (result = 1; y > 0; y >>= 1) {
+		if (y & 1)
+			result = XmulYmodN(result, x, N);
+		x = XmulYmodN(x, x, N);
 	}
 	return result;
 }

[redge]

Old viewer will crash when connect to new server.

crash is not acceptable at all, but a message that old mslogon is not supported should be better.

[llyzs]

Hi,

Yes, crash is of course not acceptable, but this is really an arithmetic overflow problem in the old 31bit code, not the patched new one. And unfortunately I don't see any possibility to for the server check if the client supports only 31bit or not.

Now I can see two options for us, correctly me if I am wrong:

1. Apply the patch to old versions, that is, for release 1.0.6.6. Or
2. Stay with 31 bits forever

This is a simple and safe patch to address a serious security issue and arithmetic overflow bug. I really don't see any reason that we should stay with this 31 bits problem forever.

[redge]

llyzs

have a look with owner of SSVNC, maybe he could be help you
he know there a bug of MSLogon

[user=16042][/user]

[llyzs]

Hi redge,

Actually before I posted here, I already had a long discussion with Karl Runge, the owner of ssvnc, x11vnc and libvncserver project, regarding this topic. The discussion started with whether to add MSLogon client-side support, and Karl pointed straight towards this 31 bit security issue in UltraVNC.

And after the discussion I realized that the security issue is not the MSLogon protocol design (the protocol itself is fully 64bit, that's the good news), but just a bad algorithm implementing that protocol (that's the bad news). And this is why I decided to contribute this patch to solve the issue.

Please check some mail archives with topic "MSLogon discussion" here:

http://sourceforge.net/mailarchive/foru ... ax_rows=25

[krunge]

Hello Vic and Redge,

Yes, Vic and I have discussed this at length.

I think the only thing I want to point out is that although full 64 bits Anonymous DH is better than 31 bits, real security applications consider 512 bits the absolute minimum, and most use 1024 bits or more for the exchange.

Remember this is not a session key (that typically we want to be 128 bits), but rather it (Anon DH exchange) involves a Public Key Encryption key (like RSA) that we need to have much larger (i.e. >= 1024 bits) because of the math involved. Here are some references on key sizes:

http://www.ietf.org/rfc/rfc2631.txt
http://www.scs.carleton.ca/%7Epaulv/papers/Euro96-DH.ps

I would not be surprised if someone with some skill could write a tool (or a tool already exists) to crack 64 bits DH exchange in a few seconds or minutes. So while going to 64 bits would be an improvement, I feel it is still avoiding the real issues.