unforum

[mac_monkey]

I think the most important thing is not to forget what we've done. It'll be easy to do all combinations of spaces and characters for example, but it becomes tricky when we say right, we'll introduce the possibility of a space being in the 4th space. What if we forget that we havent done all the spaces in the 1st 2nd 3rd etc.. spaces.

It's going to need to be a clever algorithm. But there's still hope.

[BBuck]

Re: Key space

[SteveC]

[chimera245]

We just had a power outage (just an hour) which is why 13L was down. It is back up now.

[chimera245]

Somebody buy Western Power a new rubber band for Pete's sake.

Back up again now.

On the expanded keyspace - once I heard that 'Punctuation' was in the password I actually assumed it was still under a random basis.

We commonly use passwords of the form:

8l!meyM@t3

Using simple substitution.

Whether you go with 'anywhere' expanded keyset, or placed expanded keyset - I can code the client appropriately for you.

Once the original keyspace is exhausted (and assuming of course we don't find the answer), that keyspace can be re-searched however you like.

On the new host - don't forget it needs to be available 24/7 - and have appropriate OS licencing. You won't be able to use XP Pro if you are going to expand your clientbase much. Also I would strongly recommend SQL Server 2005 for the back end - Express is free and fully featured.

[SteveC]

With regards to the licensing, we've got a Server 2003 license covered - but that obviously implies that it's a dedicated machine that someone can help us with... And as chimera says, the actual DB is a freebie from the nice folks at MS, so that's Ok too..

anyone?!?...

Even if you only know someone who has a decent Internet line that we could piggy back on, that would be a help, so don't be shy, come forward!

[obrienk]

i have a 10mb cable line, but upload speed is pants, so probably no good ?

[SteveC]

Just to clarify that, yes, ADSL lines and Cable lines probably need not apply. Although it might eek through, your use of it would be killed completely!

1Mb sync means it can do at least that in each direction, ADSL typicaly provides <=384Kb in the main direction we need.

[mac_monkey]

Urm maybe someone should ask skenmy...

He doesnt read these boards I dont think, but he does work for a web hosting company

[skenmy]

Get in touch with me, SteveC / chimera / Guin - I'm very willing to run the server side of things with you guys.

I don't have a server to donate but I need to chat with you guys to learn about bandwidth usage and whatnot so we can work on getting a decent server and line to run it on.

[Guin]

new puzzle for you all on the live journal

puzzle fun

[BBuck]

A few thoughts about an expanded keyspace, for what they're worth. Hope they make some sort of sense, and apologies for a long post.

I think that the absolute maximum keyspace to search is likely to be 97: the 62 alphanumeric and the 35 non-alphanumeric characters on the keyboard. We've searched a keyspace so far of 62^8 = 218.34 trillion. There are a total of 97^8 options with an expanded keyspace = 7837.43 trillion, roughly 36 times more.

From what I can see on the 13th Labour site, the effort has averaged somewhere between 1000-1200 clients over a period of four months, and 63% of the keyspace has been completed.

From Michael Smith's comment in the MTV interview of 30, 000 computers taking several months to solve this, I think we can extrapolate the likely keyspace to search.

A few assumptions:

- the code we're using is no faster nor slower than that asssumed by MC in their calculations
- "several months" does not mean the entire keyspace would be searched in that time, just sufficient to have a, say, 75% chance of finding the key.
- "several months" is between 3-6 months.

The best case on these assumptions is that it would take 3 months for 30, 000 computers operating at the same rate as our efforts to search 75% of the keyspace. This implies a keyspace of roughly 66. The worst case on these assumptions, 6 months, is a keyspace of roughly 72.

To search a keyspace of 97 with 30, 000 computers in six months, the WU rate would need to be ten times faster than we're achieving. I'm not a programmer, but it looks like some very good ones have been working on this, and we're at or near optimal, so I think this is unlikely.

So, assuming a keyspace of 72, how best to search? I'm not sure that the approach suggested earlier of trying all combinations with " ", then moving on to all with " " plus "." (say) is the way to maximise the chances of finding the key quickly. It depends completely on the order in which the non-alphanumeric characters are chosen, and I think from the estimates above, we are looking at a keyspace of around 72.

If we do expand the keyspace to 72, then there are two ways to reduce the number of options, depending on whether we believe the key was constructed randomly or non-randomly.

i) Random key: If the key has been chosen randomly, then the chances of there being x occurences of non-alphanumeric characters from a keyspace of 72 are:

[arnezami]

Just would like to point out that a form of directed search on a random key is not possible. The only thing you do by choosing any kind of subset is speeding up the process at the expense of lowering your chance of finding the random key (with the same proportion).

Essentially if you choose a subset which covers only 40% of the entire search space you reduce your chance of finding it to 40% aswell.

In other words: if they used a random key we're screwed (if we take the 30000 clients/3-6 months as accurate). So I think we have to believe its not random OR to hope their estimate was far off and they used a random key with a much smaller amount of characters than we might conclude from their estimate.

[mac_monkey]

How about just adding these characters to the current keyspace...

" " . , ! ? ' "

so 7 extra characters... which means 20,099,202 extra work units to do.

I'd personally rather search for these characters being randomly inserted in a key rather than being at the end. Although that said, it may be worth doing both, starting with them at the end as it's a smaller keyspace.

However, this I'm guessing would mess up work unit allocation, as they are given out based on the first 4 characters, not the last 4.

EDIT:Forgive me if my maths is wrong.

[BBuck]