The flaws of shared-secret authentication

Consider the scenario where Alice wants to authenticate to Bob; that is, prove her identity to Bob. Also, let us limit the discussion to digital communication.

Shared-secret authentication is common. In particular, password-based authentication is still the most common way to authenticate a user to website. Gmail, Twitter, Facebook -- all major Internet services still use some type of password-based login.

Shared-secret authentication is an authentication approach based on sharing secret information between Alice and Bob prior to the start of the authentication. For example a password (or pin code, Mifare UUID, credit card number etc) is shared between Alice and Bob.

The inherent flaws of shared-secret authentication are:

• Impersonation. Since Bob knows the password of Alice, Bob can impersonate Alice if Alice reuses the same shared secret when authenticating with other parties.
• Proliferation of secrets. To avoid the problem with impersonation, Alice may choose to use one password for each party she would like to authenticate with. The obviously leads to a problem of remembering the passwords and having password-recovery mechanisms for all of them.
• No real identity. Shared-secret authentication can only be used among the parties who know the secret. Alice cannot use the same credential to prove her identity to others if she wants to avoid the threat of impersonation. Therefore, she cannot build a single identity between, for example, Internet services. The identity really only exists between Alice and Bob. Alice is not able to prove her identity to some one else using the same credential she is using to authenticate with Bob.

All these problems can be fixed! And, of course, the solution is to use public-key cryptography.

Let's call this public-key authentication. Alice and Bob generates key pairs and exchange their public keys with each other. Bob cannot impersonate Alice, Alice can safely reuse her credential for authenticating with multiple parties, and she can (if she chooses to) maintain a single identity between multiple parties.

The principle is: secret credentials should never be shared! The key pair should be generated by Alice and the private key should not leave the place where it was generated (except for backup purposes).

One could also call this type of authentication: zero-knowledge authentication. This is because Alice proves possession of her private key without revealing any information about the private key itself. She needs to reveal zero information about her secret credential to Bob or any one else.

Conclusion:

If Alice wants real, secure authentication, she should use public-key authentication. This requires a credential that can do public key crypto computations and handle a digital dialogue with Bob. To generate the key pair, a source of random data is also required.

Three fundamental types of identifiers: Local ID, Global ID, and Provable ID

Identifiers are crucial in information technology and in our society in general. There seems to be three fundamentally distinct types of identifiers. Surprisingly, I could not find any prior text on these identifier types, so I will describe them in this blog post.

1. Local ID. Local IDs are unique, but only within a specific context. They require an ID issuer to attain unique IDs within the context. For example, an integer can be used as an ID of a row in a database table (primary key). This ID can be used to pick one row in the specific table. The database manager is the ID issuer that ensures that each row of the table has a unique ID. Uniqness of the ID is not guaranteed outside the ID context (the database table in the example).
   
   Local IDs are common. Examples include: domain names, passport numbers, email addresses, variable names and US social security numbers.
2. Global ID. Global ID schemes require no central ID issuer. An ID can be 16 random bytes for example. Version 4 UUIDs, and GUIDs are other examples of global IDs. A checksum of byte content can be used as a global ID of the content as long as the content is static.
   
   Global IDs are (in practice) globally unique, but they can be forged. Anyone can create a specific global ID and claim that it identifies something.
3. Provable ID. A provable ID is an identifier that in itself can be used to prove what it identifies. The identification (id -> entity) is provable. A provable ID cannot be forged like a global ID or a local ID. No one can create a different ID and claim that it identifies the same thing. Also, no one can use a particular provable ID and claim that it identifies something else.
   
   A provable ID is a cryptographic construction -- a public key or a secure hash or similar. A secure hash can be used to as a provable ID of static content (content-addressable storage [3]). The GIT version control system uses a secure hash (Merkle tree) to identify commits. This is one example of a provable ID.
   
   To identify entities that are "live" (can compute) their public key can be used as a provable ID. An entity identified with its public key can prove possession of the corresponding private key.

Some IDs have other information included in them beyond the data needed to identify an element. Such identifiers are not considered in this blog post.

