[messaging] Group messaging consistency under resource constraints

[Natanael]

Den 20 okt 2014 19:22 skrev "Ximin Luo" <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> 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> 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?).

Clicking those warnings show you who has/hasn't seen what, and where
something seems to be missing.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20141020/0541b553/attachment.html>