Zero-Knowledge Proofs

I think I’m going to make Sundays “Learn About Cryptology Day”.  Here’s the first installment: Zero-Knowledge Proofs.  ZKP is an interactive process in which one party can prove that they know a secret without revealing any information about that secret.  In doing this, a ZKP must satisfy three criteria:

1. Must be complete in the sense that if a person follows the protocol and passes then they have successfully proved that they are honest (within reasonable probability)
2. Must be sound such that a dishonest party cannot fool anyone (within reasonable probability)
3. Must be zero-knowledge meaning it cannot reveal any information about the secret, thus a dishonest party cannot learn anything while faking the process.

Cave Example

To demonstrate a hypothetical system I need to introduce some characters.  ZKPs are usually a two party systems, there is a prover (Peggy) whose goal is to convince a verifier (Victor) something.  In this example, Peggy will know a secret that opens a door in a cave.  The cave is circular and there is a door on the far end that blocks the path.

Victor would like to purchase this password from Peggy, but he  doesn’t want to give her any money until he is convinced that she knows the password.  Peggy is not about to tell him anything about the password since that would devalue it.  Together, they devise a system that will convince Victor that Peggy knows the password but satisfy Peggy’s need to secrecy.

Peggy enters the cave by selecting a path, A or B, at random.  Victor does not know which direction she chose.  Once Peggy is beyond the bend, Victor enters the front of the cave, picks a direction, A or B, and shouts it to Peggy.  She must exit the cave in this direction.  If she has to pass the door to do this, then she must unlock the door with the password.  There is a probability of 0.5 that Victor will chose the path that Peggy entered and she can simply turn around an leave.  This at first might seem like it ruins the whole procedure, but consider the probability of Peggy successfully anticipating Victor’s request say, 100 times (0.5^100 = 7.8×10^-31).  The chances of this happening are sufficiently low to be considered within reasonable probability.  The protocol is shown below (images from Wikipedia)

NP Problems

A more realistic implementation of ZKP is done with NP-complete problems.  NP-complete problems are a set of problems that are computationally difficult to solve, but easy to verify given then question and the solution.  They are a subset of NP (Non-deterministic Polynomial time) class problems.  A common implementation of ZKP with an NP-complete problem is to use Isomorphic graph transformations and Hamiltonian cycles.  Given a graph G, a Hamiltonian cycle is a path around G that visits each vertex exactly once and returns to the starting vertex.  There are many different cycles for each graph, provided the graph has a cycle to begin with.  In this example, Peggy knows a graph G, and a Hamiltonian cycle.  Victor knows the graph, but not the cycle.  Peggy aims to convince Victor that she knows the cycle without revealing anything about it.

1. Peggy creates an isomorphic graph of G, call it H, and sends it to Victor. 
2. Victor now asks Peggy to do one of two things:  show that H is isomorphic to G, or give a Hamiltonian cycle to H.  By revealing the cycle of H Peggy proves that she knows the cycle of G, because it is trivial to transform the cycle of G to that of H if G and H are isomorphic. 
3. If Victor asked Peggy to show that H is isomorphic to G then she must provide the vertex translations needed to transform H into G.
4. If Victor asked Peggy for a Hamiltonian cycle for H then she transforms the cycle that she has for G and sends it to Victor.  This reveals nothing about the cycle of G since Victor won’t have the vertex translations and doesn’t know exactly how H is isomorphic to G.

This problem is exactly the same as cave, with a probability of 0.5 that Peggy will be able to fool Victor at each step.  Any NP-complete problem can be adapted and used in a ZKP, provided there hasn’t been a break through that allows NP-complete problems to be solved efficiently (P=NP).  The security of these systems rely on the number of times the system is repeated, each time making it more and more difficult for Peggy to continue to fool Victor. 

There are many adaptations of ZKP, including a non-interactive version, and research is ongoing trying to find ways to incorporate these into authentication systems and the Internet. Post questions in the comments section below.

When a File Exists, but Doesn’t

I stumbled across a rather obnoxious “feature” in Vista today that I thought I should share with everyone.  With Vista, Windows finally enforces file system permissions and separates applications from user data.  It does this by restricting write access to the C:\ directory.  A user can read and write freely in their C:\Users\$username\ directory, but when they try to write to C:\Program Files or C:\Windows, they are presented with a UAC prompt that demands administrator privileges.   

This poses a problem for legacy applications that weren’t written with Vista’s security model in mind.  When you launch a program you are starting it with your permission set, which by default doesn’t have write access to the C:\ root.  If a program tries to write to say, C:\Windows, it will be denied.  To ease compatibility problems, Vista redirects these programs to a virtual directory that the program does have write access to.  A program trying to write to C:\Windows will be redirected to C:\Users\$username\AppData\Local\VirtualStore\Windows and will never know there was a problem. 

