* 5 *

Protocols and data integrity

Fact of the week

The data encryption standard DES was adopted in 1970s as a standard for non-classified government encryption. The effective key length of 56 bits (in 8 bytes) today provides weak encryption. The algorithm can be used with three separate 56 bit keys (in 24 bytes) using so-called 3DES encyrption. DES has outlived its expected shelf-life by more than ten years! In 1997 the AES or "advanced encryption standard" was announced as a replacement for DES and a competition held for algorithms. In October 2000 Rijndael was accepted, by two Belgian scientists. This is similar to DES in concept, but modernized.

Chapter 10 Gollmann, chapter 4 Stallings
One theory on the evolution of human intelligence is based on the idea that intelligence is used for trickery and deception. Experience amply confirms that without the ability to verify facts and truths, our world would quickly degenerate into corruption and power struggles. This is our nature. Authentication systems are a vital stepping stone in the evolution of information systems and the fight against deception and corruption.

Last week, we spent some time thinking about how authentication and integrity can be made to work, with the help of secrets, unique attributes, encryption and digital signatures. Before moving on, let's look at some examples of how these issues are used in several schemes.

Authentication schemes

Secure shell

Secure Shell has become a de-facto modern Unix standard authentication scheme, using public/private key encryption to verify the identity of both hosts to one another.

The hosts begin by attempting to verify one another's identity. First they check the IP address and hostname. Then the user has to type in a password and sends a public key (first time he/she logs on). Here's a quote from the manual page:

Each user creates a public / private key pair for authentication purposes. The server knows the user's public key, and only the user has the private key. The filenames of private keys that are used in authentication are set in $HOME/.ssh2/identification. When the user tries to authenticate himself, the server checks $HOME/.ssh2/authorization for filenames of matching public keys and sends a challenge to the user end. User is authenticated by signing the challenge using the private key.

Ssh2 automatically maintains and checks a database con- taining public keys of hosts. When logging on to a host for the first time, the host's public key is stored to a file .ssh2/hostkey_PORTNUMBER_HOSTNAME.pub in the user's home directory. If a host's identification changes, ssh2 issues warning and disables password authentication to prevent a Trojan horse from getting the user's password. Another purpose of this mechanism is to prevent man-in- the-middle attacks which could otherwise be used to cir- cumvent the encryption.

They thus check to see whether they know the public key of the remote host already, and verify the transmitted key with the one stored. If they key is unknown, it is transmitted by the remote host, and accepted on trust. If they do not match, an authentication error is issued. If all goes well, the hosts communicate a random session key, for further communication. This is not an RSA pair, but a regular shared key DESab(t), which is much cheaper to compute. 

    |      ( authentication )      |
    |          password            |  
  A |  --------->PUBa -----------> |  B  (knows public key)
    |                              |
    | --- sign PRIV a -----------> |
    |                              |
    |          ( data )            |
    |                              |
    |  ---- >  DESab(t)  ----->    |
    |  <----   DESab(t)  -----     |
It is also possible to avoid tying in a password, if you transfer you public key manually, or share a common home-directory on the wto hosts.

Cfengine - secure copy

During cfengine remote copies, connections are verified by host name and IP address. Since high levels of privacy are not crucial in system administration, a simple and computationally cheap approach is used. A common shared 3DES key is used between all hosts in a trusted configuration. This is used to exchange a one-time session key which is then used to encrypt all subsequent exchanges, avoiding replays. 

    |     ( authentication )       |
    |                              |  
  A |  -->DESab(DESab(t)) -------> |  B
    |                              |
    |  <------ DESab(t) ---------- |
    |                              |
    |          ( data )            |
    |                              |
    |  ---- >  DESab(t)  ----->    |
    |  <----   DESab(t)  -----     |
The integrity of transferred files is checked with an MD5 checksum after transfer, prior to installation.

Kerberos

Kerberos is an authentication system designed as part of project Athena at the Massachusetts Institute of Technology (MIT). Athena was to be an eight year project in collaboration with IBM and DEC (now Compaq) in order to create a secure environment for students at workstations, where password sniffing was a major problem. The authentication system Kerberos has found wide acceptance, in spite of its obvious shortcomings. Ironically, the Kerberos system, while designed for Unix workstations turns out to be more appropriate or NT, where only single user logins are permitted per host.

