MEMS3 Seed To Key
Algorithm
The notes below show how the Pascal function which implements the Security Access seed to key algorithm in MEMS3 Mapper may be derived from the raw ECU assembly language implementation. I have shown the final Pascal implementation, a Pascal pseudocode version and the raw ECU assembly language from both firmware ksr3p004 and boot loader bootp033. The pseudocode implementation is a “half way house”, where the assembly language has been distilled down into higher level code structures but is still laid out in the order of the assembly language code with corresponding addresses.
Seed To Key Algorithm – Final Pascal Implementation
This is the final Delphi Pascal implementation of the SeedToKey method. This Pascal code is distilled from the ECU pseudocode implementation below.
class
function TStandardMems3.SeedToKey(ASeed: Word): Word;
var
I: Integer;
begin
Result:=0;
I:=1;
if Odd(ASeed shr 15) then
Inc(I, 8);
if Odd(ASeed shr 7) then
Inc(I, 4);
if Odd(ASeed shr 4) then
Inc(I, 2);
if Odd(ASeed) then
Inc(I);
for I:=1 To I do
begin
Result:=(((ASeed shr 1) and $FFFE)
or Ord(not(Odd(ASeed shr 13) and Odd(ASeed shr 3))))
and $7FFF;
if Odd(ASeed shr 9) xor Odd(ASeed shr 8) xor Odd(ASeed shr
2) xor Odd(ASeed shr 1) then
Result:=Result or $8000;
ASeed:=Result;
end;
end;
Seed To Key Algorithm – Arduino C++ Implementation
This is the final Arduino C++ implementation of the SeedToKey method. This Arduino code is translated from the Delphi Pascal implementation above.
uint16_t seedToKey(uint16_t
seed) {
uint16_t
result = 0;
uint16_t
count = 1;
if
(getBit(seed,
15)) {
count += 8;
}
if
(getBit(seed,
7)) {
count += 4;
}
if
(getBit(seed,
4)) {
count += 2;
}
if
(getBit(seed,
0)) {
count ++;
}
for
(uint16_t
i = 0; i < count; i++)
{
result = (((seed
>> 1) & 0xFFFE)
| (getBit(seed,
13) && getBit(seed,
3) ? 0
: 1)) & 0x7FFF;
if
(getBit(seed,
9) ^ getBit(seed,
8) ^ getBit(seed,
2) ^ getBit(seed,
1)) {
result |= 0x8000;
}
seed = result;
}
return
result;
}
Seed To Key Algorithm – Pascal Pseudocode Implementation – Firmware
ksr3p004
This is a pseudocode translation of the seed to key algorithm in the ECU, which is distilled from the raw assembly language implementation below. Addresses shown are for firmware version ksr3p004. In the ECU, the seed key algorithm is called as part of a process that generates a new seed then calculates the key that goes with it. The seed and key are therefore both calculated at the same time as a pair and both stored. The seed is used to generate the new seed on the next call, the key is used to compare with the value returned over OBDII. This routine is entered with the newly generated seed in register D5. It therefore starts by storing the new seed from D5 in Word variable SEED_00000bf0, which it then later references to set D6. D6 holds the key which corresponds to the seed on completion.
0012220A SEED_00000bf0:=D5;
... //
Omitted some checking and updating of flags which is not directly relevant
here.
00122234 D1:=0;
00122236 if Odd(D5 shr 15) then
0012223e Inc(D1, 8);
00122242 if Odd(D5 shr 7) then
0012224a Inc(D1, 4);
0012224e if Odd(D shr 4) then
00122256 Inc(D1, 2);
0012225a if Odd(D5) then
00122262 Inc(D1);
00122266 Inc(D1);
0012226a D6:=SEED_00000bf0;
0012226e for D2:=1
00122272 to D1 do
begin
00122280 D3:=0;
00122282 if Odd(D6 shr 1) then
0012228a Inc(D3);
0012228e if Odd(D6 shr 2) then
00122296 Inc(D3);
0012229a if Odd(D6 shr 8) then
001222a2 Inc(D3);
001222a6 if Odd(D6 shr 9) then
001222ae Inc(D3);
001222b2 D4:=1;
001222b6 if Odd(D6 shr 3)
001222be and Odd(D6 shr 13)
then
001222c6 D4:=0; //
Equivalent to D4:=not(Odd(D6 shr 13) and Odd(D6 shr 3)).
001222c8 D6:=D6 shr 1;
001222ca if (D3=1) // D3 will be 1 or 3 if an odd number of the conditions
highlighted are met. This is therefore equivalent to XORing the conditions.
001222d0 or (D3=3) then
001222d6 D6:=D6 or $8000;
001222da if D4<>0 then
001222e0 D6:=D6 or $1
001222e4 else
001222e6 D6:=D6 and $7FFF;
001222ea end;
Seed To Key Algorithm – Raw ECU
Assembly Implementation – Firmware ksr3p004
This is the raw listing of the seed to key algorithm as actually implemented in the ECU, in the firmware. Again, addresses shown are for firmware version ksr3p004.
LAB_0012220a
XREF[1]: 00122204 (j)
0012220a 31 c5
0b f0 move.w
D5w ,(BYTE_00000bf0 ).w
0012220e 31 fc 00
move.w #0xfb ,(BYTE_00000514
).w
fb 05 14
00122214 31 f8 0b
move.w (BYTE_00000bf0 ).w,(BYTE_00000516
).w
f0 05 16
0012221a 08 f8 00
bset.b 0x7 ,(byteBitFlags08F9
).w
07 08 f9
00122220 08 38 00
btst.b 0x5 ,(byteBitFlags131A
).w
05 13 1a
00122226 66 0c bne.b LAB_00122234
00122228 08 38 00
btst.b 0x0 ,(BYTE_00001313 ).w
00 13 13
0012222e 67 ff
00 beq.l: LAB_001222f6
00
00 c6
LAB_00122234
XREF[1]: 00122226 (j)
00122234 42 41
clr.w D1w
00122236 08 05
00 0f btst.l
0xf ,D5
0012223a 67 00
00 06 beq.w
LAB_00122242
0012223e 06 41
00 08 addi.w
#0x8 ,D1w
LAB_00122242
XREF[1]: 0012223a (j)
00122242 08
05 00 07
btst.l 0x7 ,D5
00122246 67 00 00
06 beq.w LAB_0012224e
0012224a 06 41 00
04 addi.w #0x4 ,D1w
LAB_0012224e
XREF[1]: 00122246 (j)
0012224e 08 05 00
04 btst.l 0x4 ,D5
00122252 67
00 00 06
beq.w LAB_0012225a
00122256 06 41
00 02 addi.w
#0x2 ,D1w
LAB_0012225a
XREF[1]: 00122252 (j)
0012225a 08 05
00 00 btst.l
0x0 ,D5
0012225e 67 00
00 06 beq.w
LAB_00122266
00122262 06 41
00 01 addi.w
#0x1 ,D1w
LAB_00122266
XREF[1]: 0012225e (j)
00122266 06 41
00 01 addi.w
#0x1 ,D1w
0012226a 3c 38
0b f0 move.w
(BYTE_00000bf0 ).w,D6w
0012226e 34
3c 00 01
move.w #0x1 ,D2w
00122272 60 04 bra.b LAB_00122278
LAB_00122274
XREF[1]: 001222ea (j)
00122274 06 42
00 01 addi.w
#0x1 ,D2w
LAB_00122278
XREF[1]: 00122272 (j)
00122278 b4 41
cmp.w D1w ,D2w
0012227a 6e
ff 00 bgt.l: LAB_001222ec
00
00 70
00122280 42
43 clr.w D3w
00122282 08 06 00
01 btst.l 0x1 ,D6
00122286 67
00 00 06
beq.w LAB_0012228e
0012228a 06 43
00 01 addi.w
#0x1 ,D3w
LAB_0012228e
XREF[1]: 00122286 (j)
0012228e 08 06
00 02 btst.l
0x2 ,D6
00122292 67 00
00 06 beq.w
LAB_0012229a
00122296 06 43 00
01 addi.w #0x1 ,D3w
LAB_0012229a XREF[1]: 00122292 (j)
0012229a 08 06 00
08 btst.l 0x8 ,D6
0012229e 67 00 00
06 beq.w LAB_001222a6
001222a2 06 43 00
01 addi.w #0x1 ,D3w
LAB_001222a6
XREF[1]: 0012229e (j)
001222a6 08 06 00
09 btst.l 0x9 ,D6
001222aa 67 00 00
06 beq.w LAB_001222b2
001222ae 06 43 00
01 addi.w #0x1 ,D3w
LAB_001222b2
XREF[1]: 001222aa (j)
001222b2 38 3c 00
01 move.w #0x1 ,D4w
001222b6 08 06 00
03 btst.l 0x3 ,D6
001222ba 67 00 00
0c beq.w LAB_001222c8
001222be 08 06 00
0d btst.l 0xd ,D6
001222c2 67 00 00
04 beq.w LAB_001222c8
001222c6 42 44 clr.w D4w
LAB_001222c8
XREF[2]: 001222ba (j) ,
001222c2 (j)
001222c8 e2
4e lsr.w #0x1 ,D6w
001222ca 0c 43 00
01 cmpi.w #0x1 ,D3w
001222ce 67
06 beq.b LAB_001222d6
001222d0 0c 43
00 03 cmpi.w
#0x3 ,D3w
001222d4 66
04 bne.b LAB_001222da
LAB_001222d6
XREF[1]: 001222ce (j)
001222d6 08
c6 00 0f
bset.l 0xf ,D6
LAB_001222da
XREF[1]: 001222d4 (j)
001222da 0c 44 00
00 cmpi.w #0x0 ,D4w
001222de 67 06 beq.b LAB_001222e6
001222e0 08 c6 00
00 bset.l 0x0 ,D6
001222e4 60 04 bra.b LAB_001222ea
LAB_001222e6
XREF[1]: 001222de (j)
001222e6 08 86
00 00 bclr.l
0x0 ,D6
LAB_001222ea
XREF[1]: 001222e4 (j)
001222ea 60
88 bra.b LAB_00122274
Seed To Key Algorithm – Raw ECU
Assembly Implementation – Boot Loader bootp033
This is the raw listing of the seed to key algorithm as actually implemented in the ECU, in the boot loader. Addresses shown are for boot loader version bootp033. It is functionally identical to the routine in the firmware. It is repeated because both the firmware (General Diagnostic Session) and boot loader (Programming Diagnostic Session) support KWP2000 Service $27 “Security Access” and run independently.
LAB_00106258
XREF[1]: 00106252 (j)
00106258 31 c5 04
36 move.w D5w ,(BYTE_00000436 ).w
0010625c 31 fc 00
move.w #0xfb ,(BYTE_00000294
).w
fb 02 94
00106262 31 f8 04
move.w (BYTE_00000436 ).w,(BYTE_00000296
).w
36 02 96
00106268 08 f8 00
bset.b 0x7 ,(BYTE_00000413 ).w
07 04 13
0010626e 08 38 00
btst.b 0x3 ,(BYTE_00000583 ).w
03 05 83
00106274 66 0c bne.b LAB_00106282
00106276 08 38 00
btst.b 0x6 ,(BYTE_0000057e ).w
06 05 7e
0010627c 67 ff
00 beq.l: LAB_00106344
00
00 c6
LAB_00106282
XREF[1]: 00106274 (j)
00106282 42 41
clr.w D1w
00106284 08 05
00 0f btst.l
0xf ,D5
00106288 67 00
00 06 beq.w
LAB_00106290
0010628c 06 41
00 08 addi.w
#0x8 ,D1w
LAB_00106290
XREF[1]: 00106288 (j)
00106290 08 05
00 07 btst.l
0x7 ,D5
00106294 67 00
00 06 beq.w
LAB_0010629c
00106298 06 41
00 04 addi.w
#0x4 ,D1w
LAB_0010629c
XREF[1]: 00106294 (j)
0010629c 08 05
00 04 btst.l
0x4 ,D5
001062a0 67 00
00 06 beq.w
LAB_001062a8
001062a4 06 41
00 02 addi.w
#0x2 ,D1w
LAB_001062a8
XREF[1]: 001062a0 (j)
001062a8 08 05
00 00 btst.l
0x0 ,D5
001062ac 67 00
00 06 beq.w
LAB_001062b4
001062b0 06 41
00 01 addi.w
#0x1 ,D1w
LAB_001062b4
XREF[1]: 001062ac (j)
001062b4 06 41
00 01 addi.w
#0x1 ,D1w
001062b8 3c 38
04 36 move.w
(BYTE_00000436 ).w,D6w
001062bc 34 3c
00 01 move.w
#0x1 ,D2w
001062c0 60 04
bra.b LAB_001062c6
LAB_001062c2
XREF[1]: 00106338 (j)
001062c2 06 42
00 01 addi.w
#0x1 ,D2w
LAB_001062c6
XREF[1]: 001062c0 (j)
001062c6 b4 41
cmp.w D1w ,D2w
001062c8 6e ff
00 bgt.l: LAB_0010633a
00
00 70
001062ce 42 43
clr.w D3w
001062d0 08 06
00 01 btst.l
0x1 ,D6
001062d4 67 00 00
06 beq.w LAB_001062dc
001062d8 06 43 00
01 addi.w #0x1 ,D3w
LAB_001062dc
XREF[1]: 001062d4 (j)
001062dc 08
06 00 02
btst.l 0x2 ,D6
001062e0 67 00
00 06 beq.w
LAB_001062e8
001062e4 06 43
00 01 addi.w
#0x1 ,D3w
LAB_001062e8
XREF[1]: 001062e0 (j)
001062e8 08 06
00 08 btst.l
0x8 ,D6
001062ec 67 00
00 06 beq.w
LAB_001062f4
001062f0 06 43
00 01 addi.w
#0x1 ,D3w
LAB_001062f4
XREF[1]: 001062ec (j)
001062f4 08 06 00
09 btst.l 0x9 ,D6
001062f8 67 00 00
06 beq.w LAB_00106300
001062fc 06 43 00
01 addi.w #0x1 ,D3w
LAB_00106300
XREF[1]: 001062f8 (j)
00106300 38 3c 00
01 move.w #0x1 ,D4w
00106304 08 06 00
03 btst.l 0x3 ,D6
00106308 67 00 00
0c beq.w LAB_00106316
0010630c 08 06 00
0d btst.l 0xd ,D6
00106310 67 00 00
04 beq.w LAB_00106316
00106314 42 44 clr.w D4w
LAB_00106316 XREF[2]: 00106308 (j) , 00106310 (j)
00106316 e2 4e lsr.w #0x1 ,D6w
00106318 0c 43 00
01 cmpi.w #0x1 ,D3w
0010631c 67 06 beq.b LAB_00106324
0010631e 0c 43 00
03 cmpi.w #0x3 ,D3w
00106322 66 04 bne.b LAB_00106328
LAB_00106324
XREF[1]: 0010631c (j)
00106324 08 c6 00
0f bset.l 0xf ,D6
LAB_00106328
XREF[1]: 00106322 (j)
00106328 0c 44 00
00 cmpi.w #0x0 ,D4w
0010632c 67 06 beq.b LAB_00106334
0010632e 08 c6 00
00 bset.l 0x0 ,D6
00106332 60
04 bra.b LAB_00106338
LAB_00106334
XREF[1]: 0010632c (j)
00106334 08 86
00 00 bclr.l
0x0 ,D6
LAB_00106338
XREF[1]: 00106332 (j)
00106338 60 88
bra.b LAB_001062c2