Re: Truncating SHA2 hashes vs shortening a MAC for ZFS Crypto

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

On Wednesday,2009-11-04, at 7:04 , Darren J Moffat wrote:

The SHA-256 is unkeyed so there would be nothing to stop an  
attacker that can write to the disks but doesn't know the key from  
modifying the on disk ciphertext and all the SHA-256 hashes up to  
the top of the Merkle tree to the uberblock.  That would create a  
valid ZFS pool but the data would have been tampered with.   I  
don't see that as an acceptable risk.

I see.  It is interesting that you and I have different intuitions  
about this.  My intuition is that it is easier to make sure that the  
Merkle Tree root hash wasn't unauthorizedly changed than to make sure  
that an unauthorized person hasn't learned a secret.  Is your  
intuition the opposite?  I suppose in different situations either one  
could be true.

Now I better appreciate why you want to use both a secure hash and a  
MAC.  Now I understand the appeal of Nico Williams's proposal to MAC  
just the root of the tree and not every node of the tree.  That would  
save space in all the non-root nodes but would retain the property  
that you have to both know the secret *and* be able to write to the  
root hash in order to change the filesystem.

So if I don't truncate the SHA-256 how big does my MAC need to be  
given every ZFS block has its own IV ?

I don't know the answer to this question.  I have a hard time  
understanding if the minimum safe size of the MAC is zero (i.e. you  
don't need it anyway) or a 128 bits (i.e. you rely on the MAC and you  
want 128-bit crypto strength) or something in between.



The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to

hedging our bets -- in case SHA-256 turns out to be insecure

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


We're going to be deploying a new crypto scheme in Tahoe-LAFS next  
year -- the year 2010.  Tahoe-LAFS is used for long-term storage, and  
I won't be surprised if people store files on Tahoe-LAFS in 2010 and  
then rely on the confidentiality and integrity of those files for  
many years or even decades to come.  (People started storing files on  
Tahoe-LAFS in 2008 and so far they show no signs of losing interest  
in the integrity and confidentiality of those files.)

This long-term focus makes Tahoe-LAFS's job harder than the job of  
protecting transient network packets.  If someone figures out in 2020  
or 2030 how to spoof a network transaction that you sent in 2010 (see  
[1]), it'll be far too late to do you any harm, but if they figure  
out in 2030 how to alter a file that you uploaded to a Tahoe-LAFS  
grid in 2010, that might harm you.

Therefore I've been thinking about how to make Tahoe-LAFS robust  
against the possibility that SHA-256 will turn out to be insecure.

A very good way to do this is to design Tahoe-LAFS so that it relies  
as little as possible on SHA-256's security properties.  The property  
that seems to be the hardest for a secure hash function to provide is  
collision-resistance.  We are analyzing new crypto schemes to see how  
many security properties of Tahoe-LAFS we can continue to guarantee  
even if the collision-resistance of the underlying secure hash  
function fails, and similarly for the other properties of the secure  
hash function which might fail [2].

This note is not about that design process, though, but about how to  
maximize the chance that the underlying hash function does provide  
the desired security properties.

We could use a different hash function than SHA-256 -- there are many  
alternatives.  SHA-512 would probably be safer, but it is extremely  
expensive on the cheap, low-power 32-bit ARM CPUs that are one of our  
design targets [3], and the output size of 512 bits is too large to  
fit into Tahoe-LAFS capabilities.  There are fourteen candidates left  
in the SHA-3 contest at the moment.  Several of them have  
conservative designs and good performance, but there is always the  
risk that they will be found to have catastrophic design flaws or  
that a great advance in hash function cryptanalysis will suddenly  
show how to crack them.  Of course, a similar risk applies to SHA-256!

So I turn to the question of how to combine multiple hash functions  
to build a hash function which is secure even if one or more of the  
underlying hash functions turns out to be weak.

I've read several interesting papers on the subject -- such as [4, 5]  
and especially Robust Multi-Property Combiners for Hash Functions  
Revisited by Marc Fischlin, Anja Lehmann, and Krzysztof Pietrzak  
[6].  The good news is that it turns out to be doable!  The latter  
two papers show nice strong theoretical results -- ways to combine  
hash functions so that the resulting combination is as strong or  
stronger than the two underlying hash functions.  The bad news is  
that the proposal in [6] builds a combined function whose output is  
twice the size of the output of a single hash function.  There is a  
good theoretical reason for this [4], but it won't work for our  
practical engineering requirements -- we need hash function outputs  
as small as possible (partially due to usability issues)

The other bad news is that the construction proposed in [6] is  
complicated, underspecified, and for the strongest version of it, it  
imposes a limit on the length of the inputs that you can feed to your  
hash function.  It grows to such complexity and incurs such  
limitations because it is, if I may call it this, too theoretical.   
It is designed to guarantee certain output properties predicated on  
minimal theoretical assumptions about the properties of the  
underlying hash functions.  This is a fine goal, but in practice we  
don't want to pay such a high cost in complexity and performance in  
order to gain such abstract improvement.  We should be able to hedge  
our bets and achieve a comfortable margin of safety with a very  
simple and efficient scheme by making stronger, less formal, but very  
plausible assumptions about the underlying hash functions.  Read on.

I propose the following combined hash function C, built out of two  
hash functions H1 and H2:

C(x) = H1(H1(x) || H2(x))

The first observation is that if H1 is collision-resistant then so is  
C.  In practice I would expect to use SHA-256 for H1, so the  
resulting combiner C[SHA-256, H2] will be at least as strong as  
SHA-256.  (One could even think of this combiner C as just being a  
tricky way to strengthen SHA-256 by using the output of H2(x) as a  
randomized salt -- see [7].)

The next observation is that finding a pair of inputs x1, x2 which  
collide in *both* H1 and in H2 is likely to be much harder than  
finding a pair of inputs that collide in H1 and finding a pair 

Re: Truncating SHA2 hashes vs shortening a MAC for ZFS Crypto

2009-11-02 Thread Zooko Wilcox-O'Hearn

Dear Darren J Moffat:

