2

I'm writing a level for a game in which the player has an advantage if they know a password. I want it to be infeasible to find the password from looking at the level's source code.

The problem is that the language's levels are written in an ad-hoc scripting language without any crypto libraries, so I have to implement everything myself.

Also, inputting passwords within the game is a little awkward, so I'd like the password to be no larger than a random 64-bit integer, which should provide enough entropy to avoid a brute-force attack.

One possibility I've considered is to store a large semiprime and have the password be one of its factors. Validation is very easy to implement, but semiprimes need to have factors much larger than 64 bits to be secure. I've considered storing the first 448 bits of a 512-bit factor and have the password be the remaining 64 bits, but I have no idea if this is secure.

Another possibility is to implement SHA-256 and store the password's hash. This would of course be much harder to implement.

So my questions are:

  • If a 1024-bit semiprime is stored along with the first 448 bits of one of its factors, can the remaining 64 bits of that factor be feasibly found?

  • Is there another easy-to-implement but hard-to-crack password validation scheme I could use?

cardboard_box
  • 123
  • 4
  • How secure does it need to be? ROT16 may be enough to deter a casual attacker. (or any other number besides 13, because they'll still guess that) – user253751 Aug 11 '16 at 07:07
  • @immibis The reason for making this level is that I'm going to submit it to a tournament where players can submit their own. I want to give myself an advantage by hiding a password in it. Last year's tournament I did the same thing, but the crypto I used wasn't strong, and another competitor had a friend who is a grad student studying cryptography, and he cracked it. So ideally I'd like it to be secure against cryptographers, hence looking into SHA-256 and large semiprimes. – cardboard_box Aug 11 '16 at 16:38

2 Answers2

3

The problem with the method that you have suggested is that it is basically a partial-key exposure of RSA. You are exposing some bits of a factor of a semiprime. Dan Boneh's survey on RSA attacks lists a theorem from Coppersmith that states that if the n/4 least significant or most significant bits of a factor of N are known, then N can be factored efficiently. Since you want to leak way more than n/4, I think your method would be susceptible to that attack.

The good news is, Boneh gives some insight into something that might work:

It is interesting that discrete log-based cryptosystems, such as the ElGamal public key system, do not seem susceptible to partial key exposure. Indeed, if g^x mod p and a constant fraction of the bits of x are given, there is no known polynomial-time algorithm to compute the rest of x.

So, you could pick some random x, a large prime (1024 bits) p, and a generator g (in practice I'd use some standard NIST values for P and g). Compute g^x mod p, store that in your software. Store some number of bits of x in your program. The user must supply the remaining bits of x. Call their bits plus the stored bits x'. You compute g^x' mod p and see if that matches with what you had stored.

I believe that the statement from Boneh has not changed since it was published. That maybe something you want to ask on Crypto.SE, along with recommendations of how many bits should be left out of the source code.

mikeazo
  • 2,827
  • 12
  • 29
  • In practice, a real attacker would just disable the check in the code to bypass it, but that isn't the type of attack you are looking at. – mikeazo Aug 11 '16 at 17:57
  • Thanks, this should be pretty easy to implement. And yes, that kind of attack will allow people to figure out what happens when you enter the correct password, but won't allow them to cause that to happen during the tournament. – cardboard_box Aug 11 '16 at 18:01
  • It seems that exposing all but `n` bits of a secret key is only as good as having an `n`-bit secret key to begin with - if the secret part of the key is `s` and the exposed part of the key is `e`, then the concatenated key is `x = 2^n * e + s`. An attacker has `g^x` and `e` so they can compute `(g^x) * (g^(2^n * e))^-1 = g^s`, and the problem is reduced to finding the discrete log of `s`. – cardboard_box Aug 12 '16 at 18:04
  • Come to think of it, the attack described by Boneh could be used to validate the key - have the user input 1/4 of the key and perform the described attack to find and validate the rest of the key. Though this system is probably more complicated to implement than a commonly used hash function. – cardboard_box Aug 12 '16 at 22:41
-1

I don't know if any game does not require internet connections now, why not use a server to do the authentication?

No matter how you encrypt the password, as long as it is saved somewhere on the client, it can be broken. Especially after the algorithm you designed is leaked or cracked, the authentication will pretty much become useless.

user3894299
  • 7
  • 2
  • 1
    I gather it's not supposed to be unbreakable, just enough to deter people from casually reading the source code for the password. (Even if it *was* unbreakable, someone would just post the password on the Internet anyway!) – user253751 Aug 11 '16 at 03:54
  • 5
    And -1 for the suggestion to make the game require Internet access just for this one trivial thing. – user253751 Aug 11 '16 at 03:55
  • The game does not require internet access and it's not possible to access the internet through the level's scripting language. – cardboard_box Aug 11 '16 at 06:42
  • Also, regarding your 2nd paragraph, if I were to store a 1024-bit semiprime and have the password be a 512-bit factor of it, it would be uncrackable by today's standards even if the attacker has access to the source code (the largest RSA number to be cracked is 729 bits). So yes, if the algorithm is leaked it still can be secure. – cardboard_box Aug 11 '16 at 06:47
  • I got a couple of questions: Let's say you want to use 2 prime numbers to verify, P x F = S, where P is the user's input, F is the other prime, and S is the product (your 1024-bit prime number): 1. where do you hide F? 2. how do you prevent different player sharing the password? - unless you are implementing something like ""Sesame, Open". – user3894299 Aug 11 '16 at 14:33
  • @user3894299 You don't need to store F, you store S, user inputs P, then you check if S is divisible by P (you can even obtain F by dividing S / P). As for preventing password sharing, I intend to be the only person who knows the password (until I use it during a tournament in which the level will be included - competitors can submit their own). – cardboard_box Aug 11 '16 at 16:36