Previous Next

Some technical notes on S/Key, PGP, and detailed explanation of some of the glib explantions I give in the first letter:

Table of Contents:

Section A. An overview

Section B. Philosophy

Section C: The packages

Section D: The Network

Section E: S/Key Section F: Weaknesses


Section A. Overview.

The login program has been replaced. It requests a one time password, instead of the reusable password, and then acts the same as the old login. (Well, it does more logging.) One time passwords (OTPs) are generated based on a random secret key, or a key screened by Adam. The list of OTPs is then distributed by email, protected and authenticated with PGP.

Back to Table of Contents


Section B. Why free security software?

Many people, when considering security software, seem to have an urge to run to a vendor, who will send in a bunch of smart sounding guys with short hair and suits, who will swear on their mother's grave that their product is 110% secure. And then they will give you a manual and some disks (in exchange for lots of money), and you trust these guys, and the people in their back room, to have written that software 100% correctly.

When you ask about the algorithms used, you discover that they are secret. Otherwise, how could the product be really secure?

Well, fact is, secrecy about the algorithm does not buy security. A really bright attacker can find out about it. You could find out about it, with enough work. A much, much better road to take is to publish the source code. Allow anyone and everyone to read it. Design it so that even when your enemy knows exactly what you did, it will not be possible to use that knowledge in an attack. That is what the products here S/Key and PGP, do. I've read the source to all of S/Key--Its short. I'm confident that if the mathematics work as advertised, the system is secure. I could never say that about vendor supplied software.

Back to Table of Contents


Section C. The packages we will be using.

C.1. What is S/key?
(This blurb is from the S/key README file.)

"The S/KEY one-time password system provides authentication over networks that are subject to eavesdropping/reply attacks. This system has several advantages compared with other one-time or multi-use authentication systems. The user's secret password never crosses the network during login, or when executing other commands requiring authentication such as the UNIX passwd or su commands. No secret information is stored anywhere, including the host being protected, and the underlying algorithm may be (and it fact, is) public knowledge. The remote end of this system can run on any locally available computer. The host end could be integrated into any application requiring authentication."
C.2. What is PGP? (This is again taken from the readme file that comes with pgp.)

