Potential vulnerability in Telegram Android

Disclaimer: Described below potential vulnerability at the moment is fixed: December 18, 2014 has been updated to the version on Google Play, January 3, 2015 have been made changes to public code on GitHub.

It so happened that I needed to study the source codes of the encryption, transmission and decryption mechanism of messages in Telegram for mobile platforms iOS and Android. That is, we are talking about client applications, it is their sources ( iOS , Android ) that are in the public domain.

Since I specialize more in iOS, I first started to study the version for this platform. After spending about a day reading the source code and working with the debugger, I realized what was happening and started the Android version. It is easy to guess that the mechanisms and principles of work should be identical due to the compatibility of all platforms with each other. But to my surprise, I found several differences in the message decryption algorithm in the Android version, which created a vulnerability, so to speak. The general essence of the vulnerability is that in the client application there is no comparison of the hash of the decrypted message with the original hash transmitted along with the encrypted message. In fact, there is no verification of the signature of the message. The absence of such verification may allow third parties with access to the server, create random activity from individuals participating in secret chat. However, access to the shared secret key is not required, and it remains invulnerable to third parties.

To understand the point, let's first look at the principle of messaging. It consists of three main stages:

1. Generation of a shared secret key;
2. Outgoing message encryption
3. Decryption of an incoming message.

Note: I here intentionally omitted the stages of client-server interaction (establishing a connection, sending / receiving messages), since they represent exactly the same 3 stages. That is, the same security principle is used to encrypt / decrypt a single message and to transfer data between the client and server.

The principle of generating a shared secret key is based on the Diffie-Hellman protocol .

Encryption:

1. We form an object representing the original message;
2. In the special. field write an array of 1 to 16 random bytes;
3. We serialize the original object into an array of bytes;
4. From the zero position of the array, select 4 bytes and write the data length in the array;
5. We calculate the hash (sha1) of the resulting data array;
6. We calculate the message key (the last 16 bytes of the hash);
7. Based on the shared secret and message keys, we calculate the parameters for AES-256 encryption;
8. We add random data to the original data array until the length of the resulting array is a multiple of 16 (AES requires 128-bit data blocks);
9. The resulting array is encrypted using AES-256;
10. We calculate the hash (sha1) of the shared secret key;
11. We calculate the identifier of the shared secret key (last 8 bytes of the hash);
12. We form the final data array consisting of the identifier of the shared secret key (8 bytes), a message key (16 bytes) and an encrypted data array (the size will turn out).

Decryption:

1. We calculate the hash (sha1) of the shared secret key, which is stored locally;
2. We calculate the identifier of the shared secret key (last 8 bytes of the hash);
3. Read the identifier of the shared secret key from the received data array (first 8 bytes);
4. Compare with the locally calculated identifier. In case of equality, proceed to the next paragraph, otherwise we ignore the message;
5. We read the message key from the received data array (the next 16 bytes);
6. Based on the shared secret and message keys, we calculate the parameters for AES-256 decryption;
7. We read the remaining bytes from the resulting data array and decrypt them using AES-256;
8. Read the message length from the decrypted data array (first 4 bytes);
9. Check the message length: the value must be greater than zero and less than the length of the remaining decrypted data array. If the length is valid, then go to the next point, otherwise we ignore the message;
10. In the decrypted array, we leave only the useful data (delete the first 4 bytes and bytes at the end, if the length of the array exceeds the length of the message);
11. We calculate the hash (sha1) of the decrypted data array;
12. We calculate the message key (the last 16 bytes of the hash);
13. Compare the calculated message key with the key read from the received data array. In case of equality, proceed to the next paragraph, otherwise we ignore the message;
14. Deserialize the decrypted data array into an object representing the received message.

We figured out the theory. It's time to move on to practice.
Consider the message decryption code for both platforms (no differences or errors were found in the code for generating the shared secret key and encrypting the message, so we will omit it). The code corresponds to the latest revision of the master branch. Fundamental checks are numbered in the comments (1, 2, 3).
Telegram iOS: TGUpdateStateRequestBuilder.mm

