At the recent HOPE conference, the “secure instant messaging (IM) client”, ScatterChat, was released in a blaze of publicity. It was designed by J. Salvatore Testa II to allow human rights and democracy activists to securely communicate while under surveillance. It uses cryptography to protect confidentiality and authenticity, and integrates Tor to provide anonymity and is bundled with an easy to use user interface. Sadly not everything is as good as it sounds.

When I first started supervising undergraduates at Cambridge, Richard Clayton explained that the real purpose of the security course was to teach students not to invent the following (in increasing order of importance): protocols, hash functions, block ciphers and modes of operation. Academic literature is scattered with the bones of flawed proposals for all of these, despite being designed by very capable and experienced cryptographers. Instead, wherever possible, implementors should use peer-reviewed building blocks, as normally there is already a solution which can do the job, but has withstood more analysis and so is more likely to be secure.

Unfortunately, ScatterChat uses both a custom protocol and mode of operation, neither which are as secure as hoped. While looking at the developer documentation I found a few problems and reported them to the author. As always, there is the question of whether such vulnerabilities should be disclosed. It is likely that these problems would be discovered eventually, so it is better for them to be caught early and users allowed to take precautions, rather than attackers who independently find the weaknesses being able to exploit them with impunity. Also, I hope this will serve as a cautionary tale, reminding software designers that cryptography and protocol design is fraught with difficulties so is better managed through open peer-review.

The most serious of the three vulnerabilities was published today in an advisory (technical version), assigned CVE-2006-4021, from the ScatterChat author, but I also found two lesser ones. The three vulnerabilities are as follows (in increasing order of severity):

Capability probing and spoofing attack

Another protocol with very similar goals to ScatterChat is Off-the-Record Messaging (OTR). One of the reasons that OTR was not used for ScatterChat is that the OTR plugin will automatically respond to a key-exchange request, and so confirm to anyone that OTR is installed. In some situations this may be undesirable (e.g. where encryption is illegal or considered suspicious), so ScatterChat was designed to not respond to requests from unknown users. However, due to a lack of identity binding and key confirmation, this protection can be circumvented in some cases.

A simplified version of the initial stages of the protocol is:

Alice initiates a ScatterChat session:
A → B: Sapub || Eapub || Sig(Sapriv, Eapub)
Bob verifies Alices’ signature and confirms that he is willing to let Alice know that he supports ScatterChat:
B → A: Sbpub || Ebpub || Sig(Sbpriv, Ebpub
where:
Sxpub: X’s public and private signing keys respectively
Expub: X’s public encryption key
Sig(k, d): Signature of data d under key k

Say Eve wishes to collect evidence about Bob’s use of encryption. Note that Alice’s signed message implies Alice’s name, but does not include Bob’s and contains no guarantee of freshness. So Eve can start up a conversation with Alice (who does not want to hide her use of encryption) and collect Sig(Sa_PRIV, Ea_PUB). This can be replayed to Bob who will see an incoming connection from Alice, so trusting her, will respond with his public key, revealing his use of encryption.

Eve’s deception cannot continue past this point, since she does not have Alice’s private encryption key, so cannot send valid messages or decrypt Bob’s, but partial spoofing can still be dangerous in some circumstances. For example, perhaps Eve would like to persuade Bob that Alice has Internet connectivity at a date when she does not, is at a particular IP address, or is in control of a particular instant messaging account.

Perfect forward secrecy (or lack thereof)

When released, ScatterChat advertised resistance to “partial compromise through perfect forward secrecy”. This means that the compromise of any long-term secret will not risk the confidentiality of any previous communication, even if all ciphertext was recorded. This is normally achieved by applying Diffie-Hellman key-exchange to derive an ephemeral key, with a digital signature to protect against man-in-the-middle attacks. Subsequent data is encrypted under the ephemeral key and when the session is complete, the key is discarded and even with access to any secret keys, the session key cannot be recovered.

ScatterChat works differently. After the asymmetric encryption key transfer described above, each side generates a random session key component and encrypts it to the other party’s public key. These components are xor-ed to derive the session key. If both parties’ private encryption keys are compromised, then the transfer of the session key components can by decrypted, and so decrypt all previous conversations that were recorded. This clearly does not meet the requirements of perfect forward secrecy.

In discussions with the protocol designer, it transpired that the problem was a misunderstanding of the term “perfect-forward secrecy”. ScatterChat is believed to be resistant to one party’s encryption key being compromised (because of the xor), but not both. The matter was clarified in an announcement released on Saturday.

Collision attacks

ScatterChat uses a non-standard mode of operation (the author prefers to call it “creative”) for message encryption, based on electronic codebook (ECB). Standard ECB consistently encrypts the same plaintext block to the same ciphertext block so reveals patterns in the plaintext. Other modes of operation, such as cipher-block chaining (CBC) and counter (CTR) modes remove this weakness. ScatterChat takes a different approach of inserting one random byte for every three bytes of plaintext. This introduces a 33% overhead and puts strain on the operating system entropy pool, but it was hoped to resist the weaknesses of ECB. Unfortunately, for significant message lengths, it fails to provide adequate protection.

AES, which is used by ScatterChat, has a 16-byte (128 bit) block size. This means that in every block there will be 4 bytes (32 bits) of random data. From the birthday theorem, after approximately 1.1774 × 2¹⁶ (77 162) blocks there is a 50% probability of two ciphertext blocks being identical if the plaintext blocks are. This allows an attacker to find patterns in messages, in the extreme case leading to plaintext disclosure. This corresponds to 904kB of plaintext, but for the probability to be 1% it is only 109kB and reaches 99% after 2.3MB.

To validate this hypothesis, I wrote a simulation of the ScatterChat encryption mechanism and tried to distinguish two 10MB encrypted files — the plaintext for one was zeros and the other was random numbers. The goal was to tell the difference between the two input files. For comparison, I also repeated the test with CBC encryption. The table below shows the number of repeated blocks in the four encrypted files.

As can be seen, the ScatterChat encryption mode leaks information about the content of the encrypted file as there are no collisions for the random plaintext and 47 for the file filled with zeros (the expected value is 50). In contrast, CBC properly hides the file content. While this is a demonstration of a pathological case, this not an expected weakness in modern deployed security systems. The vulnerability in ScatterChat only affects the IM component, because file transfer uses CTR mode, and IM communications are likely to be quite short. However, there is an API for ScatterChat messaging so it is conceivable some users will be making use of it in a vulnerable way.

Conclusions

ScatterChat suffers from a number of protocol flaws which, while not critical, do introduce a vulnerability within certain threat models. A new version is under development, which will be based around the well reviewed and formally analysed OTR protocol. In the meantime, a similar result can be achieved with GAIM, and official OTR plugin then configuring them to use Tor, albeit without secure file transfer.