libsodium: Public-key authenticated encryption or how I decrypted a message without a private key

This article is an example of how a misunderstanding of the work of cryptographic primitives and excessive self-confidence can lead to critical errors in the implementation of cryptographic protection. I hope my mistake will be a useful example for someone.

It all started with the fact that in one small project I needed to use encryption. Clients must send messages to the Server that are protected from interception. Since client authentication was not required in principle, and the data went only one way (from Clients to the Server), and in addition, I did not want to bother with storing common encryption keys, the idea came up with using asymmetric cryptography. The idea looks simple: Clients are given the public key of the Server, with which they encrypt the message sent to the Server. The server (and only he), in turn, can decrypt the received message using the private key known to him.

Manually implementing cryptographic primitives is ungrateful and fraught with errors, so it was decided to use some open source library to implement the above idea. Since the project already used the ZeroMQ libraries , its CZMQ wrapper , which in turn ensured the security of data transfer based on the libsodium library , the choice fell on her. Indeed, why create dependencies if everything is already in it.


So, a quick reading of the documentation showed that the library contains an implementation of asymmetric encryption on elliptic curves of Public-key authenticated encryption . In addition, it is possible to authenticate the message via MAC . MAC encryption and generation is performed using the function crypto_box_easy, the reverse procedure (verification and decryption) is performed using crypto_box_open_easy.

From the documentation:

Original

Using public-key authenticated encryption, Bob can encrypt a confidential message specifically for Alice, using Alice's public key.
Using Bob's public key, Alice can verify that the encrypted message was actually created by Bob and was not tampered with, before eventually decrypting it.
Alice only needs Bob's public key, the nonce and the ciphertext. Bob should never ever share his secret key, even with Alice.
And in order to send messages to Alice, Bob only needs Alice's public key. Alice should never ever share her secret key either, even with Bob.

Using public key encryption with authentication support, Bob can encrypt a confidential message for Alice using her public key.

Using Bob’s public key, Alice can verify even before decryption that the encrypted message was actually created by Bob and not faked.

Alice needs only Bob's public key, nonce, and an encrypted message. Bob must keep his private key secret even from Alice.

To send messages to Alice, Bob only needs Alice’s public key. Alice, in turn, must keep her private key secret even from Bob.

Everything seems to be simple and clear. The Client encrypts the message with the Server’s public key and signs the message with its private key. The server, having received the message, checks it using the Client’s public key and decrypts it with its private key. Apart from the Server, no one can decrypt the message, since it was encrypted with its public key (at least this is the main principle of asymmetric cryptography). However, the devil is in the details.

To test the concept, I copied the example from the official site, but accidentally made a mistake and got a strange result.


In the test for Alice and Bob, at first a pair of keys ( crypto_box_keypair) is randomly generated , then, again, nonce ( randombytes_buf) is randomly filled . After that, Alice encrypts her message for Bob using his public key and forms a MAC using her private key.

// message alice -> bob
if (crypto_box_easy(ciphertext, (const unsigned char*)MESSAGE, MESSAGE_LEN, nonce, bob_publickey, alice_secretkey) != 0)
{
	return false;
}

However, in the decryption procedure, I made a mistake and passed the wrong parameters. Instead of decrypting the message for Bob with his private key, I tried to decrypt the message with Bob's public key and Alice's private key ( Copy-paste so that it ).

// Код с "ошибкой"
if (crypto_box_open_easy(decrypted, ciphertext, CIPHERTEXT_LEN, nonce, bob_publickey, alice_secretkey) != 0)
{
	return false;
}

Imagine my surprise when the message was decrypted! It was very strange and brought me into a state of cognitive dissonance. Before my eyes was found 0-day vulnerability and recognition of the world community . I couldn’t understand how to decrypt the message for Bob without using his private key. And besides, the MAC check was successfully performed without using Alice’s public key!

The first thing I thought of doing was decrypting as in the original example, while everything also went smoothly - the message was decrypted and verified. Thus, to decrypt (and check!) The message could be any pair of keys - Bob's public key and Alice's private key, or vice versa - Bob's private key and Alice's public key.

My second thought was that I was using an old version of the library. Updated to the latest version, but the test behavior has not changed.

Frankly, I had little time and desire to delve into the libsodium sources. The answer was found on Stackoverflow. It turns out that libsodium doesn’t understand “Public-key authenticated encryption” somewhat differently than it seemed to me.

After a detailed review, the encryption algorithm turned out to be like this:

1. Using the ECDH algorithm , a common key is generated for a symmetric cipher.
2. The message is encrypted using the XSalsa20 symmetric cipher using the shared key obtained in the first step.
3. A MAC simulation insert ( Poly1305 ) is generated using the same shared key.

The following conclusions and properties of this algorithm follow from this:

• The same message generated by Bob or Alice (each generates a message with his private key and the public key of the interlocutor) generates the same encrypted message.
• From the previous conclusion it follows that it is impossible to say exactly who wrote the message to whom - Bob Alice or Alice Bob.
• If Alice’s private key is compromised, this will decrypt all previously sent messages to Bob (and this is one of the advantages of asymmetric cryptography).
• If Alice’s private key is compromised, the attacker will be able to fake messages from Bob for Alice (without even knowing Bob’s private key).

I understand that these properties of the algorithm are normal and the fact is that I tried to apply the wrong algorithm. However, I believe that the documentation on the official website misleads users about the features of the work and situations suitable for its use.

Since my goal was to use an algorithm that would not allow to decrypt the message for the Server without knowing its private key, this behavior of this cryptographic primitive did not suit me and I refused to use it.

I just can’t get rid of the thought: what if someone used this method to implement truly critical systems, hoping for the reliability of a proven library, because I realized my mistake only because I made another and accidentally stumbled upon the “strange” behavior of the function .

I hope I was useful to someone. Good luck to all.