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

2009-09-04 Thread Zooko Wilcox-O'Hearn

On Thursday,2009-08-27, at 19:14 , James A. Donald wrote:


Zooko Wilcox-O'Hearn wrote:
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.

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


Jim, I'm not sure you understood the specific problem I meant -- I'm  
concerned (for starters) with the problems that arise if we support  
more than one secure hash algorithm *even* when none of the supported  
secure hash algorithms ever becomes crackable!


So much so that I currently intend to avoid having a notion of  
algorithm agility inside the current Tahoe-LAFS code base, and  
instead plan for an algorithm upgrade to require a code base upgrade  
and a separate, syntactically distinct, type of file capability.


This is almost precisely the example problem I discuss in http:// 
jim.com/security/prefix_free_number_encoding.html


Hey, that's interesting.  I'll study your prefix-free encoding format  
some time.


Regards,

Zooko

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com


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

2009-08-31 Thread 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.



-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com


a crypto puzzle about digital signatures and future compatibility

2009-08-26 Thread Zooko Wilcox-O'Hearn

Folks:

My brother Nathan Wilcox asked me in private mail about protocol  
versioning issues.  (He was inspired by this thread on  
cryptography@metzdowd.com [1, 2, 3]).  After rambling for a while  
about my theories and experiences with such things, I remembered this  
vexing future-compatibility issue that I still don't know how to  
solve:


Here is a puzzle for you (I don't know the answer).

Would it be a reasonable safety measure to deploy a Tahoe-LAFS v1.6,  
which used SHA-2 but didn't know how to use SHA-3 (because it hasn't  
been defined yet), and then later deploy a Tahoe-LAFS v1.7, which did  
know how to use SHA-3, and have v1.7 writers produce new files which  
v1.6 readers can integrity-check (using SHA-2) and also v1.7 readers  
can integrity-check (using SHA-3)?


So far this seems like an obvious win, but then you have to say what  
if, after we've deployed v1.7, someone posts a perl script to  
sci.crypt which produces second-pre-images for SHA-2 (but not  
SHA-3)?  Then writers who are using Tahoe-LAFS v1.7 really want to be  
able to *stop* producing files which v1.6 readers will trust based on  
SHA-2, right?  And also, even if that doesn't happen and SHA-2 is  
still believed to be reliable, then what if some sneaky v1.7 user  
hacks his v1.7 software to make two different files, sign one of them  
with SHA-2 and the other wish SHA-3, and then put both hashes into a  
single immutable file cap and give it to a v1.6 reader, asking him to  
inspect the file and then pass it on to his trusted, v1.7-using,  
partner?


Hm...

This at least suggests that the v1.7 readers need to check *all*  
hashes that are offered and raise an alarm if some verify and others  
don't.  Is that good enough?


:-/

Regards,

Zooko

[1] http://www.mail-archive.com/cryptography@metzdowd.com/msg10791.html
[2] http://www.mail-archive.com/cryptography@metzdowd.com/msg10807.html
[3] http://www.mail-archive.com/cryptography@metzdowd.com/msg10805.html

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com