13
$\begingroup$

I have tried out an encryption method, in which I swap bits in the text.

The text length is N bit, then I generate several random number pairs in the range 0..N-1, as [n,k] pairs. After that I swap the n-th and k-th bits in the message, if they are different, of course. After several swap the message becomes unreadable.

The message can be decrypted by applying the swaps in the reverse order.

Can this be a good encryption method or is it equivalent with the usual XOR cipher, or even weaker?

For example I can generate the random number pairs with a pseudo random number generator, with a starting seed. And the seed can be obtained from a passphrase, for example the integer hash of the passphrase. Then I can use the passphrase to encrypt the message this way, and the same passphrase for decrypting, as the random number pairs will be the same again, due the the same seed applied at the start.

$\endgroup$
  • 23
    $\begingroup$ Given that the hamming weight doesn't change, that's a lot of leakage right there. $\endgroup$ – Maeher Jun 1 at 20:39
  • 5
    $\begingroup$ And only swapping when the values are not identical is dangerous too. It is almost certainly going to leak timing information. It will happen pretty fast, but there are tricks to slow things down. What you seem to define is a transposition cipher; those are known cipher variants, but generally transposition is just one of the methods that make modern ciphers secure. $\endgroup$ – Maarten Bodewes Jun 1 at 20:51
  • $\begingroup$ And what about swapping the two chosen bits, and negating one of them at the same time? $\endgroup$ – Konstantin Jun 1 at 21:24
  • 3
    $\begingroup$ Separate question to consider with a scheme like this: How do you plan on transmitting the correct sequence of swaps? If it's static, then anyone who can decrypt one message can decrypt every one. If it's random, how will the receiver know what it is without transmitting it alongside the message? If it's distributed ahead of time, how is it different from a One-time Pad? $\endgroup$ – Bobson Jun 2 at 18:26
  • $\begingroup$ @Bobson when something "new" is discussed, one can safely assume that every aspect not explicitly mentioned is something standard. The sequence of the swaps is simply the key and we know a lot of key management schemes. $\endgroup$ – fraxinus Jun 3 at 7:03
35
$\begingroup$

First problem is you're not specifying at all how many swaps you need to do for a given message length, other than saying it's "several." For an $n$-bit messsage there are $n!$ ways of rearranging its bits, gives a lower bound of $\mathrm{log}_2(n!) = \sum_{i=1}^{n}\mathrm{log}_2(i)$ bits for on how much pseudorandomness you'll need. Rather than analyze a precise number of rounds your random swaps method needs to achieve a good result, however, it's just simpler to substitute in a Fisher-Yates shuffle that'll fairly permute an $n$-item sequence in $n$ steps.

But whatever you do, even if we assume true random bit permutations, the technical answer is that this is straightforwardly insecure because an adversary can easily and reliably distinguish encryptions from random strings by looking whether the number of ones vs. zeroes is the same as their chosen plaintexts. A special case of this is that any message that's only zeroes or only ones encrypts to itself.

Even if we assume the attacker doesn't get to choose plaintexts, they can use this property to test whether a given ciphertext could be the encryption of some plaintext they guess at. Take for example the binary ASCII codes for these strings:

HAHA ===> 01001000 01000001 01001000 01000001 ===>  8 ones
YEAH ===> 01011001 01000101 01000001 01001000 ===> 11 ones
NOPE ===> 01001110 01001111 01010000 01000101 ===> 14 ones

If I see a ciphertext with 11 ones I can tell that it's definitely neither HAHA nor NOPE, but could still be YEAH.

| improve this answer | |
$\endgroup$
  • 6
    $\begingroup$ $\log(n!) \approx n \log n$, by Sterling's approximation (this is actually where the $O(n \log n)$ bound for comparison sort comes from) $\endgroup$ – BlueRaja - Danny Pflughoeft Jun 2 at 9:13
  • $\begingroup$ Kinda expensive, but man I can imagine this procedure driving cryptographers batty if it's interwoven between rounds of a block cipher. $\endgroup$ – Joshua Jun 4 at 3:53
5
$\begingroup$

If an attacker has a way of getting you to encrypt a message of their choosing this way, it would be trivial break. Imagine you swap each bit randomly with another bit. If you have a message of 800 bits an attacker could discover the entire pattern with 11 attempts. The attacker could set bits 0-399 to 1 and map those to 1s in the encrypted message and the 0s to the 0s. Then you could send bits 0-199 and 400-599 to 1 and try again. The ones that were 0 in the first attempt and 1 in the second attempt would map to 400-599, the ones that were 0 in both would be 600-799, the ones that were 1 in both would map to 0-199, and the ones that were 1 then 0 would map to 200-399. So first you can map two groups of 400, then you can whittle it down to 4 groups of 200 in another message. Keep seeing half of each known mapping to 1 and you get to 8 groups of 100, 16 groups of 50, 32 groups of 25, 64 groups of 12/13, 128 groups of 6/7, 256 groups of 3/4, 512 groups of 1/2, and finally to a 1:1 mapping for all 800 bits in 11 messages.

