Score:0

Finding out corrupted S Box value in DES implementation?

ca flag

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.

Monem Ahmed avatar
ca flag
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?
Score:0
ng flag

$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.
Monem Ahmed avatar
ca flag
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.
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.