[Phizo]

It has been a while since I have posted anything hacking related. I thought this might be fun for some of you newbies out there who may be interested in some beginner-level cryptanalysis.

Context
LDES (linear DES) is an example of a block cipher which includes a 2-round Feistel network. It operates on 4-bit blocks and 2-bit keys. The important characteristic of LDES is that the S-box has been replaced with a linear operation, which makes the whole cipher linear. The purpose of this exercise is to help you understand the importance of the S-box in DES. Without the S-box, the cipher becomes linear and can be completely and trivially broken.

The following diagrams illustrate how LDES functions. On the left, we have the 2-round Feistel network which takes the 4-bit message M, applies a single bitwise left shift, and splits the message into two registers, {A, B}. The rounds are computed such that A[n] = B[n-1] and B[n] = A[n-1] ⊕ F(B[n-1], K[n]) with 0 < n ≤ 2 (note that ⊕ represents XOR). K represents a key which is distributed as subkeys by the key scheduler for each round in the Feistel network, which simply expands each n'th bit of K into K[n] for 1 ≤ n ≤ 2. Following the two rounds, a P-box is introduced (permutes the registers), and finally a single bitwise right shift of the 4-bit M produces the 4-bit ciphertext C. The F (Feistel) function is the heart of (L)DES. F is given by F : X × Y → Z such that X is a partial (2-bit) block given by register B, Y is a 3-bit subkey, and Z is a "scrambled" partial (2-bit) block. E represents the expansion function: the 2-bit input X is expanded to a 3-bit X which is XOR'd against the subkey Y also passed into F. The resulting 3-bit output is input for the linear operation which replaces the S-box. This operation is simply the bitwise complement/NOT of the last two bits of I: J[1] = I[2] + 1 mod 2; J[2] = I[3] + 1 mod 2.




Goal
Given the following known plaintext-ciphertext pairs:

E(0000) = 0110
E(1000) = 1110
E(0100) = 0011
E(0010) = 1100
E(0001) = 0111

You are to solve the following (i.e. compute the corresponding plaintexts):

E(1100)
E(1010)
E(1001)
E(0110)
E(0101)
E(0011)
E(0111)
E(1011)
E(1101)
E(1110)
E(1111)

This demonstrates that if an adversary knows E(0000), E(1000), E(0100), E(0010), and E(0001), he can encrypt any message. In general, for a linear cipher with block size n, if an adversary knows n+1 plaintext-ciphertext pairs, he can encrypt/decrypt any message without even knowing the key.

A large hint as to how one solves this is given by the following property: for a linear encryption function E, we have E(X ⊕ Y) = E(X) ⊕ E(Y).

In truth, you don't need to really understand the intricates of how this cipher works in order to break it, but context is good regardless. Solving this is actually very trivial.

Please put your solutions in spoiler tags so every participant gets a chance. Show all necessary working.
If you have any questions, feel free to post them. I will provide another hint depending on how people do, and I will post the solution maybe in a week or so.

Good luck.

[Jesse Pinkman.]

This seems like a very interesting challenge. I'm curious to see if anyone is able to solve it?

[Bronze5]

Sounds rlly hard .-. but im down thx

[݃݃݃๖ۣۜKosdff]

Welp. This just broke my brain.

[Phizo]

Glad to finally see some interested individuals. I thought no one would make an attempt, which would be unfortunate, as I was looking to post more challenges in the future. Honestly, as I said in the last paragraph, this really is not too difficult. The algorithm of the cipher itself will be challenging to interpret for someone who is new to this sort of stuff, but as I said, you don't really need to understand the algorithm in order to solve this challenge. It's just a bit of context. It is easier than it seems.

I will provide some hints, as I want to see some people actually attempt/solve this and learn something:
Spoiler (Click to View)
What do you notice about each of the plaintexts in the five plaintext-ciphertext pairs provided? What is significant about their values, collectively?


An even bigger hint:
Spoiler (Click to View)
Can some of the plaintext-ciphertext pairs be combined in order to compute a new pair? How is the aforementioned pattern useful here?

---

100 views and no attempts. Don't any of you want to learn some real hacking? You will never evolve unless you challenge yourself. I would like to post more challenges in the future, but there is no point if no one is willing to participate. Throw your lame RATs away and do something interesting that's actually worth your while. :)

[Baud]

I'm currently giving it a try with little to no cryptography knowledge but by using logic and bitwise arithmetics. I will update this in a few hours, I may be able to get this right.

I'd love to see more of these challenges by the way, it's a good excuse for me to use my brain and a chance to get to learn more about cryptography.

[Phizo]

I'm currently giving it a try with little to no cryptography knowledge but by using logic and bitwise arithmetics. I will update this in a few hours, I may be able to get this right.

