[tahoe-dev] a crypto puzzle about digital signatures and future compatibility
James A. Donald
jamesd at echeque.com
Fri Aug 28 01:14:32 UTC 2009
Zooko Wilcox-O'Hearn wrote:
> On Wednesday,2009-08-26, at 19:49 , Brian Warner wrote:
>> Attack B is where Alice uploads a file, Bob gets the filecap and
>> downloads it, Carol gets the same filecap and downloads it, and
>> Carol desires to see the same file that Bob saw. ... The attackers
>> (who may be Alice and/or other parties) get to craft the filecap
>> and the shares however they like. The attackers win if Bob and
>> Carol accept different documents.
> Right, and if we add algorithm agility then this attack is possible
> even if both SHA-2 and SHA-3 are perfectly secure!
> Consider this variation of the scenario: Alice generates a filecap
> and gives it to Bob. Bob uses it to fetch a file, reads the file and
> sends the filecap to Carol along with a note saying that he approves
> this file. Carol uses the filecap to fetch the file. The Bob-and-
> Carol team loses if she gets a different file than the one he got.
If Bob and Carol want to be sure they are seeing the same file, have to
use a capability to an immutable file.
Obviously a capability to an immutable file has to commit the file to a
particular hash algorithm.
(Using "capability" in the sense of capabilities as cryptographic data,
capabilities as sparse addresses in a large address space identifying
So the leading bits of the capability have to be an algorithm
identifier. If Bob's tool does not recognize the algorithm, it fails,
and he has to upgrade to a tool that recognizes more algorithms.
If the protocol allows multiple hash types, then the hash has to start
with a number that identifies the algorithm. Yet we want that number to
comprise of very, very few bits.
This is almost precisely the example problem I discuss in
Now suppose an older algorithm is broken, and Alice wants to show Bob
one file, and Carol another, and pretend they are the same file.
So she just uses the older algorithm. Bob and Carol, however, have the
newer tool, which if the older algorithm is thoroughly broken, will
probably pop up "deprecated algorithm", which Bob and Carol will
cheerfully click through.
If however, the older algorithm has been broken a good long time, and we
are well past the transition period, and no one should be using the
older algorithm any more, except to wrap old format immutable files
inside new format immutable files, then Bob's tool will fail. Problem
Yes, during the transition period, people can be hosed, especially if
they see nag messages so often that they click them off, as they
probably will, but that is true no matter what. If an algorithm gets
broken, people can be hurt during the transition. The point, however,
is to have a smooth transition, even if security sucks during the
More information about the tahoe-dev