Filename:107-PBC.txt
Title:The pairing-based key negotiation protocol
Version:0.0.1
Last modified:
Author:Watson Ladd
Created:9-March-2007
Status:Open

Overview: This document describes a new version of the tor protocol
	  that uses pairing-based cryptography following [1].

Motivation: The protocol described in [1] is much more efficient in both
	    bandwith and CPU then the current protocol.

Backwards-compatability: Sadly, use of the VERSION cell will negate some of the
			 advantages of the new protocol. This is very much
			 a work in progress. Current solution is a new cell
			 type.

Proposal:
Section 0.0: Magic Numbers
Section 1.0: Circuit Establisment
Section 1.1: The distributed PKG.
Section 2.1: The new directory format

Section 0.0: Magic Numbers
	Curve P-521 in FIPS 186 [2] is to be used. New cell types is defined:
	[7] CREATE_WARPSPEED, and [8] EXITING_HYPERSPACE
	 The master key expiration period is 24 hours exact to the nearest
	 second. The private key expiration period is one hour to the nearest
	 second.

Section 1.0: Circuit establishment
	In 1.1 the orgin of v_m, U, and sU will be mentioned. v_m is a
	timestamp consisting of the number of seconds since midnight
	Jan 1, 1970 to the begining of the Master Key Validity Period.
	Let i be an index variable taken over all OR's in the circuit.
	Then let Q_vi=H(v||ID_i) where v is the timestamp at the begining
	of the Private Key Validity Period, and ID_i is the ID of router i.
	Then let y_vi=P(sU, Q_vi). Let r_i be random integers not zero in
	Z_n where n is the size of the group. r_i's are selected randomly
	for each OR i. Then let P_i=r_iU and compute y_vi^r_i for each OR i.
	From each y_vi^r_i a forwards key K_f_i and backwards key K_b_i are
	computed.

	Let A,..,N be the nodes being put into an onion circuit. Then the
	CREATE_WARPSPEED cell being sent to A has the following payload:
	cid,r_AU,{B, r_BU,{ ... {N, r_NU, {NULL}_{K_f_N}}...}_{K_f_B}}_{K_f_A}
	On recipt of a CREATE_WARPSPEED cell the OR i computes P(r_iU,d_vi)
	and from it derives K_f_i and K_b_i. It then finds out what router
	to send the next CREATE_WARPSPEED cell to. In the process it chops off
	the router's name and replaces it with the circuit id it wants to use
	for that link of the circuit. The NULL message is a EXITING_HYPERSPACE cell.
	On noticing that the decrypted message is an EXITING_HYPERSPACE cell, the OR is
	expected to send a CIRCUIT_CREATED cell back, encrypting it with K_b_i, just like
	all traffic on the newly established circuit.

Section 1.1 TODO
Section 1.2 TODO