Feature request: Crypto APIs should optionally return bigints

[no2chem]

Now that bigint support is part of V8, the crypto APIs should be updated to optionally return bigints instead of buffers.

I've done a bit of testing with N-API and get significantly increased performance, something like 3-4x depending on the algorithm involved, even though I'm using OpenSSL just as Node is to do the hashing: https://github.com/no2chem/bigint-hash

It also seems that providing a one-shot hashing implementation (which just hashes a buffer instead of allocating a Hash object) would improve hashing performance as well.

I'm happy to take a look at submitting a PR for this if this is something that makes sense for node.

[tniessen]

cc @nodejs/crypto

Now that bigint support is part of V8, the crypto APIs should be updated to optionally return bigints instead of buffers.

One problem with bigints is that people might try to use them in order to increase performance by computing hash values as bigints and then comparing them, which will most likely introduce side-channel vulnerabilities since comparing bigints is not timing-safe. How would we compensate for that?

Let's leave performane aside for a moment: Which crypto operations are commonly used to actually produce bigints?

It also seems that providing a one-shot hashing implementation (which just hashes a buffer instead of allocating a Hash object) would improve hashing performance as well.

It obviously will. The current API was designed to allow hashing of arbitrarily large data streams. The same applies to createHash, createSign, createVerify, createCipher, createDecipher, createCipheriv, createDecipheriv and createHmac, but if we decided to add one-shot APIs, we would need to be really careful not to bloat the API surface with lots of functions.

[no2chem]

which will most likely introduce side-channel vulnerabilities since comparing bigints is not timing-safe

While true, I think that differences due to timing comparisons would be due to bit-width, and the digest (hash) size would be fixed by the algorithm chosen, which is going to be the same if you're comparing hashes. Besides, it's just as timing unsafe as comparing a Buffer, I really doubt that the timing performance is value dependent.

[tniessen]

For buffers, there is crypto.timingSafeEqual, but I'm not sure how easy it would be to adapt that to also work with bigints.

[no2chem]

I see, I stand corrected. It seems that the implementation in v8 currently just iterates over the digits:

bool BigInt::EqualToBigInt(BigInt* x, BigInt* y) {
  if (x->sign() != y->sign()) return false;
  if (x->length() != y->length()) return false;
  for (int i = 0; i < x->length(); i++) {
    if (x->digit(i) != y->digit(i)) return false;
  }
  return true;
}

Which seems quite vulnerable to timing attacks.

It seems though that this isn't easily measured. I performed some simple benchmarks:

bigint compare small: 169458328±0.53% ops/s 5.90±0.153 ns/op (91 runs)
bigint compare large: 168162980±1.36% ops/s 5.95±0.397 ns/op (93 runs)
bigint compare large 2vals: 169617690±0.28% ops/s 5.90±0.081 ns/op (96 runs)
bigint compare large with fewer bits: 168035082±1.03% ops/s 5.95±0.300 ns/op (92 runs)
bigint compare large with small: 168757732±0.35% ops/s 5.93±0.100 ns/op (92 runs)
bigint compare large with 1: 169567537±0.26% ops/s 5.90±0.075 ns/op (93 runs)
bigint compare small with 0: 168169244±0.82% ops/s 5.95±0.239 ns/op (92 runs)
bigint compare large with 0: 110366905±3.45% ops/s 9.06±1.417 ns/op (79 runs)

I don't know why comparison with 0 is slower for a large bigint (the length check should just return false), but practically speaking, measuring these time differences would be quite difficult, compared to string/buffer comparisons, which operate much slowly.

I guess it wouldn't be that hard to implement a timing safe-comparison using N-API.

Which goes back to your comment, @tniessen -

we would need to be really careful not to bloat the API surface with lots of functions

I'm not really connected to node development, but what's the preference here over implementing an external library?

[tniessen]

It seems though that this isn't easily measured.

Yes, timing differences are usually barely noticable, and are usually difficult to exploit. However, some scenarios (e.g. massive CPU load causing the process to be much slower, scheduler timing, access to actual CPU time / statistics etc.) make such attacks more likely.

From a (theoretical) cryptographer's point of view, an attacker should not be able to decide whether the first or last bit of a bitstring differs from the expected value with a probability that is significantly better than guessing at random, even if the length of the bitstring approaches infinity. And this is not true for bigints, at least not with the v8 implementation.

I'm not really connected to node development, but what's the preference here over implementing an external library?

I am not sure what you mean, sorry. Could you try to rephrase it?

[no2chem]

From a (theoretical) cryptographer's point of view, an attacker should not be able to decide whether the first or last bit of a bitstring differs from the expected value with a probability that is significantly better than guessing at random, even if the length of the bitstring approaches infinity. And this is not true for bigints, at least not with the v8 implementation.

