forked from dedis/Dissent
-
Notifications
You must be signed in to change notification settings - Fork 1
/
BLAME
253 lines (204 loc) · 12.9 KB
/
BLAME
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
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
Known Attacks Against Dissent and Solutions for Handling Them
Overview
===============================================================================
There are various cases for potential attcks on the protocol some are solvable
through the internal blaming mechanism and others are not. This document will
cover the attacks, solutions for those that have been solved and thoughts on
how the unsolved can be handled.
Attacks Cases
===============================================================================
01 - O - A member receives an invalid public keys
02 - X - A member distributes different public keys to different members
03 - X - A member inserts an invalid outer cipher block into the initial cipher
04 - O - A member inserts an invalid inner cipher block into the initial cipher
05 - X - A shuffler duplicates cipher blocks
06 - X - A shuffler replaces cipher blocks
07 - X - The final shuffler broadcasts different messages to different members
08 - X - A member reports a false no go
09 - O - A member reports a false no go to some members and a go to others
10 - O - A member reports a false go
11 - O - A member broadcasts an invalid inner private key
12 - X - A member shares different inner or outer private keys in a round
13 - O - A member initiates blame when there is none
14 - X - A member shares an invalid blame message
15 - X - A member shares improper messages in their blame log
16 - X - A member shares a blame log missing intermediate messages
17 - X - A member shares a blame log cutting off the end
18 - O - A member does not send messages in an appropriate amount of time
19 - O - A member sends a properly signed although malformed message
20 - O - Shufflers ignore a no go from a non-shuffler
21 - O - Shuffler exchanges different private keys to different nodes
22 - O - A member distributes an xor message of the incorrect length
23 - O - A member distributes different xor messages in the bulk phase
24 - O - A member does not respect the message size requirements in the shuffle
Legend:
ID - Handled (X) - Description
Discovering the Attacks
===============================================================================
01 is discovered by verifying that a public key is valid.
02 is handled by inspecting the hash of broadcast messages during the go / no
go phase.
03, attacks on the outer cipher blocks will be discovered during shuffling, a
member will discover that a message cannot be decrypted.
04, attacks on the inner cipher cannot be discovered until decryption at each
site, where a decryption may fail.
05, duplicating shuffle blocks can be discovered during shuffle by ensuring
there are no duplicate messages at each shuffle round.
06, to prevent replacing cipher blocks, all members need to verify their cipher
block exists at the end of the shuffling, prior to releasing their keys.
07, like 02, is handled by inspecting the hash of broadcast messages during
the go / no go phase.
08, must be handled during a blame phase.
09 will create a blame phase for some members and not for others, therefore,
after blame data has been broadcasted, thus needs an additional verification
phase, as discussed below.
10, this cannot be handled, as only the member individual members know whether or
not their message is in the final data set.
11, this is discovered at the end of the protocol run during decryption, this
is similar to the attack 04, however, this attack can be resolved without
revealing the identity of innocent members.
12, this will be discovered during the go / no go phase broadcast
verification, where in it will be verified during a blame phase.
13, this requires a causal relationship between incoming and outgoing messages
in order to narrow down during a blame phase where the blame message came from.
Obviously, the first member(s) to start a blame phase are the guilty party.
14, this requires a verification on the blame phase prior to investigating the
logs.
15, this will be discovered during replay of the blame messages
16, this will be discovered during replay of the blame messages
17, this can be discovered by comparing the state of members later in the group
order.
18, this is a complex problem.
19, this is a complex problem.
20, this is discovered when a member receives private keys instead of blame
data, in the current protocol this will result in the node sharing blame data
and other nodes being uncertain why.
21, this is discovered in the final phase, when private keys are distributed.
22, this is discovered during reception of a message in the bulk round.
23, this is discovered during reception of a message in the bulk round.
24, discovered by first shuffler node
Handling Attacks on the Blame Phase
===============================================================================
An easy way for attacks to occur is by allowing imperfect messages from
tainting the system. Therefore, no messages are recorded if there is any
problems with them. This means a message will be entirely deciphered prior to
making a state change or all members must verify that the data is consistent
prior to using it. Primarily this falls on invalid signatures as other
messages can easily be verified via blame.
Once a member has generated a log of only verified messages, it can be
distributed to other members allowing them to rebuild the state of the system
in a verifiable way (the remote peers signed messages) and then verify that
that member's behavior is consistent with its claim.
Unfortuantely, the blame state itself can be attacked, 13. A malicious member
owning several resource may want to partition the Dissent ring or avoid having
a specific resource be identified during the blame phase. In order to avoid
partition attacks, blame messages should be verified in a post blame broadcast
round. Therefore, each member will distribute with their blame message a hash
of the message that is signed with their key. Upon collecting all blame
messages, the members will share this verification data with other member. EAch
member will be able to see that other members share their verification data or
there is a mismatch. A mismatch will occur because either the sender of the
blame data sent different messages to different members, in which case it will
be signed correctly, or the receipient changed messages and it is not signed
properly. Because of the second property, all peers must verify signatures
prior to exchanging verifications. If a signature fails, then the message is
considered faulty and should be resolved similarly to a missing message, 14, or
a well crafted malicious message, 15.
The general format for blame message verifications are:
- msg = [blame data packet id][round id / nonce][hash]
- signature = {msg}signing_key
- distributed message = [hash][signature]
So each member will share with other memebers the distributed message, which
can then be used to verify integrity during the blame phase.
If an attack occurs during the blame phase initiation, progress is currently
halted for simplicity reasons. Alternatively, members could potentially
progress forward excluding the faulty members in an attempt to find additional
faulty members. The current goal of the blame is to find at least 1 malicious
peer and ending the blame scenarios at the end of each blame phase step.
Executing the Blame Phase
===============================================================================
After receiving all blame messages and verifying their integrity, each member
will have the same log and will run through an identical process of replaying
messages. Each member will reconstruct the round from each other members
perspective, including their own.
During replay, if a message fails, that member is to blame for including a
faulty message in the blame log. The process for replaying messages continues
until completion. All members with faulty logs are noted as bad members, and
if there are any bad members, execution of the blame phase concludes.
Otherwise the next stage begins. This covers attacks 15 and 16.
Each stage here out, follows the flow of the Dissent shuffle algorithm.
Members confirm that all public keys match each other. If there are any
mismatches, then the mismatched peer is at fault. If no mismatches execution
continues. This covers attack 02.
The members will now execute through the shuffle rounds, if a members input
does not match their output, they are to blame. In otherwords, their output
will be the input into the next peer of the shuffle. This covers attacks
03, 05, 06, 07
Finally, each peer will be checked for faulty blame by independently cycling
through the onion data by decrypting it in order without shuffling. Then a
peers incoming message to the first peer can be matched all the way to the
final message distributed to the last peer. If their message is in that final
message, then they should announce go, otherwise no go. This covers 08, 09,
and 10. Although 10 cannot be detected.
Blame in the Bulk Phase
===============================================================================
In the current instantiation, the bulk phase uses the shuffle to do the prep
work. In the shuffle, each bulk member that wants to share a message will
distribute an anonymous DiffieHellman public key, N hashes for xor data, and
the length of the bulk data (L). The DiffieHellman public key is used along with
the memberss well known DiffieHellman key to generate a random seed, which is
used to generate xor text. Each member will transmit L xor bytes, except the
member whose message is being transmitted. That member will distribute the
xor of his cleartext and the accumulated xor message of the other members.
After receiving messages, each member will validate their messages, similar to
the blame verification mentioned earlier. In this session, a node will
distribute a go, if everything is fine, otherwise it will distribute a no go
and a copy of the invalid message. If the message is not verifiable, the
blaming node is blamed. If the message is verifiable and of insufficient
bytes, the sender is blamed, 22. The rest of the attacks fall under 23. If
the message is verifiable, of sufficient bytes, and sent to all members, the
anonymous sender and the sender are suspected. The blame can be determined by
having a shuffle round in which the anonymous sender reveals the means to
verify the message. Otherwise at least one member has a properly constructed
message, which implies that the sender of the xor data is to blame.
Bulk phase consists of three communication stages, shuffle of descriptors, bulk
messages, and a verification. In the verification phase, nodes will distribute
a message of the following form:
[BulkVerification][good/bad][[X1,Y1][X2,Y2]], where X and Y are the nodes index
and error they caused, either incorrect length or hash.
If all honest nodes received incorrect length except the offending nodes, the
node is blamed. If all nodes receive an improperly hashed message, a shuffle
cycle is required to reveal the seed used to generate the message so that it
hashes properly. If no seed is revealed, the shufflers will work together to
reveal the submitter of the descriptor. If the seed is correct, the bulk
sender is blamed. If the a correctly hashed message is received by at least
one peer, it is distributed to all peers, and the peer is blamed. If multiple
invalid seeds are released, then the shufflers will reveal the identity of
those seeds.
Handling Network Failures or Faulty Messages
===============================================================================
Faulty messages could be potentially solved by simply broadcasting a properly
signed albeit faulty message to the entire group. The bounds of what
constitues an incriminating faulty message depends on the intent of the
message. This is currently left as future work. Attacks that fall into this
category include 01, 11, 19, 21, and to some degree 20. 20 is a
special case as it involves a significant compromise to the system, see below.
A network failure would require all memberss to conclude that the peer has not
sent a message and is either non-responsive or malicious. Handling this is
left for future work. Attack 18 falls into this category.
Unhandled
===============================================================================
13, false blame initiation, cannot be handled within the current approach as
their is no means to guarantee message causalty.
09 cannot be handled in the current protocol. This could be solved by
requiring a system wide ack much like the one discussed for the changing blame
data.
04 cannot be (easily) handled although it could be treated as a null data
block.
20 results from a compromised group of shufflers, the node could potentially
share this knowledge with others, in which case the other members could force a
blame phase. How to handle this properly is open for discussion.
Notes
===============================================================================
This is an evolving document and is far from complete. This document continues
from the original discussion on blame from the file legacy/py/README(BLAME).