string generation

[Ken Human]

I want to generate every possible 16 character combination of the
characters 0-9, A-Z, and a-z programatically. My current code follows:

#include <stdio.h>
#include <ctype.h>

int main() {
char strBuf[17] = {0};
int i, j;

for(i = 0; i < 16; i++) {
for(j = '0'; j <= 'z'; j++) {
if(!isalnum(j)) continue;
strBuf = j;
printf("%s\n", strBuf);
}
}

return 0;
}

Only the last character increments. I understand my problem and I can
fix it with a for loop for each space in the array, but I'd like to know
if there's a better solution.

 

[Chris McDonald]

I want to generate every possible 16 character combination of the
characters 0-9, A-Z, and a-z programatically. My current code follows:

Really, every one?
And on what computer are you hoping to run this?

 

[Martin Ambuhl]

I want to generate every possible 16 character combination of the
characters 0-9, A-Z, and a-z programatically.

Are you sure? That's pow(62,16), which is a lot of combinations.
About 4.8e28, I think.

My current code follows:

#include <stdio.h>
#include <ctype.h>

int main() {
char strBuf[17] = {0};
int i, j;

for(i = 0; i < 16; i++) {
for(j = '0'; j <= 'z'; j++) {
if(!isalnum(j)) continue;
strBuf = j;
printf("%s\n", strBuf);
}
}

return 0;
}

Only the last character increments. I understand my problem and I can
fix it with a for loop for each space in the array, but I'd like to know
if there's a better solution.

untested code block:
{
char foo[]="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
"abcdefghijklmnopqrstuvwxyz";
unsigned nfoos = sizeof foo/sizeof *foo;
unsigned ndx[16] = {0}, i;
while(ndx[15] != nfoos)
{
for (i = 0; i < 16; i++) putchar(foo[ndx]);
putchar('\n');
for(i = 0; i < 16; i++)
{
ndx++;
if (ndx < nfoos) break;
ndx = 0;
}
}
}

 

[Ken Human]

Really, every one?
And on what computer are you hoping to run this?

I was never very good at math, is the number of possible combinations
62^16? Thank you for your concern. I'm running it on the Plasmo Mag-8,
which can calculate this exact amount of data in 1 second. Needless to
say, it also has an unlimited amount of memory.

Let's say that I want a 4 character combination.

 

[Ken Human]

I want to generate every possible 16 character combination of the
characters 0-9, A-Z, and a-z programatically.

Are you sure? That's pow(62,16), which is a lot of combinations.
About 4.8e28, I think.
[...]

untested code block:
{
char foo[]="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
"abcdefghijklmnopqrstuvwxyz";
unsigned nfoos = sizeof foo/sizeof *foo;
unsigned ndx[16] = {0}, i;
while(ndx[15] != nfoos)
{
for (i = 0; i < 16; i++) putchar(foo[ndx]);
putchar('\n');
for(i = 0; i < 16; i++)
{
ndx++;
if (ndx < nfoos) break;
ndx = 0;
}
}
}

Thanks, Martin. That was what I was looking for.

 

[Walter Roberson]

I want to generate every possible 16 character combination of the
characters 0-9, A-Z, and a-z programatically.

Are you sure????

That's 62 symbols, and you want 16 of them, so that's pow(62,16)
combinations, which is 47672401706823533450263330816
If you are able to generate them at the rate of 1 GHz
then even presuming you have storage system able to handle
17 gigabyte/second, it would take 1.5E12 years.

At a 1 GHz production rate, you could get through 8 positions
worth in just over a day... and that alone would require over 1.3
petabytes of storage.

My current code follows:

#include <stdio.h>
#include <ctype.h>

int main() {
char strBuf[17] = {0};
int i, j;

for(i = 0; i < 16; i++) {
for(j = '0'; j <= 'z'; j++) {
if(!isalnum(j)) continue;
strBuf = j;
printf("%s\n", strBuf);
}
}
return 0;
}

I would suggest that instead of testing for isalnum, that
you create an array of the valid choices and index it by
the current j (which would range over 0 to the number of choices minus 1
instead of '0' to 'z'). That will save you from the conditional
test at each point.

This won't save you from the problem of only incrementing the
last byte. There are various ways of handling that situation,
but we have to leave you -something- to be inventive over ;-)

 

[Emmanuel Delahaye]

Ken Human wrote on 22/05/05 :

I want to generate every possible 16 character combination of the characters
0-9, A-Z, and a-z programatically. My current code follows:

Really ? It may take hours or days to print them out... Sounds like a
cracking device...

#include <stdio.h>
#include <ctype.h>

int main() {
char strBuf[17] = {0};
int i, j;

for(i = 0; i < 16; i++) {
for(j = '0'; j <= 'z'; j++) {

Don't make assumptions on characters values. It only works with digits.
Use an array of char

static char const

if(!isalnum(j)) continue;
strBuf = j;
printf("%s\n", strBuf);
}
}

return 0;
}

Only the last character increments. I understand my problem and I can fix it
with a for loop for each space in the array, but I'd like to know if there's
a better solution.

