3

I'm trying to figure out a secure method to generate a rng seed to a rng using a small pin number that is 5 digits.

The issue that i can see with this is an attacker could very easily just loop through all possible 5 digit numbers and eventually determine the seed.

I apologize if this is a very basic and naive question. Just trying to get some thoughts about it

EDIT

I want to be able to seed the random number generate with input that can be remembered because i want a user to be able to go to a different computer and have the same output from the rng.

CBaker
  • 219
  • 2
  • 7
  • 1
    Um...yes? 5 digits is probably not enough entropy for secure random number generation. Why do you think you need to use a 5-digit PIN for this, exactly? – Ben Feb 18 '16 at 21:02
  • i want the user to be able to enter input to the system that is used as a seed. I just used a pin as an example because its something that can be remember. A 128 bit key doesn't seem realistic. – CBaker Feb 18 '16 at 21:16
  • 1
    @CBaker I think that you will probably get better answers if you explain *why* you want to seed a rng with rememberable user input. There may be better solutions to your problem. – tim Feb 18 '16 at 21:36
  • That makes sense, i updated the question – CBaker Feb 18 '16 at 22:03
  • 2
    You cannot reasonably have a secure RNG with only 100,000 potential seed values. – Xander Feb 18 '16 at 23:13

2 Answers2

4

If the user can go to a different computer, then so can the attacker. What differentiates the attacker from the normal user is only the knowledge of the 5-digit PIN.

Computers are deterministic systems, which means that the attacker can conceptually own 100000 computers; on computer 0, he runs your key derivation function over PIN 00000; on computer 1, he runs the function with PIN 00001; and so on. One of these computers will necessarily use the true user PIN, and produce the same "RNG seed" as the attacked user.

This kind of simulation is highly flexible. Generally speaking, if the user needs to invest X resources into using your system (say, it takes one second of computation on a normal computer), then the attacker can simulate all the virtual users with 100000*X resources. This can be by using 100000 computers and be done within one second; or by reusing one computer again and again, and thus taking 100000 seconds to iterate through all possible user PIN (that's a bit less than 28 hours). Or any combination in between (e.g. 10 computers running for 3 hours).

You have only two ways out of this conundrum, neither of which really solving your problem:

  1. You can try to arrange for the derivation from PIN to RNG seed to take a lot of resources. This is basically the approach of password hashing. The main problem here is that the user is not patient, and won't use your system if it takes 20 seconds to process the PIN (for card payment systems, it has been measured that the whole process must be done within 8 seconds, otherwise the consumer goes berserk). The attacker, on the other hand, has a lot more patience, often has more powerful computers that can go faster than the average user's hardware (especially if we are talking about smartphones), and can in general muster a lot of them (if only by renting machines in some cloud like Amazon's).

  2. In some very rare contexts, you can arrange for making it impossible to test for a good PIN. In the exhaustive search attack, the attacker tries all possible PIN and stops when he finds the one that "works". If a bad PIN yields a result that is ultimately as plausible as what you have with the good PIN, then the attack no longer works. But this is very restrictive.

    For example, if the PIN is about protecting (through encryption) the user's files on a smartphone, then the attacker can easily see if the decryption yields files that "make sense", or just random garbage.

So, in practice, what you are trying to achieve won't work with a 5-digit PIN. Since the problem is basically that the attacker is more patient and more powerful than the user, and has comparatively few combinations to try, you need to either make the user more patient (good luck with that), or more powerful (hard to do, since the attacker can buy at least the same kind of machine as the user), or to increase the number of possible combinations. This is known as "password entropy". See this question for some discussion on kinds of passwords that can pack substantially more entropy (in that case, 44 bits, i.e. 244 = 17592186044416 combinations) while remaining easy to remember for a normal human user.

Thomas Pornin
  • 320,799
  • 57
  • 780
  • 949
1

I would suggest that you use PBKDF2 and iterate over the input for e.g. 5000 times. Then use the output as seed for the rng.

This would make it harder to brute-force all PINS and would also work for other inputs such as a password.

Be advised that this is not a good idea for proper (cryptographic) random number generation when you only use 5-digits. It might server it's purpose for simple randomization though.

John
  • 997
  • 5
  • 14
  • 2
    You're still only going to have 10^5 possible seeds though, which is a tiny, tiny space. – Xander Feb 18 '16 at 22:30
  • @Xander yep if you stick with the 5-digits. I wouldn't recommend that, but that is what was asked for. – John Feb 18 '16 at 22:58
  • @Xander It's all about cost. You could setup the work factor on PBKDF2 to something very high that it would take litterally 1 year to generate the random number. Suddenly with that work factor it becomes unpractical to try all the possibilities (or to generate the number...) OP has to determined how long he wants the random number to stay "secure" and set the cost accordingly. – Gudradain Feb 18 '16 at 23:00
  • 2
    @ꓨꓵꓷꓤꓯꓷꓯꓲꓠ Yes, but that isn't the point. The point is that no matter what the cost, with only 100,000 potential seed values, the cost isn't going to be very high, relatively speaking, without making it unusable for the intended users. – Xander Feb 18 '16 at 23:13
  • John, sometimes the best answer is just to say it can't be done. Your answer, starting with a suggestion for how to do it, makes it sound reasonable. – Neil Smithline Feb 19 '16 at 05:57