Peer to Peer Information Systems Week 5 File Storage Old Dominion University Department of Computer Science CS 595 Fall 2003 Michael L Nelson mln cs odu edu 09 23 03 The Magic of Hashes a 1 1 function to map from a domain to a range typically generate fixed length output regardless of the length of the input a simple example A B C X Y Z 01 02 03 24 25 26 A Secret Hash This example is only slightly harder to reverse A B C X Y Z 10 26 03 02 19 04 A One Way Hash Cannot be reversed given an output it is not computationally feasible to determine the input g x A B C X Y Z 02 03 05 89 97 101 f x g x 1 g x g x 1 where x a character in a string such please be hard to read well this example is probably neither 1 way nor a true hash but it is illustrative A Brief Review of Cryptography An excellent book is Applied Cryptography Bruce Schneier 1996 by Secret key encryption you and I share a single key typically a password or phrase that can both encrypt and decrypt a message trick must share the key out of band Public Private Keys Public Private keys each party has 2 keys a public key that they share with the world and a private key that they share with no one the 2 keys are linked so that if I encrypt a message to you with your public key the only way the message can be decrypted is with your private key even I the sender cannot decrypt the message that I just encrypted a common example is PGP e mail key management becomes the trick Digital Signatures I can add a signature to a message or object if I encrypt some text with my private key and include it with the message since my public key widely known you can decrypt my signature using my public key since I am the only one that knows my private key you can safely assume that I am the one that originated the message no one can generate a signature w o knowing my private key Cryptography Public Private keys use 1 way hashing functions based on the premise that large numbers are hard to factor see Schneier 1996 for details public private is slower than secret Common trick pick a secret key encrypt and exchange that with public private and do all the bulk transfer with the symmetric secret key Freenet Goals prevent censorship of documents provide autonomy for users remove any single point of failure or control efficiently store and distribute documents provide plausible deniability for node operators Info http freenet sourceforge net Clarke Miller Hong Sandberg Wiley Protecting Free Expression Online with Freenet IEEE Internet Computing January 2002 http freenet sourceforge net papers freenet ieee pdf Globally Unique Identifiers GUIDs can be created by using SHA 1 secure hashes FIPS 180 1 http www itl nist gov fipspubs fip180 1 htm Two kinds of hashes content hash keys CHK signed subspace keys SSK comprises the keyword signed keys KSK and signature verification keys SVK as described in Chapter 9 of Oram Content Hash Keys Run the file you wish to store through the hash function A location independent identifier for the file even if the file is generated by separate uncooperating users Easy to verify if the retrieved file is the file you requested Signed Subspace Keys Used to establish a personal name space example Politics RIAA Suits Against Preteens 1 2 3 4 5 6 generate a public private key for the file hash the public key hash the descriptive string Politics RIAA concatenate the results from steps 2 3 hash the result from step 4 provide a digital signature using your private key cf pp 130 131 in Chapter 9 Retrieval with SSKs To recreate the SSK you need the subspace s public key the descriptive string SSKs are generally used for indirect files that maintain pointers to files via CHKs in web terms these are home pages in digital library terms these are collections or repositories only the owner of the subspace can update the SSK a level of indirection for the CHKs Routing Tables Each node has a private routing table information is not shared with other nodes when requesting data from a node it checks its local cache and if it doesn t have the data it forwards the request to the node with closest key value data can move to areas of high interest corollary unpopular data will be eventually overwritten Verbs each have TTLs InsertRequest if data does not exist InsertReply is returned DataInsert is then used to write data along the path traveled by the original InsertRequest DataRequest if data does not exist TimedOut is returned Routing Table Data Store Key Data Address 2092asdfZ2229z asdfa923jkas9a0 tcp 128 7 2 3 3222 209384kaz0999s kasdjw28090azz2 tcp 68 2 9 19 3211 29lkasd92q2299 mmn123908S32ss2 tcp 32 5 119 2 80 3840asd29sdz22 tcp 68 9 1 19 3281 90ulk34jsf0902 tcp 45 2 9 10 8211 hh290399920002 tcp 137 7 9 15 1199 cf Figure 9 1 in Oram Encrypted Data It is encouraged to encrypt data that goes into Freenet decryption keys must be shared out of band This provides plausible deniability for the nodes there is no way to know what is contained at your local node a node cannot selectively cheat based on content cf a node set up by riaa org however this does assume a great deal of out of band communication Building the Network Freenet s w is installed on a machine using a portion of the available disk storage A public private key pair is generated for the node keys are not certified to real world identities keys are independent of location An existing Freenet node is picked via out of band communication and the existence of the new node is announced to it the existence is then announced to a random node from that nodes routing table and so on with each hop decrementing the TTL the nodes then collectively assign the new node the responsibility for part of the keyspace Locating Files in the Network Figure 1 from Clarke Miller Hong Sandberg Wiley IEEE IC Jan Feb 2002 Connections Per Node Figure 2 from Clarke Miller Hong Sandberg Wiley IEEE IC Jan Feb 2002 Hops Per Request Figure 3 from Clarke Miller Hong Sandberg Wiley IEEE IC Jan Feb 2002 Fault Tolerance Figures 4 5 from Clarke Miller Hong Sandberg Wiley IEEE IC Jan Feb 2002 Open Issues How to search in Freenet set up easily discovered keyword SSKs keyword virginia tech football keyword dj shadow how to resolve disputes over namespaces How to handle denial of service attacks how to handle name space squatters above how to handle floods of junk data to cause caches to be cleaned Free Haven http www freehaven net Goals anonymity full end to end anonymity persistence a document s lifetime is determined by