0
$\begingroup$

I am using DES encryption when writing a file in an embedded device. When I decrypt the file. I get a partially corrupted file. Kind of randomly some 8-byte blocks are corrupted. Some are not. When I regenerate the file, It shows the same corruption. But If I reset the device, the file is okay.

My DES encryption function resides in RAM. I am suspecting that somehow the DES encryption function gets corrupted. Maybe some values in the S Boxes got corrupted. I have intentionally inserted some wrong values in the s boxes and found that the corruption pattern is the same. But since I can't reproduce the issue, I am not able to inspect the memory, when the actual issue occurs.

I now want to find out what kind of corruption may generate this kind of cipher. I want to introduce the erroneous values in the S boxes and verify that similar corruption occurs in the file. I want to know if it will be feasible to find out. Also, how may I do that? I have the plain text, cipher, Key, IV.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ I didn't quite understand it. Could you please clarify it a bit more. The implementation I have has 8 S boxes with 64 values in each. let's say one or two values got corrupted in the S[8] Box. The blocks that use this corrupted value, will be corrupted. All blocks won't use this. But the corrupted cipher will be used as IV for next block. but that isn't an issue I think. although the cipher is corrupted, I will be able to retrieve the data of the next block using it. So all blocks shouldn't be corrupted. This is how I understood it. Am I wrong in some way? $\endgroup$
    – Monem Ahmed
    Commented Aug 18, 2023 at 12:14
  • $\begingroup$ If you only want to verify if your implementation has bugs or not (without getting to know which bugs exactly), you could use Rivest's DES test. $\endgroup$
    – garfunkel
    Commented May 15 at 11:56

1 Answer 1

Reset to default
1
$\begingroup$

$16$ times per DES block encryption, an essentially random entry among $64$ is used in each of the S-boxes. A 1-bit RAM corruption in one of the S-boxes has probability near $1-(63/64)^{16}\approx22\%$ to affect the block. In most implementations of encryption based on DES, S-boxes (in whatever form they may be) are reused from one block encrypted to the other, and then an error in S-boxes would affect about that proportion of the blocks encrypted after the corruption occurred.

In CBC mode (which we are told applies), an error in a block encryption will affect later ciphertext. Encrypting with one bad entry in an S-box would cause the wrong ciphertext to be produced starting from the first block in error. That would be made apparent by using a known-good DES-CBC encryption applied to the known plaintext with known key and known IV, and comparing to the actual ciphertext. And when deciphering the ciphertext using a known-good DES-CBC decryption, the result would match the known plaintext except for about 22% of the blocks.

If the observed errors are consistent with that (or perhaps with 40% of the blocks in error on decryption for two bad S-box entries), the hypothesis that the error is caused by a corruption in the S-boxes makes sense. If there was much less blocks in error (or for a single block in error, more than about a dozen contiguous blocks not affected by the error after a block in error), the hypothesis would be dubious at best.

That hypothesis can probably be confirmed and the defect pinpointed. We need to:

  • Deduce the input and output of one (or a few) DES block in error
  • Find which alteration of the S-boxes would cause exactly such input/output pair for the known key. We don't need optimized code to try every alteration of 1 bit in the S-boxes (2048 attempts, or at most 64 if we restrict to active S-boxes), or every alteration of a single entry (7680 attempts, or at most 240 with the same optimization). It's still very feasible to try every alteration of 2 active S-boxes (≤27000 attempts). With some care, we could find much larger alterations.
  • Confirm the finding, e.g. by deciphering the ciphertext with the altered S-boxes.
Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ There are much more than a dozen blocks after an error. But they are not subsequent blocks. I can see one/two block corrupted, then three/ four blocks correct. Then one corrupted, then maybe two/three blocks correct. Then 2 blocks corrupted. A kind of random pattern like this. It might be greater than 22%. And the operating mode is CBC mode. $\endgroup$
    – Monem Ahmed
    Commented Aug 18, 2023 at 18:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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