Author Archives: Erik Tews

SSLv3 considered to be insucure – How the POODLE attack works in detail

POODLE is a recent attack on SSLv3. This article will explain the attack in detail:

The POODLE attack on SSL Version 3, that sometimes allows an attacker to decrypt a single byte of an SSLv3 protected conversation. Repeating the attack might allow an attacker to decrypt multiple bytes of a secret (for example Session-Cookie, Password…) that is repeatedly send.

 When can the POODLE attack be applied?

The POODLE attack can be applied if:

  • A network connection is secured using SSLv3
  • A block cipher is used for the connection
  • The attacker is an active adversary in the path between the client and the server and he is able to intercept and modify network traffic

To improve the success probability, the attacker should be able to:

  • Force the client to repeatedly send a secret over that network connection
  • Force the client to vary the position of that secret in the transmission

What can an attacker gain using the POODLE attack?

An attacker will be able to decrypt a single byte of the encrypted content with a probability of 1/256. By repeating the attack (the same secret is send again), he will be able to decrypt that single byte with probability 1. By varying the position of a secret content, he will be able to fully recover that secret.

What cannot be done using POODLE?

Using POODLE, it is not possible to:

  • Impersonate an SSL/TLS Server
  • Recover the secret key of an SSL/TLS Server
  • Modify any data that is transmitted

What is the weak point of SSLv3 that is exploited?

When using a block cipher for SSv3, the data to be transmitted is protected against unauthorized modification by adding a MAC to that data first. The result will most likely not have a length that is an integral multiple of the block length of the block cipher. To expand the data to be encrypted to a proper length, a padding is added. The last byte of the padding contains the length of the padding, so that the padding can be properly removed. The data is then encrypted with the block cipher in CBC mode.

Assuming that the last block of the ciphertext (C_i) is entirely filled with padding. The last byte of plaintext in this block will be the length of the padding l. An attacker might now replace that block C_i with a previous block in that session C_j. The server will decrypt that block by computing P_i = D(C_j) \oplus C_{i-1}. If the last byte of P_i is now l, the server will correctly decode the length of the padding and will decode the entire ciphertext correctly. If the last byte differs, the server will very likely fail to decode that ciphertext correctly and close the connection.

This can be used to decode the last bytes of arbitrary ciphertext blocks in a conversation by repeating the process. The attacker might also shift the secret in a conversation to fully decode it.

What countermeasures are possible?

As long as SSLv3 is not used (also, SSLv2 is very weak and should not be used anymore), the attack is not possible. I consider disabling SSLv3 on the server or the client side (best is both sides) to be the best solution. If for any reasons, SSLv3 still needs to be used, you might disable all block cipher suites. However, the only stream cipher available in SSLv3 is RC4, which is also broken. I would currently assume that it takes more repeated conversations in SSLv3 using RC4 to recover a secret than it takes to decrypt a secret using POODLE. However, attacks against SSLv3 using RC4 can be done passively.

Will I notice the attack?

As long as logging is used on the client or the server, the attack will very likely produce a lot of error messages related to MAC verification failures or incorrectly terminated connections.

Which methods are available to shift a secret in a conversation?

That depends on the protocol. If the secret is for example a session cookie, the request URL in an HTTP request might be altered to have a varying length. As a result, this will also shift the position of a session cookie in the transmission.

Which methods are available to make a client to repeat a conversation?

That also depends on the protocol. For POP3/IMAP, this might happen automatically. For HTTP, the attacker might run javascript code or similar things in the victims browser to make it reload a certain URL. You don’t need an exploit for the browser to do this.

SSL/TLS broken again – A weakness in the RC4 stream cipher

A few days ago, a new attack against SSL/TLS has been published by Nadhem AlFardan, Dan Bernstein, Kenny Paterson, Bertram Poettering and Jacob Schuldt. Many attacks on SSL/TLS in the past relied on the protocol design itself, broken implementations leaking side channels, or the X.509 certificate system and improper issuing of certificates. In contrast to these, the new attack is focused on the RC4 stream cipher, that can be used against SSL/TLS.

RC4 usage in SSL/TLS

SSL/TLS doesn’t rely on a single cryptographic primitive. Instead when a new SSL/TLS session is established, both parties negotiate a ciphersuite. A ciphersuite consists of a key exchange algorithm, an encryption method and an integrity protection method. To agree on a common ciphersuite, the SSL/TLS client sends a list of all ciphersuites it supports, and the server choses one of the methods from the list, usually the first one which is also supported by the server. The RC4 stream cipher is one of the possible choices for the encryption method, and also wildly supported and used. Compared to many other encryption methods, RC4 is very fast in software, very easy to implement, and also very efficient because it doesn’t require any padding as many encryption methods based on block ciphers do.

