Embedding a Checksum in an Image File

This is a bit of the chicken and egg thing.  If you want a embed a checksum in a code module to report the checksum, is there a way of doing this?  It's a bit like being your own grandfather, I think. 

I'm not thinking anything too fancy, like a CRC, but rather a simple modulo N addition, maybe N being 2^16.  

I keep thinking of using a placeholder, but that doesn't seem to work out in any useful way.  Even if you try to anticipate the impact of adding the checksum, that only gives you a different checksum, that you then need to anticipate further... ad infinitum.  

I'm not thinking of any special checksum generator that excludes the checksum data.  That would be too messy.  

I keep thinking there is a different way of looking at this to achieve the result I want... 

Maybe I can prove it is impossible.  Assume the file checksums to X when the checksum data is zero.  The goal would then be to include the checksum data value Y in the file, that would change X to Y.  Given the properties of the module N checksum, this would appear to be impossible for the general case, unless...  Add another data value, called, checksum normalizer.  This data value checksums with the original checksum to give the result zero.  Then, when the checksum is also added, the resulting checksum is, in fact, the checksum.  Another way of looking at this is to add a value that combines with the added checksum, to be zero, leaving the original checksum intact. 

This might be inordinately hard for a CRC, but a simple checksum would not be an issue, I think.  At least, this could work in software, where data can be included in an image file as itself.  In a device like an FPGA, it might not be included in the bit stream file so directly... but that might depend on where in the device it is inserted.  Memory might have data that is stored as itself.  I'll need to look into that. 

-- 

  Rick C.

  - Get 1,000 miles of free Supercharging
  - Tesla referral code - https://ts.la/richard11209

On 2023-04-20 5:06, Rick C wrote:
> This is a bit of the chicken and egg thing.  If you want a embed a
> checksum in a code module to report the checksum, is there a way of
> doing this?  It's a bit like being your own grandfather, I think.
> 
> I'm not thinking anything too fancy, like a CRC, but rather a simple
> modulo N addition, maybe N being 2^16.

Some decades ago I was involved with a project for an 8052-based device, 
which was required to perform a code-check-sum check at boot.

We decided to use a byte-per-byte xor checksum and make the correct 
check-sum be zero. We had a code module (possibly in assembler, I don't 
remember) that defined a one-byte "adjustment" constant in code memory. 
For each new version of the code, we first set the adjustment constant 
to zero, then ran the program, and it usually reported an error at boot 
because the check-sum was not zero. We then changed the adjustment 
constant to the actual reported checksum, C say, and that zeroed the 
check-sum because C xor C = 0. Bingo. You can use this method to make 
the checksum anything you like, for example hex 55.

With a more advanced order-sensitive check-sum such as a CRC you could 
use the same method if you also ensure (by linker commands) that the 
adjustment value is always the last value that enters in the computed 
check-sum (assuming that the linking order of the other code modules is 
not incidentally changed when the value of the adjustment constant is 
changed).

Rick C <gnuarm.deletethisbit@gmail.com> wrote:
>This is a bit of the chicken and egg thing.  If you want a embed a checksum in a code module to report the checksum, is there a way of doing this?  It's a bit like being your own grandfather, I think. 

>I'm not thinking anything too fancy, like a CRC, but rather a simple modulo N addition, maybe N being 2^16.  

What about putting the following structure at a fixed address at the end of
ROM?:
<startaddr><len><checksum>
Your check function then for example does a 16 bit sum of the bytes from
<startaddr>..<startaddr>+<len>-1 and compares with <checksum>
<startaddr>, <len> an <checksum> can be evaluated at compile time.


-- 
Dipl.-Inform(FH) Peter Heitzer, peter.heitzer@rz.uni-regensburg.de

Un bel giorno Rick C digit�:

