# A modified secure version of the Telegram protocol

## 前置知识

### 无限混淆拓展

IGE 的定义为:
$c_i = f_K(m_i \oplus c_{i-1}) \oplus m_{i-1}$

IGE 模式图示

## 摘要

Abstract — The advent of mobile phones and the spread of the internet have caused a substantial increase in the utilization of these technologies for personal communication. A wide range of mobile applications exist, most of which use their own proprietary protocol. Reports of snooping attacks have prompted the parent organizations and users to guarantee that the encrypted data sent over a public network is decrypted only by the intended recipient. Smart phone operating systems provide GPS data to these applications so that users can tag photos with this information. As these applications mostly run a daemon or service in the background to automatically receive messages, an unattended switched on location service coupled with a weak protocol leaves the user highly vulnerable of being tracked by eavesdroppers. These applications are known to, by observing their behaviour, upload the user's contact list to the server so as identify those contacts using the same application. These are but just two important data that need to be protected by tough security measures during transit. Any loop hole in security protocols will leave the user vulnerable to attacks, even outside the digital world. Online chat protocols such as the Telegram protocol ensure end-toend security of data. Although the protocol itself has been explained in much detail by the designers, this protocol is disfavored because of its performance drawbacks and its susceptibility to man-in-themiddle attacks. In this paper, we modify the Telegram protocol in an attempt to make it more efficient and secure.

## Ⅰ. 说明

I. INTRODUCTION

Secure chat protocols have seen a huge increase in use in recent years as concerns over data privacy grow. All applications for digital devices now use novel protocols to ensure that their users' data is not compromised during transit, Telegram being one among them. The Telegram protocol has many features to ensure data integrity but being quite new in the domain, it has still has room for improvements in terms of performance and security. In this paper, we propose replacements and modifications to few modules of the protocol to improve the performance and security of the resulting implementation. We also try to specifically show the performance improvement that comes along with parallelizing the main encryption algorithm.

## Ⅱ. 文献综述

Ⅱ. LITERATURE REVIEW

The whole topic of encrypting using OpenCL has been extensively studied and analysed. The performance results of the various algorithms, under various hardware systems and various software platforms too have been extensively studied and analysed. In our paper the main focus has been on analyzing the deficiencies of the Telegram protocol. Hence the topics that we have focussed on are parallelization issues and encryption vulnerabilities. In parallelization issues we have looked at the hardware implementation of parallel hardware architectures and how their processing capabilities and their memory architectures can be harnessed to make algorithms much faster. We have also focussed on replacing the symmetric encryption algorithm by a version that supports parallelization.

Parallel hardware architectures have been a major research area in computer science for a decade now. Much of the initial work was focussed on getting parallel processors to speed up graphics processing since most algorithms used for graphics processing can be readily parallelized. The demand for faster graphics processing fuelled the development of faster and more sophisticated GPUs. The exponential rise in the power of graphics processors has been extensively documented. It was soon noticed that the same architectures that are used for graphics processing can also be used for improving the performance of algorithms of other kinds. The first software platform that allowed for the use of this was OpenGL. This was soon followed by other standards like OpenCL and CUDA.

Similarly the concepts and techniques used for ensuring and privacy security have also seen new developments. Encryption techniques and the vulnerabilities inherent in them are being exploited with a malicious intent with ever increasing frequency. This calls for the development and application of more rigorous and resilient cryptographic techniques and protocols. Critical vulnerabilities like ‘Heartbleed’ have severely affected secure systems in the recent past. Hence there is a major requirement for more efficient cryptosystems.

## Ⅲ. 概念

### 1. 数字证书

1. Digital Certificates

Digital certificates, also called public key certificates are a class of cryptographic techniques used to verify and validate ownership and authenticity of data. For example, to send secure data over to abc.com, you would contact a trusted party called a Certificate Authority and request a digital certificate for the particular website, containing a public key. The user can use this public key to encrypt data before sending it over to the website. Only the authentic source will have the private key to the corresponding public key and hence only they would be able to decrypt the particular message. However the certificate authorities are themselves vulnerable to a multitude of attacks.

