ed25519 verification is malleable and accepts forged signatures

[paulmillr]

tweetnacl ed25519 signature verification is malleable and does not have SUF-CMA (strong unforgeability under chosen message attacks). Malleability is problematic in blockchain context. MtGox was hacked because of it.

// mkdir test && cd test && npm init -y && npm install @noble/curves@1.0.0 tweetnacl@1.0.3
// touch demo.mjs; then node demo.mjs
import { ed25519 } from '@noble/curves/ed25519';
import { bytesToNumberLE, numberToBytesLE } from '@noble/curves/abstract/utils';
import { default as nacl } from 'tweetnacl';

const priv = ed25519.utils.randomPrivateKey();
const pub = ed25519.getPublicKey(priv);
const msg = new TextEncoder().encode('hello world');
const sig = ed25519.sign(msg, priv);
const [R, s] = [sig.slice(0, 32), sig.slice(32, 64)];
const s_forged = numberToBytesLE(bytesToNumberLE(s) + ed25519.CURVE.n, 32);
const sig_forged = new Uint8Array([...R, ...s_forged]);

console.log('reference', ed25519.verify(sig, msg, pub), ed25519.verify(sig_forged, msg, pub));
console.log('nacl', nacl.sign.detached.verify(msg, sig, pub), nacl.sign.detached.verify(msg, sig_forged.slice(), pub));

The behavior defies RFC 8032, which prohibits S >= L. Folks in 2020/1244.pdf also mentioned similar stuff.

[dchest]

Thanks! I've added a new Security Considerations section to README which describes this and some other properties.

Since this library is supposed to be a 1-to-1 port of the original TweetNaCl (with some parts ported from other sources for performance reasons), I don't want to introduce potential breaking changes to it until at least 2.0 (if it ever happens).

I will keep this issue open as a proposal for 2.0 if I decide that it no longer should be the TweetNaCl port and implement all the recent security improvements for the original NaCl.

[nikitaeverywhere]

@dchest thanks for your work on tweetnacl-js. As I see you're busy on other projects, are there any plans to accept PRs/maintain this lib? What's the state of its maintenance?

Also to @paulmillr: appreciate your work and used your library as well in some of my projects. My use case in one of them however requires the tiniest possible in size asymmetric encryption ("box") + sign/verify primitives. When compared to tweetnacl, your lib is still ~100% larger in bundle size (which is critical for my purposes), while I tried my best to minimize it.

I would be more than grateful if either of you @paulmillr @dchest could suggest how to mitigate the described signature malleability problem in tweetnacl tho. I'd be happy to fork/and/or PR the fix, if that's not the "core" problem. I believe this will help others too. Or if there is any existing fork with fix it that I'm not aware of, I'll be happy to take a look.

RFC 8032, which prohibits S >= L

How "big" is the fix actually?

[dchest]

@nikitaeverywhere TweetNaCl-js achieved its goal of porting TweetNaCl to pure JavaScript and thus is the state of the "finished software". The expected maintenance is only fixing bugs and future JS compatibility issues if found. Maybe ES-module support in the future.

Now that everything supports WASM, I'd recommend using WASM-compiled libsodium or something like it instead. Alternatively, WebCrypto APIs are starting to add 25519, so it may be an option. For Node, I believe there's OpenSSL-based native support for 25519.

[paulmillr]

@nikitaeverywhere

your lib is still ~100% larger in bundle size

Can you clarify how you've measured it? Exporting this with esbuild gives similar-sized 2.3KLOC build as tweetnacl.

export { ed25519, x25519 } from '@noble/curves/ed25519';
export { chacha20poly1305 } from '@noble/ciphers/chacha';

[nikitaeverywhere]

@nikitaeverywhere TweetNaCl-js achieved its goal of porting TweetNaCl to pure JavaScript and thus is the state of the "finished software". The expected maintenance is only fixing bugs and future JS compatibility issues if found. Maybe ES-module support in the future.

Got it, thanks for explaining @dchest. I've found a nicely refactored tweetnacl-ts library which solves es modules & tree shaking for me. Still, I'm thinking to refactor the "slower" implementation which will save another 8kb on a bundle size.

Now that everything support WASM, I'd recommend using WASM-compiled libsodium or something like it instead. Alternatively, WebCrypto APIs are starting to add 25519, so it may be an option. For Node, I believe there's OpenSSL-based native support for 25519.

Thank you. My js requirements are very unique - I can't use browser APIs (which also means no WASM) and I need the most minimal library size possible. Given this tweetnacl (~ tweetnacl-ts) seems to be the best candidate out there.

[nikitaeverywhere]

Can you clarify how you've measured it? Exporting this with esbuild gives similar-sized 2.3KLOC build as tweetnacl.

@paulmillr my requirements were:

• basic crypto primitives, any methods
  • sing + verify
  • asymmetric cipher (encrypt with public key, decrypt with private)
• no browser apis used (this is on me - not expected from libs)
• the smallest bundle size possible (important)

I have around ~10-20kb of overhead to my own js above crypto libraries, and I've got the following results so far, just FYI:

Script 1 size:
~42.19kb with @noble/* cryptography libraries
~39.65 tweetnacl
~33.8kb tweetnacl-ts
~25.64kb tweetnacl ("slower version"), (~13.41 gzipped)

Script 2 size:
~45.15kb @noble/* cryptography libraries
~30.77kb tweetnacl (due to no tree shaking I guess; script 2 doesn't use sign/verify)
~29.75kb tweetnacl-ts (~14.93 gzipped)
// Presumably slower tree-shaked tweetnacl version port would give ~23kb

This was the quick test by using @noble/* vs tweetnacl* libs.

tweetnacl imports:

import { box_keyPair, sign_detached_verify, sign, box, box_open } from 'tweetnacl-ts';

@noble/* imports:

import { xchacha20poly1305 } from '@noble/ciphers/chacha';
import { concatBytes } from '@noble/ciphers/utils';
import { ed25519 } from '@noble/curves/ed25519';
import { hkdf } from '@noble/hashes/hkdf';
import { sha512 } from '@noble/hashes/sha512';

...which are then bundled with my code by esbuild (minified). The usage is somewhat simplified code from here for encrypt/decrypt, just with one algo, xchacha20poly1305, and sha512 instead of sha256 for hkdf to decrease the bundle size. I need to admit I'm not very advanced in primitive cryptography, so perhaps my task (sign/verify + encrypt/decrypt asymmetric) could include less cryptographic primitives – LMK if you think so :)

[paulmillr]

@nikitaeverywhere it's actually 36KB vs 28KB, 30% increase - not 2x. Let's move here to not disturb Dmitry with offtopic https://gist.github.com/paulmillr/f655a39d7144481e1bc0a374fb65689d