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.
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.
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.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.
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.
| ( 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.
| ( 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 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.
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.
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:
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.
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 2The 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:
|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.
N --------------------- | 1 1 0 1 .... 0 | 1 | 0 0 0 1 .... 1 | 1 M | ... | . | ... | . |________________|___ | 1 1 0 0 .... 0 | 1We 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 messagethen, 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.
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 - 1errors with m bits. Note that errors can also occur in the syndrome itself, so
m 2 - 1 >= n + m or m n <= 2 - m - 1For 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 15Consider 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
We can work out the syndrome for this message.
Now suppose the message gets corrupted in transit. So that the message looks like this:
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?