### 2. 对称加密

2. Symmetric Key Cryptography

Symmetric key cryptosystems are those that use the same key for both encryption and decryption. They can be used as stream or block ciphers. Stream ciphers are those where encryption happens one byte at a time. Block ciphers are those where a whole block is encrypted at a time. The most widely used symmetric key cryptosystem is the AES [1] (Advanced Encryption Standard) cryptosystem. Telegram uses the AES symmetric key encryption protocol in IGE block chaining mode to encrypt the messages.

### 3. 分组密码模式

3. Block Cipher Modes

These are algorithms that work on block ciphers to provide confidentiality and authenticity. A block cipher specifies how to repeatedly apply a particular operation on a large set of blocks such that the desired characteristics in the cipher text are enhanced. There are different block cipher modes under AES such as ECB, CBC, CFB, OFB and CTR. Each of these modes has different error propagation properties and, hence, is best suited for different scenarios.

### 4. 区块链

4. Blockchain

The block chain is the cornerstone of the Bitcoin protocol and was originally invented for the same. The basic idea espoused in the block-chain concept is that if people have to agree on the ordering of certain events in the digital world then there has to be a monetary incentive attached to it. The mathematical implementation of this idea is considered to be one of the greatest achievements in cryptography and technology in general in the past decade. As it has a monetary value associated with it, it can be just as well used as a currency or a contract. Blockchain technology has been used as the backbone of many crypto currencies over the past five to six years. However the technology can be used to agree on many other things relevant to the digital space. Name-coin was one of the first forks of the original BitCoin protocol. NameCoin used the block-chain idea to attack an old technological challenge in the online world, Domain Names. Traditionally the handling of DNS servers rested at the hands of a centralized internet authority, ICANN. ICANN was suspected to be at least under the partial influence of the US government.

This led to a demand from mainly the anarchist community for a truly decentralized system that can map IP addresses to domain names in which the first and final authority on control rested with the end user. NameCoin protocol was a response to this demand. Each entry in the NameCoin blockchain can be used for storing any identification information of a certain data size. This exact idea has been extended to include domain names and a corresponding public key rather than the IP address. The domain name is associated with each public key and the owner of that NameCoin has the sole authority to edit the value of the pair. Traditionally, this role was fulfilled by certificate authorities.

### 5. 并行处理

5. Parallel Processing

Latest advances in computer hardware like specialized graphics drivers have greatly increased the number of computational units available in each system. Nowadays even mobile systems contain 4 or more cores. Certain mid-range and higher models also feature a GPU. This has made it possible to create algorithms that run on multiple cores simultaneously, thus increasing the speed of execution. This has also led to a lot of research on what kinds of algorithms can be parallelized [2]. A good part of that effort is focused on encryption algorithms. This concept is relevant to our protocol since encryption algorithms are generally computationally intensive. An encryption algorithm that is parallelized will allow a protocol to encrypt large files quickly.

### 6. OpenCL

6. OpenCL

OpenCL is a standard that was developed to provide a common API to developers who want to leverage the computational capabilities of GPUs and multicore CPUs in a platform independent manner. Any GPU or multi-core CPU with a compatible OpenCL library can run OpenCL programs. An OPENCL program is written in a modified version of C which is then compiled to give an executable, specific to the given architecture on which the program will be run. It standardizes memory hierarchies and computational units making it possible for the programmer to care less about many low level details.

OpenCL 是一个开发标准，可以以跨平台、硬件的前提下，为调用 CPU、GPU 提供了通用 API。任何兼容 OpenCL 的 CPU 和 GPU 都可以运行 OpenCL 程序，开发者不需要考虑底层细节。其是修改后的 C 语言，将其编译成可执行程序后即可运行。

## Ⅳ. MTProto 中的问题

### 1. AES IGE 不适用于并行计算

1. Inadaptability of AES IGE to parallel processing

