Log in

View Full Version : finding out the algorithm used


ndog
March 29th, 2006, 22:12
I feel as if I dont belong here however this is the newbie thing I have been looking for and any help would be appreciated. Cheers.

I work at a net cafe and we have a wireless acess point for people with laptops and we issue them with tickets that have got a 6 digit algorithim, they go to a local site put that number in and then they get acess.

What I am trying to do is not crack or reverse engineer, i am simply trying to figure out the algorithm that is used. Since I have no idea what this is technically called searching google for terms "create own key gen" "reverse algorithm" etc etc proved unfruitful, but lead to this forum, so I hope someone out there could help me out.

All I need is a bit of help or redirection to help/forums/scripts/tools that can take 2-3 or more known values (input) and then figure out the algorithm and create a key generator (output). Pretty simple I know, pretty hard to find!

Thanks for reading this

btw the inputs i already have are:
818565
458371
179386

LLXX
March 29th, 2006, 22:25
You should take a look at whatever program generates those numbers.

naides
March 29th, 2006, 22:37
Note of caution:

There may not be an algorithm.
Let me explain.
The program generates a random, 6 digit valid code, and stores it an a data base as valid.
The user keys in the code, if it is in the data base is valid, and allows it to connect. If it is not in the good boy list it denies it.
So there may not be any hidden information or validate feature in the 6 digit key.

I learned this from a car washing service.

Woodmann
March 29th, 2006, 23:08
Quote:
I learned this from a car washing service.


I thought I was the only "lower level" butcher .

Get a laptop and try some of the numbers you have found. I am willing to bet that the "login numbers" are a set group.

Regards, Woodmann

SiGiNT
March 30th, 2006, 02:23
I knew I should have kept all those numbers, but I think I'll only try it at a station that has the wash booth out of site from the clerk. - BTW - if there is an algo. you would need somewhere in the area of at least 60 numbers to analyze, just a WAG.

SiGiNT

disavowed
March 30th, 2006, 10:27
Quote:
[Originally Posted by sigint33]if there is an algo. you would need somewhere in the area of at least 60 numbers to analyze, just a WAG.

sigint33, could you explain this more please?

SiGiNT
March 30th, 2006, 11:11
It was just a thought, working backwards to find an algo without some sort of seed info would be nearly impossible unless, you had a very large sampling and could find a trend.

SiGiNT

Admiral
March 30th, 2006, 11:26
ndog
Don't worry about being out of place. Everybody's welcome here.

I hate to say it, but your task (as it stands) is probably impossible. I'm guessing that these keys only work once (and of course, have a nonzero shelf-life). If that's the case, then there is no single analytic or algorithmic function that will do the trick. Though it is possible that there is one algorithm responsible for veryfying that the given key is valid and another that checks that it hasn't been used before. If that's the case, then at least you have somewhere to start from.

The unviersal algorithm finder that you speak of, I'm afraid, doesn't and never will exist. Supposing that we're working in the domain of linear functions (which is a tall order in itself), the rank-nullity theorem of linear algebra says that you will need at least one constraint (or working key) for every degree of freedom of your algorithm. Considering we know nothing of the dimension of the problem, you're in some trouble. Two or three working examples are very unlikely to be of much use.
Perhaps more importantly, there is the concern that the algorithm is nonlinear anyway (it's likely to use modular arithmetic, for example).
I'd be happy to throw more mathematical jargon at you, but the bottom line is that you won't be able to work out the specifics of the function without knowing some of its generals (for example, if it is modular, polynomial, hash etc.) unless you want to try out all 2^900000 ~ 10^270926 possible (first-order-logical) models. And even that assumes that there are no other variables coming into play, like MAC/IP/date/time for example.
Since there is no real way to work out the nature of this algorithm (if it even exists), you have nowhere to start from (unless you want to try your luck on some arbitrary ansatz, which of course isn't recommended).

So without having access to the script/code responsible for checking the keys, a keygen is out of the question. I'm sorry if this disappoints you.
However, you could really have some luck with a brute-force approach:

You say that the keys are always six digits. This gives you a tight constraint 99999 < n < 1000000. So since there are only 900000 possible keys, if you have a fast enough connection you could try, with minimal programming knowledge, writing a basic script to check these out (ideally in an arbitrary order). Supposing that the keys aren't issued and removed on an as-needed basis, this method is guaranteed to yielding some results, eventually.

I approach the problem from a mathematical standpoint. With a little research/social engineering you could whittle down the haystack considerably. Perhaps sombody else on this forum knows how these systems are usually implemented and could give you something tangible to work with, but I'm afraid I'm out of my territory.

Regards
Admiral

ndog
March 30th, 2006, 20:24
Well thanks guys for the advice. I am/was suspicious that the WiFi Internet access ticket is using a database, however we have more algorithims than just that one (eg tickets for gaming, tickets for phone time) which dont require a database check, thats why I was hoping for a straight linear (i think) reverse key finder generator (what ever your call it). Anyway if its not possible, I will look into brute forcing, however it may give you guys something to think about,

I am sure someone has designed something like this before eg keygens for gaming, although I know its a hell of a lot different and you get to reverse engineer the game which is a good source of information

PS I dont have access to the programs which create the algorithims, i just print them - doh!

Thanks again

Woodmann
March 30th, 2006, 22:21
Howdy,

I am sticking by my guns

I believe they have a set number of 6 digit access numbers.
100001-100060 for instance.
If you look at the logistics of generating random numbers, I think you will see that it would be too much for the type of setting you are trying to analyze.
(it would be overkill)

With that being said, I could of course be completely wrong .
You may all call me an asshole for suggesting such a thing BUT,
given the fact that where I live, it takes no effort to find a wifi network.

Woodmann

LLXX
March 30th, 2006, 22:43
Even though, as Admiral explained, there are *many* possible algorithms that can generate those keys, in practice the humam mind is rather less creative in such situations and there seems to be a small set of algorithms that are constantly reused with minor changes. These include:

- Sum of digits (not applicable here)
- Sum of digits mod n (not applicable here either)
- Interleaved sums
- Interleaved sums mod n
- Congruent to m (mod n) - this is a common algorithm... finding m and n are easy given a large enough dataset.

On several occasions I've "guessed" an algorithm of a protection scheme to be one of the above, simply by finding as many valid codes as I could from the Internet and inspecting them mathematically.

SiGiNT
March 31st, 2006, 01:24
Quote:
[Originally Posted by LLXX]

- Sum of digits (not applicable here)
-easy given a large enough dataset.
On several occasions I've "guessed" an algorithm of a protection scheme to be one of the above, simply by finding as many valid codes as I could from the Internet and inspecting them mathematically.


I rest my case on needing a largerer dataset, however - I'm not so sure that the sum of the digits can be totally discounted - it ranges from 28-34 with the 3 numbers given, in a 6 digit code - you could try 647345 - just athought (and probably dead wrong).

SiGiNT

Admiral
March 31st, 2006, 07:47
Quote:
[Originally Posted by LLXX]- Congruent to m (mod n) - this is a common algorithm... finding m and n are easy given a large enough dataset.

Indeed, such modular arithmetic is a very popular method of key validation. However, of the similar schemes I have seen recently, I can't think of one that didn't use exponentiation.
If I were to guess, I'd say the system uses something aong the lines of

Key^ConstExponent == ConstCongruence (mod ConstModulus)

But like I said, making arbitrary guesses isn't going to get anybody anywhere.

Regards
Admiral