Broken XOR 3

[rmplpmpl]

As gfoot pointed out correctly I should not ask for hints in the challenge section on how to solve this.

My approach was the same as in the "normal" XOR 3 challenge: brute force key and offset with two loops, which makes 256^2 solutions. To reduce computation time I threw away every attempts that led to characters with an ASCII below 32 and above 122.

On the broken XOR I came to key and offset and did then alter the ciphercode to add the zeroes where they were lost.

My approach is not very smart and my problem of thinking is what would have happen if a zero would have been missing in the first few bytes. With my approach I would not have been able to track down the correct key and offset. Brute forcing would have been extremely difficult as far as I understand this, as you would have to assume the probability that there could have been zeroes lost everywhere.

So, would there have been a smarter approach? Would it be possible to solve this in a reasonable amount of computations if a zero would have been missing in, say, the first and third byte?

I am enjoying these challenges very much, and though I am working in the IT and have learned some basic programming, I have learned a lot more in the past three weeks that I am working on these challenges.

At the moment I am struggeling with JAVA, which seems to be needed for the protected password challenges and some more...

[gfoot]

So what I was alluding to was really that before rejecting a key pair due to having some characters out of range, you'd try inserting a zero before the first out-of-range character. If that fixes the next few characters, insert another one before the new first broken character, and so on.

It's not fully correct - it might be necessary to add a zero before a valid character, not just before one that otherwise decodes badly - but this would be a good start I guess, and it doesn't add many additional steps to your algorithm. Worst case, you find that adding a zero doesn't help anyway.

You can also be more aggressive, trying inserting a zero at each possible location, and recursing to try the next location too in any case where the characters up to that point are valid ascii text. I suppose that's technically O(2^n) but in practice most of the places you can insert a zero will only work in one direction, and often won't work in either direction, where your key pair is just wrong.

Another observation (the one I actually used - the above is just theory) is that adding a single zero at the start reveals a bunch of characters which were obscured because of their hex codes being out of phase. With the right key pair you'd probably expect a little under half of the message to be valid ascii text, and inserting a zero right at the start should still make a little under half be valid text. It should also be basically the opposite of the bits that were correct the first time. The bits that are wrong both ways are the places where the actual zeros need to go.

Finally, my general approach to these xor challenges, especially with the "x" part of the key, was to visualize the decryptions for different k values, for a given x, and manually modulate x until certain patterns in the output resolved. I found it was a bit like tuning a radio - when your x value is approximately correct, you get some good clues that you're close to the right value. The different k values all being shown particularly helps, because the incorrect k values actually give useful data when you're near the right x value (they look like ascii text too, for the most part, and an incorrect x leads to the message getting kind of skewed across the table).

I also found that, at the places where you should insert zeros, for the most part there was an obvious jump in the chart. So visualizing these charts (just using different k values for each line on the screen) was really quite effective, and more interesting that brute force.

[the_impaler]

Wow!
I am impressed by the analysis! Really.
Brute force approach doesn't have to start from the beginning of the string.
I looked through the sequence and found that there are 0 in it which meant that these were 0 as last digit, not first. This was a good starting point. So I extracted 3 short substrings between those numbers and from the length of the substring there could be only even numbers of 0 missing - I had only 4 different variations of each substring. Again, brute force approach cares only about validity of the resulting characters - so I made 4**3 combined strings. I used brute force on the list of substrings to get a list of possible values and it was fast - substrings are rather short. Surprisingly I got only 1 pair , I was expecting that I would get a dozen that I would need to check manually.

[Captain Failure]

The XOR 3 cipher has the nice weakness that you can quickly guess a valid pair of b and x based on the MSBs of the encrypted string. The longer the message, the more precise the guess will be. That'll crack XOR 3 in less than 1 second.

For Broken XOR 3 I reused this code and extended the XOR 3 cracker to report the number of the character that failed first. On top of this ran a recursive binary search for all possible un-broken cipher strings. The search algo reacts on the failing character number and skips all subsequent recursions for this level. It's quite fast this way and revealed the answer within a minute or so.

[laz0r]

Actually, the 0s in the ciphertext might be the start of 00, so you can't assume a540 is a5 40, it may be ...a 54 00

[Captain Segfault]

My approach was accidentally fast -- due to a bug in my code during my first pass I only considered the first 30ish hex digits. That turned up a string "the answer tod".

I tried "tod" and it didn't work, then I noticed the bug in my code and fixed it. Then I realized I'd found the key, so I might as well hard code it in so I'm only searching for missing zeros.

[DamaTeq]

my approach is pretty fast (it takes only a few secs) but it is not perfect.

btw, don't look at the goto's hehe

Code: Select all

class FalsePositive
{
    public int Index { get; set; }
    public int Length { get; set; }
    public byte Key { get; set; }

    public FalsePositive(int index, int length, byte key)
    {
        Index = index;
        Length = length;
        Key = key;
    }
}

