Self Protection using Opportunistically Cached Keys

Ways to Distribute Keys Safely in an Unsafe Universe

Kirk, James T.

Table of Contents

Abstract: Opportunistic Cryptography can be used to protect a wide variety of applications. It has come to the fore with successful applications such as SSH and OpenPGP. It stands in contrast to more statically minded, no-risk approaches such as SSL, which has been deployed only at unacceptable expense.

We introduce a framework to compare different approaches and levels to opportunistic distribution of keys We call this SPOCK ratings, as a catchy acronym. Each increasing number indicates a better and more intelligent protection for the application.



TBD ...


Schools of Cryptographic Thought

Opportunistic cryptography is that approach of cryptographic design that most benefits from the tools close to hand, and relies on risk-benefit analysis to deliver the best security at the lowest cost. That is, opportunistic cryptography holds costs and risks in balance, and aims to achieve a good level of security for a low level of cost.

It stands in contrast to no-risk cryptography, which conducts a "perfect" security model by careful construction of assumptions. This latter school has been much criticised for assuming away real difficulties, and creating infrastructures that have resulted in greater costs than the value of the security so delivered.

First in Their Class

Most representative of the two schools are the SSH and SSL protocols. In the former (SSH, or secure shell) the key is cached by the client in the first instance, and compared in each following use, thus leading to protection against any MITMs that turn up later. In the latter protocol, (SSL, or secure socket layer) keys are signed by certificate authorities ("CAs"), and the CA-signed certificate forms the mainstay of its protection against the man-in-the-middle ("MITM") attack and spoofing, threats assumed to be serious.

Both make their assumptions. SSH assumes that the MITM will not be present in the first connection. SSL assumes that the CA is correct in its statement that the key is correct.

As presented here, these assumptions are grossly simplified, but even still, their efficacy can be compared and contrasted. The first falls to a first instance error. The second falls to a shifting the burden error. SSH, the first, acknowledges and accepts that error, as an acceptable cost of an otherwise free connection.

SSL on the other hand attempts to shift the burden further and further; implementations initially push the burden onto the "merchant" who pushes the burden onto the CA, which pushes the burden onto key security systems and audits such as those under the WebTrust regime. In order to assure themselves that the statement in the certificate is correct in its claims, more and more complexity is assumed.

The Market Rules

The result can be seen in their respective marketplaces. By market penetration measures, SSL (in its originally designed field of browsing) has failed to secure even 1% of the servers [SS]. SSH on the other hand has dominated its original designed market, that of terminal connections. It has ousted telnet and secure-telnet from serious consideration, and is now the standard for terminal connections, whether they need protection or not (for example, the added expense of crypto is probably not needed in an internal LAN, yet SSH remains standard). And, it has done so in the presence of actual password sniffing threats that inspired its invention.

Structure of this Paper

The further efficacy of these methods is beyond this present note. Instead, we rely on the simple comparison that highlights SSH's relative market success. This is sufficient reason to concentrate on taking the SSH model and developing it further.

Firstly, architectures of key distribution protocols are briefly reviewed.

Then, five different SPOCK ratings are presented. We describe the specific opportunistic cryptography technique of client-side key caching, first popularised with SSH. It extends that basic caching into a serious of 5 improvements, which we call SPOCK levels. Each higher SPOCK level, for self-protection using Opportunistically Cached Keys, delivers a better level of protection, at increasingly higher implementation or application cost.

Finally, concluding remarks are added.

Key Distribution

A Primer on Key Distribution Issues

An essential resultant feature of cryptographic protocols is that protected packets are encrypted with a secret key algorithm. The sender encrypts, and the receiver decrypts. For this to work, in general, both sender and receiver must share the same key.

In order for sender and receiver to share a key, they must engage in what we call a key distribution protocol. This is quite a tricky affair; we cannot use the the cryptosystem itself to protect the key, as it is not yet shared. We have a bootstrapping problem - in order to share secret information, we need to have shared secret information.

This dilemma is alleviated somewhat with the invention of public key cryptography [DH]. Diffie and Hellman postulated that one key of a special pair could be used to encrypt, and the other be used to decrypt. The encryption key could be published, the decryption key kept private.

