0
$\begingroup$

I've wrote following C# method that basically takes 3 seeds and gives you number in 0-100 range. I then use that number for variety of purposes but for this question the most important one is the ability of clients to see server and supply client value. Here is the method:

// random sha512
private const decimal DIVIDER = (uint.MaxValue - 1)/100M;
public static decimal Random0To100(string secret, string server, string client)
{
    // add 3 strings together, calculate SHA512 hash
    var str = secret + server + client;
    var byt = Encoding.ASCII.GetBytes(str);
    byte[] hashByte = null;
    using (SHA512 shaM = new SHA512Managed())
    {
        hashByte = shaM.ComputeHash(byt);
    }

    // convert hash into hexadecimal string
    var hexHash = BitConverter.ToString(hashByte).Replace("-", "");

    // get unsigned 32 integer from first 8 chars of hash
    var hex8 = hexHash.Substring(0, 8);
    uint l = Convert.ToUInt32(hex8, 16);

    // get number between 0 and 100 from hash with 2 decimals
    var num = l / DIVIDER;
    var fin = Math.Round(num, 2);

    // return result, like 71.28
    return fin;
}

Secret seed is 512 bit value sent in as a string.

The thing I am curious about is if it's possible for end-user to guess secret seed if he is given ability to supply BOTH server & client values (and see the 0-100 output obviously) for extended period of time (say the time is 24 hours and the only restriction I impose is that those server/client are at least 10 char long when added TOGETHER).

If you deem that it is theoretically possible to guess secret, please advise as to what I can do without changing the algorithm too much. I was thinking about variety of things:

  1. Increase seed size (1024, 2048... etc)
  2. Increase range from uint (32bit), to ulong (64bit)
  3. Enforce stronger requirements for server/client strings

Basically, I just want to make sure that it's not possible for someone to guess seed or random number while still providing users with ability to supply both server & client values (obviously for server value I'll re-generate it on server on user request, not allow him to supply it directly).

Because of high number of comments (most of which point to unrelated things), let me try to clarify the question. In a nutshell what I am trying to do is generate a random number that users can later verify was not fixed/influenced in any way by me. So, I will generate secret seed using RNGCryptoServiceProvider and it'll be say 512 chars long. Then I'll give ability to clients to generate 10 numbers for raffle (they can request generation of new server seed for each request they send in, plus send arbitrary string as a client seed). After those 10 numbers I'll generate new secret seed, publish old one so they see nothing influenced by me and so on...

So, I am:

  • NOT trying invent new crypto standard
  • NOT trying to generate true random numbers

I am building a method that takes in a string (secret+server+client seed) and produces number from 0.00 to 100.00. And the only thing I was wondering was whether or not somebody can guess secret string if he is able to get enough numbers back from that method (+ he sees server string and can send arbitrary client string). That's all. No homebrew crypto. No true random.

So, if anyone with computer science knowledge can confirm that what I am doing in algorithm is not prone to attack (user can guess secret seed after sending server/client seeds and getting several values back), or suggest a better way and post code that explains it - I would be extremely grateful. Otherwise, if you can only talk about theory and post unrelated links, I beg you to please just leave the question alone and not pollute it. Thanks.

To show in practice, these are 5 random numbers along with server/client seeds (server = server seed, c = client seed, number = generated number from that method; server and client seeds are short on purpose).

server C Number
k23op 0 96.40
gfsqu 1 22.07
n0dpd 2 91.62
ds02d 3 48.25
hf03d 4 55.26

Let me know if you can guess the secret seed. If you need more computing power, send me algorithm you are trying to execute, I'll review it and put it to run on multiple servers.

$\endgroup$
11
  • 1
    $\begingroup$ Please don't try and create your own CSPRNG. Use an existing off-the-shelf one, like RNGCryptoServiceProvider. $\endgroup$ Mar 31, 2014 at 20:35
  • $\begingroup$ @StephenTouset Sorry man - need to do it this way as I need to provide users with ability to later verify that random number generated was truly "random" (not fixed as needed by the system)... when I provide them with secret seed like 24 hours later. That being said - obviously for generating secret seed I'll use something like RNGCryptoServiceProvider - thanks for linking it. $\endgroup$
    – nikib3ro
    Mar 31, 2014 at 20:38
  • $\begingroup$ possible duplicate of A simple block cipher based on the SHA-256 hash function, which in itself already represented a duplicate of Is it feasible to build a stream cipher from a cryptographic hash function?. (Tip: You might want to check the answers there, as they’ll provide ample insights related to your question.) $\endgroup$
    – e-sushi
    Mar 31, 2014 at 20:45
  • $\begingroup$ You are incorrect; you don't need to do it this way (which seems problematic; trivially, you're dividing $2^{32}$ possible values into 100 buckets, and this cannot happen with equal probability). Your requirements seem to be that the RNG is deterministic (based on a seed) and unpredictable (without the seed). $\endgroup$ Mar 31, 2014 at 20:58
  • 1
    $\begingroup$ @e-sushi Also: correct way to map random number to defined range? $\endgroup$ Mar 31, 2014 at 21:00

