Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I am aware of the vulnerabilities of simple xor ciphers and recently I came across a block cipher that claims to solve those vulnerabilities.

The cipher goes as follows with both the block and key sizes at 256-bits: the key is separated into chunks of length 1 bit. Every bit in the plaintext is xored with every key chunk.

For example assume that the first bit of the plaintext is 1. Say that the key is 10100101010010101…
The operation that takes place is:

1 xor 1 = 0
0 xor 0 = 0
0 xor 1 = 1
1 xor 0 = 1
1 xor 0 = 1

This continues until the end of the key and the result becomes the first bit of the ciphertext.

Is this really as secure as advertised?
If not why?

share|improve this question

3 Answers 3

up vote 6 down vote accepted

If I understand right, your operation effectively is $$\forall i: c_i = p_i \oplus k_0 \oplus k_1 \oplus k_2 \oplus \dots \oplus k_n,$$ whith $c_i$ the ciphertext bits, $p_i$ the plaintext bits, and $k_j$ the key bits.

As $\oplus$ (this is XOR) is associative, this is equivalent to

$$k^* := k_0 \oplus k_1 \oplus k_2 \oplus \dots \oplus k_n,$$ $$\forall i: c_i = p_i \oplus k^*.$$

Now $k^*$ is either 0 or 1 - in the first case this operation is the identity, in the second case it is simple negation. Neither of those can be considered an encryption, and you effectively have a key space of 2 (= 1 bit).

Whoever told you this either wanted to play a joke with you, or knows nothing of cryptography (or both). Or I misunderstood your presention of the algorithm.

share|improve this answer
3  
Take your message and flip a coin. If it is heads, output the message. If it is tails, output the message with each bit flipped. Sounds secure :) –  PulpSpy Sep 7 '11 at 18:15
2  
You will still have to somehow securely send the value of the coin flip to the receiver, else he won't be in a better position than the attacker. –  Paŭlo Ebermann Sep 7 '11 at 18:24

Unless you are badly (and I mean truly badly) misrepresenting the idea, it is one of the worse ideas I've seen in crypto in quite some time.

The first bit is effectively exclusive or'ed with the parity of the key; the ciphertext bit will be either the plaintext bit (if the key has an even number of '1' bits) or the complement of the first plaintext bit (if the key has an odd number of '1' bits). Now, what happens to the second plaintext bit? If it does through this same operation, the second ciphertext bit will be set to either the plaintext bit or its complement (using the exact same logic is the first bit).

Extending this, we see that the entire first ciphertext block will be either the plaintext block or its complement, with no other possibilities.

A "block cipher" that does either an identity transform or a complementation is worse than weak. The only good side I can see is that your key is secure; other than its parity, the attacker can't deduce anything about it :-)

share|improve this answer
    
The parity is also everything an attacker needs to know about the key, though. –  Paŭlo Ebermann Sep 7 '11 at 17:45
    
With respect to the key space this would indeed be the worst possible encryption method. –  starblue Sep 7 '11 at 20:26
1  
Well, no, these is something worse than something that transforms the plaintext in two different ways depending on the key... –  poncho Sep 7 '11 at 20:29

In an effort to guess what the poster is saying, I tried to develop a "secure-as-possible" (but not really secure at all) cipher using only minor modifications of the above:

$Key = {k_0, k_1 ... k_m}$

$Plaintext = {p_0, p_1 ... p_n}$

$Ciphertext = {c_0, c_1 ... c_n}$

$\forall i: i \le m \rightarrow c_i = p_i \oplus k_i$

The first $m$ bits of ciphertext are the first $m$ bits of key xored with the first $m$ bits of plaintext.

$\forall i: i > m \rightarrow c_i = p_i \oplus p_{i-1} \oplus p_{i-2} ... \oplus p_{i-m} \oplus k_{i \mod m} $

The next $n$ bits of the ciphertext are the current plaintext bit xored with the last $m$ plaintext bits and the current key bit $k_{i \mod m}$.

The idea here is that the typical attack against a OTP-like scheme that reuses the key is slightly harder here (but still remains trivially easy).

share|improve this answer
    
Hmm, some kind of plaintext-feedback mode? ;-) –  Paŭlo Ebermann Sep 7 '11 at 20:11
    
@paulo Ebermann - Exactly. What I really want to do is use the key as a seed to a PRNG but no PRNG is available so instead I built a really lame LFSR with really lame tap positions. Something better could be built by running a LFSR on the key with good tap positions but then I'm just reinventing a bad linear-stream cipher. –  Ethan Heilman Sep 7 '11 at 20:22

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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