0
$\begingroup$

I've looked at this crypto SE post but it doesn't address the how of my question.


I've been interested in cryptography for some time. I wrote a relatively basic cryptosystem in Python that uses base conversion as one of its layers of security (I don't actually use it for anything, don't worry). I've heard time and time again that encoding is not encryption, and in its most basic form, I understand this completely. But why is it still not encryption if we use a secret symbol set?

Example

We can easily convert from decimal to hex because we know that the decimal symbols are 0123456789 in that order, and the hex symbols are 0123456789ABCDEF in that order. There is no encryption in this. But what if we shuffled the hex symbols? Like so:

$$\\\\$$

Decimal plaintext: 69420

Shuffled hex symbols: 87FC9ED61543B20A (secret!)

Encode using shuffled hex symbols: 69420 -> 78AFB

$$\\\\$$

If you didn't know the shuffled hex symbol set, how would you crack this encoding? In this case we have $16! \approx 10^{13}$ possible hex symbol sets which is not hard to brute-force.

EDIT: Actually I realized we can extract the hex symbols by incrementing the plaintext by 1 and encoding 16 times, but anyway later we shuffle the plaintext symbols which I think destroys the ability to "increment by 1" - correct me if I'm wrong.

But what if our encoding used larger symbol sets, AND we also shuffle the plaintext symbols before encoding?

For example, if we're encoding from the first 256 Unicode symbols to the 94 printable non-whitespace ASCII symbols, then the number of possible ciphertext symbol sets is $94! \approx 10^{146}$ which is difficult to brute-force; and if we shuffle the 256 Unicode symbols before encoding, it adds another obstacle. How would one crack this?

The big question

I know base conversion is slow. I'm not asking why it's not practical, I'm asking how the above system can be cracked mathematically/algorithmically without knowing the key, which is the orderings of the ciphertext and plaintext symbol sets.


P.S.

My humble Python cryptosystem, which is very similar to the one described above, if you're curious: https://github.com/SamerN88/DRE.94

$\endgroup$
5
  • 3
    $\begingroup$ Well, start reading a basic cryptography book. You reinvented the Substitution cipher which is broken 1000 years ago by frequency analysis. $\endgroup$
    – kelalaka
    Oct 3, 2022 at 23:26
  • $\begingroup$ @kelalaka Base conversion is not the same as substitution cipher, hence basic frequency analysis would not work. Test it yourself. The most basic way to see this is like this: $$\text{hex}(111111111111) = \text{19DEBD01C7}$$ Clearly the high frequency of 1s was not reflected at all in the output. I took a cryptography course that covered substitution ciphers and frequency analysis (among other things like RSA, Diffie-Hellman, etc.), but it was more or less introductory. That's the extent of my knowledge. $\endgroup$
    – SNN
    Oct 4, 2022 at 0:39
  • $\begingroup$ @kelalaka I imagine a way one can apply frequency analysis on base conversion is by encoding the ciphertext using any symbol set as long as it has the same base as the original plaintext. Then just apply normal frequency analysis. But this assumes you know the base of the plaintext symbol set. $\endgroup$
    – SNN
    Oct 4, 2022 at 1:12
  • $\begingroup$ Base conversion does not prevent attackers - they can find some way to bypass it, what would you do against known-plaintext attackers that can easily reveal your key? $\endgroup$
    – kelalaka
    Oct 4, 2022 at 5:25
  • $\begingroup$ @kelalaka I never claimed base conversion prevents attackers, obviously this isn't an unbreakable system. My question asks how would one attack the system I described without knowing the key. You mentioned known-plaintext attack, sure, but that assumes you have a known plaintext. And still, I think you'd need to know the base of the plaintext, although I could be wrong there. What if you don't have any of that? $\endgroup$
    – SNN
    Oct 4, 2022 at 18:56

1 Answer 1

0
$\begingroup$

Assumptions

You should assume that the attacker knows the algorithm and the only unknown is the key. In your case they key can be a combination of the base and the substitution table.

You should assume that the attacker can apply your encryption to any messages the attackers wants (e.g. the attacker tricks you out to encrypt some specific messages) and knows the encryption results.

Why are they important? Because cryptography is usually required in real life cases, e.g. when millions of messages need to be encrypted. And if the data are of big importance, the attacker finds usually ways to know about the software and hardware a lot of everything. And the only unknown part remains the key.

If you say these assumptions do not hold, then the question not about mathematics and cryptographic algorithms, and thus it is off topic on this.

Chosen-plaintext attack

The attacker creates some random message and applies your encryption. Then changes a single bit in the original message and applies your encryption. According to your algorithm a single bit in the resulting message will be changed. Then the attacker changes the 2nd bit and applies the encryption. again. And so on. If the changed bits in the encrypted message are close to each other within let say 5 bits, the base is 32. If there will be groups of 6 bits, the base is 64, etc. Thus the base will be detected after a very small number of operations.

After the base is determined, then only a single step more is needed. The attacker will create a message consisting of all possible values in the given base and encrypt it. The encrypted message will be actually the substitution table.

$\endgroup$
14
  • $\begingroup$ I need some clarification. When you say change a bit then change the 2nd bit, do you mean flip the 1st bit of the plaintext and encrypt, then go back to the original plaintext and flip only the 2nd bit and encrypt, then flip only the 3rd bit and encrypt, etc...? Also, when you say the base is revealed, which base are you referring to? The plaintext is treated as a base-M number and the ciphertext is treated as a base-N number, as this is base conversion from M to N. Which base is revealed, M or N? Remember, $M≠N$. $\endgroup$
    – SNN
    Oct 6, 2022 at 2:16
  • $\begingroup$ 1) I mean flipping the bit in the original message: Original message with flipped 1st bit, original message with flipped 2nd bit etc. $\endgroup$
    – mentallurg
    Oct 6, 2022 at 2:29
  • $\begingroup$ 2) The original message is just a sequence of bits. It does not depend on any base. The word "base" makes only sense for interpretation or transformation of data. If you apply base 16, you will get representation of the original message as a hexadecimal digits. If you apply base 256, you will get representation as ASCII characters, etc. If your transformation includes 2 bases - split the sequence of bits into groups according to base M and transform using base N - this does not change anything in the attack. It will just take a bit more tests, but will be still very quick. $\endgroup$
    – mentallurg
    Oct 6, 2022 at 2:36
  • $\begingroup$ Forgive me, I'm sure you're right, but I'm just not seeing it. I understand that the message is just a sequence of bits independent of base; but to even have a notion of base conversion, we need agreed-upon symbol sets. If we don't know the symbol sets, we can't encode, and that's where I have trouble reconciling your attack. Let me give you an example and you show me step by step how to crack it. I will try to use simplified parameters (see next comment). $\endgroup$
    – SNN
    Oct 6, 2022 at 4:50
  • $\begingroup$ Our key is both the plaintext & ciphertext symbol sets. Let's say we convert from hex to decimal:$$\\$$ Standard hex symbol set: 0123456789ABCDEF$$\\$$ Shuffled hex symbol set: D934CA26B71805EF (1st part of key)$$\\$$ Standard decimal symbol set: 0123456789$$\\$$ Shuffled decimal symbol set: 9716403258 (2nd part of key)$$\\$$ Key: (D934CA26B71805EF, 9716403258) (secret!) $$\\$$ Plaintext (hex): ABC123$$\\$$ ENCRYPT - convert using key symbol sets: $$\\$$ Ciphertext (decimal): 5786210$$\\$$ Since this is a known-plaintext attack, the plaintext is not secret. $\endgroup$
    – SNN
    Oct 6, 2022 at 4:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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