crypto.getDiffieHellman missing

[browserify]

crypto.getDiffieHellman missing

[dominictarr]

sweet.

[juliangruber]

doesn't look like it's possible, with a private key approx. the size of the used prime the computation just takes forever.

[juliangruber]

and a private key <= 10000 won't be of much real help I guess

[juliangruber]

also node's crypto api is using buffers for big numbers, so I constantly have to convert from buffers to bignumbers and back

[dominictarr]

bignumbers are strings? I guess we'd need a bignumber implementation that uses bops.
Also, maybe emscriptem is a viable option here?

[juliangruber]

bignumbers are objects with coefficients, exponent and sign.

The operation that is causing trouble is:

2 ^ x % prime, 0 < x < prime

The smallest prime we could use is modp1:

155251809230070893513091813125848175563133404943451431320235
119490296623994910210725866945387659164244291000768028886422
915080371891804634263272761303128298374438082089019628850917
0691316593175367469551763119843371637221007210577919

[juliangruber]

hmmm, probably there already exists a very efficient way of calculating this term? cc @mikolalysenko

[dominictarr]

those all look like integer operations... maybe we just need big int, not big number?

[juliangruber]

i found http://john-edwin-tobey.org/Scheme/javascript-bignum/docs/files/biginteger-js.html, but the largest exponent it allows in .pow is 2147483647

[juliangruber]

this

x ^ y % z

operation must be common in computer science, I'm pretty sure there's a smart way to calculate it.

[mikolalysenko]

Yep. Pretty standard trick: http://en.wikipedia.org/wiki/Exponentiation_by_squaring

[jdeblese]

I'm interested in tackling this problem, if no one's worked on it further?

I've been reading the RFCs on SSH and DH key exchange, but I'm not intimately familiar with it so correct me if I'm wrong...

• The private key is just some long, random integer
• The public key is 2 ^ (private_key) % prime, with prime being either modp1 or modp14, the factor 2 being the generator.
• The shared secret is (other_public_key) ^ (private_key) % prime

Is this correct?
Should be easy enough. I hacked together a quick test of that exponentiation by squaring technique and it did 2 to the power of a random 10 digit number in less than a millisecond under Chrome. We'll see if it holds up to a 200+ digit key.

[dominictarr]

sounds good!

[jdeblese]

Speed will depend very much on the bignum library used. First one I tried needed 2 minutes to calculate the modp14-based public key. Using node-bignumber and its modexp function cut that down to half a second.

https://github.com/JoeDoyle23/node-bignumber

How do you feel about adding another require to crypto-browserify?

[juliangruber]

hmm that's a big dependency... Maybe you can pick only what you need? I did the same for keypair and included only the parts of forge that I needed.

I assume that most people use crypto-browserify for hashing functions and currently this module is quite small. But with @substack's upcoming dead code removal, adding something like node-bignumber shouldn't be that big of an issue.

[jdeblese]

Ok, I'll see how much I can scrap before it stops working, and I'll look around to see if there aren't any smaller libraries I could use.

I plan to use crypto-browserify to build an SFTP app for a Chromebook, as options for getting files on and off that machine are otherwise limited.

[dominictarr]

@jdeblese add whatever it takes to make crypto-browserify work just like node's crypto.
if it gets large what we do is split each part into it's own file so you can do require('crypto-browserify/create-hash') and that just gives you the simple bit.

[juliangruber]

true, forgot about that

[jdeblese]

Ok, got something basic working in my fork. Seems to work, but comments are welcome.

I compared it with node.js for a few random private keys, and it correctly generates the public key. Also correctly generates the shared secret for a given public key.

Everything about key generation said just generate a long random number, so that's what I used. That could probably be improved, as well as the createDiffieHellman function.

[dominictarr]

@jdeblese link?

[jdeblese]

@dominictarr oh, sorry: https://github.com/jdeblese/crypto-browserify

[jdeblese]

I've been looking at implementing some of the other missing functions, such as createVerify, but it seems node.js relies directly on OpenSSL to implement this. I can't reimplement that in javascript on my own, so I think our best bet for more advanced functionality is the webcrypto api:

