* 3 *

Pretty Good Security

Fact of the week

In 1977, three MIT professors Ronald Rivest, Adi Shamir and Len Adleman, building on the work of Diffie and Hellmann created a method of encrypting data for transmission which has become a standard for the transmission of sensitive information. This is known as RSA encryption. The method was patented in the US and a company was formed to license the technology.

Stallings chapters 3 og 5

Preparing for battle

Last week we talked about the requirements for security in computer systems in a general way. Let's now start the course on a pragmatic note by looking at practical techniques for helping with personal security. We say helping with, rather than implementing security because, as we have emphasized before any inexperienced user can be a weak link in the security chain, regardless of what tools you put in his hands.

Backups (redundancy)

Just about everyone who has used a computer system has experienced losing important data in some kind of accident. There are many reasons why data get lost: it might be due to carelessness or natural disaster. The purpose of a backup is to make a copy of data which is unlikely to be lost or destroyed by the same act as the original.

In older times, backups of disks were always made to tape. Tape was chosen because it is a relatively cheap medium, which is easily transported. If we want a backup to be protected from the same accident that would destroy the original, we have to store it in a different physical location. Today, the economics of backup have changed and data can often be mirrored to a disk at a different physical location, by using network copying. Tapes are relatively unreliable, so they have low security compared to disks. Operating systems have different preferred ways of making backups, using different software and media. Some things are common to all systems however.

The key principle of backups is redundancy. Redundancy means making multiple copies of data, so that we always have something to fall back on. We can have backups of data, but we can also have backup of services, in case we lose an important piece of hardware. Redundancy is like an insurance policy.

Clearly, making backups of every file is a time-consuming process, and it requires a lot of storage. There are two kinds of backup

Incremental dumps are applied according to some pattern. There are various philosophies about how to choose the backup types. Here is a simple sequence: 
        Day  Level
        ----------
        Mon   0
        Tue   1
        Wed   2
        Thu   3
        Fri   4
        Sat   1
See how this works. We start with a full dump on Monday evening, then on Tuesday we dump files which have been modified since Monday, on Wednesday we dump everything which has changes since Tuesday and so on, until Saturday, where we summarize everything which has changed since Monday. If we copy each dump to a different tape, or other medium, this means we now have potentially several copies of each modified file on backup, i.e. we have a high level of redundancy. This may or may not be necessary.

Another well-known sequence which provides a very high level of redundancy is the so-called Towers of Hanoi algorithm. The pattern over a number of weeks goes like this: 

       0 -> 3 -> 2 -> 5 -> 4 -> 6
       1 -> 3 -> 2 -> 5 -> 4 -> 6
       1 -> 3 -> 2 -> 5 -> 4 -> 6
       1 -> 3 -> 2 -> 5 -> 4 -> 6

    (to end of month)
You should work out for yourself, as an exercise, just how many copies of files are made in this scheme.

Digital Hashes or Message Digests

Trust is the most pernicious problem in security. How are we able to trust files and data which others send? Programs which we download could contain viruses or Trojan horses. Assuming that we trust the person who wrote the program, how can we be sure that no one else has tampered with it in between?

There are some things we can do to increase our confidence in data we receive from a foreign source, but when it comes down to it, all we can do is to verify the source of data and the integrity of data. In other words, we can tell with reasonable certainty who sent a message, and we can tell that the message has not been altered by anyone else in getting from the sender to the recipient. Trust must then be implicit.

Checksums or Message digests are non-forgeable digital signatures which quickly summarize the contents of a file. The idea is to create an algorithm which digests the contents of a file and produces a single value which uniquely summarizes its contents. If we change one bit of a file, then the value of the message digest also changes. Popular algorithms include: 

     MD4
     MD5   (Stronger than md4)
     SHA1
