[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
"KeyNote" -- how to describe cryptographic keys.
Here is a revised proposal ("KeyNote") for representing cryptographic keys. It
provides increased flexibility with readable, compact notation.
An example of a KeyNote public signature verification key is:
(public-key (object-hash (md5 object))
(object-hash (rsa signature (const &03)(const &0435))))
We first distinguish two notions of what a "cryptographic key" is.
(1) Parameters that are input to a particular cryptographic
algorithm to fully specify how it should process an input.
Example: a DES key, or an RSA key.
Note that the specification of the algorithm is missing, or implicit.
We call this a "traditional cryptographic key".
(2) A complete specification of how to process an input, including
naming the cryptographic algorithms to be used, and how the
algorithms are to be composed.
Example: "Apply DES with key 0fDA443C2A5FFC2 to the result of
applying SHA to the input".
We call this a "general cryptographic key".
In what follows, we use "key" to mean "general cryptographic key".
Our keys will be programs in a tiny programming language ("KeyNote")
that has many standard cryptographic algorithms built-in.
An example of a KeyNote key is
(public-key (object-hash (md5 object))
(object-hash (rsa signature (const &03)(const &0435))))
This consists of two "statements" that can be roughly read as:
-- let object-hash be the result of applying md5 to the variable
called "object"
-- recompute object-hash again, this time as the result of raising
the variable called "signature" to the 3rd power modulo &0435.
Since we are recomputing the value of a variable that already
has a value, "fail" if the new value is different than the old one.
The high-level syntax for a key is one of the following:
( public-key <statement-1> <statement2> ... <statement-k> )
( secret-key <statement-1> <statement2> ... <statement-k> )
These are identical, except that a public-key may be freely disclosed
to anyone, whereas a secret-key may not. A "secret-key" may specify a
conventional secret-key transformation (e.g. DES), or it may specify
the private half of a two-key algorithm (e.g. RSA).
The statements are executed in order until the last statement is
executed or until one of the statements fails. KeyNote has no
if-then-else or looping constructs; a key is just a "straight-line
program". In some cases, executing a statment may result in a
"failure", in which case the execution of the KeyNote key terminates
with failure. A KeyNote key mail also fail if it does not define
a value for a variable that it is supposed to. (E.g. a signing
key must define a value for the variable "signature".)
Each statement is an assignment statement of the form:
(v1 v2 ... vk f)
where the vi's are variable names (octet strings), and f is an
expression to be evaluated. The number k of variables should be equal
to the number of values that f returns. (Note that some cryptographic
algorithms, such as DSA, return more than one value.) The effect of
executing the statement is to assign a value to each of v1 ... vk.
Each variable can hold a value that is an S-expression or "undefined".
The function f can return a sequence of values, each of which can be
an S-expression, or "undefined".
The statement fails if one of the variables vi was previously defined
and the assignment statement tries to define it differently. (It does
not fail if f returns "undefined" but the variable is already defined, or
if f returns "undefined" and the variable was undefined.)
A form f can have one of the following forms:
v f can be the name of a variable v. The value is the
current value of the variable named v.
Example: (a b) assigns the value of b to a
(const S) Here S is an arbitrary S-expression. The value of
f is just S.
Example: (a (const &03)) assigns the value &03 to a
(alg p1 p2 ... pk) Here f is a "function call" to the function
named "alg". Each of parameters pi must either be
a variable name or an expression of the form
(const S). If any of the parameters are undefined,
the result is "undefined" for all outputs.
Example: (y (des-encrypt (const &023487df6453197c) x))
assigns y the value obtained by encrypting
the current value of x with the key &02...
This completes the description of the KeyNote statements.
Certain assumptions are made about the run-time environment and the use
of keys for signing, verification, and encryption/decryption:
For a given kind of application, certain variables are pre-defined
and certain variables must be defined by the execution of the key.
(If not, the statement fails.) Here are these constraints:
For signing: predefined: object
must-define: object-hash
signature
For verification: pre-defined: object (optional)
object-hash
signature
must-define: (nothing; no failure means
signature verifies)
(For the record, let's also specify:
For encryption: pre-defined: object
must-define: ciphertext
For decryption: pre-defined: ciphertext
must-define: object
)
Here are some pre-defined algorithms, for to help with the next example:
(md5 x) -- returns md5 applied to x
(sha1 x) -- returns sha1 applied to x
(rsa m e n) -- returns m^e mod n
Thus, an RSA signature key might look like this:
(secret-key (object-hash (md5 object))
(signature (rsa h (const &6fda...)(const &0435)))
The corresponding public signature verification key might be:
(public-key (object-hash (md5 object))
(object-hash (rsa signature (const &03)(const &0435))))
Note that the statement (object-hash (md5-object)) has the following effect:
-- if object is defined, but object-hash is not, then a new value
is computed for object-hash.
-- if object and object-hash are both defined, then it is checked
whether or not object-hash is indeed the hash of object. If not,
the statement fails.
-- if object is not defined, then nothing happens.
The overall effect of the verification key is to check that the object-hash
gives the same result when computed two different ways (as the hash of the
object, or as the third power of the signature).
Further cryptographic functions need to be defined, but that's it for
describing keys!
I believe that the overall architecture of KeyNote is very clean,
yielding a straightforward implementation. Its clarity and
flexibility should improve the readability of keys and greatly reduce
the need for creating a large number of ad-hoc algorithm names.
Ron Rivest
Follow-Ups: