BitTorrent has added a new method for encrypting peer lists. This is an attempt to avoid ISPs (such as Comcast) blocking connections that seem to be P2P traffic, as I previously wrote. This extension’s advantages and limitations are a good example for illustrating the fundamental leverage both sides have in this battle.

The actual extension is pretty straightforward.  Trackers manage files by their SHA-1 (aka infohash).  The extension specifies that a tracker RC4-encrypt the peer list with a key of SHA-1(infohash).  Thus, a peer must know the infohash of the file they are requesting to decrypt the peer list.  Obviously, they have the infohash since they had to know it to look up the file in the first place.

There are a couple weaknesses in this design.  If an ISP can read the infohash from the peer’s tracker connection, then they can also decrypt the peer list.  This is mitigated by some trackers supporting SSL connections.  Also, the specification allows for reuse of the RC4 keystream, a definite no-no.

Encryption is only a small skirmish in this battle.  Eventually, all traffic will be encrypted and probably encapsulated in SSL-like headers to avoid signature detection.  That will leave ISPs with traffic analysis as their only tool.  Since it appears that at least Comcast is already doing this and not relying on data in the stream, it’s unclear how effective this additional layer of obfuscation will be.

The BitTorrent developers have the advantage in that they control all endpoints (peers and trackers). Their software can take any measures it wants to obfuscate its data signatures (i.e., encryption) and traffic characteristics (i.e., timing or message sizes).  However, the biggest disadvantage is that they don’t control the behavior of non-BitTorrent hosts.

The ISPs have an advantage in that they see all the traffic between the hosts they care about and the Internet.  They can forge packets or even add filters to block particular IPs.  They know the mapping between IP or MAC address and subscriber account.   However, they can’t be sure what software is running on an endpoint and could lose subscribers if their response is too drastic or the wrong application is affected.

Even though traditional wisdom says BitTorrent has the advantage, I think the ISPs have the technical edge in this battle.  Since the BitTorrent developers can’t control hosts that don’t run their software, they will be forced to conform to the traffic profile of web browsing.  Because this is asymmetrical (uplink is only used for small ACKs), the performance advantages of BitTorrent would be eliminated.

However, it’s likely political/judicial moves will have a longer term impact on which side wins.  I think this would be a good thing.  Since there are only two broadband circuit providers in the US (telco or cable), competition won’t eliminate a progression of more onerous requirements for endpoints.  Without intervention, I could see a slow creep towards requiring virus scanning of endpoints or prohibitions on specific applications.  I already have to lie and claim to be running Windows to get tech support to run a line test when my DSL goes down (“oh yeah, it rebooted fine but the line is still down”).

Assuming a bad law doesn’t get added, I think regulation of ISPs would be a good thing to prevent further interference with our traffic.  I refuse to use the Internet as a TV.

Another attack that was addressed in TLS 1.1 results from a predictable initialization vector for encryption. This allows an attacker to verify guesses about previous plaintext and is an interesting example of how slight implementation variations in well-known cryptographic constructions can introduce exploitable flaws. Phil Rogaway and Bodo Moeller have some more detailed notes on such problems.

Remember that CBC encryption is a way of chaining multiple blocks together into a longer message. It first requires an IV to kick things off, then the encryption of subsequent blocks is made unique via each previous block’s ciphertext. Compare this to ECB, where each ciphertext block is independent and thus reveals information about its contents if plaintext is repeated.

An IV must have the following properties:

• Unique: must not be repeated for any message encrypted with a given key
• Unpredictable: an attacker who observes any number of messages and their IVs should have no information to predict the next one with probability of success greater than 50% per bit (i.e., indistinguishable from random)

Uniqueness is necessary because CBC devolves to ECB without it. It’s critically necessary for other modes of operation like OFB or stream ciphers where a repeated seed produces a repeated keystream, which is totally insecure.

Unpredictability is more subtle. The attack on TLS’s CBC IV is based on it being predictable, even though it was unique. More on that later.

Note that an IV does not have to be random. There’s a difference between computational indistinguishability and true randomness. Since you want some assurance that each IV is unique, it’s theoretically better to load an initial seed into a secure PRNG once and then generate only 2^n/2 output bits before re-seeding it. If the PRNG is based on a secure permutation (say, a block cipher), you are guaranteed the sequence will not repeat if you limit the number of output bits before re-seeding. However, in practice, it’s also effective to continue feeding the PRNG entropy as it becomes available as a short cycle is extremely unlikely.

TLS’s record layer provides message boundaries for the application. Each message is typically encrypted in CBC mode if a block cipher like AES is being used. Each time a new message is sent, the last block of the previous message’s ciphertext is used as the IV. This means that an attacker observing the encrypted traffic knows what the next IV will be, even though it is unique/non-repeating.

The attack is simple. After observing a message, the attacker knows the IV for the next message will be ciphertext block C_n-1. Using this knowledge, the attacker can try to guess any previous plaintext block P_x. He does this by constructing a plaintext block with the following format:

P_guess = C_n-1 XOR P_x XOR C_x-1

Let’s break this down. The first item, C_n-1, is the known IV for the next message. P_x is the guess for some previous block of plaintext, any will do. Finally, C_x-1 is the original block of ciphertext before our guessed block of plaintext. We know based on the operation of CBC that P_x was chained with this value.

When P_guess is encrypted, the IV will cancel out (A XOR A = 0), leaving:

C_guess = ENCRYPT(P_x XOR C_x-1)

As you can see, if the guess for was correct, the ciphertext C_guess will be identical to C_x. If the guess is wrong, the ciphertext will be different. This attack may be unrealistic in scenarios where the attacker cannot submit plaintext to the same TLS session as the target. However, this is feasible in shared connections such as a TLS/SSL VPN.

