Return to Unfiction unforum
 a.r.g.b.b 
FAQ FAQ   Search Search 
 
Welcome!
New users, PLEASE read these forum guidelines. New posters, SEARCH before posting and read these rules before posting your killer new campaign. New players may also wish to peruse the ARG Player Tutorial.

All users must abide by the Terms of Service.
Website Restoration Project
This archiving project is a collaboration between Unfiction and Sean Stacey (SpaceBass), Brian Enigma (BrianEnigma), and Laura E. Hall (lehall) with
the Center for Immersive Arts.
Announcements
This is a static snapshot of the
Unfiction forums, as of
July 23, 2017.
This site is intended as an archive to chronicle the history of Alternate Reality Games.
 
The time now is Mon Nov 18, 2024 7:31 pm
All times are UTC - 4 (DST in action)
View posts in this forum since last visit
View unanswered posts in this forum
Calendar
 Forum index » Diversions » Perplex City Puzzle Cards » PXC: Silver Puzzle Cards
[PUZZLE] #251 - Silver - The Thirteenth Labour - READ POST#1
Moderators: AnthraX101, bagsbee, BrianEnigma, cassandra, Giskard, lhall, Mikeyj, myf, poozle, RobMagus, xnbomb
View previous topicView next topic
Page 26 of 73 [1087 Posts]   Goto page: Previous 1, 2, 3, ..., 24, 25, 26, 27, 28, ..., 71, 72, 73  Next
Author Message
chimera245
Decorated

Joined: 09 Mar 2006
Posts: 209

Excellent news Sk1zz.

Are you happy with me taking your code and incorporating it (with further testing) into the client code line?

I should be able to work on this quite quickly now as RL is clearing up - perhaps starting tomorrow night?

PostPosted: Tue May 02, 2006 10:49 pm
 View user's profile Visit poster's website
 Back to top 
jazzychad
Veteran

Joined: 03 May 2006
Posts: 74

Assault Benchmarks?

Hi all,

I thought it would be handy if people running guin's Assault client would post their "benchmarks" per se... What kind of OS/processor speed/time per workunit, etc...

Here are mine:

1) PC - Win 2000, AMD Athlon XP 2600+ 2.1 GHz, 1.5 GB RAM, 20 min/wu
2) Laptop - Win XP, Intel P4 1.2 GHz, 512 MB RAM, 40 min/wu
3) PC - Linux Fedora Core 4, Intel III 933 MHz, 512 MB RAM, 60 min/wu
4) Laptop - Mac OS X (Darwin), PowerPC G3 700 MHz, 640 RAM, 60 min/wu

All of these times are for running the client at, or near, full-throttle.

What kind of speeds are other people seeing?

PostPosted: Wed May 03, 2006 1:59 am
 View user's profile
 Back to top 
chimera245
Decorated

Joined: 09 Mar 2006
Posts: 209

