Name: Diego Moriarty
Course: BSc (Hons) Computing
Supervisor: Dr. Gerard Parr
Academic Year: 1996/7
Table of contents
Introduction 1The Problem 1The Environment 2Literature Review 2Proposed Solution 5Cryptography Background 6Public Key Cryptography 6RSA 6Hashing 7Description of CryptoNet 9Public Key Cryptography in CryptoNet 9Electronic Commerce in CryptoNet 9Quality Of Service in CryptoNet 10Design 12Main Objects 12Two Layers Of Encryption 13The Packets 13Addressing 16User Manual 17Further Development 22Conclusion and Summary 23Bibliography 24Congestion: 24Security/Privacy: 25Electronic commerce: 25
I would like to thank Jarkko Oikarinen for creating the Internet Relay Chat network, Timothy C. May for his vision, Greg Swann for his political inspiration, Jeffrey K. MacKie-Mason and Hal R. Varian for their ideas about economics, Norman Hardy and E. D. Tribble for their stories from The Digital Silk Road and the Sun Java team.
On a personal level I would like to thank Connor
for his Java assignments and my friends from
House 6009 for their patience.
This document describes a possible solution to the problems of congestion, privacy and electronic commerce on a publicly accessible computer network like the Internet.
The solution offered is a network software package that enables programmers to write applications such as web servers/browsers, chat systems, remote login, email, etc.. . The difference from current Internet software is that, using this new applications, the final user has control on the quality of service provided by the network and is able to buy/sell products with the assurance that the communications are always confidential.
The package is entirely written in Java, and implements a virtual network over the Internet that is cryptographically secure, thus the name CryptoNet.
The Internet as currently three problems: congestion, no privacy and no electronic commerce.
The Internet Protocol (IP) has no means of providing different quality of service to different people, everybody is equal. This may be very democratic, but when the resource (bandwidth) is scarce it is desirable to have some kind of arbitration method so that it is distributed to those who need/want it most.
It is almost trivial for Internet Service Providers to read their customers mail since the mail is stored for a while in their machines. At a lower level, IP doesn't provide any security or identification controls, packets can be snooped on and useful information (credit card numbers, passwords, etc..) extracted from them, also packet addresses can be faked to impersonate another machine. At the moment privacy and security is wanted by the users but the Internet is not providing it.
At the moment it is not easy to buy or sell a product over the Internet. With the most common approach buyers have to have a major credit card and sellers have to have an agreement with that credit card company. In order to send the credit card number a secure connection has to be established, and due to politics this "secure connection" is not really secure if the buyer or seller are outside the USA.
There are other solutions that are based on cryptographic protocols that ensure some level of privacy, but they all need users to install software to access the bank/broker with which they must have an account. With these solutions the problem is in the bank's software, proprietary, non-scalable or insecure.
It would be desirable to allow every user of the Internet (even the most disadvantaged) to buy or sell products and information without any risk.
The environment is the Internet, a network of
that can transfer information on an interactive time-scale. Most of the
users of the Internet are connected through a personal computer capable
of running programs such as a web browser. In particular the proposed
expects the users to have a Java enabled browser, this may not be the
case at the moment, but the trend is for end users to update their
software to enable them to execute Java applications.
In 1994 Jeffrey K. MacKie-Mason and Hal R. Varian, both renowned economists, published a document titled "Some FAQs about Usage-Based Pricing" .
They describe the (still) current situation about the pricing of the Internet. When the service is contracted, the amount of information that the customer moves on the Internet doesn't matter, users of multimedia pay the same price for using video-conferencing as other users do for using email. The rate is per-minute of connection, rather than per byte transferred.
This arrangement does not encourage users to act responsibly when accessing the network. Multimedia applications are very bandwidth-hungry and a few users can easily generate the same bandwidth as hundreds of text-based users. Therefore congesting the network.
They argue that usage-based pricing is the proper way to get the revenue necessary to expand the network as the demand gets higher. A full accounting of bandwidth used and a pricing based on this usage would encourage the users to equate the bandwidth generated with the actual social cost to other users.
They propose a system where users would determine their priority requirements on a voluntary basis, this information travelling along with the packets through the Internet, and not be charged more than a fixed rate when the network is not congested. But as the bandwidth becomes scarce and packets queued and dropped, the accountancy part of the network would automatically charge the users not based on the priority of their packets, but rather on the priority of the packets that have to be dropped or delayed in order to route them. In this way, the packets would always carry a real (and honest) evaluation of their priority. This is a form of "Vickrey auction" or "second-price auction", which economists have shown to be incentive compatible.
If the accountancy software can be implemented, they predict some kind of usage-based pricing scheme being installed at the level of Internet Service Providers and then the system would spread (inevitably) to the rest of the ISPs. The reasoning being that when one Service Provider charges on a per-usage basis, multimedia users would rapidly flee to other providers that don't, thereby congesting that ISP, and forcing it to install as well a usage-based pricing system.
In this document they refer to a previous one written by Norman Hardy and E. D. Tribble in 1993, titled "The Digital Silk Road".
Hardy and Tribble propose a system where the packets of information passed through the network, not only state their priority, but they do so by transferring actual money as part of their payload.
Their idea is to make every single node on the network to have an economic standing with its neighbours. At each link, a node would know how much is owed to/by the neighbouring node to which it connects. When passing a packet with a non-zero money field, this balance would be affected. Accounts would be settled off-line after a predetermined period of time by conventional methods. When a packet travels through the network, balances in many different links may change, but the net change would be that the sender owes someone in the network and the destination is owed by someone else (not necessarily the same).
They argue as well that if each node in the network
a small amount to deliver the packet, this would produce a competition
that would make efficiency of resource usage a prime concern to all the
nodes. Nodes that take bad decisions or charge too much would in the
be avoided when routing packets.
Inspired by The Digital Silk Road, CryptoNet implements a virtual network in which all the users are directly connected to just a few of their neighbours, but can communicate with anybody in the network.
In order to access CryptoNet, the user should know how to connect to a neighbour, this is a similar process to "connecting to the Internet" from home using a modem.
Once connected, users can run CryptoNet applications in the same way they use Internet applications when connected to the Internet.
It is up to the application programmer to allow the
to specify what is the quality of service desired. The higher the
the higher the guarantee that the information is transmitted
but the user is charged more for the service. Other possible facilities
would be for example: to inform the user of the cost of downloading a
the total cost of a chat once it is finished, etc. All this facilities
are provided at a lower level by CryptoNet.
Cryptography has for thousands of years helped people send secret message to one another through non trusted channels, this was usually achieved with a "key" to encrypt a message that was later needed again to decrypt it. That is called private key cryptography.
The problem with private key cryptography that the recipient may not have the key before the message is received. If so, the key has to be sent as well; but if there is no trusted channel the same problem appears again.
That was solved with public key cryptography. In this system, two keys are created together. Their relationship is that one key can decrypt messages encrypted with the other key. The encrypting key is called the public key and it should be advertised to anybody wanting to use it. The decrypting key is called the private key and it should be kept secret.
The creation of the keys involves usually (depending on the algorithm) quite complicated maths, but the idea is that once generated, it is very difficult (to the point of impracticability) to discover the private key having only the public key.
This acronym stands for the initials of Rivest, Shamir and Adelman, the three cryptographers who developed the first time-tested public key algorithm.
It relies on the properties of some integer numbers in relation to some operations, namely:
Being p and q some prime numbers and e any integer, if another integer d exists such that d*e mod (p-1)*(q-1) = 1, then being n=p*q, the public key is (e,n) and the private key is (d,n).
Note that no d will exist if (p-1)*(q-1) can be divided evenly by e. In practice the number e is agreed upon beforehand (usually being three or 257), then the only number that has to be advertised is n
Having (e,n) and a message m, the encrypted message c is m^e mod n and having (d,n) and an encrypted message c, the decrypted message is c^d mod n.
Notice from the original formula that d and e are interchangeable, in the same way as (d,n) decrypts messages encrypted with (e,n), (e,n) can be used to decrypt messages encrypted with (d,n). This can be useful for signing messages:
The owner of the private key can encrypt a message with (d,n) to create a signature. Afterwards, it can be proved that a signature is valid if decrypting it with (e,n) gives the original message.
Note that public key encryption/decryption is orders of magnitude slower than using secret key algorithms.
With this and other public key algorithms it is not possible to encrypt or decrypt a message bigger than n, a work around is to split the message into smaller pieces and work with the pieces instead. A more common solution is to encrypt only a short message stating the value of a secret key, that will be used in conjunction with a secret key algorithm to decrypt/encrypt the rest of the message.
In computer terms to hash some information is to transform it in some way that will generate a smaller amount of information that uniquely identifies it in the presence of other hashes. For example a valid hash algorithm for a student could be the initials of the name plus the graduation year.
It is not possible to regenerate the original information from its hash, but it is very useful to keep indexes in dictionaries, databases, telephone guides, etc.
A cryptographically secure hash algorithm is one with which is easy to generate a hash having the original message, but is very difficult (to the point of being impractical) to come up with a message that will generate the same hash.
To calculate the hash of some information is orders of magnitude faster than to calculate its signature, that is way secure hashing is used in many cryptographic systems, it is much more efficient to sign the hash than to sign the whole message.
Cryptography is at the core of CryptoNet, and RSA is the algorithm used to implement it. The value e of the public key is agreed to be always three, authentication is assured by signed hashes, the hash algorithm being MD5.
The current approach to big messages is to split them into smaller messages and encrypt/decrypt the pieces separately, the implementation a secondary secret key algorithm is left as a future possible improvement.
The user has the option to generate a new RSA key pair or to use a previously generated pair. The user can select the size of the desired keys with the maximum being 2048 bits, which is expected to be safe for the next few decades.
Throughout CryptoNet, the public key is used as a "User ID" and the private key is used as a password. As far as the user is concerned, this is similar to a login_name/password except that the pairs are always computer generated and they are almost impossible to remember.
Privacy and authentication are provided by the network, the applications programmer has only to send information away and it is automatically signed and encrypted. When receiving from the network, the application gets information generated only by the expected user.
A user connects to CryptoNet by setting up links to and from a group of "neighbours". These are just other users in the network using all the same software. Before any of these peer-to-peer connections is allowed, there has to be a previous trust relationship between both users, some kind of real-world contract as it is typical between Internet Service Providers and their customers, or between the different communications companies. Only then can money flow through the connection (in the form of authenticated IOUs), the key point is that money can flow in both directions and none of them knows who is going to end up owing the other.
To send some money to a far away destination, the user has no choice but to rely on a trusted neighbour, this neighbour may in turn not have a trust relationship with the final destination, in this case yet another neighbour is used and so on in a long chain until the final destination gets the money.
When a user forwards money from one neighbour to another, the IOUs for the links are modified, but the total balance stays the same. It doesn't really cost anything to forward money.
After a specified period of time, the accounts between each two neighbours will be settled in the real world and the IOUs ripped apart.
After receiving a group of packets from the same source, the destination replies with an acknowledgement packet.
To avoid a bad node keeping the money and blaming it on someone else, if the acknowledgement is not received under a specified time, then all the money is claimed back.
Once having secure money transfer on the network is very easy to solve the problem of congestion on the network. In the Internet users can not choose the priority of their packets, since it costs the same to them the priority would be always "critical". CryptoNet solves this situation by charging a small amount of money for forwarding each packet, depending on the congestion of the network and how far away the final destination is. This "travel money" is specified by the application (ultimately by the user), and as the packet passes through different nodes, each will keep a small percentage "for the trouble".
When a node accepts a packet, it accepts as well the responsibility of getting it to the final destination on time, in the same way as for money transfer, a node will automatically claim back the travelling money if it doesn't get an acknowledgement from the final destination in a specified amount of time.
When there are more packet coming in than a node can handle, the packets are accumulated for later forwarding, but if they are stored for too long they may become useless information and not be needed anymore. Many different factors contribute to the decision of what packet should go next, including the risk of it being discarded somewhere downstream, the expected cost of the transfer and the loss on reputation if it is discarded strait away. This is a perfect example where good artificial intelligence is needed, and the more intelligent a node is, the higher the profit for the owner of the node.
CryptoNet allows packets be constrained by an
arrival time and a maximum allowed jitter (variance from the expected
time). A packet with very tight constrains will be more expensive to
than a non-urgent packet. Also packets will be charged at a maximum
during peak time, while when there is no congestion the cost could go
Due to the fact that Java is an object oriented language, the design is also object oriented and it follows closely the principle of "mimic real world objects".
The first and most obvious object is the node, it represents the user's machine. It takes care of the processing of the network layer in the OSI reference model.
Then there are two different kinds of links, outward and inward. They always exist in pairs, that is, for an outward link in one node, there is always an inward link in some other node. These two objects take care of all the link layer processing in the OSI reference model. The physical layer of the OSI model is simulated by a TCP connection from node to node.
CryptoNet is a packet switching network, therefore a "packet" object exists, which does not perform any action but rather it passively holds information and is created, passed around and destroyed by the other objects.
The node does not distinguish where the packets are coming from or where are they sent to, even the information from and to the user is treated as coming and going through links.
Applications that want to interact with other users in CryptoNet, are supplied with objects called Xockets (cryptographic sockets) which are quite similar to Internet sockets and provide a simple datagram service to the application. This is the transport layer on the OSI reference model.
There is an object called CryptoNet that controls the node, it interacts with the user to connect to a neighbour or to accept connections from a requesting neighbour. It is the equivalent of a "control panel" for technical details, typically the final user will rarely interact with this GUI and settings should be remembered from session to session.
For maintainability purposes all the cryptography related operations are held in the same object "Crypto", it is a static object that is used by others to encrypt, decrypt or check signatures.
Cryptography is at the core of CryptoNet and it is used at two of the OSI layers: the network layer and the data link layer.
At the network layer, packets have to be encrypted because otherwise every single node that the packet travels through would be able to read the contents. At the link layer the reason is more subtle, since money is being passed from node to node towards a final destination, if the link layer was not encrypted, an adversary with sufficient resources could tap into this communication and learn what packets are being transmitted, to where, with how much money etc..
For maximum security the link layer packet is a completely encrypted block, with only the size preceding it:
size link layer encrypted payload
After decrypting the payload, the recipient neighbour will be able to extract the network layer packet:
value time-out money transfer arrival time jitter destination payload signature
Note that the signature should match the hash of all the previous fields put together and certifies that the link packet originates from the expected neighbour.
The value field is the "travelling money" and it is modified by every node as the packet travels through the network, the time-out specifies until when is the previous neighbour going to wait for an acknowledgement before claiming the money back.
The money transfer field states how much money is to be transfer from one neighbour to another, and unlike the value field, it is not to be disturbed.
Arrival time and jitter specify the constrains of this packet and they may force the packet to be disregarded if the commitment can not be kept.
The destination field is the address of the final node, which is the only one who can decrypt the last field, the payload.
The decryption of the payload by the final destination produces the final information, which may come in two different flavours:
port source final message signature
port final message signature
The source address is only needed by the final destination when it is an unexpected packet, such as when requesting a public service. When the destination determines the port number, it will discern if it is destined to a public service or a private port, if it is destined for a private port then the source is already known by the application.
Note that this network layer signature (different from the link layer one) does not only certify these fields, but also the money transfer field, the arrival time, jitter and destination fields from that are accessible to the intermediate nodes. If any field is tampered with then the signature check will fail, the packet will be considered a hack and it will be dumped.
In CryptoNet the address of a node is the public key of the user. As it can be up to 256 bytes this is clearly very inefficient. It is left as a possible future improvement to have dynamic usage of aliases at the link layer to compress this information.
An important choice in the design is to not include the source address of the packet. As they travel through the network, the packets are anonymous until they reach the destination. Who will decrypt it and if necessary extract the source address from the payload.
In order for this packet to propagate back to the
of the group, all nodes should remember the hashes of the packets they
routed and from what link they came from.
By browsing the web, the user may end up in a page like this:
This is the point when a first time user has to generate a new pair of keys, for casual testing of CryptoNet, a size of 10 is enough, for serious use, a size of 512 is recommended, although it can take a minute or two to generate. If the User ID and password are to be reused on another session, the user should take care of remembering them, saving them in a file or similar.
Then it is the moment to press "Enter CryptoNet". If the provided User ID and password are not typed correctly, they will be overwritten with question marks, prompting the user to try again.
If they are a valid combination of User ID and password then the user will be presented with a screen like this:
This is the equivalent of the control panel for an Internet connection.
The first thing to do is to connect to a group of neighbours. Three details are needed to connect to each neighbour: User ID, Internet address and Internet port. The user would get these details in the same way as with a normal Internet Service Provider.
After connecting with two neighbours, the control panel may look like this:
This means that the connections where accepted and there is a trust relationship between the user and both of the neighbours.
From this moment, packets can be sent and received from CryptoNet, the balance will always appear on the control panel if the user wants to check. Normally the user would just forget about this screen and start using some applications that depend on CryptoNet.
It is possible for the user to receive unsolicited requests to connect from any user on the Internet, if so the system will query the user before accepting the connection (unless the auto-accept switch is on). The user at this point has the option to open an outward connection to the requester (this is done automatically if the auto-connect is switched on).
A small utility called "Packet Constructor" is provided to send small messages to a particular user. Knowing the proper destination User ID, the user can complete the fields on the packet constructor and then press "send". Note that the packet will be ignored if there is no xocket waiting at the destination service.
The next and more meaningful application demo is called "Flea Market". It implements a multi-user chat system with money transfer, the smallest example of an information market. To join a group of people, a user has to send a "whisper" message to another one who is already chatting, knowing the User ID is essential, but not at all the Internet address or the listening port.
The balance is marked in dollars, and it may change
the user sends or receives messages from other people in the CryptoNet.
The quality of service can be changed to reflect how much does the user
value this communication, the higher the value, the speedy the delivery
compared to the rest of the users.
The current version of CryptoNet was designed and implemented as a proof of concept. The priorities where security and functionality, so at many stages and due to time constrains, efficiency was sacrificed in favour of results.
The most important immediate improvement would be a facility to save passwords, user IDs and miscellaneous settings to disk.
Users can not be expected to remember user Ids, so a proper DNS like service could be implemented.
CryptoNet could be made connection oriented as in TCP, the simple datagram service that provides now has only limited uses.
All the cryptographic implementation should be reviewed by a third party.
An area that can always be improved is the routing
it is a perfect area to research Artificial Intelligence topics.
This project aimed to tackle very big issues on computer networking. From concept to realisation the problems encountered where very challenging, and therefore very enjoyable.
The main issue (cryptographic cash-based network) was solved. Although the design and implementation options could have made the details of this project somewhat different, the functionality as far as end users are concerned wouldn't have changed much.
Throughout the design I had to learn a lot about
key cryptography, routing algorithms and communication protocols.
the implementation, to learn about the capabilities of Java, related
environments, tools, etc.. was one of the main day to day tasks.
"Economic FAQs About the Internet"
"Billing Users and Pricing for TCP" - Richard J. Edell et al. IEEE Journal in Selected Areas of Communication.
RFC-1272: "Internet Accounting: Background". C. Mills et al
RFC-1346: "Resource Allocation, Control, and Accounting for the use of Network Resources". P. Jones - Joint Network Team
"Congestion Pricing Alternatives: Are They Worth Settling For?" - Laura Brice.
"Some FAQs about Usage-Based Pricing" Jeffrey K. Mackie-Mason and Hal R. Varian - University of Michigan
"The Chilean Internet Connection or I Never Promised You a Rose Garden" J.M. Piquer et al.
William Vickrey and Hal Varian are economists that have studied the problem of the Internet Congestion as if it were just another scare resource, with some common characteristics with land ownership.
In www.agorics.com there is a study of different auction types, very relevant reading in order to find a proper billing system for the Internet.
The Internet is full of papers about security and privacy, from their political issues to cryptographic algorithms based on obscure mathematics. This are just a few entry points.
"Answers to frequently Asked Questions About Today's Cryptography" - Paul Fahn - RSA Laboratories.
"Cryptography FAQ" News:Sci.crypt
"The dining Cryptographers Problem: Unconditional
Sender and recipient Untraceability" David Chaum
"NetBill: An Internet Commerce System Optimized for Network Delivered Services" - Carnegie Mellon
"PayWord and MicroMint: Two simple micropayment schemes" Ronald L. Rivest and Adi Shamir.
"Online Cash Checks" David Chaum
David Chaum is the creator of Ecash, a cryptographically secure banking system that allows customers to buy products from a seller when the bank is off-line and the seller would clear the transaction afterwards with the bank.
"The Millicent protocols for Electronic commerce" Mark S. Manasse
Robert Hettinga's assorted rants about geodesic networks are very relevant and are in the same line (and inspired by) the Digital Silk Road.
"The Digital Silk Road". Norman Hardy and Eric Dean Tribble
This paper alone is more relevant to CryptoNet than
the others put together.
Done by Diego Moriarty