The important lesson here is that both uniqueness and unpredictability are vital when using IVs.

Following my recent posts on TLS/SSL security, I gave a talk (slides are here) on a security flaw in the record layer that was fixed in TLS 1.1. The last page of my slides gives some interesting links if you’re interested in understanding SSL security better.

This flaw (found by Bodo Moeller) is in the use of padding as part of the integrity protection of the actual data being exchanged. Padding is needed because block ciphers encrypt data in chunks and something has to go in the remainder of the last block. This attack is particularly interesting because it allows an attacker to iteratively decrypt part of the message using side-channel leakage.

Side channel attacks are still often neglected, despite proof that they can be performed over the Internet. System designers always seem to have the same initial response when learning about timing attacks: make the computation time constant by adding a calibrated delay. When problems in this strategy are pointed out, their next move is to add a random delay after the computation (not blinding).

This usually repeats with each approach getting shot down until they eventually admit this is a hard problem and that appropriate measures need to be integrated with the actual process (not bolted on) and carefully evaluated for unforeseen problems. For example, one fix for this attack is to always compute the MAC even if the padding is incorrect. However, the logic path of noting that the padding is incorrect but continuing anyway still requires a conditional branch, which creates a small but observable timing difference that can be used in a successful attack.

Preventing side channel attacks is a difficult problem. If confronted with them, take the time to get your countermeasures carefully evaluated.

The first notable attack on SSL 3.0 was Bleichenbacher’s PKCS#1 padding attack (1998). This gave the astonishing result that any possible side channel that gave information about the result of the RSA decryption could be used to iteratively decrypt bits of a previous session key exchange. This was recently applied to an attack on the version information added to the PKCS#1 padding in SSL 3.0.

The fix to these attacks is to substitute random data for the PremasterSecret and continue the handshake if the RSA decryption result fails any validity check. This will cause the server and client to calculate different MasterSecret values, which will be detected in the encrypted Finished message and result in an error. (If you need a refresher on the SSL/TLS protocol, see this presentation.)

Note that this approach still leaves a very slight timing channel since the failure path calls the PRNG. For example, the initial padding bytes in the result would be checked and a flag set if they are invalid. But that check involves a compare and conditional branch so technically there’s still a small leak. It’s hard to eliminate all side channels, so countermeasures to them need to be carefully evaluated.

The attack is quite clever and illustrates RSA’s malleability that I wrote about in this earlier series of articles (with Thomas Ptacek). It involves successive approximation, zeroing in on the value of the plaintext message M by sending variants of the ciphertext (C) to the server. The server decrypts each message and reports “padding incorrect” or continues processing. Remember, this oracle doesn’t have to explicitly report an error message, although that’s the most obvious way to distinguish the decryption result. It could just be a timing difference.

If the server does not report “padding incorrect”, then the attacker knows that the decryption result had the proper PKCS#1 padding (e.g., starts with the bytes ’00 02′ among other things) even though the remaining bytes are incorrect. If these bytes were uncorrelated to the other bytes in the message, this wouldn’t be useful to an attacker. For example, it’s easy to create a ciphertext that AES decrypts to a value with ’00 02′ for the first two bytes but this doesn’t tell you anything about the remaining bytes. However, RSA is based on an algebraic primitive (modular exponentiation) and thus does reveal a small amount of information about the remaining bytes, which are the message the attacker is trying to guess. In fact, an early finding about RSA is that an attacker who can predict the least-significant bit of the plaintext can decrypt the entire message.

The first step of the attack is to create a number of variants of the ciphertext, which is c = m^e mod n. These are all of the form c’ = cs^e mod n, where s is a random number. Once this is decrypted by raising it to d (the private exponent), the s value can be masked off by multiplying it by s^-1. This property is used in blinding to prevent timing attacks.

The second step is to send these values to the server. It decrypts each one and reports a “padding incorrect” error or success (but with a garbage result). For the s values that result in correct padding (’00 02′), the attacker knows the most-significant bit of the result is 0. In the paper, Bleichenbacher refers to this case as 2B <= ms mod n < 3B, which gives an interval of possible values for the message m. As more and smaller s values are found that are PKCS conforming, the number of possible intervals is reduced to one. That is, the union of all conforming ms_i values eliminates false intervals until only one is left, the one that contains the desired plaintext message.

The third step is to increase the size of the s_i values until they confine the message m to a single value. At that point, the original plaintext message has been found (after stripping off the given s_i value).

While this is a brilliant attack with far-reaching implications, it also illustrates the fragility of algebraic cryptography (i.e., public key) when subjected to seemingly insignificant implementation decisions. What engineer would think reporting an error condition was a bad thing?

I recently gave a talk to a networking class at Cal Poly on the design principles behind SSL. The talk was a bit basic because I had to assume the class had little security experience. My approach was to discuss how it works and stop at each phase of the protocol, asking what security flaws might be introduced by changing or removing elements. This worked well to get them thinking about why SSL has certain components that appear weird at first glance but make sense after closer inspection.

Others have told me that they use a similar technique when learning a new crypto algorithm by starting with the simplest primitive, identifying attacks, and then adding subsequent elements until the whole algorithm is present. If attacks still exist, the algorithm is flawed.

For example, consider DSA, one of the more complex signature schemes. Use the random value k directly (instead of calculating r = (g^k mod p) mod q) and the signature operation is simply:

s = k^-1(H(m)) + x mod q

This introduces a fatal flaw. k^-1 can be calculated from k via the extended Euclidean algorithm. The message is usually known, and thus H(m) is also. Thus, this would directly reveal the private key x to any recipient!

The references section at the end of the talk gives a good intro to the design principles behind SSL, especially the Wagner et al paper. My next articles will explain some SSL attacks in more detail.