static void Main(string[] args)
{
    Console.BufferWidth = I200;

    String encoded = "8d541...57e3b1";

    Parallel.ForEach(Enumerable.Range(0, 0xFF), intB1 =>
    {
        byte b1 = (byte)intB1;
        for (byte x = 0; x < 0xFF; x++)
        {
            StringBuilder sb = new StringBuilder();
            byte key = b1;
            bool first = true;

            List<FalsePositive> false_pos = new List<FalsePositive>();

            for (int i = 0; i < encoded.Length - 1; i += 2)
            {
                bool check0 = true;
            last_false_positve:
                byte c = HexOperations.HexStringToByteArray(encoded.Substring(i, 2))[0];

                byte chck = c;
                if (check0) chck >>= 2;//start with checking 0
            try_again_without_leading_0:
                byte decoded = (byte)(chck ^ key);

                #region break if decoded is non readable ascii
                if (decoded < 32 || decoded > 122)
                {
                    if (check0)
                    {
                        chck = c;
                        check0 = false;
                        goto try_again_without_leading_0;
                    }
                    else if (false_pos.Count > 0)
                    {
                        var last = false_pos.Last();
                        i = last.Index;
                        sb = new StringBuilder(sb.ToString().Substring(0, last.Length));
                        key = last.Key;
                        false_pos.Remove(last);

                        goto last_false_positve;
                    }
                    if (first) goto b1_not_ok;
                    goto x_not_ok;
                }
                else if (check0)
                {
                    false_pos.Add(new FalsePositive(i, sb.ToString().Length, key));
                    i--;
                }
                #endregion

                first = false;
                key = (byte)((key + x) % 256);
                sb.Append((char)decoded);
            }
            Console.WriteLine("b1 = {0}, x = {1} \t {2} ", b1, x, sb);
        x_not_ok: ;
        }
    b1_not_ok: ;
    });
    Console.WriteLine("Ready ...");
    Console.ReadLine();
}

€dit: I made a more readable solution, which is (in my opinion) a littlebit slower than the one above.

Code: Select all

class FalsePositive
{
    public int Index { get; set; }
    public string Answer { get; set; }
    public byte Key { get; set; }

    public FalsePositive(int index, string answer, byte key)
    {
        Index = index;
        Answer = answer;
        Key = key;
    }
}

static void Main(string[] args)
{
    Console.BufferWidth = 200;
    String encoded = "8d541...57e3b1";

    Parallel.ForEach(Enumerable.Range(0, 0xFF), intB1 =>
    {
        byte b1 = (byte)intB1;
        for (byte x = 0; x < 0xFF; x++)
        {
            StringBuilder answer = new StringBuilder();
            byte key = b1;
            bool check_b1_wrong = true;

            List<FalsePositive> false_pos = new List<FalsePositive>();

            for (int i = 0; i < encoded.Length - 1; i += 2)
            {
                byte encodedByte = HexOperations.HexStringToByteArray(encoded.Substring(i, 2))[0];
                //Try to decode with a leading 0 first
                byte decodedByte = decode((byte)(encodedByte >> 2), key);
                if (isReadableASCII(decodedByte))
                {
                    //This could be a false positive
                    false_pos.Add(new FalsePositive(i, answer.ToString(), key));
                    i--;
                }
                else
                {
                again:
                    decodedByte = decode(encodedByte, key);
                    if (!isReadableASCII(decodedByte))
                    {
                        if (false_pos.Count > 0)
                        {
                            var last = false_pos.Last();
                            false_pos.Remove(last);

                            //Restore old values
                            i = last.Index;
                            encodedByte = HexOperations.HexStringToByteArray(encoded.Substring(i, 2))[0];
                            answer = new StringBuilder(last.Answer);
                            key = last.Key;

                            goto again;
                        }
                        else if (check_b1_wrong) return;
                        else break;
                    }
                }

                check_b1_wrong = false;
                key = (byte)((key + x) % 256);
                answer.Append((char)decodedByte);

                if (i + 2 >= (encoded.Length - 1))
                {
                    Console.WriteLine("b1 = {0}, x = {1} \t {2} ", b1, x, answer);
                }
            }
        }
    });
    Console.WriteLine("Ready ...");
    Console.ReadLine();
}
static byte decode(byte encoded, byte key)
{
    return (byte)(encoded ^ key);
}
static bool isReadableASCII(byte c)
{
    return !(c < 32 || c > 122);
}

[ohcibi]

After some hints in the not solved forum, I found out that just bruting the xor3-algorithm over the string brings me to "the answer to this broken challenge is". (My algorithm stopped trying with the current X and b if there was one char that doesnt makes any sense).

For broken xor I then split the string until the first 70 bytes (the "the answer to..." part), treating it as it was xor3. I then knew that I have found the right x and b and could try the rest of the string a bit less strict.

I started by trying if the first two chars make any sense (i.e. are in range [32,122]). If yes, i'll decrypt them and add them to the string; if not I add a 0 to the first char, decrypt it and then add it to the string, continueing with the second char as it was the MSB of the next byte and applying the same logic until I hit the end of the string.

The solution then was "the answer to this broken challenge is `solution`, so just X<some-more-wrong-chars>". As there is a wrong X appearing and X is a char in [32,122] my algorithm fails then, but it as sufficient to find the solution.

I did all this in ruby.