Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
    
Fast C implementation + JNI calls = reasonably fast Java implementation –  pg1989 Jul 3 '13 at 21:34
    
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. –  hunter Jul 3 '13 at 22:12
    
@pg1989 I'd prefer to avoid a JNI solution if possible. –  Nuoji Jul 3 '13 at 23:02
    
@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. –  Nuoji Jul 3 '13 at 23:04
    
@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. –  hunter Jul 4 '13 at 0:04

1 Answer 1

up vote 5 down vote accepted

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.

share|improve this answer
1  
Exactly. Salsa is fast thanks to SIMD - Java has no SIMD - Salsa becomes slow. –  orlp Jul 4 '13 at 1:45
    
Awesome answer. It begs the question "what's the stream cipher with the fastest java implementation?" though. Any ideas? –  Nuoji Jul 4 '13 at 8:27
    
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. –  archie Jul 4 '13 at 10:33
    
Do you have a link to an optimized Salsa20 implementation? –  CodesInChaos Jul 4 '13 at 11:29
2  
djbs Salsa20 page has a variety of optimised implementations and a breakdown of their throughput in the ECRYPT benchmarks. –  archie Jul 4 '13 at 19:37

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.