1 a812ae4b 2004-12-27 devnull // PAK is an encrypted key exchange protocol designed by Philip MacKenzie et al.
2 a812ae4b 2004-12-27 devnull // It is patented and use outside Plan 9 requires you get a license.
3 a812ae4b 2004-12-27 devnull // (All other EKE protocols are patented as well, by Lucent or others.)
4 a812ae4b 2004-12-27 devnull #include <u.h>
5 a812ae4b 2004-12-27 devnull #include <libc.h>
6 a812ae4b 2004-12-27 devnull #include <mp.h>
7 a812ae4b 2004-12-27 devnull #include <libsec.h>
8 a812ae4b 2004-12-27 devnull #include "SConn.h"
9 a812ae4b 2004-12-27 devnull #include "secstore.h"
11 a812ae4b 2004-12-27 devnull extern int verbose;
13 a812ae4b 2004-12-27 devnull char VERSION[] = "secstore";
14 a812ae4b 2004-12-27 devnull static char *feedback[] = {"alpha","bravo","charlie","delta","echo","foxtrot","golf","hotel"};
16 a812ae4b 2004-12-27 devnull typedef struct PAKparams{
17 a812ae4b 2004-12-27 devnull mpint *q, *p, *r, *g;
18 a812ae4b 2004-12-27 devnull } PAKparams;
20 a812ae4b 2004-12-27 devnull static PAKparams *pak;
22 a812ae4b 2004-12-27 devnull // from seed EB7B6E35F7CD37B511D96C67D6688CC4DD440E1E
23 a812ae4b 2004-12-27 devnull static void
24 a812ae4b 2004-12-27 devnull initPAKparams(void)
28 a812ae4b 2004-12-27 devnull pak = (PAKparams*)emalloc(sizeof(*pak));
29 a812ae4b 2004-12-27 devnull pak->q = strtomp("E0F0EF284E10796C5A2A511E94748BA03C795C13", nil, 16, nil);
30 a812ae4b 2004-12-27 devnull pak->p = strtomp("C41CFBE4D4846F67A3DF7DE9921A49D3B42DC33728427AB159CEC8CBB"
31 a812ae4b 2004-12-27 devnull "DB12B5F0C244F1A734AEB9840804EA3C25036AD1B61AFF3ABBC247CD4B384224567A86"
32 a812ae4b 2004-12-27 devnull "3A6F020E7EE9795554BCD08ABAD7321AF27E1E92E3DB1C6E7E94FAAE590AE9C48F96D9"
33 a812ae4b 2004-12-27 devnull "3D178E809401ABE8A534A1EC44359733475A36A70C7B425125062B1142D",
34 a812ae4b 2004-12-27 devnull nil, 16, nil);
35 a812ae4b 2004-12-27 devnull pak->r = strtomp("DF310F4E54A5FEC5D86D3E14863921E834113E060F90052AD332B3241"
36 a812ae4b 2004-12-27 devnull "CEF2497EFA0303D6344F7C819691A0F9C4A773815AF8EAECFB7EC1D98F039F17A32A7E"
37 a812ae4b 2004-12-27 devnull "887D97251A927D093F44A55577F4D70444AEBD06B9B45695EC23962B175F266895C67D"
38 a812ae4b 2004-12-27 devnull "21C4656848614D888A4", nil, 16, nil);
39 a812ae4b 2004-12-27 devnull pak->g = strtomp("2F1C308DC46B9A44B52DF7DACCE1208CCEF72F69C743ADD4D23271734"
40 a812ae4b 2004-12-27 devnull "44ED6E65E074694246E07F9FD4AE26E0FDDD9F54F813C40CB9BCD4338EA6F242AB94CD"
41 a812ae4b 2004-12-27 devnull "410E676C290368A16B1A3594877437E516C53A6EEE5493A038A017E955E218E7819734"
42 a812ae4b 2004-12-27 devnull "E3E2A6E0BAE08B14258F8C03CC1B30E0DDADFCF7CEDF0727684D3D255F1",
43 a812ae4b 2004-12-27 devnull nil, 16, nil);
46 a812ae4b 2004-12-27 devnull // H = (sha(ver,C,sha(passphrase)))^r mod p,
47 a812ae4b 2004-12-27 devnull // a hash function expensive to attack by brute force.
48 a812ae4b 2004-12-27 devnull static void
49 a812ae4b 2004-12-27 devnull longhash(char *ver, char *C, uchar *passwd, mpint *H)
51 a812ae4b 2004-12-27 devnull uchar *Cp;
52 a812ae4b 2004-12-27 devnull int i, n, nver, nC;
53 a812ae4b 2004-12-27 devnull uchar buf[140], key[1];
55 a812ae4b 2004-12-27 devnull nver = strlen(ver);
56 a812ae4b 2004-12-27 devnull nC = strlen(C);
57 a812ae4b 2004-12-27 devnull n = nver + nC + SHA1dlen;
58 a812ae4b 2004-12-27 devnull Cp = (uchar*)emalloc(n);
59 a812ae4b 2004-12-27 devnull memmove(Cp, ver, nver);
60 a812ae4b 2004-12-27 devnull memmove(Cp+nver, C, nC);
61 a812ae4b 2004-12-27 devnull memmove(Cp+nver+nC, passwd, SHA1dlen);
62 a812ae4b 2004-12-27 devnull for(i = 0; i < 7; i++){
63 a812ae4b 2004-12-27 devnull key[0] = 'A'+i;
64 a812ae4b 2004-12-27 devnull hmac_sha1(Cp, n, key, sizeof key, buf+i*SHA1dlen, nil);
66 a812ae4b 2004-12-27 devnull memset(Cp, 0, n);
67 a812ae4b 2004-12-27 devnull free(Cp);
68 a812ae4b 2004-12-27 devnull betomp(buf, sizeof buf, H);
69 a812ae4b 2004-12-27 devnull mpmod(H, pak->p, H);
70 a812ae4b 2004-12-27 devnull mpexp(H, pak->r, pak->p, H);
73 a812ae4b 2004-12-27 devnull // Hi = H^-1 mod p
75 a812ae4b 2004-12-27 devnull PAK_Hi(char *C, char *passphrase, mpint *H, mpint *Hi)
77 a812ae4b 2004-12-27 devnull uchar passhash[SHA1dlen];
79 a812ae4b 2004-12-27 devnull sha1((uchar *)passphrase, strlen(passphrase), passhash, nil);
80 a812ae4b 2004-12-27 devnull initPAKparams();
81 a812ae4b 2004-12-27 devnull longhash(VERSION, C, passhash, H);
82 a812ae4b 2004-12-27 devnull mpinvert(H, pak->p, Hi);
83 a812ae4b 2004-12-27 devnull return mptoa(Hi, 64, nil, 0);
86 a812ae4b 2004-12-27 devnull // another, faster, hash function for each party to
87 a812ae4b 2004-12-27 devnull // confirm that the other has the right secrets.
88 a812ae4b 2004-12-27 devnull static void
89 a812ae4b 2004-12-27 devnull shorthash(char *mess, char *C, char *S, char *m, char *mu, char *sigma, char *Hi, uchar *digest)
91 a812ae4b 2004-12-27 devnull SHA1state *state;
93 a812ae4b 2004-12-27 devnull state = sha1((uchar*)mess, strlen(mess), 0, 0);
94 a812ae4b 2004-12-27 devnull state = sha1((uchar*)C, strlen(C), 0, state);
95 a812ae4b 2004-12-27 devnull state = sha1((uchar*)S, strlen(S), 0, state);
96 a812ae4b 2004-12-27 devnull state = sha1((uchar*)m, strlen(m), 0, state);
97 a812ae4b 2004-12-27 devnull state = sha1((uchar*)mu, strlen(mu), 0, state);
98 a812ae4b 2004-12-27 devnull state = sha1((uchar*)sigma, strlen(sigma), 0, state);
99 a812ae4b 2004-12-27 devnull state = sha1((uchar*)Hi, strlen(Hi), 0, state);
100 a812ae4b 2004-12-27 devnull state = sha1((uchar*)mess, strlen(mess), 0, state);
101 a812ae4b 2004-12-27 devnull state = sha1((uchar*)C, strlen(C), 0, state);
102 a812ae4b 2004-12-27 devnull state = sha1((uchar*)S, strlen(S), 0, state);
103 a812ae4b 2004-12-27 devnull state = sha1((uchar*)m, strlen(m), 0, state);
104 a812ae4b 2004-12-27 devnull state = sha1((uchar*)mu, strlen(mu), 0, state);
105 a812ae4b 2004-12-27 devnull state = sha1((uchar*)sigma, strlen(sigma), 0, state);
106 a812ae4b 2004-12-27 devnull sha1((uchar*)Hi, strlen(Hi), digest, state);
109 a812ae4b 2004-12-27 devnull // On input, conn provides an open channel to the server;
110 a812ae4b 2004-12-27 devnull // C is the name this client calls itself;
111 a812ae4b 2004-12-27 devnull // pass is the user's passphrase
112 a812ae4b 2004-12-27 devnull // On output, session secret has been set in conn
113 a812ae4b 2004-12-27 devnull // (unless return code is negative, which means failure).
114 a812ae4b 2004-12-27 devnull // If pS is not nil, it is set to the (alloc'd) name the server calls itself.
116 a812ae4b 2004-12-27 devnull PAKclient(SConn *conn, char *C, char *pass, char **pS)
118 a812ae4b 2004-12-27 devnull char *mess, *mess2, *eol, *S, *hexmu, *ks, *hexm, *hexsigma = nil, *hexHi;
119 a812ae4b 2004-12-27 devnull char kc[2*SHA1dlen+1];
120 a812ae4b 2004-12-27 devnull uchar digest[SHA1dlen];
121 a812ae4b 2004-12-27 devnull int rc = -1, n;
122 a812ae4b 2004-12-27 devnull mpint *x, *m = mpnew(0), *mu = mpnew(0), *sigma = mpnew(0);
123 a812ae4b 2004-12-27 devnull mpint *H = mpnew(0), *Hi = mpnew(0);
125 a812ae4b 2004-12-27 devnull hexHi = PAK_Hi(C, pass, H, Hi);
126 a812ae4b 2004-12-27 devnull if(verbose)
127 a812ae4b 2004-12-27 devnull fprint(2,"%s\n", feedback[H->p[0]&0x7]); // provide a clue to catch typos
129 a812ae4b 2004-12-27 devnull // random 1<=x<=q-1; send C, m=g**x H
130 a812ae4b 2004-12-27 devnull x = mprand(240, genrandom, nil);
131 a812ae4b 2004-12-27 devnull mpmod(x, pak->q, x);
132 a812ae4b 2004-12-27 devnull if(mpcmp(x, mpzero) == 0)
133 a812ae4b 2004-12-27 devnull mpassign(mpone, x);
134 a812ae4b 2004-12-27 devnull mpexp(pak->g, x, pak->p, m);
135 a812ae4b 2004-12-27 devnull mpmul(m, H, m);
136 a812ae4b 2004-12-27 devnull mpmod(m, pak->p, m);
137 a812ae4b 2004-12-27 devnull hexm = mptoa(m, 64, nil, 0);
138 a812ae4b 2004-12-27 devnull mess = (char*)emalloc(2*Maxmsg+2);
139 a812ae4b 2004-12-27 devnull mess2 = mess+Maxmsg+1;
140 a812ae4b 2004-12-27 devnull snprint(mess, Maxmsg, "%s\tPAK\nC=%s\nm=%s\n", VERSION, C, hexm);
141 a812ae4b 2004-12-27 devnull conn->write(conn, (uchar*)mess, strlen(mess));
143 a812ae4b 2004-12-27 devnull // recv g**y, S, check hash1(g**xy)
144 a812ae4b 2004-12-27 devnull if(readstr(conn, mess) < 0){
145 a812ae4b 2004-12-27 devnull fprint(2, "error: %s\n", mess);
146 a812ae4b 2004-12-27 devnull writerr(conn, "couldn't read g**y");
147 a812ae4b 2004-12-27 devnull goto done;
149 a812ae4b 2004-12-27 devnull eol = strchr(mess, '\n');
150 a812ae4b 2004-12-27 devnull if(strncmp("mu=", mess, 3) != 0 || !eol || strncmp("\nk=", eol, 3) != 0){
151 a812ae4b 2004-12-27 devnull writerr(conn, "verifier syntax error");
152 a812ae4b 2004-12-27 devnull goto done;
154 a812ae4b 2004-12-27 devnull hexmu = mess+3;
155 a812ae4b 2004-12-27 devnull *eol = 0;
156 a812ae4b 2004-12-27 devnull ks = eol+3;
157 a812ae4b 2004-12-27 devnull eol = strchr(ks, '\n');
158 a812ae4b 2004-12-27 devnull if(!eol || strncmp("\nS=", eol, 3) != 0){
159 a812ae4b 2004-12-27 devnull writerr(conn, "verifier syntax error for secstore 1.0");
160 a812ae4b 2004-12-27 devnull goto done;
162 a812ae4b 2004-12-27 devnull *eol = 0;
163 a812ae4b 2004-12-27 devnull S = eol+3;
164 a812ae4b 2004-12-27 devnull eol = strchr(S, '\n');
165 a812ae4b 2004-12-27 devnull if(!eol){
166 a812ae4b 2004-12-27 devnull writerr(conn, "verifier syntax error for secstore 1.0");
167 a812ae4b 2004-12-27 devnull goto done;
169 a812ae4b 2004-12-27 devnull *eol = 0;
171 a812ae4b 2004-12-27 devnull *pS = estrdup(S);
172 a812ae4b 2004-12-27 devnull strtomp(hexmu, nil, 64, mu);
173 a812ae4b 2004-12-27 devnull mpexp(mu, x, pak->p, sigma);
174 a812ae4b 2004-12-27 devnull hexsigma = mptoa(sigma, 64, nil, 0);
175 a812ae4b 2004-12-27 devnull shorthash("server", C, S, hexm, hexmu, hexsigma, hexHi, digest);
176 a812ae4b 2004-12-27 devnull enc64(kc, sizeof kc, digest, SHA1dlen);
177 a812ae4b 2004-12-27 devnull if(strcmp(ks, kc) != 0){
178 a812ae4b 2004-12-27 devnull writerr(conn, "verifier didn't match");
179 a812ae4b 2004-12-27 devnull goto done;
182 a812ae4b 2004-12-27 devnull // send hash2(g**xy)
183 a812ae4b 2004-12-27 devnull shorthash("client", C, S, hexm, hexmu, hexsigma, hexHi, digest);
184 a812ae4b 2004-12-27 devnull enc64(kc, sizeof kc, digest, SHA1dlen);
185 a812ae4b 2004-12-27 devnull snprint(mess2, Maxmsg, "k'=%s\n", kc);
186 a812ae4b 2004-12-27 devnull conn->write(conn, (uchar*)mess2, strlen(mess2));
188 a812ae4b 2004-12-27 devnull // set session key
189 a812ae4b 2004-12-27 devnull shorthash("session", C, S, hexm, hexmu, hexsigma, hexHi, digest);
190 a812ae4b 2004-12-27 devnull memset(hexsigma, 0, strlen(hexsigma));
191 a812ae4b 2004-12-27 devnull n = conn->secret(conn, digest, 0);
192 a812ae4b 2004-12-27 devnull memset(digest, 0, SHA1dlen);
193 a812ae4b 2004-12-27 devnull if(n < 0){
194 a812ae4b 2004-12-27 devnull writerr(conn, "can't set secret");
195 a812ae4b 2004-12-27 devnull goto done;
200 a812ae4b 2004-12-27 devnull mpfree(x);
201 a812ae4b 2004-12-27 devnull mpfree(sigma);
202 a812ae4b 2004-12-27 devnull mpfree(mu);
203 a812ae4b 2004-12-27 devnull mpfree(m);
204 a812ae4b 2004-12-27 devnull mpfree(Hi);
205 a812ae4b 2004-12-27 devnull mpfree(H);
206 a812ae4b 2004-12-27 devnull free(hexsigma);
207 a812ae4b 2004-12-27 devnull free(hexHi);
208 a812ae4b 2004-12-27 devnull free(hexm);
209 a812ae4b 2004-12-27 devnull free(mess);
210 a812ae4b 2004-12-27 devnull return rc;
213 a812ae4b 2004-12-27 devnull // On input,
214 a812ae4b 2004-12-27 devnull // mess contains first message;
215 a812ae4b 2004-12-27 devnull // name is name this server should call itself.
216 a812ae4b 2004-12-27 devnull // On output, session secret has been set in conn;
217 a812ae4b 2004-12-27 devnull // if pw!=nil, then *pw points to PW struct for authenticated user.
218 a812ae4b 2004-12-27 devnull // returns -1 if error
220 a812ae4b 2004-12-27 devnull PAKserver(SConn *conn, char *S, char *mess, PW **pwp)
222 a812ae4b 2004-12-27 devnull int rc = -1, n;
223 a812ae4b 2004-12-27 devnull char mess2[Maxmsg+1], *eol;
224 a812ae4b 2004-12-27 devnull char *C, ks[41], *kc, *hexm, *hexmu = nil, *hexsigma = nil, *hexHi = nil;
225 a812ae4b 2004-12-27 devnull uchar digest[SHA1dlen];
226 a812ae4b 2004-12-27 devnull mpint *H = mpnew(0), *Hi = mpnew(0);
227 a812ae4b 2004-12-27 devnull mpint *y = nil, *m = mpnew(0), *mu = mpnew(0), *sigma = mpnew(0);
228 a812ae4b 2004-12-27 devnull PW *pw = nil;
230 a812ae4b 2004-12-27 devnull // secstore version and algorithm
231 a812ae4b 2004-12-27 devnull snprint(mess2,Maxmsg,"%s\tPAK\n", VERSION);
232 a812ae4b 2004-12-27 devnull n = strlen(mess2);
233 a812ae4b 2004-12-27 devnull if(strncmp(mess,mess2,n) != 0){
234 a812ae4b 2004-12-27 devnull writerr(conn, "protocol should start with ver alg");
235 a812ae4b 2004-12-27 devnull return -1;
237 a812ae4b 2004-12-27 devnull mess += n;
238 a812ae4b 2004-12-27 devnull initPAKparams();
240 a812ae4b 2004-12-27 devnull // parse first message into C, m
241 a812ae4b 2004-12-27 devnull eol = strchr(mess, '\n');
242 a812ae4b 2004-12-27 devnull if(strncmp("C=", mess, 2) != 0 || !eol){
243 a812ae4b 2004-12-27 devnull fprint(2,"mess[1]=%s\n", mess);
244 a812ae4b 2004-12-27 devnull writerr(conn, "PAK version mismatch");
245 a812ae4b 2004-12-27 devnull goto done;
247 a812ae4b 2004-12-27 devnull C = mess+2;
248 a812ae4b 2004-12-27 devnull *eol = 0;
249 a812ae4b 2004-12-27 devnull hexm = eol+3;
250 a812ae4b 2004-12-27 devnull eol = strchr(hexm, '\n');
251 a812ae4b 2004-12-27 devnull if(strncmp("m=", hexm-2, 2) != 0 || !eol){
252 a812ae4b 2004-12-27 devnull writerr(conn, "PAK version mismatch");
253 a812ae4b 2004-12-27 devnull goto done;
255 a812ae4b 2004-12-27 devnull *eol = 0;
256 a812ae4b 2004-12-27 devnull strtomp(hexm, nil, 64, m);
257 a812ae4b 2004-12-27 devnull mpmod(m, pak->p, m);
259 a812ae4b 2004-12-27 devnull // lookup client
260 a812ae4b 2004-12-27 devnull if((pw = getPW(C,0)) == nil) {
261 a812ae4b 2004-12-27 devnull snprint(mess2, sizeof mess2, "%r");
262 a812ae4b 2004-12-27 devnull writerr(conn, mess2);
263 a812ae4b 2004-12-27 devnull goto done;
265 a812ae4b 2004-12-27 devnull if(mpcmp(m, mpzero) == 0) {
266 a812ae4b 2004-12-27 devnull writerr(conn, "account exists");
267 a812ae4b 2004-12-27 devnull freePW(pw);
268 a812ae4b 2004-12-27 devnull pw = nil;
269 a812ae4b 2004-12-27 devnull goto done;
271 a812ae4b 2004-12-27 devnull hexHi = mptoa(pw->Hi, 64, nil, 0);
273 a812ae4b 2004-12-27 devnull // random y, mu=g**y, sigma=g**xy
274 a812ae4b 2004-12-27 devnull y = mprand(240, genrandom, nil);
275 a812ae4b 2004-12-27 devnull mpmod(y, pak->q, y);
276 a812ae4b 2004-12-27 devnull if(mpcmp(y, mpzero) == 0){
277 a812ae4b 2004-12-27 devnull mpassign(mpone, y);
279 a812ae4b 2004-12-27 devnull mpexp(pak->g, y, pak->p, mu);
280 a812ae4b 2004-12-27 devnull mpmul(m, pw->Hi, m);
281 a812ae4b 2004-12-27 devnull mpmod(m, pak->p, m);
282 a812ae4b 2004-12-27 devnull mpexp(m, y, pak->p, sigma);
284 a812ae4b 2004-12-27 devnull // send g**y, hash1(g**xy)
285 a812ae4b 2004-12-27 devnull hexmu = mptoa(mu, 64, nil, 0);
286 a812ae4b 2004-12-27 devnull hexsigma = mptoa(sigma, 64, nil, 0);
287 a812ae4b 2004-12-27 devnull shorthash("server", C, S, hexm, hexmu, hexsigma, hexHi, digest);
288 a812ae4b 2004-12-27 devnull enc64(ks, sizeof ks, digest, SHA1dlen);
289 a812ae4b 2004-12-27 devnull snprint(mess2, sizeof mess2, "mu=%s\nk=%s\nS=%s\n", hexmu, ks, S);
290 a812ae4b 2004-12-27 devnull conn->write(conn, (uchar*)mess2, strlen(mess2));
292 a812ae4b 2004-12-27 devnull // recv hash2(g**xy)
293 a812ae4b 2004-12-27 devnull if(readstr(conn, mess2) < 0){
294 a812ae4b 2004-12-27 devnull writerr(conn, "couldn't read verifier");
295 a812ae4b 2004-12-27 devnull goto done;
297 a812ae4b 2004-12-27 devnull eol = strchr(mess2, '\n');
298 a812ae4b 2004-12-27 devnull if(strncmp("k'=", mess2, 3) != 0 || !eol){
299 a812ae4b 2004-12-27 devnull writerr(conn, "verifier syntax error");
300 a812ae4b 2004-12-27 devnull goto done;
302 a812ae4b 2004-12-27 devnull kc = mess2+3;
303 a812ae4b 2004-12-27 devnull *eol = 0;
304 a812ae4b 2004-12-27 devnull shorthash("client", C, S, hexm, hexmu, hexsigma, hexHi, digest);
305 a812ae4b 2004-12-27 devnull enc64(ks, sizeof ks, digest, SHA1dlen);
306 a812ae4b 2004-12-27 devnull if(strcmp(ks, kc) != 0) {
307 a812ae4b 2004-12-27 devnull rc = -2;
308 a812ae4b 2004-12-27 devnull goto done;
311 a812ae4b 2004-12-27 devnull // set session key
312 a812ae4b 2004-12-27 devnull shorthash("session", C, S, hexm, hexmu, hexsigma, hexHi, digest);
313 a812ae4b 2004-12-27 devnull n = conn->secret(conn, digest, 1);
314 a812ae4b 2004-12-27 devnull if(n < 0){
315 a812ae4b 2004-12-27 devnull writerr(conn, "can't set secret");
316 a812ae4b 2004-12-27 devnull goto done;
321 a812ae4b 2004-12-27 devnull if(rc<0 && pw){
322 a812ae4b 2004-12-27 devnull pw->failed++;
323 a812ae4b 2004-12-27 devnull putPW(pw);
325 a812ae4b 2004-12-27 devnull if(rc==0 && pw && pw->failed>0){
326 a812ae4b 2004-12-27 devnull pw->failed = 0;
327 a812ae4b 2004-12-27 devnull putPW(pw);
330 a812ae4b 2004-12-27 devnull *pwp = pw;
332 a812ae4b 2004-12-27 devnull freePW(pw);
333 a812ae4b 2004-12-27 devnull free(hexsigma);
334 a812ae4b 2004-12-27 devnull free(hexHi);
335 a812ae4b 2004-12-27 devnull free(hexmu);
336 a812ae4b 2004-12-27 devnull mpfree(y);
337 a812ae4b 2004-12-27 devnull mpfree(sigma);
338 a812ae4b 2004-12-27 devnull mpfree(mu);
339 a812ae4b 2004-12-27 devnull mpfree(m);
340 a812ae4b 2004-12-27 devnull mpfree(Hi);
341 a812ae4b 2004-12-27 devnull mpfree(H);
342 a812ae4b 2004-12-27 devnull return rc;
