Help on a (probably) "custom" CRC

[P13r0]

Hi all, and thank you in advance for your help.

Here's my issue.
I was recently given a small router (GO-DSL-AC750), and I'm trying to modify it's firmware. My goal is to have it executing a small script at boot time.
I have unpacked the firmware file (which contains kernel + filesystem), modified the filesystem and packed all back; but I'm experiencing problems with a couple of checksums located at the end of the file, which (obviously) need to be changed accordingly:

00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 15 0E FB 00 15 0F 00 00 7B 90 00 BB BB BB BB
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 30 31 32 33 34 35 36 37
38 39 00 00 00 00 00 00 52 32 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 6D 74 37 35 31 78 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 90 9F 00 00 00 00 01
54 42 53 54 4C 56 30 31 00 00 00 00 AA AA AA AA

Both checksums are 4 bytes long. The final checksum ("AA AA AA AA") is not a problem, because the router's bootloader (while checking the f/w file, before loading it in flash) finds it's wrong, and declares the expected (right) value; but for the other one ("BB BB BB BB")... no such luck :(

I have downloaded the bootloader's source code, and found that both checksums are managed/checked by the same function (tbs_calc_sum_addr):

(code for "AA AA AA AA")

(...)

	if(update_flag & F_CRC_CHECK) {/* Check file CRC by default, jump this step when force enabled */
		tbs_calc_sum_addr(buf, &checksum, len - i + VERSION_LEN);
		if(checksum != uppa->tail.image_checksum) {
			printf("File CRC 0x%08x check failed, expecting 0x%08x\n", checksum, uppa->tail.image_checksum);
			ret_val = ERROR_CRC;
			goto err;
		}
(...)

(code for "BB BB BB BB")

(...)

{
    unsigned long crc_checksum;
    unsigned int len;
    int ret_val = -ERROR_CRC;
    struct sys_cfg *syscfg;

    syscfg = (struct sys_cfg *)(gd->syscfg_addr);
    if(0 == first_second_flag)
		{ // 从第一个image启动
		len = syscfg->first_rootfs_offset + syscfg->first_rootfs_len - syscfg->first_kernel_offset;
		fldebug("first_rootfs_offset=%08x first_rootfs_len=%08x first_kernel_offset=%08x firlen=%08x\n",			    syscfg->first_rootfs_offset, syscfg->first_rootfs_len, syscfg->first_kernel_offset, len);
		flash_read_buf(info, (unsigned long *)(CONFIG_FLASH_BASE + syscfg->first_kernel_offset), &buf, len);
		tbs_calc_sum_addr(buf, &crc_checksum, len);
		if(syscfg->first_image_checksum == crc_checksum)
			{
			ret_val = ERROR_OK;
			}
		else
			{
			printf("First image CRC validation failed\n");
			fldebug("first_image_checksum=0x%08x, crc_checksum=0x%08x\n", syscfg->first_image_checksum, crc_checksum);
			}

(...)

Then I found that tbs_calc_sum_addr (in bootloader's source code) is inside a file called crc32.c; but even if those "checksums" are 32 bits long, they're not CRC32....

(see next post)

[P13r0]

Here's crc32.c:

/* crc32.c -- compute the CRC-32 of a data stream
 * Copyright (C) 1995-2002 Mark Adler
 * For conditions of distribution and use, see copyright notice in zlib.h 
 */

/* @(#) $Id: crc32.c,v 1.1.1.1 2006/06/07 05:27:50 kaohj Exp $ */

#include "zlib.h"
#include <crc.h>

#define local static

#ifdef DYNAMIC_CRC_TABLE

local int crc_table_empty = 1;
local uLongf crc_table[256];
local void make_crc_table OF((void));

/*
  Generate a table for a byte-wise 32-bit CRC calculation on the polynomial:
  x^32+x^26+x^23+x^22+x^16+x^12+x^11+x^10+x^8+x^7+x^5+x^4+x^2+x+1.

  Polynomials over GF(2) are represented in binary, one bit per coefficient,
  with the lowest powers in the most significant bit.  Then adding polynomials
  is just exclusive-or, and multiplying a polynomial by x is a right shift by
  one.  If we call the above polynomial p, and represent a byte as the
  polynomial q, also with the lowest power in the most significant bit (so the
  byte 0xb1 is the polynomial x^7+x^3+x+1), then the CRC is (q*x^32) mod p,
  where a mod b means the remainder after dividing a by b.

  This calculation is done using the shift-register method of multiplying and
  taking the remainder.  The register is initialized to zero, and for each
  incoming bit, x^32 is added mod p to the register if the bit is a one (where
  x^32 mod p is p+x^32 = x^26+...+1), and the register is multiplied mod p by
  x (which is shifting right by one and adding x^32 mod p if the bit shifted
  out is a one).  We start with the highest power (least significant bit) of
  q and repeat for all eight bits of q.

  The table is simply the CRC of all possible eight bit values.  This is all
  the information needed to generate CRC's on data a byte at a time for all
  combinations of CRC register values and incoming bytes.
*/
local void make_crc_table()
{
  uLong c;
  int n, k;
  uLong poly;            /* polynomial exclusive-or pattern */
  /* terms of polynomial defining this crc (except x^32): */
  static const Byte p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26};

  /* make exclusive-or pattern from polynomial (0xedb88320L) */
  poly = 0L;
  for (n = 0; n < sizeof(p)/sizeof(Byte); n++)
    poly |= 1L << (31 - p[n]);
 
  for (n = 0; n < 256; n++)
  {
    c = (uLong)n;
    for (k = 0; k < 8; k++)
      c = c & 1 ? poly ^ (c >> 1) : c >> 1;
    crc_table[n] = c;
  }
  crc_table_empty = 0;
}
#else
/* ========================================================================
 * Table of CRC-32's of all single-byte values (made by make_crc_table)
 */
local const uLongf crc_table[256] = {
  0x00000000L, 0x77073096L, 0xee0e612cL, 0x990951baL, 0x076dc419L,
  0x706af48fL, 0xe963a535L, 0x9e6495a3L, 0x0edb8832L, 0x79dcb8a4L,
  0xe0d5e91eL, 0x97d2d988L, 0x09b64c2bL, 0x7eb17cbdL, 0xe7b82d07L,
  0x90bf1d91L, 0x1db71064L, 0x6ab020f2L, 0xf3b97148L, 0x84be41deL,
  0x1adad47dL, 0x6ddde4ebL, 0xf4d4b551L, 0x83d385c7L, 0x136c9856L,
  0x646ba8c0L, 0xfd62f97aL, 0x8a65c9ecL, 0x14015c4fL, 0x63066cd9L,
  0xfa0f3d63L, 0x8d080df5L, 0x3b6e20c8L, 0x4c69105eL, 0xd56041e4L,
  0xa2677172L, 0x3c03e4d1L, 0x4b04d447L, 0xd20d85fdL, 0xa50ab56bL,
  0x35b5a8faL, 0x42b2986cL, 0xdbbbc9d6L, 0xacbcf940L, 0x32d86ce3L,
  0x45df5c75L, 0xdcd60dcfL, 0xabd13d59L, 0x26d930acL, 0x51de003aL,
  0xc8d75180L, 0xbfd06116L, 0x21b4f4b5L, 0x56b3c423L, 0xcfba9599L,
  0xb8bda50fL, 0x2802b89eL, 0x5f058808L, 0xc60cd9b2L, 0xb10be924L,
  0x2f6f7c87L, 0x58684c11L, 0xc1611dabL, 0xb6662d3dL, 0x76dc4190L,
  0x01db7106L, 0x98d220bcL, 0xefd5102aL, 0x71b18589L, 0x06b6b51fL,
  0x9fbfe4a5L, 0xe8b8d433L, 0x7807c9a2L, 0x0f00f934L, 0x9609a88eL,
  0xe10e9818L, 0x7f6a0dbbL, 0x086d3d2dL, 0x91646c97L, 0xe6635c01L,
  0x6b6b51f4L, 0x1c6c6162L, 0x856530d8L, 0xf262004eL, 0x6c0695edL,
  0x1b01a57bL, 0x8208f4c1L, 0xf50fc457L, 0x65b0d9c6L, 0x12b7e950L,
  0x8bbeb8eaL, 0xfcb9887cL, 0x62dd1ddfL, 0x15da2d49L, 0x8cd37cf3L,
  0xfbd44c65L, 0x4db26158L, 0x3ab551ceL, 0xa3bc0074L, 0xd4bb30e2L,
  0x4adfa541L, 0x3dd895d7L, 0xa4d1c46dL, 0xd3d6f4fbL, 0x4369e96aL,
  0x346ed9fcL, 0xad678846L, 0xda60b8d0L, 0x44042d73L, 0x33031de5L,
  0xaa0a4c5fL, 0xdd0d7cc9L, 0x5005713cL, 0x270241aaL, 0xbe0b1010L,
  0xc90c2086L, 0x5768b525L, 0x206f85b3L, 0xb966d409L, 0xce61e49fL,
  0x5edef90eL, 0x29d9c998L, 0xb0d09822L, 0xc7d7a8b4L, 0x59b33d17L,
  0x2eb40d81L, 0xb7bd5c3bL, 0xc0ba6cadL, 0xedb88320L, 0x9abfb3b6L,
  0x03b6e20cL, 0x74b1d29aL, 0xead54739L, 0x9dd277afL, 0x04db2615L,
  0x73dc1683L, 0xe3630b12L, 0x94643b84L, 0x0d6d6a3eL, 0x7a6a5aa8L,
  0xe40ecf0bL, 0x9309ff9dL, 0x0a00ae27L, 0x7d079eb1L, 0xf00f9344L,
  0x8708a3d2L, 0x1e01f268L, 0x6906c2feL, 0xf762575dL, 0x806567cbL,
  0x196c3671L, 0x6e6b06e7L, 0xfed41b76L, 0x89d32be0L, 0x10da7a5aL,
  0x67dd4accL, 0xf9b9df6fL, 0x8ebeeff9L, 0x17b7be43L, 0x60b08ed5L,
  0xd6d6a3e8L, 0xa1d1937eL, 0x38d8c2c4L, 0x4fdff252L, 0xd1bb67f1L,
  0xa6bc5767L, 0x3fb506ddL, 0x48b2364bL, 0xd80d2bdaL, 0xaf0a1b4cL,
  0x36034af6L, 0x41047a60L, 0xdf60efc3L, 0xa867df55L, 0x316e8eefL,
  0x4669be79L, 0xcb61b38cL, 0xbc66831aL, 0x256fd2a0L, 0x5268e236L,
  0xcc0c7795L, 0xbb0b4703L, 0x220216b9L, 0x5505262fL, 0xc5ba3bbeL,
  0xb2bd0b28L, 0x2bb45a92L, 0x5cb36a04L, 0xc2d7ffa7L, 0xb5d0cf31L,
  0x2cd99e8bL, 0x5bdeae1dL, 0x9b64c2b0L, 0xec63f226L, 0x756aa39cL,
  0x026d930aL, 0x9c0906a9L, 0xeb0e363fL, 0x72076785L, 0x05005713L,
  0x95bf4a82L, 0xe2b87a14L, 0x7bb12baeL, 0x0cb61b38L, 0x92d28e9bL,
  0xe5d5be0dL, 0x7cdcefb7L, 0x0bdbdf21L, 0x86d3d2d4L, 0xf1d4e242L,
  0x68ddb3f8L, 0x1fda836eL, 0x81be16cdL, 0xf6b9265bL, 0x6fb077e1L,
  0x18b74777L, 0x88085ae6L, 0xff0f6a70L, 0x66063bcaL, 0x11010b5cL,
  0x8f659effL, 0xf862ae69L, 0x616bffd3L, 0x166ccf45L, 0xa00ae278L,
  0xd70dd2eeL, 0x4e048354L, 0x3903b3c2L, 0xa7672661L, 0xd06016f7L,
  0x4969474dL, 0x3e6e77dbL, 0xaed16a4aL, 0xd9d65adcL, 0x40df0b66L,
  0x37d83bf0L, 0xa9bcae53L, 0xdebb9ec5L, 0x47b2cf7fL, 0x30b5ffe9L,
  0xbdbdf21cL, 0xcabac28aL, 0x53b39330L, 0x24b4a3a6L, 0xbad03605L,
  0xcdd70693L, 0x54de5729L, 0x23d967bfL, 0xb3667a2eL, 0xc4614ab8L,
  0x5d681b02L, 0x2a6f2b94L, 0xb40bbe37L, 0xc30c8ea1L, 0x5a05df1bL,
  0x2d02ef8dL
};
#endif

/* =========================================================================
 * This function can be used by asm versions of crc32()
 */
const uLongf * ZEXPORT get_crc_table()
{
#ifdef DYNAMIC_CRC_TABLE
  if (crc_table_empty) make_crc_table();
#endif
  return (const uLongf *)crc_table;
}

/* ========================================================================= */
#define DO1(buf) crc = crc_table[((int)crc ^ (*buf++)) & 0xff] ^ (crc >> 8);
#define DO2(buf)  DO1(buf); DO1(buf);
#define DO4(buf)  DO2(buf); DO2(buf);
#define DO8(buf)  DO4(buf); DO4(buf);

/* ========================================================================= */
uLong ZEXPORT crc32(uLong crc, const Bytef *buf, uInt len)
{
    if (buf == Z_NULL) return 0L;
#ifdef DYNAMIC_CRC_TABLE
    if (crc_table_empty)
      make_crc_table();
#endif
    crc = crc ^ 0xffffffffL;
    while (len >= 8)
    {
      DO8(buf);
      len -= 8;
    }
    if (len) do {
      DO1(buf);
    } while (--len);
    return crc ^ 0xffffffffL;
}

uLong ZEXPORT gz_crc32(uLong crc, const Bytef *buf, uInt len)
{
    return crc32(crc, buf, len);
}

void tbs_calc_sum_addr(unsigned char *cp, unsigned long *res,unsigned int size)
{
	unsigned long crc = 0;
	unsigned int length = 0;

	length = size;	
	while(size--)
		crc =(crc << 8) ^ crc_table[((crc >> 24) ^ *cp++) & 0xFF];

	for(; length; length >>= 8)
		crc =(crc << 8) ^ crc_table[((crc >> 24) ^ length) & 0xFF];

	crc = ~crc & 0xFFFFFFFF;

	*res = crc;
}

And at the end, this is my question: since I have no (zero) knowledge about C/C++, is there anyone who could explain me what calculation that function does, since it's not a CRC32? In other words: how could I obtain the result, using a different way (a tool, or something lika that)?

Sorry for my poor English (and for my poor question, too)...
... and again: thank you in advance for your help.


Regards

[salem c]

> I have unpacked the firmware file (which contains kernel + filesystem), modified the filesystem and packed all back;
Did you first try unpack + pack without actually changing anything to make sure you could perform a round-trip?

> len = syscfg->first_rootfs_offset + syscfg->first_rootfs_len - syscfg->first_kernel_offset;
> fldebug("first_rootfs_offset=%08x first_rootfs_len=%08x first_kernel_offset=%08x firlen=%08x\n" ...
1. Do you see fldebug messages anywhere?
2. If you modified the file system, did you also modify the syscfg field which contains the length?

Links to where you found the apparent source code would be useful.

[P13r0]

First of all: thank you for your reply.

Did you first try unpack + pack without actually changing anything to make sure you could perform a round-trip?

No, I didn't. You're right, maybe I'll have further problems with this... but first I must be able to correctly compute those CRCs; otherwise I can't verify, nor set the right compression algorithm's parameters.

Do you see fldebug messages anywhere?

Unfortunately, no.
I've just built a TTL<>RS232 i/f to see bootloader's (console) messages, during a firmware upgrade... and I've seen that changing a single bit in firmware's file is enough to change its "final" CRC. In other words: the "final" CRC ("AA AA AA AA") is computed taking into account all the preceding bytes (while the other CRC, "BB BB BB BB", needs further investigations).
Here are my tests, working on f/w "GO-DSL-AC750_fw_revt_108_ALL_multi_20161129"; the final CRC of this f/w is 0x6f304512 (...while CRC-32 of the same file is 0x63a43ae1):

Test 1 - Modified byte in position 00, from 0x5D to 0x4D

TBS bootloader V1.0 Build6942 for DLINK_AC750(May 12 2014-11:27:05)

DRAM: 64 MB
FLASH: 16 MB S25FL128P at mode 1
Switch: MT7510FE
IP: 192.168.1.1 MAC: ec:22:80:0c:82:18
Hit Space or Enter key to stop autoboot: 0
Listening on local port 80
MT751X# Connection was closed!
Listening on local port 80
Connection was reset!
Listening on local port 80
Connection was closed!
Listening on local port 80
Connection was reset!
Listening on local port 80
http_content_length=9478259
Data start point found!
Data end point found!
received_content_len =9478259
data_length=9478048, update_flag=31
Found the tail information
File CRC 0x631c04ba check failed, expecting 0x6f304512
Connection was closed!

(Note: the underlined value is -obviously!- the right CRC of the just uploaded file, since it's computed by tbs_calc_sum_addr. The italic value is the content of last 4 bytes of the file. If these values differ,the upload procedure stops, before writing on MTD.
I """just""" need to understand how tbs_calc_sum_addr works to obtain the right CRC...)


Test 2 - Modified byte in position 01, from 0x00 to 0x01

http_content_length=9478259
Data start point found!
Data end point found!
received_content_len =9478259
data_length=9478048, update_flag=31
Found the tail information
File CRC 0xfe264875 check failed, expecting 0x6f304512
Connection was closed!


Test 3 - Modified byte in position 909F9B (last byte before CRC), from 0x00 to 0x01

http_content_length=9478259
Data start point found!
Data end point found!
received_content_len =9478259
data_length=9478048, update_flag=31
Found the tail information
File CRC 0xf7bdb324 check failed, expecting 0x6f304512
Connection was closed!


Test 4 - Modified byte in position 909F9F (last byte of file, last of "final" CRC), from 0x12 to 0x11

http_content_length=9478259
Data start point found!
Data end point found!
received_content_len =9478259
data_length=9478048, update_flag=31
Found the tail information
File CRC 0x6f304512 check failed, expecting 0x6f304511
Connection was closed!

Again: in my opinion, it would be enough to understand what tbs_calc_sum_addr does to obtain those 4 bytes. In other words, what's the difference between a "classic" CRC-32 and this one.

If you modified the file system, did you also modify the syscfg field which contains the length?

Yes. The modded f/w is loadable, and it COULD work... but after rebooting, the router stops with

First image CRC validation failed

For f/w and (GPL) source code, you can enter

ftp://ftp.dlink.de/go/go-dsl-ac750/driver_software/ 

Thank you for your help... I still hope to find a way.
"Playfully doing something difficult, whether useful or not, that is hacking" :)


Regards

[Cubbi]

for what it's worth, I once had to interface with a device that used a non-standard CRC, and found that boost.crc was able to match that algorithm with the right combination of its four template parameters
(it wasn't any of the predefined ones https://www.boost.org/doc/libs/1_70_0/doc/html/crc/crc_samples.html , though I'd start with those in your case)

[jonnin]

I have used sunshine's page to reverse engineer a few CRCs. If you know the expected input and output, you can try to find the polynomial and final adjuster used easily and it has most of the major ones already coded so you can try the high probability crcs first. There are ... A LOT of possible 32 bit crcs out there. But in a router, its likely used one of the known ones because the vast majority of crcs do not correct as many bits as the good ones can.

if you want to try it:
http://www.sunshine2k.de/coding/javascript/crc/crc_js.html

[P13r0]

@Cubbi, @jonnin

Thank you for your suggestions, but I guess (...or better: I hope...) that having access to the source code of router's CRC computing algorithm, brute force should not be an option.
In other words: I hope that someone is able to read that function's core,

void tbs_calc_sum_addr(unsigned char *cp, unsigned long *res,unsigned int size)
{
	unsigned long crc = 0;
	unsigned int length = 0;

	length = size;	
	while(size--)
		crc =(crc << 8) ^ crc_table[((crc >> 24) ^ *cp++) & 0xFF];

	for(; length; length >>= 8)
		crc =(crc << 8) ^ crc_table[((crc >> 24) ^ length) & 0xFF];

	crc = ~crc & 0xFFFFFFFF;

	*res = crc;
}

and explain me how could I compute it; pointing me to the right polynomial, xor values and so on -in order to use a public CRC computing tool, if possible- or helping me in writing / compiling a specific tool (using pocketcpp, for example).

...Not so nice, I agree. But after months of attempts, I can tell that I'll never get out by myself :(

Regards

[jonnin]

That 'crc' routine is nonstandard. I tied it to the one I use, using the same polynomial, and the results are very different. And I know mine is matching as I tested it on millions of records with 100% identical results to the target one.

all I know to tell you to do is export your crc table and make a program on your machine that runs this code against the input. If that matches, run it on the data, get the value, and put the answer back in where it goes.

[P13r0]

Ok, a good friend of mine did it :)

int main(int ac, char** av) {  
	
	FILE* fp;
	unsigned long crc;
	char *buf;
	long size;
	
	if (ac == 2) {
		fp = fopen(av[1], "rb");
		if (fp != 0) {

			fseek(fp, 0, SEEK_END);
			size = ftell(fp);
			fseek(fp, 0, SEEK_SET);
			
			buf = (char*)calloc(size+1, 1);
			fread(buf, 1, size, fp);
			printf("Letti %d bytes del file di input %s\n", size, (char*)av[1]);
			
			tbs_calc_sum_addr((unsigned char*)buf, &crc, size);
			if (!ferror(fp)) 
				printf("CRC: %08X per il file %s\n", crc, av[1]);
			
			fclose(fp); 
			
			free(buf);
		}
		else {
			printf("non sono riuscito ad aprire il file in input: '%s'", av[1]);
		}
	}
	else {
		printf("Utilizzare questo programma con un solo argomento di input: il file di cui si vuole calcolare il CRC.");
	}
	return 0;
}

Regards