Exam 2 study guide
The one-hour study guide for exam 2
March 29, 2009
Disclaimer: This study guide attempts to touch upon the most important topics that may be covered on the exam but does not claim to necessarily cover everything that one needs to know for the exam. Finally, don't take the one hour time window in the title literally.
Distributed file systems (continued)
AFS
AFS was designed as an improvement over NFS to support file sharing on a massive scale. NFS suffered because clients would never cache data for a long time (not knowing if it would become obsolete) and had to frequently contact the server. AFS introduced the use of a partition on a client's disk to cache large amounts of data for a long time: whole file caching and long-term caching. It supports a file download-upload model. The entire file is downloaded on first access (whole file download) and uploaded back to the server after a close only if it was modified. Because of this behavior, AFS provides session semantics: the last one to close a modified file wins and other changes (earlier closes) are lost.
During file access, the client need never bother the server: it already has the file. When a client first downloads a file, the server makes a callback promise: it maintains a list of each client that has downloaded a copy of a certain file. Whenever it gets an update for that file, the server goes through the list and sends a callback to each client that may have a cached copy so that it can be invalidated on the client. The next time the client opens that file, it will download it from the server. Files under AFS are shared in units called volumes. A volume is just a directory (with its subdirectories and files) on a file server that is assigned a unique ID among the cell of machines (remember cells from DCE RPC?). If an administrator decides to move the volume to another server, the old server can issue a referral to the new server. This allows the client to remain unaware of resource movement.
CODA
Coda was built on top of AFS and focused on two things: supporting replicated servers and disconnected operation. To support replicated storage, AFS's concept of a volume was expanded into that of a Volume Storage Group (VSG). Before a client accesses a file, it first looks up the replicated volume ID of the file to get the list of servers containing replicated volumes and the respective local volume IDs. While it can read files from any available server, it first checks the versions from all of them to ensure that one or more servers don't have out-of-date files. If the client discovers that a server has an old version of a file, it initiates a resolution process by sending a message to that server. When a client closes a file, if there were any modifications, the changes are written out to all available replicated volumes.
If no servers are available for access, the client goes into disconnected operation mode. In this mode, no attempt is made to contact the server and any file updates are logged instead in a client modification log (CML). Upon connection, the client plays back the log to send updated files to the servers and receive invalidations. If conflicts arise (e.g., the file may have been modified on the server while the client was disconnected) user intervention may be required.
Because there's a chance that users may need to access files that are note yet in the local cache, Coda supports hoarding, which is a term for user-directed caching. It provides a user interface that allows a user to look over what is already in the cache and bring additional files into the cache if needed.
DFS (AFS version 3)
AFS evolved over the years. The most significant evolutionary version is version 3, which was adopted as the recommended distributed file system in the Distributed Computing Environment (DCE) where it is named DFS (Distributed File System). The primary design goal of this system was to avoid the unpredictable lost data problems of session semantics if multiple clients are modifying the same file. The concept of tokens was introduced. A token is permission given by the server to the client to perform certain operations on a file and cache a file's data. The system has four classes of tokens: open, data, status, and lock tokens. An open token must be obtained to have permission to open a file. A read data token must be obtained for a byte range of a file to have permission to access that part of the file. Similarly, a write data token is needed to write the file. Status tokens tell the client that it may be able to cache file attributes. These tokens give the server control over who is doing what to a file. Tokens are granted and revoked by the server. For example, if one client needs to write to a file then any outstanding read and write data tokens that were issued to any clients for that byte range get revoked: those clients are now denied access until they get new tokens.
SMB/CIFS
Microsoft's Server Message Block protocol was designed as a connection-oriented, stateful file system with a priority on file consistency and support of locking rather than client caching and performance. While it does not use remote procedure calls, its access principle is the same: requests (message blocks) are functional messages, providing file access commands such as open, create, rename, read, write, and close.
With the advent of Windows NT 4.0 and an increasing
need to provide improved performance via caching, Microsoft introduced
the concept of opportunistic locks
(oplocks) into the operating
system. This is a modified form of DFS's tokens. An oplock tells
the client how it may cache data. At any time, a client's oplock
may be revoked or changed by the server. A level 1 oplock tells the
client that it has exclusive access to the file (nobody else is
reading or writing it), so it can cache lock information, file
attributes, and perform read-aheads and write-behinds. A
xFS
Traditional distributed file systems are not truly distributed but rely on a central server to serve a set of directories. Some systems, such as CODA, support replicated servers. Berkeley's xFS is proof-of-concept serverless file system, where any machine can store, cache or control any block of data. Any machine can also assume the responsibilities of any failed component
Google File System (GFS)
The Google File System is an application-specific file system: it is designed to be optimal for the needs of the Google search application. The system is designed for an environment where there are many thousands of storage servers, some of which are expected to be down at any given point in time. THe data managed comprises of billions of objects and many terabytes (petabytes, likely).
Each GFS cluster contains one master file server. This is a faster and more reliable machine that contains file system metadata, such as names and attributes of files and directories. None of the actual file data resides on this system. Instead, it contains a mapping of the file contents to the chunks that hold the data. Chunks are stored in chunkservers. The chunkservers are less reliable than the master and are replicated so that each chunk is stored on at lease three separate chunkservers.
Clients contact the master to look up files. The master gives them a chunkserver name and chunk ID numbers for the files requested.
WebDAV
WebDAV is a file access protocol built as an extention to the standart HTTP commands. Additional HTTP commands were added to copy and move resources, manage directory structures, and lock/unlock resources.
Many popular applications use WebDAV (Apple's iCal and iDisk, Microsoft Exchange and IIS) and it is supported as a network file system type by popular operating systems (Linux, OS X, Windows).
GmailFS
GmailFS is an example of writing a custom file system to take advantage of the free storage provided by Gmail (over 7 GB). Each message represents a file. Subject headers identify the file system name so the interface can find all relevant messages that constitute the "file system". They also contain file names and other metadata (symbolic link information, user ID, size, etc.). The actual file data resides in attachments to the message.
Logical clocks
Lamport clocks allow one to assign sequence numbers ("timestamps") to messages and other events so that all cooperating processes can agree on the order of related events. There is no assumption of a central time source and no concept of total ordering (when events took place). The central concept with logical clocks is the happened-before relation: a→b represents that event a occurred before event b. This order is imposed upon consecutive events at a process and also upon a message being sent before it is received at another process. Beyond that, we can use the transitive property of the relationship to determine causality: if a→b and b→c then a→c. If there is no causal relationship between two events (e.g., they occur on different processes that do not exchange messages or have not yet exchanged messages), the events are concurrent.
Lamport's algorithm states that every event is timestamped (assigned a sequence number) and each message carries a timestamp of the sender's clock (sequence number). A message comprises two events: (1) at the sender, we have the event of sending the message and (2) at the receiver, we have the event of receiving the message. The clock is a process-wide counter (e.g., a global variable) and is always incremented before each event. When a message arrives, if the receiver's clock is less than or equal to the message's timestamp, the clock is set to the message timestamp + 1. This ensures that the timestamp marking the event of a received message will always be greater than the timestamp of that sent message.
One problem with Lamport timestamps is that multiple events on different processes may all be tagged with the same timestamp. We can force each timestamp to be unique by suffixing it with a globally unique process number. While these new timestamps will not relate to real time ordering, they will be unique numbers that can be used for consistent comparisons of timestamps (e.g., if we need to make a decision on who gets to access a resource based on comparing two timestamps).
A second deficiency with Lamport timestamps is that, by looking at
timestamps, one cannot determine whether there is a causal relationship
between two events. For example, just because event a has a timestamp
of 5 and event b has a timestamp of 6, it does not imply that event
a happened before event b. A way to create timestamps that allow
us to discern causal relationships is to use a vector clock. A
vector clock is no longer a single value but rather a vector of
numbers, each element corresponding to a process. Before affixing
a vector timestamp to an event, a process increments the element
of its local vector that corresponds to its position in the (for
example, process 0 increments element 0 of its vector; process 1
increments element 1 of its vector). When a process receives a
message, it sets the vector of the event to one that contains the
higher of two values when doing and element-by-element comparison
of the original event's vector and the vector received in the
message. This becomes the new per-process vector from which future
events on that process will be timestamped. For example, in an
environment of four processors, P1 will "own" the second element
of the vector. If one event on P1 is (2, 4, 0, 1) then the next
event will be (2, 5, 0, 1). If the event after that is the receipt
of a message with a timestamp of (3, 2, 9, 8) then the timestamp
will be created by setting an element-by-element maximum of (2, 6,
0, 1) and (3, 2, 9, 8), which is (3, 6, 9, 8). We can illustrate this
with the following pseudocode where e is the system's
vector counter and r is the received vector timestamp:
Two events are concurrent if one vector timestamp is neither greater than or equal nor less than or equal to the other element when doing an element-by-element comparison. For example, events (2, 4, 6, 8) and (3, 4, 7, 9) are not concurrent (i.e., they are causally related) because every element of the first vector is less than or equal to the corresponding element of the second vector. The vectors (2, 4, 6, 8) and (1, 5, 4, 9) represent concurrent events. Neither vector is less than or equal to the other. For instance, 2 ≥ 1 (first element of the first vector is greater than the first element of the second vector) but 4 ≤ 5 (second element of the first vector is less than the second element of the second vector).
Clock synchronization
No two clocks tick in perfect synchrony with each other. The difference between two clocks at any given instant is the clock skew. The rate at which the clocks are drifting is the clock drift. A linear compensating function adjusts the rate at which time is measured on a computer (e.g., number of ticks that make up a second).
Cristian's algorithm sets the time on a client to the time returned by the server plus an offset that is one half of the transit time between the request and response messages: Tclient = Tserver + ½(Treceived - Tsent). It also allows one to compute the maximum error of the new time stamp. The error is ± ½[(round-trip time) - (best-case round-trip time)]. Errors are additive. If you incur an error of ±50 msec and the server's clock source has an error of ±80 msec, your clock's error is now ±130 msec.
The Berkeley algorithm does not assume the presence of a server with an accurate time (i.e., one that keeps track of UTC time). Instead, one system is chosen to act as a coordinator. It requests the time from all systems in the group (including itself) and computes a fault-tolerant average (an arithmetic average, dismissing systems whose time values differ by more than a certain amount). It then sends each machine an offset by which to adjust its clock.
The Network Time Protocol, NTP, was created to allow a large set of machines to synchronize their clocks. A set of machines acts as time servers – this collection of machines is the synchronization subnet. The subnet is hierarchical, with the time server's stratum defined as the number of hops it is from a machine that synchronizes from a direct time source. Machines that are directly connected to a time source (e.g., a GPS receiver) are at stratum 0. Machines that synchronize from a system at stratum 0 are at stratum one, and so on. The Simple Network Time Protocol, SNTP, is a restricted form of NTP that does not support peer-to-peer synchronization of time servers. The peer-to-peer mode maintains state on drift and synchronization time and is intended for time servers to synchronize with each other. SNTP is essentially the same as Cristian's algorithm. The formula for SNTP is time_offset = ½ (T2 - T1 + T3 - T4) where T1 is the time the message left the client, T2 is the time it arrived at the server, T3 is the time the response left the server, and T4 is the time that it arrived at the client. If we let TS = ½(T2+T3) then we arrive at Cristian's formula.
Distributed Lookup Services
The purpose of a distributed lookup service is to find the machine that has data that corresponds to a key that you have. For example, the key can be the name of the song and the machine is one that is hosting the MP3 file.
The most straightforward approach is to use a central server to store all the keys and their mapping to machines. You ask the server to look up a key and it gives you the machine containing the content. This is the classic Napster implementation.
Another approach is to "flood" the network with queries. What happens here is that your machine knows of a few peer machines. Those machines, in turn, know of other peer machines. When a machine needs to look up a key, it forwards the request to all of its peer nodes. If one of the peers has the content, then it responds. Otherwise, it forwards the request to its peers (and they forward the request to their peers ...). This approach was used by the Gnutella file sharing system.
Finally, the distributed hash table (DHT) approach is a set of solutions that is based on hashing the search key to a number that is then used to find the node responsible for items that hash to that number (or a range of numbers). A key difference between the DHT approach and the centralized or flooding approaches is that a specific node is responsible for holding information relating to the key: the one that is responsible for managing hash(key).
Group communication
Point-to-point communication is known as unicast. This is what we generally use to communicate a single client and server. There are other modes of communication. Broadcast is the sending of data to every node on the network. Anycast is point-to-point communication (as in unicast) but the receiver is the nearest one of receivers with specific capabilities (for example, IPv6 uses this to allow a host to update the routing table of the nearest host). Finally, there's group communication, known as multicast. This is point-to-multipoint communication. A message gets sent to everyone in the group. One implementation of multicast is known as netcast. This simulates hardware multicast by invoking multiple unicasts, one to each recipient. There are two considerations in group communication (multicast): reliability and message ordering.
Reliability
An atomic multicast requires that a message must reach all group members (if one node cannot get the message, no others can process it). This multicast must survive machines going down – both the sender and/or receivers. Because of this, it requires the most overhead in implementation, often employing persistent logs.
A reliable multicast is a best-effort multicast. The sender sends a message and waits for an acknowledgement. If it doesn't receive the acknowledgement in time, it will retransmit the message. Eventually, after a longer interval of time, it will give up and assume the receiver is dead.
An unreliable multicast doesn't wait for acknowledgements and will generally use whatever underlying multicast mechanism is provided.
Message ordering
The issue in message ordering is that multiple nodes can be sending messages to the entire group at the same time. Will each node receive all the messages in the exact same order? Will each node receive all the messages in the order they were sent?
Global time ordering requires that all messages arrive in the exact order they were sent: if node A sent a message 5 nanoseconds before node B did then all nodes should receive the message from node A first. This is impossible to implement (clocks can't be that perfectly synchronized and the chance of a tie always arises; also, networks will not be able to guarantee this kind of ordering if routing is involved). A more practical approach is total ordering. This requires that all messages arrive in the same order at all nodes. This can be easily achieved by providing a mechanism for obtaining a totally sequenced message ID: for example, from a sequence number server.
Causal ordering is the ordering you would get by attaching Lamport time stamps to messages. The ordering of unrelated (concurrent) messages is insignificant, but causally related messages will be in the proper order. Sync ordering guarantees that all messages from a specific sender will arrive in FIFO (first-in, first-out) order.
Sync ordering requires a special type of message — a sync message. When this is issued, any messages that were already sent have to be processed (and acknowledged to the senders). The sync assures that any messages sent before the sync will be processed before any messages after the sync (globally – for all nodes).
Finally, an unordered multicast doesn't impose any message ordering among messages from other nodes. It may choose to impose FIFO (first in, first out) ordering on messages from a particular source (e.g. as TCP does).
IP multicast
An IP multicast address (also known as a class D address) contains a 28-bit multicast address. A host may join this address and receive messages addressed to that multicast ID. Within a LAN, an IP class D address is mapped onto an Ethernet multicast address by copying the least-significant 23 bits of the address onto an Ethernet multicast address. Within a LAN, an ethernet chip is programmed to to perform an exact match on a small set of addresses or to accept addresses that hash to particular values. The ethernet driver will need to remove any unneeded addresses that pass through. The ethernet chip can also be set to multicast promiscuous mode, where it will accept all multicast ethernet packets.
The Internet Group Management Protocol (IGMP) manages membership beyond a LAN. A node broadcasts a multicast join message to join a specific group. A multicast-aware router will pick this message up and sent the join message to other connected networks (this way a spanning tree is built, ultimately forwarding the request to the source). Periodically, each router sends a query message for each multicast group. If any node (or router) is still interested in the group, it must send a join message. If no join messages are received, then the router will stop responding to join messages and the LAN will no longer receive packets for that group.
Distributed Authentication via OpenID
OpenID was created to solve the problem of how a user can manage multiple identities (logins and passwords) at many different web sites. user logs in with a URI from which the name of the user's Identity Provider can be fetched. OpenID Identity Providers are responsible for authenticating users (typically with a login and password) and storing various user attributes.
When a user enters a login URI, the web site, known as a relying party issues a redirect to the user's browser, taking it to the user's OpenID Identity Provider login page. The user authenticates with the Identity Provider, which then sends a redirect back to the originating web site. This redirect contains a digitally-signed user credentials. The web site validates these either using a cached secret key that it has previously established with the Identity Provider or else it connects to the Identity Provider via HTTPS and requests authentication information directly and compare that with what it received via the browser redirect (this guards against a malicious attacker). If the site is convinced that the credentials are genuine then the user is considered to be logged in.
Through the Identity Provider, the user can control how many logins should be allowed (e.g. one, one per day, etc.) before the user has to intervene. The user can also control what attributes get sent to each site requesting user credentials.
Mutual exclusion
The centralized algorithm is a server that accepts REQUEST messages for a resource (e.g., critical section). If nobody is using the resource, it responds with a GRANT message. If somebody is using the resource, it doesn't respond. When a client is done with a resource, it sends the server a RELEASE message. The server then sends a GRANT message to the next client in the queue (if there is one).
The token ring algorithm creates a logical communication ring among the nodes in the group. A message, called a token, is created for each resource. This token is passed from node to node along the ring. If a node receives a token and does not need to access that resource, it simply passes the token to the next node. Otherwise, it will hold on to the token until it is done with the resource.
The Ricart & Agrawala algorithm was an early demonstration that a truly distributed algorithm is possible. A node that wants to enter a critical section sends a request to all other nodes in the group and waits for all of them to respond. If another node is currently using the critical section, that node delays its response until it is done. If node A and node B sent out requests concurrently (i.e., two systems want the same resource concurrently), each system compares the timestamp of that request with that of its own request. If node A received a request from node B that is older (a lower timestamp), then node A will give node B priority to access the resource by sending a response to node B . Otherwise, if node A has the earlier timestamp, it will queue the request from B and continue to wait for all acknowledgements, sending a response to B (and any other nodes who wanted the resource) only when it is done using the resource. The key point is that nodes A and B will make the same comparison and exactly one will hold back on sending the response.
Lamport's algorithm, like the Ricart & Agrawala algorithm, is also based on reliable multicast. This algorithm has a node send a timestamped request to all nodes in the group, including itself. Every message is acknowledged immediately. A process decides whether it can access the resource by checking whether its own request is the earliest one in the queue of all requests that it has received. If so, it accesses the resource and, when done, sends a release to all members (including itself). The receipt of a release message causes each process to remove the process from the ordered queue. If a process now finds itself as the earliest process in the queue, it knows that it is now its turn to access the resource.
Election algorithms
The bully algorithm selects the largest process ID as the coordinator. If a process detects a dead coordinator, it sends an ELECTION message to all processes with a higher ID number and waits for any replies. If it gets none within a certain time, it announces itself as a coordinator. When a process receives an ELECTION message it immediately sends a response back to the requestor (so the requestor won't become the coordinator) and holds an election to see if there are any higher-numbered processes that will respond.
The ring algorithm requires a logical communication ring among the nodes in the group. When a process detects a non-responding coordinator, it creates an ELECTION message with its own process ID and sends it to the next node on the ring. If the node is dead, it sends it to the following node (skipping dead nodes until it finds one that can receive the message). When a node receives an ELECTION message, it adds its own process ID to the body and sends that message out to the neighboring node. When the election message circulates back to the original sender, the sender gets the list of active nodes from the body and chooses a coordinator from among them (e.g., highest ID).
One problem with election algorithms is when a network gets segmented: one set of nodes is separated from another. In this case, each segment may elect its own coordinator and problems can arise. This is known as a split brain situation. To combat this, a redundant network is needed (or some alternate communication mechanism to enquire about the state of nodes).
Distributed shared memory
Distributed shared memory (DSM) is a mechanism to allow processes on different machines to have the illusion of sharing memory (i.e., being able read data from memory that another process wrote to memory). Transparency is generally achieved through the system's memory management unit (MMU). When a page fault occurs, the page fault handler invokes the DSM algorithm, which can fetch the page from another server, map it into the process' address space and restart the instruction. A directory is the server, or set of servers that allows a node to find out where the needed page lives (and possibly where cached copies reside).
A well-defined memory consistency models is key to DSM is the algorithms must enforce the model. Sequential consistency is what we generally expect from a memory system. A read always returns the result of the last write for a given instruction stream. For multiple streams (concurrent processes), any interleaving is acceptable as long as accesses within each stream are in sequential order. To achieve sequential consistency, each write operation must invalidate or update all cached copies before the write completes. Since writes have to be visible in the same order by all processes, a read cannot take place until the write is acknowledged.
Presenting sequential consistency is an expensive proposition, since considerable network activity has to take place for each write operation. To enhance performance, weaker consistency models can be employed.
A weak (or relaxed) consistency model requires that memory be consistent only at specific synchronization events. For example, a sync variable is an operation that will force all local operations to be propagated out and remote operations on memory to be brought in. This way, memory is made consistent explicitly on a sync rather than for each operation. Release consistency allows us to break up the operations of sending out changes and receiving updates into two parts: an acquire phase and a release phase. An acquire indicates that the processor is about to perform operations on the memory and needs to get any updates from other processors. A release indicates that the processor is done with its operations on the memory. Any of the processor's writes now have to be made visible to a processor doing a subsequent acquire. There are two variants of release consistency: eager and lazy. The eager protocol ensures that all copies of pages on other nodes are updated with the contents of the newly-modified pages when a processor performs a release operation. In fact, page invalidations may be sent during program execution and the release operation itself is a blocking on that ensures that all invalidations have been acknowledged. The lazy protocol does not bother to update or invalidate existing copies of the pages upon a release (on the assumption that those nodes with cached copies of the page might never even access the page again). Instead, page invalidations are propagated at acquire time.
Finally, entry consistency allows the acquire and release operations to take place on regions of memory (such as individual variables or data structures) rather than all of shared memory. To achieve entry consistency, one must employ smart compilers or control the consistency explicitly since the system's MMU cannot protect these boundaries.
Cryptography
Cryptography deals with encrypting plaintext using a cipher (also known as an encryption algorithm to create ciphertext, which is unintelligible to anyone unless they can decrypt the message.
A restricted cipher is one where the workings of the cipher must be kept secret. There is no reliance on a key and the secrecy of the cipher is crucial to the value of the algorithm. This has obvious flaws (people in the know leaking the secret, coming up with a poor algorithm, reverse engineering). For any serious encryption, we use non-secret algorithms that rely on secret keys.
A symmetric encryption algorithm uses the same secret key for encryption and decryption. A public key algorithm uses one key for encryption and another for decryption. One of these keys is kept private (known only to the creator) and is known as the private key. The corresponding key is generally made visible to others and is known as the public key. Anything encrypted with the private key can only be decrypted with the public key. This is the basis for digital signatures. Anything that is encrypted with a public key can be encrypted only with the corresponding private key. This is the basis for authentication and covert communication.
A one-way function is one that can be computed relatively easily in one direction but there is no direct way of computing the inverse function. One-way functions are crucial in a number of cryptographic algorithms, including digital signatures, Diffie-Hellman key exchage, and RSA public key cryptography. For Diffie-Hellman and RSA keys, they ensure that someone cannot generate the corresponding private key when presented with a public key. A particularly useful form of a one-way function is the hash function. This is a one-way function whose output is always a fixed number of bits for any input. For good cryptographic hash functions, it is highly unlikely that two messages will ever hash to the same value, it is extremely difficult to construct text that hashes to a specific value, and it is extremely difficult to modify the plaintext without changing its hash. The hash function is the basis for message authentication codes and digital signatures. Note that when we talk about cryptography and mention phrases like "extremely difficult", we mean "impossible for all practical purposes," not that you can do it if you spend an entire day working on the problem.
Monoalphabetic substitution ciphers
The earliest form of cryptography was the substitution cipher. In this cipher, each character of plaintext is substituted with a character of ciphertext based on a substitution alphabet (a lookup table). The simplest of these is the Cæsar cipher, in which a plaintext character is replaced with a character that is n positions away in the alphabet. The key is the number n. Substitution ciphers are vulnerable to frequency analysis attacks, in which an analyst analyzes letter frequencies in ciphertext and substitutes characters with those that occur with the same frequency in natural language text (e.g., if "x" occurs 12% of the time, it's likely to really be an "e" since "e" occurs in English text approximately 12% of the time while "x" occurs only 0.1% of the time).
Polyalphabetic substitution ciphers
Polyalphabetic ciphers were designed to increase resiliency against frequency analysis attacks. Instead of using a single plaintext to ciphertext mapping for the entire message, the substitution alphabet may change periodically. In the Alberti cipher (essentially a secret decoder ring), the substitution alphabet changes every n characters as the ring is rotated one position every n characters. The Vigenère cipher is a grid of Cæsar ciphers that uses a key. The next character of the key determines which Cæsar cipher (which row of the grid) will be used for the next character of plaintext. The position of the plaintext character identifies the column of the grid.
Rotor-Machines
A rotor machine is an electromechanical device that implements a polyalphabetic substitution cipher. It uses a set of disks (rotors), each of which implements a substitution cipher. The rotors rotate with each character in the style of an odometer (after a complete rotation of one rotor, the next rotor advances one position). This allows for a huge number of substitution alphabets to be employed before they start repeating (the rotors all reach their starting position). The number of alphabets is cr, where c is the number of characters in the alphabet and r is the number of rotors.
An input character creates a circuit that goes through the set of disks. Each disk has a set of input and output contacts and wiring within that permutes an input to an output (implementing a substitution alphabet).
Transposition ciphers
Instead of substituting one character of plaintext for a character of ciphertext, a transposition cipher scrambles the position of the plaintext characters. Decryption is the knowledge of how to unscramble them.
One-time Pads
The one-time pad is the only provably secure cipher. It requires a completely random key that is as long as the plaintext. Each character of plaintext is permuted by a character of ciphertext (e.g., add the characters modulo the size of the alphabet or exclusive-or binary data). The reason this cryptosystem is not particularly useful is because the key has to be as long as the message, so transporting the key securely becomes a problem. The challenge of sending a message securely is now replaced with the challenge of sending the key securely. Moreover, the recipient needs to have a key that is as long as all the messages that a sender might send and the sender's and recipient's position in the key (pad) must be synchronized at all times. Error recovery from unsynchronized keys is not possible. Finally, for the cipher to be secure, a key must be composed of truly random characters, not ones drived by an algorithmic pseudorandom number generator. Because the key is as long as a message, any ciphertext can be converted to any plaintext, depending on the key that is used.
DES
The Data Encryption Standard, DES, was standardized in 1976 and is a block cipher that encrypts 64-bit chunks of data at a time. It uses a 56 bit key and employs 16 iterations of substitutions followed by permutations.
The only serious weakness of DES is its key 56-bit key. By the 1990s it was possible to build machines that can iterate through all of the 256 permutations of keys within a few hours. Networked efforts can also test hundreds of billions of keys per second.
To prevent against such a brute force attack, DES would need a longer key. Triple-DES solves this problem by using the standard 56-bit DES algorithm three times:
C = EK3(DK2(EK1(P)))
If K1 = K3, then we have a "classic" Triple-DES mode that uses a 2*56 (112-bit) key. If K1 = K2 = K3, then the middle decryption undoes the first encryption and we have a standard 56-bit DES algorithm. Finally, if all three keys are different, then we have a 168 bit (3*56) key