The MD5 algorithm is free for use in any program, as licensed by RSA who wrote it The Secure Hash Algorithm is proprietary, owned by the US department of commerce. It availabilty for use in programs outside of the US is therefore unclear. The MD5 program can be collected and installed on any system with a C compiler. Today, functions which implement the algorithm are built into most languages. It produces a 128 bit hash of a file, which is represented in a printable ASCII sequence:, e.g. 
     cube% md5 .cshrc
     MD5 (.cshrc) = 519ab7d30dba4a2d16b86328e025ec72
MD5 signatures are often quoted at security software repositories so that it is possible to verify the authenticity of software (assuming the MD5 signature is authentic!)

Another type of signature which is used by PGP, amongst other schemes (see below), is the Message Authentication Code (MAC). This is like a message digest but includes a component encrypted with a private key, in such a way that the receiver of the message can use a public key to check the identity of the sender.

Private and public key encryption

In the 1970's, an ingeneous form of encryption was devised which would allow any two persons to communicate on a private channel using only two keys per person. WIth traditional cryptography, each pair of persons would have to share a secret key. Thus N persons would need N(N-1)/2 keys in order to ensure privacy! The first realization of this was the RSA algorithm. The idea is this. Using an ingeneous algorithm, which we shall return to describe later in the course, Thus by publishing a public key to anyone and everyone, anyone can encrypt a message to X, but only X can decrypt it. We shall not yet concern ourselves as to how this magic works, rather we shall see how it works in practice. Note that, if we want to send 10 persons a message, the message has to be encrypted separately for each person, with each of their pubic keys. `Public key' does not mean that we can send a private message to everyone at once (what would then be the point of encrypting such a message?). What X can do, however, is to sign a message with data encrypted with X's private key. That way, anyone (who knows X's public key) can decrypt the data and verify that only X could have sent it, by knowing his private key. This is a digital signature of Message Authentication Code.

PGP: pretty good privacy

PGP is a program with a long and important history. It has been at the centre of a debate about American privacy laws, as well as laws concerning the export of strong encryption software. It is illegal in the US to export software providing strong encryption. Encryption software is classified as a munition, though recently the laws have been relaxed to allow American companies to compete in international markets. For this reason, there are two versions of the PGP software: a US version and an international one. There is even a GNU clone.

We shall use the GNU Privacy Guard program, for this course, since PGP has become poorly documented and difficult to understand. The principles are the same. PGP is called "pretty good privacy" because it explores the use of public, private key methods to enable encryption and signing. This allows users to send private messages to one another using strong cryptographic methods. Why not perfect security then? The reason is that, while the cryptographic methods might work well, users can still be tricked into trusting false data, so the security of even cryptographic methods is not perfect.

To begin using GPG, you have to create a pair of keys: a private key and a public key. To do this you use: 

gpg --gen-key
and follow the prompts (and defaults). You will need to think of a pass-phrase which is long but easy to remember: e.g. 
  I could tell you my pass-phrase but then I would have to kill you
This will be used to encrypt your private key, so that only you can read it. Of course you should not reveal the pass-phrase to anyone. When the key pair is created, it is hidden in private files. If you want to make your public key available for others, so that they can send you encrypted files, you must extract it as text and mail it to them. The keys are complicated and can be used in binary form, or ASCII form. My public key is extracted with 
gpg --export -a mark > filename
and looks something like this: 
-----BEGIN PGP PUBLIC KEY BLOCK-----
Version: GnuPG v0.9.10 (SunOS)
Comment: For info see http://www.gnupg.org
 