I don't understand why you need a MAC when you already have the hash  
of the ciphertext.  Does it have something to do with the fact that  
the checksum is non-cryptographic by default ( 
docs/doc/819-5461/ftyue?a=view ), and is that still true?  Your  
original design document [1] said you needed a way to force the  
checksum to be SHA-256 if encryption was turned on.  But back then  
you were planning to support non-authenticating modes like CBC.  I  
guess once you dropped non-authenticating modes then you could relax  
that requirement to force the checksum to be secure.

Too bad, though!  Not only are you now tight on space in part because  
you have two integrity values where one ought to do, but also a  
secure hash of the ciphertext is actually stronger than a MAC!  A  
secure hash of the ciphertext tells whether the ciphertext is right  
(assuming the hash function is secure and implemented correctly).   
Given that the ciphertext is right, then the plaintext is right  
(given that the encryption is implemented correctly and you use the  
right decryption key).  A MAC on the plaintext tells you only that  
the plaintext was chosen by someone who knew the key.  See what I  
mean?  A MAC can't be used to give someone the ability to read some  
data while withholding from them the ability to alter that data.  A  
secure hash can.

One of the founding ideas of the whole design of ZFS was end-to-end  
integrity checking.  It does that successfully now, for the case of  
accidents, using large checksums.  If the checksum is secure then it  
also does it for the case of malice.  In contrast a MAC doesn't do  
end-to-end integrity checking.  For example, if you've previously  
allowed someone to read a filesystem (i.e., you've given them access  
to the key), but you never gave them permission to write to it, but  
they are able to exploit the isses that you mention at the beginning  
of [1] such as Untrusted path to SAN, then the MAC can't stop them  
from altering the file, nor can the non-secure checksum, but a secure  
hash can (provided that they can't overwrite all the way up the  
Merkle Tree of the whole pool and any copies of the Merkle Tree root  

Likewise, a secure hash can be relied on as a dedupe tag *even* if  
someone with malicious intent may have slipped data into the pool.   
An insecure hash or a MAC tag can't -- a malicious actor could submit  
data which would cause a collision in an insecure hash or a MAC tag,  
causing tag-based dedupe to mistakenly unify two different blocks.

So, since you're tight on space, it would be really nice if you could  
tell your users to use a secure hash for the checksum and then  
allocate more space to the secure hash value and less space to the  
now-unnecessary MAC tag.  :-)

Anyway, if this is the checksum which is used for dedupe then  
remember the birthday so-called paradox -- some people may be  
uncomfortable with the prospect of not being able to safely dedupe  
their 2^64-block storage pool if the hash is only 128 bits, for  
example.  :-)  Maybe you could include the MAC tag in the dedupe  

Also, the IVs for GCM don't need to be random, they need only to be  
unique.  Can you use a block number and birth number or other such  
guaranteed-unique data instead of storing an IV?  (Apropos recent  
discussion on the cryptography list [2].)




Your cloud storage provider does not need access to your data.
Tahoe-LAFS --

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to

deterministic random numbers in crypto protocols -- Re: Possibly questionable security decisions in DNS root management

2009-11-01 Thread Zooko Wilcox-O'Hearn

On 2009 Oct 19, at 9:15 , Jack Lloyd wrote:

On Sat, Oct 17, 2009 at 02:23:25AM -0700, John Gilmore wrote:

DSA was (designed to be) full of covert channels.

one can make DSA deterministic by choosing the k values to be HMAC- 
SHA256(key, H(m))

I've noticed people tinkering with (EC) DSA by constraining that  
number k.  For example, Wei Dai's Crypto++ library generates k by  
hashing in the message itself as well as a timestamp into an RNG:

Wei Dai's motivation for this is to deal with the case that there is  
a rollback of the random number generator, which has always been  
possible and nowadays seems increasingly likely because of the rise  
of virtualization.  See also Scott Yilek: 
2009/474 which appears to be a formal argument that this technique is  
secure (but I suspect that Scott Yilek and Wei Dai are unaware of one  
another's work).  Yilek's work is motivated by virtual machines, but  
one should note that the same issues have bedeviled normal old  
physical machines for years.

Since the Dai/Yilek approach also uses an RNG it is still a covert  
channel, but one could easily remove the RNG part and just use the  
hash-of-the-message part.

I'm beginning to think that *in general* when I see a random number  
required for a crypto protocol then I want to either  
deterministically generate it from other data which is already  
present or to have it explicitly provided by the higher-layer  
protocol.  In other words, I want to constrain the crypto protocol  
implementation by forbidding it to read the clock or to read from a  
globally-available RNG, thus making that layer deterministic.

This facilitates testing, which would help to detect implementation  
flaws like the OpenSSL/Debian fiasco.  It also avoids covert channels  
and can avoid relying on an RNG for security.  If the random numbers  
are generated fully deterministically then it can also provide  
engineering advantages because of convergence of the output -- that  
two computations of the same protocol with the same inputs yield the  
same output.

Now, Yilek's paper argues for the security of generating the needed  
random number by hashing together *both* an input random number (e.g.  
from the system RNG) *and* the message.  This is exactly the  
technique that Wei Dai has implemented.  I'm not sure how hard it  
would be to write a similar argument for the security of my proposed  
technique of generating the needed random number by hashing just the  
message.  (Here's a crack at it: Yilek proves that the Dai technique  
is secure even when the system RNG fails and gives you the same  
number more than once, right?  So then let's hardcode the system RNG  
to always give you the random number 4.  QED :-))

Okay, aside from the theoretical proofs, the engineering question  
facing me is What's more likely: RNG failure or novel cryptanalysis  
that exploits the fact that the random number isn't truly random but  
is instead generated, e.g. by a KDF from other secrets?.  No  
contest!  The former is common in practice and the latter is probably  

Minimizing the risk of the latter is one reason why I am so  
interested in KDF's nowadays, such as the recently proposed HKDF: .

On Tuesday,2009-10-20, at 15:45 , Greg Rose wrote:

