crypto.getDiffieHellman missing

juliangruber commented 11 years ago

will see if i can come up with a pr

dominictarr commented 11 years ago

sweet.

juliangruber commented 11 years ago

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

juliangruber commented 11 years ago

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

juliangruber commented 11 years ago

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

dominictarr commented 11 years ago

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

juliangruber commented 11 years ago

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 commented 11 years ago

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

dominictarr commented 11 years ago

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

juliangruber commented 11 years ago

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 commented 11 years ago

this

x ^ y % z

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

mikolalysenko commented 11 years ago

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

jdeblese commented 11 years ago

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 commented 11 years ago

sounds good!

jdeblese commented 11 years ago

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 commented 11 years ago

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 commented 11 years ago

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 commented 11 years ago

@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 commented 11 years ago

true, forgot about that

jdeblese commented 11 years ago

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 commented 11 years ago

@jdeblese link?

jdeblese commented 11 years ago

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

jdeblese commented 10 years ago

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 commented 10 years ago

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 commented 10 years ago

@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 commented 10 years ago

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 commented 10 years ago

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 commented 10 years ago

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 commented 10 years ago

I've pushed my code, take a look at this commit: https://github.com/jduncanator/crypto-browserify/commit/802376113177b1b40a21ea544cd3a23cda15c885

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

dominictarr commented 10 years ago

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 commented 10 years ago

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 commented 10 years ago

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 commented 10 years ago

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 commented 10 years ago

Check out https://github.com/jduncanator/crypto-browserify/commit/34fb84d516396bce2c0b3764ead27da617e61a64, 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 :smile:). 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 commented 10 years ago

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 commented 10 years ago

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

jduncanator commented 10 years ago

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

dominictarr commented 10 years ago

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

jduncanator commented 10 years ago

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 commented 10 years ago

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

dominictarr commented 10 years ago

All these functions work with Arrays too.

calvinmetcalf commented 10 years ago

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

indutny commented 10 years ago

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 commented 10 years ago

excellent I will update it

On Mon, Nov 3, 2014 at 12:28 AM, Fedor Indutny notifications@github.com 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 https://github.com/dominictarr/crypto-browserify/issues/12#issuecomment-61441969 .

-Calvin W. Metcalf

calvinmetcalf commented 10 years ago

@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 commented 10 years ago

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 commented 10 years ago

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

calvinmetcalf commented 10 years ago

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 commented 10 years ago

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

calvinmetcalf commented 10 years ago

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 commented 10 years ago

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

browserify / crypto-browserify

crypto.getDiffieHellman missing #12