How to perform frequency analysis of a substitution cipher using a Base64 alphabet

Question

Let's imagine a cipher that works like the following:

1. Plaintext is encoded to Base64.
2. The characters in the encoded plaintext are substituted with a randomly shuffled character set(A-z, 0-9, -, _, =). The shuffled alphabet is, in essence, the key.

Not particularly complex or even secure. But...

What if I wanted to do frequency analysis?

For example, "RUNFORYOURLIFE" when encoded in Base64 is:

UlVORk9SWU9VUkxJRkU=

When the character set is shuffled, the final cryptext can look something like this:

xv24DYG9qxG2xYg6DYxf

The key being:

yhAc5bTOWeYvBXCpVuoMJLdg8P1jHN3ZIsi67SrK4E_D9-x2qRQmnlkwUaFt0G=zf

Which is a shuffled version of:

abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789-_=

Let's also assume that the character set in subsequent messages is in the same order(ie the key is re-used).

Since the bytes are basically split up resulting in different character units that may or may not correspond, is frequency analysis still feasible? Does encoding plaintext this way before encryption add any form of security?

My question mostly pertains to longer messages, as my example may be too short for any sort of real analysis.

Answer 1

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.

Answer 2

The encryption is weak

This encryption is more susceptible to frequency analysis than original "substitution ciphers" because the frequency tables should be much more Non-uniform. In my opinion, it should be less secure than substitution cipher although the key space is much much bigger (compare $64!$ to $26!$).

Some evidences of the weakness

If I assume that the plaintext is an ALL-CAPS message then the first Base64 encoded character should be any of "Q, ""R", "S", "T", "U", "V", "W". And apparently this should be repeated for all $4n$-th characters. As you can see your short encoded message has one of these 7 characters on $4\times n$ positions:

UlVORk9SWU9VUkxJRkU=

The frequency of each of these characters on $4\times n$ positions can be easily calculated. If the input text is english the frequency of each of "R", "S", "T", "U", "V", "W" on $4\times n$ positions are as follow:

Q = 12.44% (A+B+C)
R = 21.20% (D+E+F+G)
S = 13.98% (H+I+J+K)
T = 20.66% (L+M+N+O)
U = 14.31% (P+Q+R+S)
V = 15.13% (T+U+V+W)
W = 2.19% (X+Y+Z)

So the substituted characters should be easy to guess.

Additionally, there is a very good chance (roughly 66%) that the last character of the encoded plaintext is "=" and if the last two characters of ciphertext are identical almost certainly (more than "99%") those are substitutions of "==".

How to attack the encryption with Ciphertext-Only-Attack

These are the steps:

1. Break a huge corpus in the target language into parts with almost the same size as the original plaintext should be.

2. Encode these parts into Base64.

3. Calculate the frequency table for each of $4n$, $4n+1$, $4n+2$, $4n+3$ positions using the encoded corpus.

4. Using heuristic algorithms (e.g. Genetic Algorithm) and NLP statistical analysis guess keys which would result in decryptions closer to human language text.

5. Human's intelligence might help in the last step for full decryption of the ciphertext.

Answer 3

Here is one way I could do frequency analysis. First, assume the original text uses one byte (8 bits) for each character (this is without loss of generality, as I believe a similar construction could for other encodings). Second, note that base64 character represents 6 bits. This mean that the first 4 base64 characters encodes the first 3 bytes of plaintext, i.e, the 3 first characters (since 4*6 = 3*8). The next 4 base64 characters will then encode the next 3 characters of plaintext and so on.

Using this observation it is easy to do frequency analysis. Just compute the frequencies of all 3 character strings of plaintext, and the frequencies of all 4 character strings of ciphertext. Then do a frequency analysis attack as usual only keeping in mind that 3 characters of plaintext corresponds to 4 characters of ciphertext.

Note, there may be smarter ways of doing it but at least this is one.