Modern Ciphers | .NET Security and Cryptography

Modern ciphers do not operate on a set of letters such as A through Z, but Caesar was probably unfamiliar with the concept of bits and bytes! Instead, modern ciphers use numbers, sometimes extremely large numbers , to represent keys and plaintext or chunks of plaintext. Arithmetic is used to implement encryption; however, it may not always be the arithmetic you recall from grade school.

Cryptography and the .NET Framework

The .NET Framework class library provides the System.Security.Cryptography namespace, which supports the most important symmetric and asymmetric ciphers as well as several secure hash algorithms and a cryptographic-quality random number generator. This cryptography architecture is extensible, allowing third parties to provide alternative implementations and additional algorithms, in the form of cryptographic service providers. The System.Security.Cryptography. XML namespace implements the W3C standard for digitally signing XML objects, and the System.Security.Cryptography.X509Certificates namespace provides some support for working with public certificates. Here are the major standards implemented by the .NET Framework class library. We review most of these features in more detail in Chapters 3, 4, and 5.

DES : Digital Encryption Standard (symmetric block cipher)
3DES : Triple DES (symmetric block cipher; stronger alternative to DES)
Rijndael : AES ^[27] (symmetric block cipher)

^[27] The U.S. government selected Rijndael as the AES (Advanced Encryption Standard) encryption standard in October 2000, replacing the DES.
RC2 : Cipher design by Ronald Rivest (symmetric stream cipher)
RSA : Cipher design by Rivest, Shamir, and Adleman (asymmetric algorithm for both encryption and digital signatures)
DSA : Digital Signature Algorithm (asymmetric algorithm only for digital signatures)
MD5 : Message digest (i.e., a secure hash) algorithm developed by Rivest
SHA-1, SHA-256, SHA-384, SHA-512 : Standard secure hash algorithms developed by NIST (National Institute of Standards and Technology) along with the NSA (for use with the Digital Signature Standard)
Pseudorandom Number Generator (PRNG)
XML Signatures : Digital signatures for XML data
X.509 : Public certificates standard

Symmetric Cryptography

Just as the telegraph was a technology in the 1800s that spawned new interest in cryptography, the digital computer, which itself was born out of a need for cryptanalysis in World War II, created an enormous new interest in developing new cryptographic algorithms. From this, the fastest and strongest ^[28] cryptography in history came into being in the form of modern symmetric block ciphers. The fruits of this came in the form of DES, Triple DES, AES, and several others.

^[28] You may recall that the OTP is theoretically the strongest cipher possible. However, the OTP is not practical for most realistic scenarios due to the large key size and the difficulty in securely storing and exchanging keys. Therefore, modern symmetric block ciphers are considered to be the strongest practical ciphers available.

Horst Feistel, working at IBM in the early 1970s, developed symmetric block cipher designs that eventually evolved into the Data Encryption Standard ^[29] (DES). In DES the same algorithm and the same 56-bit key are used for encrypting and decrypting a message. The DES design is based on repeating 16 rounds, where each round is comprised of a substitution followed by a permutation on a 64-bit input data block. The effect is to introduce confusion and diffusion into the ciphertext in each round, but, of course, in a reversible manner. Substitution adds confusion, since it makes the relationship between plaintext and ciphertext more complex. Transposition results in diffusion, since it rearranges the information, which tends to dissipate statistical redundancies in the plaintext throughout the ciphertext .

^[29] DES was adopted as a standard by NIST, and it is documented in FIPS PUB 46, published in 1977.

Since plaintext data is not typically a multiple of 64 bits, it must first be broken into 64-bit blocks, and then the last partial block must be padded with any required additional bits. Each DES round takes a 64-bit block of input data, which is then partitioned into two 32-bit halves . The right half is encrypted with a specialized encryption function ^[30] using a subkey unique to the current round, and XORed with the left portion to form the new right portion for the next round. The previous right portion is then substituted into the left portion for the next round. Figure 2-9 shows the basic structure of a single round of DES. We cover DES and other symmetric block ciphers in more detail in Chapters 3.

^[30] This specialized encryption function is described in Chapter 3.

Figure 2-9. A single round of DES.

graphics/02fig09.gif