Depending on how you generate the pairs, that might be enough for other message lengths. For instance say you use a seeded random number for each bit except the last to determine what position to map the cell too. The number is generated as 0.0 to 0.999999999 and multiplied by 800 to choose which bit to swap with (including the first bit which means no swap). If it turns out to be bit 399 then the number is around 0.49. That means a message of length 800 would swap bit 0 to 399, a message of length 400 would swap to bit 199, etc. Submitting just a few messages should be enough to figure out the algorithm and find the key.

As Land mentioned if you don't actually modify the data and just swap the bits, information can be gleaned about the message by the number of 1s and 0s. Say what you are encrypting is a 1024 bit private key. Let's say it has 500 1s and 524 0s. You've now greatly reduced the amount of time needed to brute force the key because you can skip checking any key that has a different number of 1s and 0s.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ so you would know those two bits are swapped I think this is a mistake. You only know that bit X gets sent to bit Y; bit Y might get sent back to bit X, but it might not. Consider a 3-bit sequence where there are two swaps, 1<>2 and 2<>3. Then bit 1 goes to bit 3, bit 3 goes to bit 2, and bit 2 goes to bit 1. $\endgroup$ – MegaWidget Jun 3 at 7:17
  • $\begingroup$ True, I was misinterpreting it... $\endgroup$ – Jason Goemaat Jun 3 at 21:15
1
$\begingroup$

You can do that. But this is a bad encryption algorithm. It can't be used in real application, because one can easily recover the plaintext from its ciphertext.

| improve this answer | |
$\endgroup$
  • 6
    $\begingroup$ Explaining how the plaintext can be recovered would improve this answer significantly. $\endgroup$ – Ray Jun 2 at 20:34
  • 1
    $\begingroup$ Without a published algorithm, it wouldn't be possible to specify exactly how it's weaknesses could be exploited to decrypt the messages. As this appears to be a variant of a simple substitution cipher, one should assume that it can be attacked in the same ways as other algorithms of this family. $\endgroup$ – Byron Jones Jun 3 at 12:45
  • 2
    $\begingroup$ @ByronJones It's a transposition cipher, not a substitution cipher. $\endgroup$ – Maeher Jun 3 at 18:39
0
$\begingroup$

Can you? Sure! It'll be a great exercise to code up and then you can research why it might be particularly weak to attacks (such as what has been mentioned here).

In fact I'd really encourage you to explore cryptography as it is both fun and frustrating at the same time.

When you've decided you've had enough, I'd then recommend some deep diving on the web for proper cryptographic implementations, the pitfalls of crypto in software, and what not. I won't mention resources as what I knew is far out of date.

But yes, learn- yes- you can- yes- do it!

...then learn to do it the 'safe' way. Because crypto is hard. I can't tell you the number of stories you see/hear/read about people that thought crypto was easy, used their own method, and got p0wn3d.

| improve this answer | |
$\endgroup$
0
$\begingroup$

This sounds like a kind of fractionated transposition cipher. My understanding is that some kinds of transposition-alone ciphers can be more difficult to crack than double-Playfair (WGBH 2000), and fractionated transposition ciphers, such as ADFGVX Cipher are considered more difficult to crack than transposition-alone ciphers (Rijmenants).

As others have pointed out, it is trivially easy, if you encode the letters using ASCII, to rule out some possible messages -- messages that have a different Hamming weight than the (transposed) ciphertext.

However, it is in principle for transposition alone (with other kinds of encoding) to give (with sufficiently unguessable shuffling) "perfect security", although this doesn't seem useful in practice. (Because other, apparently simpler techniques also give "perfect security"; and because we find in practice that we're willing to give up perfect security in order to make key distribution easier).

For example: algorithm A:

  • Ahead of time, Alice and Bob share one-time pads of random numbers.
  • Alice encodes a message into a series of 40 character lines using some constant-weight code (every possible message in that encoding has exactly the same Hamming weight).
  • Alice rearranges the bits in each encoded line with a Fisher-Yates shuffle to fairly permute all the bits in the 40-character line (thank you, Luis Casillas), using the numbers from her one-time transmit pad to decide which of all possible shuffles to use.
  • Alice sends a series of lines to Bob, and destroys the used pages of her one-time transmit pad.
  • Bob unshuffles the bits in each line of text using his one-time receive pad, then decodes each line into 40 characters of plaintext, and destroyed the used pages of his one-time receive pad.

From any possible ciphertext generated by this algorithm A, a cryptanalyst can "decrypt" any possible message with the same number of lines of text, simply by using a different one-time pad, so algorithm A has perfect security. (A particular ciphertext might represent "YEAH", "NOPE", "HAHA", "GOGO", etc.) (Alas, this uses up the one-time pads of numbers much faster than enciphering the same messages with traditional XOR encryption one-time pad, which also has "perfect security").

My understanding is that a fixed, publicly-known transposition could be used in the inner block of a Even-Mansour cipher.

Another kind of encoding that seems better than ASCII for transposition ciphers is: encoding text into a complete deck of cards, as suggested by Tim Warriner and Lee J Haywood.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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