For Java I'm only aware of the Bouncy Castle implementation of Salsa20. However, that version is significantly slower than AES-CTR and ARC4.
There are plenty of libraries in C, but are there any good implementations of this stream cipher in Java?
$\begingroup$
$\endgroup$
5
-
$\begingroup$ Fast C implementation + JNI calls = reasonably fast Java implementation $\endgroup$– pg1989Commented Jul 3, 2013 at 21:34
-
$\begingroup$ I can't testify as to it's speed, but this java version of NaCl contains an implementation of Salsa20 (and XSalsa20). Give it a try. $\endgroup$– hunterCommented Jul 3, 2013 at 22:12
-
$\begingroup$ @pg1989 I'd prefer to avoid a JNI solution if possible. $\endgroup$– NuojiCommented Jul 3, 2013 at 23:02
-
$\begingroup$ @hunter that implementation is honestly a bit hard to understand, seeing as it only uses static methods everywhere. It's very streamlined just to work with its intended usage. I tried to time it, but I'm not sure I set it up correctly or not. A different implementation would be preferable. $\endgroup$– NuojiCommented Jul 3, 2013 at 23:04
-
$\begingroup$ @Nuoji - yup, it took me a little while to figure it out too, but check out the original documentation as the naming conventions are quite consistent. In the Salsa20 class, you'll find the function crypto_stream_xor. Simply pass in the output buffer c (ciphertext), input buffer m (message), mlen (number of message bytes to be processed), n (8-byte nonce), noffset (0 if you're using Salsa20 and not XSalsa20), and k (256-bit key). Salsa20 test vectors are here. $\endgroup$– hunterCommented Jul 4, 2013 at 0:04
Comments disabled on deleted / locked posts / reviews
|
1 Answer
$\begingroup$
$\endgroup$
7
I doubt you will find a fast implementation of Salsa20 in Java (having spent much time attempting to achieve just this).
Salsa20 mutates a 512 bit state made up of 16 x 32 bit integers, which means that implementations that don't take advantage of SIMD (on Java or otherwise) will probably not perform well - there are too many independent state parts to keep them all in general purpose registers on any common architecture, so you inevitably incur load/store overhead, which kills your throughput.
Java (Hotspot at least) does a reasonable job of optimising all the basic operations (e.g. inlining, single instruction rotate etc.) but it doesn't have the smarts to dynamically do small scale SIMD optimisations.
I've tried various approaches to get around this: simulated SIMD by packing 32 bit integers into 64 bit longs (too many additional instructions); triggering hotspot vectorisation optimisations (too much array munging overhead), and didn't find anything that worked.
By comparison: Threefish 512, despite having the same state size uses 8 x 64 bit words, so on 64 bit Java the entire state can be held in registers, and the performance is ~150% the speed of AES.
The BouncyCastle Salsa20 implementation can be pushed a bit (by registerising the state as much as possible) to get it just faster than AES, but it's still woefully slow compared to implementations on SIMD capable platforms.
XSalsa20 and ChaCha will have the same issues, as they have the same basic structure.
-
2$\begingroup$ Exactly. Salsa is fast thanks to SIMD - Java has no SIMD - Salsa becomes slow. $\endgroup$– orlpCommented Jul 4, 2013 at 1:45
-
$\begingroup$ Awesome answer. It begs the question "what's the stream cipher with the fastest java implementation?" though. Any ideas? $\endgroup$– NuojiCommented Jul 4, 2013 at 8:27
-
$\begingroup$ From a quick benchmark, the fastest stream cipher in BC is RC4 at 11c/b ;). HC-128 does very well (16c/b), followed by HC-256 (18c/b) and Salsa20 (22c/b). AES/CTR for reference comes in at 29c/b. Optimized SIMD implementations of Salsa20 pull about 4c/b, so there's an ~5x penalty in Java. $\endgroup$– archieCommented Jul 4, 2013 at 10:33
-
$\begingroup$ Do you have a link to an optimized Salsa20 implementation? $\endgroup$ Commented Jul 4, 2013 at 11:29
-
2$\begingroup$ djbs Salsa20 page has a variety of optimised implementations and a breakdown of their throughput in the ECRYPT benchmarks. $\endgroup$– archieCommented Jul 4, 2013 at 19:37