Which step am I missing - DES-OFB Key
#1
I am trying to map out how you can recover the Encryption key from a DES-OFB cipher with a known plain text attack.

As it stands I have the IV - 64 Bits, the Cipher - 64 bits and the original/plain text - 64 bits.

From what I can work out, to encrypt the original text into OFB, the DES encryption is run 8 times producing 16 bits of cipher text each time. Each time before the returned encryption is XOR with the plain text to produce the cipher text the 16 bits of data are appended to the end of the original 64 bit IV and the front 16 bits are discarded.

Long story short, I believe I only need to crack anyone of these 8 encryption cycles to produce the Encryption key but to do that I need the 64 bit input and the 64 encrypted output (prior to it being XOR to produce the cipher text).

By XOR the cipher and plain text for each position, I can reproduce the 64 bit input for any location, but I can only get the first 16 bits for all the outputs, as this is the only data that is used in the XOR to produce the cipher for that location. The remaining bits are discarded.

I wanted to use Hashcat to brute force the DES encryption but I am unable to get a full 64 bits for the plain text input required.

Am I missing a step or am I approaching this the wrong way?
#2
Can you please post example data trace (all 8 iterations). Like, whats the ct/pt with each iteration
#3
(02-08-2017, 11:54 AM)atom Wrote:
Can you please post example data trace (all 8 iterations). Like, whats the ct/pt with each iteration


Thanks for replying,


No Problem, so showing with a quickly generated example:

In this example I will post the Encryption key in case it helps with reverse engineering the results but in reality the Ek is what i am trying to obtain:

so a straight DES-OFB encryption using the following data (in HEX)
Plain Text (PT) : 69 77 69 6e 68 61 68 61
Initialization Vector (IV):    a9 cc 34 d3 f9 c2 ba fe

Encryption Key (Ek):   69 61 6d 61 6b 65 79 7a (Should be unknown)

gives a Cipher text (CT) of: c4 cc b0 ed 6d fe ab 86


Using the DES encryption 8 times simulating OFB mode to create to same cipher text gives the following iterations:


Output 1:
Input(IV): a9 cc 34 d3 f9 c2 ba fe
Ek(Should Be Unknown):69616d616b65797a
output: ad d7 69 43 e9 09 51 b5 
Cipher Text 1= XOR of ad and 69 (output 1 and plain text 1) = c4 == original Cipher text1

Cipher text now = c4

Output 2:

Input(IV): cc 34 d3 f9 c2 ba fe ad <-- first 16 bytes from previous output before XOR
Ek(Should Be Unknown):69616d616b65797a
output:[font=monospace]bb 58 f3 09 52 51 6f 1e
Cipher Text 2= XOR of bb and 77 (output 1 and plain text 2) = cc == original Cipher text2
[/font]

[font=monospace]Cipher text now = c4 cc

Output 3:
[/font]

Input(IV): 34 d3 f9 c2 ba fe ad bb<-- first 16 bytes from previous output before XOR

Ek(Should Be Unknown):69616d616b65797a
output:[font=monospace][font=monospace][font=monospace]d9 e3 d2 49 83 f9 c0 60
[/font]
Cypher Text 3= XOR of d9 and 69 (output 1 and plain text 3) = b0 == original Cipher text3[/font]
[/font]


[font=monospace][font=monospace]Cipher text now = c4 cc b0[/font][/font]
[font=monospace]
[font=monospace]Output 4:

[/font]
[/font]

Input(IV): d3 f9 c2 ba fe ad bb d9<-- first 16 bytes from previous output before XOR

Ek(Should Be Unknown):69616d616b65797a
[font=monospace][font=monospace]output:[font=monospace][font=monospace][font=monospace][font=monospace]83 22 1c 8f 58 eb 02 35  
[/font]
[/font]
Cypher Text 4= XOR of 83 and 6e (output 1 and plain text 4) = ed == original Cipher text4[/font]
[/font]


Cipher text now = c4 cc b0 ed

[/font]Output 5:
[/font]

Input(IV): f9c2bafeadbbd983 <-- first 16 bytes from previous output before XOR

Ek(Should Be Unknown):69616d616b65797a
output:[font=monospace][font=monospace][font=monospace]05  0a 00 d4 a4 ab a5 94

[/font]
Cypher Text 5= XOR of 05 and 68 (output 1 and plain text 5) = 6d == original Cipher text5
[/font]
[/font]

[font=monospace][font=monospace][font=monospace]Cipher text now = c4 cc b0 ed 6d[/font]

[/font]Output 6:
[/font]

Input(IV): c2 ba fe ad bb d9 83 05<-- first 16 bytes from previous output before XOR

Ek(Should Be Unknown):69616d616b65797a
output:[font=monospace][font=monospace][font=monospace]9f de f0 ca 60 6a 60 a9

[/font]
Cypher Text 6= XOR of 9f and 61 (output 1 and plain text 6) = fe == original Cipher text6

Cipher text now = c4 cc b0 ed 6d fe[/font]
[/font]


Output 7:

Input(IV): ba fe ad bb d9 83 05 9f<-- first 16 bytes from previous output before XOR

Ek(Should Be Unknown):69616d616b65797a
output:[font=monospace][font=monospace][font=monospace]c3 1e 86 3d a31 85 34 ff

[/font]
Cypher Text 7= XOR of c3 and 68 (output 1 and plain text 7) = ab == original Cipher text7

[/font][font=monospace][font=monospace]Cipher text now = c4 cc b0 ed 6d fe ab[/font][/font]

Output 8:
[/font]

Input(IV): fe ad bb d9 83 05 9f c3<-- first 16 bytes from previous output before XOR

Ek(Should Be Unknown):69616d616b65797a
output:[font=monospace][font=monospace][font=monospace]e7 46 a0 52 22 1c 86 66 

[/font]
Cypher Text 8= XOR of e7 and 61 (output 1 and plain text 8) = 86 == original Cipher text8
[/font]
[/font]

Cipher text now = c4 cc b0 ed 6d fe ab 86

After 8 cycles of DES encryption, cipher text == DES-OFB encryption in one pass

It can be seen that the IV or input text can be seen discovered at all stages but when you attempt to reverse the process by XORing the output bits you can only recover the 2 bits (16 bytes) that are at the start of the encoded text at each step, the remaining data is discarded.

so from a Hashcat DES decryption point of view I keep ending up with 

CipherText 1: ad XX XX XX XX XX XX XX  with a plaint text input of: a9 cc 34 d3 f9 c2 ba fe
[font=monospace][font=monospace]CipherText 2:    bb XX XX XX XX XX XX XX   with a plaint text [font=monospace] input of: cc 34 d3 f9 c2 ba fe ad [/font][/font]
[font=monospace]CipherText 3:    d9 XX XX XX XX XX XX XX  with a plaint text [font=monospace] input of: 34 d3 f9 c2 ba fe ad bb[/font][/font][/font]

[font=monospace][font=monospace]CipherText 4:    83 XX XX XX XX XX XX XX  with a plaint text [font=monospace] input of: d3 f9 c2 ba fe ad bb d9[/font][/font]
[font=monospace]CipherText 5:    05 XX XX XX XX XX XX XX  with a plaint text [font=monospace] input of  f9 c2 ba fe ad bb d9 83[/font][/font]
[font=monospace]CipherText 6:    9f XX XX XX XX XX XX XX  with a plaint text [font=monospace] input of  c2 ba fe ad bb d9 83 05[/font][/font][/font]

[font=monospace][font=monospace][font=monospace]CipherText 7:    c3 XX XX XX XX XX XX XX  with a plaint text [font=monospace] input of  ba fe ad bb d9 83 05 9f[/font][/font][/font][/font]
[font=monospace][font=monospace][font=monospace]CipherText 8:    e7 XX XX XX XX XX XX XX  with a plaint text [font=monospace] input of  fe ad bb d9 83 05 9f c3[/font][/font][/font]

In order to be able to use Hashcat to recover the Encryption Key, I need to be able to work out the complete decrypted HEX at any point in the 8 cycles, as the key is applied each time unchanged.[/font]