You probably want 16 nested loops... or a smart recursive function with
a huge automatic memory...

--
Emmanuel
The C-FAQ: http://www.eskimo.com/~scs/C-faq/faq.html
The C-library: http://www.dinkumware.com/refxc.html

..sig under repair

 

[Emmanuel Delahaye]

Martin Ambuhl wrote on 22/05/05 :

untested code block:
{
char foo[]="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
"abcdefghijklmnopqrstuvwxyz";
unsigned nfoos = sizeof foo/sizeof *foo;
unsigned ndx[16] = {0}, i;
while(ndx[15] != nfoos)
{
for (i = 0; i < 16; i++) putchar(foo[ndx]);
putchar('\n');
for(i = 0; i < 16; i++)
{
ndx++;
if (ndx < nfoos) break;
ndx = 0;
}
}
}

Very smart. A little fix:

#include <stdio.h>

int main (void)
{
static char const foo[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
"abcdefghijklmnopqrstuvwxyz";
unsigned const nfoos = strlen(foo);
#define N 3
unsigned ndx[N] =
{0};

while (ndx[N-1] != nfoos)
{
{
unsigned i;

for (i = 0; i < N; i++)
{
putchar (foo[ndx]);
}
putchar ('\n');
}

{
unsigned i;

for (i = 0; i < N; i++)
{
ndx++;
if (ndx < nfoos)
{
break;
}
ndx = 0;
}
}
}
return 0;
}

--
Emmanuel
The C-FAQ: http://www.eskimo.com/~scs/C-faq/faq.html
The C-library: http://www.dinkumware.com/refxc.html

I once asked an expert COBOL programmer, how to
declare local variables in COBOL, the reply was:
"what is a local variable?"

 

[Martin Ambuhl]

Ken Human wrote:

Thanks, Martin. That was what I was looking for.

Quickly looking back, I see that I have at least an off-by-one error in:

>> char foo[]="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
>> "abcdefghijklmnopqrstuvwxyz";
>> unsigned nfoos = sizeof foo/sizeof *foo;

Other errors may be lurking there as well. That's what happens when I
code on the fly while asleep.

 

[Keith Thompson]

Ken Human wrote on 22/05/05 :

Really ? It may take hours or days to print them out... Sounds like a
cracking device...

Hours or days? You'd better buy a sweater; it's going to get chilly
after the sun burns out (which will happen long before this thing is
finished).

 

[Ken Human]

Ken Human wrote:

Thanks, Martin. That was what I was looking for.

Quickly looking back, I see that I have at least an off-by-one error in:

char foo[]="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
"abcdefghijklmnopqrstuvwxyz";
unsigned nfoos = sizeof foo/sizeof *foo;

Other errors may be lurking there as well. That's what happens when I
code on the fly while asleep.

I caught that, yes. Your idea was a good base to finish what I was
working on, thanks.

 

[Ken Human]

Hours or days? You'd better buy a sweater; it's going to get chilly
after the sun burns out (which will happen long before this thing is
finished).

I'm afraid I worded my post badly. I picked the number 16 as to
demonstrate why a large nested-loop would not look good. It's usually
stopping at 4 - 6 digits and it'll never go past 8 at the moment.

 

[Malcolm]

I was never very good at math, is the number of possible combinations
62^16? Thank you for your concern. I'm running it on the Plasmo Mag-8,
which can calculate this exact amount of data in 1 second. Needless to
say, it also has an unlimited amount of memory.

Wow. Can I have your old Plasmo Mag-8, when you upgrade to the next model?

Let's say that I want a 4 character combination.

Martin Ambuhl's code should work. Just replace the 16 with a 4.

What do you need these 16-character permutations for? I suspect that there
may be a much more efficient way of achieving it than setting the Plasmo
Mag-8 on absolutely every combination. However I can't be certain.

 

[Mark McIntyre]

I want to generate every possible 16 character combination of the
characters 0-9, A-Z, and a-z programatically.

Thats a lot of combinations.

for(j = '0'; j <= 'z'; j++) {

this isn't guaranteed to include all the characters you want. There's
nothing in C that requires the characters to be in order from 0 to z.

 

[Ken Human]

Martin Ambuhl's code should work. Just replace the 16 with a 4.

What do you need these 16-character permutations for? I suspect that there
may be a much more efficient way of achieving it than setting the Plasmo
Mag-8 on absolutely every combination. However I can't be certain.

It's for a game, actually. During a part of the game the user is asked
to develop a way to crack a random password that consists of those 62
characters. I provide a scripting language and this particular tool,
they have to figure out how to use it in the most efficient way. The
user usually won't actually try every possible combination, unless he
doesn't understand what he's supposed to be doing.

Basically there's a rule set that's similiar to: 5 - 7 digits and must
not start with a capital letter or number.

I needed the best way to find every combination because it's possible
that the user will want to try every combination, and 16 just happens to
be the longest length of password I want to use for the game. If the
user chooses to try every combination on a 16 digit password he'll most
likely not advance.

 

[CBFalconer]

Ken Human wrote on 22/05/05 :


Really ? It may take hours or days to print them out... Sounds
like a cracking device...

I don't think any of you, he, or I will live to see the program run
to completion.

--
Some informative links:
http://www.geocities.com/nnqweb/
http://www.catb.org/~esr/faqs/smart-questions.html
http://www.caliburn.nl/topposting.html
http://www.netmeister.org/news/learn2quote.html

 

[Simon Biber]

Hours or days? You'd better buy a sweater; it's going to get chilly
after the sun burns out (which will happen long before this thing is
finished).

If computer speeds double every 3 years, and the fastest computer at the
beginning of 2005 can run 2^30 iterations per second, then the earliest
completion date is January 20, 2124. You would buy the computer on
August 22, 2119, and it would run for 4 years, 3 months, 29 days.

Mathematica expression used:
Minimize[2005 + 3 * Log[62^16 / (2^30 * 31556952 * length)]
/ Log[2] + length, {length}]

(where 2005 is the date at which computers have the given speed,
3 is the number of years to double,
62^16 is the number of computations,
2^30 is the number of computations per second,
31556952 is the number of seconds per year,
length is how long the computation will take in years)

The length of computation for the first possible completion date is
3 / Log[2]

Interestingly, this is merely a function of the rate of speed growth,
and is entirely independent of the complexity of the problem.

The start date is: 2005 + 3 / Log[2] * Log[
31^16 / (3 / Log[2] * 31556952 * 2^14)]

As an even sillier aside, keeping the same assumptions and working
backwards, for such a "standard" computer to iterate those combinations
of length 7 was first possible in 1963, length 8 was first possible in
1981, length 9 in 1999, and length 10 will be possible in 2016.

 

[Walter Roberson]

If computer speeds double every 3 years, and the fastest computer at the
beginning of 2005 can run 2^30 iterations per second, then the earliest
completion date is January 20, 2124. You would buy the computer on
August 22, 2119, and it would run for 4 years, 3 months, 29 days.

Heh ;-)

As an even sillier aside, keeping the same assumptions and working
backwards, for such a "standard" computer to iterate those combinations
of length 7 was first possible in 1963, length 8 was first possible in
1981, length 9 in 1999, and length 10 will be possible in 2016.

I am quite not sure here what you mean by "possible". Length 10
at 2^30 per second would take about 24 3/4 years, but that's
-possible-.

 

[Malcolm]

It's for a game, actually. During a part of the game the user is asked to
develop a way to crack a random password that consists of those 62
characters. I provide a scripting language and this particular tool, they
have to figure out how to use it in the most efficient way. The user
usually won't actually try every possible combination, unless he doesn't
understand what he's supposed to be doing.

Basically there's a rule set that's similiar to: 5 - 7 digits and must not
start with a capital letter or number.

I needed the best way to find every combination because it's possible that
the user will want to try every combination, and 16 just happens to be the
longest length of password I want to use for the game. If the user
chooses to try every combination on a 16 digit password he'll most likely
not advance.

Why not write these functions

/*
return true if a string is a valid password.
*/
int validpassword(char *str)

/*
store a password entered by the user
*/
int storepassword(char *pass)

/*
return true if the password has already been tried
*/
int paswordtried(char *pass)

/*
clear the list of stored passwords
*/
void clearattemptlist(void)

I think with these functions you can achieve what you want, without any need
for an exhaustive iteration. The whole point of a password is that it is too
difficult to enumerate all possibilities, anyway.

 

[Ken Human]

Why not write these functions

/*
return true if a string is a valid password.
*/
int validpassword(char *str)

/*
store a password entered by the user
*/
int storepassword(char *pass)

/*
return true if the password has already been tried
*/
int paswordtried(char *pass)

/*
clear the list of stored passwords
*/
void clearattemptlist(void)

I think with these functions you can achieve what you want, without any need
for an exhaustive iteration. The whole point of a password is that it is too
difficult to enumerate all possibilities, anyway.

I'm very interested in the possibility of not having to use this type of
code on the end user's machine, but the point of this part of the game
is to write a working brute force attack that won't take forever. I
want to keep the scripting language itself as simple as possible.

To demonstrate exactly what the problem is, I'll explain the problem in
the game: The user is given an MD5 hash of a password to gain access to
a privileged part of the program. The user has an idea of how the
password is formed, and an idea of the size. So say that information is
4 - 6 digits, and the password looks like 00Ab(A?)(b?) (he got this
information by walking around in a building and looking at people typing
in their passwords).

So in the scripting language he'd write something like:

bool BruteForce(string MD5, string format) {
if(format) while(MD5 != crack(format));
else while(MD5 != crack());
}

int main(void) {
bool found = BruteForce(hash, "%N%N%L%l%?L%?l");
if(!found) return errorCode();
return 0;
}

and crack() is the previously posted code
(
that checks every combination of those 62 characters with the
modification of knowing what to do with a "string format". The actual
script does not resemble C as much and would look more complex.

My scripting language can not accomplish what crack() would, as I'm
trying to keep it minimalistic. Unfortunatley I don't really think the
ideas you posted could apply, but if you see something I don't, I'd love
to hear it.