[Cryptography] Cryptographically securing a two-phase commit

[Jon Callas]

> 
> Can anyone suggest a means of avoiding this overhead that doesn't require
> inventing a custom protocol or format for the purpose?  In other words that
> works within the PGP or S/MIME format to try and avoid this issue?  One
> obvious solution that doesn't work is to precede the blob with a signed token
> saying "the blob that follows is legit", but since there's no way to
> cryptographically tie it to the blob that follows it's still vulnerable to a
> spoofing attack, capture and/or replay a signed token and follow it up with a
> dummy blob to force the 2PC overhead.
> 
> Again, it needs to be achievable using a standard format like PGP or S/MIME,
> inventing a new protocol or format to do it isn't an option.  Breaking the
> single blob up into lots of little sub-blobs, each individually authenticated
> and hash-chained together, is possible as a last resort but anything better
> would be preferable.

I'm not sure this is even possible. 

Let's just model this abstractly. You have a bit stream, and the last bit is bad. We can't know the stream is bad until we receive and compute on that last bit.

Let's also assume that every bit is authenticated. This can let us know that it was precisely that the last bit and only the last bit was bad. (Ironically, in the case of bit-level, as opposed to some larger chunk, we also get error correction, since knowing the bit is bad makes guessing the correct value easy. It's only a factoid, but I still was amused by it when I realized it.) We still have to make the entire authentication contingent on getting and computing the last bit.

So my naive take is that this is just flat-out impossible. It is always possible for an attacker who can arbitrarily jigger your inputs to DoS you. 

However, I think that there are countermeasures that are at least possible. I think you could use some sort of TTL or timestamp or serial number to make this harder for the attacker. You can do some trick like your up-front authentication declaration and keep track of valid things seen in a time window. My mental design on this leads me to think I can restrict them to replaying only the last thing seen, which is easy to look for. If you were evaluating c_0, c_1, ..., c_n and and while starting to evaluate c_n, you can implicitly know that any replay of c_j where j < n is a replay and just reject it.

However however, consider the case where the attacker doesn't modify that last chunk, they just drop it on the floor. You've had to compute everything up to that point and now you see what is apparently a dropped connection. The attacker can then basically replay by saying, "Sorry about that, where was I? Oh, yes, I wanted to send you this nth commitment" and start the whole thing over again and then lather, rinse, repeat. They get to DoS your this way, by emulating an arbitrary broken connection and restart. In many cases, the attacker doesn't even need to emulate it, they just let you compute some section of the commitment and then force a restart. I can discuss more, but I think we have the point. The attacker DoSes you with the present connection and can in your chained system just keep replaying something to force you to hold state open.

So in the general case, I don't think this is possible at all; forget formats. I think you can restrict the attacker to putting you into a retry loop, which any sufficiently evil router can approximate anyway. That's cold comfort. That final thing is really the easiest attack (compared to replays etc.). 

Am I missing something?

	Jon