PDA

View Full Version : Seed Key and Algorithms


nobber
January 9th, 2007, 01:16
Hi

We have a number of projects which we have 2 byte and 4 byte seed key challenge responses, and as you can imagine they are sometimes an aboslute pig to decode and come up with an algorithm or calculation to emulate the seed key.

These are mainly used on diagnostic routines between diagnostic equipment and the vehicle.

Is there anyone or company that anyone knows that offers solutions to this type of problem ? or any suggestions how we can approach them ?

Thanks

Greg Chambers
Advanced Diagnostics

LLXX
January 9th, 2007, 01:34
Quote:
[Originally Posted by nobber;63639]to emulate the seed key.
You need not emulate, merely copy+paste of the code (with minor alterations, of course) is good enough.

nobber
January 9th, 2007, 01:54
When you say copy and paste the code ? what code ?

We are talking machines that run on PC's and getting the code that runs the seed key is like needle in a haystack.


Silkut
January 9th, 2007, 12:21
I think LLXX is talking about the algo code, afaik RCE is reverse engineering about code, I also wonder how would we be able to help you without some snippet ? =)

nobber
January 10th, 2007, 07:47
OK, here goes...

On a particular vehicle Ssangyong we have to talk to the Engine Control ECU on the car via a ISO protocol communication standard.

Within the protocol, there is a 4 byte Algorithm that you have to send a command to.

We have emulated the command and can have the machine sit here number crunching and have obtained about 200,000 codes.

However, to get a reasonable percentage would take about 10 years.

So, we need a person or company to take the codes we have and work out the algorithm.

We can emulate the algorithm, but the ECU needs a response in 3 seconds, and that is just not possible to get the code emulate it with the car diagnostic kit and send a response back.

Basiclly it is working out a calculation for the algorithm, from the codes we have...

Here is a few examples for seed and key...

00000001,00000000000000000000000000000001;
65C29B86,01100101110000101001101110000110;

00000002,00000000000000000000000000000010;
F5DB24B1,11110101110110110010010010110001;

00000003,00000000000000000000000000000011;
B5F4679F,10110101111101000110011110011111;

00000004,00000000000000000000000000000100;
97E752A2,10010111111001110101001010100010;

00000005,00000000000000000000000000000101;
20D59C62,00100000110101011001110001100010;

00000006,00000000000000000000000000000110;
5BB04370,01011011101100000100001101110000;

We are willing to pay for help by the way if we can find
someone good enough.

Regards

naides
January 10th, 2007, 22:09
Nobber, I think you are talking too fast.

Explain the problem again, for somebody (nobody) that is not working in your company and does not have hands on experience with the problem, using terms that are not so much hardware engineering specific, or rather lay terms, and may be someone here can give you suggestions.

For instance: my interpretation:

You have a specific vehicle Ssangyong and you want to reverse engineer the communication protocol that is used to interrogate it. Right??

Is that software protocol available? For sure someone (The manufacturer), somewhere does communicate successfully with the ECU. Can you get your hands on the software?

reversing the Software is much simpler than reversing the communication protocol as a "Black Box Problem" .

OK. I assume you do not have that software, key algorithm or means to get it.

"Within the protocol, there is a 4 byte Algorithm that you have to send a command to."

I do not understand that sentence. Please elaborate.
What is 4 bytes? the message you send to the car's ECU? Then the ECU sends back a 32 bit answer back?

"We have emulated the command and can have the machine sit here number crunching and have obtained about 200,000 codes."

How have you emulated the command? What is a command: a 4 byte key??

From what I gathered you have coded a program that sends a 4 byte challenge and reads the 32 bit response, and you are trying to brute force it, collecting pairs of challenge-responses. . . right ?

What I still do not understand is once you have the "conversion formula" the "translation pattern", meaning learning how

00000001;

elicits

65C29B86;

Somehow allows you to perform some communication with the ECU unit.

More likely , I completely missed the point of your problem/question.

disavowed
January 11th, 2007, 02:01
please don't tell me this is going to be used for stealing cars...

JMI
January 11th, 2007, 03:47
If so, he's not doing a very good job of concealing his identity.

http://www.advanced-diagnostics.co.uk/htm/Main.php

Apparently his request may have something to do with:

Transponder Key Programming equipment.

