The story of Android, cryptography and a crippled 3DES

Asymmetric and symmetric encryption, different algorithms (AES/DES), block/stream ciphers, operation modes  - all of these terms are difficult enough on their own, put aside their specific implementation in Your Programming Environment of Choice. You usually need strong math skills to get through all the tiny details that matter in cryptography. To make things worse, cryptanalysis attacks are constantly improving, so you also need to stay current.

Thankfully, you don't need all that much to simply use it. After all, you're not inventing a new home-brew encryption algorithm (if you do - stop immediately!), so all you need to do is RTFM.

But that enough is difficult, because the web is filled with code examples that are simply wrong. It's always a good idea to do some code review for a cryptography related parts of your project. As an example, we'll look into Android Remote Notifier project - it had a few interesting vulnerabilities which significantly weakened its cipher strength. Author took my comments into consideration and fixed the issues, so consider this a "responsible disclosure" ;).

Short introduction

Android remote notifier is a application for Android phones that "sends notifications to a desktop computer when certain events happen on an Android device, such as the phone ringing, an SMS being received, or the battery running low. The notifications can be sent over Wifi, Bluetooth, or (in the future) USB.". There is an app in the phone that broadcasts notification, and a receiver on the desktop which listens to those and reacts e.g. displays a message box with SMS text. It's a new project (beta-quality), but it is already gaining attention in Android community.

The notifications include confidential information and may be transmitted over insecure channel (e.g.  broadcasted to 255.255.255.255 over current WiFi connection). This was not fun - after all, a simple network sniffer could reveal all the SMSes of your colleague sitting nearby.

We need encryption!

Because of this vulnerability, a few days ago the author implemented the symmetric encryption of the messages. The chosen cipher was Triple DES (DES-EBE in Java community), a 112 bit strong block cipher, working in CBC mode.

When configuring the app, phone user enters a short password - key which will be used to encrypt the messages. The same password has to be configured in the desktop app so that it may decrypt the notifications. Without knowing the password the sniffing attacker cannot intercept and read the notification.

In theory, we're good. A key is never transferred and becomes a shared secret, and a strong cipher has been selected. Any brute force attacks against Triple DES will currently take enormous amounts of time. But the devil is in the detail. Let's look at the (now obsolete) implementation of the encryption/decryption scheme in Remote Notifier:

The padding issue

import java.io.UnsupportedEncodingException;
import java.security.GeneralSecurityException;
import javax.crypto.Cipher;
import javax.crypto.spec.DESedeKeySpec;
import javax.crypto.spec.IvParameterSpec;
import javax.crypto.spec.SecretKeySpec;

/**
 * @author rdamazio
 * @see http://code.google.com/p/android-notifier/
 */
public class Encryption {

  public static int MAX_KEY_LENGTH = DESedeKeySpec.DES_EDE_KEY_LEN;
  private static String ENCRYPTION_KEY_TYPE = "DESede";
  private static String ENCRYPTION_ALGORITHM = "DESede/CBC/PKCS5Padding";
  private final SecretKeySpec keySpec;

  public Encryption(String passphrase) {
    byte[] key;
    try {
      // get bytes representation of the password
      key = passphrase.getBytes("UTF8");
    } catch (UnsupportedEncodingException e) {
      throw new IllegalArgumentException(e);
    }

    key = padKeyToLength(key, MAX_KEY_LENGTH);
    keySpec = new SecretKeySpec(key, ENCRYPTION_KEY_TYPE);
  }

  // !!! - see post below
  private byte[] padKeyToLength(byte[] key, int len) {
    byte[] newKey = new byte[len];
    System.arraycopy(key, 0, newKey, 0, Math.min(key.length, len));
    return newKey;
  }

  // standard stuff
  public byte[] encrypt(byte[] unencrypted) throws GeneralSecurityException {
    return doCipher(unencrypted, Cipher.ENCRYPT_MODE);
  }

  public byte[] decrypt(byte[] encrypted) throws GeneralSecurityException {
    return doCipher(encrypted, Cipher.DECRYPT_MODE);
  }

