Okay, this is somewhat funny. After putting quite some effort into optimising our implementation of ISAAC, I now propose we replace it with HC-128.
Just like ISAAC and RC-4 before it, HC-128 is an array based stream cipher that we use as an RNG. Comparison:
Security / predictability
ISAAC is designed to be usable for applications that need a cryptographically secure PRNG. But it does not really meet the current standards for one. This makes ISAAC overkill for applications that just need a statistically good PRNG, and not good enough for anything that needs guarantees for security.
HC-128 is designed by Hongjun Wu, one of the experts in the field. It is well received, and selected as one of the "stream ciphers suitable for widespread adoption" by eSTREAM. A very comprehensive analysis of the current state of attacks / known weaknesses of HC-128 is given in "Some Results On Analysis And Implementation Of HC-128 Stream Cipher" by Shashwat Raizada.
HC-128 has no known weaknesses that are easier to exploit than doing a brute-force search of 2^128. Is makes clear security promises, and also has a clear story around initialization.
Performance
HC-128 is an 32-bit algorithm. It performs usually 30% faster than the 32-bit ISAAC, and mostly the same as the 64-bit ISAAC-64. Only for fill_bytes ISAAC-64 is about 45% faster. Note that this makes it still as fast as our implementation until a week ago.
The results here may improve a little bit, because I have not been able yet to have to compiler optimise out all bounds checks. It now does one per u32.
x86 (all numbers in Mb/s):
| PRNG |
u32 |
u64 |
byte stream |
| ISAAC (rand 0.3.16) |
743 |
764 |
432 |
| ISAAC (current) |
916 |
1043 |
1219 |
| ISAAC-64 (rand 0.3.16) |
668 |
1307 |
743 |
| ISAAC-64 (current) |
937 |
1410 |
1451 |
| HC-128 |
1231 |
1417 |
1231 |
x86_64 (all numbers in Mb/s):
| PRNG |
u32 |
u64 |
byte stream |
| ISAAC (rand 0.3.16) |
826 |
831 |
488 |
| ISAAC (current) |
980 |
1118 |
1434 |
| ISAAC-64 (rand 0.3.16) |
937 |
1874 |
620 |
| ISAAC-64 (current) |
1287 |
1930 |
2640 |
| HC-128 |
1300 |
1810 |
1833 |
For the time it takes to initialise I don't yet have good numbers. With the unoptimised routine from hc128 it takes about as much time as ISAAC-64. It can probably be improved by ~30%.
Memory
ISAAC uses two arrays: one to hold 256 state words, and one to hold 256 results. HC-128 needs two arrays of 512 words to hold its state. As an optimisation we include a 16-word array of results.
Memory usage (excl. counters etc.):
| PRNG |
state |
results |
total |
| ISAAC |
256*4 = 1024 |
256*4 = 1024 |
2048 bytes |
| ISAAC-64 |
256*8 = 2048 |
256*8 = 2048 |
4096 bytes |
| HC-128 |
25124 = 4096 |
16*4 = 64 |
4160 bytes |
Overall HC-128 seems like a clear improvement over ISAAC. For ISAAC it is not really clear what its place is in the world. HC-128 is a super-fast cryptographic PRNG that works similar.
Okay, this is somewhat funny. After putting quite some effort into optimising our implementation of ISAAC, I now propose we replace it with HC-128.
Just like ISAAC and RC-4 before it, HC-128 is an array based stream cipher that we use as an RNG. Comparison:
Security / predictability
ISAAC is designed to be usable for applications that need a cryptographically secure PRNG. But it does not really meet the current standards for one. This makes ISAAC overkill for applications that just need a statistically good PRNG, and not good enough for anything that needs guarantees for security.
HC-128 is designed by Hongjun Wu, one of the experts in the field. It is well received, and selected as one of the "stream ciphers suitable for widespread adoption" by eSTREAM. A very comprehensive analysis of the current state of attacks / known weaknesses of HC-128 is given in "Some Results On Analysis And Implementation Of HC-128 Stream Cipher" by Shashwat Raizada.
HC-128 has no known weaknesses that are easier to exploit than doing a brute-force search of 2^128. Is makes clear security promises, and also has a clear story around initialization.
Performance
HC-128 is an 32-bit algorithm. It performs usually 30% faster than the 32-bit ISAAC, and mostly the same as the 64-bit ISAAC-64. Only for
fill_bytesISAAC-64 is about 45% faster. Note that this makes it still as fast as our implementation until a week ago.The results here may improve a little bit, because I have not been able yet to have to compiler optimise out all bounds checks. It now does one per
u32.x86 (all numbers in Mb/s):
x86_64 (all numbers in Mb/s):
For the time it takes to initialise I don't yet have good numbers. With the unoptimised routine from hc128 it takes about as much time as ISAAC-64. It can probably be improved by ~30%.
Memory
ISAAC uses two arrays: one to hold 256 state words, and one to hold 256 results. HC-128 needs two arrays of 512 words to hold its state. As an optimisation we include a 16-word array of results.
Memory usage (excl. counters etc.):
Overall HC-128 seems like a clear improvement over ISAAC. For ISAAC it is not really clear what its place is in the world. HC-128 is a super-fast cryptographic PRNG that works similar.