I did some benchmarking early on in the piece with the 13th Labour client (GuiN has done the Web Site/Marketting but it's lil ole me that did all the development stuff), but really abandoned it as unreliable.

While the throttle is a guide to performance - it is a vague one. The setup of your OS (and what else is running), the processor type you use (AMD runs faster in most situations but does not respond to throttle), and the OS you use (Rosetta == Very Bad) make much more difference.

I think the top numbers I got were just under 9 minutes on a hyperthreaded Intel PIV 3.2Ghz with an environment where basically it was all Windows had to worry about.

PostPosted: Wed May 03, 2006 5:03 am
 View user's profile Visit poster's website
 Back to top 
Skizz
Boot

Joined: 11 Jan 2006
Posts: 37

chimera245:
Go ahead - that's why I made the code public. For your information, the Worker.cpp/.h is the file containing the threaded decryption code. Decrypt.cpp/.h contains the UI and thread control - this file will need to be updated to run as a client. You'll probably want to cache pending work units so the decryption doesn't wait on server comunication (i.e. get WUs, dispatch WUs, get next WUs, wait, dispatch new WUs, send result, get next WUs, wait, etc...). At the moment it only stores the keys that produced valid output, not the output/plain text (memory access is so slow).

It did occur to me that the communication with the server will become the bottleneck in this application. But that's another problem Wink

Dranioth:
People have been reporting Work Unit times as quick as 9 minutes on a 3GHz PC. My 3GHz Dual Core PC using this fast client can average a Work Unit every 10-15 seconds. Although it uses all the available CPUs reported by the OS, I don't think a hyperthreaded CPU will gain much advantage over a single core PC. Obviously, doing any foreground work will slow down the decryption - the fast client runs at idle priority which means other applications will get the CPU in preference to the client. If you look at the task manager you'll see the system's idle process is 90% or more most of the time so you shouldn't see any difference in normal day-to-day usage when running the fast client. Laptop users will notice their batteries drain quicker though.

Remember to disable the screen saver if you plan to leave any client running when you're not around!

Skizz

PostPosted: Wed May 03, 2006 6:27 am
 View user's profile
 Back to top 
Skizz
Boot

Joined: 11 Jan 2006
Posts: 37

Just out of interest, would it be possible to submit CPU details to the server (with user permission, of course). I'm just wondering if it's worth doing a 64bit version of the client (i.e. anyone using an AMD64 CPU) as this would again provide a step up in speed due to the single instruction 64 bit rotate (as opposed to the hoops the client currently jumps through) and the extra registers.

Skizz

PostPosted: Wed May 03, 2006 6:57 am
 View user's profile
 Back to top 
mac_monkey
Decorated

Joined: 25 Feb 2006
Posts: 250

Well without much knowings of the internal workings of chimera's client, or the correctness of skizz's client It would be excellent if the two can be combined to produce a faster client, if not though-i think everyone's still donea great job with this!

Keep up the work guys!
_________________
Now Playing: Super-8

PostPosted: Wed May 03, 2006 7:12 am
 View user's profile
 Back to top 
Fuseunderground
Decorated

Joined: 17 Dec 2005
Posts: 151

Thanks to the 1.03 version (well done again Chimera245)
we have been able to monitor how many units were processed,
registered to our own e-mail address.

I calculated the percentage of the total processed units that I have done.
I was happy to see that this was reducing day by day,
because this meant there were more and more units being processed elsewhere,
[as I have a fairly constant flow of units through 2 (occasionally 3) PC's].

Recently, my percentage of the total has been increasing,
which implies people were running it have stopped or reduced their processing, which is disappointing.

I'm sure there are many of you out there that have processed lots more units than me,
Which means that others are doing even less, but obviously every little helps.

I guess I started typing this to simply share my observations,
But I think now that we need more ways to encourage many more of the ~10,000 active PXC players to participate.

One way could be a leaderboard on the 13th labour website,
(There's nothing like a leaderboard to encourage participation – ask Mind Candy Wink )
Perhaps one board for people running one client,
and one for people with multiple clients (to encourage/not discourage the 'little guy')
This would obviously serve no real purpose, but would help people visualize how much they can affect the task.

Also is it possible to add the number of active unique users (e-mail addresses) to the client as well, as the number of active clients on it's own make it look like there's more people participating than there is (so some people may think 'they have enough help already….')

Anyway those are my thoughts for the day, feel free to ignore them. Smile

Rich
_________________
Like your hero TJ Hooker you tackle challenges head-on with determination and vigour paying scant attention to the law. This devil-may-care attitude may work for fictional crimefighters but it can be counterproductive in real life.

PostPosted: Wed May 03, 2006 7:21 am
 View user's profile
 Back to top 
arnezami
Veteran


Joined: 14 Apr 2006
Posts: 136

Skizz wrote:
Hi All,

I've reworked the source to my fast client - it now correctly decodes the above test case! And, it's double the speed! (Those pesky div instructions are even slower than I thought!) I've attached the source again and the release build of the executable - no changes in it's visual appearance or use.

In the end, it was case (3) in my previous post. The rccrypt program deviates slightly from the standard RC5 algortihm as designed by Ronald Rivest. Firstly, the key scambling code in rccrypt is:

...

whereas the original algorithm is:

...

which is subtly different. The main en/de-cryption loop does additional work - it adds a redundant* block at the start and adds a terminating block to indicate length of the plain text.

Anyway, it now works with the test case. All that's needed now is some more testing (compare results against known work unit - it'll probably report slightly more possible keys as it uses the range 0-127 inclusive as valid characters) and integrating into existing PC client code - then we'd have a super fast attack!

Skizz

* redundant in that the xor'ing of blocks together isn't being done so the result of the decryption of the first block is thrown away.

Man you're good!! Some real hard core coding there!

Regarding the 0-127 chars. As c1023 pointed out the chance of producing any false positives is extremely low (let alone several) even when going through the entire 2^64 search space. So this filter works perfectly. There is absolutely no need to filter it down further to prevent false positives. In fact it would be unwise since there is always the possibilty of filtering too much.

When looking at the assembler I see you are using two pipes to do mostly the same (integer and SSE). Just wondering if one is faster and (when looking at comsumed cycles per instruction) there is a chance to tweak it a little further (by sometimes doing more instructions with one than the other etc). And if one pipe is almost twice as fast would it be possible to do twice as many with one pipe? Or somehow doing 2 with one and 3 with the other? You'll probably be much better at answering these questions than I will ever be...

As for the difference in "original" and "rccrypt" implementation of the rc5 decryption: how sure are we of this? Is Von's hint proof enough for us using the rccrypt implementation? Or should we seek confirmation of this? (since there is so much at stake here).

And since this code is SO much faster would it be a good idea to try more characters? For example (taken from this site):
Code:
ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789!@#$%^&*()-_+=

or
Code:
ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789!@#$%^&*()-_+=~`[]{}|\:;"'<>,.?/


The first one would add 15 new characters on top of the 62. So instead of a search space of 62^8 = 2.18e14 you get 77^8 = 12.35e14. Which is "only" 6 times slower but covers more (reasonable) possibilities. I believe the last one includes all possible characters that can be produced by a keyboard. Just a thought.

Again great work! Smile

arnezami

PostPosted: Wed May 03, 2006 9:18 am
 View user's profile
 Back to top 
Skizz
Boot

Joined: 11 Jan 2006
Posts: 37

The two slowest parts of the code are the key mixing loop (lots of memory read/writes) and the 64 bit integer rotations (conditional branches). As for the relative speeds of the two pipes, I couldn't really say without something like Intel's VTune, which I don't have as it's rather pricey and I'm not working for anyone who's got it (but there is a trial version available which I may download). I would hazzard a guess that the integer pipeline is quicker as the integer unit can dispatch up to two instructions per cycle whereas the SSE can only dispatch one.

The biggest speed up would be to use a 64bit CPU (e.g. AMD-64 / PowerPC G5) as this would eliminate the conditional jumps as well as free up registers.

What's interesting about this algorithm is its unsuitability for SIMD (although I use the SIMD parts I only use them as SISD).

I think Von's clue implies that the encrypted text was created using rccrypt, thus the assumptions about the decryption algorithm are well founded. The only possible option as far as I can see is the xor'ing of blocks together (the -p option I think). This is this only option rccrypt has which isn't specified by the card.

Skizz

PostPosted: Wed May 03, 2006 10:09 am
 View user's profile
 Back to top 
arnezami
Veteran


Joined: 14 Apr 2006
Posts: 136

Skizz wrote:
The two slowest parts of the code are the key mixing loop (lots of memory read/writes) and the 64 bit integer rotations (conditional branches). As for the relative speeds of the two pipes, I couldn't really say without something like Intel's VTune, which I don't have as it's rather pricey and I'm not working for anyone who's got it (but there is a trial version available which I may download). I would hazzard a guess that the integer pipeline is quicker as the integer unit can dispatch up to two instructions per cycle whereas the SSE can only dispatch one.

Would it be possible to basicly turn off all the SSE code to see if it is a "drag" on the integer part? And if so how much? If it becomes (almost) twice as fast it may be worth exploring. Otherwise probably not.

But as you indicated memory usage/rotation is most time consuming so this may not be worth it anyway.

Its just an idea.

arnezami

PostPosted: Wed May 03, 2006 10:27 am
 View user's profile
 Back to top 
jazzychad
Veteran

Joined: 03 May 2006
Posts: 74

Skizz,
What are you using to compile your source code? I've tried running the binary on my machine (win2k), but it fails... I also tried compiling using Visual C++ v6 (old, i know...), but it throws a bunch of errors. Any pointers (haha, pun not intended) on how to compile? I'd really like to play around with this, too.

Thanks.

PostPosted: Wed May 03, 2006 4:32 pm
 View user's profile
 Back to top 
chimera245
Decorated

Joined: 09 Mar 2006
Posts: 209

Quote:
And since this code is SO much faster would it be a good idea to try more characters?


I don't see any reason to add to the alphabet at this stage - we can use the extra speed to get through the existing alphabet much faster.

PostPosted: Wed May 03, 2006 9:44 pm
 View user's profile Visit poster's website
 Back to top 
jazzychad
Veteran

Joined: 03 May 2006
Posts: 74

Yes, but I would hate for the answer to be something like:

<!-- You solved me -->

and miss it solely because we used an alphanumeric set...

Are you looking for decrypted text that is entirely ascii-text? or are you considering ones that at least contain ascii-text?

PostPosted: Wed May 03, 2006 10:10 pm
 View user's profile
 Back to top 
chimera245
Decorated

Joined: 09 Mar 2006
Posts: 209

Hi,

The alphabet is for the 8 character key not the solution.

For a solution, we are including all values <= '~' I.e. from 0 to 126 - I am excluding DEL (127) and all higher - but this includes all the early crap too.

If the 8 character key happens to be

!@#$%^&*

instead of

8ugg3rM3

we will miss it - but we can cross that bridge at the end if necessary. It is not hard to come up with the work units/processing to go through the remaining combos. I just (and others in this and previous threads) have not thought that this would be necessary.

PostPosted: Wed May 03, 2006 11:36 pm
 View user's profile Visit poster's website
 Back to top 
Skizz
Boot

Joined: 11 Jan 2006
Posts: 37

jazzychad:
I used MS Visual Studio 2003 to compile it (but it ought work with 2005 express which is free). V6 probably complained about the assembler code. It probably failed on your PC because your CPU doesn't support the SSE2 extension the program uses. It really should check the CPUID I guess.

Skizz

PostPosted: Thu May 04, 2006 3:10 am
 View user's profile
 Back to top 
Display posts from previous:   Sort by:   
Page 26 of 73 [1087 Posts]   Goto page: Previous 1, 2, 3, ..., 24, 25, 26, 27, 28, ..., 71, 72, 73  Next
View previous topicView next topic
 Forum index » Diversions » Perplex City Puzzle Cards » PXC: Silver Puzzle Cards
Jump to:  

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum
You cannot post calendar events in this forum



Powered by phpBB © 2001, 2005 phpBB Group