CIS307: SECURITY

Read Chapter 7 in Kurose-Ross's book and chapter 8 in Tanenbaum-VanSteen.

Security Threats can occur to data, hardware, software, and communication links. Examples of security threats are interruptions (with loss of data, denial of service), interceptions, modifications, fabrications. Of course we aim for Secure Systems, with properties such as:

We will focus on the first three properties.

In considering security we need to distinguish what are the security policies supported and what are the security mechanisms used to carry out the policies.

Some of the mechanisms involve:

Examples of higher level mechanisms are:

CRYPTOGRAPHY

  • SENDER -->message-->ENCRYPT-->encrypted-->DECRYPT-->message-->RECEIVER

  • message = plaintext

  • encrypted = cyphertext

  • C = E(M), E: encryption algorithm, M: Message, C: Encrypted form of message
    M = D(C), D: decryption algorithm
    Since good en/decryption algorithm are hard to find, and can be stolen, people find it best to use keys in the algorithm, so that if a key is stolen, one can choose another key, without having to invent, implement, distribute a new algorithm. So the algorithm is public (not private) and the key is private (for now). When using keys, it is usual to write the encoding/decoding as follows:
    C = E(M, Ke), M = D(C, Kd) Ke: encryption key, Kd: decryption key

  • One-way function: a function that is easy to compute but difficult to invert: F(X) is easy to compute with result Y, but given Y is very difficult to determine X such that F(X) is Y.

  • Trap-door function: a one-way function that, if we know a specific piece of information, can be inverted easily. That is the case when we have the decryption key to decode an encrypted message.

  • The key can be private (also called secret) or public. If private only one program knows it. If public, any program can obtain it, usually from an appropriate service. The longer the key, the safer it is. Suppose that I use a key that is just one bit. It is either 0 or 1; it will not take a malicious listener long before the key is guessed!

  • An encryption/decription schema is symmetric if the same key is used for encryption and for decryption. [To be precise, en/decryption is symmetric if there is a well defined known function for converting between the encryption and decryption key.] It is asymmetric otherwise. Usually symmetric algorithms are much faster than asymmetric algorithms. Often one uses asymmetric cryptography to obtain a key for symmetric cryptography; this key, called a session key, remains valid only for one communication session.

  • Data Encryption Standard (DES) - secret key, symmetric. Uses 64 bit keys (56 of information plus parity bits). It encrypts/decrypts data in chunks that are 64 bit long. Other sizes often used in DES are 128 (112 of information) and 192 (168 of information). As the size of the key grows, the difficulty of breaking the code grows, exponentially.

  • Diffie-Hellman (1976) introduced the concept of public keys. [Apparently, in 1973 Clifford Cocks in England came up with the same concept.] If two interlocutors want to talk we will have a Sender and a Receiver. The Sender will find out from a "reliable source" the public key used by Receiver and encode the message with that key. Only the intended receiver will know the private key and decode the message. [To answer the Receiver will have to use the public key of the Sender.]

  • Rivest-Shamir-Adleman (RSA) (1978) 
    	D = E, i.e. same algorithm for encryption and decryption
	Ke is public, so we call it Kp
	Kd is secret, so we call it Ks
	----------------------------------
	Choose two primes p and q, let N = p*q
	We will be able to send only messages whose numeric code is < N
	Choose an integer e relatively prime to (p-1)*(q-1) = Z.
	Find the smallest integer d such that
		(d*e)mod Z = 1
	Then the public key Kp is [e,N] and the private key Ks is [d,N].
		     e
		C = M   mod N   //This says that the message M must be smaller
                                //than N. If longer, break it up into 
				//chunks smaller than N and encrypt them 
				//individually.
		     d
		M = C   mod N
        Apparently, given N and e, it is computationally hard to compute d,
        if N is sufficiently large [al least 512 bits]. p and q must each
	be more than 200 bits.
	----------------------------------
	Example: p = 13, q = 17, N = 13*17 = 221, Z = (p-1)(q-1) = 192
		 e = 5
		 d = 77
		 The number of bits we can encrypt is 7 since
		 2^7 = 128 < N = 221.
		 So if we want to send a message longer than
		 7 bits we will decompose it in 7 bit fragments
		 and encrypt them individually. 
	----------------------------------


    


	The RSA algorithm is not good for protecting
	large messages since with it encryption/decryption are fairly
	slow - more that 1000 slower than DES. But it can 
	be used to transmit essential information, such as 
	secret keys and passwords. [Apparently on a 175Mhz Alpha
	RSA encrypts 1kbps, while 56-bit DES encodes over 30Mbps.] 
	In RSA it is normal to use 512-bit and 1024-bit keys.
    Secrecy: Principal A wants to send a secret message M to principal B. [It is usual in the security area to use names like Alice and Bob for the principals involved in the interaction.] Let Kp(B) be the public key of B, Ks(B) the secret key of B. A will send E(M, Kp(B)). B is the only one with Ks(B), thus it is the only one who can read the message. 
                    A  -->  E(M, Kp(B))  -->  B
  • The Key distribution problem for public and private keys is dealt with through a Public Key Infrastructure and the use of digital certificates.

  • One-Time Pad: There is a an encryption method that is unbreakable, but very inconvenient. Suppose that we know that we need to send from A to B a message of n bits. We give before hand to both A and B a pad string s of n bits randomly generated. Then A will encrypt his message M as M^s, where ^ means exclusive or. And B will decrypt the encrypted message E with E^s. The trick is that, take a message bit x and a pad bit y, we have

    x^y^y = x

    Try it for any of the values of x and y and you will see it is true.

  • Block Cyphers: Both DES and RSA are block cyphers, that is the message is broken into chunks, or blocks, that are individually encrypted. This gives rise to a problem: an attacker may infer something about the code by looking at the individual blocks that may be repeated in different messages or in the same message. For this reason Cypher Block Chaining was introduced.

  • Cypher Block Chaining (CRC): Each message is started with an extra block, say, the current daytime, which makes the block unique. This plaintext block is encrypted. For all successive plaintext block, before encryption we will XOR it with the encrypted block of the preceding plaintext block. At the receiver we will decrypt the first cypher block. Then for all other cypher blocks, before decryption, we will XOR them with the preceding cypher block. [Remember: XOR is idempotent.]

  • Stream Cyphers: For the transmission of phone conversations, for efficiency reasons, instead of block cyphers are used cyphers that encrypt messages incrementally one bit at a time.

  • Steganography: On a totally different plane, a secret message may be superimposed on a visible message. For example, in an image where color is encoded as a 24bit number using RGB coding (one byte per color), we may use one bit from each color to send a message. The change in the picture would be not easily detectable, and we could transmit a secret message. [In a picture with 100,000 pixels, we would have 300,000 bits, i.e. 7,500 bytes available for our secret message.]

    • DIGITAL SIGNATURES and DIGEST FUNCTIONS (Integrity)

    User A writes a document M, wants to distribute it and be sure that A does not care who or how many principals(programs/people) read the message.

    Digest Function: a function that, given a document M generates a brief "fingerprint" or "message digest" or "hash value" or "thumbprint" that identifies this document uniquely with almost certainty.

    MD5 (Rivest, 1992): A digest function that generates a 128 bit fingerprint from its text argument. It is much quicker to compute than encrypting with DES [on a 175Mhz Alpha, MD5 digest is computed at over 80Mbps]. Another often used digest function is SHA-1, which generates a 160 bit fingerprint from its text argument.

    A sends: 

    	M + E(MD5(M), Ks(A))    // Ks(A) = Secret key of A
    ['+' means concatenation, E(MD5(M), Ks(A)) is called the digital signature of the message. It is also often called a Message Authentication Code (MAC).]
    R uses the identity of A to determine the public key of A.
    R uses this public key of A to decrypt the "digital signature" of M and obtain the hash value MD5(M).
    R uses the Digest Function to compute the hash value of M.
    If the two hash values are the same, all is well. Otherwise message was corrupted or not sent by A. 
    	A  ----> M + E(MD5(M), Ks(A)) ---> B
    If in addition to authentication and integrity we also want secrecy then the message sent will be 
    	A  ----> E(M + E(MD5(M), Ks(A)), Kp(B)) ---> B
    A weakness of the use of digital signatures is that it requires knowledge of the public key of the interlocutors. The danger is impersonation - if there is no reliable way of distributing public keys. The solution, as we will see later, is to use digital certificates and certificate authorities.

    Attempts at Authentication

    Principal A wants to authenticate itself to other principals. Let Kp(A) be the public key of A, Ks(A) the secret key of A. A will append E(A_id, Ks(A)) to its messages. Any principal B that receives this information will use Kp(A) to decode the signature, if it succeeds and finds "A_id", it will "know" that only A could have sent the message. In the following we use "+" to express "concatenation". 
    		A  -->  A_id + E(A_id, Ks(A))  -->  B
    Note that this authentication, as it stands, is dangerous: somebody could capture and save that message (A_id+E(A_id,Ks(A))), and then use it to impersonate A by playing back a previous authentication message. We can solve the problem as follows: when A wants to authenticate itself to B, it asks B to send first to A a string x which is likely being sent for the first time to A (choose x at random as a 100 digits number!). Then A sends to B 
    		A_id + E(A_id + x, Ks(A))
    now nobody can have memorized the authentication message and play it back.
    Note that also this authentication is dangerous if anybody, not just B, could have sent to A the nonce x. Because then C could impersonate A in interacting with B. It gets in the middle between A and B. Waits for A to make a request to B and intercepts the communication. 
    		A  --> A_id --> C  -->  A_id  --> B       
		A  <--  x  <--  C  <--  x  <-- B
	 	A  --> E(A_id + x, Ks(A)) --> C  --> E(A_id + x, Ks(A)) --> B
    and now B believes that C is really A, while A just thinks the communication was lost. We get back to this later. This is a form of man-in-the-middle attack. Later we will see another form.

    Direct Authentication and Session Key exchange (using symmetric key)

    We want a client to authenticate its identity to the server and the server to authenticate its identity to the client. We assume that the true client and server share a secret password P from which an algorithm can compute a key K. We use the notation K(Client) and K(Server) to indicate the value of K as assumed respectively by the client and the server. We should have K = K(Client) = K(Server). [Instead of a protocol based on symmetric cryptography, we could have used a protocol based on asymmetryc cryptography.]
    1. The client sends to the server the message 
               clientId
    2. The server selects at random an integer x [it is random so that likely it was not used before] and sends to the client the message 
      	x
    3. The client uses K(Client) to encode the message received, selects at random a number y, and sends to the server the message 
      	E(x, K(client)) + y
    4. At this point, if x is retrieved, the server is certain of the identity of the client. Now the server sends to the client the message 
      	E(y, K(Client))
    5. The client uses K(Client) to decode the message. If y is retrieved, the client is certain of the identity of the server. Mutual authentication has been achieved.
    If desired at this point the server can send to the client the message 
    	E(SK, K(Server))
    where SK is the session key that the server and client can use to exchange information during this session. Note that only the specified client will be able to decode the session key. This session key will be valid only for a specified time interval. The fact that K is used only during the exchange that results in the sharing of the session key SK, makes it more difficult for an hostile party to guess K. Notice also that we have shown the case of the server giving to the client the session key. The viceversa, with the client selecting the session key and giving it to the server is also possible.
    We are combining in this way the security of secret key cryptography (now used efficiently because only for little data) with the efficiency of public key cryptography (now used securely because only for one session).

    The values x and y are usually called nonces. They are just computed random numbers. As already observed, they are used so that an intruder cannot imitate an interlocutor by just remembering what that interlocutor returned in another occasion.

    Reflection Attack: A case of bad Authentication (using symmetric key)

    Here is an example of how easy it is to come up with bad security protocols. We are still using secret keys as in the last protocol. In the following x, y, and z are nonces.
    1. client ---> clientId + x ---> server
    2. client < -- E(x, K(server)) + y < -- server
      The client decripts the E(x, K(server)) term using the secret key K(client) = K(server). If it obtains x, it knows that the server is who it is supposed to be.
    3. client ---> E(y, K(client)) ---> server
      The server decripts the E(y, K(client)) term using the secret key K(server) = K(client). If it obtains y, it knows that the client is who it is supposed to be.
    This "Authentication Protocol" is bad in that it can be fooled with a Reflection Attack, as shown in the following modification:
    1. client ---> clientId + x ---> server
    2. client < -- E(x, K(server)) + y < -- server
    3. client < -- serverId + y < -- hostile
    4. client ---> E(y, K(client)) + z ---> hostile
    5. hostile ---> E(y, K(client)) ---> server
      The server decripts the E(y, K(client)) term using the server's secret key K(server) = K(client). It optains y, thus it knows that the client is who it is supposed to be, yet we know that it is really "hostile".

    Direct exchanges of public keys: Man-in-the-Middle Attack

    Alice and Bob are friends and want to communicate with absolute secrecy. They agree to exchange, say by email, public keys while authenticating each other. At the time that the public keys are exchanged a malicious third-party, Mallory does the following: 
      Alice --> Alice_id --> Mallory --> Alice_id --> Bob
                         Mallory <-- x <-- Bob
			 Mallory --> E(x, Ks(Mallory)) --> Bob
                         Mallory <-- send me your public key <-- Bob
                         Mallory --> Public_key_of_Mallory --> Bob 
                                       Bob now thinks Mallory is Alice since
				       it can decrypt E(x,Ks(Mallory))
  Alice   <--    x  <--  Mallory
  Alice --> E(x, Ks(Alice)) --> Mallory
  Alice <-- Send me your public key <--  Mallory
  Alice --> Public_key_of_Alice --> Mallory
          Now Alice has authenticated herself to Mallory.
  Alice  <-- Bob_id <-- Mallory
  Alice  --> y -->  Mallory
  Alice  <-- E(y, Ks(Mallory)) <-- Mallory
  Alice --> Send me your public key --> Mallory
  Alice <-- Public_key_of_Mallory <-- Mallory
    Alice now thinks that Mallory is bob since it
    can decrypt E(y,Ks(Mallory))
          When Bob sends data d to Alice it sends
		E(d, Public_key_of_Mallory)
          Mallory decrypts and sends to Alice
		E(d, Public_key_of_Alice)
          and similarly in the opposite direction.
    From this moment on everything exchanged by Alice and Bob gets interpreted by Mallory even if encrypted. Clearly the idea of exchanging naively public keys is no good. Some certified way of exchanging public keys is required, a public-key infrastructure.

    Authentication Server and Distribution of Session Key

    Here is an Authentication protocol (modified from a protocol by Needham - Schroeder, and related to Kerberos) used when there is an Authentication Authority S that generates session keys for interaction between two interlocutors A and B. It is carried out when a Client A wants to communicate with a server B. It is assumed that the authentication server and A share a secret key K(A) and the authentication server and B share a secret key K(B). Usually these secret keys are computed from userid, password pairs.
    1. A sends to S the cleartext message 
      	A + B
      to mean that A wants to interact with B.
    2. S generates a timestamp T, a duration L (Lifetime), and a session key K and sends to A the message: 
      	E(T + L + K + B, K(A)) + E(T + L + K + A, K(B))
    3. Now A uses its key K(A) to obtain the session key K, plus T and L; it then sends to B the message 
      	E(T + L + K + A, K(B)) + E(A + T, K)
    4. B uses K(B) to determine T, L, K and A. The E(A + T, K) part is necessary to authenticate that the message is really from A (only A can have obtained the session key K, as demonstrated by the A+T value) and not from somebody that eavesdropped the conversion between S and A and obtained the E(T + L + K + A, K(B)) part. For this reason the E(A+T,K) part is called an authenticator. Now also B has the session key K, plus T and L, and knows that it can interact with A. It does so by sending to A the message 
      	E(T+1, K)
      to indicate that B is ready. This authenticates B to A since only B has the session key K, as demonstrated by T+1.

    More About Digital Certificates, Certificate Authorities, and SSL

    As already indicated, a digital certificate is associated with an internet interlocutor to make secure its interactions with other interlocutors. At a minimum a digital certificate will include: In addition it may contain also the owner's address, e-mail address, phone, etc. The certificate is encoded by the issuing certificate authority using its private key so that the content of the certificate cannot be tampered with without detection. Here is how the certificate works. The sender requests the certificate of the recipient from the CA. This certificate is encrypted with the CA's secret key and contains the recipients's public key and additional information. The sender decodes the certificate with the public key of the CA and encodes the message with the retrieved public key of the receiver. The standard for Digital Certificates is X.509.]
    A message M can be sent as follows: 
    	M + DigitalSignatureOfM + DigitalCertificateOfSender
    and, if the certification authority is reliable, we are guaranteed authentication and non-tampering. Thus digital certificates can be used in place of passwords to identify principals. If in addition to authentication and integrity we want secrecy, it is easy to do since the DigitalCertificateOfSender contains the Public_key_Of_Sender. Thus we send 
      E(M+DigitalSignatureOfM, Public_key_Of_Sender) +
	DigitalCertificateOfSender

    A Certificate Authority, in addition to issuing certificates, will be concerned with renewing (i.e. extend the duration), and revoking (i.e. terminating the validity) existing certificates. A Certificate Authority cannot appear as a single server to which all users make appeal. Instead, as in the case of DSN (Distributed Name Service) one needs a distributed structure of communicating certificate authorities. At present there are a number of competing certificate authority services and a server used in e-commerce will have to keep certificates for the certification services it trusts. Front ends to certificate authorities are often called Registration Authorities.

    SSL, the Secure Socket Layer, acts as an intermediate layer between the application protocol, say HTTP, and the transport protocol, say TCP. SSL has two subprotocols. One specifies the format of the messages exchanged. The other specifies the handshakes taking place between clients and servers. The protocol allows the selection of the cryptographic algorithm used. It always requires authentication of the server. Authentication of the client is optional. [Server authentication is almost always crucial - think of client having to give to server its own visa card number. Client authentication is rarer - necessary, for instance, if client asks for bank balance; not necessary if client asks for today's weather. In the case that the client gives a credit card number, the application using SSL will have other methods to make sure that the client is who it claims to be.]

    In their SSL interactions interlocutors use digital signatures, digital certificates, and rely on certificate authorities. They use random numbers (nonces) to eliminate the possibility of hostile interlocutors remembering old interactions. Communications between client and server are encrypted. Public key cryptography is used only during session setup: the client, usually a browser, selects a secret symmetric session key, encrypts it with the public key of the server, and sends it to the server. Afterwards client and server communicate with the selected secret session key.
    SSL has been modified into an Internet standard, the Transport Layer Security (TLS) protocol, as expressed in RFC 2246