I discovered this the hard way this morning.  I have an application that normally needs to run with elevated privileges.  It has to start a kernel-mode service, read a log file in C:\Windows and write its own log file there.  When the application starts up it loads its own log file and displays it to the screen.  I wanted to run the application with a clean slate, so I stopped the service, deleted the services log and deleted the applications log.  I started up the program and was surprised that it was still loading its log file.  I thought I had deleted it!  Both Explorer and the command prompt claimed that the file was gone.  I tried to enter the path directly into Explorer and it couldn’t load the file.  But still, my application could load it.  I thought there might have been some strange caching with .Net applications, so I wrote a Win32 C program that loads the file and that one worked too!  So, now I’ve got two applications that claim to be loading a file that doesn’t exist!  Now I’m starting to get confused.  I run my program in Debug mode and drop into the debugger when it tries to load the file.  I was hoping that the debugger could give me more information about the file that it’s loading.  Even the debugger is telling me that it’s loading a log file in C:\Windows that doesn’t exist!  How can a debugger lie?  Ok, I know the answer to that, but it really doesn’t apply here…  The most bizarre part of this is that I could read the file from the command prompt with Edit, but only if I ran as a standard user, not an administrator.

As you can see, the admin prompt loads nothing, but the standard one loads the log.  What could possibly be going on here!?  It turns out, the Vista developers decided it would be better to completely lie to an application instead of allowing it to crash.  Apparently, I opened my application once as a standard user, and it got redirected to C:\Users\$usersname\AppData\Local\VirtualStore\Windows and wrote the log there.  Whenever an application tried to load a file from a protected folder, it will check that location, and then check the Virtual Store.  If the file is in the VS, then the application is given a handle to that, but the OS never tells the program where the file actually is located.  This keeps the transition invisible to legacy programs who will end up just reading and writing from the virtual store.  This would explain why Edit could only find the file if it was opened under standard user, since the admin one wouldn’t know which user’s virtual store to look into.

This was all quite aggravating to me and violates venerable UNIX law:

when you fail, fail loudly with lots on information to stderr

I guess this is what happens when you try to make changes to a system but still support backwards compatibility.  My opinion is that developers have been allowed to abuse the user permission system in Windows for too long, and don’t deserve the niceties provided but this feature.  If you want to write in a protect folder, you must run with elevated privileges, otherwise you catch the error or crash.  This Virtual Store is no more than a lie and operating systems shouldn’t lie.

Update??

So I’m happily using my computer this evening, browsing around the web, and suddenly the Apple Software Update program pops up.  I hadn’t seen it in a while, so I figured there must be an update to iTunes or QuickTime since I have it set to check for updates automatically and those are the only programs from Apple that I have.  Then I looked at what Apple wanted me to “update”

Look at that list of software.  No iTunes.  No QuickTime.  No update!  They are using their update engine to push out new software.  I have never installed Safari, nor do I have any wish to install it.  I really hate it when updates try to push new programs on me.  The worst offender used to be Java, which would offer me the Google Toolbar and OpenOffice during an update, but this just takes the cake.  The worst part is that I almost clicked through the screen without thinking about it.  I’ve had adware that was less obnoxious than this.  Software updates should be a sacred process, and developers have to fight for the trust of their users.  If a user doesn’t trust that an update is important, or this case even relevant, then they are less likely to update.  If users are slow to patch and update their software then they leave themselves open and vulnerable to attack.  A great example of this is the Code Red computer worm that took advantage of a hole in IIS that had been patched a month earlier.  If users had quickly applied the update supplied by vendors, then the worm outbreak could have been prevented.  It astonishes me that a major software company doesn’t understand this concept and is willing to stoop to this level of intrusion just for market share.  Then again, we’ve already talked about Apple’s lack of regard for the update process.   

Office Open XML Now an ISO standard

It looks like ISO has accepted Microsoft’s open file format Office Open XML and is set to become standard number DIS 29500.  The discussion on both sides of the issue has been heated for a couple of years now, with major companies like IBM and Sun opposing the standard and backing OpenOffice’s ODF, and Microsoft, of course, supporting its own format.  I’ve pretty much stayed out of the issue since I don’t pretend to know very much about either formats.  All I can say about this is that it is pretty big industry news.  This sets the table for improved interoperability between office products.  Wikipedia has a long list of applications that support OOXML documents in one way or another.  The length of the list is remarkable, considering the format has been available for such a short amount of time.  Gone are the days of reverse engineering an opaque binary file, now we just have to read through a 6,045 page specification document…

ISO adopts OOXML format as international standard [Washington Post]