I'll assume that the plaintext consists entirely of capital ASCII letters as in the example. This implies the high 3 bits of each byte of plaintext are 010
.
It is useful to visualize how 3 consecutive bytes of plaintext map to 4 consecutive Base64 characters.

1. Frequency analysis of the last character of 4-char blocks in ciphertext
We see there is a straight mapping from the last of every three characters in the plaintext to the last of every four characters in the Base64 encoding (notice that the characters in Base64 codes the 5 lower bits of the character in the plaintext, on the right of the above picture, which are characteristic of the letter). It follows that we can perform single-letter frequency analysis on the ciphertext restricted to the last character of every block of four characters. If among the characters kept the last one is different from all the others, it likely represents =
in Base64; all the other characters kept should be among 26 characters (else the assumption made above is disproved). The mapping, ordered by decreasing expected letter frequency in English plaintext (according to this source) is:
Plaintext Plaintext Plaintext Plaintext
| Base64 | Base64 | Base64 | Base64
| | Frequency | | Frequency | | Frequency | | Frequency
E F 0.12702 H I 0.06094 W X 0.02360 K L 0.00772
T U 0.09056 R S 0.05987 F G 0.02228 J K 0.00153
A B 0.08167 D E 0.04253 G H 0.02015 X Y 0.00150
O P 0.07507 L M 0.04025 Y Z 0.01974 Q R 0.00095
I J 0.06966 C D 0.02782 P Q 0.01929 Z a 0.00074
N O 0.06749 U V 0.02758 B C 0.01492
S T 0.06327 M N 0.02406 V W 0.00978
and with a kilobytes of ciphertext, it is likely that the most frequent character in the fraction of the ciphertext kept corresponds to E
in the plaintext, thus F
in the Base64.
2. Frequency analysis of the first character of 4-char blocks in ciphertext
There is a function from the first of every three characters in the plaintext to the first of every four characters in the Base64 encoding; we can perform a variant of single-letter frequency analysis on the ciphertext restricted to the first character of every block of four characters. The characters kept should be among 7. Expected frequency is
Plaintext Base64 Frequency
DEFG R 0.21198 = 0.04253 + 0.12702 + 0.02228 + 0.02015
LMNO T 0.20687 = 0.04025 + 0.02406 + 0.06749 + 0.07507
TUVW V 0.15152 = 0.09056 + 0.02758 + 0.00978 + 0.02360
PQRS U 0.14338 = 0.01929 + 0.00095 + 0.05987 + 0.06327
HIJK S 0.13985 = 0.06094 + 0.06966 + 0.00153 + 0.00772
ABC Q 0.12441 = 0.08167 + 0.01492 + 0.02782
XYZ W 0.02198 = 0.00150 + 0.01974 + 0.00074
It happens that the set of Base64 characters in the second method is a subset of the set for the first; this allows cross-checking the guesses.
3. Frequency analysis of the third character of 4-char blocks in ciphertext
There is a function from the second of every three characters in the plaintext to the third of every four characters in the Base64 encoding; we can perform a variant of single-letter frequency analysis on the ciphertext restricted to the third character of every block of four characters. The characters kept should be among 16 (except perhaps the last, which may map to =
in the Base64 character set). Expected frequency is
Plaintext Plaintext
| Base64 | Base64
| | Frequency | | Frequency
EU V 0.15460 = 0.12702 + 0.02758 HX h 0.06244 = 0.06094 + 0.0015
DT R 0.13309 = 0.04253 + 0.09056 GW d 0.04375 = 0.02015 + 0.0236
CS N 0.09109 = 0.02782 + 0.06327 L x 0.04025
IY l 0.08940 = 0.06966 + 0.01974 FV Z 0.03206 = 0.02228 + 0.00978
AQ F 0.08262 = 0.08167 + 0.00095 M 1 0.02406
O 9 0.07507 P B 0.01929
BR J 0.07479 = 0.01492 + 0.05987 K t 0.00772
N 5 0.06749 JZ p 0.00227 = 0.00153 + 0.00074
Several of the characters in the Base64 character set for this third method also occur in the first two methods; this allows cross-checking the guesses.
Frequency analysis of bigrams
We can also consider bigrams in plaintext occurring in the last character of a block of three, and the first character of the next block; and how they map to bigrams in Base64 occurring in the last character of a block of four, and the character following. We can compute the common bigrams obtained in the ciphertext by keeping (as first character of bigram) the last character of a block of four, and (as other character of bigram) the next character; and compare to common bigrams in English (adding frequencies of up to 4 bigrams as we did in the second method).
This also works for bigrams in plaintext occurring in the last two characters of a block of three, mapping to bigrams in Base64 occurring in the last two characters of a block of four; again well be comparing to the frequencies of common bigrams in English (adding frequencies of up to 2 bigrams as we did in the third method).
Common/guessable trigrams in plaintext to finish the analysis
The above will allows recovering the mapping to ciphertext of no more than 36 out of 65 characters used in Base64. For the others, we should guess some aligned blocks of three characters in the plaintext based on what we already know and common English words, transcode these blocks of three plaintext characters to four Base64 characters, see if there is a contradiction with the established mapping of Base64 to ciphertext, and if not cautiously apply the new guesses.
Automated cryptanalysis
As rightly pointed in that other answer, heuristic algorithms can handle the search automatically. Still, I guess that the first three techniques (which can be adapted to different plaintext alphabets, e.g. with space, lowercase..) will greatly simplify the heuristic.
UlVORk9SWU9VUkxJRkU=
can't lead tok9U9VUJx=RWUOSkVUklR
by character substitution. For example, the fourU
in the original are substituted with the differentk
,R
,O
andl
. $\endgroup$U
(resp.O
R
S
) in first (resp. fourth, fifth, eighth) position of the Base64? How does the expected frequency of letters in plaintext translate to expect frequency in first, fourth.. (resp third, sixth..) letter of the Base64? What about digrams in third and fourth, sixth and seventh.. position in plaintext and relation to digrams in fourth and fiveth, eighth and nineth.. position in the Base64? $\endgroup$