~ubuntu-branches/ubuntu/lucid/openssl/lucid-proposed

BN_hex2bn(&params->p, "fd7f53811d75122952df4a9c2eece4e7f611b7523cef4400c31e3f80b6512669455d402251fb593d8d58fabfc5f5ba30f6cb9b556cd7813b801d346ff26660b76b9950a5a49f9fe8047b1022c24fbba9d7feb7c61bf83b57e7c6a8a6150f04fb83f6d3c51ec3023554135a169132f675f3ae2b61d72aeff22203199dd14801c7");

params->q = NULL;

BN_hex2bn(&params->q, "9760508f15230bccb292b982a2eb840bf0581cf5");

params->g = NULL;

BN_hex2bn(&params->g, "f7e1a085d69b3ddecbbcab5c36b857b97994afbbfa3aea82f9574c0b3d0782675159578ebad4594fe67107108180b449167123e84c281613b7cf09328cc8a6e13c167a8b547c8d28e0a3ae1e2bb3a675916ea37f0bfa213562f1fb627a01243bcca4f1bea8519089a883dfe15ae59f06928b665e807b552564014c3bfecf492a");

showbn("p", params->p);

showbn("q", params->q);

showbn("g", params->g);

}

typedef struct

{

BIGNUM *gr; // g^r (r random)

BIGNUM *b; // b = r - x*h, h=hash(g, g^r, g^x, name)

} JPakeZKP;

typedef struct

{

BIGNUM *gx; // g^x

JPakeZKP zkpx; // ZKP(x)

} JPakeStep1;

typedef struct

{

BIGNUM *X; // g^(xa + xc + xd) * xb * s

JPakeZKP zkpxbs; // ZKP(xb * s)

} JPakeStep2;

typedef struct

{

const char *name; // Must be unique

int base; // 1 for Alice, 3 for Bob. Only used for printing stuff.

JPakeStep1 s1c; // Alice's g^x3, ZKP(x3) or Bob's g^x1, ZKP(x1)

JPakeStep1 s1d; // Alice's g^x4, ZKP(x4) or Bob's g^x2, ZKP(x2)

JPakeStep2 s2; // Alice's A, ZKP(x2 * s) or Bob's B, ZKP(x4 * s)

} JPakeUserPublic;

* The user structure. In the definition, (xa, xb, xc, xd) are Alice's

* (x1, x2, x3, x4) or Bob's (x3, x4, x1, x2). If you see what I mean.

typedef struct

{

JPakeUserPublic p;

BIGNUM *secret; // The shared secret

BIGNUM *key; // The calculated (shared) key

BIGNUM *xa; // Alice's x1 or Bob's x3

BIGNUM *xb; // Alice's x2 or Bob's x4

} JPakeUser;

// Generate each party's random numbers. xa is in [0, q), xb is in [1, q).

static void genrand(JPakeUser *user, const JPakeParameters *params)

{

BIGNUM *qm1;

// xa in [0, q)

user->xa = BN_new();

BN_rand_range(user->xa, params->q);

// q-1

qm1 = BN_new();

100

BN_copy(qm1, params->q);

101

BN_sub_word(qm1, 1);

102

103

// ... and xb in [0, q-1)

104

user->xb = BN_new();

105

BN_rand_range(user->xb, qm1);

106

// [1, q)

107

BN_add_word(user->xb, 1);

108

109

// cleanup

110

BN_free(qm1);

111

112

// Show

113

printf("x%d", user->p.base);

114

showbn("", user->xa);

115

printf("x%d", user->p.base+1);

116

showbn("", user->xb);

117

}

118

119

static void hashlength(SHA_CTX *sha, size_t l)

120

{

121

unsigned char b[2];

122

123

assert(l <= 0xffff);

124

b[0] = l >> 8;

125

b[1] = l&0xff;

126

SHA1_Update(sha, b, 2);

127

}

128

129

static void hashstring(SHA_CTX *sha, const char *string)

130

{

131

size_t l = strlen(string);

132

133

hashlength(sha, l);

134

SHA1_Update(sha, string, l);

135

}

136

137

static void hashbn(SHA_CTX *sha, const BIGNUM *bn)

138

