# Is it possible to decrypt the entire message with one half of the key in this example?

In this scheme, a 256 bit key is split into two 128 bit sub-keys. Message blocks are 256 bits and are also split into two sub-blocks. Before encryption, each sub-block is xor'd with it's partner and then xor'd with the opposite sub-key, in order to link the entire key to both blocks.

From the example below:

sub_aes_key1 = a
sub_aes_key2 = b
sub_block_1  = w
sub_block_2  = x
ciphertxt_1  = y = aes(message= sub_block_1 ^ sub_block_2 ^ sub_key_2, key = sub_key_1)
ciphertxt_2  = z = aes(message= sub_block_2 ^ sub_block_1 ^ sub_key_1, key = sub_key_2)


Essentially, the crux of my question is whether or not the hypothetical Susan, who somehow aquired one half of the key, would be able to infer the rest of the text. I'd also like to know if there are any other obvious vulnerabilities to this variant if you can see them.

Pseudocode example

function func_1(a, b):
encrypt message "a" with key "b"

function func_2(a, b)
decrypt message "a" with key "b"

John knows:
a, b = 255, 100
c, d =  83,  97
w, x =  86, 205      (b XOR c XOR d), (a XOR c XOR d) #
y, z =  44, 196      func_1(w, a),      func_1(x, b)

Susan knows:
a, b = ___, 100
c, d = ___, ___
w, x = ___, 205      ???,               func_2(z, b)
y, z =  44, 196

a = c ^ d ^ x   =   ___ ^ ___ ^ 205
d = a ^ c ^ x   =   ___ ^ ___ ^ 205
c = b ^ d ^ w   =   100 ^ ___ ^ ___
w = b ^ c ^ d   =   100 ^ ___ ^ ___


There are two major problems with this method.

The first problem is that Susan is likely to be able to recover significant amount of data from a series of such blocks.

For example, if Susan knows $subkey_1$, then she could recover the value $subblock_1 \oplus subblock_2 \oplus subkey_2$; if a single block is encrypted with this key, she can't deduce anything from this (as she has no information about $subkey_2$; however if multiple blocks are encrypted with the same key, then she can exclusive or the values, obtaining the value $subblock_1 \oplus subblock_2 \oplus subblock_3 \oplus subblock_4$; if she has a guess about the encrypted data, this is likely to reveal more.

The second problem is that someone with the entire key is unable to uniquely decrypt.

Here's why: someone with the encrypt key could decrypt $ciphertxt_1$ to compute $subblock_1 \oplus subblock_2 \oplus subkey_2$, and thus recover $subblock_1 \oplus subblock_2$

And, they could decrypt $ciphertxt_2$ to recover $subblock_2 \oplus subblock_1$

At this point, they have the value $subblock_1 \oplus subblock_2$, howqever without any further information, they cannot recover either the values $subblock_1$ or the value $subblock_2$. Yes, if the decryptor had some side information about either of those values, he could determine the other; however we generally don't assume that the legitimate decryptor has such side information.

Hence, this method makes things possible for the attacker, and not possible for the legimate user.

