CODEWITHSUNDEEP
javascriptalgorithmcryptography
Cory Harper
Cory Harper

Reputation: 1055

Best approaches to use to guess a a string of a certain length under certain conditions

I have been working on a recreational code challenge wherein I need to successfully generate a string of numbers (32 characters in length, numbers 0-9, able to repeat) that matches to a value that is otherwise unknown to me. At first I built a brute force solution, but not only was it basically impossible with something like 10^32 possibilities to make any meaningful guesses, there are time constraints (12 second) and multiple tests to pass within that time span (10 tests with different passcodes each).

Are there specific approaches I can research that might actually be able to solve this problem?

Here was my original bruteforce solution, but I've pretty much discarded the idea of using a brute-force solution:

const carryRemainder = (code, index = 31) => {
  if (code[index] === "9") {
    return index === 0 ? carryRemainder(code, 31) : carryRemainder(code, index - 1);
  }
  
  const newCode = `${code.slice(0, index)}${Number(code[index]) + 1}${"0".repeat(31 - index)}`;
  
  return newCode;
}

function crack(login) {
  let code = '00000000000000000000000000000000';
  
  while (!login(code)) {
    code = carryRemainder(code);
  }
  
  return code;
}

Challenge in question:

https://www.codewars.com/kata/59ae7edbba7b60c17500006e/train/javascript

Upvotes: 0

Views: 193

Answers (1)

trincot
trincot

Reputation: 350770

Brute force is not a viable solution: 1032 is more than there are atoms in the human body.

One information you could use is this: how much time does it take the blackbox verifier to tell you whether the guess was right or wrong?

If that verifier is not so well designed, it could look like this:

for (let i = 0; i < 32; i++) {
    if (secret[i] != guess[i]) return false;
}
return true;

This may look like a very obvious implementation (in that blackbox), but it has a vulnerability: the more characters are correct (as a prefix), the more iterations it will perform. So this gives a hacker some information.

They could time the execution and see if there is on average a tiny tiny longer execution for one particular first character. If with many runs it becomes clear that one character stands out, they can assume it is correct, and repeat the same process with the second character, and so on. This is one variant of a side-channel attack.

As execution times always have a variable component, due to other things happening on the computer, dynamic execution optimisations (typical for JavaScript engines), garbage collection, ...etc, it is important to run enough samples before jumping to conclusions, but it certainly is the way to do it when the blackbox implementation is designed like above.

Upvotes: 3

Related Questions