But this is not a total solution - the distribution of the public key can still be intercepted, and the interceptor can substitute his own public key. From then on, the interceptor can - and has to - also intercept all messages to decrypt and re-encrypt. This is known as the man-in-the-middle attack.

Key Distribution within Protocols

All good cryptographic protocols divide into two parts, the first of which says to the second, "trust this key completely [RC]."

The first part is often termed a key distribution protocol. It is generally integral with and tuned to the needs of the second part, which might be termed the protection protocol. The two walk hand in hand, and rarely is this marriage split asunder.

The following subsections describe common strategies for distributing public (encryption) keys. These approaches are most representative of Internet practice. In each case, the goal of the (first) protocol is to distribute the public key of one party as securely as possible.


SSH is a terminal connection system used to remotely manage Unix servers. It also offers a convenient tunnelling service. As such it is primarily a connection-oriented cryptosystem.

SSH clients take responsibility for detecting MITM. In the first instance, the client distributes its key .........





PKI use a deductive reasoning approach.

Schools of thought in Key Distribution

PKI/SSL leads the deductive school. In SSL's PKI approach, assumptions are stated concerning the well-being of keys. In simple terms, root keys packaged with clients are assumed to be good. Anything signed by a root key is deductively concluded to be good.

SSH on the other hand presents the inductive school. In SSH, a key presented for the first time is assumed to be good. This is a premise, and is only approximately true; its truth is based in part on the statistical rarity of the MITM attack, in further part on the knowledge that the user has of her context and her actions, and in final part the likelihood of this connection being vulnerable due to network factors.

Self Protection using Opportunistic Cached Keys

Unless specifically stated, the term keys refer to public keys, below.

SPOCK 0 - Static Checks - Prima Facea acceptance

When a key is presented by a remote node to the local host, a decision is required as to its acceptability. If the key is accepted, based on only the contents of the key packet as sent in that instance, then this would represent a null, or trivial level of care. This is labelled SPOCK 0, indicating its trivial level. The security properties are equivalent to using Diffie-Hellman key exchange.

Note that the presence of a CA signature on the key, making this key into a cert, is independent to the SPOCK rating. The protection provided by the CA signature on the statement of authenticity of the key is unaffected. The sum of both protections may be greater than the two apart, or not. If the authentication implied by the CA's signature is relied upon, and nothing else, then the protocol makes no use of opportunistic techniques presented here [SB].

SPOCK 1 - Present For Inspection

When a key is presented as above, its provenance may not be clear. There is a chance that an attacker has presented a false key, in what is known as a man-in-the-middle attack. Protocols are susceptible to this attack at one level or another, and our task is one of reducing the chances that an attacker can succeed in his attack.

The most basic way to check the provenance of a key is to punt it up to the application and request confirmation that it is good. In a user context, this can be done conveniently by displaying the fingerprint in the case of a raw key, or through other data available within the user's context, such as a signed user identifier (OpenPGP), or another signing key (certificates, Ricardian Contracts [RC2]).

Such a check only has merit if the higher layer has some special knowledge. It also needs to be repeated for each new presentation of the key, which may raise clumsiness in the application. We address that in the next SPOCK rating.


A fingerprint is a secure message digest of a key, presented in a form that allows the user to read it, send it, or compare it. The most common form is OpenPGP's hexadecimal grouping [gpg].

galland$ gpg --list-keys --fingerprint Grigg
pub 1024D/F72EFEA5 2003-12-08 Ian Grigg (DSS4) <iang@systemics.com>
     Key fingerprint = 64F7 F362 9591 4402 0252 DB5C 8674 8ABC F72E FEA5
sub 4096g/A9298CC9 2003-12-08

Using hexadecimal may seem odd, but it has evolved over much experience as an efficient way to read fingerprints over the phone. The letters can be read phonetically (alpha, bravo, charlie, delta, echo, foxtrot) and the group of 4 letters is a good compromise between speed and the participants' short term memory.

SPOCK 2 - Cache and compare

The key presented and confirmed as above can be cached. Every time that a new session is established, the key can be checked against a cached copy in a saved list. Then, one of three possibilities can happen.

Firstly, if the key is unknown, an application check can be requested. This is a fallback to SPOCK 1. On confirmation by the application, the key is cached for the next time, using as index the name that the local node knows the remote as (not the name that the remote node presents).

