Schneier on Security

Clive Robinson • July 6, 2011 2:13 AM

Here is a thought for people to dwell on.

In most of history our security or defence has relied on individuals.

As (currently) it’s not possible to see inside our heads sufficiently well to tell if a person is trustworthy or not it means in reality that they cannot be trusted.

So when it comes to humans we have put systems in place to deal as best we can with the problem but still get work done.

Now the question arises why should silicone be treated any differently?

That is do we actualy need chips that are provably correct or can we build systems where they don’t need to be “trustworthy” in 100% of cases 100% of the time?

After a little thought you will realise that we don’t, all you need is some way of determining when they are not working the way they are expected to, and the question changes to “what do we do when an error is detected?”

In an IEEE article linked to by @ Sam (10:43AM) one of the people asked made a comment about using a 512bit keyword as a “kill switch”.

Essentialy the base of their argument was that an adversary could place a circuit inside a chip that when a particular number was presented to it the chip would stop working either entirely or the way it was expected to. Their argument then went on that there was not enough time to go through all 512bit combinations to test that such a “kill switch” circuit did not exist within a chip.

Whilst the argument is correct in of it’s self, it is based on a set of assumptions that are not necessarily correct for any given end system.

That is it assumes a few things for the argument to hold three of which are,

1, The adversary can get the 512bit number into the chip when it’s in a system.
2, That a “single point of failure” will stop a system from working.
3, That only that chip and that chip alone is in use in a system.

Change any of these (and several other assumptions) and the argument does not hold.

The first assumption is actually very iffy and based on an argument that the adversary is omnipitant.

That is when the chip is designed the adversary knows exactly what sort of system the chip is to be put in, but also “knows the system” sufficiently well that they can guarantee getting the 512bit number to the correct pin as and when required.

Whilst this might be likley for front end devices in open communications systems it is by no means true. Importantly the further you get into a system the less likley it is to be true.

As a general case this sort of “omnipitance” only lies with the system designer not with a sub-component designer. Thus the less of the system goes on any given chip the less likley this attack is to work.

The second and third arguments are well known to design engineers and have well known solutions that originated from trying to design reliable systems using unreliable components and suppliers.

One of the logical results that was seen was the use of “voting protocols” by NASA to get the level of reliability required.

Put simply critical parts of the system where designed and built by three seperate unconnected organisations. The three different parts where all used in parallel in the final system. Each part received the same inputs as the others, however the outputs were put into a voting system as long as they all agreed then the action was taken. However if one part disagreed with the others the majority vote was used.

So for this “Kill Switch” idea to work with a voting system sufficient parts have to have kill switches built in that the adversary knows about and can actually use.

If you think about it a little further the voting idea can also work with a single device but using time displacment, and this is how we generaly realise a human has become unreliable. That is those around them notice that their behaviour has changed to a given set of circumstances and this raises alarm bells.

Similar detection systems can be used around chips, and inside chips when usuing imported blocks from other designers.

Clive Robinson • July 6, 2011 8:36 AM

@ RobertT,

“… expect that we are already firmly in the age of Systems on chip”

Yes and thereby hangs the problem, as you noted,

“… so a 50mm2 chip could contain 1000 full microcontrollers each executing their own independent program.”

It is not realisticaly possible to check all of these CPU equivalent cores on a chip, possibly only at the design stage and that’s questionable these days (how many SOC designers actually do any gate level development these days? as I understand it the majority just use libraries of functional blocks).

Which means effectivly we can not get what IARPA is chasing after in the way described, hence why I think we should look at other ways.

As you note breaking SOC systems down into seperate functional blocks on seperate chips is not likley to happen, not only for efficiency but also because some systems just won’t work if you try. However from a security aspect it should be high on the list of consideration as a method.

So let’s make an assumption that we can do things the “masked programable way” That is suppliers make available various functional blocks on chip but not connected up. The DOD or who ever puts out the spec for the same functional blocks to N independent suppliers and get back N different basic chip wafers that the DOD then track up as required.

The question then arises do they actually need to trust any of these functional blocks if they have some way of verifing their black box function in use?

I suspect that with some appropriate thought this could be done (with some loss of performance both in functional power and speed).

If you remember back some time ago Nick P and myself where having a conversation about methodology (Castles-v-Prisons). My view point was to have a large number of low gate count CPU cores connected to a shared bus to various resources such as system memory. However the important thing is the connection was not direct it was through a hardware interface the likes of an MMU that was controled by a hypervisor. That is the CPU was the Prisoner the MMU interface was effectivly the cell&door and the Hypervisor the trusty or guard. The CPU had no knowledge of any external environment and was limited in any function it performed and any memory resourses it was allocated. The hypervisor is responsible for loading the program into an arbitary CPU resource area and all comms would be via a write only + read only buffer mechanisum controled by the hypervisor. Importantly the Hypervisor can halt any CPU core and examin it’s registers state etc at will but importantly the CPU core would be unaware of this. Likewise when the core writes to a buffer the CPU core is automaticaly halted the Hypervisor reads and acts on the buffer contents and puts the appropriate information into the read only buffer and un-halts the core.

At first it appears overly complicated, however the idea is to segregate the CPU core from other system activity and have a minimal function that can be easily verified by the use of other cores and direct examination of the state. Also each function a CPU core could carry out has a signiture interms of CPU cycles/time memory/register usage and I/O buffer behaviour. The signiture is monitored by the hypervisor system.

The design assumption was that the CPU cores although trusted in terms of gate layout etc could not be trusted in the code they were running (ie it might be possible to get malware in). Likewise the trusty level hypervisors were only trusted a little further and so on up a multilevel hypervisor stack to the governor hypervisor. However the CPU core would never actually see or be able to influance the trusty layer and so on up the stack.

Now the question becomes can I extend the model to use untrusted CPU cores etc? and I think in some respects it can be done.

However at some point some hardware needs to be trusted, and originaly I assumed the hypervisor at some level was not a general purpose CPU but a limited functionality state machine with all states known.

So the question becomes can I have untrusted CPU cores on chip and a series of uncomited gates, that I can wire up by the mask to provide a trusted state machine. Obviously the wire up of the mask in this area remains unknown to the chip supplier as does anything other than the base functionality.

Clive Robinson • July 13, 2011 1:25 PM

@ Gregw,

“I suspect you might need 4-way (3n+1) due to the existence of “Byzantine faults” to resist subversion from a single source”

Yes in a 2n+1 system could be fritzed with one path owned, but the faults are not easy to generate because the other two systems should still agree with each other.

However going to 3n+1 means that if no pathways are owned, but a minor fault may cause two paths too go one way and the other two the other way you end up with an even vote so in a simple system you get deadlog (in a more complex system you can use voting history to see if one path is degrading but this in turn has it’s own issues). The next obvious solution is 4n+1 to give a 3of5 majority vote but this in turn has it’s own problems.

Voting protocols have advantages but… the original assumption is honest systems that are either functioning correctly or at fault and are thus switched out. Not that one system might be dishonest and therefore cheating.

One solution is using cheating protocols within the voting protocol where each system that makes a minority vote gets it’s vote value reduced. Another is to use two or more sets of voting systems but randomly flip the input values to the pathways so that any subverted system can be detected because it does not know it’s inputs have been fliped but the voting system does.