How safe are Libsodium Crypto Boxes?

Question

I am currently working on a huge PHP project and we are seriously considering to use the Libsodium PHP library in it.

My question is related to the "sodium crypto box" functionality. We would use this functionality to implement public key authenticated encryption. We would generate keypairs using the "sodium crypto box keypair" function, nonces using the "sodium crypto box noncebytes" function, and seal/open the crypto boxes through the "sodium crypto box" and "sodium crypto box open" functions.

My question is basically "how safe is this"?

Public keys will be public, so our concern is that someone might be able to generate a correctly sealed box by "cracking" somehow the secret key of the sender, or to open a sealed box by cracking the SK of the receiver. These keys are 64-digit hexadecimal strings. Is my assumption correct that this means that there are 16^64?

If yes, this would mean that brute forcing all possible combinations at a rate of 1 million tries per second would take 3.6717430630808 * 10^63 years? Or are there more "efficient" attacks?

On the official Libsodium website I found the following algorithm details with respect to the functions we want to use:

Key exchange: X25519
Encryption: XSalsa20 stream cipher
Authentication: Poly1305 MAC

Can someone try to explain me what this means ? Is following interpretation correct:

• X25519: This is the keypair generation algorithm?
• XSalsa20: This is the encryption algorithm?
• Poly1305: This is the nonce generation algorithm?

Answer 1

You can think of crypto_box_curve25519xsalsa20poly1305 as some composition of X25519, a key agreement scheme; XSalsa20, a symmetric-key stream cipher; and Poly1305, a one-time polynomial evaluation message authentication code. But that's not the best way to think about it when you're engineering something out of it—partly because there are many ways you could compose those, but mainly because it doesn't help you to figure out how it fits into your application.

Instead, you should think of it as a contract, with obligations on your part and security services on the part of crypto_box_curve25519xsalsa20poly1305:

1. Your obligations to crypto_box_curve25519xsalsa20poly1305.

   (a) You must generate a secret key uniformly at random.

   (b) You must choose a distinct nonce for every public key and message you use that secret key with. You may generate them uniformly at random if you like.

2. Security provided by crypto_box_curve25519xsalsa20poly1305, even in the face of an adversary who can intercept every box on the wire and persuade the legitimate users to create boxes for arbitrary messages of their choice adaptively.

   (a) Anyone who does not know one of the two secrets keys for a sender and receiver cannot open boxes whose contents did not already know.

   (b) Anyone who does not know one of the two secret keys for a sender and receiver cannot forge a box not created by the sender or receiver.

crypto_box_curve25519xsalsa20poly1305 does not provide third-party verifiability, also known in some circles as nonrepudiation: if Alice sends a box to Bob, Bob can't cryptographically persuade Charlie that Alice sent him that message without also demonstrating to Charlie the ability to forge Alice$\rightarrow$Bob messages.

This is spelled out in slightly more academic detail in the NaCl crypto_box documentation under ‘Security model’.

Attack costs. crypto_box_curve25519xsalsa20poly1305 is designed to target a ‘128-bit security level’, which means that the area*time cost—area on a silicon die times amount of time you spend powering it—of the best known attacks is around that of $2^{128}$ bit operations, which is more than we can imagine anyone ever carrying out.

The secret keys of crypto_box_curve25519xsalsa20poly1305 are indeed 256 bits long, but there is enough mathematical structure in X25519 to admit an attack cheaper than simply enumerating and trying all possible secret keys—so much cheaper that the best you can hope to get for an elliptic curve over a field of 256 bits is a 128-bit security level. You can find highly technical references about these attacks at SafeCurves under ‘ECDLP security’.

The secret keys of crypto_secretbox_xsalsa20poly1305, an operation out of which crypto_box_curve25519xsalsa20poly1305 is built, are also 256 bits long, but the nature of the kind of object that a secretbox is allows multi-target attacks, where the best known area*time cost of breaking at least one of a set of $n$ target $k$-bit keys with nonnegligible probability is significantly less than $2^k$. Using a 256-bit key for crypto_secretbox guarantees that even for an unimaginably large set of $2^{128}$ targets, the best known area*time cost of breaking at least one of those targets with nonnegligible probability still exceeds that of $2^{128}$ bit operations.

Answer 2

Some of your assumption are closer, but not correctly at all. I think I can explain what is the X25519, XSalsa20 and the Poly1005.

The X25519 is the DH using the Curve25519, it has 128 bits of security, it allows to create some “shared-secret”, between both users involved.

The XSalsa20 is the symmetric encryption algorithm, that is uses the secret-key, that was “exchanged” in the X25519, and the nonce that you generate.

The Poly1305 is the MAC, it will guaranty that the message was not changed. To compare, if you use the OpenSSL before, with their AES-CBC, you probably use the HMAC, for the same reason. It’s not involved with the generation of the nonce.

---

Have something that is important to know. The Sealed Boxes(sodium_crypto_box_seal) and the Secret Boxes (sodium_crypto_box) are different. The “Sealed Boxes” uses a “temporary key” and the public key of the receiver, so the sender creates a random key for each message. The “Secret Boxes” uses the private key (and public key) of the sender and the public key of the recipient, so it allows to check who send it.

---

The assumption of 16^64 is correctly, since the key length is 256 bits. Until now, the brute force still the best attack method. But, as describe by @Squeamish Ossifrage, you need to generate a secure random key, in your post you mention about sodium_crypto_box_keypair, it is secure. The nonce need to be random and unique, you can use the random_bytes(24) for this propose, the length of the nonce is 24 bytes.