Ah, but this doesn't solve the problem; a compliant implementation  
would be deterministic and free of covert channels, but you can't  
reveal enough information to convince someone *else* that the  
implementation is compliant (short of using zero-knowledge proofs,  
let's not go there). So a hardware nubbin could still leak  

Good point!  But can't the one who verifies the signature also verify  
that the k was generated according to the prescribed technique?



P.S.  If you read this letter all the way to the end then please let  
me know.  I try to make them short, but sometimes I think they are  
too long and make too many assumptions about what the reader already  
knows.  Did this message make sense?

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to

Re: [tahoe-dev] Bringing Tahoe ideas to HTTP

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

On Wednesday,2009-09-16, at 14:44 , Ivan Krstić wrote:

Yes, and I'd be happy to opine on that as soon as someone told me  
what those important problems are.

The message that you quoted from Brian Warner, which ended with him  
wondering aloud what new applications could be enabled by such  
features, began with him mentioning a specific use case that he cares  
about and sees how to improve: authentication of Mozilla plugins.   
Brian has an admirable habit of documenting the use cases that  
motivate his engineering decisions.  I think in this case he omitted  
some explanation of why he finds the current solution unsatisfactory,  
perhaps because he assumed the audience already shared his view.  (I  
think he mentioned something in his letter like the well-known  
failures of the SSL/CA approach to this problem.)


The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to

Re: how to encrypt and integrity-check with only one key

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

following-up to my own post:

On Monday,2009-09-14, at 10:22 , Zooko Wilcox-O'Hearn wrote:

David-Sarah Hopwood suggested the improvement that the integrity- 
check value V could be computed as an integrity check (i.e. a  
secure hash) on the K1_enc in addition to the file contents.

Oops, that's impossible.  What David-Sarah Hopwood actually said was  
that this would be nice if it were possible, but since it isn't then  
people should pass around the tuple of (v, K1_enc) whenever they want  
to verify the integrity of the ciphertext.



The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to

Re: RNG using AES CTR as encryption algorithm

2009-09-09 Thread Zooko Wilcox-O'Hearn
And while you are at it, please implement these test vectors and  
report to Niels Ferguson:



The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to

Re: so how do *you* manage your keys, then? part 3

2009-09-08 Thread Zooko Wilcox-O'Hearn
[added Cc:, and I added on  
the whitelist so his posts will go through to tahoe-dev even if he  
isn't subscribed]

On Tuesday,2009-09-08, at 5:54 , Kevin Easton wrote:

Possession of the read-cap to the mutable file gives you two  
things: it gives you the symmetric encryption key with which you  
decrypt the file contents, and it gives you the public key with  
which you check a digital signature in order to be sure that the  
file contents were written by an authorized writer.

How do you prevent someone possessing the read-cap for a mutable  
file from rolling the file back to an earlier version that they  
have seen, without the consent of the write-cap possessor(s)?

You don't even need a read-cap to perform a roll-back attack -- if  
you can control the ciphertext that the reader gets, then you can  
give them a copy of an older ciphertext, even if you yourself are  
incapable of decrypting it.  This is a difficult attack to defend  
against.  In the current version of Tahoe-LAFS we already have one  
interesting defense -- we the reader is communicating with many  
different servers, and if *any* of the servers is honest and up-to- 
date and informs the reader about the existence of a newer version,  
then the reader knows that the older version that he can read is not  
the latest.  Readers in Tahoe-LAFS always download shares of the file  
from multiple servers, and all of the servers that it uses would have  
to agree on the version number.  Therefore, to perform a rollback  
attack you need to control at least that many servers as well as you  
have to control or deny-access-to any other servers which the reader  
would query and which would inform him about the newer version  
number.  See section 5 of [1].

Does that answer your question about rollback?

It would be interesting to build stronger defenses against rollback  
attack.  For starters, if the same reader reads the same file  
multiple times and gets new contents each time, he might as well  
remember the version number so that he will detect whether that file  
rolled back during his inspection of it.  Also, it would be  
interesting if a file handle to a mutable file included the version  
number that the mutable file was at when the file handle was  
created.  Building on that, it would be really cool if, in a future  
version of Tahoe-LAFS, we could make it so that you can take a cheap  
snapshot of the current contents and then give someone a file-handle  
which *both* securely identified the most recent version that you  
can find of this file and *also* the specific (immutable) version  
of this file that existed when I created this file-handle.

Also, am I correct in assuming that once write-caps have been  
distributed, they cannot be revoked, and a new file handle must be  

Currently, yes.  An improvement that I would like to make in the next  
version of Tahoe-LAFS is to allow the holder of a write-cap to revoke  
it.  While some kinds of revocation are tantamount to DRM (Digital  
Restrictions Management) and seem to be sufficiently difficult that  
we're not even going to try to implement them, the specific kind of  
revocation that you asked about seems to be quite doable.  Also, it  
happens to be the kind of revocation that I have already wanted for  
my own personal use of Tahoe-LAFS (to host my blog).  :-)

Here is a letter about that which explains why I needed this and how  
I envision it working: [2]

Stronger defenses against rollback attack, and revocation of write- 
caps -- these are only a few of the many possible extensions to the  
Tahoe-LAFS secure storage design.  We have a rich library of such  
designs documented on our issue tracker and our wiki.  We are  
currently having a detailed design discussion on the tahoe-dev list  
to which several cryptographers are contributing [e.g. 3, 4].  The  
primary goal for the next version of Tahoe-LAFS caps is to reduce the  
size of the caps and improve performance, but we're also cataloguing  
new features such as these to see if we can work them in.  Here is  
the wiki page where we're keeping our notes: [5].

If any smart cryptographer or hacker reading this wants to create  
secure, decentralized storage, please join us!  We could use the  
help!  :-)




The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to

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  

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://

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



The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to

so how do *you* manage your keys, then? part 3

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

So How Do You Manage Your Keys Then, part 3 of 5

In part one of this series [1] I described how Tahoe-LAFS combines  
decryption, integrity-checking, identification, and access into one  
bitstring, called an immutable file read-cap (short for  
capability).  In part two [2] I described how users can build tree- 
like structures of files which contain caps pointing to other files,  
and how the cap pointing to the root of such a structure can reside  
on a different computer than the ciphertext.  (Which is necessary if  
you want someone to store the ciphertext for you but you don't want  
to give them the ability to read the file contents.)

In this installment, consider the question of whether you can give  
someone a cap (which acts as a file handle) and then change the  
contents of the file that the cap points to, while preserving their  
ability to read with the original cap.

