[tahoe-dev] a crypto puzzle about digital signatures and future compatibility

[James A. Donald]

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 
communication channels)

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 
<http://jim.com/security/prefix_free_number_encoding.html>

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 
solved.

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 
transition.