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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
|
% #1: fig:label
% #2: Handler title
% #3: caption
\newenvironment{handler}[3]{%
\def\handlerlabel{fig:#1}%
\def\handlertitle{#2}%
\def\handlercaption{#3}%
\begin{figure}%
\center\vspace{1em}%
\noindent\begin{tabular}{|p{\myboxlen}|}%
\hline%
\footnotesize%
{\tt\bf \handlertitle}%
}
{%
\\ \hline%
\end{tabular}%
\caption{\handlercaption}%
\label{\handlerlabel}%
\end{figure}%
}
\begin{handler}{server-init}{Server at round $i$}{}
\begin{lstlisting}{}
let phase$^i$ = Seeding;
let seed$^i$ = random_seed();
let S$^i_{seed}$ = sign( <$i$,seed$^i$>, KS$_{priv}$);
let M$^i_{seed}$ = Seed($i$,seed$^i$,S$^i_{seed}$);
let map$^i$ = $\emptyset$
$\forall q \in$ NS$_{server}$, send($q$, M$^i_{seed}$);
wait $T$;
phase$^i$ = Idle;
H$^i$ = Hash(map$^i$);
let S$^i_{pulse}$ = sign( <$i$,seed$^i$,H$^i$>, KS$_{priv}$ );
let M$^i_{pulse}$ = Pulse($i$, seed$^i$, H$^i$,
0, $\{$ 0 $\rightarrow$ map$^i$ $\}$, S$^i_{pulse}$);
$\forall q \in$ NS$_{server}$, send($q$, M$^i_{pulse}$);
\end{lstlisting}
\end{handler}
\begin{handler}{xn}{Server or peer receiving SeedReply ($i$, X$_q$) from peer $q$:}{}
\begin{lstlisting}{}
if phase$^i$ = Seeding then
map$^i$ = $\{ q \rightarrow $X$_q \} \oplus$ map$^i$;
end if
\end{lstlisting}
\end{handler}
\begin{handler}{xn}{Every $\Delta << T$ seconds, on peer $p$:}{}
\begin{lstlisting}{}
if phase$^i$ = Seeding then
let H$^i$ = H(map$^i$);
let M$^i_{seedreply}$ = SeedReply($i$, H$^i$ );
nreplies$^i$ = nreplies$^i$ + 1;
replies$^i$[ nreplies$^i$ ] = (H$^i$, map$^i$);
$\forall q \in$ NS$_p$, send($q$, M$^i_{seedreply}$);
end if
\end{lstlisting}
\end{handler}
\begin{handler}{x1}{Peer $p$ receiving M$^i_{seed}$ = Seed ($i$,seed$^i$,S$^i_{seed}$):}{}
\begin{lstlisting}{}
if verify_sig( S$^i_{seed}$, <$i$,seed$^i$>, KS$_{priv}$) then
$\forall q \in$ NS$_p$, send($q$, M$^i_{seed}$);
let S$^i_p$ = sign( <$i$,seed$^i$>, K$^p_{priv}$);
let map$^i$ = $\{ p \rightarrow H(S^i_p) \}$
nreplies$^i$ = 0;
phase$^i$ = Seeding;
end if
\end{lstlisting}
\end{handler}
\begin{handler}{x3}{Peer $p$ receiving
Pulse($i$, seed$^i$, H$^i$, level, tree$^i$, S$^i_{pulse}$):}{}
\begin{lstlisting}{}
if
verify_sig(S$^i_{pulse}$, <$i$, seed$^i$, H$^i$ >, KS$_{pub}$ )
then
phase$^i$ = Idle;
included$^i$ = $\bot$;
if
$\exists$ $\{$ $p$ $\rightarrow$ H$^i$ $\}$ $\in$ tree$^i$[level] and
$\exists$ $n$ $|$ replies[$n$] = (H$^i$, oldmap$^i$) and
included$^i$ $<$ $n$ and
verify_tree(H$^i$, level, tree$^i$)
then
let tree'$^i$ = tree$^i$ $\oplus$ $\{$ level+1 $\rightarrow$ oldmap$^i$ $\}$;
M$^i_{pulse}$ = ($i$, seed$^i$, H$^i$, level+1, tree'$^i$, S$^i_{pulse}$)
History[$i$] = M$^i_{pulse}$;
included$^i$ = $n$;
$\forall q \in$ children$^p$, send($q$, Pulse M$^i_{pulse}$);
end if
end if
\end{lstlisting}
\end{handler}
\begin{handler}{x4}{Peer $p$ sending to $q$ its availability at round $i$:}{}
\begin{lstlisting}{}
let bits$^i$ = new bitfield[$N_t$];
for $x$ in [1..$N_t$]
if History[$i-N_t+x$] = $\emptyset$ then
bits$^i$[$x$] := 0
else
bits$^i$[$x$] := 1
end if
end for
let S$^i_{avail}$ = sign( < $i$, bits$^i$ >, K$^p_{priv}$ )
let M$^i_{avail}$ = ($i$,bits,S$^i_{avail}$);
send( $q$, Availability M$^i_{avail}$ )
\end{lstlisting}
\end{handler}
\begin{handler}{x5}{Peer $p$ receiving Challenge($i$, nonce) from peer $q$:}{}
\begin{lstlisting}{}
let M$^i_{pulse}$ = History[$i$]
send( $q$, Proof M$^i_{pulse}$)
\end{lstlisting}
\end{handler}
\begin{handler}{x6}{Peer $q$ receiving from peer $p$
Proof ($i$, nonce, K$^i_{pub}$, trees$^i$, S$^i_p$, S$^i_{pulse}$, S$_{proof}$):}{}
\begin{lstlisting}{}
Peer $q$ receiving from peer $p$
Proof ($i$, nonce, K$^i_{pub}$, trees$^i$, S$^i_p$, S$^i_{pulse}$, S$_{proof}$):
if
($i$, nonce, $p$) $\in$ challenges $\land$
verify_sig(S$^i_{pulse}$,<$i$, seed$^i$,$K^i_{pub}$,trees$^i$[0]>,KS$_{pub}$) $\land$
verify_sig(S$^i_p$, <$i$, seed$^i$ >, K$^p_{pub}$) $\land$
S$^i_p$ $\in$ trees$^i$ $\land$
$\forall n>0$, H(trees$^i$[n]) $\in$ trees$^i$[n-1] $\land$
verify_sig(S$_{proof}$, < nonce, H$^p$, H$^q$ >, K$^i_{pub}$ )
then
good_reply($p$)
else
bad_reply($p$)
end if
\end{lstlisting}
\end{handler}
\endinput
A major problem in peer-to-peer networks is that peers might work together
({\em collude}) to break security properties of a protocol. In our case, some
peers might work together to increase their measured availability. In this
section, we describe an extension of our protocol to fight against collusion.
The easiest way to collude to break our original protocol is for a peer
to give the pulse to another peer, that was not available when the pulse
was distributed. This can be done as part of an exchange (for other
pulses) so that both peers will increase their measured availability, or
as part of an attack, if the peer wants to increase measured availability
of all peers to break the system.
Our solution is a three phases protocol:
\begin{itemize}
\item {\bf Phase 1} The server diffuses a {\em seed} for the round on the
network using a {\tt Seed} message.
\item {\bf Phase 2} Every client generates a signature of the
seed with its private key. It then computes a short hash of the
signature. It then joins its hash to the hashes received from its children
and computes a new hash, that it sends to its parents, using a {\tt Tree} message.
The server itself computes a hash from the hashes received from its children.
\item {\bf Phase 3} The server computes the new pulse for the round, and
diffuses it in a {\tt Pulse} message, together with the seed for the round and
the hash computed in phase 2, both signed by its private key. Every parent propagates the
pulse to its children, adding also the list of hashes it used to compute
the hash sent to its parents.
\end{itemize}
The goal of this extension of the original protocol is that the pulse now
contains a piece of information recording the presence of all the peers in
the network through a merkle-tree\cite{1979-merkle}. Colluding peers will
only be able to use the pulse if they can provide the signature of the hash
and the merkle tree showing it has been taken into account in the computation
of the pulse.
Now, let's assume peers $p$ and $q$ are colluding: peer $p$ is online
during the diffusion of the pulse, while $q$ is offline. To be able to
give a useful pulse to $q$, $p$ must have included $q$ into the
merkle-tree. To do that, it must have issued a signature of the seed using
$q$ private key, and then put the hash of the signature in its own tree. This
means that peer $p$ must know the private key of peer $q$ to collude.
It is thus an important requirement on applications using our system that
they discourage peers from sharing their private keys. This can easily
been done by giving extra-power to key owners, i.e. for instance the owner
of a private key should be allowed to delete data associated with the
key, or to book storage using the key. As a consequence, colluding peers
would have to trust each other, to such a high degree that collusion would
only be possible among a very small part of the network.
We assume to know the depth of the network. Is it bad ? Probably... ;-)
|
