[math-fun] A Permutation Cipher Text
https://0x0.st/zwRU.txt Easy to brute force if you get the gist of the permutation scheme but looks difficult to reverse engineer otherwise. Codebreaking algorithms? --Brad
On 9 Oct 2019 at 20:05, Brad Klee wrote:
Easy to brute force if you get the gist of the permutation scheme but looks difficult to reverse engineer otherwise.
I remember reading in a issue of Cryptologia, prolly 40 years ago, about an unbreakable permutation cipher. It's point was you permute the *bits* and then regroup them into characters for transmission. They said that you can count the # of 1s and 0s and simply add a block of 1s or 0s at the end so the cleartext is exacts 50/50 1s and 0s. Then permute that. As I remember the argument, since *every* clear text has the same bit-level distribution, in theory any cipher text could, depending on the permutation, become *any* clear text and so it was pretty much unbreakable. [I think the idea was even if you manages to "unscramble" the bits into a clear text, there was no way to tell if it was the *right* clear text. I never saw any mention of it again so I guess it isn't of general interest [or didn't work, although I'm not sure why not]. /Bernie\ Bernie Cosell bernie@fantasyfarm.com -- Too many people; too few sheep --
The main problem with a bit-permutation cipher is that it needs a very large key; if you want all n! permutations of an n-bit message to be possible, then the key has to be log(n!) bits long, which is longer than the plaintext. And even with such a large key you have the problem that known plaintext/ciphertext pairs leak a lot of information; after seeing one such pair there are only n/2 bit positions that might have been mapped to (say) position 1, after k known pairs there are only n/2^k possibilities for each position. Yet another problem (although it does not matter for many applications) is that you have to have the entire plaintext in hand before you can start encrypting, and must have the entire ciphertext in hand before you can start decrypting. On Wed, Oct 9, 2019 at 7:53 PM Bernie Cosell <bernie@fantasyfarm.com> wrote:
On 9 Oct 2019 at 20:05, Brad Klee wrote:
Easy to brute force if you get the gist of the permutation scheme but looks difficult to reverse engineer otherwise.
I remember reading in a issue of Cryptologia, prolly 40 years ago, about an unbreakable permutation cipher. It's point was you permute the *bits* and then regroup them into characters for transmission. They said that you can count the # of 1s and 0s and simply add a block of 1s or 0s at the end so the cleartext is exacts 50/50 1s and 0s. Then permute that.
As I remember the argument, since *every* clear text has the same bit-level distribution, in theory any cipher text could, depending on the permutation, become *any* clear text and so it was pretty much unbreakable. [I think the idea was even if you manages to "unscramble" the bits into a clear text, there was no way to tell if it was the *right* clear text.
I never saw any mention of it again so I guess it isn't of general interest [or didn't work, although I'm not sure why not].
/Bernie\
Bernie Cosell bernie@fantasyfarm.com -- Too many people; too few sheep --
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
For reference, here is the pseudo code: ========================================================== Input: Block Size M, (M^n)X(M^n) cleartext, read and write keys. Output: (M^n)X(M^n) ciphertext. ========================================================== 1. Read & Write key generates a pair of MxM space-filling Z-function definitions, along with level-0 axioms. 2. From axioms, generate Read and Write curves over (M^n)X(M^n) domain. 3. Read plaintext from matrix to vector using Read curve. 4. Write vector back to matrix using Write curve. ========================================================== My main worry is that, when M is known, it may be possible to design a recursive attack, which unscrambles block by block. However, If K is the number of possible permutations per block, the number of valid permutations is: K^(M^2 + M^4 + M^6+ ... + M^(2*(n-1)) ) For M=2, n=6, this is already K^1364. This prohibits brute force, but a better algorithm could possibly try to identify the pair of Z-functions as it goes. This runs into a difficulty that each unscrambled block has a many-to-one correspondence with pairs of replacement symbols. Seems unlikely, but I am not an expert attacker. Now let K be the number of replacement symbols, then an upper bound for the number of viable Z-functions is K^(K*M^2), which is usually smaller than the above, but still astronomically large. Meanwhile the key is a vector containing at worst K*M^2 integers from 1-K. Said another way: the number of valid permutations is roughly K^keylength. As I said earlier, the ciphertext above is relatively easy to break, because both read and write functions come from a set of 97: https://github.com/bradklee/Docs/blob/master/TwoByTwoZFs.pdf So there are only 97^2 = 9409 alternatives to check. However, my estimate from a few days ago of 10^27 functions on 2x2 is certainly too large to brute force attack. If even this is not enough, we could go higher to M=3, 4, etc. It is also a "weakness" that the permutation scheme may leave some portions of the text unencrypted. This could probably be avoided by engineering rule space and restricting key choice. But why should we worry? It adds to suspense and curiosity, when some small fragments of the message are immediately available. In the previous example, we are left to wonder about the "stronghold", which adds to urgency. Any more thoughts on attacking? A hyperlink to the decryption? --Brad On Wed, Oct 9, 2019 at 9:27 PM Michael Collins <mjcollins10@gmail.com> wrote:
The main problem with a bit-permutation cipher is that it needs a very large key; if you want all n! permutations of an n-bit message to be possible, then the key has to be log(n!) bits long, which is longer than the plaintext. And even with such a large key you have the problem that known plaintext/ciphertext pairs leak a lot of information; after seeing one such pair there are only n/2 bit positions that might have been mapped to (say) position 1, after k known pairs there are only n/2^k possibilities for each position. Yet another problem (although it does not matter for many applications) is that you have to have the entire plaintext in hand before you can start encrypting, and must have the entire ciphertext in hand before you can start decrypting.
On Wed, Oct 9, 2019 at 7:53 PM Bernie Cosell <bernie@fantasyfarm.com> wrote:
On 9 Oct 2019 at 20:05, Brad Klee wrote:
Easy to brute force if you get the gist of the permutation scheme but looks difficult to reverse engineer otherwise.
I remember reading in a issue of Cryptologia, prolly 40 years ago, about an unbreakable permutation cipher. It's point was you permute the *bits* and then regroup them into characters for transmission. They said that you can count the # of 1s and 0s and simply add a block of 1s or 0s at the end so the cleartext is exacts 50/50 1s and 0s. Then permute that.
As I remember the argument, since *every* clear text has the same bit-level distribution, in theory any cipher text could, depending on the permutation, become *any* clear text and so it was pretty much unbreakable. [I think the idea was even if you manages to "unscramble" the bits into a clear text, there was no way to tell if it was the *right* clear text.
I never saw any mention of it again so I guess it isn't of general interest [or didn't work, although I'm not sure why not].
/Bernie\
Bernie Cosell bernie@fantasyfarm.com -- Too many people; too few sheep --
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Another similar scheme produces the cipherimage: https://0x0.st/zxaU.png , with a decryption key: "hxxstvjhdcvrcmhuhphufxhdshirjpgjblcgrovfuhisoweubrviplbcpulvflwpdlgjjhidhktchvtpjlhwtfstnkdfowss" from a permutation space of size ~10^132, as in: https://0x0.st/zxaI.pdf . Any thoughts? --Brad On Wed, Oct 9, 2019 at 8:05 PM Brad Klee <bradklee@gmail.com> wrote:
Easy to brute force if you get the gist of the permutation scheme but looks difficult to reverse engineer otherwise.
Codebreaking algorithms?
--Brad
participants (3)
-
Bernie Cosell -
Brad Klee -
Michael Collins