Hello all,
I have done some work for specifying a way to use passwords to connect
two instances of genode. The most work was done in minimalizing the
codebase that is needed to implement all functionality. Nevertheless
I'm not sure I have found the point of minimal (algorithmic) complexity.
Therefore I want to describe the point found (with rationale) and listen
to comments before doing further work in this direction.
First I represent all strings in the protocol as their hashes turned into
points on an elliptic curve. Rationale: Because curve points are needed
anyway to encrypt the traffic between the two instances of genode and in
this protocol at least partly represent the connected parties I want to
reuse that in the password protocol.
Second I want to associate every PD with a secret key, that is only available
to that PD. For this I would propose that core should host an implementation
of the PBKDF2 function with a fixed salt. This function should turn the trusted
path of its client into a cryptographic random string. This string can then be
used to produce individual and stable cryptographic keys in every component that
uses this functionality. To reuse as much functionality as possible I would propose
to use a ROM session with a special name ("keysalt" comes to mind) to implement
this functionality. Rationale: I would expect that in the future many components
will need to store cryptographic material from shutdown to boot. Therefore a central
facility to help there could be advantagous.
Third I want to be able to externally configure the connections with as much privacy
as possible. That privacy comes in handy when it is needed to store passwords.
Rationale: Especially in embedded there may not be a possibility to enter connection
information. And I don't want to have to implement two different protocols for the
same functionality.
I think this makes this the most general description of my approach: Name all items
(computer, components, user, passwords) with points on an elliptic curve with known
logarithms. Connect them with a data structure that encrypts that connection in such
a way that this connection is only visible to those who are connected, expressed as
those who know the relevant logarithms.
Now a little more detail: The most important information needed to understand the
concept is the construction of the connecting data structure. It consists of three
points on an elliptic curve. Two of them are simple. I will describe this structure
by giving the algorithm to compute it.
First you have the points A and B which name the proverbial Alice and Bob, the items
which should be connected. You need to compute the points K,R and C which make up the
data structure.
1. Choose a random point on the elliptic curve and name it R. (I said it was simple :-)
2. Choose a random scalar k, multiply it with the generator G and name the result K.
(Two points down and hardly a sweat. And independend of A or B!)
3. Compute R-kA and call it D.
4. Also compute R-kB and call it E.
5. Hash D (with possibly some identifying string for Alice) to a scalar d.
6. Hash E (with possibly some identifying string for Bob) to a scalar e.
7. Compute k(eB+dA) and name this point C.
The data structure consists of the points K,R and C and the identifying information
used in the hash (possibly implicit).
To use that information Alice (for example) computes this:
1. Compute R-aK and call it D.
2. Hash D (with identifying information) to scalar d.
3. Compute C-daK (where 'a' is the private key to A) and call it F.
4. Compute daF and call it M.
M is the same point for both A and B but not for other keys.
>From M there can be calculated a common key and a common string for connecting
(for instance a channel on IRC). Over this a method for more direct communication
(for instance DCC) can be negotiated. Of course encrypted.
Or in the case of a password M can be used in a PAKE implementation.
Now to the mapping of items to points:
- component
This component runs in a PD. That PD is associated (via "keysalt") with keying
material. From this a public key can be calculated and that point will be the
name of the component.
- computer
There needs to be a component that makes the computer available on the network.
The key of this component is modified by multiplying with its own secret key to
make a difference between the name of the computer and the name of any component.
- user
The users name string is hashed with the point that names the computer where the
user is registered. That makes users name point unique even in case of the same
name string. Because that scalar is not really secret the point derived from this
can not be used as a key. Not even in the connection data described above. But
it can be encrypted with ElGamal and used to lookup records in a database.
- password
The users name point is hashed together with the password string to a scalar.
This scalar is divided by a random scalar and multiplied with the name point
of the computer where the multiplicator is stored. The resulting point must
be transfered together with the name point of the user to the computer where
the multiplicator is stored. That computer looks up the record of the user
with its name point. When it has found the record it checks the last access
time and waits a little bit and returns the provisonally password point
multiplied with the multiplicator. If no record is found the users name point
is hashed together with some secret key to compute a fake multiplicator.
In every case a point for the calculation of a password point is returned
after a delay. (Rationale: By splitting the password and delaying the calculation
a brute force attac is legthened into impractical times.) The returned point
is then multiplied with the random scalar from above and the result is then
hashed again with the password string to the password scalar. That password
scalar is then multiplied with the generator point to obtain the password
point. This password point is only used to generate a connecting data structure
together with the component name point of the component that is authenticated to.
And the password scalar is needed to open this connecting data structure.
The connecting data structure is stored in a record together with the users
name point and returned if questioned with the (encrypted) users name point.
Rationale for making hashes dependent on points: In the password algorithm it
protects against some esoteric cases of password theft. Maybe the connection
data structure protects as well but I leave them in because double protection
is better than faulty protection. And when this is implemented anyway I would
want to use the same routine for all hashes and use the points for domain
separation (or the string in case of M). It can also protect against faults
in the hash algorithm. For instance SHA1 is broken, HMAC-SHA1 is not,last I heard.
So I would opt for using the pattern of HMAC with the point as key.
I hope I didn't overwhelm you with so many details. But I think they are needed
to get an idea of the direction I think is the most advantageous. If you think
the most advantageous lies in another direction entirely, please tell me so.
If you need more details please ask. But I wont promise a satisfying answer in
short time because I would have first to think about it. But I have some inkling
of the direction(s) that are possible so a handwavey answer is possible in short
time. So if you ask, please include some indication which way lay your preferences
for the answer.