3 Answers 3

2
$\begingroup$

With your clarification edits it is clear what you are looking for.

Generated Value = SHA512(A || B || C)
Where A = 512 bit secret
Where B = x bits server seed and can be attacker chosen
Where C = x bits client seed and can be attacker chosen

The thing I am curious about is if it's possible for end-user to guess secret seed if he is given ability to supply BOTH server & client values (and see the 0-100 output obviously) for extended period of time (say the time is 24 hours and the only restriction I impose is that those server/client are at least 10 char long when added TOGETHER).

If you are using SHA-512, and you are using a 512-bit secret with at least half entropy, then no, it should be impossible for them to determine the secret seed. This is a brute force attack on a 512-bit hash function with 512-bits of unknown input, the amount of computing power to do this in 24 hours (or 24 years) does not currently exist on this planet. You should be able to generate billions of outputs with this secret and stay safe.

The same logic follows with being able to guess outputs without the secret. Although the size of your output is a concern here, the output of the hash will be impossible to predict if an attacker controls the server and client seeds but has no knowledge of the secret.

I would also suggest that it should be infeasible for an you to generate a list of outputs for all possible client seeds for any given server in advance, for the comfort of the clients. That means having larger server and client seeds, I would say 64 to 128 bits in length.

Your server seeds should be fixed with full entropy and never changed, have them be a unique ID for that server. I would be more comfortable as a client knowing you aren't intentionally manipulating them to match the secret in some way. They could be generated deterministically, such as by using a block cipher in counter mode, and incrementing the counter. Publishing the key used to generate them (such as SHA256("Generating Key")) and the method used is a good idea, proving there was no special way they were generated.

The client seeds should also be large enough that a collision is unlikely to occur. I would suggest publishing a 64-bit user id for each client, and allowing the client to choose and 2nd 64-bit value for their input, and concatenate these to form the client seed.

This gives 3 inputs to the hash, a 512 bit secret, a 128 bit server seed, and a 128 bit client seed. All 3 run through a single iteration of the hash, and then compressed or truncated. If I was a client, and knew how the scheme worked, I would be confident you could not manipulate the outcome, even if you never published the secret. Publishing the secret would allow me to verify that you are in fact using the scheme the way you described.

Of course I would need to know that you did not manipulate the secret after the first client input, this can be done by publishing something to prove what secret you are using but does not allow knowledge of the secret, such as SHA256(SHA256(Secret)) a la bitcoin proof of work. It would be trivial to publish this before input of client seeds, then once the secret is published, users could verify the secret existed before the first client seed was processed.

The concern I have here is the size of your outputs. A decimal number seems.... small. I would suggest a 32 or 64 bit unsigned integer value, such as the first few hash bytes converted to hexidecimal. If you have some specific reason for having a decimal output with only 10000 possible outputs I would like to hear it. That would make me uncomfortable as a client, unless there is a very good reason for it.

A Stephen said, you should maintain verifiable records of all generated values.

$\endgroup$
3
  • $\begingroup$ Thanks for reviewing algorithm and providing an answer in plain English ;). I love that SHA256(SHA256(secret)) suggestion... and presume you wouldn't mind if I made it SHA512(SHA512(secret+secret_created_at_salt)). As for size of the output - I am only doing it to map it into a "general purpose decision space" for AI. If you review the algorithm you can see that I'm actually extracting first 4 bytes of hash and turning them into uint. Only then I divide it by (2^32-1)/100.00 to map it into smaller space for AI decisions. That said, I'll see if I can log generated uint for player's review. $\endgroup$
    – nikib3ro
    Apr 1, 2014 at 18:44
  • $\begingroup$ Actually SHA256 was there because you are using SHA512 to process the secret later, although the double round should make it safe. A salt is used to prevent identical hash/kdf inputs (like passwords) from generating the same output, it would not be necessary in your case as the secret is large and suitably pseudorandom (and possibly even compared against prior secrets). $\endgroup$ Apr 1, 2014 at 19:16
  • $\begingroup$ OK, I guess I'll then just go with SHA256 twice and not worry too much. I'll see with site owner if after publishing it online I can share link here and give some BTC to you and other people willing to review what we are doing so that it's obvious game is fair. Thanks again for all your suggestions. $\endgroup$
    – nikib3ro
    Apr 1, 2014 at 20:02
