From daw@cs.berkeley.edu Thu Aug 8 03:27:03 PDT 1996 Article: 18 of isaac.lists.netware-hack Path: news.isaac.cs.berkeley.edu!not-for-mail From: David Wagner Newsgroups: isaac.lists.netware-hack Subject: Netware challenge-response Date: 5 Aug 1996 17:55:36 -0700 Organization: ISAAC Group, UC Berkeley Lines: 112 Sender: daemon@abraham.cs.berkeley.edu Approved: mail2news@news.isaac.cs.berkeley.edu Distribution: isaac Message-ID: <199608052352.QAA27690@joseph.cs.berkeley.edu> NNTP-Posting-Host: abraham.cs.berkeley.edu Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit >Received: (from majordom@localhost) by dey-systems.com (8.6.12/8.6.12) id UAA00452 for netware-hack-outgoing; Mon, 5 Aug 1996 20:21:55 -0500 X-Mailer: ELM [version 2.4 PL25] Precedence: bulk I took another look at the Netware 3.x challenge-response password authentication protocol, which (as I understand it) is essentially server -> client: r,s [challenge] client -> server: f(r) xor f(s) [response] Here r and s are each 32 bit values which together form the server's challenge (aka "session encryption key" to some folks, though it is not really a session encryption key). Also f(r) is the hash (aka "encryption" to some folks, though it's really just hashing) of the user's password and the value r. I think the protocol implemention may contain a weakness. Here's why. Note that if r == s, then the client's response is easy to predict: it's just 0, regardless of the user's password. If r == s happens with fairly high probability, then an attacker can pretend to be the client, using any old password he likes, and just repeatedly try to log in. The attacker will succeed if the server ever uses a challenge r,s with r == s, so if r == s is picked fairly often by the server, the attacker won't have to try too many times. So we need to analyze how often r == s will happen. A long time ago Fauzan Mirza kindly passed on to me some C source code which claimed to be reverse-engineered from the Netware server implementation. That code shows a pretty bad random number generator to pick r,s: the server maintains two LCPRNGs, as follows: /* paraphrased to protect the anonymity of the folks who did * the reverse engineering, in case they want to remain anonymous. */ int seed1, seed2; /* 7-byte record contains the time of day, just for extra scrambling */ struct { char year, month, day, hour, minutes, seconds, weed; } tod; int rand_num() { int strangeness; /* update seed1, seed2 */ seed1 = seed1 * 2; seed2 = seed2 * 2; if (seed1 >= 947) seed1 -= 947; if (seed1 >= 941) seed1 -= 941; /* extract a random byte */ strangeness = ((unsigned char *)&tod)[ (seed1+seed2)%7 ]; return (strangeness + seed1 + seed2) & 0xFF; } generate_challenge(uint32 *r, uint32 *s, int conn) { int i; for (i=0; i<4; i++) ((unsigned char *)r)[i] = (rand_num() + conn) & 0xFF; for (i=0; i<4; i++) ((unsigned char *)s)[i] = (rand_num() + conn) & 0xFF; } Each byte of r,s is generated from this simple random number generator. So it's not to hard to write a simple program to exhaustively try all possible starting values for seed1,seed2 and check whether r == s ever. It turns out that there exactly 4 starting values (out of the 889240 possible) which do yield r == s. Actually, it's not too hard to analyze why those four starting values work. A sufficient requirement is that seed1+seed2 be the same at each point in the first 'for' loop of generate_challenge() as in the second 'for' loop. For example, when initially seed1 = 943 (= -4 mod 947) seed2 = 4 (mod 941) then we get as output for the 4 bytes of r and 4 bytes of s: i seed1 seed2 seed1+seed2 0 939=-8 8 947 1 931=-16 16 947 2 915=-32 32 947 3 883=-64 64 947 [now to generate s: ] 0 819=-128 128 947 ... So you see that each byte of r and s should be ( ((unsigned char *)&tod)[2] + 947 + c ) & 0xFF where c is the same for all 8 bytes generated. Thus this starting value of seed1,seed2 causes r == s. It turns out that there are 4 such starting values which cause the server to generate a challenge of the form r == s: that is, about 1 in 220,000 challenges should have this weak exploitable form. That is far too many, far more than you'd expect by chance if you had a good random number generator. An attacker should be able to get in, without knowing the password, if he just tries a few hundred thousand times in rapid succesion. I should add a disclaimer. I don't know very much about Netware; I based my examination on the code I was sent, which may or may not accurately reflect what real Netware servers are doing; and I have no idea whether this behavior really happens. (I also don't know if it is Netware 3.x-specific.) What I'm saying is that I think bad challenges may occur awfully frequently. I can't test that prediction myself, unfortunately, since I don't have access to a Netware server. Is anyone out there interested in testing my hypothesis? Comments & criticisms are welcome. -- Dave Wagner