string generation

[CBFalconer]

Re: string generation

Emmanuel Delahaye wrote:[color=blue]
> Ken Human wrote on 22/05/05 :
>[color=green]
>> I want to generate every possible 16 character combination of
>> the characters 0-9, A-Z, and a-z programatically . My current
>> code follows:[/color]
>
> Really ? It may take hours or days to print them out... Sounds
> like a cracking device...[/color]

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

--
Some informative links:
news:news.annou nce.newusers

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]

Re: string generation

Keith Thompson wrote:[color=blue]
> 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).[/color]

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.

--
Simon.

[Walter Roberson]

Re: string generation

In article <429072d3$0$812 0$afc38c87@news .optusnet.com.a u>,
Simon Biber <news@ralmin.cc > wrote:[color=blue]
>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.[/color]

Heh ;-)

[color=blue]
>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.[/color]

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-.
--
Look out, there are llamas!

[Malcolm]

Re: string generation

"Ken Human" <kenhuman@comca st.net> wrote[color=blue]
>
> 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.
>[/color]
Why not write these functions

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

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

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

/*
clear the list of stored passwords
*/
void clearattemptlis t(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]

Re: string generation

Malcolm wrote:[color=blue]
> "Ken Human" <kenhuman@comca st.net> wrote
>[color=green]
>>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.
>>[/color]
>
> Why not write these functions
>
> /*
> return true if a string is a valid password.
> */
> int validpassword(c har *str)
>
> /*
> store a password entered by the user
> */
> int storepassword(c har *pass)
>
> /*
> return true if the password has already been tried
> */
> int paswordtried(ch ar *pass)
>
> /*
> clear the list of stored passwords
> */
> void clearattemptlis t(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.
>
>[/color]

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(stri ng 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
(news://news.comcast.gi ganews.com:119/dSUje.5646$uR4. 3569@newsread2. news.atl.earthl ink.net)
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.

[Ken Human]

Re: string generation

Ken Human wrote:
[color=blue]
> and crack() is the previously posted code
> (news://news.comcast.gi ganews.com:119/dSUje.5646$uR4. 3569@newsread2. news.atl.earthl ink.net)
> that checks every combination of those 62 characters with the
> modification of knowing what to do with a "string format".[/color]

Forgive me, I did not post the correct address to the code in question.
It is
news://news.comcast.gi ganews.com:119/RsQje.5561$uR4. 4992@newsread2. news.atl.earthl ink.net

[Simon Biber]

Re: string generation

Walter Roberson wrote:[color=blue]
> In article <429072d3$0$812 0$afc38c87@news .optusnet.com.a u>,
> Simon Biber <news@ralmin.cc > wrote:
>[color=green]
>>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.[/color]
>
> Heh ;-)
>[color=green]
>>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.[/color]
>
> 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-.[/color]

Yes, but if computers capable of 2^30 per second are not available until
2005, and it takes 24 3/4 years, then it won't finish by the year 2016,
will it?

I mean that the earliest possible completion date is 2016, and that will
only be possible if you wait until around 2012 to buy the computer, so
it will complete in only 4 years.

--
Simon.

[Michael Wojcik]

Re: string generation


In article <lnvf5bvmag.fsf @nuthaus.mib.or g>, Keith Thompson <kst-u@mib.org> writes:[color=blue]
> "Emmanuel Delahaye" <emdel@YOURBRAn oos.fr> writes:[color=green]
> > Ken Human wrote on 22/05/05 :[color=darkred]
> >> I want to generate every possible 16 character combination of the
> >> characters 0-9, A-Z, and a-z programatically . My current code
> >> follows:[/color]
> >
> > Really ? It may take hours or days to print them out... Sounds like a
> > cracking device...[/color]
>
> 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).[/color]

Yes, but it still sounds like a cracking device, Dangermouse!

Of course, there's no need to generate them anyway. We already have
the list, in a handy compressed form that allows random access. Just
pick an integer between 0 and 62**16-1 and convert it into its base-
62 representation. A function implementing that algorithm serves as
the "array" of values, and its parameter as the "index".

Iteration is slower than iterating through an actual array, but since
constructing the actual array is, er, infeasible, that hardly matters.

(64 characters would actually be better here, since converting a
number in "pure binary" representation to base 64 is easier than
converting to base 62, but neither is difficult.)

--
Michael Wojcik michael.wojcik@ microfocus.com

Push up the bottom with your finger, it will puffy and makes stand up.
-- instructions for "swan" from an origami kit

[CBFalconer]

Resolving a macro (was: string generation)

Michael Wojcik wrote:[color=blue]
> Keith Thompson <kst-u@mib.org> writes:[color=green]
>> "Emmanuel Delahaye" <emdel@YOURBRAn oos.fr> writes:[color=darkred]
>> > Ken Human wrote on 22/05/05 :[/color][/color]
>[color=green][color=darkred]
>>>> 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...[/color]
>>
>> 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).[/color]
>
> Yes, but it still sounds like a cracking device, Dangermouse!
>
> Of course, there's no need to generate them anyway. We already
> have the list, in a handy compressed form that allows random
> access. Just pick an integer between 0 and 62**16-1 and convert
> it into its base-62 representation. A function implementing that
> algorithm serves as the "array" of values, and its parameter as
> the "index".
>
> Iteration is slower than iterating through an actual array, but
> since constructing the actual array is, er, infeasible, that
> hardly matters.
>
> (64 characters would actually be better here, since converting a
> number in "pure binary" representation to base 64 is easier than
> converting to base 62, but neither is difficult.)[/color]

Having a handy number to stream in base routine, I tried diddling
it to go up to base 64, basically by modifying the digit conversion
routine below:

/* Mask and convert digit to hex representation */
/* Output range is 0..9 and a..v only (base 32) */
static int hexify(unsigned int value)
{
static char hexchars[] = "0123456789abcd ef"
"ghijklmnopqrst uv"
"wxyzABCDEFGHIJ KL"
"MNOPQRSTUVWXYZ @#";

/* allow for terminal '\0' */
#define MAXBASE 64 /*(sizeof(hexcha rs)-1)*/

return (hexchars[value & (MAXBASE-1)]);
} /* hexify */

What I want to do is keep hexchars private, and export the value of
MAXBASE, computed from the actual hexchars definition. Doesn't
work, because hexchars is undefined when the macro is expanded.
Can I get around this? The macro needs to be evaluated at the
declaration point.

--
Some useful references about C:
<http://www.ungerhu.com/jxh/clc.welcome.txt >
<http://www.eskimo.com/~scs/C-faq/top.html>
<http://benpfaff.org/writings/clc/off-topic.html>
<http://anubis.dkuug.dk/jtc1/sc22/wg14/www/docs/n869/> (C99)
<http://www.dinkumware. com/refxc.html> (C-library}
<http://gcc.gnu.org/onlinedocs/> (GNU docs)

[Michael Wojcik]

Re: Resolving a macro (was: string generation)


In article <42928222.8E211 E8C@yahoo.com>, CBFalconer <cbfalconer@yah oo.com> writes:[color=blue]
>
> static int hexify(unsigned int value)
> {
> static char hexchars[] = "0123456789abcd ef"
> "ghijklmnopqrst uv"
> "wxyzABCDEFGHIJ KL"
> "MNOPQRSTUVWXYZ @#";
>
> /* allow for terminal '\0' */
> #define MAXBASE 64 /*(sizeof(hexcha rs)-1)*/
>
> return (hexchars[value & (MAXBASE-1)]);
> } /* hexify */
>
> What I want to do is keep hexchars private, and export the value of
> MAXBASE, computed from the actual hexchars definition. Doesn't
> work, because hexchars is undefined when the macro is expanded.
> Can I get around this? The macro needs to be evaluated at the
> declaration point.[/color]

I can't see any way of doing that - sizeof needs an object of complete
type.

As an alternative, you could always make MAXBASE a fixed value in your
header, then do a compile-time check to verify that it's the same as
sizeof hexchars in the C file:

#include "hexify.h"

static int hexify(unsigned int value)
{
static char hexchars[] = "0123456789abcd ef"
"ghijklmnopqrst uv"
"wxyzABCDEFGHIJ KL"
"MNOPQRSTUVWXYZ @#";

#if sizeof hexchars != MAXBASE
#error "MAXBASE is defined incorrectly"
#endif

Not as satisfying as having MAXBASE computed automatically, but it
does at least catch skew between the header and the implementation.

--
Michael Wojcik michael.wojcik@ microfocus.com

[After the lynching of George "Big Nose" Parrot, Dr. John] Osborne
had the skin tanned and made into a pair of shoes and a medical bag.
Osborne, who became governor, frequently wore the shoes.
-- _Lincoln [Nebraska] Journal Star_

[Old Wolf]

Re: Resolving a macro (was: string generation)

Michael Wojcik wrote:[color=blue]
>
> As an alternative, you could always make MAXBASE a fixed value in your
> header, then do a compile-time check to verify that it's the same as
> sizeof hexchars in the C file:
>
> static int hexify(unsigned int value)
> {
> static char hexchars[] = "0123456789abcd ef"
> "ghijklmnopqrst uv"
> "wxyzABCDEFGHIJ KL"
> "MNOPQRSTUVWXYZ @#";
>
> #if sizeof hexchars != MAXBASE
> #error "MAXBASE is defined incorrectly"
> #endif
>
> Not as satisfying as having MAXBASE computed automatically, but it
> does at least catch skew between the header and the implementation.[/color]

You can't use 'sizeof' in a preprocessor test, because the
preprocessing is done before the compiling!

Although I have seen a preprocessor that supports what you
suggest, it is uncommon and non-standard.

[Michael Wojcik]

Re: Resolving a macro (was: string generation)


In article <1117159538.007 380.199060@z14g 2000cwz.googleg roups.com>, "Old Wolf" <oldwolf@inspir e.net.nz> writes:[color=blue]
> Michael Wojcik wrote:[color=green]
> >
> > #if sizeof hexchars != MAXBASE
> > #error "MAXBASE is defined incorrectly"
> > #endif[/color]
>
> You can't use 'sizeof' in a preprocessor test,[/color]

Ugh. Right. Didn't engage my brain.

You'd have to use a macro for the size of the hexchars array in the
first place; the appropriate thing would be to put MAXBASE in the
header and then use it as the explicit length of the hexchars array.
[color=blue]
> because the preprocessing is done before the compiling![/color]

Well, no, it isn't, strictly speaking. "Preprocess ing" is trans-
lation phase 4. The standard doesn't define "compiling" , but I'd
consider it the entire translation process. You might consider, say,
translation phase 7 "compiling" , but the term is open to interpre-
tation.

(I also note that the grammar in C90 Annex B implies that you *can*
use sizeof in a #if expression, as constant-expressions include
relational-expressions which can include unary-expressions which
include the sizeof operator applied to another unary-expression;
but this is just another case where the grammar is not the whole
story. The constraints in 6.8.1 include other restrictions.)

--
Michael Wojcik michael.wojcik@ microfocus.com

Thanatos, thanatos! The labourer, dropping his lever,
Hides a black letter close to his heart and goes,
Thanatos, thanatos, home for the day and for ever. -- George Barker

[Keith Thompson]

Re: Resolving a macro (was: string generation)

"Old Wolf" <oldwolf@inspir e.net.nz> writes:
[...][color=blue]
> You can't use 'sizeof' in a preprocessor test, because the
> preprocessing is done before the compiling!
>
> Although I have seen a preprocessor that supports what you
> suggest, it is uncommon and non-standard.[/color]

Dennis Ritchie posted something on this topic in comp.std.c back in
1998 (sorry, groups.google.c om mangled some of the headers):

] From: Dennis Ritchie <d...@bell-labs.com>
] Subject: Re: Computing sizeof() during compilation
] Date: 1998/05/08
] Message-ID: <35527014.7B15@ bell-labs.com>#1/1
] References: <6it2mh$dhq$1@c lient3.news.psi .net> <dennisEsLr3E.D 9G@netcom.com>
] Organization: Bell Labs, Lucent Technologies
] Reply-To: d...@bell-labs.com
] Newsgroups: comp.std.c
]
]
] > You are right. It was nice back in the days when things like
] >
] > #if (sizeof(int) == 8)
] >
] > actually worked (on some compilers).
]
] Must have been before my time.
]
] Dennis

--
Keith Thompson (The_Other_Keit h) kst-u@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.