EDC16C34 checksum algorithm

[JeanLuc38]

Hello,

I'm trying to understand how the checksum of EDC16C34 (PSA) is calculated.
I already found the 1024bits RSA key and managed to decrypt the signature.
The RSA modulus and public exponent (3) is located in the code zone (before 0x1c0000) and it is easy to find it in a full dump.
(find a 1024 bit big endian number that is not easy to factor and not prime, then check the sig with found canditates)
The 1024bits signature is located at 0x1FDF7C (in the MAP zone) and is readable via OBD.
All my dump collection of PSA EDC16C34 share the same RSA public key (modulus and exponent).
You can devryt the signature by doing the follwoing:



BigInteger n = new BigInteger(
"9f63259b570099e4435112058526405d"+
"edd701b8b51d42d80b46c71839171620"+
"fe91c5d46aaf2ccf8921b6eb56c62f46"+
"4f2930d1b0970bb77c686a30123400ef"+
"b406bff133151cc4100b4d715c038f0f"+
"50aa247e5b710e0a8893de467077d169"+
"db2c496d7205c3c44a6b3b1e37bfa03b"+
"35d9a44f1879f76523ffde1a0e501151",
16
);

BigInteger a = new BigInteger(
"7C0BAF52E70054CFECBC7E14F41C9E39"+
"D33E2501083F2455872B7B47A35D3D5D"+
"1538D15D2C50D0D6B8A88A852A5349EB"+
"A27585936055E0F8890B4B0C5C1823C2"+
"D844357A6AA4F050541BA790D0EC9AEB"+
"DE78DB8E2D5A76821B6A1E0D45167054"+
"E114E5B148CFCAD8E6BDAF5797CA0770"+
"6879D768FED02193F4DC53D7727D8685"
,16);

BigInteger sig = a.pow(3).mod(n);
System.out.println(sig.toString(16) + " " + sig.bitLength() + "bits");

Output:

1ffffffffffffffff00c371e42fdb4d3808b3f0559437cb20f 6000000003931330000000000000000000000000031343a313 03a34312030332d30382d3037e42d139c6adc1f855d87000ed 8052481c7b494d198fe81a92a2406ab30c3a3ae953d4a3d2a5 f621e207cb62f9d5fad5ef735b7fccce4594796f1b458ee560 c5a


An original signature looks like this:


0001ffffffffffffffff00feda839f0a536be7114da06cde4a c7f6000000003931310000000000000000000000000031343a 31393a34322031362d31312d3036dc6c083a64afccdfa711c8 984d1e5aabdda747ad6f6ad1d5cc3d5fc24044f97cb62bb5f3 5a0249d246b0ced88a9112971f3c4dccec07ce2d994550d938 cf9055
. . . . . . . . . . . . . . . . S k . . M . l . J . . . . . . 9 1 1 . . . . . . . . . . . . . 1 4 : 1 9 : 4 2 1 6 - 1 1 - 0 6 . l . : d . . . . . . . M . Z . . . G . o j . . . = _ . @ D . | . + . . Z . I . F . . . . . . . . < M . . . . - . E P . 8 . . U


A corrected one looks like this:

By winols: winols adds BPG-8101 inside its signature:



9f63259b570099e4435112058526405dedd701b8b51d42d80b 46c71839171620fe91c5d46aaf2ccf8921b6eb56c62f464f29 30d1b0970bb77c686a30123400efb406bff133151cc4100b4d 715c038f0f50aa247e5b4ea0e63e695862d738823786e4ba78 e88203b34fddbc7836aca5162cf87358cb74c65740c5ec0c46 1b1390
0001ffffffffffffffff00885ac5e6fee40cd7f7bbdaaeeb3c 57d14250472d3831303100000000000021c2b276bf784d885d cd17b73bd7e29302512be2e4f2e7831d8fff35951d06feffda 1f4748eb89bad75e5be9a504ab124766b97528da4394e66475 129f716c1c2ed391626cfa47175d5aad3c343cb9e1bef12f9c 85e810
. . . . . . . . . . . . Z . . . . . . . . . . . < W . B P G - 8 1 0 1 . . . . . . ! . . v . x M . ] . . . ; . . . . Q + . . . . . . . . 5 . . . . . . . G H . . . . ^ [ . . . . . G f . u ( . C . . d u . . q l . . . . b l . G . ] Z . < 4 < . . . . / . . . .


By MPPS:


00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 0000000000000000000001428a2f98d728ae220835a672cdd5 ee33c799c5a3418d6b167cc857b3692d5bcdcf4d06ca12be35 68e4ce
0001ffffffffffffffff00885ac5e6fee40cd7f7bbdaaeeb3c 57d1000000000000000000000000000000c0ffb7c19af461d9 ffdb87764502cc89dfadd61a37c3c1ae8350aacccad9a9d540 39d3a0b3756075ad784033a09aa7cdab281803bc6ba3f986b6 4f6cbad447204cdce6d2dda0bd1ea9ccf76787a04a779d3172 ed13b8
. . . . . . . . . . . . Z . . . . . . . . . . . < W . . . . . . . . . . . . . . . . . . . . . . a . . . . v E . . . . . . . 7 . . . . P . . . . . . @ 9 . . . u ` u . x @ 3 . . . . . ( . . . k . . . . O l . . G L . . . . . . . . . . g . . J w . 1 r . . .


We can remark that only the prefix 0001ffffffffffffffff00 followed by the 128 bits hash (MD5) is kept, the other byte are used to find a cubic root (mod n), this is a common RSA failure when the padding is not fully checked.


I manged to locate the MD5 code in the MPC code, here is the routine that initialise the MD5 initial state.
Then follow the MD5 round code.

https://content-eu.invisioncic.com/m304542/monthly_2022_06/large.mpc_md5.jpg.ad122beef4b8b383d90702c3a4fc5b98 .jpg

Now the problem is to find how the MD5 is calculated, i presume it is calculated on several areas and not on the full MAP zone.
I didn't manage to find addresses and length of this areas.
It is also difficult to set all the environement in the TRACE32 debbuger, to run the program and get addresses and length, it is difficult to find information on the boot sector.
So any suggestions or additionnal informations would be welcome :)

Thanks

[metercar]

I applaud your tenacious practice of reverse engineering... but what is the end of it, leaving educational purposes aside?

[JeanLuc38]

Yes it is first for my understanding and to make a checksum correcotor available for free and as open source as i did for this tool https://github.com/JeanLucPons/DTCController.

[metercar]

great job mate!, surely you will find that small contribution for your discovery in this forum or at least the moral support

[JeanLuc38]

Ok, I found out how the MD5 is calculated, now a last point is remaining, the last 32 bits of the checksum area. I will try several CRC32, SUM32, etc, combination...
I'm progressing....

[metercar]

disassemble the code and find the routine that does the checksum...small subroutine at the beginning you will surely find it if you manage to label each subroutine individually

[metercar]

something related must be the malicious code p0606... it is generated hidden at the beginning (surely after this there is a call to the sum) waiting for something to happen... sadly it is just one bit of many

[JeanLuc38]

I managed to compute this last 32bit control sum (it is a -sum32 of the RSA signature) but with some small particularities. I still have to do some checks.
I'm progressing and I'm starting to see the light at the end of the tunnel :D

[JeanLuc38]

I point out a strange thing:

In all the PSA EDC16C34 orig files I have, the last 32bits of the checksum area (@0x1FDFFC) is equal to -0xD01FE500 - sum32[0x1FDF7C..0x1FDFFB].The offset0xD01FE500 is fixed and used in my whole orig dump collection. Winols and MPPS seem to compute an offset which also depends on the MAP zone.
I didn't find in the code of the MPC where this sum is computed and I doubt that this value is really checked by the SW when the engine starts. The MPC code is not obfuscated and this kind of checksum should be easy to detect as for a MD5 checksum.

However, i will perform more test with winols but IMHO, they're is something wrong there in both MPPS and Winols.

[JeanLuc38]

Hello,

Here is a small code that corrects the checksums (the result is seen ok by winols).
You can find the RSA attack which is very fast due to the large number of free bits.




package ASAP2;

import com.sun.deploy.security.RootCertStore;

import java.io.IOException;
import java.math.BigInteger;
import java.nio.file.Files;
import java.nio.file.Path;
import java.nio.file.Paths;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;

class RootResult {
BigInteger y;
boolean isPerfectRoot;
}

public class EDC16RSA {

static public RootResult nthroot(BigInteger x,int nth) {

RootResult r = new RootResult();

// Finds the integer component of the n'th root of x,
// or an integer such that y^n < x < (y + 1)^n

BigInteger high = new BigInteger("1");
while(high.pow(nth).compareTo(x)<=0) {
high = high.shiftLeft(1);
}
BigInteger low = new BigInteger(String.valueOf(high));
low = low.shiftRight(1);
boolean eof = false;
while(!eof) {
BigInteger mid = low.add(high);
mid = mid.shiftRight(1);
if(mid.pow(nth).compareTo(x)<0) {
low = mid;
} else if (mid.pow(nth).compareTo(x)>0) {
high = mid;
} else {
// Perfect root
r.y = mid;
r.isPerfectRoot = true;
return r;
}
BigInteger diff = high.subtract(low);
eof = diff.compareTo(BigInteger.ONE)<=0;
}
// Not a perfect root
r.y = low;
r.isPerfectRoot = false;
return r;

}

public static BigInteger RSARootAttack1024(BigInteger sig,BigInteger n,int nth,int freeBit) {

// Sig has his message in the first (1024 - freeBit) bits. Other bits are unused.
// Try to find a RSA signature x such that pow(x,nth) = sig + offset(freeBit) + (lambda).n

RootResult rr = null;
boolean eos = false;
while( !eos ) {
rr = nthroot(sig, nth);
eos = rr.isPerfectRoot;
if(!eos) {
BigInteger offset = rr.y.add(BigInteger.ONE).pow(nth).subtract(sig);
if(offset.bitLength()<freeBit)
// done
sig = sig.add(offset);
else
// one more lambda
sig = sig.add(n);
}
}

return rr.y.mod(n);

}

public static byte[] loadDump(String fileName) throws IOException {

// Load a dump
byte ret[];
Path p = Paths.get(fileName);
ret = Files.readAllBytes(p);
System.out.println(fileName + ": " + ret.length + " dump bytes loaded.");
return ret;

}

public static void saveDump(String fileName,byte[] dump) throws IOException {

// Save a dump
Path p = Paths.get(fileName);
Files.write(p,dump);
System.out.println("Write: " + fileName);

}

public static BigInteger getBI(byte[] dump,int address,int size) {

// Extract BigInteger from the dump
StringBuffer buff = new StringBuffer();
for(int i=0;i<size;i++)
buff.append(String.format("%02X",dump[address+i]));
return new BigInteger(buff.toString(),16);

}


public static byte[] getBuffer(BigInteger a,int size) {
byte[] ret = new byte[size];
byte[] buff = a.toByteArray();
int h = ret.length - buff.length;
int o = 0;
int l = buff.length;
if(h<0) {
o = -h;
h = 0;
l = size;
}
System.arraycopy(buff,o,ret,h,l);
return ret;
}

public static String getASCII(byte[] array) {

StringBuffer buff = new StringBuffer();

buff.append(". ");
for(int i=0;i<array.length;i++ ) {
byte b = array[i];
if(b>=32 && b<=127)
buff.append((char)b + " ");
else
buff.append(". ");
}
return buff.toString();

}

public static String getHex(byte[] array) {
return getHex(array,true);
}

public static String getHex(byte[] array,boolean insertSpace) {
StringBuffer buff = new StringBuffer();
for(int i=0;i<array.length;i++) {
if(insertSpace && i%4==0 && i!=0) buff.append(" ");
buff.append(String.format("%02x", array[i]));
}
return buff.toString();
}

public static long getU32(byte[] dump, int addr, boolean littleEndian) {

long b0 = ((long)dump[addr+0]) & 0xFF;
long b1 = ((long)dump[addr+1]) & 0xFF;
long b2 = ((long)dump[addr+2]) & 0xFF;
long b3 = ((long)dump[addr+3]) & 0xFF;

if(littleEndian) {
return (b3<<24) + (b2<<16) + (b1<<8) + b0;
} else {
return (b0 << 24) + (b1 << 16) + (b2 << 8) + b3;
}

}

public static long SUM32(byte[] dump,int start,int end) {

long sum = 0;
for(int i=start;i<end;i+=4)
sum += EDC16RSA.getU32(dump,i,false);
return sum;

}

public static long computeCS1(byte[] dump,long offset) {

// Compute MAP checksum
// All orig file using RSA has an offset of 0 and
// This CS might not be checked by the ECU
long sum = 0xA03FCA00L - SUM32(dump,0x1c0000,0x1FDF78) + offset;
return sum&0xFFFFFFFFL;

}

public static long computeCS2(byte[] dump,long offset) {

// Compute signature checksum
// All orig file using RSA has an offset of 0
// This CS might not be checked by the ECU
long sum = 0x2FE01B00L - SUM32(dump, 0x1FDF7C,0x1FDFFC) + offset;
return sum&0xFFFFFFFFL;

}

public static byte[] extractMD5(byte[] sig) {

// Extract MD5 from the signature (must be 128 byte array)
byte[] retMD5 = new byte[16];
System.arraycopy(sig,11,retMD5,0,16);
return retMD5;

}

public static byte[] computeMD5(byte[] dump) {

// Compute the MD5 of the MAP area
try {
MessageDigest md = MessageDigest.getInstance("MD5");
md.update(dump, 0x1c0000, 0x3DF7C);
return md.digest();
} catch (NoSuchAlgorithmException e) {
System.out.println("Failed to get MD5: " + e.getMessage());
}

return null;

}

public static boolean checkSig(byte[] sig) {

// Check RSA signature prefix
return
(sig[0] == 0) &&
(sig[1] == 1) &&
(sig[2] == -1) &&
(sig[3] == -1) &&
(sig[4] == -1) &&
(sig[5] == -1) &&
(sig[6] == -1) &&
(sig[7] == -1) &&
(sig[8] == -1) &&
(sig[9] == -1) &&
(sig[10] == 0);

}

public static void exitError(String err) {
System.out.println(err);
System.exit(0);
}

public static void main (String args[]) {

// RSA modulus, public exponent is 3
// This key is stored in the full dump
// All PSA EDC16C34 seems to share the same public key
BigInteger n = new BigInteger(
"9f63259b570099e4435112058526405d"+
"edd701b8b51d42d80b46c71839171620"+
"fe91c5d46aaf2ccf8921b6eb56c62f46"+
"4f2930d1b0970bb77c686a30123400ef"+
"b406bff133151cc4100b4d715c038f0f"+
"50aa247e5b710e0a8893de467077d169"+
"db2c496d7205c3c44a6b3b1e37bfa03b"+
"35d9a44f1879f76523ffde1a0e501151",
16
);


byte[] dump1 = null;
byte[] dump2 = null;

try {

dump1 = loadDump("C:\\Users\\pons\\Desktop\\Full DUMP\\1_Flash C4 ori.bin");
BigInteger a = getBI(dump1,0x1FDF7C ,128);
BigInteger sig = a.pow(3).mod(n);
byte[] sigArr = getBuffer(sig,128);
System.out.println( getHex(sigArr,false) );
System.out.println( getASCII(sigArr) );
if(!checkSig(sigArr)) exitError("Invalid RSA signature");

System.out.println( "MCS32 :" + String.format("%08X",getU32(dump1,0x1FDF78,false)) );
System.out.println( "calcMCS32:" + String.format("%08X", computeCS1(dump1,0)) );
System.out.println( "MD5 :" + getHex(extractMD5(sigArr)) );
System.out.println( "calcMD5 :" + getHex(computeMD5(dump1)) );
System.out.println( "SCS32 :" + String.format("%08X",getU32(dump1,0x1FDFFC,false)) );
System.out.println( "calcSCS32:" + String.format("%08X", computeCS2(dump1,0)) );

// Correct the mods
dump2 = loadDump("C:\\Users\\pons\\Desktop\\Full DUMP\\1_Flash dpf.bin");

// MAP CS
long newCS1 = computeCS1(dump2,0);
dump2[0x1FDF78] = (byte)( newCS1>>24 );
dump2[0x1FDF79] = (byte)( newCS1>>16 );
dump2[0x1FDF7A] = (byte)( newCS1>>8 );
dump2[0x1FDF7B] = (byte)( newCS1 );

// Compute new RSA signature
BigInteger newSig = new BigInteger("0001ffffffffffffffff00" +
getHex(computeMD5(dump2),false),16 );

int freeBit = (128-(11/*prefix length*/+16/*MD5 length*/))*8;
newSig = newSig.shiftLeft(freeBit);
sigArr = getBuffer(newSig,128);
System.out.println( getHex(sigArr,false) );

// Copy the new RSA signature into the dump
BigInteger root = RSARootAttack1024(newSig,n,3,freeBit);
byte[] rootArr = getBuffer(root,128);
System.arraycopy(rootArr,0,dump2,0x1FDF7C,128);

// RSA signature CS
long newCS2 = computeCS2(dump2,0);
dump2[0x1FDFFC] = (byte)( newCS2>>24 );
dump2[0x1FDFFD] = (byte)( newCS2>>16 );
dump2[0x1FDFFE] = (byte)( newCS2>>8 );
dump2[0x1FDFFF] = (byte)( newCS2 );

saveDump("C:\\Users\\pons\\Desktop\\Full DUMP\\1_Flash dpf_csok.bin",dump2);

} catch (IOException e) {
System.out.println("Fail:" + e.getMessage());
System.exit(0);
}

}

}

[JeanLuc38]

Hi there.

If you want to modify the code part, there is similar checksum where signature data are located at the end of the code zone (just before 0x1c0000)
(The good old galletto is able to dump this zone via OBD but warning it does nut dump the full code zone, so it can creates some wrong signature depenging on flash tools used)
The RSA key is not the same as for the MAP zone but can be found easliy (find a 1024 bit number not easy to factor).
Lauterbach Trace 32 is really a great tool if you want to patch this code and make you car better.

My 1.6 HDI (320.000km) consumes now less than 4 liter/100km (in summer) with its full power and a much better response. Strickly no problem since the reprog (~1 year ago).
I also added specific personnal fetaures....

[volodin69]

Great, but, BTW... if you can do this, why don't you work on a big trust to pay you better? With winols installed, (free on this forjm), you can make checksum fast and easy.

[JeanLuc38]

My goal is not to earn money and not only playing with checksums. My gaol is to have a perfect understabnding of my car.
For instance (among others), extend CAN-DIAG to have full engine informations available with a cheap OBD2 chip.
Change PID govenor of flap to optimize consuptim according to my driving condidition.
Having map selection on demand (as we have on certain mororbike).
etc....

I recall that i published an opem source (https://github.com/JeanLucPons/DTCController) fully free.
And i will go defintelyy further....

[JeanLuc38]

Hello,
I add to this post the algorithm to decode and calculate the pin code and checksum of the corresponding e2prom (95160).



# EDC16C34 95160 E2PROM PIN DECODER (PSA platform)

import sys

#XOR Masks
L1_MASK = bytes([0xFA,0xBE,0x86,0x75])
L2_MASK = bytes([0xCE,0xDF,0x23,0x41])
L3_MASK = bytes([0xDB,0xAC,0x92,0x73])

def printPIN(dump,address,mask):
unmask = bytes([_a ^ _b for _a, _b in zip(dump[address:address+4], mask[0:4])])
print(unmask[0:4].decode("ascii"))

def checksum(dump,address):
sum = 0
for i in range(address,address+6):
sum += dump[i]
calcSum = 0xFFFF - sum
print("Stored checksum: " + hex(dump[address+6]) + hex(dump[address+7])[2:])
print("Calculated checksum: " + hex(calcSum))

def decodePIN(fileName):
f = open(fileName, "rb")
dump = f.read()
# The pin code is duplicated 3 times at address 0x60,0x80,0xA0 and hidden by a constant XOR mask
printPIN(dump,0x60,L1_MASK)
printPIN(dump,0x80,L2_MASK)
printPIN(dump,0xA0,L3_MASK)
# There is 3 checksum for each line
checksum(dump,0x60)
checksum(dump,0x80)
checksum(dump,0xA0)

if __name__ == "__main__":
args = sys.argv[1:]
if len(args) != 1:
print("Usage pyPIN dump.bin")
exit(-1)
decodePIN(args[0])


Note: The above python code will faill for immooff dump (decoded PIN to 0x000000FF) with:


File "pyPIN.py", line 12, in printPIN
print(unmask[0:4].decode("ascii"))
UnicodeDecodeError: 'ascii' codec can't decode byte 0xff in position 3: ordinal not in range(128)