{

139

size_t l = BN_num_bytes(bn);

140

unsigned char *bin = alloca(l);

141

142

hashlength(sha, l);

143

BN_bn2bin(bn, bin);

144

SHA1_Update(sha, bin, l);

145

}

146

147

// h=hash(g, g^r, g^x, name)

148

static void zkpHash(BIGNUM *h, const JPakeZKP *zkp, const BIGNUM *gx,

149

const JPakeUserPublic *from, const JPakeParameters *params)

150

{

151

unsigned char md[SHA_DIGEST_LENGTH];

152

SHA_CTX sha;

153

154

// XXX: hash should not allow moving of the boundaries - Java code

155

// is flawed in this respect. Length encoding seems simplest.

156

SHA1_Init(&sha);

157

hashbn(&sha, params->g);

158

hashbn(&sha, zkp->gr);

159

hashbn(&sha, gx);

160

hashstring(&sha, from->name);

161

SHA1_Final(md, &sha);

162

BN_bin2bn(md, SHA_DIGEST_LENGTH, h);

163

}

164

165

// Prove knowledge of x

166

// Note that we don't send g^x because, as it happens, we've always

167

// sent it elsewhere. Also note that because of that, we could avoid

168

// calculating it here, but we don't, for clarity...

169

static void CreateZKP(JPakeZKP *zkp, const BIGNUM *x, const JPakeUser *us,

170

const BIGNUM *zkpg, const JPakeParameters *params,

171

int n, const char *suffix)

172

{

173

BIGNUM *r = BN_new();

174

BIGNUM *gx = BN_new();

175

BIGNUM *h = BN_new();

176

BIGNUM *t = BN_new();

177

178

// r in [0,q)

179

// XXX: Java chooses r in [0, 2^160) - i.e. distribution not uniform

180

BN_rand_range(r, params->q);

181

// g^r

182

zkp->gr = BN_new();

183

BN_mod_exp(zkp->gr, zkpg, r, params->p, params->ctx);

184

// g^x

185

BN_mod_exp(gx, zkpg, x, params->p, params->ctx);

186

187

// h=hash...

188

zkpHash(h, zkp, gx, &us->p, params);

189

190

// b = r - x*h

191

BN_mod_mul(t, x, h, params->q, params->ctx);

192

zkp->b = BN_new();

193

BN_mod_sub(zkp->b, r, t, params->q, params->ctx);

194

195

// show

196

printf(" ZKP(x%d%s)\n", n, suffix);

197

showbn(" zkpg", zkpg);

198

showbn(" g^x", gx);

199

showbn(" g^r", zkp->gr);

200

showbn(" b", zkp->b);

201

202

// cleanup

203

BN_free(t);

204

BN_free(h);

205

BN_free(gx);

206

BN_free(r);

207

}

208

209

static int VerifyZKP(const JPakeZKP *zkp, BIGNUM *gx,

210

const JPakeUserPublic *them, const BIGNUM *zkpg,

211

const JPakeParameters *params, int n, const char *suffix)

212

{

213

BIGNUM *h = BN_new();

214

BIGNUM *t1 = BN_new();

215

BIGNUM *t2 = BN_new();

216

BIGNUM *t3 = BN_new();

217

int ret = 0;

218

219

zkpHash(h, zkp, gx, them, params);

220

221

// t1 = g^b

222

BN_mod_exp(t1, zkpg, zkp->b, params->p, params->ctx);

223

// t2 = (g^x)^h = g^{hx}

224

BN_mod_exp(t2, gx, h, params->p, params->ctx);

225

// t3 = t1 * t2 = g^{hx} * g^b = g^{hx+b} = g^r (allegedly)

226

BN_mod_mul(t3, t1, t2, params->p, params->ctx);

227

228

printf(" ZKP(x%d%s)\n", n, suffix);

229

showbn(" zkpg", zkpg);

230

showbn(" g^r'", t3);

231

232

// verify t3 == g^r

233

if(BN_cmp(t3, zkp->gr) == 0)

234

ret = 1;

235

236

// cleanup

237

BN_free(t3);

238

BN_free(t2);

239

BN_free(t1);

240

BN_free(h);

241

242

if(ret)

243

puts(" OK");

244

else

245

puts(" FAIL");

246

247

return ret;

248

}

249

250