http://www.w3.org/TR/WebCryptoAPI/

There's a partial pure JS implementation here: https://github.com/polycrypt/foxycrypt
The API is being implemented in Chrome, in version 32 if I read correctly.

Crypto-browserify could then just serve as a wrapper.

edit: sorry, wrong link. Foxycrypt is an implementation using Firefox NSS. The pure JS implementation is at http://polycrypt.net/

[jduncanator]

The pure diffie-hellman exchange isn't computationally intensive at all. The computationally intensive part of DH is actually the generation of the base and prime. Assuming you have already generated these (which most people have, there is really no use-case to in-browser generation of base/prime) then the actual Diffie-Hellman exchange is a simple exponentiation and modulus away. I have a Diffie-Hellman branch in my local fork that I'll submit a pull-request for in a few days.

[dominictarr]

@jdeblese I think the best approach here is to make your diffieHelman code it's own module,
the reason that crypto is one module is because node is just wrapping openssl. but we are basically rewriting openssl in javascript... so, we should do that a javascript way, modular.
then crypto-browserify can just be a bundle of modules, so it's a partial drop in (I do not intend to implement all of openssl!) for node's crypto.

[dominictarr]

the most important thing here is tests. I'd have tests that can do an DH exchange between two instances of DH.js, and between DH.js and node. I wonder also if we can implement a big number lib on top of buffers?

[jduncanator]

I have tests that do tests against the OpenSSL test servers that run OpenSSL DH which I've ported the code across from. The test cases are really quite extensive and I've been adding test cases as I've been finding bugs. I'll be putting all my implementations in my own fork for now so if you wish to merge it in some time later down the track then you can do so. If you check out https://github.com/jduncanator/cryptonum then you'll see the ported JSBN2 library I'm using for DH.

Implementing any bignumber library on top of a Buffer SHIM in a browser will be immensely slow. I'm currently in discussion with a few Chromium developers in a mailing list regarding performance and there should be a bug fix incorporated tonight into the nightly build that fixes some performance issues regarding <26 bit operations. Performance wise, using Nodes randomBytes, it takes 36ms to do a diffie-hellman exchange (thats with both sides of the agreement happening on the same computer). It seems to me that the actual limitation is Nodes randomBytes implementation as it takes 21ms to get a 1024bit random array.

Regarding RNGs, I've ported across the Linux Kernel's CPRNG to Javascript in place of using Math.random on browsers lacking the crypto api. The reason for this is its based on a publicly audited method, its efficient and it allows entropy to be mixed in trivially! I'm working on entropy sources but for now I have Math.random as a filler when entropy is low (as opposed to blocking on /dev/random) and then to simply add entropy over time I'm using all of the following when available:

• ondeviceorientation/ondevicemotion - Pulls in motion and orientation data from a devices gyro/accelerometer as fast as the browser will dish it out. The algorithm prefers fractional changes as these minute differences are more likely to be random (eg. iPhone in the car, laptop on a lap etc.) Estimated entropy is based on 1st through to 5th level deltas.
• onkeypress - Generates entropy from keyboard input, mainly timing between key press events. I'm still discussing with some friends about the sort of entropy level this contains.
• onkeydown/onkeyup - Main source of keyboard entropy. I use the timing between keydown and keyup events and hash them directly into the entropy pool. Like above, still discussing entropy level
• onmousemove - Uses mouse movements as a source of entropy. Uses code almost directly ported from PuTTy's keygen tool. Entropy from this is calculated using 1st to 4th level deltas. Once 4th to 1st level deltas are the same mouse movements stop contributing entropy.
• Math.random - Simply pulls in x amount of bytes every second and hashes them into the entropy pool. Estimated entropy is around 1bit per byte (unless the browser is detected to be Opera in which case their Math.random returns 53bits of entropy per all [See Here]) .
• window.performance API - Uses the performance API if available to factor in page and resource load times. Entropy is estimated at 1bit per byte of data generated.
• DOM - If all (or most) of the above are unavailable or are unable to provide enough entropy then the DOM will be used as a source of seed entropy to seed the PRNG at page load. As entropy only ever increases there is no consequence to using the DOM (which isn't exactly random) to add entropy so long as an attacker is not able to deduce the internal state of the PRNG solely from controlling the DOM. This is mitigated by hashing all DOM input before mixing into the entropy pool.

The above are in order of preference. All new Apple devices support the first source (motion) and with tablets on the rise, I wouldn't mind betting that around 40% of devices on the market today have some sort of Gyro in them. Also, I've added a sanity check for Nodejs and will use the Nodejs CryptoAPI in place of our own if the library is running under node (which could be possible).

[jduncanator]

Oh I also forgot to mention that I plan on adding "external" sources for entropy. Developers can then choose to use these if they wish as they are not strictly adhering to the Node.js CryptoAPI. Currently I have a WebSocket server that simply dishes out Cryptographically secure random data when requested. This is only used as a source of entropy when entropy is running low.

[jduncanator]

I've pushed my code, take a look at this commit: jduncanator@8023761

As of now, everything works except for DH Parameter generation which will come after I finish my CSPRNG.

[dominictarr]

Wow, looks good!
you didn't push any tests though.
Also, where is the random number generator code?
From what I see, your fork still has the Math.random fallback.

Is depending on an external entity for entropy safe? this seems like a vulnerability.

@jduncanator can you publish the dh stuff as a separate module and we'll just have crypto-browserify depend on it?

[jduncanator]

For some odd reason, Browserify is now screwing up under Firefox and IE < 10. From all my debugging Buffer.isBuffer is screwing up and Buffer._isBuffer doesn't exist. Not sure if the substack guys did something to mess up buffer-browserify but none of the current tests are passing. Even rebasing and forcing testling to run previously fine tests again causes them to fail. Not sure whats going on for now, so ignore the testling test results until its fixed.

[jduncanator]

The tests I am still porting but with Browserify bugging up at the moment, I can't make much more progress.

The random number generator isn't done yet so I haven't merged in the branch. I'll do it once its working alright. Like said, external entropy isn't exactly a mainline feature of Node.js so it will be an optional thing to enable. That said, a WebSocket server running over WSS should be pretty safe as you'd have to mount a MITM attack AND fake a SSL Certificate to do that.

[dominictarr]

Just because it isn't finished, doesn't mean you shouldn't push it!
unfinished code is the code with the most to gain from being public!

@jduncanator so, they could hack the random number machine.
it just massively expands the attack surface. I guess if it's easy to mix in another entropy source,
then that is okay, because you can just not use it. How much random bytes do you need anyway?

OH by the way, believe it or not @substack is actually only one person!

[jduncanator]

Check out jduncanator@34fb84d, I've implemented DH Parameter generation. It seems to be faster than OpenSSL's generator but I believe thats due to the fact that its using Math.random which is faster.

The code for the RNG breaks everything so the buildbot complains and I loose "maintainability score" (sorry, I'm a stat junkie 😄). How exactly does a verifiable external entropy source "massively expand attack surface". I have a node.js WebSocket server that simply pumps crypto.randomBytes over the connection when requested and it runs over WSS (the SSL version of WebSocket). If you can Man-In-The-Middle the WebSocket connection and fake entropy, then you obviously have the capabilities to MITM the web page connection too, meaning I could simply modify any of the javascript files and get the RNG to dish out 000000000 consistently. If you can hack SSL then you have a lot more to worry about than people messing with entropy. Remember, entropy never decreases it only increases, so mixing in a source of zero entropy does nothing.

On top of that I also pushed a copy of the documentation for the CryptoAPI here

[dominictarr]

exponentation by squaring is not enough here, since the exponent is very large, and x is 2.
because 2^x == 1<<x.
If X is very large, you have just allocated a very large buffer of zeros with one 1 at the end.

but, there are simplifications that take advantage of doing the modulus at the same time.
currently learning about this.

[dominictarr]

http://en.wikipedia.org/wiki/Modular_exponentiation

[jduncanator]

Most of the time you'd use Montgomery reduction when having large exponents. Were you thinking of rolling your own BigInteger library lol?

[dominictarr]

As a learning exercise, (a perfect excuse): https://github.com/dominictarr/math-buffer

[jduncanator]

One issue with using Buffers for Math is that most browsers won't recognise the pattern and hence won't be able to optimize it well... just a thought.

[dominictarr]

the cool browsers have Uint8Array, which makes this: https://github.com/feross/native-buffer-browserify
possible.

[dominictarr]

All these functions work with Arrays too.

[calvinmetcalf]

mostly there the key was @indutny's fantastic (but poorly documented) big num library which implements the Montgomery reduction.

[indutny]

I'd strongly advise against using montgomery here, it is much faster to use pseudo-mersenne primes reduction, and bn.js supports it too.

[calvinmetcalf]

excellent I will update it

On Mon, Nov 3, 2014 at 12:28 AM, Fedor Indutny [email protected]
wrote:

I'd strongly advise against using montgomery here, it is much faster to
use pseudo-mersenne primes reduction, and bn.js supports it too.

—
Reply to this email directly or view it on GitHub
#12 (comment)
.

-Calvin W. Metcalf

[calvinmetcalf]

@indutny assuming I am converting the modp groups to pseudo-mersenne objects correctly then doing a Montgomery reduction with a pseudo-mersenne prime is approximately 50x slower, not much speed up over regular reduction.

[indutny]

This is because converting to and from Montgomery representation is not cheap. Also, you don't really need montgomery representation if you are using psudo-mersenne primes that bn.js knows, see: https://github.com/indutny/bn.js/blob/master/test/red-test.js#L119-L123

[calvinmetcalf]

sorry mis phrased, montgomery with regular prime is 50x faster then non-Montgomery with psudo-mersenne primes,

[calvinmetcalf]

I had to make some edits to bn.js to allow me to define new primes but the psudo-mersenne code path was being followed

[indutny]

@calvinmetcalf could you please post a benchmark? (I assume you are benching it on bn.js)?

[calvinmetcalf]

I was running them in the DiffieHellman, I can port them over to your repo if that is easier.

I had to make these changes to allow me to define more primes then these in my repo to use the psudo-mersenne primes.

[indutny]

Ok, this is probably because they don't have fast imulK: https://github.com/calvinmetcalf/bn.js/blob/41244674376a76e6fe1479c9a1af6f0d33a9e038/lib/bn.js#L1482-L1510

[calvinmetcalf]

@indutny I figured I was missing something, thanks

[calvinmetcalf]

I don't think the modp primes are psudo-mersenne primes modp1 is 2^768 - 2^704 - 1 + 2^64 * { [2^638 pi] + 149686 } so k (which would have to be less then 2^(768/2) or 2^384 ) would be 36f0255dde973dcb3b399d747f23e32ed6fdb1f77598338bfdf44159c4ec64ddaeb5f78671cbfb22106ae64c32c5bce4cfd4f5920da0ebc8b01eca9292ae3dba1b7a4a899da181390bb3bd1659c5c9df0000000000000001 which comes out to be bigger then 2^384

[indutny]

@calvinmetcalf what prime are you using? :) Not every prime is pseudo-mersenne prime.

[calvinmetcalf]

the modp primes you get from crypto.getDiffieHellman, pseudo-mersenne might
only work as a speed up when a prime is generated

On Mon, Nov 3, 2014 at 11:12 PM, Fedor Indutny [email protected]
wrote:

@calvinmetcalf https://github.com/calvinmetcalf what prime are you
using? :) Not every prime is pseudo-mersenne prime.

—
Reply to this email directly or view it on GitHub
#12 (comment)
.

-Calvin W. Metcalf

[indutny]

Ah, it is for random primes. I guess then the Montgomery is the only way to go right now in bn.js.

[calvinmetcalf]

@indutny worse, random ones might sometimes work, these are specced to never work :) when generating primes we can (try) to make them pseudo-mersenne

[indutny]

@calvinmetcalf I think it is pretty dangerous business. I'd rather keep them random.

[calvinmetcalf]

I'm adding in the ability to generate primes, but the modp stuff is mainly to copy the current node api..

[calvinmetcalf]

Right read what you were responding to, generating them fully randomly

[dominictarr]

closed by: #62