Tahoe-LAFS key management, part 2: Tahoe-LAFS is like encrypted git
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 identification. (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.. Regards, Zooko [*] 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 majord...@metzdowd.com
Re: [tahoe-dev] Tahoe-LAFS key management, part 2: Tahoe-LAFS is like encrypted git
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. He didn't go out of his way to give credit to Monotone, and many people mistakenly think that he invented the idea. OT trivia: The idea actually predates either monotone or git; opencm (http://opencm.org/docs.html) was using a similiar technique for VCS access control a year or two prior to monotone's first release. AFAIK Graydon Hoare (the original monotone designer) came up with the technique independently of the opencm design. I'm actually not certain that opencm originated the technique, either; all I can say for certain is that it was using it prior to monotone or git. -Jack - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: [tahoe-dev] Tahoe-LAFS key management, part 2: Tahoe-LAFS is like encrypted git
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 (http://opencm.org/docs.html) was using a similiar technique for VCS access control a year or two prior to monotone's first release. 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. :-) Regards, Zooko - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: [tahoe-dev] Tahoe-LAFS key management, part 2: Tahoe-LAFS is like encrypted git
Zooko Wilcox-O'Hearn zo...@zooko.com writes: 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 (http://opencm.org/docs.html) was using a similiar technique for VCS access control a year or two prior to monotone's first release. 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 whole thing simply seems like a very obvious use of Merkle hash trees. It is very understandable that many people familiar with Merkle trees and related structures would think to apply them this way, since it is more or less the purpose for which they were intended. Perry - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Crypto '09 rump session summary?
Watching the rump session online briefly last night, I saw that some interesting new results on MD5 and AES seem to have been discussed at the conference. Would anyone care to give us a brief overview for the mailing list? Perry -- Perry E. Metzgerpe...@piermont.com - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: [tahoe-dev] Tahoe-LAFS key management, part 2: Tahoe-LAFS is like encrypted git
[*] 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 (http://opencm.org/docs.html) was using a similiar technique for VCS access control a year or two prior to monotone's first release. 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. :-) Getting back towards topic, the hash function employed by Git is showing signs of bitrot, which, given people's desire to introduce malware backdoors and legal backdoors into Linux, could well become a problem in the very near future. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
SHA-1 and Git (was Re: [tahoe-dev] Tahoe-LAFS key management, part 2: Tahoe-LAFS is like encrypted git)
James A. Donald jam...@echeque.com writes: Getting back towards topic, the hash function employed by Git is showing signs of bitrot, which, given people's desire to introduce malware backdoors and legal backdoors into Linux, could well become a problem in the very near future. I believe attacks on Git's use of SHA-1 would require second pre-image attacks, and I don't think anyone has demonstrated such a thing for SHA-1 at this point. None the less, I agree that it would be better if Git eventually used better hash functions. Attacks only get better with time, and SHA-1 is certainly creaking. Emphasis on eventually, however. This is a as soon as convenient, not as soon as possible sort of situation -- more like within a year than within a week. Yet another reason why you always should make the crypto algorithms you use pluggable in any system -- you *will* have to replace them some day. Perry -- Perry E. Metzgerpe...@piermont.com - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Crypto '09 rump session summary?
Target collisions for MD5 can be calculated in seconds on a laptop, based on just a small change in the first block of input. There was also a semi-successful demo of MD5 certificate problems; you could join the special wireless network, and any https connection would be silently proxied using the fake CA certificate generated a few months ago. (You had to set your clock back to 2004, though, since the CA certificate was intentionally generated to be long expired). The SHA-1 attack complexity of 2^52 was a correct improvement to an incorrect result. Don't currently have an accurate estimate; IIUC it's bounded above by 2^56. The related-key attacks on AES have been extended to AES-192, and also to some sort of non-standard AES-128, but it wasn't clear to me what it was that they did. AES-128 as standardized is still (and likely to remain) safe. The National Museum of Computing (at Bletchley Park in England) is doing interesting stuff, but is still starved for cash. There is a 501(c)3 you can donate to for tax deductibility and corporate matching, if people want to donate. Don't run algorithms on secret data in the cloud; it's not too difficult for an attacker to get themselves assigned to the same machine and use timing/cache attacks to recover your keys. (At that point I was tired and inebriated and left.) Greg. On 2009 Aug 19, at 2:01 , Perry E. Metzger wrote: Watching the rump session online briefly last night, I saw that some interesting new results on MD5 and AES seem to have been discussed at the conference. Would anyone care to give us a brief overview for the mailing list? Perry -- Perry E. Metzgerpe...@piermont.com - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Certainty
At 5:28 PM -0400 8/19/09, Perry E. Metzger wrote: I believe attacks on Git's use of SHA-1 would require second pre-image attacks, and I don't think anyone has demonstrated such a thing for SHA-1 at this point. None the less, I agree that it would be better if Git eventually used better hash functions. Attacks only get better with time, and SHA-1 is certainly creaking. I understand that creaking is not a technical cryptography term, but certainly is. When do we become certain that devastating attacks on one feature of hash functions (collision resistance) have any effect at all on even weak attacks on a different feature (either first or second preimages)? This is a serious question. Has anyone seen any research that took some of the excellent research on collision resistance and used it directly for preimage attacks, even with greatly reduced rounds? The longer that MD5 goes without any hint of preimage attacks, the less certain I am that collision attacks are even related to preimage attacks. Of course, I still believe in hash algorithm agility: regardless of how preimage attacks will be found, we need to be able to deal with them immediately. --Paul Hoffman, Director --VPN Consortium - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Crypto '09 rump session summary?
At 2:46 PM -0700 8/19/09, Greg Rose wrote: ...some summaries of some of the presentations... More like this, please! The rump sessions have a lot of value (beyond the often-strained attempts at humor). --Paul Hoffman, Director --VPN Consortium - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Certainty
Paul Hoffman paul.hoff...@vpnc.org writes: The longer that MD5 goes without any hint of preimage attacks, the less certain I am that collision attacks are even related to preimage attacks. I believe that yesterday, at the rump session at Crypto, restricted preimage attacks were described. Not quite what you want, but getting closer. Perry - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re (security fix): A Basic Rabin-Williams Digital Signature Specification
Dear all: A revised document has been posted at http://www.connotech.com/doc_rw_sign_basic-02.html, including a fix for an elementary security issue (and two other items, see document revision history). I received some, but not much, feedback (positive) on the first version. Regards, - Thierry On Jul 27, 2009, at 10:35 AM, Thierry Moreau wrote: Title and abstract: Scirpo, a Basic Rabin-Williams Digital Signature Specification The public key cryptography digital signatures are well studied since the early publications by academics three decades ago. On the deployment front, many standardization efforts brought the digital signature techniques at the core of current computer networks. This document almost completely ignores such standards, and focuses on the theoretical foundations of the Rabin-Williams digital signature scheme; it merely describes a simple digital signature scheme including minimal interoperability provisions. While devoid of any advance to the art or science of applied cryptography, this document appears original in its formalization of a signature scheme details with this minimalistic approach centered on theoretical foundations. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com