> This is a bit of the chicken and egg thing.  If you want a embed a
> checksum in a code module to report the checksum, is there a way of
> doing this?  It's a bit like being your own grandfather, I think. 
> 
> I'm not thinking anything too fancy, like a CRC, but rather a simple
> modulo N addition, maybe N being 2^16. 
> 
> I keep thinking of using a placeholder, but that doesn't seem to work
> out in any useful way.  Even if you try to anticipate the impact of
> adding the checksum, that only gives you a different checksum, that you
> then need to anticipate further... ad infinitum. 

I'm probably not understanding what you mean, but normally the checksum is
stored in a memory section which is not subjected to the checksum
calculation itself.

The actual implementation depends on the tools you are using. Many linkers
support this directly: you specify the memory section(s) subjected to
checksum calculation, the type of checksum (CRC16, CRC32 etc) and the
memory section that will store the checksum.

Here is a technical note for IAR:
https://www.iar.com/knowledge/support/technical-notes/general/checksum-calculation-with-xlink/

A "poor man" solution is to do it manually:

-In the source code, declare your checksum initializing to a known, fixed
value (e.g. 0xDEADBEEF)
-Run the program with a debugger; set a breakpoint when it calculates the
checksum (and fails), and write down the correct checksum
-Using a binary editor, find the fixed value into the executable binary,
and replace it with the correct value.

-- 
Fletto i muscoli e sono nel vuoto.

On Thursday, April 20, 2023 at 7:47:54 AM UTC-4, dalai lamah wrote:
> Un bel giorno Rick C digitò:
> > This is a bit of the chicken and egg thing. If you want a embed a 
> > checksum in a code module to report the checksum, is there a way of 
> > doing this? It's a bit like being your own grandfather, I think. 
> > 
> > I'm not thinking anything too fancy, like a CRC, but rather a simple 
> > modulo N addition, maybe N being 2^16. 
> > 
> > I keep thinking of using a placeholder, but that doesn't seem to work 
> > out in any useful way. Even if you try to anticipate the impact of 
> > adding the checksum, that only gives you a different checksum, that you 
> > then need to anticipate further... ad infinitum.
> I'm probably not understanding what you mean, but normally the checksum is 
> stored in a memory section which is not subjected to the checksum 
> calculation itself. 

Yes, I didn't explain it clearly.  I am not looking for a way to calculate the checksum from a processor.  That would be trivial.  I want to embed the checksum in the code, so that it can be provided at run time as an ID, a way to validate the version number.  


> The actual implementation depends on the tools you are using. Many linkers 
> support this directly: you specify the memory section(s) subjected to 
> checksum calculation, the type of checksum (CRC16, CRC32 etc) and the 
> memory section that will store the checksum. 

I wish to perform this checksum on the executable file.  


> Here is a technical note for IAR: 
> https://www.iar.com/knowledge/support/technical-notes/general/checksum-calculation-with-xlink/ 
> 
> A "poor man" solution is to do it manually: 
> 
> -In the source code, declare your checksum initializing to a known, fixed 
> value (e.g. 0xDEADBEEF) 
> -Run the program with a debugger; set a breakpoint when it calculates the 
> checksum (and fails), and write down the correct checksum 
> -Using a binary editor, find the fixed value into the executable binary, 
> and replace it with the correct value. 

Yeah, this is not useful, because changing the value stored changes the checksum. It also makes assumptions about the target. 

Maybe this was not the best group to ask the question in.  I thought this was more of a math problem with I started writing the question and the embedded community had already dealt with it.  

-- 

  Rick C.

  + Get 1,000 miles of free Supercharging
  + Tesla referral code - https://ts.la/richard11209

