# Base64 with shuffled alphabet

I have a base64 'cipher' text. I know that in clear text is a hidden XML document (I know nothing about its structure), but the base64 alphabet was somehow shuffled. Is there any smart way, how to detect the modified alphabet better than checking all 64! permutations? I can slightly reduce 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 are still 62! permutations which are still not computable.

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

• 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 Dec 13 '14 at 4:34
• 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. Dec 13 '14 at 4:36
• 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. Dec 13 '14 at 12:00
• Related question
– fgrieu
Jan 10 '20 at 8:32
• Also related Jan 11 '20 at 9:44

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.