Also,
http://www.usenix.org/publications/library/proceedings/security95/full_paper
s/adamson.txt
A single login for Kerberos and Netware/NDS. Source might be available.
-----Original Message-----
X-Loop: openpgp.net
From: Anonymous Bastard [mailto:[EMAIL PROTECTED]]
Sent: Tuesday, April 18, 2000 12:04 PM
To: [EMAIL PROTECTED]
Subject: Novell NDS Authentication Protocol
A while back, I was at a conference, expecting to be totally bored.
Imagine my surprise, when the guy next to me turned out to be a former
Novell coder. He seemed really hot on NDS, and willing to talk about the
secret parts, if I promised to keep his name anonymous. I took a lot of
notes, and filled in some details later. Here's what I figured out about
the authentication system. Enjoy.
BASIC ALGORITHMS
===== ==========
H(p,i) NetWare Password Hash
p: password
i: NetWare userID (4 bytes)
They use the same old algorithm that hashes together the user's
password and ID, generating a 16-byte hash.
K(I,k) Keyed Hash
I: initialization vector (length in bytes l(I))
k: key (length in bytes l(k))
P: permutation of [0 ... 255]:
189, 86, 234, 242, 162, 241, 172, 42, 176, 147, 209, 156,
27,
51, 253, 208, 48, 4, 182, 220, 125, 223, 50, 75, 247, 203,
69,
155, 49, 187, 33, 90, 65, 159, 225, 217, 74, 77, 158, 218,
160, 104, 44, 195, 39, 95, 128, 54, 62, 238, 251, 149, 26,
254, 206, 168, 52, 169, 19, 240, 166, 63, 216, 12, 120, 36,
175, 35, 82, 193, 103, 23, 245, 102, 144, 231, 232, 7, 184,
96, 72, 230, 30, 83, 243, 146, 164, 114, 140, 8, 21, 110,
134,
0, 132, 250, 244, 127, 138, 66, 25, 246, 219, 205, 20, 141,
80, 18, 186, 60, 6, 78, 236, 179, 53, 17, 161, 136, 142, 43,
148, 153, 183, 113, 116, 211, 228, 191, 58, 222, 150, 14,
188,
10, 237, 119, 252, 55, 107, 3, 121, 137, 98, 198, 215, 192,
210, 124, 106, 139, 34, 163, 91, 5, 93, 2, 117, 213, 97,
227,
24, 143, 85, 81, 173, 31, 11, 94, 133, 229, 194, 87, 99,
202,
61, 108, 180, 197, 204, 112, 178, 145, 89, 13, 71, 32, 200,
79, 88, 224, 1, 226, 22, 56, 196, 111, 59, 15, 101, 70, 190,
126, 45, 123, 130, 249, 64, 181, 29, 115, 248, 235, 38, 199,
135, 151, 37, 84, 177, 40, 170, 152, 157, 165, 100, 109,
122,
212, 16, 129, 68, 239, 73, 214, 174, 46, 221, 118, 92, 47,
167, 28, 201, 9, 105, 154, 131, 207, 41, 57, 185, 233, 76,
255, 67, 171
The result H has the same lenght as I and is computed like this:
Set H = I
For each key byte k[i] (i = 0, 1, ... l(k)-1)
set H[i mod l(I)] = k[i] XOR P[H[i mod l(I)] XOR
H[i+1 mod l(I)]]
Rotate H left (l(k) mod l(I)) bytes. (H[l(k) mod l(I)] is moved to
H[0], H[l(k)+1 mod l(I)] is moved to H[1], etc.)
C(l,m) Checksum
l: length of result (in bytes)
m: message
The checksum is a keyed hash, using the message as key and
initialization vector of all 0's:
C(l,m) = K(0(length l),m)
M(m) Message Digest
m: message
Generate a 16 byte message digest. The algorithm differs from MD2
(RFC
1319) in two ways:
1...The permutation listed above for K(I,k) replaces the PI_SUBST
permutation from RFC 1319.
2...MD2Transform is modified slightly. Here's a patch to apply to
RFC
1319:
===============================================
***************
*** 553,560 ****
t = 0;
for (i = 0; i < 18; i++) {
for (j = 0; j < 48; j++)
! t = x[j] ^= PI_SUBST[t];
! t = (t + i) & 0xff;
}
--- 553,559 ----
t = 0;
for (i = 0; i < 18; i++) {
for (j = 0; j < 48; j++)
! t = x[j] ^= PI_SUBST[(t+48-j)&0xff];
}
===============================================
E(m,k) and D(m,k) Block Cipher Encryption and Decryption
m: message (lenght in bytes always a multiple of 8)
k: key
They use RC2 (RFC 2268) in CBC mode. The key k isn't used directly
in
RC2, it's first hashed to an 8 byte (64 bit) effective key, e:
Set e = 0 (length 8)
Repeat 10 times:
set e = K(e,k)
NDS AUTHENTICATION
=== ==============
NDS Authentication takes place in two phases, called "login" and
"authentication." During login, the client attaches to an NDS server,
obtains the user's RSA private key, and builds blocks called the
"credential" and the "signiture." During authentication, the client
attaches to a desired fileserver and builds a block called the "proof."
The credential and proof are transmitted on the network, but the signiture
is nown only to the client. The proof represents a Gillou-Quisquater zero
knowledge proof that the client knows the signiture (and the user's
private key).
Login Phase
1. The client obtains PU, the user's password.
2. The client attaches to the NDS server and obtains some info:
NU, the user's full NDS name (e.g. CN=John.O=Megacorp), in Unicode
IU, the user's NDS entryID
3. The client sends "Begin Login" containing IU. The server replies,
sending a 4 byte random value, RN1.
4. The client builds DU1:
11 (1 byte, fill character)
RU1 (28 bytes, random)
11 11 ... 11 (11 bytes)
C(5,m) (5 bytes, checksum of prev 2 fields)
C(2,m) (2 bytes, checksum of prev 4 fields)
RU2 (5 bytes, random)
5. The client obtains the server's RSA public key: modulus MN and
exponent EN. The public key is contained in the "Public Key" attribute for
the server: it contains a tagged data structure with these items:
TAG VALUE
=== =====
BL l(MN), length in bits
NN MN
EN EN
MA 8 byte checksum of all preceeding tagged fields
6. The client encrypts DU1 with the server's public key MN/EN. (DU1 is
viewed as a multibyte number, LSB first.) The result is DU2, a block of
length ceil(l(MN)/8).
7. The client builds DU3:
RN1 (4 bytes)
7 7 ... 7 (7 bytes of fill)
C(5,m) (5 bytes, checksum of prev fields)
8. The client builds DU4:
1 0 0 0 1 0 6 0 (8 bytes)
16 0 (2 bytes, length of ciphertext)
4 0 (2 bytes)
E(DU3,H(PU,IU)) (16 bytes)
9. The client builds DU5:
RU3 (4 bytes, random)
0 4 0 0 (4 bytes, length of next field)
RU4 (1024 bytes, random)
28 0 0 0 (4 bytes, length of DU4)
DU4 (28 bytes)
3 3 3 (3 bytes of fill, making total length a
multiple of 8)
C(5,m) (5 bytes, checksum of prev fields)
10. The client sends "Finish Login" containing:
IU (4 bytes)
length (4 bytes, length of following data)
1 0 0 0 9 0 2 0 (8 bytes)
length (4 bytes, length of following data)
length (4 bytes, ceil(l(MN)/8)+12)
1 0 0 0 1 0 9 0 (8 bytes)
length (2 bytes, ceil(l(MN)/8))
length (2 bytes, 2*ceil(l(MN)/32))
DU2 (ceil(l(MN)/8) bytes)
pad (pad to 4 byte alignment)
length (4 bytes, length of following data)
1 0 0 0 1 0 6 0 (8 bytes)
length (2 bytes, 1072)
length (2 bytes, 1064)
E(DU5,RU1) (1072 bytes)
11. The NDS server validates the login: it decrypts DU2, verifies the
checksums, and extracts RU1. It uses RU1 to decrypt the 1072 byte block,
obtaining DU5. It verifies the checksum and extracts RU3, RU4, and DU4. It
decrypts the 16 byte ciphertext from DU4, obtaining DU3. In DU3, it
verifies the checksum and RN1.
12. The server prepares the user's RSA private key for transmission. The
user's private key (KU) is a tagged data structure containing:
TAG VALUE
=== =====
BL l(MU), length in bits of the modulus
NN MU, public key modulus
EN EU, public key exponent
PN first prime factor of MU
QN second prime factor of MU
DP private key exponent mod (PN-1)
DQ private key exponent mod (QN-1)
CR private key helper value, (QN^-1) mod PN
MA 8 byte checksum of all preceeding tagged fields
The NDS tree doesn't contain KU in this form: KU is first inserted into a
block DN1:
KU (variable length)
fill (1 to 8 bytes, making total length a
multiple of 8)
C(5,m) (5 bytes, checksum of prev fields)
and then a block DN2 is built:
1 0 0 0 1 0 6 0 (8 bytes)
length (2 bytes, length of DN1)
length (2 bytes, length of KU)
E(DN1,H(PU,IU)) (variable length)
The NDS tree contains the user's private key in this form.
13. The server XORs DN2 with an equal number of bytes from RU4, resulting
in a block DN3 the same size as DN2.
14. The server builds block DN4:
RU3 (4 bytes)
length (4 bytes, length of DN3)
DN3 (variable length)
fill (1 to 8 bytes, making total length a
multiple of 8)
C(5,m) (5 bytes, checksum of prev fields)
15. The server sends "Finish Login" reply, containing this information:
DN5 (8 bytes, timestamp and other credential
data)
length (4 bytes, length of following data)
1 0 0 0 1 0 6 0 (8 bytes)
length (2 bytes, length of DN4)
length (2 bytes, length of DN3 + 8)
E(DN4,DU4) (variable length)
16. The client validates the response: it decrypts the last field,
obtaining DN4. It verifies the checksum and RU3, and extracts DN3. It XORs
with RU4, obtaining DN2, and decrypts the last field in DN2 to obtain DN1.
It verifies the checksum and extracts KU.
17. The client builds the user's credential CU:
1 0 0 0 6 0 (6 bytes)
DN5 (8 bytes)
RU5 (4 bytes, random)
0 0 (2 bytes)
length (2 bytes, length of NU)
NU (variable length)
18. The client computes the message digest M(CU), then encyrpts it with
the user's private key. The result is the signiture, SU, a block of length
ceil(l(MU)/8).
Authentication Phase
1. The client obtains some info:
IS, the fileserver's NDS entryID
MS/ES, the fileserver's RSA public key modulus/exponent
2. The client attached to the fileserver and sends "Begin Authentication"
containing:
RU6 (4 bytes, random)
3. The server builds block DS1:
11 (1 byte, fill character)
RS1 (28 bytes, random)
11 11 ... 11 (11 bytes)
C(5,m) (5 bytes, checksum of prev 2 fields)
C(2,m) (2 bytes, checksum of prev 4 fields)
RS2 (5 bytes, random)
4. The server encrypts DS1 with the server's private key. The result is a
block DS2 of length ceil(l(MS)/8).
5. The server builds DS3:
RU6 (4 bytes)
7 7 ... 7 (7 bytes)
C(5,m) (5 bytes, checksum of prev fields)
6. The server sends "Begin Authentication" reply, including:
RS3 (4 bytes, random)
length (4 bytes, length of following data)
1 0 0 0 9 0 2 0 (8 bytes)
length (4 bytes, length of following data)
length (4 bytes, ceil(l(MS)/8)+12)
1 0 0 0 1 0 10 0 (8 bytes)
length (2 bytes, ceil(l(MS)/8))
length (2 bytes, 2*ceil(l(MS)/32))
DS2 (ceil(l(MS)/8) bytes)
pad (pad to 4 byte alignment)
length (4 bytes, length of following data)
1 0 0 0 1 0 6 0 (8 bytes)
length (2 bytes, 16)
length (2 bytes, 4)
E(DS3,RS1) (16 bytes)
7. The client decrypts DS2 with key MS/ES, obtaining DS1. It verifies the
checksums and extracts RS1. It decrypts the last field of the reply,
obtaining DS3. It verifies the checksum and RU6.
8. The client chooses 3 random numbers, RU7, RU8, and RU9, less than MU.
These are blocks of length ceil(l(MU)/8).
9. The client encrypts each of RU7, RU8, RU9 with MU/EU. The results are
DU6, DU7, and DU8, more blocks of length ceil(l(MU)/8).
10. The client builds block DU9:
0 0 0 0 (4 bytes)
60 0 0 0 (4 bytes)
RS3 (4 bytes)
length (4 bytes, length of CU)
CU (variable length)
DU6 (ceil(l(MU)/8) bytes)
0 ... 0 (fill with 0 to 4 byte alignment)
DU7 (ceil(l(MU)/8) bytes)
0 ... 0 (fill with 0 to 4 byte alignment)
DU8 (ceil(l(MU)/8) bytes)
0 ... 0 (fill with 0 to 4 byte alignment)
11. The client computes M(DU9), and uses the first 3 pairs of bytes as
exponent values EV1, EV2, and EV3. (The last 10 bytes of the digest are
unused.)
12. The client computes three test values:
TV1 = (RU7*(SU^EV1)) mod MU
TV2 = (RU8*(SU^EV2)) mod MU
TV3 = (RU9*(SU^EV3)) mod MU
The results are blocks of length ceil(l(MU)/8).
13. The client builds the proof structure PRU:
1 0 0 0 8 0 16 0 (8 bytes)
3 0 (2 bytes, number of test values)
length (2 bytes, 12*ceil(l(MU)/32))
DU6 (ceil(l(MU)/8) bytes)
0 ... 0 (fill with 0 to 4 byte alignment)
DU7 (ceil(l(MU)/8) bytes)
0 ... 0 (fill with 0 to 4 byte alignment)
DU8 (ceil(l(MU)/8) bytes)
0 ... 0 (fill with 0 to 4 byte alignment)
TV1 (ceil(l(MU)/8) bytes)
0 ... 0 (fill with 0 to 4 byte alignment)
TV2 (ceil(l(MU)/8) bytes)
0 ... 0 (fill with 0 to 4 byte alignment)
TV3 (ceil(l(MU)/8) bytes)
0 ... 0 (fill with 0 to 4 byte alignment)
14. The client send "Finish Authentication" including:
length (4 bytes, length of CU)
CU (variable length)
pad (pad to 4 byte alignment)
lenght (4 bytes, length of PRU)
PRU (variable length)
15. The server validates the credential and proof: reconstruct DU9,
compute M(DU9), extract exponents EV1, EV2, and EV3. Then verify 3
equations:
(TV1^EU) mod MU = (DU6*(M(CU)^EV1)) mod MU
(TV2^EU) mod MU = (DU7*(M(CU)^EV2)) mod MU
(TV3^EU) mod MU = (DU8*(M(CU)^EV3)) mod MU
