1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
|
Filename: xxx-ntor-handshake.txt
Title: Improved circuit-creation key exchange
Author: Nick Mathewson
Created: 11-May-2011
Status: Draft
This is an attempt to translate the proposed circuit handshake from
"Anonymity and one-way authentication in key-exchange protocols" by
Goldberg, Stebila, and Ustaoglu, into a Tor proposal format.
It assumes something like Robert Ransom's proposal draft is in place to
provide an extended CREATE cell format that can indicate what type of
handshake is in use.
Notation:
Let a|b be the concatenation of a with b.
Let H(x,t) be a tweakable hash function of output width H_LENGTH bytes.
Let t_mac, t_key, and t_verify be a set of arbitrarily-chosen tweaks
for the hash function.
Let EXP(a,b) be a^b in some appropriate group G where the appropriate DH
parameters hold. Let's say elements of this group, when represented as
byte strings, are all G_LENGTH bytes long. Let's say we are using a
generator g for this group.
Let a,A=KEYGEN() yield a new private-public keypair in G, where a is the
secret key and A = EXP(g,a). If additional checks are needed to insure
a valid keypair, they should be performed.
Let PROTOID be a string designating this variant of the protocol.
Let KEYID be a collision-resistant (but not necessarily preimage-resistant)
hash function on members of G, of output length H_LENGTH bytes.
Instantiation:
Let's call this PROTOID "ntor-curve25519-sha256-1" (We might want to make
this shorter if it turns out to save us a block of hashing somewhere.)
Set H(x,t) == HMAC_SHA256 with message x and key t. So H_LENGTH == 32.
Set t_mac == PROTOID | ":mac"
t_key == PROTOID | ":key"
t_verify == PROTOID | ":verify"
Set EXP(a,b) == curve25519(.,b,a), and g == 9 . Let KEYGEN() do the
appropriate manipulations when generating the secret key (clearing the
low bits, twiddling the high bits).
Set KEYID(B) == B. (We don't need to use a hash function here, since our
keys are already very short. It is trivially collision-resistant, since
KEYID(A)==KEYID(B) iff A==B.)
Protocol:
Take a router with identity key digest ID.
As setup, the router generates a secret key b, and a public onion key
B with b, B = KEYGEN(). The router publishes B in its server descriptor.
To send a create cell, the client generates a keypair x,X = KEYGEN(), and
sends a CREATE cell with contents:
NODEID: ID -- H_LENGTH bytes
KEYID: KEYID(B) -- H_LENGTH bytes
CLIENT_PK: X -- G_LENGTH bytes
The server generates a keypair of y,Y = KEYGEN(), and computes
secret_input = EXP(X,y) | EXP(X,b) | ID | B | X | Y | PROTOID
KEY_SEED = H(secret_input, t_key)
verify = H(secret_input, t_verify)
auth_input = verify | ID | B | Y | X | PROTOID | "Server"
The server sends a CREATED cell containing:
SERVER_PK: Y -- G_LENGTH bytes
AUTH: H(auth_input, t_mac) -- H_LENGTH byets
The client then checks Y is in G^* [see below], and computes
secret_input = EXP(Y,x) | EXP(B,x) | ID | B | X | Y | PROTOID
KEY_SEED = H(secret_input, t_key)
verify = H(secret_input, t_verify)
auth_input = verify | ID | B | Y | X | PROTOID | "Server"
The client verifies that AUTH == H(auth_input, t_mac).
[NOTE: It may be adequate to check that EXP(Y,x) is not the point at
infinity. See tor-dev thread.]
Both parties now have a shared value for KEY_SEED. They expand this into
the keys needed for the Tor relay protocol.
Key expansion:
Currently, the key expansion formula used by Tor here is
K = SHA(K0 | [00]) | SHA(K0 | [01]) | SHA(K0 | [02]) | ...
where K0==g^xy, and K is divvied up into Df, Db, Kf, and Kb portions.
Instead, let's have it be
K = K_0 | K_1 | K_2 | K_3 | ...
Where K_0 = H(m_expand | INT8(i) , KEY_SEED )
and K_(i+1) = H(K_i | m_expand | INT8(i) , KEY_SEED )
and m_expend is an arbitrarily chosen value,
and INT8(i) is a octet with the value "i".
Ian says this is due to a construction from Krawczyk at
http://eprint.iacr.org/2010/264 .
Performance notes:
In Tor's current circuit creation handshake, the client does:
One RSA public-key encryption
A full DH handshake in Z_p
A short AES encryption
Five SHA1s for key expansion
And the server does:
One RSA private-key decryption
A full DH handshake in Z_p
A short AES decryption
Five SHA1s for key expansion
While in the revised handshake, the client does:
A full DH handshake
A public-half of a DH handshake
3 H operations for the handshake
3 H operations for the key expansion
and the server does:
A full DH handshake
A private-half of a DH handshake
3 H operations for the handshake
3 H operations for the key expansion
|
