On Secure Provenance and the logic behind the threat model

In our USENIX FAST 2009 paper (the "Picasso" paper), we discussed a scheme for providing integrity and confidentiality assurances to provenance of files. While this is a good first step towards securing provenance, I think there are many more issues we need to resolve.

These days, I see many security related papers advocating this or that scheme to secure objects. However, I really don't buy anything that claims to solve problems by having access control or policies. Here is why: access control works fine if the system is centralized, or the sysadmin of the system is incorruptible. However, when you have a distributed system with no control over other principals/their systems, OR when even sysadmins may become an attacker, there is no guarantee that access control constraints will be honored.

So, in the "REAL World", we can't claim to have a system that will prevent attacks from happening. With enough money, even trusted hardware devices can be breached (my co-advisor Radu Sion likes to stress on this point ... nothing is invincible). So, what can we do? We can't prevent someone from lying about themselves, or from deleting / changing things in their possession. What we CAN do is to prevent people from lying about others (i.e. "honest" others). This is exactly what guarantee we provide in our Secure Provenance work ... we prevent people from undetectably "invent" history involving other honest people.

To give a real life analogy, suppose a forger has painted a fake Picasso painting. The forger benefits here by taking his fake Picasso, and then inventing a fake history / provenance record involving his painting. He must have some honest buyers / art galleries listed in the provenance, otherwise, if the provenance only lists his cronies, it won't be believed.

The forger will NEVER do the opposite thing, i.e. take a real Picasso, and then remove its provenance and claim it to be painted by him. :)

The analogy applies to many scenarios involving data. I won't claim that it applies to all cases ... there are scenarios where the adversary might want to claim something as his own. An example would be the case of copyright disputes ... imagine two scientists bickering over who discovered something. But in most cases, the forger's goal with data is just like real life objects ... the forger wants to pass off something as what it's not ... so he needs a fake history, and that fake history must involve "honest" principals.

There are tons of issues to solve in order to have secure provenance ... but I'll write more about them later.

BTW, the painting shown above is a "real" Picasso, it is the painting titled "Dora Maar au Chat" (Dora Maar with cat). It is one of the most expensive paintings in the world; it was auctioned off in 2004 for $95 million!! Now, that has got to be the costliest painting of a cat!!