Security vulnerability: nacl.sign.detached accepts invalid keys

[paulmillr]

Security vulnerability: nacl.sign.detached accepts invalid keys

[dchest]

Let's try to clearly define the problem.

Signing

1. nacl.sign.keyPair generates a key pair consisting of a 32-byte public key and a 64-byte secret key. Example:

{
  publicKey: Uint8Array(32) [
    105, 163, 150, 206, 160, 113, 164,
    191, 145, 161,  57, 215,  78, 209,
    204,  38, 148,  73,  20, 173, 115,
    236, 207, 233, 142, 206,   5,  25,
     57, 163,  65, 183
  ],
  secretKey: Uint8Array(64) [
     77, 167,  21,  30,  65,  52, 105,  71,  97,  39, 238,
    163,  51, 136, 226,  20,  93,  37, 187, 249,  11, 208,
     65, 115, 151,  40,  31, 242, 185,  68,  68,  46, 105,
    163, 150, 206, 160, 113, 164, 191, 145, 161,  57, 215,
     78, 209, 204,  38, 148,  73,  20, 173, 115, 236, 207,
    233, 142, 206,   5,  25,  57, 163,  65, 183
  ]
}

2. nacl.sign (and nacl.sign.detached) sign a message with a 64-byte secret key.
3. The message (embedded in the case of nacl.sign or provided separately in the case of nacl.sign.detached) can be verified with the corresponding 32-byte public key.

Claim

Internally, the 64-byte secret key actually embeds both 32-byte private and 32-byte public key. Due to a quirk of ed25519 construction, if a different public key part is used for signing another message with the same 32-byte private part, it is possible to reveal the original 32-byte private part.

Attacks

1. Exploiting design vulnerability

The programmer may mistakely use a different 32-byte public key part of the secret key along with the correct 32-byte secret part. If an attacker can provide a different public key part for signing, and the user signs a message with such secret key, the attacker can learn the secret key.

2. Malicious corruption

An attacker gets a write-only access to the system that stores the secret key and modifies the public key part of it. The next time the user signs a message with such secret key, the attacker can learn the secret key.

3. Accidental corruption

Cosmic rays or bugs in software modify the public key part, but not the secret key part, thus allowing anyone know has different messages signed under different public key parts to learn the secret key.

What is a secret key?

According to Wikipedia, "A key in cryptography is a piece of information, ... when processed through a cryptographic algorithm, can encode or decode cryptographic data. Based on the used method, the key can be different sizes and varieties, but in all cases, the strength of the encryption relies on the security of the key being maintained" (emphasis mine).

Indeed, if we suppose that an attacker (be it an actual attacker or a cosmic ray) can modify the secret key, to various degrees, most of the cryptosystems are not secure.

How attacks affect NaCl/TweetNaCl/TweetNaCl.js

1. Exploiting design vulnerability

NaCl uses 64-byte secret keys. Its API does not allow providing the public key part of it separately for the signing operation. Some other libraries, as listed in https://github.com/MystenLabs/ed25519-unsafe-libs (earlier thread: jedisct1/libsodium#170), allow providing the two 32-byte parts separately, making it more likely that the programmer creates a design vulnerability.

No such mistake can happen with NaCl unless the programmer knowingly and deliberately modifies the secret key. Thus, the attack 1 is not valid for NaCl/TweetNaCl/TweetNaCl.js.

2. Malicious corruption

...where we have an attacker that cannot read the secret key, but can modify it.

If we consider this a valid attack, then the attack is valid even without the design quirk of ed25519. Similar to the timing attack, the attacker can modify the 32-byte secret part of the key, zeroing out some bytes, and leaving some of the original bytes, receiving signed messages, bruteforcing the non-zeroed secret key bytes by signing the same message with guesses, and repeating until learning the whole secret key.

If this is a valid attack, it is also a valid attack on AES.

Here's an example of the attack on AES, where an attacker can modify the secret key and sees two encrypted messages:

1. A user generates and stores a 128-bit AES key, using it to encrypt messages.
2. The attacker, who is capable of bruteforcing, say, 2^64 AES operations, zeroes out the first part of their key.
3. The user encrypts a message with the modified key.
4. The attacker gets the encrypted message and bruteforces the 64-bit key, knowing that the second part of the key is all-zero.
5. The attacker zeroes out the second part of the key (leaving the first part unmodified).
6. The user encrypts another message with the modified key.
7. The attacker gets the encrypted message and bruteforces the 64-bit key, knowing that the first part of the key is all-zero.
8. The attacker now posseses two 64-bit parts of the key, and combines them to get the user's 128-bit key.

Again, this is a version of the common timing attacks, and can be scaled for any capability of the attacker down to bit-by-bit corruption - this would require up to 128 messages to reveal the whole key with a capability of bruteforcing only 2^1 operations.

Referring back to the definition of the secret key, we don't consider attacks that compromise the security of the secret key valid. Thus, either the attack 2 is not valid or it is valid for all cryptosystems.

3. Accidental corruption