The MTProto protocol by Telegram is claimed to be
one of the highly secure data exchange protocols [3]. It offers end to end encryption between two users and even though the server is involved in the transfer, it cannot decipher the data passing through it. The Telegram MTProto protocol uses end to end encryption using the AES encryption protocol with blocks being chained in the IGE (Infinite Garble Extension) mode. Block chaining in symmetric cryptosystems is an extensive subject that has been studied in detail. The most common mode of encryption, ECB, in which each block is treated independently, is not used normally, since it is very insecure. When pictures are encrypted using this method, the basic outline of the picture is many a times still visible in the final cipher. For example if the image of the Linux mascot, tux, in JPEG format is encrypted using AES ECB the cipher version of the image still contains the rough outline of the penguin. There are many cases when even this lack of randomness might severely ompromise security. Block chaining modes ensure greater randomness, and hence security, by ensuring that each block is encrypted with a different key.

The downside of this is that in many of the block chaining encryption modes (CBC, ABC) each block relies on a previous one for encryption. Thus the algorithm itself cannot be parallelized. However there is another AES mode that allows for parallelization. This is called AES-CTR and it is this mode that we have proposed in our protocol. In the CTR mode, unique counter values are generated for encrypting each block. This allows the data blocks to be encrypted in parallel since the counter value is known to be unique and is not dependent on the result of a previous encryption.

MTProto 号称是高度安全得数据交换协议，其提供了端到端的加密，即使信息通过服务器进行传输，服务器仍然无法解密出数据。Telegram 使用 IGE 分组链接模式的 AES。对于常见的 ECB 模式，各分组独自加密，因此非常不安全。如下面的图片，尽管每部分都被加密了（与原来的颜色不同），但是轮廓仍然可以辨别。

### 2. 中间人攻击

2. Room for Man in the Middle attack

As we have discussed earlier, the MTProto protocol used in Telegram is basically split into two steps. Firstly, the DeffieHellman key exchange mechanism is used to exchange keys. These keys are then used along the AES-IGE to encrypt messages.

However there is still a question of trust involved here. This the exchange of keys using Deffie-Hellman is is because overseen by the Telegram. The centralized server can choose to perform an active man in the middle attack on the connection between two users. In an active man in the middle attack, the attacker maintains two connections with each of the communicating parties and convinces each of them that they are talking to the intended destination while actually reading all the information being sent through it [4]. The protocol is riddled with further problems. Once the keys have been transferred the protocol mandates sending a hash of the key pairs across to the other node. This is compared with the corresponding hash on the receiver’s side. This again leaves the possibility of a birthday attack on the hash wide open.

Telegram 的 MTProto 分为两部分，首先使用 Diffie-Hellman 进行密钥疾患，接着使用 AES-IGE 对消息进行加密。

### 3. 生日攻击

3. The birthday attack

The ‘birthday attack’ is a technique that exploits the mathematics behind the birthday problem in probability. If an algorithm has a fixed number of outputs and an indefinite number of inputs, then the probability that two inputs will have the same output increases exponentially with the number of inputs. The principle can be employed to find such pairs in cryptographic hash functions since they have a fixed number of inputs bits. This takes messages hashing especially that rely on cryptographic vulnerable since this attack allows an authentically signed message to be replaced with a fake one. In a critical message that involves financial transaction this can be very dangerous.

The birthday attack in this case is performed on the hash that is sent across the network to validate the keys required for AES. The hash is converted into a (128x128) block picture which is send across by both parties. A malicious eavesdropper can extract the AES keys from just this information with a birthday attack. The birthday attack on the protocol was calculated to take 2^64 operations for a 50 percent probability [5], something that is considered unacceptably weak in 2015.

### 4. 匿名性丢失

4. Lack of Anonymity

In the Telegram protocol user verification happens in the conventional manner. A SMS is sent to the particular phone and the device is authenticated with the central server. This removes anonymity to a great extent since the server can know which node a message originated from. This too is a serious handicap for any chat system that claims to be more ‘private’ than the others. In the ideal scenario the messages should be strictly anonymous and access to the messages should strictly be based on access to the encrypted messages’ private keys. We have tried to overcome this issue too in our proposal.

## V. 协议草案

### 1. 概述

1. Overview