During the 1990s, DES had probably come to the end of its useful life. To maintain backward compatibility with much hardware and software, many organizations have adopted Triple DES, which is really just regular DES repeated three times with distinct keys. However, DES has recently been formally replaced by a symmetric block cipher called Rijndael as the new AES ^[31] standard. Rijndael, pronounced "rain doll" or "Rhine doll," was designed by the Belgian cryptographers Joan Daemen and Vincent Rijmen.

^[31] For more information on the new AES standard, please see http://csrc.nist.gov/encryption/aes/.

The .NET Framework provides the following classes for working with several important symmetric algorithms.

System.Security.Cryptography. DES
System.Security.Cryptography. RC2
System.Security.Cryptography. Rijndael
System.Security.Cryptography. TripleDES

Asymmetric Cryptography

Asymmetric cryptography, which was publicly introduced in the late 1970s, ^[32] is a relatively new invention in the long history of cryptography. It is actually quite surprising that it was not invented much earlier, considering that it solves the very long-standing problems of securely exchanging keys and allowing spontaneous secure messaging. These have been vexing problems confronting well- funded governments for centuries and large corporations for decades. What adds to this curiosity is that the mathematics behind asymmetric encryption was well-known for several hundred years . However, it was not until Whitfield Diffie and Martin E. Hellman ^[33] published the article "New Directions in Cryptography" in 1976 that asymmetric cryptography was born.

^[32] There are claims that some form of asymmetric encryption was secretly used by British intelligence in the 1950s.

^[33] Partial credit must also be given Ralph Merkle, who was working independently on closely related ideas.

Asymmetric cryptography uses modular arithmetic and simple number theory to make it possible to construct two distinct keys. One of the keys is used for encryption, and the other is used for decryption. Together they form a key pair. Although the two keys are intimately mathematically related to one another, it is exceedingly difficult to determine one by only knowing the other. One of the keys is made publicly known, and the other is retained as a closely guarded secret.

Privacy and confidentiality can be achieved by encrypting with the public key and decrypting with the private key. On the other side of the coin, authenticity, integrity, and nonrepudiation can be achieved by encrypting with the private key and decrypting with the public key.

In every case, asymmetric cryptography is based on the idea of a one-way function that has a trapdoor. The details on what this actually means are clarified in Chapter 4. For now, we can loosely describe a one-way function as any function that is easy to calculate in the forward direction but very hard to calculate in the reverse direction. In other words, given x , it is easy to find y = f ( x ), but given y , it is very hard to find x = f ¹ ( y ). You probably know many analogies to this from everyday life. For example, it is easy to put milk into your coffee, but just try to get it back out!

A trapdoor one-way function is simply a one-way function that suddenly becomes much easier to calculate in the reverse direction if you are provided additional secret information (i.e., a key). A backdoor for getting the milk back out of your coffee would be specialized knowledge of organic chemistry , enabling you to separate the milk using a complex sequence of chemical reagents, followed by filtering and a whirl on the centrifuge. However, I do not think that I would want to drink the result!

Several asymmetric encryption algorithms have been devised, including the RSA, ElGamal, and ECC Cryptosystems. ^[34] However, by far the most heavily used is RSA. We will go into much more detail on the mechanics of the RSA cipher in Chapter 4, but here is a quick overview of the process. First, Alice decides that she wants to allow Bob to send her a secret message:

^[34] Each of these is based on a different one-way backdoor function resulting from a specific mathematical problem. RSA is based on the integer factorization problem, ElGamal is based on the discrete logarithm problem, and ECC is based on the elliptic curve discrete logarithm problem. Although it has never been mathematically proven, many researchers are now inclined to believe that ECC is the strongest known asymmetric cipher. RSA stands for its inventors, Ron Rivest, Adi Shamir, and Len Adleman. ElGamal is named after its inventor Taher ElGamal. ECC stands for Elliptic Curve Cryptography, which was proposed by Neal Koblitz and Victor Miller in 1985.

Alice randomly picks two large prime numbers p and q, which she keeps as the secret key ( p,q ).
Alice multiplies the two large prime numbers to obtain the product n = p q .
Alice calculates Euler's totient function f ( n ) = ( p 1)( q 1). The function f ( n ) is the number of number of integers less than n that are relatively prime to n .
Alice selects an exponent value e such that 1 < e < f ( n ) and gcd( e, f ( n )) = 1.
Alice makes the product n and the exponent e available together as the public key ( n,e ).
Alice calculates d as the modular inverse of e such that for any x, then x = ( x ^e ) ^d (mod n ).