I'd love to see more of these challenges by the way, it's a good excuse for me to use my brain and a chance to get to learn more about cryptography.

Glad to see a participant. You honestly don't need to be very familiar with cryptography in order to solve this. All you need to know is how to compute C = A XOR B. If you don't know, that is effectively C = (A + B) mod 2. You won't need any other bitwise operation for this. Keep the property I gave in mind, as it is the key to solving this: for a linear encryption function E, E(X ⊕ Y) = E(X) ⊕ E(Y). This is because a linear Boolean function is defined as f(x[0], x[2], ..., x[n]) = ∑c[i]x[i] where c[i], x[i] ∈ {0, 1} – note that it is addition modulo 2, i.e. XOR. The polynomial must have a degree of 1. If you don't understand this, don't worry, as it is contextual more than anything. So long as you can utilise the property I gave, you should be able to solve this easily. If you haven't already, take a look at the hints I provided in the post prior to yours. Good luck. :)

Also, good, I will post more in that case. Even if a few amount of people are interested and benefit from these challenges, I'm happy to post some more.

[Bronze5]

Shit this is acutally hard ;-;(for me). I read like 6 pages on cyrpthograpy just for this still not getting near, but thx for the tips.

[Phizo]

Shit this is acutally hard ;-;(for me). I read like 6 pages on cyrpthograpy just for this still not getting near, but thx for the tips.

I don't think you will find anything on this in particular online, in a book, etc. I haven't found this problem online. You don't need to read up on cryptography. Everything you need is in this thread, especially in the post prior to yours. :)

[Asdethprime]

E(1100) = E(1000) XOR E(0100)
= 1110 XOR 0011
= 1101

E(1010) = E(1000) XOR E(0010)
= 1110 XOR 1100
= 0010
E(1001) = E(1000) XOR E(0001)
= 0011 XOR 0111
= 0100

That's what I have got so far. Is this how it's done? I know very little about encryption, really a topic I should really read up on.

[Phizo]

-snip-

That's what I have got so far. Is this how it's done? I know very little about encryption, really a topic I should really read up on.

Firstly, please wrap your solution in spoiler tags ([sp0iler]...[/sp0iler]).
You're very close. That is the principle, yes. However, it's still not correct. I will give you part of the solution so you can try to determine what else you are missing:
Spoiler (Click to View)

E(1100) = 1011
E(1010) = 0100
E(1001) = 1111

Here is a good hint for you: compute E(0111). Why is this different to the ones you have attempted?

[Baud]

This is a placeholder because I just found the solution and I'm going to write it here as soon as I come back home, I solved all the numbers.

Edit: well... after seeing what Phizo posted I just found out my solution is not correct, still, I'm going to post it here to see if at least I went close enough.

Spoiler (Click to View)

Code

E(1100) = E(1000) xor E(0100) =
E(1000) = 1110
E(0100) = 0011
1101

E(1010) = E(1000) xor E(0010) =
E(1000) = 1110
E(0010) = 1100
0010

E(1001) = E(1000) xor E(0001) =
E(1000) = 1110
E(0001) = 0111
1001

E(0110) = E(0100) xor E(0010) =
E(0100) = 0011
E(0010) = 1100
1111

E(0101) = E(0100) xor E(0001) =
E(0100) = 0011
E(0001) = 0111
0100

E(0011) = E(0010) xor E(0001) =
E(0010) = 1100
E(0001) = 0111
1011

E(0111) = E(0100) xor E(0010) xor E(0001)=
E(0100) = 0011
E(0010) = 1100
E(0001) = 0111
1000

E(1011) = E(1000) xor E(0010) xor E(0001)=
E(1000) = 1110
E(0010) = 1100
E(0001) = 0111
0101

E(1101) = E(1000) xor E(0100) xor E(0001)=
E(1000) = 1110
E(0100) = 0011
E(0001) = 0111
1010

E(1110) = E(1000) xor E(0100) xor E(0010)=
E(1000) = 1110
E(0100) = 0011
E(0010) = 1100
0001

E(1111) = E(1000) xor E(0100) xor E(0010) xor E(0001)=
E(1000) = 1110
E(0100) = 0011
E(0010) = 1100
E(0001) = 0111
0110

[Phizo]

This is a placeholder because I just found the solution and I'm going to write it here as soon as I come back home, I solved all the numbers.

Edit: well... after seeing what Phizo posted I just found out my solution is not correct, still, I'm going to post it here to see if at least I went close enough.

Spoiler (Click to View)

Code

E(1100) = E(1000) xor E(0100) =
E(1000) = 1110
E(0100) = 0011
1101

E(1010) = E(1000) xor E(0010) =
E(1000) = 1110
E(0010) = 1100
0010

E(1001) = E(1000) xor E(0001) =
E(1000) = 1110
E(0001) = 0111
1001