• I just encrypted another message, so that Susan can now see x=7 (in line with the psedocode). I still couldn't use that to deduce any further information about the rest of the key or either message. I'm having trouble seeing how knowing one half of a key would ever give any useful information. As to the second problem, if I understand you correctly, it isn't a problem and in fact was how I designed this. The whole point of this is to avoid MITM attacks while using two AES-128 keys. I'm trying to double the security of AES-128 without using another encryption algorithm or just using AES-256. Nov 7, 2014 at 0:45
• @user4131185: you are correct; knowledge of one half of the key does not allow the attacker to deduce anything, as long as you use the key only once. If you encrypt, say, two 256 bit blocks, then knowledge of the half key does leak information about the blocks. As for the second issue, well, if it is not important that someone with the keys to decrypt the data, well, I would suggest a more secure way would be to output a constant block of all 0's; a constant block of 0's cannot leak anything about the plaintext, and hence is more secure. Nov 7, 2014 at 5:18
• Alright, I'm gonna clarify one more time then I'll just consider myself dumb and move on. The way I intended this to work: the decryptor uses the second key to decrypt every even block of the full ciphertext, then they use the first key to decrypt every odd block of the full ciphertext, then xor the decrypted odd blocks with the even blocks with the first key, then xor the even blocks with the odd blocks with the second key. In my example I showed that there is absolutely no way to infer the other key, or the other plaintext, with just one key and one decrypted ciphertext. Continued below Nov 7, 2014 at 7:13
• In order to infer either the missing half of a key or the other plaintexts: in addition to one half of the key you need EITEHR the other half of the key, or access to a plaintext block encrypted with the other half of the key. At least this is my assumption, and why I asked this question. Furthermore, this is really a question of security equivalence with AES-256. The difficulty an attacker faces finding one half of the key of this variant is the same as aes-128. Even if they brute force a correct half-key, they couldn't possibly know that it was correct, since the plaintext would be random. Nov 7, 2014 at 7:20
• First of all, known plaintext is a valid attack vector. If you just have fully random plaintext then you don't have a distinguisher for the attacker, and you could just use AES-128; they will never be able to validate any key. This method is nowhere equivalent with AES-256. Poncho's answer seems spot on to me after rereading everything. So eh, I guess you have to move on from this, and congratulate yourself with asking here instead of considering yourself dumb - actually using that scheme, now that would be dumb... Nov 7, 2014 at 14:04

(posting as an "answer" because it's a little to long to fit in the "comment" section)

It sounds like you are trying to build a 256 bit block cipher, given a 128 bit cipher and 2 keys for that cipher.

I'm gonna clarify one more time ... The way I intended this to work: the decryptor uses the second key to decrypt every even block of the full ciphertext, then they use the first key to decrypt every odd block of the full ciphertext, then xor the decrypted odd blocks with the even blocks with the first key, then xor the even blocks with the odd blocks with the second key.

Or in other words, an authorized decryptor does

partial_block_1 = e = aes_decrypt( ciphertxt_1, key = sub_key_1 )
partial_block_2 = f = aes_decrypt( ciphertxt_2, key = sub_key_2 )
partial_block_3 = g = e^sub_key_2 == sub_block_1 ^ sub_block_2
partial_block_4 = h = f^sub_key_1 == sub_block_1 ^ sub_block_2


And now g and h are equal to each other? As poncho pointed out, the authorized decoder is now left with two identical blocks g and h and apparently no easy way to uniquely recover the original plaintext message w and x. (Unless maybe there's something special about w and x that you neglected to mention?)

I'm guessing maybe you intended to build a Feistel cipher -- perhaps something like this?:

modifier_1 = aes_encrypt( message= plaintext_2, key=sub_key_1 )
temp_1 = modifier_1 ^ plaintext_1 // where "^" means XOR
modifier_2 = aes_encrypt( message= temp_1, key=sub_key_2)
ciphertext_2 = modifier_2 ^ plaintext_2
modifier_3 = aes_encrypt( message= ciphertext_2, key=sub_key_1)
ciphertext_1 = modifier_3 ^ temp_1


and then an authorized decryptor does

modifier_3 = aes_encrypt( message= ciphertext_2, key=sub_key_1)
temp_1 = ciphertext_1 ^ modifier_3
modifier_2 = aes_encrypt( message= temp_1, key=sub_key_2)
plaintext_2 = ciphertext_2 ^ modifier_2
modifier_1 = aes_encrypt( message= plaintext_2, key=sub_key_1 )
plaintext_1 = temp_1 ^ modifier_1


On the other hand, perhaps you are interested in secret sharing, where several people have part of the "key", but none of them can decrypt any of the text with only their part of the key -- only if they cooperate can they recover the plaintext. In that case, you may be interested in secret splitting.