Sure. My point is just that the differences are even more subtle with BigInts, that's all.
I would make a point that this is also not true for Buffers, you have to use crypto.timingSafeEqual.

I am not sure what you mean, sorry. Could you try to rephrase it?

I mean that you brought up the question of API bloat. Now that N-API is maturing, I wonder what cutoff is for having functionality as a feature within Node, or just implemented as an addon. After all, most of crypto is just a wrapper around openSSL, and it's possible to build Node without crypto support in the first place!

And back to the previous question:

Let's leave performane aside for a moment: Which crypto operations are commonly used to actually produce bigints?

Digests and signatures seem to be pretty clear candidates here. So I would suggest having Hash, Hmac and Sign output bigints, and Verify take bigints as input. And provide a .timingSafeEqual for bigints.

[tniessen]

I mean that you brought up the question of API bloat. Now that N-API is maturing, I wonder what cutoff is for having functionality as a feature within Node, or just implemented as an addon. After all, most of crypto is just a wrapper around openSSL, and it's possible to build Node without crypto support in the first place!

You can definitely implement that as a separate module if you want to, it should be possible using the N-API BigInt API.

[bnoordhuis]

Which crypto operations are commonly used to actually produce bigints?

Anything that produces a hash, key or ciphertext? We currently output strings or buffers but they can easily be restated as bigints. Whether that's useful is another question; I'm undecided.

Some of tls.TLSSocket#getPeerCertificate()'s properties are really just numbers even though we encode them as strings or buffers, e.g., .pubkey, .fingerprint, .serialNumber, etc.

There are probably more examples.

will most likely introduce side-channel vulnerabilities since comparing bigints is not timing-safe

Good point. It should be possible to teach crypto.timingSafeEqual() about bigints. We can unbox them to bitstrings with v8::BigInt::ToWordsArray() and then treat them like we do buffers.

Open question: are other relational operators besides equality needed?

Interesting side question: can two different bitstrings encode the same number or is there a canonical encoding? They're trimmed of leading zeroes, so... yes? Needs more research.

[tniessen]

@bnoordhuis I agree, the only thing I'm unsure about is the usefulness. Most outputs will be transmitted or stored in some way, at which point most of the performance benefits are gone. It sounds reasonable to accept bigints for certain parameters though.

[sam-github]

While some crypto algorithms operate on large numbers, this is mostly opaque to users. Some exceptions exist, the RSA exponent is one. Treating outputs as numbers can also have surprising results, such as when SHA hashes are used for cert serial numbers, and some serial numbers end up being negative.

I'd want to see the performance argued in terms of end-to-end. Having a block cipher return a big int quickly, just so the app can perform an extra step to convert it to a buffer to stream it to a file or network socket might not show any perf improvement, or even be net negative.

[sam-github]

can two different bitstrings encode the same number or is there a canonical encoding? They're trimmed of leading zeroes, so... yes?

Leading ones are an issue, too, the numbers may or may not be negative. And there are endianness issues. A buffer's mapping to a big int can't be known without having some extra information.

[tniessen]

I'd want to see the performance argued in terms of end-to-end. Having a block cipher return a big int quickly, just so the app can perform an extra step to convert it to a buffer to stream it to a file or network socket might not show any perf improvement, or even be net negative.

Exactly!

[no2chem]

@sam-github Bigints are mainly useful in the crypto context in that comparisons are much more efficient than buffer compares. I'd expect that to improve as the bigint support in V8 improves, for example AVX-512 instructions could be used to do compares instead of polluting the processor cache. So if your workload is primarily checking hashes, bigints would result in a big win. In our workloads which do lots of in-memory computations and comparisons of hashes (a Merkle tree) this really helps!

Also, I don't understand your signedness argument. If the output is an unsigned bigint, I'm not sure where the signedness maters. What does matter is the size in bits of the output, which is not included with a bigint. To @bnoordhuis question - two bigints could encode the same number if they were from Buffers with different lengths. Let's use CRC16 and CRC32 as an example: CRC16 could produce 0x1234n, and crc32 could produce 0x00001234n. Buffer.compare() would have treated these as NOT equal, but these bigints are strictly equal:

> 0x1234n === 0x00001234n
true

I don't view this as a problem for digests (As only digests from the same algorithm should be compared), but for other things such as a fingerprints or keys, they could be a problem. Basically, a bigint doesn't store (or have) a maximal number of bits.

Finally,

Having a block cipher return a big int quickly, just so the app can perform an extra step to convert it to a buffer ...

I strongly agree here - I would argue that it'd be important to keep both the buffer and bigint APIs and allow the developer to choose which one to use. If you're going to output a hash (or receive a hash) over a network socket, then probably you want Buffers. If you're doing a bunch of local operations (like computing and comparing hashes locally), then bigints might be much more efficient.