mQGiBDtdcNkRBACN4xRpVDv0Zx7tbv5JhD+W1uDJKfiBO7DtZ8IXz2Nv1iuhyCFb
QIXAd3zBd6sBrYkMk15bKeNj9hcEnZXtK1gVXPYIi2s03aVhq6fEFdigNlD3qWBE
vP5rMg1sa5uxcHd813FQC8LJPjRsHwUQ7lk7wkXcY/djXhn9JmLf9RDARwCgybj0
b+D4IChXz7afqhbiynuPOJMD/01ZWl3REmLg/nt29VPot50ufMyEts4K2h9z3h0b
3eS4ZjqdcwCr6d69PlXhuhp3a6bfPDfCdZ3IMs4U8mtMpkdOA7LAbm2SXwCW+pT5
KT6pW3Hv8jjAJdsVc/EoPB8JlvyViW5HJW+oz+NdQydgohSXtm4vtTvPwV5Bvufr
b93NA/9zwFz8QbuI+VWfjQx1aLKg+xTiOS0zJaG2IdacjvLVmFwzFec/Yv87mojb
31kg7zb5z/nn/JskZx9vvekbgSJknsTik+nJs3UDdLMIM+Ol0A632XeasYIKjwyZ
U/IOwHXtZ1Aeo1AR7MIoTMOLLn6hEffnv059J9bIXGOudfpPmrRBTWFyayBCdXJn
ZXNzIChBc3NvY2lhdGUgUHJvZmVzc29yLCBPc2xvIENvbGxlZ2UpIDxtYXJrQGl1
Lmhpby5ubz6IWwQTEQIAGwUCO11w2QUJCWYBgAMLCgMDFQMCAxYCAQIXgAAKCRA+
kjZW5jiA7NIwAJ9Td7rTBEVAV0dTZoZX6qsNaBXN5gCgjbTw2dK1yecZQeCdBtfz
ZYZN+/a5AQ0EO11xCxAEAK69w0z0Ec/Ba0VFeYPSOj+VPTuvCBqMdQsAPmpquV3P
QB2UX/4mFCFrEzvERJeWuZy0cwJRoANtFGXLee/nD0hP+XstpFYmq4GwNODbcFHf
+9t5oiOnS6Hv8VlaVTjaZ/xwD3jj2LiVd1uQ5qqb12zLFVYjw1ZxBzlxdnmDzEUH
AAMFA/9cM8zAt5342zgk4bxZ7SkOMhtb+cZyI8Q2QOp2SZ98FPY1/qbCbaL+pe4y
9dd1VmasIpiXcnMPKessD3CL9LBLWR2EaS44hqkZlrpCDJpPgDE0pvvzI9xoiWfU
5V5OWLZsQIbmOISMGT1E29ks2x1a0CZVhPBMtUpQSFJYHZWctIhLBBgRAgAMBQI7
XXELBQkJZgGAAAoJED6SNlbmOIDsY14AmO0lDn0Lvhs9cf4exxDUH6u/WwIAoMRL
3vBRzQ9ZGYCtvu35++wYl7o+
=ZzKN
-----END PGP PUBLIC KEY BLOCK-----
When you receive a key from someone else, you can add it to your key-ring by saving the key to a file (exactly as above). GPG looks for the lines 
-----BEGIN PGP PUBLIC KEY BLOCK----- 
-----END PGP PUBLIC KEY BLOCK-----
and takes what lies between them, so you don't have to strip away the rest of the message. You should be careful not to get any extra spaces or characters into the file, or the key will be read incorrectly (i.e. don't cut and paste from the screen, save to a file). To add the key from a file, then: 
gpg --import filename
In order to indicate to others that you are sure you know whose key it is, you can sign keys and say how much you trust them, so that others can share in your private knowledge. You should only sign keys that you know to be authentic. Use of signatures is a way of telling others that you think they should trust the information you send them. You can also sign your own public key so that others can verify that it has not been tampered with between you and them.

To sign a key in your keyring, 

nexus$ gpg --edit-key sigmund
gpg (GnuPG) 0.9.10; Copyright (C) 1999 Free Software Foundation, Inc.
This program comes with ABSOLUTELY NO WARRANTY.
This is free software, and you are welcome to redistribute it
under certain conditions. See the file COPYING for details.
  
pub  1024D/BB3B5564  created: 2001-07-24 expires: never      trust: -/q
sub  1024g/EEF5CD48  created: 2001-07-24 expires: never
(1)  Sigmund Straumsnes <sigmund@example.org>
 
Command> sign
 
pub  1024D/BB3B5564  created: 2001-07-24 expires: never      trust: -/q
             Fingerprint: 2962 8834 FAF4 7684 0E08  1B7B 87E8 916C BB3B 5564
 
     Sigmund Straumsnes <sigmund@example.org>
 