On Thursday, April 20, 2023 at 5:15:04 AM UTC-4, Niklas Holsti wrote:
> On 2023-04-20 5:06, Rick C wrote: 
> > This is a bit of the chicken and egg thing. If you want a embed a 
> > checksum in a code module to report the checksum, is there a way of 
> > doing this? It's a bit like being your own grandfather, I think. 
> > 
> > I'm not thinking anything too fancy, like a CRC, but rather a simple 
> > modulo N addition, maybe N being 2^16.
> Some decades ago I was involved with a project for an 8052-based device, 
> which was required to perform a code-check-sum check at boot. 
> 
> We decided to use a byte-per-byte xor checksum and make the correct 
> check-sum be zero. We had a code module (possibly in assembler, I don't 
> remember) that defined a one-byte "adjustment" constant in code memory. 
> For each new version of the code, we first set the adjustment constant 
> to zero, then ran the program, and it usually reported an error at boot 
> because the check-sum was not zero. We then changed the adjustment 
> constant to the actual reported checksum, C say, and that zeroed the 
> check-sum because C xor C = 0. Bingo. You can use this method to make 
> the checksum anything you like, for example hex 55. 
> 
> With a more advanced order-sensitive check-sum such as a CRC you could 
> use the same method if you also ensure (by linker commands) that the 
> adjustment value is always the last value that enters in the computed 
> check-sum (assuming that the linking order of the other code modules is 
> not incidentally changed when the value of the adjustment constant is 
> changed).

Yes, it had occurred to me that a simple checksum could be used with adjustment codes.  But I don't want the checksum to be set to some value, in this way.  I would like to embed the check sum generated from the file.  The way to do this is to embed the checksum in the spot where it can be read for reporting.  Then another value can be embedded elsewhere, that complements the checksum, keeping the file checksum constant.  

Your mention of the XOR checksum makes me realize that if I use addition, rather than XOR, a 16 bit checksum only has a complement if the data used in the calculation are 16 bit quantities.  If the 16 bit checksum is calculated using 8 bit data, there will be a carry out of the lower 8 bits changing the final checksum.  The XOR checksum is really the equivalent of 8 separate bit level checksums.  This has the short coming of one bit detection, but two bit changes in the same bit of two bytes not being detected.  But since I'm not trying to protect against changes, this isn't really a problem.  I'm using this as a verification of the version number.  

-- 

  Rick C.

  -- Get 1,000 miles of free Supercharging
  -- Tesla referral code - https://ts.la/richard11209

On 20/04/2023 04:06, Rick C wrote:
> This is a bit of the chicken and egg thing.  If you want a embed a
> checksum in a code module to report the checksum, is there a way of
> doing this?  It's a bit like being your own grandfather, I think.
> 
> I'm not thinking anything too fancy, like a CRC, but rather a simple
> modulo N addition, maybe N being 2^16.
> 
> I keep thinking of using a placeholder, but that doesn't seem to work
> out in any useful way.  Even if you try to anticipate the impact of
> adding the checksum, that only gives you a different checksum, that
> you then need to anticipate further... ad infinitum.
> 
> I'm not thinking of any special checksum generator that excludes the
> checksum data.  That would be too messy.
> 
> I keep thinking there is a different way of looking at this to
> achieve the result I want...
> 
> Maybe I can prove it is impossible.  Assume the file checksums to X
> when the checksum data is zero.  The goal would then be to include
> the checksum data value Y in the file, that would change X to Y.
> Given the properties of the module N checksum, this would appear to
> be impossible for the general case, unless...  Add another data
> value, called, checksum normalizer.  This data value checksums with
> the original checksum to give the result zero.  Then, when the
> checksum is also added, the resulting checksum is, in fact, the
> checksum.  Another way of looking at this is to add a value that
> combines with the added checksum, to be zero, leaving the original
> checksum intact.
> 
> This might be inordinately hard for a CRC, but a simple checksum
> would not be an issue, I think.  At least, this could work in
> software, where data can be included in an image file as itself.  In
> a device like an FPGA, it might not be included in the bit stream
> file so directly... but that might depend on where in the device it
> is inserted.  Memory might have data that is stored as itself.  I'll
> need to look into that.
> 


I am not sure what your intended use-case is here.  But it is very 
common to add a checksum of some sort to binary image files after 
generating them.  This is done post-link.  You have a struct in your 
read-only data that you link at a known fixed point in the binary.  Your 
post-link patcher can read this struct (for example, to get the program 
version number that is then used to rename the final image file).  It 
can modify the struct (such as inserting the length of the image).  Then 
it calculates a CRC and appends it to the end of the image.

