|
|
Browse by Tags
All Tags » Security Concepts (RSS)
-
This post is to tie up some loose ends in regards to actually performing the RSA computations. I've avoided including too much math in the earlier posts to make them easier to read. Here are some references that help explain the individual steps. The algorithm starts with generating n, a product of large primes, and e, the encryption exponent. Large primes are typically found by generating large random numbers and testing whether they're probably prime . It's easy to eliminate the random numbers that are obviously not prime, such as multiples of small primes, leaving only a few hundred tests necessary to find a 1024-bit or 2048-bit random prime number. The encryption exponent is frequently a fixed, small value, such as 65537. Using e = 3 used to be relatively popular because the exponentiation step becomes very cheap, but we've seen how this is sometimes dangerous . The decryption exponent, d, is the modular inverse of the encryption exponent. Modular inverses can be found using the Euclidean algorithm . Messages are encrypted by exponentiating the plain text message with the encryption exponent. M' = M e mod n Messages are chunked into fixed-size blocks to make them easier to work with. Messages are decrypted by exponentiating the encrypted message with the decryption exponent. M' d mod n = (M e mod n) d mod n = M e*d mod n For both of the large primes that make up n, we can use Fermat's Little Theorem to show that M e*d = M modulo the prime number. We can then use the Chinese Remainder Theorem to combine these congruences and show that M e*d = M mod n. Next time: ROT 128 Stream Upgrade Sample, Part 1 Read More...
|
-
One of the interesting things about writing articles ahead of time is that the plan sometimes changes when it's time to publish the articles. It turns out that in the last few weeks someone has found an interesting forgery attack on RSA signatures . This isn't a totally general forgery attack because like one of the attacks we saw yesterday, it primarily affects RSA keys with small exponents . Unlike the attacks yesterday, this isn't a protocol failure because it relies on the signature verification algorithm having a bug. However, it turns out that the bug required is actually a pretty easy one to make. This new attack is from Daniel Bleichenbacher and it relies on signature verifiers not correctly interpreting an invalid PKCS message chunk. We saw earlier what the contents of the block are supposed to look like 0x00 0x01 0xff ... 0xff 0x00 hash This hash field is actually a combination of some metadata and the computed hash value. Inside the metadata is a length field that tells you how long the computed hash value is. The bug is that some implementations allow garbage data inside the message chunk after the hash is complete. In that case, the block looks like 0x00 0x01 0xff ... 0xff 0x00 metadata hash garbage If the RSA exponent is small, such as e = 3, then the attacker can manipulate the garbage data to make the value be a perfect cube. The attacker can then compute the cube root to construct a signature value that the validator will accept. This attack gets extremely less likely as the exponent gets larger. A good reference on this attack is Hal Finney's summary of the Bleichenbacher talk . Next time is the last article on security for a while before we get back to stream upgrades. Next time: Math Behind the RSA Algorithm Read More...
|
-
RSA has several weaknesses called protocol failures. Protocol failures are not actually an exploit in the RSA algorithm. Instead, a protocol failure occurs when you perform inadvisable actions that give the attacker more information than they would otherwise have. The most common attack that results from a protocol failure is a direct mathematical attack that does not rely on breaking the normal strong point of RSA, the difficulty of factoring the product of two large prime numbers. Instead, the mathematical attack uses additional information from the protocol failure to bypass the protection without having to find the factorization. Today, I'll talk about two protocol failures that occur when you send the message multiple times with different RSA parameters n and e. The common modulus failure occurs when you send the same message M with the same modulus n but different values for the encryption exponent e. Suppose you send the message once with the exponent e and again with the exponent f. If e and f have no common factors, which is the case when both are prime numbers, then you can use the Euclidean algorithm to find values r and s where e*r + f*s = 1. The e and f values were public, so anyone can compute r and s. You've sent the encrypted values M e mod n and M f mod n over the wire. Unfortunately now, (M e mod n) r *(M f mod n) s =M e*r+f*s mod n=M mod n, so it turns out to be quite trivial to figure out what the original message value was. The small exponent failure occurs when you send the same message M with the same exponent e but different values for the modulus n. While the previous attack needed two messages, this attack needs e messages making it relatively hard to pull off if e is not a small value. Each message you send on the wire looks like M e mod n i for different moduluses n i . Using the Chinese Remainder Theorem, you can compute a value M' such that M' is simultaneously congruent to M e modulo n 1 and n 2 and all the way up to n e . Since M must be smaller than each n i for RSA to work, M e is smaller than the product of all the n i 's, and therefore M' is not just congruent to M e but exactly equal to it. The modulus is larger than the number we're trying to reduce so it has no effect. Figuring out the original message then simply requires taking the e-th root of M'. Next time: A More Recent RSA Attack Read More...
|
-
A nice property of RSA is that if we swap the role of the encryption and decryption keys, it’s still possible to transmit messages . That’s because the computation (M e ) d mod n is the same as (M d ) e mod n. Typically, messages are encrypted with your public key, which means that only a person with your private key can read the message. Anyone can pick up your public key and send you a message. Turning that around, you’re the only person that can send someone else a message using your private key. However, anyone can pick up your public key and decrypt that message. This allows us to prove who the sender of the message is to the same accuracy as protecting the contents of the message. To save space, it’s not necessary to sign the entire message with your private key. Instead, you can take a hash function for which it is difficult to find collisions and sign the hashed version of your message. This allows you to create a fixed-length signature for use with arbitrarily long messages. Signing is not compatible with the algorithm presented yesterday for chunking messages . Each chunked message for encryption contains randomly-generated padding bytes. This means that the signature would unpredictably change every time we tried to recompute the message. Signing uses a padding block where every byte of padding has the value 0xff. To make sure that you know which type of padding is being used, the block type for signing is 0x01 instead of the block typeof 0x02 for encryption. The contents of a block look like 0x00 0x01 0xff ... 0xff 0x00 hash The same private key should not be used for both signing and encrypting messages. Generate multiple key pairs in that situation to prevent information attacks where an attacker has access to messages signed by both the public and private keys. Next time: Attacks on RSA Read More...
|
-
For your particular pair of RSA primes, there is a fixed size to the messages that can be encrypted with the product, n, of those primes. During decryption, you will always end up with the smallest positive integer message that satisfies the algorithm. That means that the value of your message has to be smaller than the value n to be unique. With a 1024 bit product of primes, you can only send a 1024 bit message. On the other hand, if the message value is too small, such that the modulus operation during encryption doesn’t do anything, then cracking the message becomes much easier. This means that each message should be approximately the same size but slightly smaller than n. Like many other problems, this is a job for message chunking. There is a defined standard for chunking RSA messages included in PKCS #1 (Public Key Cryptography Standard #1). There’s been several versions of the standard due to discovered vulnerabilities. I’ll use the original version since it’s the simplest but obviously you should not be using this version in your applications today. If your value of n is k-bits long, then each block is going to be k/8 bytes long. The contents of a block look like 0x00 0x02 padding 0x00 data The 0x02 stands for the block type. We’ll look at another block type tomorrow for use when signing messages instead of encrypting. The padding is then eight or more random non-zero bytes. The padding bytes prevents people from attempting to guess the original text and encrypting with the public key to check their guess. With padding, you would need to guess both the plain text and the random bytes, which can be made more expensive than attempting to crack the product of primes. During decryption, the padding is stripped off by starting from the third byte and scanning until the first non-zero byte. The data consists of the remaining bytes in the message. The padding requirement means that there’s a minimum of 11 bytes overhead in each chunk. For 1024 bit chunks, that works out to roughly 1 byte of overhead per 10 bytes of actual data. Next time: Using RSA for Signing Messages Read More...
|
-
One of the key points made about the Diffie-Hellman algorithm is that it doesn’t actually allow you to send a message from one party to another. DH is useful for constructing a new shared secret value but can’t directly be used to exchange an existing secret. The alternative that is typically used for exchange is RSA (named after the inventors Ronald Rivest, Adi Shamir, and Leonard Adleman). A lot of people spell the last one as Adelman, which as far as I can tell is incorrect. The idea of RSA is very similar to an earlier cipher called Pohlig-Hellman. RSA requires the recipient to publish two numbers, called n and e, in a directory with their identity. The n and e values play a very similar role as the group values p and g from DH. The value n is actually the product of two large prime numbers, called x and y, that the recipient keeps secret. The evidence we have is that the easiest way to break RSA is to factor n back into the primes x and y. This means that the security that the system provides is equivalent to the amount of work required to perform the factorization. This is again analogous to the security of DH provided through the difficulty of deriving the private keys A and B. To send a message M with RSA, the sender first retrieves n and e from the directory. The sender then computes M e mod n and sends that value over the wire. Call the encrypted value M’. The recipient computes a value d such that d*e = 1 mod (x – 1) and d*e = 1 mod (y – 1). It isn’t obvious how to efficiently compute this d, but it turns out to not be expensive using a variation of the Euclidean algorithm. The recipient then computes M’ d mod n, which reverses the encryption and returns the original value M. No one else can find the d to do this unless they can factor out x and y first. The similarities between DH and RSA don’t stop at the description. The size of the RSA primes you need to protect your message M is roughly the same as the DH prime you need to protect your exchanged key. This means that I don’t need to repeat the article on configuring the algorithm . Instead, I’ll go off in a different direction and talk about how to chunk a large message into multiple M values for use with RSA. Next time: Splitting Messages for RSA Read More...
|
-
We’re going to continue looking at the Diffie-Hellman algorithm today by examining how to configure the algorithm to be more resistant to attacks. DH is small enough that I’m not going to summarize the algorithm here. You can go back to the description yesterday if needed. I’ll reuse the same letters g and p for continuity. The values g and p are exchanged publicly, perhaps by putting them into a public certificate. There are two modes of DH depending on whether the generated keys for a particular g and p combination are reused. Static DH reuses the key values. Using static keys is faster and doesn’t really give any aid to an attacker that can precompute data. Ephemeral DH makes up a new set of keys for every transaction. The advantage of ephemeral keys is that they can be thrown away afterwards and even breaking into the machine later can’t help you recover what was exchanged. The sender and receiver can use different modes so ephemeral-static DH is an example with an ephemeral sender and static receiver. The other major choice when configuring DH is how big to make p and the private keys. In general, it’s easier to attack p than to attack a private key. This means that p requires more bits than a private key does. Further, the private key needs to be longer than the key that is being constructed through DH. I have seen rules of thumb that the private key should be twice as long as the exchanged key and that a 1024 bit prime p has an effective limit of a 160 bit private key. This means that a 1024 bit prime is really only good for safely constructing about an 80 bit key, smaller than the 112 bits of 3DES. You should be doing some independent reading about the DH algorithm if you actually need to pick the appropriate size of p and other desirable mathematical properties. The good news is that suites like SSL combine selected modes of DH with other techniques to protect against common attacks, such as man-in-the-middle while starting up the conversation. That means that your security does not require understanding any of this. Next time: Using RSA for Sending Messages Read More...
|
-
If you’ve been reading the previous posts on network security , then you’ve seen several instances where two parties need a shared secret. We’ve just been assuming that a shared secret is magically known. How can two parties share a secret without having previously arranged confidential information between them? This is the boot-strapping problem of encryption, because it seems like exchanging a secret requires that you’ve exchanged secrets before. However, it turns out that two parties can build a shared secret even if all of the communication between them can be intercepted. Diffie-Hellman (DH) is an algorithm that lets two parties collectively create an encryption key. You can’t directly use DH to send data from one party to another. DH lets you create an encryption key, and then you can use that key to send the data. In DH, there are two public numbers for the conversation, a shared public key for each side, and a hidden private key for each side. To start a key exchange, the two sides first share a large prime number p and a base value g that is between 1 and p - 1. These numbers can be agreed on in public, so there’s no need to protect the conversation from eavesdroppers. This allows the exchange to start without having a prearranged secret. Each side then picks a secret value that doesn’t get shared. Call the two sides and their corresponding numbers A and B. A sends g A mod p over to side B. B sends g B mod p over to side A. The values sent over the wire are still totally public. This relies on the fact that even when g, p, and the result are publicly known, it’s still very difficult to compute A or B. A knows the value A and g B mod p, making it simple for A to calculate g AB mod p. B knows the value B and g A mod p, making it simple for B to calculate g AB mod p. Anyone else would be unable to compute this value, making it possible to use this shared result as an encryption key. How difficult is it to compute g AB mod p given g, p, g A mod p, and g B mod p? That actually isn’t known, although all evidence so far points to it being quite challenging. Next time: Attacks on Diffie-Hellman Read More...
|
-
The last cipher I'm going to talk about is the Advanced Encryption Standard (AES). With this, we'll have covered about half of the important algorithms needed for a transport security implementation, such as SSL. AES started out as a contest to replace DES for use by the US government. Several submissions were made, including one called Rijndael by Joan Daemen and Vincent Rijmen. Rijndael won the contest and became AES. AES is a 128-bit block cipher with a variable length key from 128 to 256 bits. Encryption keys of 128 bits are the current minimum standard for encrypting information that has an expected lifetime of several years. The implementation of AES is significantly more complicated than for DES. AES has a key expansion stage and rounds that consist of four operations on a matrix of state bytes. The matrix operations mix in bytes from the key, modify the elements of the matrix, permute the entries in the rows of the matrix, and transform the matrix columns. These rounds are repeated 10 to 14 times depending on the size of the encryption key. The final round concludes by mixing in additional key bytes. Rather than writing your own implementation of AES or any of the algorithms that I've been talking about, you should get a standard and well-tested implementation. Most of these algorithms are available in the System.Security.Cryptography namespace. The only significant attacks on AES are known as side-channel attacks. A side-channel attack uses observations of coincidental information, such as power usage, cache hits, and execution times, to extract information about the internal state of the algorithm. If AES is run on a general-purpose processor and another process can force you to encrypt text with your secret key, then that process can extract the encryption key in a surprisingly short amount of time. When there is a lot of activity on the system, these attacks are still possible but may require averaging of many more measurements to obtain the answer. Most algorithms are vulnerable to side-channel attacks if you give attackers enough access to the device. Next time: Introducing MessageState Read More...
|
-
Block ciphers are more popular than stream ciphers , with several either in active use or recent enough to require supporting for legacy interoperability. I'll talk about the RC2 and DES algorithms today and cover the newer AES algorithm tomorrow. DES was a widely-used and analyzed cipher algorithm developed for use by the US government. DES is a 64-bit block cipher with a 64-bit key. However, 8 bits of the key are parity bits that are discarded by the algorithm so the effective key strength is 56 bits. DES works by expanding the contents of an input block by duplicating some of the bits, mixing the expanded input block with key bits derived from the encryption key, applying a non-linear transformation to the mixed bits, and finally permuting the output bits of the transformation. This process is called a round and the overall algorithm uses 16 rounds on each block. Although there's no trivial way of breaking DES, the small key space means that brute forcing a message doesn't require that much computer power. A variant called triple-DES consists of the same algorithm applied with three different keys in succession. Due to some cryptoanalytic properties, triple-DES only doubles the number of effective key strength bits to 112. However, this is still a considerable leap over normal DES. All variants of DES are now deprecated in favor of using AES. RC2 is another algorithm by Ron Rivest (there's an entire product line of these things) that intends to be very similar in application to DES. RC2 also is a 64-bit block cipher but has a variable key size of up to 128 bits. The variable key size allowed RC2 to be used in a degraded mode that met the US encryption restrictions at the time. RC2 is faster than triple-DES and includes a key salt to prevent precomputing large tables of encryption keys. RC2 has a similar round system to DES but uses two different types of rounds called mix and mash. The details of these rounds were published as RFC 2268. Both RC2 and RC4 were secret algorithms until their source code was anonymously leaked in the mid-1990s. Next time: Advanced Encryption Standard Read More...
|
-
The list of commonly used stream ciphers is very short because there's really only one. RC4, developed by Ron Rivest, is essentially the only stream cipher that has been widely deployed. RC4 is very fast and found in wireless networking devices, as part of Wired Equivalent Privacy (WEP) and WiFi Protected Access (WPA), among other places. WEP does not offer much protection because a wireless network with lots of WEP traffic will reuse portions of the key stream if you listen patiently for a while. This is exactly what you weren't supposed to do with stream ciphers. This is more a poor use of RC4 rather than a flaw in the algorithm itself. WPA is a replacement for WEP that provides better security. The RC4 key stream is generated from a 256 byte state array using a pseudorandom number generator. Each time random bits are generated, the state array gets slightly scrambled so that future output bears very little resemblance to past output. The state array is initialized by the encryption key. Encryption keys can be between 1 and 256 bytes long, with shorter keys essentially repeated to pad out the length. Initially, the state array has a fixed value. The algorithm is then initialized by looping over the repeated encryption key and scrambling the state array according to the key bit values. The encrypted stream is generated by taking the exclusive-or of the bits of the input stream with the randomly-generated bits. Next time: More Symmetric Cipher Suites Read More...
|
-
When using symmetric encryption, repetition is the enemy of security. For the basic stream cipher and block cipher algorithms, an attacker can exploit repetition in either the input or key to gain information about the protected message. Stream ciphers have a straightforward attack if you encrypt two messages with the same portion of a key stream. Due to the symmetry of encryption and decryption, you can apply the encrypted stream of one message with the encrypted stream of the other message and produce a predictable combination of the input streams. Depending on what you know about the structure of the messages, this may be enough to allow you to untangle the plaintext of each message. Of course, if the attacker controls one of the messages, then they can simply decrypt using the message text to directly obtain the encryption key. The solution to this problem is to never reuse a key stream and regenerate keys when the stream is about to repeat. Block ciphers have a similar attack when a message contains the same block more than once. Since a particular block value in one message will always encrypt to the same value, it's possible to analyze the repetitions and learn something about the input text. This type of repetition is defeated by chaining the value of the current block of input text with the value of the previous encrypted block using some function. Someone that knows the encryption key can easily undo this process but it's otherwise very difficult to find repetitions because the same encrypted text can be decoded multiple ways depending on the previous blocks. There's nothing with which to chain the first block so many algorithms create a random salt to use for initialization. This salt value is then included in the message for decoding. Even with these protections, it's still possible for two encrypted blocks to have the same value. The next pair of blocks is then susceptible to analysis because the input value being chained is the same in both cases. Fortunately, this is a rare occurrence with a large enough block size. It just so happens that we've already figured out how likely this is to occur . Next time: Symmetric Cipher Suites Read More...
|
-
Yesterday I kicked off the topic of symmetric encryption by talking about block ciphers . Stream ciphers are another common pattern for symmetric encryption algorithm. Unlike block ciphers that operate on chunks of input text, a stream cipher operates on a byte-at-a-time basis using an input stream. Actually, a stream cipher works using two data streams. The first data stream is the stream of input text. The second data stream is the stream of key data. The key data stream is generated by a function whose seed is the encryption key. Encryption works by taking a byte (or similarly sized piece) from the input stream and a byte from the key stream and combining them using some function. Typically, that function is a really simple one, such as exclusive-or. Security is provided by making the key stream hard to guess rather than making the algorithm complex. Decryption works in reverse by taking a byte from the encrypted stream and a byte from the same key stream to return the byte from the input stream. This works because the generated key stream is always the same for a particular encryption key and the encryption function has a simple reverse operation (itself). Stream ciphers are very simple but have more obvious weaknesses than the block ciphers we looked at yesterday. Stream ciphers are susceptible to targeted tampering of the message because changes to the text are narrowly scoped. Flipping a single bit in the encrypted text won't affect any of the surrounding text when the message is decoded. Flipping that same bit with a block cipher affects all of the bits in that block. There are also several attack methods if you reuse portions of the key stream for multiple messages. Since an encryption key can only generate a limited amount of key stream, safely encrypting more text requires exchanging more encryption key bits. Most of the commonly used algorithms for symmetric encryption are block ciphers. Next time: Symmetric Encryption Algorithm Design Issues Read More...
|
-
Back in May I gave a brief introduction to encryption and decryption . The next few posts are a short series on symmetric encryption algorithms, which use a shared secret key for both encryption and decryption. I've got a little bit of coverage about the general algorithms and issues with this type of cryptography before giving some examples of the actual algorithms that are used. The encryption algorithms I'll talk about come in two varieties, called block ciphers and stream ciphers. Block ciphers split the input text into fixed-size chunks called blocks. Each block of the input is exactly the same length as all of the other blocks, for example 16 bytes. Since most input texts are not going to be an exact multiple of the block size, the encryption algorithm needs to pad the input text with some additional bytes to fill out the last block. The decryption algorithm needs to remove those pad bytes before returning the resulting text. Typically, the number of pad bytes is added to the message for this purpose, meaning that every message encrypted by a block cipher is between 1 and the size of the block bytes larger than before encryption. Small messages can be inefficient to transmit using block ciphers. The operation of a block cipher is to take a block of input text and a block of key to produce a block of output text. You can think of this action as a table that contains all of the possible input text blocks as rows and all of the possible key blocks as columns, giving a value for every row-column combination. This table defines the function for encryption. There's then another table that defines the function for decryption. If you've got an input block M and a key block K, then the encryption function gives you an output block O. If you then look at row O, column K of the decryption function table, then the value of that entry will be M. As long as the two sides know the key blocks, they can exchange messages. The weakness of this simple method is that if we use a fixed key block and parts of the message repeat, then the corresponding parts of the encrypted text will also repeat. When we look at symmetric encryption algorithm issues, this is one of the ones we'll try to address. Next time: How Stream Ciphers Work Read More...
|
|
|
|