What makes RC4 a bad stream cipher

So what would be expect from a (secure) stream cipher? A stream cipher should take a key, and transform this key into a (pseudo-) random sequence of bytes, chosen from a uniform distribution. However, RC4 has also serious weaknesses. For example, RC4 is also used in the famous WEP protocol, to protect WiFi networks. Here, many similar RC4 keys are used that differ only in the first 3 bytes. These 3 bytes of the key are used as an initialization vector for the cipher, and are transmitted in clear with the encrypted packet. The remaining bytes of the key are shared among all packets, but should only be known to the operator of the network. What has been shown for WEP is, that an attacker, who knows the first 3 bytes of the key, and also has access to some bytes of the key stream can predict the next bytes of the key. The probability for predicting a single byte correct is only slightly above a random guess, but repeating the procedure for many packets (like 10.000) will reveal the secret key that protects the network with almost 100% probability. In a nutshell, if you know a part of an RC4 key, and some bytes of the keystream, then you can predict parts of the remaining key better than just guessing.

How can this be applied to SSL/TLS

But for SSL/TLS, the situation is entirely different. Here, a new key is chosen almost randomly for every new connection and no parts of the key are shown to an attacker. As a result, the methods used to attack RC4 in WEP cannot be applied for SSL/TLS connections. But there are more problems in RC4:  Even if a key for RC4 is randomly chosen, the keystream bytes of RC4 have some biases. For example the second by of output will be 0 with a probability of more than 1/256. What recently has been discovered is, that much more of such biases exist. If a plaintext is transmitted over SSL/TLS, one gets a small hint about the plaintext. If the same plaintext is transmitted over and over again using TLS with RC4 encryption, one can recover the first bytes of the plaintext using these biases in the keystream generated by RC4. No assumptions about other plaintext or keystream bytes must be made, and no knowledge of parts of the key is required. Also this works independant of the implementation used, because it doesn’t require any timings or similar side channels from the implementation.

Consequences of the attack

The number of sessions required depends on how much is known about the plaintext, and what should be recovered. A full plaintext can be recovered using 2^{30} sessions. If only a single byte needs to be recovered, about 2^{24} sessions might be sufficient, depending on the position of the byte in the plaintext. If one only wants to distinguish two plaintexts only, then less than 2^{24} sessions might be enough.

Countermeasures

One may ask now how to counter the attack. One of the best solutions would be to just simply disable RC4 support on a client or on a server. As long as a client and a server still share another common ciphersuite, they will still operate properly. Alternatively, both the server and the client can be patched to send empty application layer records, until the first 256 or 512 bytes of output of RC4 have been used. Currently, the attack works best with the first bytes of output of RC4, but less well with the following bytes.

Final remarks

I have also previously been active in research on RC4 and WEP attacks.

Secure Function Evaluation – There is an issue with OTR and plausible denability

OTR is a crypto overlay protocol for instant messaging. Instead of encrypting the connection to an instant messaging service like Gtalk, MSN, Skype or ICQ, OTR encrypts messages send over an arbitrary instant messaging service end-to-end. The message leaves your messaging client encrypted, and is later decrypted by the receivers client. Only the communicating clients are in possession of the keys necessary to decrypt the message, and the instant messaging service cannot read the message in clear.

Plausible deniability

Between other very nice properties, the OTR protocol also offers Plausible Deniability as well as Authenticity. This means, that when Alice and Bob are chatting, Alice and Bob can be sure that the messages they receive have really been send by their chat partners, and have not been altered. On the other hand, both Alice and Bob cannot prove to a third party, that any of their chat partner send a message with a specific content.

There is a trivial attack on these kinds of protocols. Assume that Alice chats with Bob, and Bob always asks Alice, to help him rob a bank. Now Alice would like to prove to a judge, that Bob really asks her to rob a Bank. A trivial way of doing this is handing over all keys of Alice to the Judge, so that the Judge can impersonate Alice and say Hi to Bob. Because Bob thinks, he is talking to Alice, he asks her again to rob a bank.

However, Alice might not be willing to hand over her keys to a Judge. Recently, greg found out, that there is a way how Alice can prove to a Judge, that Bob told her to rob a bank, without handing over her private keys. His approach uses Secure Function Evaluation: The concept of secure function evaluation is known for some time now: Assume that you have a function or an arbitrary computer program, that processes two inputs a and b, and generates an output c. Then two parties can jointly compute that function, each providing one of the inputs. The other party doesn’t learn anything about the inputs, and both parties get the output c.