"PGP, short for Pretty Good Privacy, is a public key encryption package; with it, you can secure messages you transmit against unauthorized reading and digitally sign them so that people receiving them can be sure they come from you." (Adam adds-- PGP runs on Macs, PC's, Amigas, many flavors of Unix, VMS, and possibly more.)

C.3. What is Public Key Cryptography? (This next answer is quite long, but covers important information, if you're really interested in the details, heres a large part of it.)

(The following is excerpted wholesale from the PGP users guide, volume 1, by Philip Zimmermann)

How it Works

It would help if you were already familiar with the concept of cryptography in general and public key cryptography in particular. Nonetheless, here are a few introductory remarks about public key cryptography.

First, some elementary terminology. Suppose I want to send you a message, but I don't want anyone but you to be able to read it. I can "encrypt", or "encipher" the message, which means I scramble it up in a hopelessly complicated way, rendering it unreadable to anyone except you, the intended recipient of the message. I supply a cryptographic "key" to encrypt the message, and you have to use the same key to decipher or "decrypt" it. At least that's how it works in conventional "single-key" cryptosystems.

In conventional cryptosystems, such as the US Federal Data Encryption Standard (DES), a single key is used for both encryption and decryption. This means that a key must be initially transmitted via secure channels so that both parties can know it before encrypted messages can be sent over insecure channels. This may be inconvenient. If you have a secure channel for exchanging keys, then why do you need cryptography in the first place?

In public key cryptosystems, everyone has two related complementary keys, a publicly revealed key and a secret key. Each key unlocks the code that the other key makes. Knowing the public key does not help you deduce the corresponding secret key. The public key can be published and widely disseminated across a communications network. This protocol provides privacy without the need for the same kind of secure channels that a conventional cryptosystem requires.

Anyone can use a recipient's public key to encrypt a message to that person, and that recipient uses her own corresponding secret key to decrypt that message. No one but the recipient can decrypt it, because no one else has access to that secret key. Not even the person who encrypted the message can decrypt it.

Message authentication is also provided. The sender's own secret key can be used to encrypt a message, thereby "signing" it. This creates a digital signature of a message, which the recipient (or anyone else) can check by using the sender's public key to decrypt it. This proves that the sender was the true originator of the message, and that the message has not been subsequently altered by anyone else, because the sender alone possesses the secret key that made that signature. Forgery of a signed message is infeasible, and the sender cannot later disavow his signature.

These two processes can be combined to provide both privacy and authentication by first signing a message with your own secret key, then encrypting the signed message with the recipient's public key. The recipient reverses these steps by first decrypting the message with her own secret key, then checking the enclosed signature with your public key. These steps are done automatically by the recipient's software.

Because the public key encryption algorithm is much slower than conventional single-key encryption, encryption is better accomplished by using a high-quality fast conventional single-key encryption algorithm to encipher the message. This original unenciphered message is called "plaintext". In a process invisible to the user, a temporary random key, created just for this one "session", is used to conventionally encipher the plaintext file. Then the recipient's public key is used to encipher this temporary random conventional key. This public-key-enciphered conventional "session" key is sent along with the enciphered text (called "ciphertext") to the recipient. The recipient uses her own secret key to recover this temporary session key, and then uses that key to run the fast conventional single-key algorithm to decipher the large ciphertext message.

Public keys are kept in individual "key certificates" that include the key owner's user ID (which is that person's name), a timestamp of when the key pair was generated, and the actual key material. Public key certificates contain the public key material, while secret key certificates contain the secret key material. Each secret key is also encrypted with its own password, in case it gets stolen. A key file, or "key ring" contains one or more of these key certificates. Public key rings contain public key certificates, and secret key rings contain secret key certificates.

The keys are also internally referenced by a "key ID", which is an "abbreviation" of the public key (the least significant 64 bits of the large public key). When this key ID is displayed, only the lower 24 bits are shown for further brevity. While many keys may share the same user ID, for all practical purposes no two keys share the same key ID.

PGP uses "message digests" to form signatures. A message digest is a 128-bit cryptographically strong one-way hash function of the message. It is somewhat analogous to a "checksum" or CRC error checking code, in that it compactly "represents" the message and is used to detect changes in the message. Unlike a CRC, however, it is computationally infeasible for an attacker to devise a substitute message that would produce an identical message digest. The message digest gets encrypted by the secret key to form a signature.

Documents are signed by prefixing them with signature certificates, which contain the key ID of the key that was used to sign it, a secret-key-signed message digest of the document, and a timestamp of when the signature was made. The key ID is used by the receiver to look up the sender's public key to check the signature. The receiver's software automatically looks up the sender's public key and user ID in the receiver's public key ring.

Encrypted files are prefixed by the key ID of the public key used to encrypt them. The receiver uses this key ID message prefix to look up the secret key needed to decrypt the message. The receiver's software automatically looks up the necessary secret decryption key in the receiver's secret key ring.

These two types of key rings are the principal method of storing and managing public and secret keys. Rather than keep individual keys in separate key files, they are collected in key rings to facilitate the automatic lookup of keys either by key ID or by user ID. Each user keeps his own pair of key rings. An individual public key is temporarily kept in a separate file long enough to send to your friend who will then add it to her key ring.

Back to Table of Contents

C.4. What is a one way hash function?

A one way hash function is a mathematical function whose input can not easily be guessed from its output. X squared is not one way, its pretty simple to take a square root. 'Cryptographically strong' one way functions are generated by people who spend lots of time studying this stuff, examples are DES, md4, or md5. The unix crypt(3) system call uses DES to encrypt your password locally. (Note that the crypt program does not use the crypt system call, but instead implements a variation on the German Enigma machine, which can be broken in about 3 minutes on a modern workstation.) (DES is also getting close to worthless as an encryption system. Both brute force attacks and some analytic ones are getting easier. There are also persistent rumors that the NSA (American National Security Agency) crippled it by shortening the key.)

C.5 But wait, isn't PGP illegal?

Well, the legality of using PGP used to be questionable. The RSA public key algorithm used in PGP was patented in the USA. (It was not patented outside of the USA) PGP versions before 2.4 did not include licenses for the RSA patent. There are now versions of PGP that are fully and unquestionably US legal, and they interoperate with versions outside of the USA.

C.6. Why are there are so many versions of PGP?

The MIT, International, and Viacrypt versions of PGP are all nearly identical, and interoperate completely. The international versions, (2.3, 2.6ui) were released to the world by a group of programmers outside the US who wanted strong cryptography to be available to everyone. A company called ViaCrypt has a commercial use license for RSA, and sells an unencumbered license as part of 2.7. The MIT version (2.6.2 is current) is licensed to use the RSA algorithm, but only for 'non-commercial purposes. The large number of versions in use is a little confusing and annoying.

Back to Table of Contents


(Section D: The Network)

D.1. How exactly are passwords transmitted?

There are quite a few RFC's which describe telnet, and I doubt you want that much detail. Essentially what happens is a connection is opened while you see the "Trying 134.174.81.56..." message, and once that is opened, all the data, such as the password prompt, etc, is transmitted as data, without any encryption or protection. This was recently exploited by an attack on the Panix public access internet service in New York City.

D.2. Doesn't Kerberos address this?

Yes it does. The Kerberos system (from MIT) does address this, and any other security problems, and I don't think it would be overkill to be using it.

D.3. So why aren't we using it?

Unfortunately, Kerberos requires a source license, and oodles of time to install, unless the vendor ships it. (In which case, I'd run but not trust it.) Since no vendor ships it, and I don't (as you may have noticed) have oodles of time on my hands, we aren't using it. Also, Kerberos requires secret keys to be chosen for each remote site, which is a lot of work.

Back to Table of Contents


(Section E. S/Key)

E.1. Ok, we got a great explanation of PGP, now how does Skey work?

You have a list of one time passwords. (OTP) (Either on paper, or created by a program. The OTP is the Nth hash of some secret. I'm going to use 10 as the value of N from here on, because it makes the text easier to read. When you login, the server has stored the 11th hash of the secret. You provide it with the 10th hash. (A hash is some one way function that is easy to compute, but difficult or impossible to get the data from the hash.) The server hashes the 10th hash one more time, giving it the 11th hash. It compares this to the 11th hash of your secret that it has stored, and if they match, is assured that you know the secret, and are really you. It then stores the 10th hash in the table it keeps, and next time around, you will need to provide the 9th hash. Then it runs all the normal stuff login runs, and logs you in.

E.2. Why does skey use 64 bits of data?

Good question. While md4 is secure against trying to logically figure out what input produced a given output, you can always use brute force, and try all possible values for x where md4(x)=your last used password. Trying 2^32 possible values would take a lot of work, but it can be done. Trying 2^64 would be practically impossible. To be a bit more precise, my Mac LC3 can do about 10 000 md4 hashes per second. Exhaustively searching through 32 bit numbers would take about 5 days, with solutions found, on average, every 2 1/2 days. Searching a number 32 bits longer will take 4 billion times as long.

E.3. Those credit card things are way cool. Why don't we use them?

Two reasons. Cost, and they're supplied by a vendor. The cards cost roughly $50 per card, and that can add up pretty quick, and you can see my commentary on vendors above. The other reason is that using paper lists allows us to randomly generate seeds, giving us extra protection from a dictionary attack. (A dictionary attack is based on the fact that most people use words that are a small subset of the possible combinations of eight letters. If everyone used passwords like z^rBz$34, dictionary attacks would be useless, but the fact is most people use things like sex and cash as their passwords. The Morris worm had a list of about 200 which it used, quite successfully. Since I don't expect you folks to type z^rBz$34 into your credit cards each time you login, we get nearly the same security by using a paper list generated from random seeds.)

E.4. Couldn't we do this some other way?

Sure. I'm open to suggestions. Please take a minute to look at ~adam/security/advisories/ciac-e-12:sniffing, and CA-94:01 to get some more background on the problem before making suggestions.

E.5. Why do you guys generate the password list?

Because if we don't, there is an easy attack on S/Key, and that is the passwords you choose. A badly chosen password can cut the effective entropy of that 64 bit number to 5-10 bits. You can supply a password to me (encrypted) via email. I'll decide to accept or not accept it based on my assessment of its guessability. I'll rule out single words, words with simple substitutions of zero for the letter o, the number one for the letter l, etc. I will accept phrases, two or more words strung together with something else, say dog!boat, or things, such as long German words, that look like random strings of letters. :)

This does not mean that a line noise-like password will allow you to avoid using S/key; merely that you need a dictionary attack resistant password to use a software client.

E.6. Isn't the list being stolen a really bad thing?

Well, yeah. It is. Id be much happier if the list were never stolen. However, I figure the odds of the Ubercracker picking your pocket and knowing what machine you are trying to log into is pretty slim. Also, most pickpockets are much more likely to do nasty things with your credit cards than with your password list. You will tell me at once if the list goes missing, right?

E.7. Could you tell us more about the software that runs on our home machines?

There is a Mac program and a DOS TSR that will run on your home machines as follows: You come find me and say, I'd like to run the program to avoid typing things when I'm at home. You choose a seed password. You remember this information, and type it in at home, and the magic six words will appear on your screen, ready to be cut & pasted into the login prompt. You can also do this via email, so long as the message is sent encrypted. Unencrypted or unsigned messages will not be accepted.

Back to Table of Contents


Section F. Weaknesses.

F.1. You skipped right here, eh? Everyone does. It makes a certain amount of sense. Never believe claims that any system is 100% secure. Go back and read the rest of this document; this will all make more sense if you read through the rest of this document first.

The system is compromised if someone has root access to SPL machines, and knows what they are doing. However, even Kerberos wouldn't prevent that.

Remote users could choose to leave the decrypted file of OTPs on disk, or photocopy it and leave it on the copier, or do all sorts of things with it. We try to prevent this via education. However, even if someone does get ahold of the list, and cracks a secret password, it 'only' buys them 80-100 logins. This is not quite so bad as it seems, as we do have other security measures in place, but its time enough to get root access, and be a major pain in the butt.

There are a number of theoretical weaknesses in PGP on multi-user machines, most of which are very difficult to actually exploit in practice. See volume 2 of the PGP users guide for more on these.

The system does not prevent eavesdropping on your sessions, it just prevents people from logging in without proper authorization.

There is a potential for the 'gee-whiz' aspects of the system to prevent or delay intelligent thought about potential vulnerabilities of the system.

© Copyright 1994 Adam Shostack. All rights reserved.

Previous Table of Contents Next

[Prev] [Top] [Next]