That is my take on identifiers.

[1] UUID, https://en.wikipedia.org/wiki/Universally_unique_identifier
[2] GUID, https://en.wikipedia.org/wiki/Globally_unique_identifier
[3] Content-addressable storage, https://en.wikipedia.org/wiki/Content-addressable_storage

Blog name change

Today, I am changing the name of my blog from "From Theory To Disk" to "My Take on IT" to reflect a broader blog scope. Will possibly cover just about anything in information technology.

You can reach the blog at: http://blog.franslundberg.com/ as before.

BergDB 2015.1

Released a new version of BergDB today -- BergDB 2015.1. Download it from bergdb.com.

BergDB 2014.1

I made a release of BergDB today. bergdb-2014.1.zip can be downloaded from bergdb.com.

The release is focused on stability, clean code, and an improved API. The software is getting stable. There are no known issues and 650 units tests that say it works (85 per cent code coverage). The API is getter more stable between releases and the binary database file format is not changing much.

So, in my opinion, it is now production ready for many types of development projects.

Database Mathematics

We need mathematical rigor in the theory of databases. The current situation is that we have a very weak foundation for database theory. Not even the basic concepts such as atomicity and durability have generally accepted definitions. Instead some ill-defined (yet often somewhat useful) concepts are taken for granted without clear definitions.

As mentioned before in post ACID Does Not Make Sense, the concept of ACID transactions is ill-defined. This blog also has a post (The CAP Theorem Is Not a Theorem) on the so called CAP Theorem where I agree with Mark Burgess that the so called CAP Theorem is not a theorem at all. Brewers conjecture has not been proven with mathematical rigour.

Data storage is mathematics. I believe it is possible to describe the function of modern databases in rigorous mathematical terms using existing or mostly existing mathematics. I wish I had the resources and the skills myself to develop the much needed database mathematics (or "data storage theory", "data mathematics", "database theory").

The need for more rigor is even more important now when there is a more diverse set of database products available. Yes, I do talk about the NoSQL movement. The relational model of SQL databases has a useful mathematical background. However, a decreasing subset of databases use the relational model introduced by Edgar F. Codd in 1969.

Durability could be defined using probability theory. What is the probability that we can read a value written to a database after after one second, one hour, one day, and after ten years? What is acceptable?

Atomicity would also benefit from a mathematical treatment. With global atomicity and transaction with serializable isolation level (SQL speak), the database state evolves through a sequence of distinct states. A transaction is then a mathematical function that takes the database from one state to the next. I have a draft blog entry on the different types of atomicity that are used in common database products and programming languages. We will see if and when it will be published.

There is so much more to say and think about this. It would be interesting to get in contact with a mathematician who would be interested in making a contribution in this field. And maybe I missed something in the existing literature? Maybe there is significant work on this already?

There Is No "Now"

Let's consider a common database with distributed clients. Often we tend to think about the "current state" of the database or the "now" state. But, really, in general, there is no commonly agreed on global state that all clients would agree on.

There is no now!

Even for a centralized database running on a single server, there is no consistent current state. Clients will not observe a commonly agreed on database state "now". The observers are distributed and there is always a delay until an update has reached a client. And this delay is not deterministic. No matter how short, there is always a delay.

There can be a central consistent view of the state, but not at distributed clients / "observers". This is equivalent to the Theory of Relativity. Information travels with a finite speed. Two observers will in general observe an update at different times.

So, eventual consistency is the only consistency there ever is!

However, all observers of a centralized database can agree on a global history of the database state. If the updates are sent from the central server to the clients in a given order, the whole history of the data up to the time of the last update that has reached a client can be agreed on between all clients that have received the update. All data is old, there is no agreed on now, but the history up until the last update received, can be globally agreed on.

This is one of the reasons why databases should be append-only (called "immutable" by some) and support historic queries. They should remember the history. This is the only thing that can be globally agreed on.


References:

The video: The Value of Values, Rich Hickley

http://markburgess.org/blog_cap.html
The Special Theory of Relativity for distributed systems