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:

1ffffffffffffffff00c371e42fdb4d3808b3f0559437cb20f6000000003931330000000000000000000000000031343a31303a34312030332d30382d3037e42d139c6adc1f855d87000ed8052481c7b494d198fe81a92a2406ab30c3a3ae953d4a3d2a5f621e207cb62f9d5fad5ef735b7fccce4594796f1b458ee560c5a

An original signature looks like this:

0001ffffffffffffffff00feda839f0a536be7114da06cde4ac7f6000000003931310000000000000000000000000031343a31393a34322031362d31312d3036dc6c083a64afccdfa711c8984d1e5aabdda747ad6f6ad1d5cc3d5fc24044f97cb62bb5f35a0249d246b0ced88a9112971f3c4dccec07ce2d994550d938cf9055 
. . . . . . . . . . . . . . . . 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:

9f63259b570099e4435112058526405dedd701b8b51d42d80b46c71839171620fe91c5d46aaf2ccf8921b6eb56c62f464f2930d1b0970bb77c686a30123400efb406bff133151cc4100b4d715c038f0f50aa247e5b4ea0e63e695862d738823786e4ba78e88203b34fddbc7836aca5162cf87358cb74c65740c5ec0c461b1390
0001ffffffffffffffff00885ac5e6fee40cd7f7bbdaaeeb3c57d14250472d3831303100000000000021c2b276bf784d885dcd17b73bd7e29302512be2e4f2e7831d8fff35951d06feffda1f4748eb89bad75e5be9a504ab124766b97528da4394e66475129f716c1c2ed391626cfa47175d5aad3c343cb9e1bef12f9c85e810
. . . . . . . . . . . . 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:

0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001428a2f98d728ae220835a672cdd5ee33c799c5a3418d6b167cc857b3692d5bcdcf4d06ca12be3568e4ce
0001ffffffffffffffff00885ac5e6fee40cd7f7bbdaaeeb3c57d1000000000000000000000000000000c0ffb7c19af461d9ffdb87764502cc89dfadd61a37c3c1ae8350aacccad9a9d54039d3a0b3756075ad784033a09aa7cdab281803bc6ba3f986b64f6cbad447204cdce6d2dda0bd1ea9ccf76787a04a779d3172ed13b8
. . . . . . . . . . . . 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.



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

[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)