BigInt: clarify cryptography usage

[paulmillr]

MDN URL

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/BigInt#usage_recommendations

What specific section or headline is this issue about?

Cryptography

What information was incorrect, unhelpful, or incomplete?

The operations supported on BigInt values are not constant-time, and are thus open to timing attacks. JavaScript BigInts are therefore not well-suited for use in cryptography.

What did you expect to see?

The operations supported on BigInt values are not constant-time, and are thus open to timing attacks. JavaScript BigInts are therefore could be dangerous for use in cryptography when used without mitigating factors.

Something like this

Do you have any supporting links, references, or citations?

There are tons of libraries which need some rare elliptic curve, or zk protocols, or something else bigint-related. So their solution is to use wasm, or pure js bigint stuff.

Using native bindings does not guarantee any resistance against timing attacks. Because, JS runtime would still be there. JS is garbage-collected language. And there are no guarantees your uint8arrays or any other data structure would be cleaned properly at some point. If you want 100% constant-time code, your best bet is using low-level languages directly, but even they are not the 100% solution: LLVM & other compilers could "optimize out" constant timeness.

"Using a native crypto library" means users would need to run unsigned wasm binaries that may as well contain malware & trojans. Using pure javascript code allows every JS developer to verify the js code is indeed the one published on GitHub. Compiling C / Rust code to wasm produces huge binaries, commonly without using reproducible builds. The binaries may, or may not contain some dangerous garbage.

NPM got hacked. GitHub got hacked. Developer accounts can and will get hacked. Binaries will be replaced with malware without account owner's knowledge. So using bigints js library is not worse than a bytebuffer-based wasm solution. I think, it's better.

In fact, i've developed some bigint crypto libraries, which already received security audits.

Do you have anything more you want to share?

No response

[Josh-Cena]

The alternative to "using bigints" is not "using some random binary distributed on npm / GitHub". Uint8Array, AFAICT, can be made safer than BigInts because of its lower level of abstraction. You can guarantee a more constant-time operation. Of course you can still write everything yourself; it's just a little caveat that you should not use BigInts as your underlying implementation.

Still, I'd happily review a PR that adds a paragraph or two explaining how it can be mitigated with BigInts, or what alternatives there are :)

[paulmillr]

The alternative to "using bigints" is not "using some random binary distributed on npm / GitHub"

Everyone is using npm and github nowadays. Asking people to not use these distribution channels cannot be effective. To be precise, i'm talking about cases when a popular package by a trusted maintainer gets backdoored and malwared because their pc gets infected, or when a hacker replaces binaries in trusted repo directly. GitHub and NPM were hacked quite a few times and people would still download the bad wasm binaries.

You can guarantee a more constant-time operation

"More constant time" in relation to what, and why? Any real tests showing this? Overall that's false: there are no guarantees. Garbage collection, JIT compilation, using branches, LLVM (etc) optimization, cpu optimization, cache misses, different cache lines. Writing truly constant-time code is absolutely non-trivial. Even using division is not constant-time. Should division opcode be prohibited in cryptography because of that?

Still, I'd happily review a PR that adds a paragraph or two explaining how it can be mitigated with BigInts, or what alternatives there are :)

I will think of something and come back with better wording.

[Josh-Cena]

Sigh I think you're right. Time complexity in JS is mostly bananas.

[Josh-Cena]

@paulmillr I trust your expertise on security, so if you have any ideas about how to improve, feel free to send a PR. I'll assign this to you for now.

[Josh-Cena]

I did some research on this. tc39/proposal-bigint#186 and tc39/proposal-bigint#187 came up. I believe that's the primary motivation for that paragraph.

[paulmillr]

Thanks for investigating this!

I don't think @martinthomson is fully comprehensive in the wording.

The choice in JS libraries is not between "generally insecure bigints" and "secure webcrypto". It's choice between "generally insecure bigints", "absolute garbage libraries that implement bigints in js", and "3-megabyte potentially malware-infested unsigned binaries which barely mitigate the issue". There is no "secure webcrypto", really. Try using webcrypto for keccak, blake2b, or scrypt. Webcrypto only implements a few algorithms, that's mostly it.

1. Pointing users to WebCrypto, which does not even implement Bitcoin curve secp256k1 is not helpful. "In theory" you should not use bigints. "In practice", you either use bigints, or something worse. Timing channel security in JS is extremely complex topic and it is definitely not mitigated by "using openssl compiled to wasm".
2. We're having more and more usage of various exotic protocols, zk-s[tn]arks, new curves like Pallas/Vesta/bls12-381. All of them require some kind of JS implementation. It would either be bigints, or something worse. Modern protocols also require good-enough speed, bigints allow to achieve it.
3. Noble crypto was audited by independent security firm, and a few others at least glanced at it while auditing end-user applications. That included claimed resistance to side-channel attacks.
4. Professor Matthew Green from Johns Hopkins University wrote an article about terrible state of cryptography in metamask: https://blog.cryptographyengineering.com/2022/01/14/an-extremely-casual-code-review-of-metamasks-crypto/. He also praised Noble.

Regarding the updated wording, I believe it should be:

The operations supported on BigInt values are not constant-time, and are thus open to timing attacks. JavaScript BigInts are therefore could be dangerous for use in cryptography when used without mitigating factors. As a very generic example, attacker could measure time difference between 101n ** 65537n and 17n ** 9999n, and deduce secrets, such as private keys, based on the time passed. If you still have to use bigints, take a look at https://timing.attacks.cr.yp.to/programming.html for general advice regarding the issue.

Let me know if I should send this as PR.

[paulmillr]

Notice that i've changed "not well-suited for use in cryptography" to "could be dangerous" - which makes bolder claim.