Kerberos uses DES cryptography (not RSA) to protect sensitive information on the network. When a user logs on to a host running Kerberos, the user is issued a ticket from a Ticket Granting Server (TGS) (this is a kind of session key). From that point on the ticket must be presented in all transactions. All information sent by Kerberos is encrypted with a user's pssword, so eavesdropping is not possible. Passwords are never sent over the network directly.

Kerberos authentication is based entirely on knowledge of passwords which are stored on the Kerberos Authentication Server (KAS) for a realm (Kerberos domains are called realms). Unlike Unix and NT passwords which are encrypted with a one-way hash function, Kerberos passwords are encrypted using DES and can be decrypted by the server if needed. This is seen by many as a serious disadvantage of the Kerberos system.

Using Kerberos looks just like using an ordinary host, except that tickets expire after a time and a user is asked to reauthenticate the login by entering his/her password again. This is to avoid the possibility of someone guessing or determining a user's ticket. There are two versions of Kerberos in use, i.e. versions 4 and 5. These behave differently but the general scheme is the same. Here is a simplified description (see Gollmann 10.2.1 for a better one). Suppose host A requires a service from host B.

  1. A user enters login name and password on host A at the start of a session.
  2. The username/ID is sent with a random challenge and the name of the TGS in clear text to the authentication server (KAS).
  3. The KAS replies with a session key or one-time-password for talking to the Ticket server which is ecnrypted using the user's password (stored on the KAS).
  4. The user can decrypt if the passwords match. If all goes well, the user is authenticated and is given the key K_tgs as proof.
  5. Using the session key K_tgs, the user's workstation then talks to the TGS whenever it needs a service and obtains an encryption key for each session between A and B. The user's password is no longer needed; the ticket is used instead. The ticket server is thus a one-time-password server which uses the key K_tgs as proof of identity.
Kerberos has a number of limitations.

DCE - Distributed Computing Environment

Digital Equipment Corporation (DEC, now Compaq) working in collaboration with others developed their own distributed computing framework called DCE. This has a similar login authentication scheme to Kerberos.

Directory Services: LDAP, NDS, AD

An idea which has become popular recently is that of directory services. Directory serviecs began as a way of disseminating user data (names, passwords, telephone numbers etc) throughout a complex organization. The concept has since spread into a general description of hierarchical network management, including security policies and access control mechanisms.

GNU/Linux and Unix-like systems are basing their efforts on an open standard directory service called L/DAP, devised by the University of Michigan.

Microsoft's recent addition to Windows 2000 is called the Active Directory. In Windows NT the domain was a separate entity requiring the security to be applied to each separate domain. Active Directory allows the security to be managed from the top down allowing for a consistent security policy through out the organization. Active Direcrory uses a version of Kerberos 5 for internal users. When a client PC requests authentication to a server the request goes to the Key Distribution Server (KDS). This responds to the client with the requested servers key, the client sends this key along with its request to the intended server, the server then authenticates the user. All of this communication is encrypted for use over an unprotected network.

External users can log on, using public key authentication, as in secure shell. When a user logs into AD an access token is created, these tokens consist of an individual Security Identifier (SID), a group SID for each group the user belongs to and user rights. When the user tries to access any AD object this token is compared to an Access Control List (ACL) to verify the user has authority to access the object.

Security is set in AD using group policies. This allows the administrator to set a uniform security policy across the domain. These policies can be set at the highest level of the organization and pushed down to all users.

PAM Pluggable Authentication Modules

A simple way to include multiple authentication mechanisms into OS software was introduced by Sun Microsystems. Sun's pluggable authentication modules for Solaris have since been adopted by several vendors and newer GNU/Linux distributions. They provide a transparent way to log on to several authentication systems simultaneously. PAM can be configured to use one or more authentication servers, from the usual login challenge. The default and weakest is regular Unix login. Other possibilities are Kerberos, RADIUS (PC login), NDS, DCE and user designed systems. See /etc/pam.conf.

Smartcards/Javacards

Smartcards have been around since the 1980's, particularly in Europe. They have small, dedicated microprocessor chips embedded. They typically consist of an 8-bit processor (8051/6805) and three classes of memory: ROM which holds a program, EPROM which holds customer data, and RAM (perhaps 16K) for performing computations.

Early bank cards in Norway used smartcards with embedded chips. These are now discontinued due to imcompatibilities with other systems, amongst other things. The main use today is in mobile phones and cable/satellite TV decoders, where SIMS (subscriber ID modules) are used to handle user details and encryption.

Smart cards were considered to be relatively tamper-proof and secure for years until European satellite TV started broadcasting Star Trek, and suddenly hundreds of computer-savvy geeks were looking for ways of breaking the codes.