//———————————————————————Cut———————————————————————
        int64_t keyId = 0;
        [encryptedMessage.bytes getBytes:&keyId range:NSMakeRange(0, 8)];
        NSData *messageKey = [encryptedMessage.bytes subdataWithRange:NSMakeRange(8, 16)];
        int64_t localKeyId = 0;
        NSData *key = nil;
        bool keyFound = false;
        if (cachedKeys != NULL)
        {
            auto it = cachedKeys->find(conversationId);
            if (it != cachedKeys->end())
            {
                keyFound = true;
                localKeyId = it->second.first;
                key = it->second.second;
            }
        }
        if (!keyFound)
        {
            key = [TGDatabaseInstance() encryptionKeyForConversationId:conversationId keyFingerprint:&localKeyId];
            if (cachedKeys != NULL)
                (*cachedKeys)[conversationId] = std::pair(localKeyId, key);
        }
        if (key != nil && keyId == localKeyId) // 1)
        {
            MessageKeyData keyData = [TGConversationSendMessageActor generateMessageKeyData:messageKey incoming:false key:key];
            NSMutableData *messageData = [[encryptedMessage.bytes subdataWithRange:NSMakeRange(8 + 16, encryptedMessage.bytes.length - (8 + 16))] mutableCopy];
            encryptWithAESInplace(messageData, keyData.aesKey, keyData.aesIv, false);
            int32_t messageLength = 0;
            [messageData getBytes:&messageLength range:NSMakeRange(0, 4)];
            if (messageLength < 0 || messageLength > (int32_t)messageData.length - 4) // 2)
                TGLog(@"***** Ignoring message from conversation %lld with invalid message length", encryptedMessage.chat_id);
            else
            {
                NSData *localMessageKeyFull = computeSHA1ForSubdata(messageData, 0, messageLength + 4);
                NSData *localMessageKey = [[NSData alloc] initWithBytes:(((int8_t *)localMessageKeyFull.bytes) + localMessageKeyFull.length - 16) length:16];
                if (![localMessageKey isEqualToData:messageKey]) // 3)
                    TGLog(@"***** Ignoring message from conversation with message key mismatch %lld", encryptedMessage.chat_id);
                else
                {
                    NSInputStream *is = [[NSInputStream alloc] initWithData:messageData];
                    [is open];
                    [is readInt32];
                    int32_t signature = [is readInt32];
                    id decryptedObject = TLMetaClassStore::constructObject(is, signature, nil, nil, nil);
//———————————————————————Cut———————————————————————

Telegram Android: SecretChatHelper.java

//———————————————————————Cut———————————————————————
ByteBufferDesc is = BuffersStorage.getInstance().getFreeBuffer(message.bytes.length);
is.writeRaw(message.bytes);
is.position(0);
long fingerprint = is.readInt64();
byte[] keyToDecrypt = null;
boolean new_key_used = false;
if (chat.key_fingerprint == fingerprint) { // 1)
    keyToDecrypt = chat.auth_key;
} else if (chat.future_key_fingerprint != 0 && chat.future_key_fingerprint == fingerprint) {
    keyToDecrypt = chat.future_auth_key;
    new_key_used = true;
}
if (keyToDecrypt != null) {
    byte[] messageKey = is.readData(16);
    MessageKeyData keyData = Utilities.generateMessageKeyData(keyToDecrypt, messageKey, false);
    Utilities.aesIgeEncryption(is.buffer, keyData.aesKey, keyData.aesIv, false, false, 24, is.limit() - 24);
    int len = is.readInt32();
    TLObject object = TLClassStore.Instance().TLdeserialize(is, is.readInt32());
//———————————————————————Cut———————————————————————

As you can see from the code, the following checks are performed in the iOS version:

1. Compare the identifier (hash) of the shared secret key from the body of the incoming message with the identifier (hash) of the local shared secret key;
2. Compare the transmitted length of the decrypted message with the minimum and maximum allowable length;
3. Compare the key (hash) of the received decrypted message with the key (hash) of the original message that was sent by the sender.

On Android, versions 2 and 3 are missing.

Consider a situation in which the absence of these checks can affect the secret chat:
For a constructive dialogue, we will call Alice and Bob.
And so, the characters:

1. Bob is the number one companion. For messaging uses Telegram Android;
2. Alice - interlocutor number 2. Any Telegram client uses for messaging;
3. An attacker is a developer or other person who has physical access to the Telegram server.

Scenario:

1. Bob initiates a secret chat with Alice to generate a shared secret key according to Diffie-Hellman (requests p and g from the server; performs checks; generates a and ga; passes ga to Alice);
2. Alice receives a secret chat with Bob (requests p and g from the server, checks, generates b, gb; generates a shared secret key based on b, ga and p; passes Bob the identifier (hash) of the shared secret key and gb);
3. Bob confirms a secret chat with Alice (generates a shared secret key based on a, gb and p; compares the identifier (hash) of his key with the identifier (hash) of the key received from Alice);
4. Alice sends an encrypted message to Bob;
5. Bob receives the message and decrypts it successfully;
6. An attacker sees Alice's encrypted message sent to Bob. An attacker cannot decrypt a message because it does not have access to a shared secret key;
7. An attacker extracts the following data from an intercepted encrypted message: identifier (hash) of the shared secret key (first 8 bytes), key (hash) of the decrypted message (next 16 bytes);
8. The attacker generates a new message on behalf of Alice as follows:
   
   • The first 8 bytes are equal to the identifier (hash) of the shared secret key from the intercepted message;
   • Next, an array of random data is written with a length of at least 32 bytes (16 bytes - the key (hash) of the message, 4 bytes - the length of the message, 4 bytes - the class identifier (it will become clear below), 8 bytes - additional data to form a block, correct from the point of view of AES-256 length).
   
   
9. The attacker sends a new message to Bob on behalf of Alice;
10. Bob receives a new message from Alice sent by an attacker and tries to decrypt it:
    
    • Reads the identifier (hash) of the shared secret key (first 8 bytes) and successfully compares it with the identifier calculated locally;
    • Reads the key (hash) of the decrypted message (next 16 bytes);
    • Calculates AES-256 symmetric encryption parameters using the shared secret key and the received key (hash) of the message. The received parameters are random sets of bytes and do not correspond to the original encryption parameters;
    • The received parameters are used to decrypt the message (remaining bytes). The message received at the output is a random set of bytes and does not correspond to the original message. Since at this stage there is no verification of the length and key (hash) of the resulting message, the data is transmitted for further processing, despite their deliberate falsity;
    • The first 4 bytes are cut out of the resulting message (in the original message, this data represents the length of the original message). Further in the code these 4 bytes are not used anywhere;
    • The rest of the message is passed to the deserializer: TLObject object = TLClassStore.Instance (). TLdeserialize (is, is.readInt32 ());
    • The first 4 bytes of the remaining message are interpreted as the class identifier (the second parameter in the TLdeserialize method). The TLClassStore class contains a dictionary in which the values ​​are classes of various types of messages, and the keys are class identifiers (constants 4 bytes long). The full contents of the dictionary are presented in the TLClassStore.java class .
      TLClassStore tries to find the class corresponding to the transmitted 4 random bytes. If a match is found, then a new object of the corresponding class is returned, otherwise null is returned and the incoming message is completely ignored (that is, Bob will not notice this). If successful, the rest of the message is used to initialize the parameters of the created object. Further, the received object is used for its intended purpose. For Bob, this will look like random activity from Alice (for example, a new text message with random content).
    
    

The probability of successful creation of an object is approximately equal to 382/2 ^ 32 ≃ 8.9 * 10 ^ -8, where
382 is the number of classes contained in the dictionary;
32 is the length of the class identifier in bits.
The probability, of course, is not high, but since unsuccessful cases pass unnoticed by the user, the attacker can send messages continuously, limited only by the width of the channel connecting the client to the server. In this case, the attack can be quite feasible. If we assume that the minimum traffic per message can be about 100 bytes, then about 1 GB of traffic will be required to guarantee the creation of an object.

Let's try to estimate the likelihood of a successful attack in the presence of at least one of the missed checks:
If there is a check for the message length: (2 ^
10/2 ^ 32) * (382/2 ^ 32) ≃ 2.1 * 10 ^ -18, where 2 ^ 10 = 1024 is the maximum valid message length, approximately the same amount of memory is a regular message;
32 = 4 bytes, so much memory is the length of the message.
If there is a check of the key (hash) of the message: (1/2 ^ 128) * (382/2 ^ 32) ≃ 2.6 * 10 ^ -46, where
128 is the length of the key (hash) of the message.

It should be noted that at other levels of protection verification of the signature of the message is present. For example, when establishing a client-server connection (using the same principle as when exchanging messages): ConnectionsManager.java

//———————————————————————Cut———————————————————————
byte[] realMessageKeyFull = Utilities.computeSHA1(data.buffer, 24, Math.min(messageLength + 32 + 24, data.limit()));
if (realMessageKeyFull == null) {
    return;
}
if (!Utilities.arraysEquals(messageKey, 0, realMessageKeyFull, realMessageKeyFull.length - 16)) { // 3)
    FileLog.e("tmessages", "***** Error: invalid message key");
    connection.suspendConnection(true);
    connection.connect();
    return;
}
//———————————————————————Cut———————————————————————

Although this looks a little strange, I still don’t think that in the absence of verification of the signature some malicious intent is hidden, since the vulnerability is not critical. On the other hand, there may be other vulnerabilities that, together with this, give a greater profit.

However, at the moment, the developers have made the necessary changes to the Dev branch and updated the assembly on Google Play. I also want to note the fact that for the shortcomings I found, the developers paid a reward of $ 5,000. As the saying goes, "not a trifle and nice."