I was always wondering how people reversed algorithms from matching seed/keys and my curiosity got the better of me.

I managed to deduce the Level 1 security access key (the one used for writing a flash on the ECU for example)

Using most of the information found on this site, I gave it a shot. I made an Arduino ECU simulator that replied to the basic KWP requests from a tool.
I based most of this work on information that I did find on this forum. Work done on the MED9.1 by Basano.

Most tools start by asking some basic KWP things like Hardware and software numbers and so on. I used the Arduino to feed a few messages to keep the tool happy, up until the moment the tool wants to open a development session, followed by the seed request.
It then receives a seed, calculates, using the algorithm, what the reply should be, then compares it to the reply given by the tool. If this matches, access to that security level is given. There are multiple security access levels for info.

But lets stick to the reversing strategy that I tried. Given the fact that I was using an ECU simulator, I could feed the tool any seedkey I wished. so I started off with a simple seed to try and understand its working.

I got the following matching seed/keys back

seed 01 01 01 01
key 20 20 20 20

seed 02 02 02 02
key 40 40 40 40

seed 03 03 03 03
key 60 60 60 60

so there is definitely a pattern here. lets try and work this out a bit more. to start we turn the Hex into simple bits.

seed 01010101:   00000001   00000001   00000001   00000001
reply 20202020:   00100000   00100000   00100000   00100000

From this we can see what is happening. The bits are carried 5 spaces to the left.

seed 02 02 02 02  00000010  00000010  00000010  00000010
key 40 40 40 40   01000000  01000000  01000000  01000000

Same thing is happening here and on the other ones aswel. So lets try one where the bit will carry over when it moves left 5 times.

seed   08 00 00 00   00001000  00000000  00000000  00000000       shift it 5 spaces to the left and we get
shifted :                  00000000  00000000  00000000  00000001
reply   0A221288     00001010  00100010  00010010  10001000

Quite a bit different than what we expected. So we are dealing with some modifier. Out of reading here, I found out it was possibly a XOR so here we go :

from the above, we can conclude that the hex used for the XOR could be :   00001010 00100010 00010010 10001001 , which gives us 0A 22 12 89 in hex. A lookup in my BIN brings this up aswel. But more testing is needed.

FF   FF   20   5B   D9   C6   03   00   70   00   F0   00   00   01   01   00
02   00   80   00   40   07   E8   03   05   00   0F   00   02   05   40   02
02   01   00   01   01   10   00   04   24   10   68   05   81   4A   05   87
0A   22   12   89   49   4C   FF   0F   F0   00   B0   40   BF   4F   E9   19
E6   16   A6   56   A9   59   75   85   7A   8A   3A   CA   35   C5   63   93
6C   9C   2C   DC   23   D3   D2   22   DD   2D   9D   6D   92   62   C4   34
CB   3B   8B   7B   84   74   58   A8   57   A7   17   E7   18   E8   4E   BE

After a bit more trial and error, I found out that this was indeed correct, but that the carry over (rotating) bits are used to offset this hex value

Example, if after shifting it to the left 5 times. the result ends in
xxxxxxxx xxxxxxxx xxxxxxxx xxx00001 then the hex for the XOR is 00001010 00100010 00010010 10001001
xxxxxxxx xxxxxxxx xxxxxxxx xxx00010 the hex for the XOR moves 1 to the left and becomes 00010100 01000100 00100101 00010010
xxxxxxxx xxxxxxxx xxxxxxxx xxx00100 the hex for the XOR moves 2 to the left and becomes 00101000 10001000 01001010 00100100
xxxxxxxx xxxxxxxx xxxxxxxx xxx01000 the hex for the XOR moves 3 to the left and becomes 01010001 00010000 10010100 01001000
xxxxxxxx xxxxxxxx xxxxxxxx xxx10000 the hex for the XOR moves 4 to the left and becomes 10100010 00100001 00101000 10010000

Now that we have this information we can calculate the correct response for each Seed ...

Example :

Seed 41 20 90 C8  in bits is
0100 0001 0010 0000 1001 0000 1100 1000
we rotate it
0010 0100 0001 0010 0001 1001 0000 1000
because it ends in 01000 the Hex will be
0101 0001 0001 0000 1001 0100 0100 1000

then we XOR it and we get the correct response which will be
0010 0100 0001 0010 0001 1001 0000 1000
0101 0001 0001 0000 1001 0100 0100 1000
0111 0101 0000 0010 1000 1101 0100 0000
in hex that gives us 75 02 8D 40 , which gave a correct response on my Bench ECU.

Hope this helps someone at some point.

Another approach would be to reverse engineer one of the tools, or even disasm the MEDC firmware, and find the appropriate piece of code which generates the key from a given seed.

Don't forget that VAG features a specific interpreter language which is used to generate the seed/key answers.
This is documented in a pdf and posted in this forum as well. I think this is only for UDS based modules though, not KWP.

All that works fine, but when I started playing with random keys I found there is more than one XOR
For example:
    SEED       -    XOR        -       KEY
--------------------------------------------
19 8C C6 63 - 1E66379B   - 2F FE FB F8
DD 6E 37 9B - ED578B43  - 40 91 78 38
E2 71 B8 5C - 36EE7DBF   - 95 8E FD 60

I didn't find a pattern on what XOR gets used on what SEED yet. Any suggestions?

Yes, I wish that was clear to ME earlier on