Attacks on smartcards include:

Attacks on smartcards, their owners and makers are many: and so on...

Javacards are smartcards which contain a tiny Java virtual machine in ROM. The Java environment has a nnumber of features which are useful for smartcards. Applications can rely on a standard language and API (application programmer interface). There is also the promise of code standardization and platform independence. However, Java is not known for its resource efficiency, and the obstacles are many.

Integrity schemes

We talked about data integrity schemes, checked by checksums and digital signatures. But these techniques are computationally expensive approaches for extra security. What about just checking that the computer heard a message correctly? This is a much more fundamental problem which can be solved more efficiently than by using after-the-fact checksums. As a basic physical problem, it is interesting to consider before moving on to more political issues.

Shannon: information theory

Today, we are so used to flawless data transfer and storage that we think little about the issues associated with loss and errors. But this is clearly a prerequisite for any information system, and therefore any security system. If we want data integrity, we need to understand the issues of error detection and correction. Why is this a security issue? There are two reasons: the first is clearly that data are not secure to corruption unless we can detect and correct errors. The second is something we talked about in the first lecture. Think of mission critical systems. We need to be sure that our instructions can quickly be communicated without loss or damage to some critical operation. For instance, for the Galileo/Voyager space probes, floating around somewhere in the outer solar system, it takes a message minutes or even hours to be sent. There is no time to correct errors manually. Over such long distances, signals are weak and noisy: i.e. the probability of error is high. What can we do to cope? This problem was orginally considered by Claude Shannon of Bell Labs in the 1940's. He also solved most of the fundamental problems. Suprisingly, another application for this technology is in parallel disk storage (or RAID) and memory chips.

Parity checks

Let us assume that the probability of error is small. That is certainly true with our technology today. By small we mean that the probability of a single bit being wrong in a message is some small fraction of a percent (as small as possible). In particular, we ignore catastrophic errors such as scratches or breaks in media, which produce large bursts of errors.

Parity is about evenness or oddness, in the numerical sense. To find out the parity of a message, we add up the bits in the message; if the number of 1's is even, then we say that the message has even parity (or parity zero). If the number of 1's is odd, then we say that the message has odd parity, (or parity 1). Another way of saying this is that the parity of a message is 

 Parity = Sum_of_bits mod 2
The idea of a parity check is to make an extremely primitive message digest. We use one bit in a bit-string to signal the parity of that string. The sender calculates the parity and appends a parity bit to the data (e.g. 1 bit in every byte). The receiver then checks that the parity is consistent with the received message. If it is not consistent, then an error must have occurred. There are two problems with this: Errors must be corrected by retransmission.

Encoded redundancy

One way to correct errors, assuming that errors are infrequent, is to encode the same information several times, in short bursts. For instance, suppose we want to send the following bit string 
|1001|1100|0000|0101|
We could instead send two backup copies of each group of N bytes, say N=4: 
|              |              |              |              |
|1001|1001|1001|1100|1100|1100|0000|0000|0000|0101|0101|0101|
|              |              |              |              |
Suppose an error occurs in transmission, so that this message is received as: 
|              |              |              |              |
|1001|1001|1001|1100|1100|1100|0010|0000|0000|0101|0101|0101|
|              |              |  ^           |              |
                                 | (error)
This error can be corrected by assuming that the most probable value of each bit is chosen by majority decision. i.e. it is unlikely that the same error would occur in the two backup copies.

Two dimensional parity

Using multiple redundancy is expensive. Can we adapt the idea of parity bits (which was cheaper) to not only detect but correct errors? Suppose we arrange the stream of bits we want to send in a two dimensional MxN array. 
          N
  ---------------------
  | 1 1 0 1 .... 0 | 1
  | 0 0 0 1 .... 1 | 1
M | ...            | .
  | ...            | .
  |________________|___
  | 1 1 0 0 .... 0 | 1
We make the same assumption as before, namely that errors are rare, so that the chance of two errors occurring the same row or column is extremely low. In this scheme, we add a parity sum for each row and column. Now, if an error occurs, we detect a parity error in both a row and a column. This allows us to localize the bit which is in error, using far fewer bits. Since it is only a bit which is in error, we can simply flip the bit to correct the error.

This suffers from the same problems as with ordinary parity, i.e. that we cannot detect even numbers of errors in a row or column. On the other hand it has a huge advantage in efficiency compared to the multiple redundancy approach. If we define redundancy by 


 R =  Number of bits used in full
      ---------------------------
       Number of bits in message