Then Bob encrypts a message and sends it to Alice:

Bob obtains the public key ( n,e ).
Bob creates a plaintext message in the form of a number p .
Bob calculates the ciphertext c = p ^e (mod n ), and sends it to Alice.

However, Eve is frustrated:

Eve obtains c .
Since she does not know d, she cannot calculate p = c ^d .
She also cannot calculate d from knowledge of the public key ( n,e ), since factoring n is too difficult.

But Alice is happy:

Alice obtains c .
Alice directly calculates the plaintext p = c ^d .

The .NET Framework provides the following classes for working with various asymmetric algorithms.

System.Security.Cryptography. DSA
System.Security.Cryptography. RSA

Cryptographic Algorithms

Aside from the major symmetric and asymmetric cipher algorithms, there are several important support algorithms, including random number generation and secure hash algorithms. Future chapters go into detail on cipher-specific algorithms, such as DES, RSA, and so forth. However, because PRNGs and secure hash algorithms are generally fundamental to practically all aspects of cryptography, we look at them briefly here. We do not have much more to say about PRNGs beyond our discussion in this chapter; however, we will look more closely at secure hash algorithms in Chapter 5, where we discuss digital signatures and hash authentication codes.

PSEUDORANDOM NUMBER GENERATORS

PRNGs play a very important role in cryptography and security. We have already seen how the OTP cipher critically relies on the randomness of its key to ensure perfect secrecy . In fact, all modern ciphers rely heavily on the randomness of their keys to ensure optimal security strength. If a PRNG-generated number sequence is not sufficiently random, then the numbers sequence may contain analyzable patterns that may be exploited by an attacker. If successful, the attacker may then exploit such a weakness of the PRNG to guess the generated keys that you use, which of course would be a security failure. Symmetric block ciphers typically rely on a PRNG for generating their initialization vector as well as the key.

Unfortunately, it is impossible to generate a truly random number sequence using any deterministic algorithm. Since, without specialized hardware, any computer program is inherently deterministic, all we can hope to achieve is a PRNG. A good quality PRNG is one in which it is very difficult to predict the next number generated based on previously generated numbers. A finite machine executing a deterministic algorithm will inevitably return to the same machine state, resulting in a repeating sequence of numbers, which by definition cannot be a truly random number sequence. PRNGs depend on an initialized value called the seed . Starting with a particular seed value, the PRNG then produces the same sequence of numbers. Of course, the same seed should never be used more than once.

If our source of random numbers cannot be perfect, we would at least like it to be very good. A good PRNG should have as flat a probability distribution as possible so that no numbers are significantly more likely than any other numbers over the long term . Also, no particular sequence of numbers should be more frequent than any other number sequence.

If you are willing to go to the extreme, specialized hardware may be used, relying on the assumed randomness of certain physical processes, such as the quantum electronic noise of a resistor or diode, or the radioactive decay detected with a Geiger counter. ^[35] Fractals and chaotic systems, ^[36] such as air turbulence, keyboard typing patterns, and lava lamps, have also been used for this purpose. ^[37]

^[35] Whether or not any physical process is truly random is still an open question in quantum physics. Heisenberg and others have made convincing arguments that true randomness does exist in nature. However, Einstein made the famous remark, "God does not play dice." In any case, the randomness of quantum noise and radioactive decay is certainly good enough for any cryptographic application for the foreseeable future!

^[36] Chaos theory is a relatively new branch of mathematics dealing with nonlinear dynamic systems that are deterministic but are nevertheless virtually impossible to predict over the long term. Lava lamps, stock markets, and the human mind are all considered likely to represent chaotic systems. Fractal theory deals with the mathematics of generating huge amounts of information from an initially very small piece of information, which is exactly what a PRNG must be able to do.

^[37] Either the random number itself or a seed for a PRNG is generated by calculating the cryptographic hash of a continuously changing digital image of a lava lamp.

PRNG AND THE .NET FRAMEWORK

The random number generators that are typically provided in standard platform APIs, such as Windows and UNIX (i.e., the srand and rand functions) are not of the high quality required for cryptographic applications. The .NET platform's Random class is also not good enough. The RNGCryptoServiceProvider class provides access to a high-quality PRNG provided by the cryptographic service provider (CSP). However, you may find that you never need to use this class directly, since the .NET Framework cryptographic classes use it internally to generate cryptographic keys.