  private byte[] doCipher(byte[] original, int mode) throws GeneralSecurityException {
    Cipher cipher = Cipher.getInstance(ENCRYPTION_ALGORITHM);
    // IV = 0 is yet another issue, we'll ignore it here
    IvParameterSpec iv = new IvParameterSpec(new byte[] { 0, 0, 0, 0, 0, 0, 0, 0 });
    cipher.init(mode, keySpec, iv);
    return cipher.doFinal(original);
  }
}

Encryption class is initialized with a byte array - a password entered by the user (most likely alphanumeric characters - think "mybaby69"). Triple DES requires a 168 bit key. It's 192 bits in Java (we'll get to that later), so we need to somehow generate those 192 bits (24 bytes) based on user password, which is likely shorter.

That's the purpose of padKeyToLength() function. It initializes a 24 bytes array (newKey) filled with NUL bytes and inserts the given password (key) at the beginning. In our example:

key        m  y  b  a  b  y  6  9
key hex    6d 79 62 61 62 79 36 39
newKey     m  y  b  a  b  y  6  9  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
newKeyHex  6d 79 62 61 62 79 36 39 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

No exception will be thrown, as the key is OK (192 bit long), encryption and decryption will succeed. But if you know the inner workings of Triple DES, you should be scared.

We all love math, don't we?

Triple DES (DES-EDE) uses DES algorithm 3 times (first Encrypts, than Decrypts, than Encrypts, hence the name), each time with a different 56 bits key (k1..k3). From Wikipedia:

ciphertext = E_K3(D_K2(E_K1(plaintext)))

But where do the K1,2,3 come from ? Well, in our case newKey = K1 || K2 || K3. First 8 bytes will be K1, bytes 8-16 will become K2, and K3 is the last 8 bytes.

key1  6d 79 62 61 62 79 36 39
key2  00 00 00 00 00 00 00 00
key3  00 00 00 00 00 00 00 00

For 3DES to remain strong, keys have to be different! Why? Let's do the computation:

DES is symmetric, so E_K(D_K(a)) = a.  Also, in our example K2 = K3

Let E_K1(plaintext) = x (simple DES with K1)

Let D_K2(x) = y 

E_K3(y) = E_K2(y) = E_K2(D_K2(x)) = x 

ciphertext = x

The key 2 and key 3 cancelled each other out, effectively reducing the ever-so-strong 3DES cipher into DES (which is still pretty strong for script kiddies, but breakable in reasonable time if you have $$$). If you don't believe me, I can prove it.

Lesson to remember: never pad your keys! If you have to deal with small password you need to derive your key from, calculate a hash and use it instead (but keep in mind - the weakest point in this scheme is the password, attacker could simply bruteforce the password and regenerate the key for each combination).

If you're interested in padding issues and how they can weaken the security, check out Padding Oracle - it's great and easy to read.

Parity checks are lame

Another issue with this code is related strictly to Java's implementation: 3DES requires 168 bits for the key. Java wants you to enter 8 bytes = 192 bits. As it turns out, each byte is composed of 7 bits for the key, and 1 bit of parity (LSB). While it makes no sense to me (who would ever need parity checking at this layer?), it's just a way it is. Does it change anything in our example? Of course :)

Once we literally copy a user supplied, 8-bits-per byte password into the Java's newKey, the last bit of every byte is simply ignored (parity that is never checked in the code).

As a result, messages encrypted with "Rugged" are exactly the same as the ones encrypted with "Ruffed" as a key (ASCII codes for "f" and "g" differ only in last bit) - and that also reduces the cipher strength.

How to solve this? Expand the key by using all 8 bits and adding parity along the way - or make it so that last bits are not that important for you - by hashing the password.

Final notes

Cryptography is hard to do right, but once you do it, it's worth it. If you're not familiar with the encryption scheme used - read and learn. A lot.

As usual - go to github to check all the code listed here, I also made jUnit tests proving that the described vulnerabilities are real. Current version of Android Remote Notifier changed the algorithm to AES and uses MD5 hashes to avoid key padding/parity issues, but I extracted the vulnerable version to github, so you could experiment yourselves.