Rumpelstiltskin and his children: Part 2

In this post, I tried to explain the Rumpelstiltskin tree-graph algorithm. Apparently in the second part of my explanation, the part explaining the actual algorithm, I ‘ve ended up skipping a few steps that were apparently essential for understanding what the algorithm is supposed to do, and how it relates to the directional tree. So in this follow-up I’ll try to fill up the holes I left in my previous post.

So lets start off with the directional tree graph from my previous post:

Tree

The first thing that is important here is that each node in this graph has both a strong name (a password capability) and a weak name (a name that carries no authority by itself. The arcs between the nodes above are the strong names.

Now consider that each node has knowledge only of its own strong name and of the weak names of its children. If we were only concerned with maintaining the unidirectionality of our tree graph, than the following image would allow us to derive a child strong name knowing the parent’s strong name and the child’s weak name:

step1a

So if we have the strong parent name ‘Rumpelstiltskin’ and the weak child name ‘Bob’, we could use some kind of one way function to determine the strong name of that child. In this case ‘Slardibartfast’. Having the name ‘Rumpelstiltskin’ thus implies authorty to the parent node and all of its children, but the name ‘Slardibartfast’ impies no knowledge or authority over regarding the parent node.

Next to decomposition, there is an other aspect we are interested in: attenuation. If attenuation was the only aspect we were interested in, than an other use of a one way hash function would be usable:

step1b

In this picture, our node comes with two strong names. The first name gives unattenuated authority to the node. Using a one way hash function we create a second strong name for the same node. This second name implies attenuated access to the node, In the case of a file-system, this second strong name could be a read-only capability to a file or directory.

Now comes the interesting part: we want to combine the concept of decomposition with the concept of attenuation in a single algorithm in such a way that, and this is the essential quality of the Rumpelstiltskin tree-graph algorithm: “attenuated decomposition results in the same strong name as would decomposed attenuation”.

step2

On a first glance it would seem that we’ve just combined the two diagrams, but there is an essential addition: the use of a secret salt. Again like in the attenuation only diagram, we use a one way hash to create a strong name for attenuated access, but instead of using the unattenuated strong name to determine the unattenuated strong name for the child, we now use the strong name that implies attenuated access to the parent node to create a strong name that implies unattenuated access to the child node. Without the secret salt, doing so would imply that someone with attenuated authority to the parent could unduly gain unattenuated access to the child.  By introducing the secret salt to the second hash operation, we allow the parent node to act as proxy for all decomposition operations. That is, the parent node would need to:

  • Allow decomposing unattenuated authority to a parent to strong names implying unattenuated authority to the child.
  • Allow decomposing attenuated authority to a parent to strong names implying attenuated authority to the child.
  • NOT allow decomposing attenuated authority to a parent to strong names implying unattenuated authority to the child.

The fact that the holder of the strong name does not have access to the secret salt ensures that these properties can be guaranteed by the algorithm.Looking at the above diagram, its easy to see that attenuation of decomposition and decomposition of attenuation lead to exactly the same strong names. In order to do so we had to introduce a (server side) secret salt in order to disallow unintended privilege escalation.

We’re almost there, but there is still one more step to consider. Getting back to our imp, we must consider ‘where does our imp live? Or for a file-system, where is the serialisation of this node actually stored, and how is it stored? Lets look at the case of a file-system. Lets consider the nodes are serialized to a file-system that is supplied by some cloud storage provider that we do not fully trust. We would want to encrypt the file. Given that the node may be accessed with any of the two strong names, we can’t use the unattenuated access capability here, but we could use the strong name that implies attenuated authority as an encryption key. Doing so however implies we should never disclose either of our strong names to the cloud storage provider.  As you may expect by now, again the one-way hash operation comes to the rescue. We use a third one time hash operation to calculate the relative path where the encrypted  node serialisation is to be stored.   If we want to consider the scenario that there are entities that posses attenuated access strong names and also posess write access to our cloud storage directories, than we could again add a secret salt to this third hash operation, but in most cases it would seem that salting would not be needed for the third hash operation.

step3

I hope that this follow up blog post helps in the wider comprehension of what I think is a very interesting algorithm for creating attenuatable decomposable unidirectional tree graphs using password-capabilities/strong-names.

Rumpelstiltskin and his children

When communicating about my efforts on the upcoming version of my least authority file-system collection, I often seem unable to fully communicate the base design of the core capability-based file-system, even to many cryptographically educated people. In this post I’ll try to elaborate on the algorithm that lies at the center of all my efforts: The Rumpelstiltskin hash-tree algorithm.

Rumpelstilskin

rumplestiltskin-classics-illustrated-junior

In a fairy tale by the Grimm brothers that most of you will probably know by heart, a girl, as a result of her fathers big mouth, found herself in a rather problematic situation .  The king had locked her in a tower room filled with straw and had declared that she be decapitated unless she would spin the straw into gold by morning, An imp showed up and offered to help her out in exchange for her necklace, and the girl gladly accepted the offer. Next day, larger room with more straw, same story now in exchange for her ring. third and final day, even a larger room with even more straw, but as the girl has nothing left to give in exchange, the imp makes the girl promise to give up her firstborn child in exchange for his services.

Later in the story, the girl, now a queen married to the king is visited again by the imp who comes to claim his price. After pleading with the imp, the imp agrees that he will give up his claim if the queen guesses his true name within 3 days. When by chanche the queens messenger overhears the imp chanting:

“Today I bake, tomorrow I brew, then the Queen’s child I shall stew. For nobody knows my little game, for Rumpelstiltskin is my name.”

Learning his name, the queen is able to wield authority over the evil imp, forcing him to give up his claim to her firstborn.

You could say that the unguessable name “Rumpelstiltskin” is a token of authority not unlike what in information security theory we refer to as a capability, or more precisely a password-capability.

Directional tree graph

The CapFs file-system I’m working on, like most file-systems constitutes a tree. Unlike many file-systems though, the CapFs tree structure aims to be purely directional. That is, while in DOS, Unix, OSX or Linux we are used to navigate ‘up’ using a command like “cd ..”, the CapFs ‘directional’ tree adheres to the rule that:

“Authority to a node implies authority to its children but NOT to its parent.”

Names and true names

In our fairy tale, the imp its true name was Rumpelstiltskin (cap). This was the name that implied authority over the imp. The imp might have had an other non authoritative name used by others to address him, but if he had it was not relevant for the story.  Maybe Rumpelstiltskin himself did not have an other non authoritative name, but if he had any children, and those children had true names like him that could be used to wield authority over them, Rumpelstiltskin would probably often address his children by their non authoritative names.

Now talking of authority, if Rumpelstiltskin (cap) would want to delegate the authority to one of his children to an other imp, what options would there be? Lets assume Rumpelstiltskin (cap) had a kid named Slartibartfast (cap) for who he used the casual (non authoritative) name Bob.  There would be two ways someone could come to wield authority over Bob, either by using his true name Slartibartfast or by having authority over his parent Rumpelstiltskin that by proxy would give authority over Bob.  There are thus two authoritive ways to designate Bob:

  1. Slartibartfast
  2. Rumpelstiltskin::Bob

Back to our directional tree

Tree

So if we project Rumpelstiltskin and Bob to our directional tree graph, we could say that Rumpelstiltskin might be our tree’s root node. Rumpelstilskin being the root node has no name but his true authority carrying name. Bob and any other of Rumpelstiltskin’s descendants would have two names:

  • A normal name that implies no direct authority (name)
  • An unguessable name that implies authority (capability)

Attenuation

Where using a name and a capability (true name) for each non-root node in our tree takes care of making authority to branches and leafs decomposable, the authority to any sub branch that is implied by a capability  is still absolute. If we look back at our file-system example, one might want to delegate the authority to read without delegating the authority to write. We could provide non-root nodes with a second capability that would imply attenuated authority to a node, for example read only.  So now we have:

  • A normal name that implies no direct authority (name)
  • An unguessable name that implies FULL authority (capability)
  • An unguessable name that implies attenuated authority (capability)

The algorithm

Given that we have only a single type of attenuation (for example read-only), there is an interesting algorithm we can use to securely calculate new  unguessable names for non root node’s given its name and the unguesable name of its parent.

TripleHash

In the above diagram Key1 would be the equivalent of ‘Rumpelstiltskin’, Key2 would be the equivalent of a read-only capability to Rumpelstiltskin. The subnode name would for example be ‘Bob’,  and Subnode Key1 would be the equivalent of Slartibartfast.

Going from Rumpelstiltskin to a read-only attenuated capability to Rumpelstiltskin would be straight forward. We basically take an HMAC hash of the unattenuated authority capability (Rumpelstiltskin) and some static string, and use a representation of the resulting key2 as attenuated authority capability.  There is no secret salt needed in this step, so a shared static string is used instead.

For going from a parent capability to a child capability, there are two scenario’s:

  • From unattenuated parent capability to unattenuated child capability.
  • From attenuated parent capability to attenuated child capability.

To allow both scenario’s to be used, the calculation of the unattenuated child capability is done by taking an HMAC hash of the parent attenuated authority capability and the child’s name,  together with a secret salt.

The secret salt makes sure that we can create a system where a client holding an attenuated authority capability can ask a server for an attenuated authority child capability, but can’t itself derive an unattenuated authority child capability from an attenuated authority parent capability.

Secure persistence

When looking at the diagram of the Rumpelstiltskin hash-tree algorithm, we see there is is yet a HMAC operation and a key3 that we did not yet discus. The problem is that if we want to implement something of persistence using relatively public storage, for example with a cloud storage provide we don’t fully trust to keep our big bag of secrets secret, we will want to:

  • encrypt physical file’s
  • store our files in a way that does not disclose capabilities.

In order to address the first issue, we shall let our attenuated authority capability double as file encryption key for our file. We now use a third HMAC hash operation to create a 4th name that we use to determine the location where the encrypted file is stored.

High-security versus high-scalability

Regarding the final HMAC hashing steps there are two possible implementation mode’s for the Rumpelstiltskin hash-tree algoritm: high-security and high-scalability.  In the high scalability version, encryption and decryption could potentially be client side operations, and the server takes care only of enforcing read-only attenuation. In this mode, the storage path (key3) is calculated using a HMAC hash of the attenuated authority capability together with a static string. If in contrast we value security so much that we are willing to sacrifice the scalability that comes with client side en/de-cryption in order to prevent a cloud storage provider with access to an attenuated authority (read-only) capability to combine his explicit and his implicit authority into an unattenuated authority capability, than high-security mode would include the servers secret salt in the HMAC calculation of key4, mandating server side encryption and decryption.

In my own project I shall be using the Rumpelstiltskin hash-tree algorithm in high-scalability mode for now. Maybe in the future switching to  high-security may turn out to be desired, but for now the hole plugged by giving up the potential for adding scalability seems to small to justify the price of using high-security mode.

Conclusion

I hope reading this blog post somewhat clarifies the Rumpelstiltskin hash-tree algorithm, and I hope others may find the algoritm usefull for other projects as well. I’ll be using this algorithm in MinorFs2, but I feel it might have much broader usability than just user space file-systems. Please use this algorithm as you please, and comment on this post if you think this information is usefull or still needs clarifications somewhere.

Agile development: A nasty hack for a HR-Process bug?

Unless you have been living under a rock for more than a decade, you will probably have picked up on the concept of agile software development that has grown in both popularity and in the often dogmatic, piousness of its advocates.

In agile software development, as the concept goes, we address the industries high failure rate at successfully completing software projects on schedule while remaining faithful to its promised specifications. The idea is that many decades of software development have shown our inability as an industry to handle a project phase horizon of more than a few weeks.

That is, where our ancestors managed to plan and execute large projects that spanned decades and used hundreds of skilled laborers, the software industry has often shown its inability to plan and successfully execute a relatively small project of a few years with only a few dozen craftsman.

The solution, according to the Agile advocates has been to start small. Build something that works but implements only a small fragment of the specs, and than use incremental enhancements to one day arrive at the desired goal.  If we would project this idea to our ancient history, it would be the equivalent of the ancient Egyptians building a gazebo, upgrade it to a shed, as to, in a few hundred two-week iterations finally finishing a full blown pyramid.  While this may sound ludicrous, there does seem to be empirical data that shows that for software engineering this approach is actually working relatively well. At least, that its working quite well as opposed to what was happening before whole the Agile hype started out.

So Agile might have fixed a problem that needed fixing, but it did in no way answer the question of ‘why’ software engineering had been suffering from that problem while apparently in other fields, the dreaded up-front planning and long project phases had been working out pretty darn good for the last four or five millennia at least.

I believe the root of the issue can be found in an essay by Edsger Wybe Dijkstra where he writes:

My third remark introduces you to the Buxton Index, so named after its inventor, Professor John Buxton, at the time at Warwick University. The Buxton Index of an entity, i.e. person or organization, is defined as the length of the period, measured in years, over which the entity makes its plans. For the little grocery shop around the corner it is about 1/2,for the true Christian it is infinity, and for most other entities it is in between: about 4 for the average politician who aims at his re-election, slightly more for most industries, but much less for the managers who have to write quarterly reports. The Buxton Index is an important concept because close co-operation between entities with very different Buxton Indices invariably fails and leads to moral complaints about the partner. The party with the smaller Buxton Index is accused of being superficial and short-sighted, while the party with the larger Buxton Index is accused of neglect of duty, of backing out of its responsibility, of freewheeling, etc.. In addition, each party accuses the other one of being stupid. The great advantage of the Buxton Index is that, as a simple numerical notion, it is morally neutral and lifts the difference above the plane of moral concerns. The Buxton Index is important to bear in mind when considering academic/industrial co-operation.

Lets look at this brilliant and important assertion by Dijkstra, and projecting it to our long-running project problem. For now lets look at them as long running-projects instead of long-running projects. We see that basically we have people who we could classify as marathon runners (high Buxton index) , people who we could classify as sprinters (low Buxton index) and the whole spectrum in between. From this we could raise the hypothesis that our earlier problem with completing long running project could well have been the result of having people with a low Buxton index assigned to projects that warranted a high Buxton team. That is we might have been trying to run a marathon with teams made up primary of sprinters.

Looking at some of the more popular Agile methodologies, we see that Scrum actually uses the term sprint to refer to a short iteration in witch work is done. Scrum divides a project into small, maybe two-week iterations called sprints. In this way, Scrum basically is dividing a marathon into small 400 meter dash distances suitable for sprinters.  That is, rather than fixing the problem of having the wrong type of people for the size of the project by trying to get the right kind of people, Scrum actually solves the problem by chopping up the project into byte-size chunks so our low-Buxton individuals can function in projects that used to be a bad fit for their low Buxton index.  As a result however, this has led to high-buxton index individuals that were well suited for the original problem, now feeling very unhappy and reduced to factory workers, having to do short repetitive tasks, as to them a two week sprint feels like being forced to work on an unimportant detail that is only distracting from the long term goals. This again may thus drive these high-Buxton individuals to seek a career outside of software-engineering.

Now an important question to ask is: how did we arrive at the point where software engineering teams for larger projects became so dominantly infested with low-Buxton individuals as to warrant the use of something like Scrum to get ourself producing output successfully again? My thesis is that our HR-Process has a bug. A major bug. The HR process in general and for software engineers in particular has devolved over the decades into a process that favors the hacker over the engineer, the sprinter over the marathon runner, the trivia over the deep understanding. In our earlier history we had the master apprentice system for many trades, and in many old trades remnants of this system are still present in the HR-process. Software engineering however has no roots in a master/apprentice system. Without these roots and with our fast passed HR-departments these days, the HR-Process for this relatively new trade has suffered most from a low-Buxton index favoring process.

Combining these facts and my thesis I would dare to pose the idea that the whole Agile movement as we are seeing today is the direct result of the lack of a master-apprentice culture in software engineering and the current day fast passed HR-process. That is, Agile has turned out to be a surprisingly effective but nasty hack for a bug in our HR-process. A bug that is likely going to show up in other trades as well as the master/apprentice roots of many old trades pass into oblivion.

RaiiCap pattern: Injected Singleton alternative for C++

The Singleton design pattern is a so called creational pattern from the venerable GoF design patterns book. While this book is often seen as something of a software engineering Bible, the Singleton pattern I dare say (at the risk of being stoned to dead by GoF bigots) is one that , while being widely used and being immensely popular in software design, is in fact a very controversial pattern. A design pattern that I would want to refer to as an anti-pattern. So what is this Singleton pattern meant for? The GoF book states that a singleton is intended for when you aim to :

“Ensure a class only has one instance, and provide a global access point to it.”

No wait, “Ensure a class only has one instance” I could get into why you may wish for such a thing, butprovide a global access point to it” ? There are basically a few situations where providing global access to something isn’t an extremely bad idea.

  1. If its a constant.
  2. If it is a free standing function that does in no way use static mutables.
  3. A combination of one and two.

In any other conceivable scenario, global access is a terrible idea. It leads to tight coupling, to excess authority and knowledge, hard to test code, code that is impossible to reason about with respect to security properties like integrity and confidentiality, etc, etc.

So if we agree that having global access to a singleton, at least for any singleton that could not just as well have been implemented as a free standing function that accesses no static mutables, is a very bad idea, we can look at what we could do to provide for a useful pattern that aims to provide a way to accommodate “Ensure a class only has one instance”, while at all cost avoid the  “provide a global access point to it” part.

Well lets take a step back once more. There are two questions we need to ask about our problem before we set out to fix it. “Why would we want to assure that a class has only one instance of it”, and “Why would we need any design pattern to do that?” . The answer to the first question could be abstracted to : “There is a single shared resource that we need to manage.”, When you look at how singletons are used, you often see singletons managing a small pool of resources. So we could probably rephrase this to: “There is a scarce shared resource that we need to manage.”. 

So now we have the problem clear, its a resource management issue really. We have a scarce resource from what a substantial portion is acquired at class construction time (or in the GoF Singleton pattern,  lazily, but this is hardly an essential property that the Singleton strives to accomplish). So what we basically don’t want, if we have a large code base with many people working on it, that a developer would look at our class and think : “hey that looks about right, lets instantiate one of those over here”.

So basically what we need to stop this from happening is to find a way to limit access to the constructional patterns for creating instances of a resource management class.

To summarize my reasoning thusfar: We have reduced :

“Ensure a class only has one instance, and provide a global access point to it.”

to

“Ensure a class only has one instance”

that in turn we have expanded to the larger:

“Limit access to the constructional patterns  of a resource management class”

So lets see if we can device a new pattern for accomplishing this goal. I shall look at this from C++, as I feel I’ve solved this problem with a few C++ specific constructs and idioms. Solving the same problem with a pattern suitable for other languages is something I must currently leave as an exercise for the reader.

In C++, the base pattern for resource management is called RAII. I’m not going to rehash RAII here, but basicly it can be described as a ‘Constructor Aquires, Destructor releases, single responsibility’ pattern. Given that we identified our Singleton problem as being a resource management problem, any alternative to the Singleton problem in C++ should thus IMO basically rely on RAII as its basis.

So whats the problem with RAII that keeps us from using it as Singleton alternative already? The problem is that in most cases a RAII object that claims a substantial portion of a sparse resource can be constructed from anywhere within the code-base. There is nothing about a constructor other than maybe its constructor arguments that keeps you from instantiating an object from any place where you may like to do so, and there is nothing about the interface of a RAII class that should prompt the always in a hurry maintenance programmer to consider he/she may be depleting a resource or may be breaking the resource its access model by instantiating one more object.

As you might know from previous blog posts, I’m a big fan of capability based systems, and although C++ is about the language most removed from capability secure languages that one can get, and C++ by not being memory safe could by definition never have true capabilities, this should not keep us from using a capability like object in solving our problem. That is, we are not protecting our constructor from anything needing real capabilities here. We just want to make the in a hurry maintenance programmer think twice before claiming a scarce resource.  So lets just call these capability like objects for C++ RAIICaps, as they will be used in combination with RAII classes and are rather capability like in their nature.  So what would a RAIICap look like? Consider the following simple C++ template:

template <typename T>
class raiicap {
  public:
    friend int main(int,char **);
  private:
    raiicap(){}
};

Now within our RAII class we shall define our constructor as:

class raiiclass;
class raiiclass {
  private:
    ..
  public:
    raiiclass(raiicap<raiiclass> const &);
    ..
};

So what does this template do? Basically not much, it has an empty constructor nothing more, but this empty constructor is private, what keeps it from being instantiated in the normal way. C++ however has the friend keyword that can be used to give a befriended class or function access to the private parts of a class or object. The raiicap has no private member variables, but as its constructor is defined private, only its friends can instantiate it. The above defines the programs main  as friend. This means that only main can instantiate raiicaps, that it can than delegate to other parts of the program. Given that the RAII class requires a raiicap<raiiclass> reference as constructor parameter, this simple pattern effectively limits the access to the constructor of our RAII classes.

In main, this could look something like:

int main(int,char **) {
  raiicap<Foo> foo_raii_cap;
  Bar bar(foo_raii_cap);
  Baz baz();
  ..
  bar.bla();
  baz.bla();
  ..
}

In the above,  main instantiates a raiicap for Foo and constructor injects this raiicap into a new Bar object bar. The bar object now has the capability to create Foo objects. It might further delegate this capability, but this will need to be done explicitly. The also instantiated baz object does not get a raiicap to Foo and thus will have no ability to access to Foo’s constructor.

I think the above shows that, at least in C++, simple alternatives to the GoF Singleton pattern exist, at least for that part of the singletons intend that wasn’t a real bad idea to begin with. I’m pretty sure that similar patterns should be possible in other programming languages also. The most important thing to realize is that singletons in fact are a resource management pattern, and that for managing access to allocation of scarce resources, its a pattern that is both horrible and that, as shown above,  has alternatives that don’t have the same horrible side-effects.

Caps-Lock, security and PAM (Pluggable Authentication Module)

When logging into my desktop system (running Ubuntu), every once in a while the Caps-Lock key accidentally being pressed keeps me from successfully logging in to my system. While being just a minor and rare annoyance, its stuck in the back of my mind and I started wondering if something could and should be done about it.
I started wondering, what if I would make the log-in password caps-lock insensitive on my system. The first thing we need to understand is that caps-lock insensitive isn’t the same as case insensitive. If my password is ‘TomtiDom14’, a caps-lock insensitive password chack should match only ‘TomtiDom14’ and ‘tOMTIdOM14’. So unlike case-insensitive where there would be 256 different valid passwords, seriously degrading security for you password by dropping a single bit of entropy for each dual case character in your password, a caps-lock insensitive password takes away only a single bit of entropy for the whole password. While loosing a single bit of entropy in theory cuts the amount of time or resources needed to brute-force crack your password in half, this is not really that relevant if we take the approach that caps-lock insensitivity is an authentication system issue. We are thus not talking about making our password hash caps-lock insensitive, what would indeed be a bad idea that cuts brute-force time in half if someone were to get his/her hands on the hash of your password. We are talking about an authentication system that should simply , in failure, try the case-inverted version of the presented password. Authentication systems have excellent measures for rate-limiting or even blocking brute-force attacks, so a single bit of entropy should not be that much of a problem for our approach.

Looking at the usability increase however, we can see what happens when someone by accident has his caps-lock key pressed and tries to enter a password. Chances are that he/she won’t think about checking the caps-lock led. No, the first thing he/she will think would be making a type. So the password will be typed in caps-inverted one or more consecutive times. Then he/she will start to wonder if he/she didn’t have the password mixed up with an other password. He/she will than try that password, maybe two or 3 times, than maybe a third one. In the end, the user might have entered a number of false passwords sufficient to trigger a complete lock-out. So while making our authentication caps-lock insensitive slightly decreases the security of the password, and while accidentally having the caps-lock pressed tends to be a rare condition, the usability consequences of not having a caps-lock insensitive authentication systems end up being rather big.

So now that we have established that having a caps-lock insensitive authentication system for our passwords is a quite desirable goal, we need to look at how we can establish such a system.

On (Ubuntu) Linux, the authentication system is a modular system that uses so called Plugable Authentication Modules (PAM). There are many authentication modules available, and looking at the source code of the PAM system there appeared no central place to elegantly solve the problem in a simple way. I thus chose to fix the problem for myself by looking just at stand-alone systems using the basic pam_unix module. Fixing the problem for other modules can probably be done in a similar way. Although solving the problem in individual modules may not be the most elegant solution, it does show that its almost trivial to do so in a somewhat less elegant way.

Before we can change the way the pam_unix PAM module validates passwords, we need to get our hands on the sources of the PAM system. On my Ubuntu system I hag to use the following command to get the source.

bzr branch https://code.launchpad.net/~ubuntu-core-dev/pam/ubuntu

cd ubuntu

./configure

I had to add a -lfl flag to the LIBS definition in a few Makefile files to make the code-base build on my system. Now for the almost trivial fix. After that I could build the source tree:

cd modules pam_unix

make clean

Now for the patch to pam_unix. The file ‘support.c’ defines a function named ‘_unix_verify_password’  that seems like the perfect place for our patch.

A few pages down in this function we see an invocation of the function ‘verify_pwd_hash’. This function validates the password as it was originally typed against a password hash stored in the system. By adding a litle piece of code after this invocation, we can add a second invocation of the same function with a caps inverted version of our password.  The additional code looks as follows:


/* If the first check fails, lets try with inverted case. */
if (retval != PAM_SUCCESS) {
/*Allocate a string for the case inverted password.*/
char * capsinvertedpass= (char *) calloc(strlen(p)+1,0);
if (capsinvertedpass==0) {
pam_syslog(pamh, LOG_CRIT, "no memory for caps inverted password.");
} else {
size_t ip_index=0;
size_t ip_len=strlen(p);
/* Case invert every character */
for (ip_index=0;ip_index<ip_len;ip_index++) {
char ip_c=p[ip_index];
char ip_c2=ip_c;
/* Lowercase all upcase characters */
if ((!(ip_c < 'A')) && (!(ip_c > 'Z'))) {
ip_c2 = ip_c - 'A' + 'a'; /*uppercase to lower*/
} else {
/* Uppercase all lowercase characters */
if ( (!(ip_c < 'a')) && (!(ip_c > 'z'))) {
ip_c2 = ip_c - 'a' + 'A'; /*lower case to upper*/
}
}
/* Put the updated character value in the new password string.
capsinvertedpass[ip_index]=ip_c2;
}
/* Try again once more with the caps inverted passord*/
retval = verify_pwd_hash(capsinvertedpass, salt, off(UNIX__NONULL, ctrl));
free(capsinvertedpass);
}
}

Now we build the code again and move our updated module to the proper library.

make

sudo mv /lib/x86_64-linux-gnu/security/pam_unix.so /lib/x86_64-linux-gnu/security/pam_unix.so.original

sudo mv .libs/pam_unix.so /lib/x86_64-linux-gnu/security/pam_unix.so

sudo chown root:root /lib/x86_64-linux-gnu/security/pam_unix.so

sudo chmod 644  /lib/x86_64-linux-gnu/security/pam_unix.so

Now just to make sure everything is still working ok, we call login:

sudo login

Everything worked fine, and its relatively simple to do. We can now log in with or withour the caps-lock active. Its a quite simple patch that should be almost as simple for other PAM modules. I hope the above description will help others achieve the same. I feel that although an accidental caps-lock is rare, its sufficiently annoying when it happens to want a patch like the one described above. There is a minor security implication, but IMO the usability benefits outweigh the effective loss of a single bit of entropy.

Artist versus Craftsman.

If there is one thing I’ve learned the hard way with respect to software engineers, its to never trust first impressions. In many other aspects I have always been extremely good at sizing people up based on my first impression. To such an extend that some of my friends have jokingly accused me of witchcraft.
In contrast, with respect to software engineers and their skill and productivity level, I’ve turned out to have my first impressions proven wrong so many times that I stopped trusting them.

Sure, I know how to spot a standard mediocre software engineer based on first impression, but a good one, or one that generates an exceptional high percentage off the bugs for a project,  for some reason I’ve proved to be incapable of spotting the difference between those two. To me it seemed like the difference between being exceptional and being a major source of bugs was a subtle difference that I was unable to spot. Both the exceptional software engineer and the source of many bugs software engineers share major characteristics. Both are highly intelligent, highly creative and both have a strongly developed sense for aesthetics.

It took me many years of working in software engineering to notice a pattern emerge that seemed to point to what this difference might be. After working for a while with other software engineers, there were some software engineers that at some point felt the need to emphasize the creative aspects of their work as software engineer by referring to themselves as or comparing themselves with an ‘artist’.  The pattern that seemed to emerge was that for the group of highly  intelligent, highly creative software engineers with a strong sense for aesthetics, the eventual use of the word ‘artist’ and/or ‘artistic’  seemed to coincide with the sub group that instead of being exceptional ended up being a major source of bugs.

So, with all other things being seemingly equal between the exceptional software engineer and the software engineer that turns out to become a major source of bugs, does being an artist give us any pointers to what is different between these two groups? As someone who, before becoming a software  engineer, spent much of his time making drawings and air-brush paintings, I found this notion rather disagreeable.  For me, different from those ‘artist’ I talk about, software engineering isn’t an art but a craft. When we look back at the history of art, we notice an important paradox. Many of the most adored and most priceless pieces of paintings that were ever made, were created in an era when painting wasn’t considered an art and no painter would think of himself or refer to himself as an artist. A painter was a craftsman that took pride in his craft. He used his creativity in a way subordinate to his craftsmanship and the result, looking at the old masters was amazing and unsurpassed by most modern artist type painters.

So maybe the parallel between software engineering and artistic crafts like painting is indeed valid, but more than painting, choosing the  artist approach to software engineering rather than the craftsman approach is a road not without peril.

So basically the difference between being a major source of bugs and being exceptional at software engineering might just be a state of mind. Considering your craftsmanship as a subordinate tool to your artistic creativity  might be the thing that is holding you back from reaching exceptional heights as a software engineer. So you are an artist, fine, we’ll go with that. Take an example from the old masters. Make your artistic creativity subordinate to your craftsmanship. The old masters did it and produced some of the most beautiful paintings.If you are one of those highly intelligent, highly creative software engineers with  a strongly developed sense for aesthetics who considers himself an artist, this little shift in your state of mind might transform you to an exceptional software engineer without giving up on viewing software engineering as an artistic process.

MinorFs2

People who have read my blog, have read my article, of been at any of my public talks know about the problems of the unix $HOME and $TEMP facilities. MinorFs, a set of least authority file-systems aimed to solve this problem in a relatively ‘pure’ way. That is, it was a single granularity, single paradigm solution that gave pseudo persistent processes their own private storage that could be decomposed and delegated to other pseudo persistent processes.

A few years after I released MinorFs and a few years after I wrote a Linux Journal article about MinorFs, although its painful to admit, its time to come to the conclusion that that my attempts to make the world see the advantages of the purity of model that the stack AppArmor/MinorFs/E provided has failed.

At the same time, the problem with a $HOME and $TEMP directory that are shared between all the programs a user may run is becoming a bigger and bigger problem.  On one side we have real value being stored in the users $HOME dir by programs like bitcoin. On the other side we have HTML5 that relies more and more on the browser being able to reliably store  essential parts and information of rich internet application.

The realization of these two facts made me come to an important conclusion: Its time for major changes to MinorFs.  Now I had two options. Do I patch a bunch of changes on top of the existing Perl code base, or do I start from scratch. In the past I had tried to get MinorFs accepted as an AppArmor package in Ubuntu. At that point I ran into the problem that MinorFs had rather exotic perl modules as dependencies.  So if I ever want a new version of MinorFs to be accepted as a companion package for AppArmor, I would have to rewrite it quite a bit to not use those exotic dependencies. Add to this the major changes needed to get MinorFs as practical as it gets without compromising security, I had to come to the conclusion that there was little to no benefit in re-using the old MinorFs code.  This made me have to change my earlier assertion to: Its time to write a new version of MinorFs from scratch.

So what should this new version of MinorFs do in order to make it more practical? What should I do to help ang det it packaged in the major distributions that package AppArmor? The second question is easy, be carefull with dependencies. The first question however turned out to be less simple.

I have a very persistent tendency to strive for purity of model and purity of design. But after a few years of seeing that such purity can lead to failure to adopt, I had to take a major leap and convince myself that where purity gets in the way of likelihood to be adopted, purity had to make way.

After a lot of thinking I managed to concentrate all of the impurity into a single place. A place that allowed for configuration by the user in such a way that a purity sensitive user, packagers and administrators could create a relatively pure system by way of the config, while practically inclined users, packagers and administrators could just ignore purity al together. The place where I concentrated the impurity is the persistence id service. This service that didn’t exist in the old MinorFs maps process-id’s to persistence-id’s, but it does this in a way where one process might get a persistence-id that implies a whole different level of granularity than the persistence-id an other process maps to. Where the old MinorFs had only one level of granularity (the pseudo persistent process), MinorFs2 allows different processes to exist at different granularity levels according to the needs and possibilities of their code-base.

This is the base of the first of my practical approaches. It suffers one program that requires the existing user level granularity to co-exist with for example an other program that benefits from living at the finest granularity level that MinorFs2 provides.  I tried to come up with every potentially usable granularity level I could come up with. In practice some of these levels might turn out to be useless or unneeded, but from a practical viewpoint its better to have to much than to have the one missing that would be the best fit for a particular program.

So what would be the most important practical implication of allowing multiple granularities down to user level granularity? The big goal would be : Allow to simply and effectively  replace the usage of the normal $HOME and $TEMP with the usage of MinorFs2.

We should make it possible to mount MinorFs2 filesystems at /tmp and /home and have all software function normally, but without having to worry about malware or hackers with access to the same user id gaining access to their secrets, or being able to compromise their integrity.

This practical goal completely ignores the benefits of decomposition and delegation, but it does make your computer a much safer place, while in theory still allowing application developers an upgrade path to fine grained least authority.

An other practical choice I had to make was replacing the use of symbolic links with  using overlay file-systems for minorfs2_home_fs and minorfs2_temp_fs and dissalow  ‘raw’ access to minorfs2_cap_fs to unconfined processes.  I won’t get into the details about what this entails, but basicaly I had to abandon the golden rule that states: ‘don’t prohibit what you cant enforce‘.  Unconfined processes have access to the guts of the processes running under the same uid. This makes them capable of stealing the sparse capabilities that MinorFs uses. I took the practical approach to:

  • Limit the use of raw sparse caps to delegation and attenuation (less to steal)
  • Disallow unconfined processes from directly using sparse caps

This is an other practical issue that makes stuff a bit impure. In the pure world there would be no unconfined processes in a pure world, no way to steal sparse caps from the guts of an other process. So what do we do, we break a golden rule and close the gap as good as we can. Knowing that:

  • If the unconfined malicious process can convince a confined process to proxy for it shall be able tu use the stolen sparse cap.
  • If a non malicious unconfined process wants to use a sparse cap it can’t.

It hurts having to make such impure design decisions,  it feels like I’m doing something bad,  badly plugging a hole by breaking legitimate use cases.  I hope that the pain of  the practical approach will work out being worth  it  and I’ll be able to create something with a much higher adoption rate than the old MinorFs.