Secondly, if the cached key is checked and found to be the same as the newly presented key, the protocol can proceed without further ado.

Finally, if the presented key is found to be different to the one cached under that node's index, a warning can be issued to the application, of some severity. For example, additional confirmation could be requested, or the session could be refused point blank, and the user might have to manually reset the key.

A more advanced level of security is achieved. Caching keys and checking means that all routine communications after the first may be deduced to be as acceptable as the first was.

SPOCK 2 is achieved when the key is confirmed on first sight, cached thereafter, and checked against each following use.


SSH is generally delivered with SPOCK 2. Indeed, the SSH application invented this approach, and its author, Tatu Ylönen, deserves the credit. In many ways, his invention championed if not created the approach of opportunistic cryptography, and this paper solely attempts to place SSH's invention in a framework.

SSH is a tool to provide remote logins from client to server. The SSH client caches the fingerprints of remote servers in a file known_hosts, indexed by the original name that was entered by the user seeking to do the login [SF]. On each new session initiated by the user, the key presented by the server is searched for in this file by the client program. If found, then the client permits the connection to proceed without further ado.

If not found, earlier clients ask the user to confirm or deny the fingerprint. Later generation clients terminate and force the user to manually reset the key. These differences are reflected in configuration options.


OpenPGP clients are another example of SPOCK 2. If a key is unknown, the user is notified by the client of this. If the key is then accepted, it is stored and saved. Every later use is then easier as the program recognises the prior relationship.

OpenPGP clients typically go one step further than SSH. They permit the user to sign the keys themselves. In this way, they store a greater level of validation than is possible by SSH.

Or, is this SPOCK 5 - signing stores additional info?

Some further implementation notes

When a key is cached, it should be indexed under the precise name as supplied by the user [TK]. This name is known as a petname because it is supplied by the user, and it is private to this user [PNML]. This means that if a user initiates a connection to Bob then Bob becomes the index or label for future comparison, not bob, nor bob.localdomain.com, or whatever else pops out from processing. Likewise, if the key were to be found under another petname, this is irrelevent. Each petname's key should be cached independently, as many times as required, under each petname.

It is an implementation detail whether the entire key is cached, or just the fingerprint. This is more dependent on the protocol than anything else, assuming that the security of fingerprints as message digests is unquestioned.

The precise form of the warning given when a key is found to have changed is an application decision. It is a vexing issue. If the warning is too loose, the user might ignore the warning, and thus be tricked. If the warning is too severe, the user might stop using the tool, and instead use some other weaker tool [K6]. The compromise between the two extremes can only be found with experimentation and reference to the user's activities and preferences [more].

SPOCK 3 - Traffic Analysis

Where coupled with an observer capable of some decision analysis, such as a user, the key usage can be analysed. For example, key usage can be counted. Each time a key is seen and accepted, the count is incremented. The count can be presented to the application (user) in either an advisory or a confirmatory fashion.

Additional analysis could be undertaken using any available metric, such as IP numbers, times and period lengths of usage.

SPOCK 3 would be especially efficacious for web browsers which are subject to MITM attacks against SSL-protected sites with which the user has a prior relationship. For example, consider a user's Bank of America (or goldmoney account or any online account scenario). The user is sent a mail purporting to come from the Bank, yet, the domain is more like "Rank of Amerika," and the user cannot easily see the difference. If a user were presented with a count on the chrome of a browser display that showed 100 times for visits to his Bank, and 1 time - this time - for visits to "Rank of Amerika," then this would help the user to see through the phishing attack, and realise that the browser is now subject to a man-in-the-middle attack.

A further enhancement would be for the server to also count accesses, and for the client to request that count. If the count varies dramatically from that of the client, an error can be raised. The client always keeps its count confidential from the server. Is this the case? Or will it result in a successful attack being able to duplicate that request?

SPOCK 4 - History of Times

The next advance is to record the times of access. A heuristic agent could be notified that the last successful access was on such and such a day, and the connection lasted for so many minutes.

More advanced displays, perhaps available at the click of a button, could show the history of recent accesses.

A further enhancement would be for the server to also record times, and for the client to request those times as a display. If the times vary dramatically from those stored by the client, an error can be raised. The client always keeps its times confidential from the server. Is this the case? Or will it result in a successful attack being able to duplicate that request, request the times and then repeat them when asked?