This would be impossible with the immutable file read-caps that we  
have been using so far, because each immutable file read cap uses a  
secure hash function to identify and integrity-check exactly one  
file's contents -- one unique byte pattern.  Any change to the file  
contents will cause the immutable file read-cap to no longer match.   
This can be a desirable property if what you want is a permanent  
identifier of one specific, immutable file.  With this property  
nobody -- not even the person who wrote the file in the first place  
-- is able to cause anyone else's read-caps to point to any file  
contents other than the original file contents.

But sometimes you want a different property, namely that an  
authorized writer *can* change the file contents and readers will be  
able to read the new file contents without first having to acquire a  
new file handle.

To accomplish this requires the use of public key cryptography,  
specifically digital signatures.  Using digital signatures, Tahoe- 
LAFS implements a second kind of capability, in addition to the  
immutable-file capability, which is called a mutable file  
capability.  Whenever you create a new mutable file, you get *two*  
caps to it: a write-cap and a read-cap.  (Actually you can always  
derive the read-cap from the write-cap, so for API simplicity you get  
just the write-cap to your newly created mutable file.)

Possession of the read-cap to the mutable file gives you two things:  
it gives you the symmetric encryption key with which you decrypt the  
file contents, and it gives you the public key with which you check a  
digital signature in order to be sure that the file contents were  
written by an authorized writer.  The decryption and signature  
verification both happen automatically whenever you read data from  
that file handle (it downloads the digital signature which is stored  
with the ciphertext).

Possession of the write-cap gives two things: the symmetric key with  
which you can encrypt the ciphertext, and the private key with which  
you can sign the contents.  Both are done automatically whenever you  
write data to that file handle.

The important thing about this scheme is that what we crypto geeks  
call key management is almost completely invisible to the users.   
As far as the users can tell, there aren't any keys here!  The only  
objects in sight are the file handles, which they already use all the  

All users need to know is that a write-cap grants write authority  
(only to that one file), and the read-cap grants read authority.   
They can conveniently delegate some of their read- or write-  
authority to another user, simply by giving that user a copy of that  
cap, without delegating their other authorities. They can bundle  
multiple caps (of any kind) together into a file and then use the  
capability to that file as a handle to that bundle of authorities.

At least, this is the theory that the object-capability community  
taught me, and I'm pleased to see that -- so far -- it has worked out  
in practice.

Programmers and end users appear to have no difficulty understanding  
the access control consequences of this scheme and then using the  
scheme appropriately to achieve their desired ends.

Installment 4 of this series will be about Tahoe-LAFS directories  
(those are the most convenient way to bundle together multiple caps  
-- put them all into a directory and then use the cap which points to  
that directory).  Installment 5 will be about future work and new  
crypto ideas.



# installment 1: immutable file caps
# installment 2: tree-like structure (like encrypted git)

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to

a crypto puzzle about digital signatures and future compatibility

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