The input or Plain text is not an issue but trying to work out what the output or encrypted text in full (64 bits) is for any stage is eluding me. I can only ever get the first 16 bits for any stage of the process.

I can get the full 64 bits of plain text for any stage but I need to get a full 64 bits of encrypted HEX to be able to use the Hashcat DES brute force function.
#4
XOR is not supported by hashcat, i think
#5
(02-09-2017, 12:46 AM)ccprime Wrote: XOR is not supported by hashcat, i think

Sorry if I made that hard to understand, the XOR is performed at the end of the encryption to obtain the cipher that is transmitted. I manually XOR the encryption output with the plain text to show that it produces the same cipher text as a straight DES-OFB encryption.

To obtain the encrypted text necessary for the Hashcat function you need to XOR the cipher text with the Known plain text. But that will only give the encrypted text for the first byte of each cycle.

This diagram may help to explain the encryption process
[Image: 601px-OFB_encryption.svg.png]

I cant seem to work out how to get a complete 8 bytes of encrypted text to be able to run the Hashcat DES option. As the final cipher text has one byte of output from each DES encryption cycle.

As I said earlier, I only need to find the key for any stage of the cycle as the same key is used everytime. I know the input text in full for all stages and the first byte of encrypted text for every stage.

Is it even possible to find the key in DES-OFB even if you know the plain text?
#6
Yes, you can crack it with hashcat, but you need to patch the kernel.

I really love such home-cooked algorithms. They always do something stupid, so does this one. I didn't write a poc, but I'm pretty sure you can actually exploit it. All you need to do is to compare a final value (in your example the c4) already after the first iteration. This way you can skip the entire rest of the calculation if it doesn't match at that point completely and try the next key. You can do the same for the 2nd, and so one. Doing this you will end up with a performance close to the one from raw DES instead of DES speed divided by 8.
#7
Thanks atom,

That was exactly to approach I had thought, because the key never changes, while there may be numerous keys that produce a C4 value with the IV, there will be a significantly smaller number that when using the same key with the second IV will produce CC, and so on. If it doesn't, discard the key and start again until it does.

I am yet to dive into any of the code. To achieve this are we talking major changes or will it be a relatively straight forward tweak?
#8
I think it's mostly copy / paste of the -m 14000
#9
Thanks for your help atom. I'll have a "crack" at it over the next few days.
#10
You have mis-understood the implementation of DES-OFB somewhat. Each round of DES-OFB gives you 64 bits of keystream, that is XORed with your plaintext to give you 64-bits of ciphertext. I'm not sure how or why you changed it to only use the first 8 bits of each DES round...

Example:-

Round 1 - You an 64-bit IV (which is just the first input round) and encrypt this with the DES key to give 64 bits of output from the DES cipher. This is XORed with 64 bits of plaintext to give you 64 bits of ciphertext.

Round 2 - you take the output of the previous DES register and encrypt it again with your key. This yields a further 64 bits of keystream that is XORed with the next 64 bits of plaintext.. and so on...

To break DES-OFB, you only need to know 128 consecutive bits of keystream, as long as they align with the 64-bit DES input and output blocks. Yes - it does work.

(02-09-2017, 01:18 AM)MaxPower Wrote:
(02-09-2017, 12:46 AM)ccprime Wrote: XOR is not supported by hashcat, i think

Sorry if I made that hard to understand, the XOR is performed at the end of the encryption to obtain the cipher that is transmitted. I manually XOR the encryption output with the plain text to show that it produces the same cipher text as a straight DES-OFB encryption.

To obtain the encrypted text necessary for the Hashcat function you need to XOR the cipher text with the Known plain text. But that will only give the encrypted text for the first byte of each cycle.

This diagram may help to explain the encryption process
[Image: 601px-OFB_encryption.svg.png]

I cant seem to work out how to get a complete 8 bytes of encrypted text to be able to run the Hashcat DES option. As the final cipher text has one byte of output from each DES encryption cycle.

As I said earlier, I only need to find the key for any stage of the cycle as the same key is used everytime. I know the input text in full for all stages and the first byte of encrypted text for every stage.

Is it even possible to find the key in DES-OFB even if you know the plain text?