static void sendstep1_substep(JPakeStep1 *s1, const BIGNUM *x,

251

const JPakeUser *us,

252

const JPakeParameters *params, int n)

253

{

254

s1->gx = BN_new();

255

BN_mod_exp(s1->gx, params->g, x, params->p, params->ctx);

256

printf(" g^{x%d}", n);

257

showbn("", s1->gx);

258

259

CreateZKP(&s1->zkpx, x, us, params->g, params, n, "");

260

}

261

262

static void sendstep1(const JPakeUser *us, JPakeUserPublic *them,

263

const JPakeParameters *params)

264

{

265

printf("\n%s sends %s:\n\n", us->p.name, them->name);

266

267

// from's g^xa (which becomes to's g^xc) and ZKP(xa)

268

sendstep1_substep(&them->s1c, us->xa, us, params, us->p.base);

269

// from's g^xb (which becomes to's g^xd) and ZKP(xb)

270

sendstep1_substep(&them->s1d, us->xb, us, params, us->p.base+1);

271

}

272

273

static int verifystep1(const JPakeUser *us, const JPakeUserPublic *them,

274

const JPakeParameters *params)

275

{

276

printf("\n%s verifies %s:\n\n", us->p.name, them->name);

277

278

// verify their ZKP(xc)

279

if(!VerifyZKP(&us->p.s1c.zkpx, us->p.s1c.gx, them, params->g, params,

280

them->base, ""))

281

return 0;

282

283

// verify their ZKP(xd)

284

if(!VerifyZKP(&us->p.s1d.zkpx, us->p.s1d.gx, them, params->g, params,

285

them->base+1, ""))

286

return 0;

287

288

// g^xd != 1

289

printf(" g^{x%d} != 1: ", them->base+1);

290

if(BN_is_one(us->p.s1d.gx))

291

{

292

puts("FAIL");

293

return 0;

294

}

295

puts("OK");

296

297

return 1;

298

}

299

300

static void sendstep2(const JPakeUser *us, JPakeUserPublic *them,

301

const JPakeParameters *params)

302

{

303

BIGNUM *t1 = BN_new();

304

BIGNUM *t2 = BN_new();

305

306

printf("\n%s sends %s:\n\n", us->p.name, them->name);

307

308

// X = g^{(xa + xc + xd) * xb * s}

309

// t1 = g^xa

310

BN_mod_exp(t1, params->g, us->xa, params->p, params->ctx);

311

// t2 = t1 * g^{xc} = g^{xa} * g^{xc} = g^{xa + xc}

312

BN_mod_mul(t2, t1, us->p.s1c.gx, params->p, params->ctx);

313

// t1 = t2 * g^{xd} = g^{xa + xc + xd}

314

BN_mod_mul(t1, t2, us->p.s1d.gx, params->p, params->ctx);

315

// t2 = xb * s

316

BN_mod_mul(t2, us->xb, us->secret, params->q, params->ctx);

317

// X = t1^{t2} = t1^{xb * s} = g^{(xa + xc + xd) * xb * s}

318

them->s2.X = BN_new();

319

BN_mod_exp(them->s2.X, t1, t2, params->p, params->ctx);

320

321

// Show

322

printf(" g^{(x%d + x%d + x%d) * x%d * s)", us->p.base, them->base,

323

them->base+1, us->p.base+1);

324

showbn("", them->s2.X);

325

326

// ZKP(xb * s)

327

// XXX: this is kinda funky, because we're using

328

329

// g' = g^{xa + xc + xd}

330

331

// as the generator, which means X is g'^{xb * s}

332

CreateZKP(&them->s2.zkpxbs, t2, us, t1, params, us->p.base+1, " * s");

333

334

// cleanup

335

BN_free(t1);

336

BN_free(t2);

337

}

338

339

static int verifystep2(const JPakeUser *us, const JPakeUserPublic *them,

340

const JPakeParameters *params)

341