My brother Nathan Wilcox asked me in private mail about protocol  
versioning issues.  (He was inspired by this thread on [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  

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,  


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?





The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to

Tahoe-LAFS key management, part 2: Tahoe-LAFS is like encrypted git

2009-08-19 Thread Zooko Wilcox-O'Hearn
Okay, in today's installment I'll reply to my friend Kris Nuttycombe,  
who read yesterday's installment and then asked how the storage  
service provider could provide access to the files without being able  
to see their filehandles and thus decrypt them.

I replied that the handle could be stored in another file on the  
server, and therefore encrypted so that the server couldn't see it.   
You could imagine taking a bunch of these handles -- capabilities to  
read an immutable file -- and putting them into a new file and  
uploading to the Tahoe-LAFS grid.  Uploading it would encrypt it and  
give you a capability to that new file.  The storage service provider  
wouldn't be able to read the contents of that file, so it wouldn't be  
able to read the files that it references.  This forms a  
Cryptographic Hash Function Directed Acyclic Graph structure, which  
should be familiar to many readers as the underlying structure in git  
[*].  Git uses this same technique of combining identification and  
integrity-checking into one handle.

From this perspective, Tahoe-LAFS can be seen as like git, and use  
the handle for encryption in addition to integrity-checking and  

(There are many other differences.  For starters git has a high- 
performance compression scheme and it has a decentralized revision  
control tool built on top.  Tahoe-LAFS has erasure-coding and a  
distributed key-value store for a backend.)

Okay, the bus is arriving at work.

Oh, so then Kris asked But what about the root of that tree?.  The  
answer is that the capability to the root of that tree is not stored  
on the servers.  It is held by the client, and never transmitted to  
the storage servers.  It turns out that storage servers don't need  
the capability to the file in order to serve up the ciphertext.   
(Technically, they *do* need an identifier, and ideally they would  
also have the integrity-checking part so that they could perform  
integrity checks on the file contents (in addition to clients  
performing that integrity check for themselves).  So the capability  
gets split into its component parts during the download protocol,  
when the client sends the identification and integrity-checking bits  
to the server but not the decryption key, and receives the ciphertext  
in reply.)

Therefore the next layer up, whether another program or a human user,  
needs to manage this single capability to the root of a tree.  Here  
the abstraction-piercing problem of availability versus  
confidentiality remains in force, and different programs and  
different human users have different ways to manage their caps.  I  
personally keep mine in my bookmarks in my web browser.  This is  
risky -- they could be stolen by malicious Javascript (probably) or I  
might accidentally leak them in an HTTP Referer header.  But it is  
very convenient.  For the files in question I value that convenience  
more than an extra degree of safety.  I know of other people who keep  
their Tahoe-LAFS caps more securely, on Unix filesystems, on  
encrypted USB keys, etc..



[*] Linus Torvalds got the idea of a Cryptographic Hash Function  
Directed Acyclic Graph structure from an earlier distributed revision  
control tool named Monotone.  He didn't go out of his way to give  
credit to Monotone, and many people mistakenly think that he invented  
the idea.

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to

Re: [tahoe-dev] Tahoe-LAFS key management, part 2: Tahoe-LAFS is like encrypted git

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

On Wednesday,2009-08-19, at 10:05 , Jack Lloyd wrote:

On Wed, Aug 19, 2009 at 09:28:45AM -0600, Zooko Wilcox-O'Hearn wrote:

[*] Linus Torvalds got the idea of a Cryptographic Hash Function  
Directed Acyclic Graph structure from an earlier distributed  
revision control tool named Monotone.

OT trivia: The idea actually predates either monotone or git;  
opencm ( was using a similiar technique  
for VCS access control a year or two prior to monotone's first  

Note that I didn't say Monotone invented it.  :-)  Graydon Hoare of  
Monotone got the idea from a friend of his who, as far as we know,  
came up with it independently.  I personally got it from Eric Hughes  
who came up with it independently.  I think OpenCM got it from the  
Xanadu project who came up with it independently.  :-)



The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to

strong claims about encryption safety Re: [tahoe-dev] cleversafe says: 3 Reasons Why Encryption isOverrated

2009-08-12 Thread Zooko Wilcox-O'Hearn
[removing Cc: tahoe-dev as this subthread is not about Tahoe-LAFS.   
Of course, the subscribers to tahoe-dev would probably be interested  
in this subthread, but that just goes to show that they ought to  
subscribe to]

On Monday,2009-08-10, at 11:56 , Jason Resch wrote:

I don't think there is any basis to the claims that Cleversafe  
makes that their erasure-coding (Information Dispersal)-based  
system is fundamentally safer, e.g. these claims from [3]: a  
malicious party cannot recreate data from a slice, or two, or  
three, no matter what the advances in processing power. ...  
Maybe encryption alone is 'good enough' in some cases now  - but  
Dispersal is 'good always' and represents the future.

It is fundamentally safer in that even if the transformation key  
were brute forced, the attacker only gains data from the slice,  
which in general will have 1/threshold the data.

Okay, so the Cleversafe method of erasure-coding ciphertext and  
storing the slices on different servers is safer in exactly the  
same way that encrypting and then giving an attacker only a part of  
the ciphertext is safer.  That is: having less ciphertext might  
hinder cryptanalysis a little, and also even if the attacker totally  
wins and is able to decrypt the ciphertext, at least he'll only get  
part of the plaintext that way.  On the other hand I might consider  
it scant comfort if I were told that the good news is that the  
attacker was able to read only the first 1/3 of each of your  
files.  :-)

But the Cleversafe method of appending the masked key to the last  
slice makes it less safe, because having the masked key might help a  
cryptanalyst quite a lot.

In any case, the claims that are made on the Cleversafe web site are  
wrong and misleading: a malicious party cannot recreate data from a  
slice, or two, or three, no matter what the advances in processing  
power [1].  It is easy for customers to believe this claim, because  
an honest party who is following the normal protocol is limited in  
this way and because information-theoretically-secure secret-sharing  
schemes have this property.  I kind of suspect that the Cleversafe  
folks got confused at some point by the similarities between their  
AONT+erasure-coding scheme and a secret-sharing scheme.

In any case, the statement quoted above is not true, and not only  
that isolated statement, but also the entire thrust of the  
encryption isn't safe but Cleversafe's algorithm is safer argument  
[2].  Just to pick out another of the numerous examples of misleading  
and unjustified claims along these lines, here is another: Given  
that the level of security provided by the AONT can be set  
arbitrarily high (there is no limit to the length of key it uses for  
the transformation), information theoretic security is not necessary  
as one can simply use a key so long that it could not be cracked  
before the stars burn out. [3].

On the other hand Cleversafe's arguments about key management being  
hard and about there being a trade-off between confidentiality and  
availability are spot on: [3].  Although I don't think that their  
strategy for addressing the key management issues is the best  
strategy, at least their description of the problem are correct.   
Also, if you ignore the ill-justified claims about security on that  
page, their explanation of the benefits of their approach is  
correct.  (Sorry if this comes off as smug -- I'm trying to be fair.)

(I'm not even going to address their third point [4] -- at least not  
until we take this conversation to the law mailing list! :-))

Okay, I think I've made my opinion about these issues fairly clear  
now, so I'll try to refrain from following-up to this subthread --  
the strong claims about encryption safety subthread -- unless there  
are some interesting new technical details that I haven't thought  
of.  By the way, when googling in the attempt to learn more  
information about the Cleversafe algorithm, I happened to see that  
Cleversafe is mentioned in this paper by Bellare and Rogaway: Robust  
Computational Secrete Sharing and a Unified Account of Classical  
Secret-Sharing Goals [5].  I haven't read that paper yet, but given  
the authors I would assume it is an excellent starting point for a  
modern study of the cryptographic issues.  :-)

I still do intend to follow-up on the subthread which I call So how  
do *you* do key management, then?, which I consider to be the most  
important issue for practical security of systems like these.


Zooko, writing e-mail on his lunch break


The Cryptography Mailing List
Unsubscribe by sending 

Re: [tahoe-dev] cleversafe says: 3 Reasons Why Encryption isOverrated

2009-08-11 Thread Zooko Wilcox-O'Hearn
This conversation has bifurcated, since I replied and removed tahoe- 
dev from the Cc: line, sending just to the cryptography list, and  
David-Sarah Hopwood has replied and removed cryptography, leaving  
just the tahoe-dev list.

Here is the root of the thread on the cryptography mailing list archive:

Here it is on the tahoe-dev mailing list archive.  Note that  
threading is screwed up in our mailing list archive.  :-(



The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to

Re: [tahoe-dev] cleversafe says: 3 Reasons Why Encryption isOverrated

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

On Monday,2009-08-10, at 13:47 , Zooko Wilcox-O'Hearn wrote:

This conversation has bifurcated,

Oh, and while I don't mind if people want to talk about this on the  
tahoe-dev list, it doesn't have that much to do with tahoe-lafs  
anymore, now that we're done comparing Tahoe-LAFS to Cleversafe and  
are just arguing about the cryptographic design of Cleversafe.  ;-)   
So, it seems quite topical for the cryptography list and only  
tangentially topical for the tahoe-dev list.  I've also been enjoying  
the subthread about the physical limits of computation that have  
spawned off on the cryptography mailing list.  Ooh, were you guys  
considering only classical computers and not quantum computers when  
you estimated that either 2^128, 2^200 or 2^400 was the physical  
limit of possible computation?  :-)



The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to

Re: cleversafe says: 3 Reasons Why Encryption is Overrated

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

[dropping tahoe-dev from Cc:]

On Thursday,2009-08-06, at 2:52 , Ben Laurie wrote:

Zooko Wilcox-O'Hearn wrote:
I don't think there is any basis to the claims that Cleversafe  
makes that their erasure-coding (Information Dispersal)-based  
system is fundamentally safer

Surely this is fundamental to threshold secret sharing - until you  
reach the threshold, you have not reduced the cost of an attack?

I'm sorry, I don't understand your sentence.  Cleversafe isn't using  
threshold secret sharing -- it is using All-Or-Nothing-Transform  
(built out of AES-256) followed by Reed-Solomon erasure-coding.  The  
resulting combination is a computationally-secure (not information- 
theoretically-secure) secret-sharing scheme.  The Cleversafe  
documentation doesn't use these terms and is not precise about this,  
but it seems to claim that their scheme has security that is somehow  
better than the mere computational security that encryption typically  

Oh wait, now I understand your sentence.  You in your sentence is  
the attacker.  Yes, an information-theoretically-secure secret- 
sharing scheme does have that property.  Cleversafe's scheme hasn't.



The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to

Re: cleversafe says: 3 Reasons Why Encryption is Overrated

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

[dropped tahoe-dev from Cc:]

On Thursday,2009-08-06, at 17:08 , james hughes wrote:

Until you reach the threshold, you do not have the information to  
attack. It becomes information theoretic secure.

This is true for information-theoretically secure secret sharing, but  
not true for Cleversafe's technique of composing an All-Or-Nothing- 
Transform with Reed-Solomon erasure coding.

CleverSafe can not provide any security guarantees unless these  
questions can be answered. Without answers, CleverSafe is neither  
Clever nor Safe.

Hey, let's be nice.  Cleversafe has implemented a storage system  
which integrates encryption in the attempt to make it safer.  They  
GPL at least some of their work [*], and they publish their ideas and  
engage in discussion about them.  These are all good things.  My  
remaining disagreements with them are like this:

1.  (The important one.)  I don't think the access control policy of  
whoever can access at least K of the N volumes of data is the  
access control policy that I want.  For one thing, it immediately  
leads to the questions that James Hughes was asking, about who is  
authorized to access what servers.  For another thing, I would really  
like my access control policy to be fine-grained, flexible, and  
dynamic.  So for example, I'd like to be able to give you access two  
three of my files but not all my other files, and I'd like you to  
then be able to give your friend access to two of those files but not  
the third.  See Brian Warner's and Jason Resch's discussion of these  
issues: [1, 2].

2.  Cleversafe seems to think that their scheme gives better-than- 
computational security, i.e. that it guarantees security even if  
AES-256 is crackable.  This is wrong, but it is an easy mistake to  
make!  Both Ben Laurie and James Hughes have jumped to the conclusion  
(in this thread) that the Cleversafe K-out-of-N encoding has the same  
information-theoretic security that secret-sharing K-out-of-N  
encoding has.

3.  Cleversafe should really tone down the Fear Uncertainty and Doubt  
about today's encryption being mincemeat for tomorrow's  
cryptanalysts.  It might turn out to be true, but if so it will be  
due to cryptanalytic innovations more than due to Moore's Law.  And  
it might not turn out like that -- perhaps AES-256 will remain safe  
for centuries.  Also, Cleversafe's product is not more secure than  
any other product against this threat.

It is hard to explain to non-cryptographers how much they can rely on  
the security of cryptographic schemes.  It's very complicated, and  
most schemes deployed have failed due to flaws in the surrounding  
system, engineering errors or key management (i.e. access control)  
problems.  Nobody knows what cryptanalytic techniques will be  
invented in the future.  My opinion is that relying on well- 
engineered strong encryption to protect your data is at least as safe  
alternatives such as keeping the data on your home computer or on  
your corporate server.  The Cleversafe FUD doesn't help people  
understand the issues better.




[*] Somebody stated on a mailing list somewhere that Cleversafe has  
applied for patents.  Therefore, if you want to use their work under  
the terms of the GPL, you should also be aware that if their patents  
are granted then some of what you do may be subject to the patents.   
Of course, this is always true of any software (the techniques might  
be patented), but I thought it was worth mentioning since in this  
case the company authoring the software is also the company applying  
for patents.

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to

Re: cleversafe says: 3 Reasons Why Encryption is Overrated

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

[cross-posted to and]


It doesn't look like I'm going to get time to write a long post about  
this bundle of issues, comparing Cleversafe with Tahoe-LAFS (both use  
erasure coding and encryption, and the encryption and key-management  
part differs), and arguing against the ill-advised Fear, Uncertainty,  
and Doubt that the Cleversafe folks have posted.  So, I'm going to  
try to throw out a few short pieces which hopefully each make sense.

First, the most important issue in all of this is the one that my  
programming partner Brian Warner already thoroughly addressed in [1]  
(see also the reply by Jason Resch [2]).  That is the issue of access  
control, which is intertwined with the issues of key management.  The  
other issues are cryptographic details which are important to get  
right, but the access control and key management issues are the ones  
that directly impact every user and that make or break the security  
and usefulness of the system.

Second, the Cleversafe documents seem to indicate that the security  
of their system does not rely on encryption, but it does.  The data  
in Cleversafe is encrypted with AES-256 before being erasure-coded  
and each share stored on a different server (exactly the same as in  
Tahoe-LAFS).  If AES-256 is crackable, then a storage server can  
learn information about the file (exactly as in Tahoe-LAFS).  The  
difference is that Cleversafe also stores the decryption key on the  
storage servers, encoded in such a way that  any K of the storage  
servers must cooperate to recover it.  In contrast, Tahoe-LAFS  
manages the decryption key separately.  This added step of including  
a secret-shared copy of the decryption key on the storage servers  
does not make the data less vulnerable to weaknesses in AES-256, as  
their documents claim.  (If anything, it makes it more vulnerable,  
but probably it has no effect and it is just as vulnerable to  
weaknesses in AES-256 as Tahoe-LAFS is.)

