[messaging] Group messaging consistency under resource constraints

[Ximin Luo]

On 20/10/14 22:19, Natanael wrote:
> 
> Den 20 okt 2014 19:22 skrev "Ximin Luo" <infinity0 at pwned.gg <mailto:infinity0 at pwned.gg>>:
>>
>> On 20/10/14 18:10, Trevor Perrin wrote:
>> > On Mon, Oct 20, 2014 at 8:11 AM, Ximin Luo <infinity0 at pwned.gg <mailto:infinity0 at pwned.gg>> wrote:
>> >> On 10/10/14 23:09, Trevor Perrin wrote:
>> >>> On Fri, Oct 10, 2014 at 1:21 PM, Ximin Luo <infinity0 at pwned.gg <mailto:infinity0 at pwned.gg>> wrote:
>> >> Here is another example of an attack scenario. Hopefully, this demonstrates more obviously, that the [1] scheme proposed makes certain consistency attacks invisible to some of the victims:
>> >>
>> >> Alice: (1) So let's discuss Dual EC DRBG (last-message-seen: 0) # to everyone except David
>> >> Alice: (1A) So let's discuss Fortuna (last-message-seen: 0) # to David only
>> >> Bob:   (2) Do you think this RNG is suitable, David? (last-message-seen: 1) # to everyone
>> >> # David is feeling lazy today and doesn't want to wait for the warning to disappear nor to slow down the conversation.
>> >> # Besides, nothing bad happened with the last 37 warnings. Also, Bob is a totally trustworthy friend, right?
>> >> David: (3) Yeah it's suitable, let's go with that. (last-message-seen: 2) # to everyone
>> >> Alice: (4) OK, sounds good. Team, you heard our advisor. Make it so! (last-message-seen: 3)
>> >>
>> >> Everyone else except David sees 1<-2<-3<-4 with no warnings.
>> >
>> > David's "Yeah" should have last-messages-seen: 1A, 2.  So people are
>> > warned on receiving "Yeah" that they're missing context (1A).
>> >
>> > ([1] wasn't clear that a message could reference multiple parents, but
>> > I'm pretty sure that's what was meant).
>> >
>>
>> OK, so could you (or Moxie) describe in more precise detail what exactly would be pointed to?
>>
>> If there can be multiple parents, that suggests semantics of "all branch tips". But what happens in the case where I receive (1,2,3) ... (7,8,9)? 3 is an ancestor of 7, but I don't know that since I haven't received 4,5,6. Do I point to (3,9)? But that still doesn't *fully describe* the messages that I have missed, which is the root of why the above attack is possible.
>>
>> As long as the "parent pointers" are not an unambigious description of what I have actually seen, a consistency attack like the one above is possible. It would just take me longer to come up with a convincing attack scenario... OTOH, coming up with a compact scheme that does unambigiously describe what I have seen, would fix the attack, and be a huge step forward. (I haven't managed to come up with one that isn't complex or inefficient, though.)
> 
> I think my variant I replied with previously in this thread handles this well.
> 
> Using a Merkle tree hash of the previously seen messages (how many is ideal; a few dozen, a days worth?) and a counter of how many messages it was based on, you'll both get a warning that Alice's first message was never acknowledged by David and that David was replying with a message in his history you haven't seen (yellow exclamation mark signs on both messages?).
> 

Can you elaborate on this a bit, such as providing a more precise algorithmic description? ("How many" is conceptually easy I think - just "all the messages I've seen since the last time I reported on this information" - but you still need come up with a precise statement of this, as applied to your scheme.)

So, we are working in the context that some messages might be dropped. Say there were 20 messages and Alice only received 15 of them. She builds up a root hash from these 15 messages. How do others verify this hash? They have to try all 20-choose-15=15504 combinations to determine what Alice has seen? And, what if they themselves have only received some other 17 of these messages?

X

-- 
GPG: 4096R/1318EFAC5FBBDBCE
git://github.com/infinity0/pubkeys.git

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20141020/c0dc8dc2/attachment.sig>