But that's just a guess.

Regards,

nobber
January 11th, 2007, 04:27
Ok, OK...

It is not for stealing cars. It is for programming keys when you lose your keys or want to add another one.

We do have equipment that does this, this equipment is what dealers use.

What we do is provide the same type of equipment to Locksmiths who can then do the same thing around the world.

What the manufacturers do is insert security algorithms to stop people offering equipment outside of the dealer network.

Thats what we do, but to steal a car as you say, you need to 1. Cut a key the same as the car you are going to steal, 2. Get the security Pin code to program that key, 3. Have equipment to program that key.

We do option 3, thats it.

Back to the problem....

4 bytes, which means it is made up of 1 byte = 1111 1111 in binary or FF in Hex.

So 4 bytes = FF FF FF FF

So they give us a SEED = FF F1 12 1B for example and then we have to give a 4 byte response = XX XX XX XX (This is the bit we need)

The codes in the earlier post are examples of what the dealer machine receives and sends.

We are looking for people who are able to work out these calulations, and my post here was speculative, and see whether anyone has that capability.

Probably not it seems, as understanding Bytes, Hex, Binary, bit shifting etc etc is a necesseity.

But thanks for listening.

Regards

LLXX
January 11th, 2007, 04:31
Quote:
[Originally Posted by nobber;63673]We have emulated the command and can have the machine sit here number crunching and have obtained about 200,000 codes.

However, to get a reasonable percentage would take about 10 years.
What sort of machine are you running this on? A 32-bit keyspace (4294967296 in total) is considered absolutely trivial to search today, in the age of relatively inexpensive CPUs that can perform several billion operations per second. Storing all those challenges and responses would take all of 32GB, which is again a trivial matter today.

Or, is your keysearch algorithm simply inefficient and doing less work per clock than it could?

Edit: Upon staring at those example challenges and responses you posted, I have noticed somehow they seem like they were generated by an LFSR (linear feedback shift register). I can't really describe it, but I've worked with LFSRs in the past and the output bitstreams had a specific "texture" to them which I seem to be detecting here.

nobber
January 11th, 2007, 04:39
Yes, that is correct.

The problem is getting all of them.

It takes 1 second to get a code, so multiply the number and see how many days and years that will take, its a long time.


friedo
January 11th, 2007, 05:06
Whats about reverse engineering of the ECU?!

Thatīs what people normally do and thatīs the reason why some professional equipment is real expensive because it takes hours to reverse such embedded things!

Business is not only to receive "free codes" and sell them but sometimes it need some brain and more development....

nobber
January 11th, 2007, 06:25
Hi

Yes correct.

We are experts in vehicle diagnostics.

Thats why we have hit a wall.

We are not looking for a free ride.

We are looking for a company/person who may be able to reverse the ECU or whatever will be required.

I just do not know anyone who can offer this service as a contract, hence the post.

Not looking for a free codes, just some direction of where we may get a contractor or someone who is capable of doing this type of work.

Its not your everyday project.

Thanks

Greg

naides
January 11th, 2007, 06:43
Quote:
[Originally Posted by nobber;63691]

Probably not it seems, as understanding Bytes, Hex, Binary, bit shifting etc etc is a necesseity.

But thanks for listening.

Regards


Offense taken here, young man.

I was giving a sincere effort to understand the problem, trying to make heads and tails of your rather abstruse request.

And no, it was not because I was interested in doing a side job for money.

For your information I, and very many members of this board know a fucking lot about Bytes, Hex, binary, shift, ROL, ROR, cryptography than you would ever dream.

The crux of the problem is your poor communication skills, NOT our ignorance, as you suggested.

nobber
January 11th, 2007, 06:53
I did not mean to offend. So sorry.

You asked the question what was 4 bytes ?

I assumed you did not know what a byte was.

So, if you did not know what a byte was, how was I supposed to explain myself to you.

That was my point. Sorry.

You do seem to understand the problem we have, 2 to the power of 32 is a hell of a lot of codes, and for us to get those will take an eon.

So reverse engineering the machine code in the processor is probably the only way of doing this.

But, we have no idea how to do that, or where to start, so I am looking for a pointer, a person who understand that type of engineering, a company who may help.

Not trying to be clever or mislead you, just looking for something more than we have now.

Thanks

Greg

