Didactic XOR Long Cipher

Lysander
Posts: 4
Joined: Sat Nov 01, 2008 9:51 pm

Didactic XOR Long Cipher

Post by Lysander »

I just solved the Didactic XOR Cipher 3. It took my computer about 3 seconds to calculate all 65536 possibilities and finding the right one.
But in the Didactic XOR Long Cipher I would have to calculate about 4.3 billion possibilities! Even if I consider that my CPU was in dynamic clock signal frequency state and I graciously assume 100,000 calculations per second it would still take me about 12 hours to run through all possibilities. Well, I hope that the right combination is in the first half, but still it will probably take hours.
I would like to ask someone who has already solved this challenge: Did it really take hours to find the right values? Or is there something I have missed?
gfoot
Posts: 269
Joined: Wed Sep 05, 2007 11:34 pm
Location: Brighton, UK

Post by gfoot »

Some challenges do take days to solve, but in most cases there are shortcuts of some kind. Usually the challenge is to think around the problem, and break down its complexity, rather than just to come up with enough CPU time to brute-force it.

So I think you should generally look harder for shortcuts yourself - that's half the fun - rather than ask if there are any. I won't say whether there is one or not in this case. Maybe by the time you've convinced yourself there's no shortcut, your brute force solver will have finished anyway!
stingr4y
Posts: 1
Joined: Tue Oct 28, 2008 9:28 pm

Post by stingr4y »

Solving it manually (without computer) with an ascii table took me about 45 minutes
User avatar
CoreEvil
Posts: 18
Joined: Thu Mar 27, 2008 12:20 am

Post by CoreEvil »

You can instruct your brute force algorithm to stop and move to the next iteration when a certain criteria is not met, the choice of criteria varies from one person to another, you can be very liberal or very conservative, the more intelligent your choice the less time it will take you to decipher the message (it can take seconds)
You like pink, don't you?
Hawkeye
Posts: 2
Joined: Sat Nov 08, 2008 7:52 am

Post by Hawkeye »

Nearly like stingr4y. Took me 70 minutes to solve with excel ;)
lukas
Posts: 34
Joined: Wed Nov 26, 2008 1:53 pm
Location: Germany

Post by lukas »

not need to calculate all posibilities, I also tried first this way but it was for me to long xD

one hour of each variable testing and I was having it
User avatar
m!nus
Posts: 202
Joined: Sat Jul 28, 2007 6:49 pm
Location: Germany

Post by m!nus »

trying through all 4 bytes of the key could indeed take long. i solved it with a lot less "tries" (about 1000)
Belriel
Posts: 16
Joined: Sat Dec 20, 2008 2:55 pm

Post by Belriel »

I also tried it with brute force first but was too slow and I had an error somewhere so after all the time there was no result. I went to bed then and kept thinking of the problem and I then found a much more efficient way, tried it the next day and it cracks the cipher in 2 seconds :D.
higgs
Posts: 4
Joined: Sat Jan 03, 2009 12:11 am

Post by higgs »

I made 4 lists which each contained every 4th caracter (so that all the chars with the same key were together). Then I got all 255 possibilities for each key and I looked at the list for which result only featured mostly lower case letters and no weird mumbo-jumbo such as `nj/hzf/v/l. There was generally just one result that met that criteria so I could take an educated guess that it was the right byte. Then I only had to put them in order and violà!
Cobruto
Posts: 3
Joined: Sun Jun 28, 2009 8:26 pm

Solved by hand

Post by Cobruto »

Solved it with cryptool, with the analyse function, and adjust it by hand. Wasn't that hard. only made one small mistake with uppercase/lowercase. Took me 10/15 minutes.
Cya,
CoB
Aldreyu
Posts: 3
Joined: Tue Jul 07, 2009 8:17 pm

Post by Aldreyu »

i splitet the string so i had 4x 1Byte chipher...
then wrote a programm that test all compinations 4*256 and display it when the chars in ascii make sense... 30mins i had...
chenkai036
Posts: 1
Joined: Wed Sep 02, 2009 2:28 pm

Post by chenkai036 »

I split the encrypted text into 4 parts as follows.
s[0] = txt[0] txt[4] txt[8] ...
s[1] = txt[1] txt[5] txt[9] ...
s[2] = txt[2] txt[6] txt[10] ...
s[3] = txt[3] txt[7] txt[11] ...

If we define key as k[0] k[1] k[2] k[3] for representation, we could find the k is only XORed with every elements in s. So It is easier to check only 256 possibilities for every k of key.
User avatar
Yharaskrik
Posts: 31
Joined: Wed Nov 05, 2008 11:44 am
Location: Germany

Post by Yharaskrik »

Hello,
there is a "Challenges Solved" forum...
DaymItzJack
Posts: 106
Joined: Thu Oct 29, 2009 9:21 pm

Post by DaymItzJack »

Sorry this might be a little late, but my program solved it in 3 seconds. There are ways to narrow down the possibilities.

I still had 4 nested loops however in each loop I made sure the first few characters were real letters (abcde..) to continue looping. Then I looked for words I thought might be in the encrypted message and I got it.
compudemon
Posts: 33
Joined: Sat Aug 13, 2011 2:13 pm

smart brute force

Post by compudemon »

rather then incrementing the key i used

p=p%4
if p==0 : a=((key&0xff)+1)&0xff; b=key&0xffffff00; key=a+b
elif p==1 : a=((key&0xff00)+0x100)&0xff00; b=key&0xffff00ff; key=a+b
elif p==2 : a=((key&0xff0000)+0x10000)&0xff0000; b=key&0xff00ffff; key=a+b
else : a=((key&0xff000000)+0x1000000)&0xff000000; b=key&0x00ffffff; key=a+b

where p was a location in the string where the code found a character it didn't like

if val<32 or val>126 or (chr(val) in "&*~/{}[]=+_^%@$-`\\<>|#") : err=1; break

despite using this in a loop the answer was nearly instant. this method could be done with 4 loops one for each of the 4 bytes in the key i used one loop and broke the bytes with masks
Post Reply