On Wed, 19 Apr 2023 19:06:33 -0700 (PDT), Rick C
<gnuarm.deletethisbit@gmail.com> wrote:

>This is a bit of the chicken and egg thing.  If you want a embed a
>checksum in a code module to report the checksum, is there a way of
>doing this?  It's a bit like being your own grandfather, I think. 

Take a look at the old xmodem/ymodem CRC.  It was designed such that
when the CRC was sent immediately following the data, a receiver
computing CRC over the whole incoming packet (data and CRC both) would
get a result of zero.

But AFAIK it doesn't work with CCITT equation(s) - you have to use
xmodem/ymodem.


>I'm not thinking anything too fancy, like a CRC, but rather a simple
>modulo N addition, maybe N being 2^16.  

Sorry, I don't know a way to do it with a modular checksum.
YMMV, but I think 16-bit CRC is pretty simple.

George

On Thursday, April 20, 2023 at 11:33:28 AM UTC-4, George Neuner wrote:
> On Wed, 19 Apr 2023 19:06:33 -0700 (PDT), Rick C 
> <gnuarm.del...@gmail.com> wrote: 
> 
> >This is a bit of the chicken and egg thing. If you want a embed a 
> >checksum in a code module to report the checksum, is there a way of 
> >doing this? It's a bit like being your own grandfather, I think.
> Take a look at the old xmodem/ymodem CRC. It was designed such that 
> when the CRC was sent immediately following the data, a receiver 
> computing CRC over the whole incoming packet (data and CRC both) would 
> get a result of zero. 
> 
> But AFAIK it doesn't work with CCITT equation(s) - you have to use 
> xmodem/ymodem.
> >I'm not thinking anything too fancy, like a CRC, but rather a simple 
> >modulo N addition, maybe N being 2^16.
> Sorry, I don't know a way to do it with a modular checksum. 
> YMMV, but I think 16-bit CRC is pretty simple. 
> 
> George

CRC is not complicated, but I would not know how to calculate an inserted value to force the resulting CRC to zero.  How do you do that? 

Even so, I'm not trying to validate the file.  I'm trying to come up with a substitute for a time stamp or version number.  I don't want to have to rely on my consistency in handling the version number correctly.  This would be a backup in case there was more than one version released, even only within the "lab", that were different.  A checksum that could be read by the controlling software would do the job.  

I have run into this before, where the version number was not a 100% indication of the uniqueness of an executable.  The checksum would be a second indicator. 

I should mention that I'm not looking for a solution that relies on any specific details of the tools. 

-- 

  Rick C.

  -+ Get 1,000 miles of free Supercharging
  -+ Tesla referral code - https://ts.la/richard11209

On 20.4.2023 18.33, George Neuner wrote:
> On Wed, 19 Apr 2023 19:06:33 -0700 (PDT), Rick C
> <gnuarm.deletethisbit@gmail.com> wrote:
> 
>> This is a bit of the chicken and egg thing.  If you want a embed a
>> checksum in a code module to report the checksum, is there a way of
>> doing this?  It's a bit like being your own grandfather, I think.
> 
> Take a look at the old xmodem/ymodem CRC.  It was designed such that
> when the CRC was sent immediately following the data, a receiver
> computing CRC over the whole incoming packet (data and CRC both) would
> get a result of zero.
> 
> But AFAIK it doesn't work with CCITT equation(s) - you have to use
> xmodem/ymodem.
> 
> 
>> I'm not thinking anything too fancy, like a CRC, but rather a simple
>> modulo N addition, maybe N being 2^16.
> 
> Sorry, I don't know a way to do it with a modular checksum.
> YMMV, but I think 16-bit CRC is pretty simple.
> 
> George


The method to check for a proper constant value after the whole
block and CRC are received and put through the generator works
with the CRC-CCITT (actually ITU-T). The proper final value
depends on the initial CRC and whether the CRC is inverted before
sending. The limitation is that the CRC has to be sent least
significant octet first.

For a reference, see RFC1662, Appendix C.

-- 

-TV