Same argument as for 2 — the cryptosystem relies of the security of the secret key. Additionally, if we consider accidental corruption of the secret key a valid attack, we should not only consider it valid for inputs/outputs, but also for the internal workings of the algorithm — the corruption can happen during any stage of it.

I realize that they are various degrees to corruption. Is it more likely to happen to the permanent storage than memory? Maybe. It's definitely more damaging to the secret key of ed25519 due to the mentioned quirk.

The attack is outside the scope of TweetNaCl.js. The library provides functions to sign messages with the secret key. It doesn't provide a way to safely store the secret key so that it cannot be corrupted.

Defenses

1. Exploiting design vulnerability

The library already doesn't allow providing separate parts of the secret key. The secret key is a 64-byte Uint8Array.

2. Malicious corruption

Potential defence: when provided with a secret key, validate that the public key embedded in it is actually the key that was derived from the secret material (or just re-derive for every signing.) Or verify the signature after signing (caveat).

This defense doesn't work against this attack. See the attack in which the attacker just modifies parts of the 32-byte secret part.

3. Accidental corruption

Same potential defense as for 2: we can detect if a part of the second 32-byte part of the secret key was corrupted. Only applies partially — doesn't (and cannot) fix accidental corruption elsewhere.

Conclusions

1. TweetNaCl.js provides a way to sign messages with a 64-byte secret key. Handling of the secret key (specifically, making sure it is stored securely, not modified, and not corrupted) is a responsibility of the programmer when designing and coding a cryptographic protocol and is out of the scope for this library.

2. If we consider the above attacks valid, they apply to all cryptosystems and all cryptographic libraries, to a degree. In fact, all of the above also applies to secret keys and nonces in nacl.box and nacl.secretbox (e.g. an attacker modifying a nonce so that it repeats) and is not unique to ed25519.

Comment

In general, NaCl/TweetNaCl/TweetNaCl.js have an API that is pretty robust against misuse — they don't allow many of the common pitfalls. However, they still depend on the correct handling of nonces and secret keys.

Some libraries, such as Google's Tink are more high-level and better in this regard: no worry about nonces and some higher-level key management.

Am I missing something else?

[dchest]

I don't think this is the bug mentioned in https://github.com/MystenLabs/ed25519-unsafe-libs. That issue affecting some libraries is that the 32-byte secret signing key is provided separately from the 32-byte public key, which is also used during signing, and thus they allow providing a different public key for signing for the same secret key. The API of tweetnacl-js (which is the same as tweetnacl) doesn't allow providing a separate public key unless the programmer manipulates the right part of the secret key themselves, which we can't prevent — it's the full 64-byte key, which includes both parts. I don't think validation is need for our case.

[dchest]

I would still change it, my main concern at this point is 3) accidental corruption, which could happen at some point. Cryptography should be misuse-resistant. Corrupted 32-byte private key would not be able to decrypt previously encrypted file, or sign txs from the same account — so it's alright.

"Mr. Babbage, if you put into the machine wrong figures, will the right answers come out?"

Indeed, a lot of effort in computing goes into protecting against corruption: ECC memory, rad-hardened CPUs, storage checksums, network packet checksums, database page checksums, authenticated encryption, memory-safe languages. Should we put a (literally) half-working solution to protect against a minuscule chance of accidental corruption at the cost of halving the performance by default? I don't think so. In fact, if our goal is to protect against accidental corruption, adding a simple checksum byte at the end of the secret key is a much better solution: it's faster and more reliable.

[CMEONE]

I assume you're posting this because of everything that went down yesterday on Solana and other chains regarding the wallet private key exploit?

[CMEONE]

@dchest Thanks for such a thorough explanation! I would say that for the current state of #248, freezing the keys would help prevent programmers from modifying the key accidentally (although this wouldn't prevent manual modifications or corruption), but I'm not sure whether you feel this type of behavior differs too much from the original TweetNaCl implementation and should be done in a fork instead.

[steveluscher]

I was going to say most of what you said @dchest, but you said it more eloquently. I haven't been able to think of a mechanic to produce the signatures required to recover a victim's private key that don't rely on:

• Being able to insert malicious pubkey-modifying code at the callsite to nacl.sign.detached (in which case you already have access to the secret => pwned)
• Convincing a user to entrust your system with their private key, so that you can execute this attack (in which case, you already have the private key => pwned)

The only thing I have to contribute here are some comments on the design of the API and type system, which I've illustrated in #248, but don't intend to land. They're for discussion only; feel free to run with all or none of it!

[paulmillr]

@dchest that makes sense — thanks for detailed write-down and spending time on this.

I would still change it, my main concern at this point is 3) accidental corruption, which could happen at some point. Cryptography should be misuse-resistant. Corrupted 32-byte private key would not be able to decrypt previously encrypted file, or sign txs from the same account — so it's alright.

It's up to you to decide whether to make a trade-off, or follow approach of similar libraries. I will see if I can produce some example that emulates real-world data corruption.

[CMEONE]

I agree, such corruption checks should not be added to the core library for rare instances, especially if it comes at the cost of significantly decreased performance. I feel like protecting against key corruption is out of scope for most cryptography libraries (including tweetnacl-js) and should be implemented by developers according to their own secure key management systems.