then, as the length of the rows increases the redundancy becomes small. But we can't make the rows too large, or the change of errors increases.

n-dimensional parity: Hamming codes and RAID 3/5

Let's now consider another solution which is a kind of higher dimensional generalization of this idea. Let us ask the question: how many bits do we need to add to a message in order to not only find errors but correct them? R. Hamming found a solution to this problem which is ingeneous!

We suppose to add a number of bits (m) to a message n bits long, for error checking. We call the extra bits the syndrome. Suppose we choose a syndrome which is m bits long. If we decide that a zero value of the syndrome means no errors, then we can, at most, find 

      m
     2  - 1
errors with m bits. Note that errors can also occur in the syndrome itself, so 
      m
     2  - 1  >=  n + m

or         m
     n <= 2  - m - 1
For example, if we wanted to send a message 11 bits long, we would have to include a syndrome of at least four bits, making the total message 15 bits long. The efficiency 11/15 is not very good, only about 70%, but suppose we take a message of 1000 bits (2^10 = 1024), so we need only add ten bits for the syndrome, which gives an efficiency of 1000/1010 = 99%!

Let's see how it works. The method uses the binary (logarithmic) nature of the syndrome to locate bit positions within the message. Counting in denary (base 10) produces all possible bit pattern permutations when viewed in binary, as long as the number of bits is saturated. That means that the syndrome can be used to count the positions of bits. We shall suppose that a four bit syndrome abcd is to be placed somewhere in the message. This allows us to address a 15 bit message in total, i.e. send 11 bits of actual data per syndrome. Let's look at how the coding works. 

  Binary   Denary

    dcba   

    0000   0
    0001   1
    0010   2
    0011   3
    0100   4
    0101   5
    0110   6
    0111   7
    1000   8
    1001   9
    1010  10
    1011  11
    1100  12
    1101  13
    1110  14
    1111  15
Consider the rightmost parity check. If its value ends in a one, then it could part of several denary numbers: 1,3,5,7,9,11,13,15. If the second bit from the right is non-zero then it can only be a part of either 2,3,6,7,10,11,14,15. If the third bit is non-zero then it must be 4,5,6,7,12,13,14,15 and if the fourth: 8,9,10,11,12,13,14,15. Apart from powers of 2 (1,2,4,8) each bit pattern contains at least two bits. Thus, apart from powers of 2, there is a redundancy in the coverage of positions by different parity bits. This means we can cross-reference the bits with several parity checks, just like in the square array, only now with more bits (the number of bits increases with the length of the syndrome).

Now, let's suppose that a one means that there is a parity error, while a zero means that everything is fine. We spread the bits of the syndrome itself at the power-of-two positions, since they have the least redundancy. Now imagine sending the following message: 

 Message:  10111011011 
 Syndrome:  abcd
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Coded message a b 1 c 0 1 1 d 1 0 1 1 0 1 1

We can work out the syndrome for this message.

Notice how setting the bits like this tends to make all the checks have even parity in total (if we include the syndrome bits). This means that, if we recompute the syndrome for the message including the syndrome bits, the answer will always be zero for a correct message. The coded message is thus:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Coded message 1 0 1 1 0 1 1 1 1 0 1 1 0 1 1

Now suppose the message gets corrupted in transit. So that the message looks like this:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Coded message 1 0 1 1 0 1 0 1 1 0 1 1 0 1 1
To find the error, we now try to recompute the syndrome. If there are no errors, it should be zero. We work out All the checks except the last failed. The binary value of this number is dcba=0111=7, which is the position of the error!

Notice that if the error were in the syndrome itself, it still works, because of the way we chose to place the syndrome bits! Note that we can also correct a single bit error, since we can locate it precisely.

What if there are two errors? Then everything goes wrong. Double errors are unlikely, but possible. So we can fix this and allow for double errors by adding one more bit which carries the total parity of the first 15 bits (i.e. 16 bits, making a whole number of bytes). We cannot correct double errors, but we can detect them with one extra bit.

Notice that the efficiency is low in this example, but as we increase the number of bits the efficiency increases exponentially. In RAID disk technologies, parity bits are distributed across parallel disks, so that if only one disk fails, it can be reconstructed from the parity data on the others.

Thought for the week

Do you know how authentication works on your network? What scheme is used? How susceptible is it to attack? If someone points a gun at a user, they could obtain any authentication they desired... Do you know how reliable your data storage is?

Back