Third, I don't understand why Cleversafe documents claim that public  
key cryptosystems whose security is based on math are more likely  
to fall to future advances in cryptanalysis.  I think most  
cryptographers have the opposite belief -- that encryption based on  
bit-twiddling such as block ciphers or stream ciphers is much more  
likely to fall to future cryptanalysis.  Certainly the history of  
modern cryptography seems to fit with this -- of the original crop of  
public key cryptosystems founded on a math problem, some are still  
regarded as secure today (RSA, DH, McEliece), but there has been a  
long succession of symmetric crypto primitives based on bit twiddling  
which have then turned out to be insecure.  (Including, ominously  
enough, AES-256, which was regarded as a gold standard until a few  
months ago.)

Fourth, it seems like the same access control/key management model  
that Cleversafe currently offers could be achieved by encrypting the  
data with a random AES key and then using secret sharing to split the  
key and store on share of the key with each server.  I *think* that  
this would have the same cryptographic properties as the current  
Cleversafe approach of using an All-Or-Nothing-Transform followed by  
erasure coding.  Both would qualify as computation secret sharing  
schemes as opposed to information-theoretic secret sharing  
schemes.  I would be curious if there are any significant differences  
between these two constructions.

I don't think there is any basis to the claims that Cleversafe makes  
that their erasure-coding (Information Dispersal)-based system is  
fundamentally safer, e.g. these claims from [3]: a malicious party  
cannot recreate data from a slice, or two, or three, no matter what  
the advances in processing power. ... Maybe encryption alone is  
'good enough' in some cases now  - but Dispersal is 'good always' and  
represents the future.

Fifth, as I've already mentioned, the emphasis on cryptography being  
defeated due to advances in processing power e.g. reference to  
Moore's Law is confused.  Advances in processing power would not be  
sufficient to crack modern cryptosystems and in many cases would not  
be necessary either.

Okay I think that's it.  I hope these notes are not so terse as to be  
confusing or inflammatory.


Zooko Wilcox-O'Hearn


The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to

Re: Fast MAC algorithms?

2009-08-02 Thread Zooko Wilcox-O'Hearn
I recommend Poly1305 by DJB or VMAC by Ted Krovetz and Wei Dai.  Both  
are much faster than HMAC and have security proven in terms of an  
underlying block cipher.

VMAC is implemented in the nice Crypto++ library by Wei Dai, Poly1305  
is implemented by DJB and is also in the new nacl library by DJB.

Says that VMAC(AES)-64 takes 0.6 cycles per byte (although watch out  
for that 3971 cycles to set up key and IV), compared to HMAC-SHA1  
taking 11.2 cycles per byte (after 1218 cycles to set up key and IV).

If you do any measurement comparing Poly1305 to VMAC, please report  
your measurement, at least to me privately if not to the list.  I can  
use that sort of feedback to contribute improvements to the Crypto++  
library.  Thanks!


Zooko Wilcox-O'Hearn
Tahoe, the Least-Authority Filesystem --
store your data: $10/month --
I am available for work --ésumé.html

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to

ANNOUNCING Tahoe, the Lofty-Atmospheric Filesystem, v1.5

2009-08-02 Thread Zooko Wilcox-O'Hearn
 and public-spirited support.

This is the second release of Tahoe-LAFS which was created solely as a
labor of love by volunteers; developer time is no longer funded by (see [13] for details).

Zooko Wilcox-O'Hearn
on behalf of the Tahoe-LAFS team

Special acknowledgment goes to Brian Warner, whose superb engineering
skills and dedication are primarily responsible for the Tahoe
implementation, and significantly responsible for the Tahoe design as
well, not to mention most of the docs and tests. Tahoe-LAFS wouldn't
exist without him.

August 1, 2009
Boulder, Colorado, USA

P.S.  Just kidding about that acronym.  LAFS actually stands for
Lightweight Authorization File System.  Or possibly for
Least-Authority File System.  There is no truth to the rumour that it
actually stands for Long-lived Axe-tolerant File System.


The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to

Re: cleversafe says: 3 Reasons Why Encryption is Overrated

2009-07-31 Thread Zooko Wilcox-O'Hearn


Over on the Tahoe-LAFS mailing list Brian Warner gave a typically  
thoughtful, thorough, and precise analysis of cleversafe access  
control as contrasted with Tahoe-LAFS access control.  Brian  
attempted to cross-post it to this list, but it bounced since he is  
not a subscriber.

Jason Resch of cleversafe has also been participating in the  
discussion on that list.



The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to

cleversafe says: 3 Reasons Why Encryption is Overrated

2009-07-24 Thread Zooko Wilcox-O'Hearn

[cross-posted to and]

Disclosure:  Cleversafe is to some degree a competitor of my Tahoe- 
LAFS project.  On the other hand, I tend to feel positive towards  
them because they open-source much of their work.  Our Related  
Projects page has included a link to cleversafe for years now, I  
briefly collaborated with some of them on a paper about erasure  
coding last year, and I even spoke briefly with them about the idea  
of becoming an employee of their company this year.  I am tempted to  
ignore this idea that they are pushing about encryption being  
overrated, because they are wrong and it is embarassing.  But I've  
decided not to ignore it, because people who publicly spread this  
kind of misinformation need to be publicly contradicted, lest they  
confuse others.

Cleversafe has posted a series of blog entries entitled 3 Reasons  
Why Encryption is Overrated. # 3 Reasons Why Encryption is  
Overrated # Response Part 1: Future  
Processing Power # Response Part 2:  
Complexities of Key Management # Response Part 3: Disclosure  

It begins like this:

When it comes to storage and security, discussions traditionally  
center on encryption.  The reason encryption – or the use of a  
complex algorithm to encode information – is accepted as a best  
practice rests on the premise that while it’s possible to crack  
encrypted information, most malicious hackers don’t have access to  
the amount of computer processing power they would need to decrypt  

But not so fast.  Let’s take a look at three reasons why encryption  
is overrated.


The first claim -- the today's encryption is vulnerable to tomorrow's  
processing power -- is a common goof, which is easy to make by  
conflating historical failures of cryptosystems due to having too  
small of a crypto value with failures due to weak algorithms.   
Examples of the former are DES, which failed because its 56-bit key  
was small enough to fall to brute force, and the bizarre 40-bit  
security policies of the U.S. Federal Government in the 90's.  An  
example of the latter is SHA1, whose hash output size is *not* small  
enough to brute-force, but which is insecure because, as it turns  
out, the SHA1 algorithm allows the generation of colliding inputs  
much quicker than a brute force search would.

