Breaking https:// with Bar Mitzvah


Shamir (The S of RSA) once predicted that the use of Stream Ciphers, like RC4, would inevitably decline over time. Stream Ciphers, while less secure than block ciphers, are faster and simpler to implement than block ciphers. However, with the increasing processing power of computers and the increasing understanding and adoption of Block Ciphers, Stream Ciphers are fast on the decline. Additionally, the weaknesses of Stream Ciphers like RC4 have also left administrators rushing to replace it with Block Ciphers.

1. Implications of Bar Mitzvah

Recently a new discovered attack on an RC4 implementation of TLS, dubbed Bar Mitzvah, may be the final nail in the coffin for RC4 and also for TLS versions 1.0 and 1.1. Whilst the RC4 weaknesses exploited in this attack were first published two years ago, a practical attack wasn’t feasible until a security researcher, Itsik Mantin from Imperva, discovered Bar Mitzvah.

2. RC4 basics

The RC4 algorithm is a Stream cipher that encrypts each plaintext value with a pseudorandom string of bits, known as the keystream. To generate the keystream, a secret key is combined with an initial array of values to form a permuted state, which then goes through more permutation before it is XOR’ed with the plaintext to create the ciphertext. To increase the randomness of the first permuted state, the combination of the key and initial value is done one character at a time and the result is used in the combination of the next value and so on. As the length of the initial array is fixed (e.g. at 256 bytes) and the key length is variable (e.g. may only be 128 bytes), the key is repeated to make up the bytes of the array.

The RC4 algorithm is here (from Wikipedia)

3. RC4 weaknesses

The RC4 algorithm has a few known weaknesses. Due to the way RC4 is initialised, there are single byte biases found in first few bytes of the keystream where the probability of a certain value occurring is statistically higher than average. Another problem is the invariance weakness, which is a key pattern that appears when using weak RC4 keys. This makes its possible to detect specific patterns in the cipher when weak keys are used (e.g. the Least Significant Byte of weak 16 byte keys have statistical biases e.g. even number/multiple of four have a higher probability of occurring etc.)

4. RC4 attacks

RC4 weaknesses have been used to break encryption before. WEP (Wired Equivalent Privacy) used small-sized fixed length (40 bit) keys that were shared across internal networks and never changed. Additionally it also concatenated a small-sized (24 bit) Initialisation Vector (IV) before the key. This made WEP a prime candidate for brute force attacks and a reason why the new Wireless standards enforce the use of AES block ciphers.

5. Bar Mitzvah

The recent Bar Mitzvah attack exploits the fact that in TLS, the first encrypted bytes include predictable information related to the SSL handshake. Therefore, you can use plaintext to compare against the keystream pattern of a known weak key to check if any ciphertext pattern emerges. This requires many encrypted sessions to complete, which may be possible if users have Javascript malware running on their browser, sending multiple requests to the server.

For more information

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s