E(0110) = E(0100) xor E(0010) =
E(0100) = 0011
E(0010) = 1100
1111

E(0101) = E(0100) xor E(0001) =
E(0100) = 0011
E(0001) = 0111
0100

E(0011) = E(0010) xor E(0001) =
E(0010) = 1100
E(0001) = 0111
1011

E(0111) = E(0100) xor E(0010) xor E(0001)=
E(0100) = 0011
E(0010) = 1100
E(0001) = 0111
1000

E(1011) = E(1000) xor E(0010) xor E(0001)=
E(1000) = 1110
E(0010) = 1100
E(0001) = 0111
0101

E(1101) = E(1000) xor E(0100) xor E(0001)=
E(1000) = 1110
E(0100) = 0011
E(0001) = 0111
1010

E(1110) = E(1000) xor E(0100) xor E(0010)=
E(1000) = 1110
E(0100) = 0011
E(0010) = 1100
0001

E(1111) = E(1000) xor E(0100) xor E(0010) xor E(0001)=
E(1000) = 1110
E(0100) = 0011
E(0010) = 1100
E(0001) = 0111
0110

I'm very sorry. I should have said this earlier: to anyone who is verifying a solution, you can just give me a few correct pairs and I'll know you've solved it. I understand doing them all is a bit tedious. The equation is the same for all of them, but the inputs are, of course, different. This means if you need to call E N times to solve one, you should expect to call it N times for all of them. It will be the same amount every time. This is also a hint. A good portion of your computed pairs are correct, Baud. Try and find the minimum amount of pairs you need to use in order to compute them all.

I have actually already told you which one of your solutions are correct in the post above yours. So, you should be able to easily infer the solution now. :)

[Baud]

I'm very sorry. I should have said this earlier: to anyone who is verifying a solution, you can just give me a few correct pairs and I'll know you've solved it. I understand doing them all is a bit tedious. The equation is the same for all of them, but the inputs are, of course, different. This means if you need to call E N times to solve one, you should expect to call it N times for all of them. It will be the same amount every time. This is also a hint. A good portion of your computed pairs are correct, Baud. Try and find the minimum amount of pairs you need to use in order to compute them all.

I have actually already told you which one of your solutions are correct in the post above yours. So, you should be able to easily infer the solution now. :)

Oh don't worry I was actually pretty fast in doing the calculations, I'm used to XOR bits manually since I used to be an ASM programmer. Maybe I finally figured it out, this is the error I did before:

Spoiler (Click to View)The wrong pairs were the first ones, because I need to use 3 pairs for each calculation while I only used 2, is that correct? Because I tried doing this and I finally obtained the results you posted above, what I forgot to do is to XOR for E(0000) which is 0110, so the results now would be:

Code

E(1001) = E(1000) xor E(0001) xor E(0000) =
E(1000) = 1110
E(0001) = 0111
E(0000) = 0110
______________
E(1001) = 1111

E(1100) = E(1000) xor E(0100) xor E(0000) =
E(1000) = 1110
E(0001) = 0011
E(0000) = 0110
______________
E(1001) = 1011

E(0110) = E(0100) xor E(0010) xor E(0000) =
E(0100) = 0011
E(0010) = 1100
E(0000) = 0110
______________
E(0110) = 1001

It's also possible to calculate E(1111) with just 3 pairs now, you just need to calculate the value of a number like E(1100) then xor for E(0010) and again for E(0001), so we can say that E(1111) is equal to 0000.

[Phizo]

Oh don't worry I was actually pretty fast in doing the calculations, I'm used to XOR bits manually since I used to be an ASM programmer. Maybe I finally figured it out, this is the error I did before:

Spoiler (Click to View)The wrong pairs were the first ones, because I need to use 3 pairs for each calculation while I only used 2, is that correct? Because I tried doing this and I finally obtained the results you posted above, what I forgot to do is to XOR for E(0000) which is 0110, so the results now would be:

Code

E(1001) = E(1000) xor E(0001) xor E(0000) =
E(1000) = 1110
E(0001) = 0111
E(0000) = 0110
______________
E(1001) = 1111

E(1100) = E(1000) xor E(0100) xor E(0000) =
E(1000) = 1110
E(0001) = 0011
E(0000) = 0110
______________
E(1001) = 1011

E(0110) = E(0100) xor E(0010) xor E(0000) =
E(0100) = 0011
E(0010) = 1100
E(0000) = 0110
______________
E(0110) = 1001

It's also possible to calculate E(1111) with just 3 pairs now, you just need to calculate the value of a number like E(1100) then xor for E(0010) and again for E(0001), so we can say that E(1111) is equal to 0000.

You are correct. Good work! I knew you would get it after the last post. Thanks for participating. I hope you enjoyed it. :)