Are you really sure that you want to sign this key
with your key: "Mark Burgess (Associate Professor, Oslo College) <mark@iu.hio.no>"
 
Really sign? y
 
You need a passphrase to unlock the secret key for
user: "Mark Burgess (Associate Professor, Oslo College) <mark@iu.hio.no>"
1024-bit DSA key, ID E63880EC, created 2001-07-24

Encrypting a message (asymmetric)

Suppose I want to send a message to a recipient. I have to have their public key in my keyring. Then I do this: 
gpg -r recipient --encrypt filename --output newfile

e.g.

gpg -r sigmund --encrypt sig.msg
This results in a file called filename.gpg which I can then mail or give to that person. Note that with asymmetric encryption, I encrypt specially for one recipient.

Decrypting a message (asymmetric)

When I receive a message for me from someone else, I decrypt it by typing: 
gpg --decrypt filename --output newfile
Since I need my private key to decipher the message, I have to type in my pass-phrase. The result is a newfile.

Trust and signatures

Signing a message is like adding a cryptographic message digest which verifies the state of the message when you sent it. This is only part of a signature however. The other part is like RSA encryption in reverse. By using my private key, I can encrypt a signature which anyone can decode using my public key. This tells them exactly whom the message comes from (since only the owner of the secret key could produce a message decoded by the public key). This is a way of establishing consistency.

PGP occasionally warns us that a public key might not be trustworthy. How do we really know that it is the right key for the right person? For instance, suppose I receive an encrypted file from Sigmund. I decrypt it like this: 

gpg --decrypt filename
How do I know it came from Sigmund? The answer is I don't really know, unless I watched Sigmund send me the message, and I am sure that the message was not altered in passage. Anyone could claim to be Sigmund.

We decide which keys are to be trusted or not. Our trust is conferred by signing a key with our own. If we find a key which has been signed by several trustworthy individuals, we might be more inclined to trust the authenticity of the key, assuming that we trust them. (This leads to a so-called Web of Trust) For instance, I have just received Sigmund's public key. Since I watched him send it to me, I believe that it is his. I can sign the key with my signature like this: 

nexus% gpg --clearsign filename    (or just -s for a binary file)
When ever you sign something (and use you private key) you have to give your passphrase, in order to unlock it. (This is because, on most systems, others can access your files -- e.g. anyone on Windows 95, or the superuser on Unix). This results in a new file filename.asc. (Ascii, signed message)

This is a service to me and to anyone else who trusts my signature. Now when I try to decode a message from him: 

nexus$ gpg sig.msg.asc
gpg: Signature made Tue Jul 24 15:39:27 2001 MET DST using DSA key ID E63880EC
gpg: Good signature from "Mark Burgess (Associate Professor, Oslo College) "

Trusted third party

Some software houses sign code, so that user can verify its authenticity. This, of course, implies that one trusts the database of public keys, corresponding to private keys. The solution to this problem is to create a "trusted database", run by a third party (an impartial observer). This third party makes pains to assure the authenticity of they keys in their database. When a signature is encountered then, you are only trusting the "trusted third party".

Attacks against signing and encryption

With the recent attention given to encryption and signing, there has emerged a naive belief that signing and public key encryption give strong security, especially in combination. This is partially true, assuming that the keys are authentic. It is however possible to construct attacks against the naive use of these encryption methods.

Let's define some notation for representing encrytion and signing.

Public keys: capital letters
Private keys: small letters
Encryption with public key A: { "message" }A
Signing with private key b: ( "message" )b
We can now describe two attacks: The solution to both of these attacks is to SIGN, ENCRYPT and SIGN again messages. Note that symmetrical ciphers are not susceptible to these attacks.

We see that encryption mechanisms, while useful, are not an assurance of security.

Thought of the week

If you would wish another to keep your secret, first keep it yourself.
-- Seneca in Hippolytus, c. 60AD

Back