Dancing with Uncertainties: A meritorious case for race conditions and inconsistencies in operating systems

Abstract

There are various uncertainties in real world operating systems. Race conditions, cache inconsistencies, unpredictable thread orderings are some examples of such undesirable phenomena. These cause unexplained bugs in software, cost millions to organizations and can lead to much bigger issues like a major power blackout or a fatal error in diagnostic machine. There is a vast amount of research to mitigate these and make the systems more predictable. What if we take an alternate look at these uncertainties? Can we use these uncertainties to get something useful? Consider this problem of two millionaires. Two rich persons intend to find who is richer without knowing each other’s wealth. They don’t trust anyone else to do this comparision for them. Can we use the above uncertainties to solve this problem? This problem is formally known as the millionaire problem and is a well studied problem in cryptography. This is one instance of a family of problems named Secure Multiparty computation, where multiple parties compute a common function on their inputs without revealing anything about their own inputs other than what is revealed by the output of the function itself. This is a fundemental problem in cryptography, can be achieved using a construct named Oblivious transfer, also a fundemental and crtitical problem in the field of cryptography. Cryptography has always used noise and randomness to achieve security, atleast theoritically. But the noise or uncertainty available in operating systems is never used to achieve security. There were some attempts, for example, generating random numbers from race conditions, but they were all limited to such simple usecases. In this thesis, we use the uncertainties in operating systems to achieve oblivious transfer and secure multi party computation. We propose two protocols to achieve these constructs, using different uncertain mechanisms in operating systems. We use CPU instruction order uncertainty, thread reordering, and race-conditions, in the construction of these protocols respectively. We implement them on various real world systems and prove that this novel and alternate view is indeed practical and can be used to create real world cryptographic protocols. We also propose and implement a library which, given any uncertain channel of certain characteristics, implements secure multiparty computation between parties.