SPOCK 5 - Application-level Knowledge

All of the above SPOCK ratings deal with information that the software engine within the protocol end point can definitively acquire and store itself, without regard to the content or use of the protocol. Fingerprints, keys, counts and times are protocol data.

The next and final level is to investigate data that could be acquired, stored and analysed from outside the pure protocol domain: application data. In alliance with an application, it may be plausible to record the actions undertaken in each connection, or for the application to specifically undertake actions to raise confidence. These actions could be subject to display, or some form of analysis, as directed by the application.

This form of analysis can only be conducted in concert with the application. There is little that the protocol engine itself can do to analyse the notion of the traffic passed over it, without knowledge of what that traffic means. Thus, the storage and control of this level of security protection may be totally under control of the application. The protocol engine may never see it, or may be relegated to providing a simply key-indexed storage facility.

For example, a browser user will often initiate dozens of clicks to a website before proceeding to a purchase; any one of those clicks and results could present information that would help the acceptance of the certificate. Likewise, a browser user might receive a URL over an email from a trusted friend. That friend could send a fingerprint, either separately or in the URL.

SPOCK 5 is a catchall level for that which is more driven by the application than the protocol. There is also no specific guidance on what may be dealt with, and how. In engineering terms, the implementor of a SPOCK protocol engine can safely ignore SPOCK 5, unless dealing directly with applications people. Further, it may well be that the application software does all the collection and storage. In contrast, SPOCKs 0-4 are entirely within protocol territory, and can be engineered into the protocol engine without resort and without conflict to the application (even though their effect might be low without cooperation with the application).


Independence to CA systems

SPOCK techniques are independent of the CA system of key distribution. The techniques described within can be utilised with CA certs, or instead of them. Neither side detracts from the other, and it may well be that the whole (both combined) is greater than sum the parts (high SPOCK ratings plus strong CA signatures)

This can be best seen with secure browsing. CA-signed certificates defend against DNS spoofing attacks that lead to an MITM attack that intercepts traffic. Yet CA-signed certs do not defend against phishing attacks where a bogus email causes a bogus URL to be introduced that imitates the web site under attack.

SPOCK protection defends against bogus URLs by storing and surfacing relationship information that the attacker cannot know and cannot change. SPOCK 3 when properly employed can give the user enough information that they can then protect themselves from bogus sites with some high degree of safety.

Yet, SPOCK levels will not defend against a DNS spoofed MITM attack [IP]." Together, the two defend against both classes of MITM. Apart, they only cover one each.


[credits] This paper has received substantial and important contributions from Twan Van der Schoot and Digby Tarvin.

[SS] Ian Grigg, How Effective is open source crypto? 15 March 2003. Also see the actual surveys that this claim is based on Secure Server Survey (June 1st 2004) at Security Space.

[DH] Diffie and Hellman

[RC] Ian Grigg, The Ricardian Contract forthcoming in IEEE proceedings of 1st Workshop on Electronic Contracts (WEC), 2004.

[SB] Secure browsing relies upon the CA signatures in certificates of keys, and is therefore at SPOCK 0.

[RC2] The Ricardian Contract, op cit.

[gpg] Gnu Privacy Guard, gpg(1).

[SF] For a more complete description, SSH Host Key Protection, Brian Hatch.

[TK] Tero Kivinen made this and other points, in private email. I have related it above to the petname concept.

[PNML] The Pet Name Markup Language, Mark Miller. Petnames was originally developed by the Electric Communities project.

[K6] See the 6th of Kirckhoffs' 6 Principles.

[more] I am conscious of the lack of firm advice above. The thing to consider here is that the developer rarely if ever knows as much as the user about their local security conditions. For this reason, I prefer to start light and then wind up the security as experience - attacks and breaches - prove themselves. But, this whole point is underlying the entire paper: what can we deliver that is free, unobtrusive, and secures the user without bothering them?

[IP] Actually, DNS spoofing itself may be covered by SPOCK 5 if IP numbers are cached. However, this is a quibble which does not change the essential argument of independence. There are other ways to do an MITM attack against the browser, and IP number caching suffers when network address translation and proxies are used.