The modified protocol that we propose has two major differences compared to the original one. We remove the session key exchange with Deffie-Hellman followed by a symmetric encryption technique to include asymmetric key encryption. However we again face the issue of MIM attack since even in this case the public keys have to be exchanged. To solve this we choose to include NameCoin into this protocol to act as a public key repository. In brief, our protocol would pick a session key, encrypt it with the recipients’ public key chosen from the NameCoin block-chain blockchain and send the message over to the server. The recipient then accepts this request depending on whether or not the request is legitimate i.e. after checking if the message is actually encrypted by the person as claimed and chooses to allow or close the session. Note that this part requires both parties to have access to the NameCoin blockchain. Once the session key is exchanged, further communication can happens using the AES CTR where the session key is used to generate a key for the symmetric encryption algorithm.

1. 将 Diffie-Hellman 替换为对称加密技术来包含非对称加密
2. 将 AES-IGE 替换为 AES-CTR

### 2. AES-CTR 的角色

2. Role of AES CTR

One of the deficiencies with the original Telegram protocol is that it relies on an encryption mode that cannot be parallelized. The encryption speed is acceptable when an application encrypts small data like text messages but in cases where bulk data in billions of bytes need to be encrypted, AES-IGE becomes a huge performance handicap. Hence, we propose the use of AES CTR which is readily parallelizable [6]. This makes it easy to implement over a parallel programming framework like OpenCL or CUDA.

#### 2.1 实验分析与结果

2.1 Experimental Analysis and Results

The AES-CTR implementation was tested on the OpenCL platform provided by AMD and the GPU used for the experiment was an AMD Radeon 7470M. A control program was run on the CPU to compare performance. An OpenCL kernel had to be created for AES-CTR [7].

An OpenCL kernel looks very much like a C function but with the "__kernel" (without quotes) qualifier. It accepts parameters for input and output data. The parameters of the kernel were:

• Plain text
• Output buffer
• Round keys (computed earlier on CPU)
• Nonce + counter: Nonce is a unique 8 byte value given to AES and is applied to all blocks. The counter is the next 8 bytes initialized to zero and is incremented when encrypting each block.

The input and output buffers were typecast to a 4 byte word for easy adaptation to AES. A set of 4 words (total of 16 bytes) were assigned to each OpenCL work item. As each work item has a unique global ID (obtained by calling get_global_id), the same value can be used as the counter. Each work item hence works on a 16 byte block on exactly one processing element. Hence, the speed of encryption becomes dependent only on the number of processing elements in the GPU. Despite having a lesser clock frequency than a serial CPU, the GPU provides substantial computational speed up owing to the large number of processing elements.

The performance was measured in terms of processing time taken by CPU and GPU. As the experiment was carried out on a general purpose computer, there were differences between successive readings. An average of ten readings for each data size was thus taken for both CPU and GPU. The readings have been summarized in Fig. 2. Additional speed up can be achieved by overlapping the copying and computational steps, thus improving encryption performance greatly [7]. As many network enabled applications security, it would be best rely on encryption for data to provide the GPU encryption functions to all of them through a standard API. [8] The performance increase is shown in Figure 2 and Figure 3.

Note that for small file sizes the GPU takes more time than the CPU. This is because of the extra time involved in transferring data between main memory and GPU memory. This copy time overshadows the encryption speed up that the GPU gives. As the data size grows, the GPU gives a substantial performance improvement over the CPU as shown in the graph.

AES 的输入长度为 $128$ 位，也即 $16$ 字节。为了方便计算，输入和输出缓冲区类型都是 $4$ 个字（按照 $1$ 个字 $2$ 个字节，$1$ 个双字 $4$ 个字节算，这里似乎应该是 $8$ 个字？）。每次 worker 都有一个唯一的全局 ID，通过get_global_id获得，因此可以使用相同的计数器。一个 worker 只处理一个 $16$ 字节的分组。加密的速度取决于并行的计算模块数目。

10Mb 331 559
20Mb 494 474
30Mb 770 603
40Mb 1037 730
50Mb 1269 849
60Mb 1468 976
70Mb 1757 1118
80Mb 2006 1232
90Mb 2441 1368
100Mb 2680 1488

CPU 和 GPU 的性能比较图