LLXX
January 12th, 2007, 04:46
This Forum deals with matters of reverse-engineering.

You may find the Advanced Programming/Reversing subforum appropriate.

korvak
January 12th, 2007, 20:39
in the end it all may be a "wash", which would be easier... figuring out what the alogo is or figuring out how to extract the code from the ECU... i would have to assume the ECU is some form of "protected" MPU/CPU. some are ease to glitch/hack... and some are near impossible, requiring decaping the chip and using microprobes to watch the line and "steal" the programming...

but from what it sounds like with LLXX already "seeing" a texture to the alogo, you might want to invest more time in the alogo approach... also if you can give some details on the hardware/brains used, that could help...

for what its worth...

Korvak

korvak
January 18th, 2007, 10:38
Nobber,

i have been doing a little thinking on my commute to and from work... and there is something i must have missed... you are obtaining these code key pairs from somewhere.... am i to assume you are "watching" the interaction from a dealers system talking to the ECU or is it something you have created that is running the routine to generate these key pair responses? and if this is a "dealers" system... why have you not attempted to hack it?

this one second delay it takes to get a key pair... where is the delay coming from? your equipment, the dealers equipment, or the ECU?

again i have to assume it is not your own routine that is getting the key pair or you would already know the alogo...

i just want to make sure i understand the entire process... i have also looked more closely at the posts you have given with the example key pairs and there is a pattern there (assuming the are real)... but where did they come from in sequencial order, or did you get lucky and just so happen obtain these from snooping the lines between a dealer system and the ECU... if these are not luck from watching the lines... how did you force the sequencial order? the way i understand your communication between the systems is that the ECU provides the "challange" and your device has to give the correct "response" for communications to go any futher...

what am i missing? i know, a clue...

i would just hate for this to drop, because "we" dont fully understand the project that you have been working on for a long time and fully understand...

korvak

mylo
January 18th, 2007, 18:15
Nobber,

I think if you read back your very first message carefully from the point of view of an outsider you'll find it a little hard to understand what you're aiming at too.

With that said, I agree with korvak in that some more information about the dealer's system and where and how exactly you're snooping these values would be useful.

If LLXX's educated guess is correct and an LSFR is being used to generate the values, you may be able to use something like that Berlekamp-Massey Algorithm to find the original values that are being used to generate the sequence. It's something I've had some luck with in the past. Perhaps you could provide us some more key pairs in sequence to work with?

oakville
August 12th, 2012, 11:31
Does any friend has an idea for this?

oakville
August 12th, 2012, 11:41
Quote:
[Originally Posted by oakville;93067]Does any friend has an idea for this?

I can provide over 65535 samples if any friend needs to find the algorithm

CrackZ
August 21st, 2012, 13:09
This is a classic black box problem and actually sounds quite interesting.

Sometimes these hidden algorithms are simple LSFR's as was suggested earlier, other times complex Feistel ciphers.

I'd suggest a basic paper analysis of certain patterns of bits (0x0, 0xF, 0xFF, 0xFFF, 0xFFFF etc). Some of the early dongle black boxes were broken by simple pattern forming or playing with shifts/xors/rotates and so on.

Hope the original poster found an answer. Theres always paying a company to completely take apart the silicon (starts at about $20,000 from recollection).

Regards,

CrackZ.

NickyBlue
October 11th, 2012, 11:14
This thread seems to have lot of heat! ...
Well not sure what's goin on here, When you guys don't have the clue then how can a common man like me understand whats it all about but I like the way convo goin on here. cool man!
I like it. Its enjoyable! love you guys!

cya, have fun

squidge
October 14th, 2012, 16:08
We didn't have a clue because we had no idea what he was talking about.

Now if he said "I'm trying to work out this challenge/response algo - when the challenge is X, the response is Y, and heres a few dozen samples", its quite easy to know what they expect, but when they say things like "there is a 4 byte Algorithm that you have to send a command to", it makes me go "WTF?".

I got what he was meaning later on (and so did others), but he appeared to have left well before then, thinking no one knew what a byte was...

Just a case of he didn't know how to talk to a group of geeks

elvis030313
November 21st, 2012, 09:10
Hi.

Maybe we can provide the service (seed&key algorithm) please give us the e-amil If you need.
elvis030313@hotmail.com.