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

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

[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 



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

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

[Zooko Wilcox-O'Hearn]

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.


Now suppose Alice is malicious and knows how to produce output which  
appears to come from Tahoe-SHA2-SHA3, suppose Bob uses Tahoe-SHA3,  
and suppose Carol uses Tahoe-SHA2.  Then Alice can generate two  
files, one which shows Bob what Alice wants him to see and the other  
which shows Carol what Alice wants her to see.


So by adding an optional new hash algorithm intended to strengthen  
Tahoe-LAFS against the possibility that someone can break SHA2, we  
might (if we're not careful) open up a hole that can be exploited  
even by someone who can't break SHA2.


One defense against the attack above would be to make sure that, as  
long as you might want to share files with someone who might still  
use Tahoe-SHA2, then you don't upgrade to Tahoe-SHA3 -- instead you  
have to stick with the intermediate bi-lingual version, Tahoe-SHA2- 
SHA3, which produces both kinds of hashes and checks both kinds of  
hashes.  But how can you tell whether there are still some Tahoe-SHA2  
users out there somewhere that you might eventually want to share a  
file with?  Also, might this approach somehow accidentally prolong  
Tahoe-LAFS's vulnerability to a flaw in SHA2?


So to use this defense, Bob would use Tahoe-SHA2-SHA3, and he would  
always verify both hashes before approving the file.  If one hash  
matched but the other didn't, his Tahoe-LAFS software would warn him  
that something is very wrong with Alice or her Tahoe-LAFS software.   
(This means that we have to spend the CPU cycles verifying old- 
fashioned hashes, and worse that we have to make file capabilities  
twice as big in order to hold both hashes, which could negatively  
impact the user experience.)


Another, complementary, defense against this sort of attack would be  
that if you receive a filecap which has a hash in it that you don't  
know how to check, then you should *erase* that hash from the filecap  
before you pass that filecap on to your friend.  Then if Alice has a  
malicious Tahoe-SHA2-SHA3, Bob has Tahoe-SHA2, and Carol has Tahoe- 
SHA3, Bob will give Carol a filecap with only a SHA2 hash in it,  
which Carol will not know how to check, thus defeating Alice's evil  
scheme.


The bottom line is that the whole idea of adding algorithm agility  
and an optional hash algorithm seems to entail complication and  
danger, and Tahoe-LAFS is very likely going to take the alternate  
route: a future version of Tahoe-LAFS will probably define a  
completely different type of immutable file capability which is  
syntactically distinct from the current type (i.e. it starts with a  
distinct leading character or it is a different length so that it  
cannot be confused with the old kind by a program and hopefully not  
by a human either), and which uses only SHA3.  Then you will not be  
able to produce a single filecap which can be verified with both SHA2  
and SHA3.  You can, of course, produce two different filecaps, one in  
the old format and one in the new format.  This sounds good to me  
because if Alice sends a pair of filecaps to Bob then it will be  
obvious to Bob that the two could point to different files, at  
Alice's disgression.



I always get confused about the difference between first-preimage  
and second-preimage, but I think there's a correspondence here. In  
Attack A, the attacker doesn't get to choose the filecap (i.e. the  
hash of the message): they've got to create shares to match a  
specific pre-determined cap. In Attack B, Alice can craft an  
arbitrarily complex message, taking advantage of a known collision  
or whatever.


Pre-image is figuring out the input x that someone used to compute y  
= H(x), when they give you only y.  Second-pre-image is when someone  
else chooses an x and tells you x and then you find a different x2 !=  
x such that H(x) = H(x2).  Collision is when you come up with any two  
values, x and x2 != x such that H(x) = H(x2).


Tahoe-LAFS's semantics of immutable file caps is that the cap is an  
*identifier* of the file, not just a digital signature or message  
authentication code on the file, as demo

Re: a crypto puzzle about digital signatures and future compatibility

[Jerry Leichter]

On Aug 26, 2009, at 1:39 PM, Zooko Wilcox-O'Hearn wrote:

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

"Good enough" for what purpose?

By hypothesis, "SHA-3" is secure, so computing some additional  
function can't hurt v1.7 readers.


On the other hand, v1.6 readers are still relying on the the, by  
hypothesis, fallen SHA-2, so you haven't *directly* helped them at all.


*Indirectly*, any v1.7 reader who noticed that the SHA-2 hashes agreed  
but the SHA-3 matches did not would have detected the attack.  The  
question is, what could he do about it?  You can fall back to extra- 
protocol mechanisms - e.g., he's asked to send a message to the Tahoe- 
LAFS mailing list about it - but if we posit a world of a large number  
of independent users of Tahoe-LAFS, that probably won't reach the  
right audience.  Writing to the owner of the file sounds nice on  
paper, but he may be anonymous, and even if he isn't, his *readers*  
may be anonymous to him.


If you really want to rely on detection by v1.7 users actually  
contributing to the safety of the larger community, you'd need to  
build a support mechanism into the system itself.  Something like a  
"Caution!" flag - which, of necessity, anyone could set, and whose  
semantics would be to give any user the warning "make sure you're  
running the latest version of the software, someone has noticed  
something odd about this file which your version isn't sensitive to" -  
would work.  If there's a reliable way to ensure that you're running  
the latest version of the software, you can ignore the "Caution!"  
flag, thus minimizing the effect of "caution flag spamming".   
(Presumably, you store the latest version in Tahoe-LAFS somewhere ...  
though you perhaps want to add some additional security on that, like  
a separate signature, in case *it* gets its "Caution!" flag set.)


On a general note:  The concatenation of multiple hashes can't  
possibly be less secure than the most secure of the individual hashes  
(at least in protocols where the actual data being hashed is already  
known to the receiver; if first pre-image resistance matters to you,  
the identity function as a hash will obviously give you problems).   
The attacks known have to find delicate balancing changes to the  
input.  Even a very simple additional check - say a CRC - would block  
them as they stand.  (That's not to say matching on an additional CRC  
couldn't be incorporated into an attack if someone was interested in  
doing it.)

-- Jerry

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

Re: a crypto puzzle about digital signatures and future compatibility

[Richard Salz]

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

Isn't that what SSL/TLS does?

/r$

--
STSM, DataPower CTO
WebSphere Appliance Architect
http://www.ibm.com/software/integration/datapower/

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

a crypto puzzle about digital signatures and future compatibility

[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