Oh boy, I see that in the discussion following the article Future  
Processing Power, the author writes:

I don’t think symmetric ciphers such as AES-256 are under any threat  
of being at risk to brute force attacks any time this century.

What?  Then why is he spreading this Fear, Uncertainty, and Doubt?   
Oh and then it gets *really* interesting: it turns out that  
cleversafe uses AES-256 in an All-or-Nothing Transform as part of  
their Information Dispersal algorithm.  Okay, I would like to  
understand better the cryptographic effects of that (and in  
particular, whether this means that the cleversafe architecture is  
just as susceptible to AES-256 failing as an encryption scheme such  
as is used in the Tahoe-LAFS architecture).

But, it is time for me to stop reading about cryptography and get  
ready to go to work.  :-)


Tahoe, the Least-Authority Filesystem --
store your data: $10/month --
I am available for work --ésumé.html
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to

Re: 112-bit prime ECDLP solved

2009-07-20 Thread Zooko Wilcox-O'Hearn

On Sunday,2009-07-19, at 13:24 , Paul Hoffman wrote:

At 7:54 AM -0600 7/18/09, Zooko Wilcox-O'Hearn wrote:
This involves deciding whether a 192-bit elliptic curve public key  
is strong enough...

Why not just go with 256-bit EC (128-bit symmetric strength)? Is  
the 8 bytes per signature the issue, or the extra compute time?

Those are two good guesses, but no.  The main concern is the size of  
the public key.  This is why (if I understand correctly),  
hyperelliptic curves might eventually offer public key signatures  
which are twice as good for the purposes of TahoeLAFS as elliptic  
curves.  (By which I mean, the keys are half as big.)  I discussed  
this topic a bit in a subsequent message to the cryptography mailing  
list entitled Why hyperelliptic curves?.

Actually, the computation time matters, too.  Our measurements on an  
ARM 266 MHz embedded system showed a significant penalty for 256-bit  
ECDSA vs. 192-bit:



The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to

Re: 112-bit prime ECDLP solved

2009-07-19 Thread Zooko Wilcox-O'Hearn
By the way, we've recently been planning our next crypto-capabilities  
design for the TahoeLAFS secure distributed filesystem.  This  
involves deciding whether a 192-bit elliptic curve public key is  
strong enough, as well as subtler and more unusual issues involving  
embedding keys directly into filehandles or URLS, multiple-targets  
attacks, and a novel public key scheme that I invented (and that  
therefore I think we shouldn't use):

Your comments would be appreciated!  I've added and to the list of  
addresses that can post to tahoe-dev without being subscribed.



The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to

why hyperelliptic curves?

2009-07-19 Thread Zooko Wilcox-O'Hearn
Oh, and by the way the way that TahoeLAFS uses public key  
cryptography highlights some of the weaknesses of current public key  
techniques and some of the strengths of possible future techniques  
such as hyperelliptic curves.  (I know that Tanja Lange has done a  
lot of work on those.)

TahoeLAFS generates a unique public-private key pair for each mutable  
file and each directory.  (Immutable files don't use public key  
cryptography at all -- they are secured solely with a stream cipher  
and secure hashes.)  The file handle or capability to a mutable  
file or directory contains the actual public key (if it is a read- 
only capability) or the actual private key (if it is a read-write  
capability).  Therefore some of our most important measures of  
performance are public key size and keypair generation time.   
Unfortunately, we blundered into using one of the worst possible  
public key signature algorithms for such requirements: RSA!  Our  
current project is replacing RSA with ECDSA.  TahoeLAFS v2.0 will  
support ECDSA-based capabilities (in addition to RSA-based ones for  
backward compatibility).

TahoeLAFS also requires more than two levels of privilege.  With  
traditional public/private keys there are exactly two levels: you  
either know the private key or you don't.  We need to have an  
intermediate level of privilege -- someone who doesn't know the  
private key but who does know something that not everyone knows.   
(Everyone knows the public key.)  We use these three levels of  
privilege to create read-write capabilities, read-only capabilities  
and verify capabilities.   (A verify capability gives the ability to  
check integrity of the ciphertext, which everyone has, because  
everyone knows the public key).  If this doesn't make sense to you  
then see if my longer explanation in lafs.pdf makes any more sense.

Anyway, if it is true that hyperelliptic curves have a security level  
commensurate with the number of bits in the public key, then  
hyperelliptic curves with semi-private keys would be the ideal public  
key crypto signature scheme for TahoeLAFS.  Unfortunately, semi- 
private keys aren't proven secure nor properly peer-reviewed, and  
hyperelliptic curves aren't well implemented or widely appreciated.   
Hopefully someday TahoeLAFS v3.0 will support semi-private- 
hyperelliptic-curve-based capabilities (in addition to RSA and ECDSA  
for backward compatibility).


Zooko Wilcox-O'Hearn

P.S.  Oh, I told a lie in the interests of brevity when I said that  
file handles contain actual public keys or actual private keys.  RSA  
keys are way too big for that.  So instead we go through interesting  
contortions to make a surrogate value which can be used to check  
the correctness of the RSA key (i.e. the surrogate value is derived  
from the RSA key by secure hashing) as well as can be used to control  
access to the RSA key (the RSA key is encrypted with a stream cipher  
using the surrogate value as the symmetric encryption key).  The  
surrogate value therefore offers the same integrity and access  
control properties as the RSA key itself (when the user also has  
access to the encrypted RSA key itself), but it is sufficiently short  
to embed directly into the file handles a.k.a. capabilities.  This  
too is explained more fully in lafs.pdf.


The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to

Re: Warning! New cryptographic modes!

2009-05-22 Thread Zooko Wilcox-O'Hearn
For what it is worth, in the Tahoe-LAFS project [1] we simply use CTR  
mode and a unique key for each file.  Details: [2]

Tahoe-LAFS itself doesn't do any deltas, compression, etc., but there  
are two projects layered atop Tahoe to add such features -- a plugin  
for duplicity [3] and a new project named GridBackup [4].

Those upper layers can treat the Tahoe-LAFS as a secure store of  
whole files and therefore don't have to think about details like  
cipher modes of operation, nor do they even have to think very hard  
about key management, thanks to Tahoe-LAFS's convenient capability- 
based access control scheme.




The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to