1
$\begingroup$

I have a base64 'cipher' text, I know that in clear text is a hidden xml document (I do not know nothing about its structure), but the base64 aplhabet was somehow shuffled. Is there any smart way, how to detect the modified alphabet better than checking all 64! permutations? I can reduce slightly the number of permutations by using the knowledge that xml document starts (without doctype, just root element) with opening tag (character '<') and ends with '>'. But there is still 62! permutations which is still not computable.

I have also tried to infer some other characters, but as the tags may be arbitraty long and the content may be any character, I don't see much space for frequence analysis.

$\endgroup$
  • 1
    $\begingroup$ There are several published base64 variations, try those first. I even have my own variant (url/filename safe, no padding). The value used for < may indicate if a known variant is used $\endgroup$ – Richie Frame Dec 13 '14 at 4:34
  • 1
    $\begingroup$ If you decode from 6 to 8 bit raw values, you may be able to perform a frequency analysis. This would require the entire 64 character alphabet to be known, and for you to assign arbitrary values to them. $\endgroup$ – Richie Frame Dec 13 '14 at 4:36
  • 1
    $\begingroup$ You know far more than that. For instance XML is text, so expect printable characters. There will be a lot of greater than and less than signs but also the equals operator and quotes are likely abundant because of tag attributes. And then there is the whitespace as well - lots of spaces and/or tab characters and possibly end of lines (using the double \r\n used for Windows, so if they are present you have two characters in a row!). Of course the bits are distributed over the 3 bytes encoded as 4 characters, but that could be advantageous as well. $\endgroup$ – Maarten - reinstate Monica Dec 13 '14 at 12:00
1
$\begingroup$

A well-formed XML document is subject to all sorts of constraints.

You can incorporate these constraints into a function that checks a base64 substitution key by looking for invalid syntax, such as improperly nested tags, or a tag name containing control characters, white space, or any of the characters !"#$%&'()*+,/;<=>?@[\]^`{|}~, or that starts with a dot, hyphen or numeral.

Combine this with a backtracking search algorithm, and with a bit of luck you should obtain a solution within a reasonable amount of time.

If it turns out to be too slow, there are other assumptions you could make. For example, most XML documents use only printable ASCII characters in their tag names, and often contain white space after closing tags.

$\endgroup$
  • $\begingroup$ Most base64 variants will keep a-z and A-Z and 0-9 for consecutive values. $\endgroup$ – Henno Brandsma Dec 13 '14 at 13:17
  • $\begingroup$ @HennoBrandsma This is about a shuffled base 64 alphabet, according to the question. I presume that the last two characters of the alphabet aren't just targetted. $\endgroup$ – Maarten - reinstate Monica Feb 7 '17 at 15:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.