{

342

BIGNUM *t1 = BN_new();

343

BIGNUM *t2 = BN_new();

344

int ret = 0;

345

346

printf("\n%s verifies %s:\n\n", us->p.name, them->name);

347

348

// g' = g^{xc + xa + xb} [from our POV]

349

// t1 = xa + xb

350

BN_mod_add(t1, us->xa, us->xb, params->q, params->ctx);

351

// t2 = g^{t1} = g^{xa+xb}

352

BN_mod_exp(t2, params->g, t1, params->p, params->ctx);

353

// t1 = g^{xc} * t2 = g^{xc + xa + xb}

354

BN_mod_mul(t1, us->p.s1c.gx, t2, params->p, params->ctx);

355

356

if(VerifyZKP(&us->p.s2.zkpxbs, us->p.s2.X, them, t1, params, them->base+1,

357

" * s"))

358

ret = 1;

359

360

// cleanup

361

BN_free(t2);

362

BN_free(t1);

363

364

return ret;

365

}

366

367

static void computekey(JPakeUser *us, const JPakeParameters *params)

368

{

369

BIGNUM *t1 = BN_new();

370

BIGNUM *t2 = BN_new();

371

BIGNUM *t3 = BN_new();

372

373

printf("\n%s calculates the shared key:\n\n", us->p.name);

374

375

// K = (X/g^{xb * xd * s})^{xb}

376

// = (g^{(xc + xa + xb) * xd * s - xb * xd *s})^{xb}

377

// = (g^{(xa + xc) * xd * s})^{xb}

378

// = g^{(xa + xc) * xb * xd * s}

379

// [which is the same regardless of who calculates it]

380

381

// t1 = (g^{xd})^{xb} = g^{xb * xd}

382

BN_mod_exp(t1, us->p.s1d.gx, us->xb, params->p, params->ctx);

383

// t2 = -s = q-s

384

BN_sub(t2, params->q, us->secret);

385

// t3 = t1^t2 = g^{-xb * xd * s}

386

BN_mod_exp(t3, t1, t2, params->p, params->ctx);

387

// t1 = X * t3 = X/g^{xb * xd * s}

388

BN_mod_mul(t1, us->p.s2.X, t3, params->p, params->ctx);

389

// K = t1^{xb}

390

us->key = BN_new();

391

BN_mod_exp(us->key, t1, us->xb, params->p, params->ctx);

392

393

// show

394

showbn(" K", us->key);

395

396

// cleanup

397

BN_free(t3);

398

BN_free(t2);

399

BN_free(t1);

400

}

401

402

int main(int argc, char **argv)

403

{

404

JPakeParameters params;

405

JPakeUser alice, bob;

406

407

alice.p.name = "Alice";

408

alice.p.base = 1;

409

bob.p.name = "Bob";

410

bob.p.base = 3;

411

412

JPakeParametersInit(&params);

413

414

// Shared secret

415

alice.secret = BN_new();

416

BN_rand(alice.secret, 32, -1, 0);

417

bob.secret = alice.secret;

418

showbn("secret", alice.secret);

419

420

assert(BN_cmp(alice.secret, params.q) < 0);

421

422

// Alice's x1, x2

423

genrand(&alice, &params);

424

425

// Bob's x3, x4

426

genrand(&bob, &params);

427

428

// Now send stuff to each other...

429

sendstep1(&alice, &bob.p, &params);

430

sendstep1(&bob, &alice.p, &params);

431

432

// And verify what each other sent

433

if(!verifystep1(&alice, &bob.p, &params))

434

return 1;

435

if(!verifystep1(&bob, &alice.p, &params))

436

return 2;

437

438

// Second send

439

sendstep2(&alice, &bob.p, &params);

440

sendstep2(&bob, &alice.p, &params);

441

442

// And second verify

443

if(!verifystep2(&alice, &bob.p, &params))

444

return 3;

445

if(!verifystep2(&bob, &alice.p, &params))

446

return 4;

447

448

// Compute common key

449

computekey(&alice, &params);

450

computekey(&bob, &params);

451

452

// Confirm the common key is identical

453

// XXX: if the two secrets are not the same, everything works up

454

// to this point, so the only way to detect a failure is by the

455

// difference in the calculated keys.

456

// Since we're all the same code, just compare them directly. In a

457

// real system, Alice sends Bob H(H(K)), Bob checks it, then sends

458

// back H(K), which Alice checks, or something equivalent.

459

puts("\nAlice and Bob check keys are the same:");

460

if(BN_cmp(alice.key, bob.key) == 0)

461

puts(" OK");

462

else

463

{

464

puts(" FAIL");

465

return 5;

466

}

467

468

return 0;

469

}

Older »