The abstract base class is RandomNumberGenerator , which derives into only one child class named RNGCryptoServiceProvider . The RandomNumberGenerator class supports the regular Object class methods as well as the GetBytes and GetNonZeroBytes methods, which return an array of bytes containing a cryptographically strong random sequence of values. As indicated by its name , GetNonZeroBytes returns a random byte array that contains no zero values. RandomNumberGenerator also supports two overloadings of the Create method, which creates an instance of a derived concrete implementation of a cryptographic random number generator. Since RandomNumberGenerator is abstract, you cannot create an instance of this class, and you cannot call on these methods directly. Instead, you must use the concrete derived class. Let's look at the signature of these functions.

 public abstract void  GetBytes  (byte[] data //array to fill with random bytes); public abstract void  GetNonZeroBytes  (byte[] data //array to fill with non-zero random bytes); public static RandomNumberGenerator  Create  ();    //creates instance of default PRNG implementation public static RandomNumberGenerator  Create  (string);    //creates instance of specified implementation

The concrete RNGCryptoServiceProvider class can be created and used directly. The following code snippet demonstrates how to generate an array of 128 random bytes using this class. We use the RNGCryptoServiceProvider constructor in this example; however, you could use one of the static Create methods instead if you wish.

 byte[] randomBytes = new Byte[128]; RNGCryptoServiceProvider rngcsp =    new  RNGCryptoServiceProvider  (); rngcsp.  GetBytes  (randomBytes); //array gets random bytes

CRYPTOGRAPHIC HASH ALGORITHMS

A cryptographic hash algorithm takes an arbitrary amount of input data and reduces it to a fixed-length (typically 128, 160, or 256 bits) output. The output is often referred to as a message digest or a fingerprint, and it is highly characteristic of the input data, just as a fingerprint is a highly characteristic trait of a human. Ideally, a cryptographic hash algorithm satisfies the following requirements:

It is difficult to determine the input from the output (i.e., it is one-way).
It is difficult to find an input that will generate a particular output.
It is difficult to find two inputs that will generate the same output.
A single bit change on the input changes approximately 50 percent of the output bits.

A hash algorithm is used to generate a highly characteristic fixed-size fingerprint of an arbitrary-size input data. The output of a hash algorithm can be used for the following purposes:

It can be used in detecting modifications of data.
It plays a role in implementing digital signature algorithms.
It can be used to transform a password into a secure representation that can be safely transmitted over a network or stored in an insecure database.
It can be used to transform a password into an encryption key to be used by a cipher algorithm.

The most commonly used cryptographic hash algorithms are SHA-1 and MD5. The Secure Hash Algorithm (SHA-1) was established by NIST and is specified in the Secure Hash Standard (SHS, FIPS 180-1). SHA-1 produces a 160-bit digest. SHA-1 was followed by SHA-256, SHA-384, and SHA-512, which produce 256-, 384-, and 512-bit digests, respectively. More detailed information is available at http://csrc.nist.gov/encryption/tkhash.html. MD5 produces a 128-bit digest, making it faster, but it is not as secure against brute-force attack. ^[38] MD5 was designed by Ronald Rivest in the early 1990s and was submitted as an RFC, which can be found at www.rfc.net/rfc1321.html.

^[38] One tends to think of a cipher as the only target of an attack. It may seem surprising, but hash algorithms and random number generators can also be the targets of attacks. An attack on a hash algorithm can mean determining the input from a given output or finding two inputs that give the same output. An attack on a PRNG means predicting subsequent outputs based on previous outputs. These attacks may play a role in larger attacks, such as cracking a cipher, tampering with digitally signed messages, or masquerading as someone else.

The following classes are provided by the .NET security framework library for secure hash functionality.

System.Security.Cryptography. KeyedHashAlgorithm
System.Security.Cryptography. MD5
System.Security.Cryptography. SHA1
System.Security.Cryptography. SHA256
System.Security.Cryptography. SHA384
System.Security.Cryptography. SHA512

The KeyedHashAlgorithm class provides the abstract class from which all classes that implement keyed hash algorithms must derive. A keyed hash is like an ordinary cryptographic hash function except that it takes a key as an additional input. Thus, only individuals who know the key that was used to generate the hash are able to verify the hash. There are two classes that derive from KeyedHashAlgorithm: HMACSHA1 and MACTripleDES. HMACSHA1 accepts a key of any size and generates a 20-byte Message Authentication Code (MAC) result using the SHA-1 hash algorithm. HMAC stands for Keyed-Hash Message Authentication Code, which is a NIST standard (see FIPS PUB 198). MACTripleDES generates a MAC using Triple DES as a keyed hash algorithm. It takes a key of 8, 16, or 24 bytes and generates an 8-byte hash. Keyed hash algorithms are most useful in authentication and integrity schemes, providing an alternative to digital signatures.

The other hash classes (implementing the MD5 and SHA hash functions) in the previous list are regular cryptographic hash functions that do not take a key input. They are used in situations where a hash must be used between individuals who have not shared any secret key information.

Cryptographic Protocols

A cryptographic protocol is an agreed-upon convention combining a set of cryptographic algorithms, a sequence of steps, and a group of two or more people to meet a desired security objective.

For example, a simple cryptographic protocol for encrypting and decrypting messages, using both the asymmetric RSA algorithm and the symmetric Triple DES algorithm, could be the following. ^[39] Note that the RSA algorithm is too slow to be used for bulk data encryption, so it is only used on the relatively small Triple DES private key. The faster Triple DES algorithm is then used for bulk message encryption.

^[39] The protocol shown here is kept simple for the purpose of demonstrating the intended concept. However, this scheme is vulnerable to certain attacks. One such exploit is known as the "man-in-the-middle attack." This attack has Eve intercepting all traffic between Alice and Bob, substituting her own devious messages to trick and deceive in various ways. Another vulnerability in this protocol is known as the "replay attack," in which Eve records messages flowing between Alice and Bob. Later, Eve replays one or more of these messages, tricking the recipient into thinking she is Alice or Bob. More sophisticated protocols can be devised to deal with these types of attacks.

Alice and Bob each generate their own RSA public/private key pair.
They each send their public RSA keys to one another but keep their private RSA keys secret.
They each generate their own Triple DES private key and encrypt it using the other's public RSA key. The result can only be decrypted with the corresponding private RSA key.
They each send their encrypted Triple DES private key to one another.
Whenever Alice or Bob want to send a confidential message to the other party, they encrypt their plaintext message using the other party's Triple DES private key and send the resulting ciphertext.
The receiving party receives the ciphertext and decrypts it using the private Triple DES key.

As another example, a cryptographic protocol for ensuring that a message originates from a particular person, using the asymmetric RSA algorithm and the secure hash algorithm SHA-1, could be the following. Again, note that the RSA algorithm is too slow to be used for bulk data encryption. Therefore, RSA is used only on the relatively small message hash value. Also note that this protocol is used to verify the identity of the message source, but it does nothing to ensure the privacy of the message. You can probably see how to elaborate on this authentication protocol to include message privacy.

Alice and Bob each generate their own RSA public/private key pair.
They each send their public RSA keys to one another but keep their private RSA keys secret.
Whenever Alice or Bob want to send a message to the other party, they calculate a SHA-1 hash on their message, encrypt the hash with their own private key, and send the plaintext message along with the encrypted hash to the other party.
Whenever Alice or Bob receives a message and want to convince themselves that it originated from the other party, they decrypt the SHA-1 hash with the other party's public key. They then recalculate the hash from the received message and compare it with the decrypted hash. If they are identical, then they know it did indeed originate from the other party.

Unlike many of the scenarios we have looked at here, cryptographic protocols may involve people who do not necessarily trust one another but nevertheless want to do business with each other. Financial transactions usually fall into this category, and the banking and retail industries have established industry-specific cryptographic protocols to deal with these situations.

Often, cryptographic protocols have been established as computing standards or conventions. For example, the Kerberos protocol is commonly used to ensure that both parties (i.e., client and server) can know if the other party is who he or she claims to be. Another example is the Code Access Security (CAS) model of the .NET platform, where compiled code is digitally signed by its author for verification purposes. Yet another example is the Secure Sockets Layer (SSL) used for confidential communications over the Internet. Of course, there are many other examples, including PGP (Pretty Good Privacy) for secure email and the Diffie-Hellman key agreement protocol for exchanging session keys over an insecure channel without any prior sharing of secrets. There are several standardized cryptographic protocols that are conveniently implemented for use in the .NET security framework.