unforum

[SteveC]

 [PUZZLE] #251 - Silver - The Thirteenth Labour - READ POST#1

[SteveC]

Now I've gotten that out of the way...

My further opinions....

I think the key is guessable, we need to get a list of possibles and various means of encoding them to 64 bits. The list is best generated by the original #251 thread, and lets discuss key encoding means here...

I don't think there are any viable backdoor attacks on this encryption. There is one involving situations where someone has generated a lot of encrypted text with one key, but we only have one? Correct me if I'm wrong. PLEASE!

I'm working on a webpage to automate key guesses. Initially this will take either hex strings or text strings. The latter will be maximum 8 characters, will pad anything less with zeros and will ASCII encode. I will also first letter capitalise, whole string lowercase and whole string uppercase each guess. The result will be passed to a file magic number guesser and the result will be displayed.

Dunno when this will be ready, but hopefully pretty soon. I'd like to get this solved. ANY suggestions as to other means of encoding or other tricks to try for each keyguess would be happily received.

[Jakeo]

I've contacted some of the d.net team to ask them whether their keyserver software is available. If it is, we'll be able to co-ordinate a brute-force attempt at it.

I'm not suggesting that this is the easiest way to solve the card, but between us we must have a reasonable pile of machine cycles, and we might as well get started just in case we can't guess the key

I agree with Steve that there isn't really a way to make this any easier, but just in case anyone isn't aware, the message is likely to start with

[chichiri]

One final note on introduction, when reason drew this card from a pack, fiona said to him that this card should be solved sooner rather than later, I am now fairly certain that this means that we should get started on it early because it will take the best part of forever.

no da

[SteveC]

On the topic of the keyserver from the folks at distributed.net. Jeff Lawson is unlikely to release the code to us as it's used as part of their flimsy security by obscurity efforts (self confessed, I'm not being judgemental, they just don't have any other real options).

However, it's viable that if we could cobble together a well tested and working client code (by melding their publically accessible code, and the guts of rccrypt), they might, MIGHT, set it up as a new project.

Once I've done my "try a key" webpage, I'll look at doing that. Or if brian or other coders that are more clever than I fancy doing it? it shouldn't be too hard.. Might want to ask Rick from rccrypt first though

[Jakeo]

I am one of said coders, and would be willing to try and hack something together. In my mail to Jeff I also asked if he had any pointers on how to make the whole thing work.

I guess in principle its just a case of creating a server that can generate and track work units, a transport to deliver the work units to the client machines and some sort of rccrpyt harness that will run them, look for the relevant string in the output and report the results back to the server.

[SteveC]

Jakeo, I think what you need to do is to get the rc5 client source (available on d.net), modify it using the rccrypt decrypt code rather than their 32bit variant, and approach Jeff Lawson (bovineone) asking whether it could be added as a low key project alongside ORG and RC5-72.

We'll then have to give him block priorities to try decoding first (Eg, go for ASCII ranges first I guess?)

I have no idea how he'll take it. Generally they're good guys over there, but this is even more questionable benefit than the existing RC5 contests, I think they're more into the real-world-applicable OGR these days.

Another quirk we'll have to deal with is that we don't have a great test for the success of a decrypt. My webpage looks for "magic numbers" - but that's not really practical in a brute force attack... I guess we could assume ASCII?

[Langley Moor]

From what I recall of Rick's comments on his software when contacted, the program pads the encoded script with 8(?) characters of gibberish at the start, including unprintables. This is to make it much harder to brute force by searching for answers of entirely printable characters. Therefore, any software which checks for printable characters needs to be written in such a way that it discards the first 'n' characters before checking for printables.
I'm not sure of the exact number of characters (hence the question mark), but I don't have time right now to trawl the original thread. Just thought I'd remind anybody with the skills to do this sort of programming (I don't!) of this possible pitfall.

[hamatoyoshi]

Since SteveC has the nifty webpage, I'll toss this in his direction, but anyone should feel free to respond...

I had actually been thinking about this idea earlier when people were talking about customized distributed.net clients, but I actually accidentally ran into it: a Java webpage applet that cranks out keys (hewgill.com). He even has source available.

I'm not much of a programmer, and I haven't examined the code, but would there be a way to make this multi-threaded such that multiple people could just go to a webpage and click "Go!" and the keyspace could be searched in some organized way that the server would handle?

I understand it's Java, which is not optimized for cranking out keys, or for a particular processor group, but it's a heck of a lot easier to use (particularly at work) than installing a client.

At the very least, it's fun to calculate your hypothetical key calculation numbers. My work computer, which is a Pentium 4 2.8GHz will do 1.35 Megakeys a second. Which means my computer would exhaust the keyspace in a little under 433,291 years with an applet like this (or we'd need 433,291 computers like mine to exhaust the keyspace in a year!).

[SteveC]

[hairysocks]

I wonder if those sneaky puzzle setters have made the decrypted file so that every 5th or 13th character makes up the decrypted answer (probably not 13th character because that wouldn't give many in the answer, but you get the idea hopefully).

BTW SteveC - are you recording all the values people try on your web app page? It would be useful so you eliminate values, and also give others a set of values to try for more exhaustive tests - I have already pointed out that there are 256 possible variations of an 8-letter word taking all upper and lower case possibilities, and adding in digit-for-letter substitutions pushes the number much higher.

I currently have a set of Java apps trawling through some possibilities, but its taking a long time for each word, so I've set it off over-night. It tries the combinations I've mentioned above, and reversed values of these, and also using the -p option on rccrypt, so that makes for quite a lot of combinations. I may also incorporate the idea of skipping characters as mentioned above, and also looking for graphics files (say with those square grid barcodes like on the background to "Barcode Recipe").

[SteveC]

hairysocks,

Any encoding conversation other than the plain assumption that this is RC5-64 with 64 bit blocks and 12 rounds may be legitimate, but it does not belong in this thread.

On the other topic you raise, there are actually upwards of 218 trillion possible word combinations (a-Z, 0-9 = 62^8? Check my maths someone?). That's not as bad as it sounds, that's actually a searchable space, we just need to find time or people to build an engine to check it.

Which is what we're talking about with the rc5 client and keyserver side of things.

And yes, I am recording guesses (doh! shouldn'ta said that, maybe MC would come along and try the real answer out of interest ). The webapp is extraordinarily simple (runs to a mere 85 lines of code), I'm sure I'll work on a few improvements when I get time. More interested in the keyspace side of things for now.

FYI, there have been 1071 unique guesses so far, including the fact that each plaintext guess works out as up to three.

[hally]

Sorry for posting in the thread I don't belong in, but maybe you're looking to just decode the 6th line with the silver dot next to it as opposed to the 5th or 13th character

[SteveC]

Just to be clear, you can't really decode a "middle" portion of the text, it's not a substitution cypher. RC5 text has to be decoded as the block it came in as far as I understand it, or at least it's as easy to do that as not. The decode efforts on distributed.net decode the beginning and give up when they have the first few characters. However, we don't have that luxury as we don't know for certain the beginning of the plaintext.

Anyway, other news..

Using Bri's hack of rccrypt I managed a million keys in 25 hours. I think we really need to get going with a collaborative effort. Given that we have about 220,000 times that workload to do if we cover all ASCII numbers and letters.

I'm almost there with a standalone client, once it's confirmed working I'll integrate it into the distributed.net client framework and see if I can convince them to set it up as a project, or somehow let us manage it.

[doomsdayred]

SteveC could you please describe a step by step in how I can assist with the rccrypt. I've looked at the site but am a bit clueless on how to get started.

I run Windows XP on a pentium 4 1.9 ghz. (does this help?)