### 3. NameCoin 的角色

3. Role of NameCoin

The main role of NameCoin is to provide a directory of the available public keys along with the names of the owners. The client uses these public keys to initialize sessions with another client [9]. This is radically different from the original. Telegram protocol that relied on the server to provide a session ID. Once the session key is finalized AES CTR is used in further communication.

This effectively solves the problem of the man in the attack since the responsibility for maintaining the authenticity of the NameCoin blockchain rests with the NameCoin protocol. This outsourcing is evidently advantageous since the blockchain is known to be extremely secure against precisely this kind of attack. The only kind of vulnerability that NameCoin is susceptible to, which is remotely similar to a MIM attack is a 51% attack. In this an attacker who controls more than 51% of the total network’s computational power chooses to rewrite the records to cancel certain transactions made on it, or to add a few extra ones. However as the network size grows and decentralization is maintained, it becomes extremely difficult to control more than 50% of the network’s power. Also as the blockchain’s size increases the security of the transactions recorded deep down in the blockchain (transactions that were recorded comparatively earlier) increases.

Even in the case where a 51% attack happens it is extremely easy to spot it immediately. Hence the user can directly encrypt using the public keys stored in the NameCoin blockchain without having to worry about any kind of key exchange. This removes a large part of the trust deficiency since this is the point at which the man in the middle attack normally occurs.

Since NameCoin exists as a third party component of the whole software, it can be extended to service other applications easily. For example, an application that seeks to make voice calls secure can easily use the public key provided in NameCoin to build an encryption protocol. Almost any kind of secure application can be built on top of this system. It is this flexibility that we want to really exploit in this protocol.

NameCoin 的主要作用是提供公钥目录以及所有者名称，客户端使用这些公钥来初始化会话。这和原本 Telegram 协议思路不同。当会话密钥传输完成，即可使用 AES-CTR 进行进一步的通信。

### 4. 细节内容

4. Miscellaneous Details

The only identity that a two way channel should have should be the details in the NameCoin blockchain. Many other chat systems necessitate that each new redundant application across multiple devices be verified and authenticated independently this extra overhead can easily be avoided in the method that we propose. This would make it readily transferable across multiple systems without needing verification by SMS or something similar.

The server being relieved of much of the session handling normally done by chat servers
details can be extremely lightweight. The server source can be released under an open source license thus allowing for more peer review, similar to
IRC chat [10].

The server can provide important features like storage till the other recipient logs in, providing features like group chat. However it cannot read the messages because it is encrypted. For extremely secure communication links the users can run servers on their own computers and use a third party server just to transmit their respective server addresses. They can even have their own static IP addresses listed in NameCoin thus making it a direct link between two systems without the need for a server.

### 5. 挑战

5. Challenges

The biggest challenge that is faced while trying to incorporate the NameCoin feature into such applications is the size of the block-chain. NameCoin blockchain as it is today is 2.15 GB big. Such a quantity of storage is too big for the average mobile device. Also storing the entire NameCoin blockchain on the system is somewhat similar to storing the entire DNS server on a single system, precisely the problem that the DNS system was invented to avoid. However there exist techniques to reduce the data stored at any one particular node [11]. These make the system suitable for individual desktop nodes but still too heavy for mobile devices. However since authentication is something that needs to be done only once, this can be considered a useful tradeoff. And even in the case where a copy of the NameCoin block chain is not available with every single user, the sheer existence of such a facility is a huge step up, especially

## Ⅵ. 结论

VI. CONCLUSION

In this study we have proposed modifications to the Telegram protocol that make it more secure and efficient. We have also tried to show how this general principle can be extended to other secure systems that require key exchange or public key encryption. Since the protocol in its simplest form is best suited for text messages we hope to see it for such applications in the near future. The main strength of the system is in its ability to be extended to a generalized cryptographic system. Also, Telegram supports file transfers up to 1 GB. As most personal computers and smart phones today are equipped with GPUs, utilizing this for encryption will enhance performance and hence, user experience. As mobile devices are just beginning to have graphics processors, there is more room for research in this area. This is where we believe the bulk of the further development of this protocol should be focussed.