1
$\begingroup$

Basically I need a function with the following interface:

getRandomBytes(uint128 seed, uint64 state, uint16 byteCount)

Consecutive calls with the same seed and state must give the same results.

What algorithm should I look at?

$\endgroup$
9
  • 2
    $\begingroup$ Perhaps a stream cipher with nonce support (e.g. AES-CTR, Salsa20, ChaCha, or any eStream contestant)? Or if the output size is limited, a hash should work as well. $\endgroup$ Jul 24 '16 at 14:10
  • $\begingroup$ What is the difference between seed and state? Do you need to also be able to get the current state? $\endgroup$
    – otus
    Jul 24 '16 at 15:00
  • $\begingroup$ @otus Ah, now I see, yes, I guess you should take the seed and state together. Do you need a 64 bit state, or can more information be transmitted? $\endgroup$
    – Maarten Bodewes
    Jul 24 '16 at 15:09
  • $\begingroup$ @MaartenBodewes Yeah, you're right, I should concatenate them. "State" is basically coordinates. The function is used to generate random world content. Same coordinates = same content. Changing the seed should change the whole world. $\endgroup$ Jul 24 '16 at 16:47
  • $\begingroup$ @alain_morel: Maybe you can just use a decent keyed hash function to map unique inputs to pseudo-random values. SipHash may work here, but if security is not a requirement I bet even a non-cryptographic hash like MurmurHash would work. This blog entry and this one I just found on Google are illustrative. $\endgroup$ Jul 26 '16 at 21:54
6
$\begingroup$

Probably the easiest one with regards to the protocol is a XOF, an eXtendable Output Function. Two have been defined as part of SHA-3, called SHAKE-128 and SHAKE-256. These have a single input of any length, and can output as many bytes as required.

Of course SHA-3 is relatively new, so not all runtimes / API's may support the SHAKE variants out of the box.


In your case you would feed it the 128 bit seed concatenated with the 64 bit state. There should be no need for two separate variables.

$\endgroup$
4
$\begingroup$

A stream cipher may do the trick; you'd use your "seed" as key and your "state" as nonce, and just output a prefix of the keystream. Currently popular ones are AES in CTR mode and ChaCha20.

$\endgroup$
1
  • 3
    $\begingroup$ Note that most stream ciphers are designed to be used with random keys. So if your seeds aren't random, you might need to hash them first. $\endgroup$ Jul 24 '16 at 14:21
4
$\begingroup$

This has been said by others, but I wanted to stress it more. The input sizes you are looking at all fit into AES with the (random) seed as the key and the "state" together with a counter $i$ that goes from $0$ and up to $\frac{\rm byteCount}{16}$ concatenated as the input (with additional fixed zeroes). AES is assumed to behave as a pseudorandom permutation and so this will give you a very high quality pseudorandom string each time.

AES is also much faster than using something like SHA-3. However, I want to stress that although SHA-3 and in fact all cryptographic hash functions are designed to have "random looking behavior" this is not their main design principle. They are designed to first and foremost be collision resistant, and then to behave "randomly" as a secondary design principle. In contrast, block ciphers are designed to behave pseudorandomly. As such, they are the preferred primitive of choice in these cases. Note that I am not saying that you cannot use a hash function for such purposes. However, I would typically go for it only when there's a reason not to use something like AES. In this specific case, there is no reasons (and it would be even faster).

Finally, regarding AES vs something like ChaCha20: again, being conservative, AES has undergone much more cryptanalytic scrutiny than ChaCha20 so I prefer it. If you have AES-NI hardware support then it's also well fast enough. If not, and speed is very critical then you may wish to consider something like ChaCha20.

$\endgroup$
4
  • $\begingroup$ Thanks for detailed explanation. I tried AES and it's really much faster than SHAKE. $\endgroup$ Jul 26 '16 at 15:21
  • $\begingroup$ @alain_morel Current Oracle Java and OpenJDK's use AES-NI to speed things up (and the bytecode has been optimized a lot too) so that AES is faster than SHAKE is not really a surprise. Keccak needs more attention and hardware support to get to the same level. In principle the amount of passes = 1 in both cases. $\endgroup$
    – Maarten Bodewes
    Jul 26 '16 at 15:53
  • $\begingroup$ @MaartenBodewes Thanks for information. At first I chose SHAKE because it looked simplier. But after some reading I made AES work (providing predefined initialization vector), and the speed difference is huge. $\endgroup$ Jul 26 '16 at 16:06
  • $\begingroup$ After more testing it appears that the output of processing 2 similar inputs (i.e. 1 bit difference) differs very little, not by 50%. Is it intended or I'm doing something wrong? $\endgroup$ Jul 26 '16 at 19:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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