Breaking plausible deniability

Effectively, Alice and the Judge can now jointly compute Alice sides of the protocol. Alice provides as input her private key, and the Judge provides all other inputs, including the messages send by Bob. The output of the jointly computed function can be either the short term communication keys, which Alice and Bob are using in the conversation, or the decrypted protocol messages send by Bob. In fact, this very generic approach can still be optimized exploiting some properties that are specific to the OTR protocol and the DH key exchange used in OTR.

Countermeasures

I assume that it will be very hard to counter this type of attack, because secure function evaluation is a very generic method, that is not bound to any specific properties of OTR.

However, please keep in mind, that this attack is only possible while Bob is still chatting with Alice. As soon as the communication is over, Alice cannot decide to go evil afterwards. Also, while Alice is able to prove the authenticity of the messages send by Bob to the Judge, the Judge cannot prove the authenticity of these messages to another party like a jury.

Ron was wrong, Whit is right – Weak keys in the internet

Today, Maxime Augier gave a great talk about the state of security of the internet PKI infrastructure. The corresponding paper written by Lenstra, Hughes, Augier, Bos, Kleinjung, and Wachter was uploaded to eprint.iacr.org archive a few weeks ago. In a nutshell, they found out that some RSA keys, that is often used in the SSL/TLS protocol to secure internet traffic, are generated by bad pseudo random number generators and can be easily recovered, thous providing no security at all.

The RSA cryptosystem

RSA is one of the oldest and most famous asymmetric encrytion schmes. The key generation for RSA can be summarized as follows:

For a given bitlength l (for example l = 1024 or l = 2048 bits), choose randomly two prime numbers p and q of of bitlength l/2. Choose a number 1 < e < (p-1)*(q-1), that has no divisor in common with (p-1)*(q-1). Many people choose e = 2^{16+1} here for performance reasons, but other choices are valid as well. Now, the number n = p*q and e form the public key, while d = e^{-1} \bmod (p-1)*(q-1) is the private key. Sometimes, the numbers p and q are stored with the private key, because they can be used to accelerated decryption.

To encrypt a message m, one just computes c = m^e \bmod n, and to decrypt a message, one computes m = c^d \bmod n. However, we don’t need that for the rest of this text can safely ignore that.

How random do these numbers need to be?

When generating cartographic keys, we need to distinguish between just random numbers and cryptographically secure random numbers. Many computers cannot generate real random numbers, so they generate random numbers in software. For many applications like computer games and for example simmulations of experiments, we only need number that seem to be random. Functions like “rand()” from the standard c library provide such numbers and the generation of these numbers is often initialized from the current system time only.

For cryptographic applications, we need cryptographically secure random numbers. These are numbers that a generated in a way, that there is no efficient algorithm, that distinguish them from real random numbers. Generating such random numbers on a computer can be very hard. In fact, there have been a lot of breaches of devices and programs, that used a bad random number generator for cryptographic applications.

What has been found out?

From my point of view, the paper contains two noteably results:

Many keys are shared by several certificates

6 185 228 X.509 certificates have been collected by the researchers. About 4.3% of them contained an RSA public key, that was also used in another certificate. There could be several reasons for this:

  • After a certificate has expired, another certificate is issued, that contains the same public key. From my point of view, there is nothing wrong with doing that.
  • A company changes their name or is taken over by another company. To reflect that change, a new certificate is issued, that contains another company name, but still uses the same key. I don’t see any problems here either.
  • A product comes with a pre-installed key, and the consumer has to request an certificate for that key. The same key is shipped to several customers. From my point of view, this is really a bad idea
  • Or there might be really a bad random number generator in some key generation routines, that two entities that are not related come up with the same RSA public (and private) key. This is a security nightmare.

Some keys share a common divisor

This is definitely not supposed to happen. If two RSA keys are generated, that share a common divisor by the same or by different key generation routines, the private key for both public keys can be easily determined, and the key generation routine is deeply flawed.

What are the consequences?

For those, who use an RSA public key, that shares a modulus with another different RSA public key, their key provides no protection at all. All implementations, that generated these keys definitely need to be updated and the certificates using the weak keys need to be revoked.

Which devices and vendors are affected?

Because disclosing the list of affected devices and vendors would compromise the security of these systems immediately, and allow everyone to recover their secret RSA keys, this has not been disclosed.