Skip to main content
Cryptography

Return to Question

Secure generators don't take more than a second to complete, they are faster than a delay. The real issue is the cpu usage.
Source Link
edit approved Jun 5, 2017 at 8:53
Community Bot
edit approved Jun 5, 2017 at 8:53
Community Bot
  • 1

I want to use randomized algorithms (quicksort, ect...) on a server, but secure pseudorandom generators are slowuse a lot of cpu time. But if I use a non-secure one, and the clients figure out the seed, they will be able to force a worst-case scenario. However, the users are never given the seed or output of the generator. The only way I think they can break this is by timing attacks. Will it help if I impose a delay on randomized algorithms e.g. they will be forced to run for 1 second, and if they finish earlier, just wait until 1 second passes? Also, I can reseed it with a cryptographically generated seed every now and then.

I want to use randomized algorithms (quicksort, ect...) on a server, but secure pseudorandom generators are slow. But if I use a non-secure one, and the clients figure out the seed, they will be able to force a worst-case scenario. However, the users are never given the seed or output of the generator. The only way I think they can break this is by timing attacks. Will it help if I impose a delay on randomized algorithms e.g. they will be forced to run for 1 second, and if they finish earlier, just wait until 1 second passes? Also, I can reseed it with a cryptographically generated seed every now and then.

I want to use randomized algorithms (quicksort, ect...) on a server, but secure pseudorandom generators use a lot of cpu time. But if I use a non-secure one, and the clients figure out the seed, they will be able to force a worst-case scenario. However, the users are never given the seed or output of the generator. The only way I think they can break this is by timing attacks. Will it help if I impose a delay on randomized algorithms e.g. they will be forced to run for 1 second, and if they finish earlier, just wait until 1 second passes? Also, I can reseed it with a cryptographically generated seed every now and then.

Source Link
Hantum
Hantum
  • 31
  • 1

Using a non cryptographic PRNG for randomized algorithms

I want to use randomized algorithms (quicksort, ect...) on a server, but secure pseudorandom generators are slow. But if I use a non-secure one, and the clients figure out the seed, they will be able to force a worst-case scenario. However, the users are never given the seed or output of the generator. The only way I think they can break this is by timing attacks. Will it help if I impose a delay on randomized algorithms e.g. they will be forced to run for 1 second, and if they finish earlier, just wait until 1 second passes? Also, I can reseed it with a cryptographically generated seed every now and then.