Any known protocol for establishing trust between an inherently untrustworthy source and a server without a 3rd party?

Question

Is there any kind of protocol, scheme, or theoretical paper out there that implements or examines the problem of establishing trust between two parties (communicating, listening) where the communicating party initiates contact and does not have a key/secret/password known by the listening listening party; but the listener needs to somehow verify that the communicating party is trustworthy in order to return some sensitive information without interrogating a 3rd party. Personally, this sounds near impossible, but I have tasked with investigating the feasibility. The problem we are trying to solve is provisioning devices into an environment where the devices need zero initial configuration other than being pointed at the proper remote endpoint.

Consider a situation where we have a Device (D) and a Server (S):

1. D sends initial Message M[0] to S containing D's alleged identity (name)
2. S verifies D identity using (???) and returns Key K to D
3. D uses K for all subsequent messages M[1..N-1].

The majority of this problem is in <2> where (???) occurs. Device may be as small as an 8-bit micro with limited storage options.

Answer 1

As usual, the problem is one of definition. Namely, what makes the device 'D' more "genuine" than a PC run by some ill-intentioned individual ? If you get down to it, you will say something like: device D is genuine because that's the true piece of tangible hardware, the accumulation of atoms which came out from the factory. This is fine as far as definition goes, but it does not map well to network configurations. From the point of view of the server S, there are only IP packets; zeros and ones; the server has no access whatsoever to the manifestation of the device in the physical world, but only to what it sends.

In the abstract world of networks, you are what you know. What allows a server S to recognize a remote device D as a "true device D" is that D can do things (i.e. compute things) that require some knowledge than only D possesses.

This means that you have mostly two ways out of your conundrum:

1. At some point in the building process where the device D is still on secure premises (e.g. in the factory), inject some secret key into the device. At that point, you can procedurally (with eye witnesses) make sure that only a true, genuine device will obtain such a secret key. The key can then be used later on by D to demonstrate that it is a real device.

2. Do the initial pairing between D and S under the physical control of a trusted (sworn) agent, who makes sure that the true device is used. In practice, the said agent would plug the device in his laptop computer, use some authentication mechanism to talk to S (as an authorized agent), and forward data in both directions.

I have seen (actually done) both kinds where devices were payment terminals, with a lot of money at stake, justifying the overhead of sworn agents. If your device is of the cheaper kind, then this overhead may unbearable to you. On the other hand, if you inject "sensitive information" in a cheap device, then maybe you are running to your doom: if the information is worthwhile, then some device owners will try to open it and extract the information. They do that for mere music and video files !