3
$\begingroup$

generate a random number that users can later verify was not fixed/influenced in any way by me.

There's no way to do that on your own. But you can ask users to contribute to the seed, eg.

  • Generate a seed $s$
  • Commit to $s$ and send commitment to the user
  • User generates his own seed, $s'$ and sends it to you
  • Combine (eg. XOR) the two seeds together. As long as at least one is random, neither can influence the outcome in a statistically signifcant way

  • Commence with the protocol as usual

  • Send $s$ and assorted info to the user

At the end the user is able to reconstruct the random stream.

If you don't want or can't have the users generating seeds, you can always assign this task to a trusted third party.

$\endgroup$
2
$\begingroup$

By inventing your own random number generator, you are chasing a red herring. There is no need whatsoever for you to invent your own RNG. Combining cryptographic primitives on your own is exceedingly dangerous, and worse, there's no actual need to do so.

Unfortunately, if you are only choosing 10 numbers between 1-100, there are only $100^{10}$ possible orderings. No amount of combining values from clients will save you from the fact that this is on the edge of brute-forceability for your purposes. You want to prove that you didn't manipulate the results by publishing a value after the fact, but there is no way to demonstrate you haven't simply brute-forced your way through possible seeds to reach an outcome that is favorable to you (e.g., as few winners as possible).

What you appear to need is a commitment scheme. Before your users submit entries to a particular raffle, you should publish some value that strongly commits you to a particular seed but from which the seed cannot be determined. If you generate a seed $s$ and publish $\mathrm{H}(s)$ where $H$ is something like SHA-256, it would be exceedingly difficult for you to later influence the results by finding some new seed $s'$ such that $\mathrm{H}(s) = \mathrm{H}(s')$.

However, there's one small catch. If raffle entries aren't evenly distributed, it still is possible for you to analyze their distribution and come up with seeds that, on average, reduce your payouts. So you will also likely need to publish historical seeds and distributions of winning numbers to prove that you aren't cheating.

$\endgroup$
10
  • $\begingroup$ I appreciate the time and help, but you are obviously not understanding what I'm trying to do. I mentioned raffle as an example - I am not trying to do raffle. And again I am NOT building my own random number generator for purposes of generating true random numbers. I am building a method that takes in a string (secret+server+client seed) and produces number from 0.00 to 100.00. And the only thing I was wondering was whether or not somebody can guess secret string if he is able to get enough numbers back from that method. That's all. No homebrew crypto. No true random. I'll give upvote anyway. $\endgroup$
    – nikib3ro
    Apr 1, 2014 at 0:46
  • 1
    $\begingroup$ You've also said in multiple places that you want to prove that you haven't manipulated the RNG results. Since you're only generating numbers between 1 and 100, that's quite difficult. Just as an example, it took me less than one second to find a random seed in Ruby that resulted in the "random" numbers 1, 2, 3, out of a max of 100. Without some kind of commitment scheme, users simply cannot be assured that you haven't manipulated the results. $\endgroup$ Apr 1, 2014 at 1:19
  • $\begingroup$ If your requirement is not to leak the PRNG seed, then you must use a CSPRNG. Use an existing one, and not one your own invention. If you have an additional requirement that your seeds must be shown to have been chosen in such a way that the results were not manipulated, then use a commitment scheme such as described above and publish your commitment in advance. $\endgroup$ Apr 1, 2014 at 1:20
  • $\begingroup$ It will be easy for users to confirm I haven't manipulated numbers. As soon as I can publish secret seed, they can use it with that method I've posted (also public) to verify numbers (they already have server/client seeds). As for you finding a random seed that results in 1, 2, 3 in Ruby's Random - that's completely unrelated. I've posted example with concrete numbers, see if you can figure out seed in that case. $\endgroup$
    – nikib3ro
    Apr 1, 2014 at 2:20
  • 1
    $\begingroup$ @kape123 : $\;\;\;$ Using it with the method you've posted to verify numbers does not confirm that you haven't manipulated numbers. $\:$ For example, you could choose secret seed after seeing the first client string to make the first generated number be essentially whatever you want. $\:$ By considering the result of fixing a search algorithm's randomness to its optimal value, one can see that, even after choosing all 10 server and client values and seeing their results, the probability of guessing the secret seed is at most (10001^10)/(2^512). $\;\;\;\;\;\;$ $\endgroup$
    – user991
    Apr 1, 2014 at 3:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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