Introduction to Network Security – Part 11

NOTIFICATION: These examples are provided for educational purposes. The use of this code and/or information is under your own responsibility and risk. The information and/or code is given ‘as is’. I do not take responsibilities of how they are used. You are welcome to point out any mistakes in my posting and/or leave a comment.

Key Distribution Using Public-Key Cryptography

In the previous post, introduction to network security – part 10, we saw three main methods of public-key:

  1. Public announcement,
  2. Public-key authority, and
  3. Public-key certificates

These methods can be used for encryption and decryption of messages (secrecy) and/or authentication.

These methods the disadvantage of being slow; therefore, its common to use symmetric-key encryption for secrecy and distribute using public-key encryption session keys. In this way we use the advantage of the speed of symmetric-key encryption and the security of public-key encryption.

Simple Key Distribution

In 1979,  Ralph C. Merkle created his thesis entitled “Secrecy, authentication and public key systems” which let him receive his Ph. D. in Electrical Engineering at Stanford University <http://en.wikipedia.org/wiki/Ralph_Merkle>.

For a key distribution, Merkle proposed:

  1. User A will generate a new temporaty public key pair, PUa
  2. User A send the public key, PUa, to user B together with its identity, IDa
    PUa, IDa
  3. User B generate the session key K.
  4. User B uses the public key, PUa, supplied by user A to encrypt the session key K. Then user B send the encrypted session to user A
  5. User A decrypt the message to obtain the session key K.
  6. User A discards the public key PUa
  7. User B discards user A’s public key, PUa.
  8. After the exchange of information is complete, user A and B discard the session key K.

The Man-In-The-Middle Attack

This type of key distribution have a disadvantage.  Lets assume that we have an attacker that gets in the middle of the communication in a way that this attacker can intercept the messages and then replay this message, modify this message, or send another different message.

Lets analyse this problem:

  1. User A send a message to user B which holds the public key PUa, and user A’s identifier IDa
  2. The attacker T intercept this message and create its own pair keys, public key PUt and private key PRt:
    {PUt, PRt}

  3. The attacker T send to user B, its own public key PUt together with the user A’s identification IDa :
    PUt||IDa
  4. User B generate a session key Ks. Then user B send this session key Ks encrypted using the public-key PUt that he received thinking that it came from user A.
    Ciphertext = E(PUt, Ks)
  5. The attacker T intercept the message obtaining the session key Ks by decrypting the message with his private key PRt.
    Ks = D(PRt, Ciphertext) = D(PRt, E(PUt, Ks))
  6. Then attacker T send the key session Ks to the user A using user A’s public key PUa
  7. Without user A and B knowing, the attacket T obtained the session Ks successfully.

Solution to The Man-In-The-Middle Attack

  1. The process begins with user A. User A encrypt the message containing the user A identification IDa plus a nonce N1 using the user B’s public key PUb
  2. User B generate a new nonce N2 and encrypts the message containing user A’s nonce N1 plus a new nonce N2 using the user A’s public key.
  3. Since user B is the only one that could decrypted the first message coming from user A plus the new message send from user B to user A will contain the nonce N1 (given by  user A in the first message), user A will know the new message is coming from user B and not an attacker.
  4. User A will encrypt nonce N2 using the public key PUb of user B. Then user A will send then encrypted nonce N2 to user B. In this way, since nonce N2 was generated by user B, when user B find nonce N2, user B will known the message came from user A.
  5. User A generate a secret key Ks. User A will encrypt first the secret key Ks using the private key PUa of user A which would provide authentication, and then it will encrypt the output of the encryption with the public key PUb of user B to produce a new ciphertext M which provide confidentiality.
  6. User B decrypt the ciphertext M by decrypting the ciphertext M using the private key PUb of userB, and the result will be decrypted again using the public key PUa of user A. In this way the secret key Ks is obtained.

Hybrid Key Distribution

Public key encryption is an algorithm that require a lot of processing. In a system that require to distribute session keys thought many users and require a frequently change of session keys, the public key encryption can slow the performance of the system as the load on the system keep increasing. One solution to this problem is to use an hybrid of different key distribution.

In an hybrid key distribution, the key distribution center (KDC) will be in charge of distributing a master key MK to each user of the system plus perform the distribution of session keys. Before these session keys are distributed, they will be encrypted by using the master key MK. Also, the master key is encrypted using a public key encryption. Since the master key only update in few occasions then the load of the system is reduced.

Share

Introduction to Network Security – Part 5

NOTIFICATION: These examples are provided for educational purposes. The use of this code and/or information is under your own responsibility and risk. The information and/or code is given ‘as is’. I do not take responsibilities of how they are used.

Symmetric Encryption

In the symmetric encryption, the same key (normally a single-key) is used to perform the encryption and decryption of the ciphertext.

Symmetric Cipher Model: This model is performed by performing transformations and substitutions on the plaintext. A secret key, independent from the plaintext and the algorithm, is used to cipher the plaintext. After, the ciphertext plus the secret key is used with the decryption algorithm to obtain the original plaintext.

Symmetric Encryption is the opposite to the concept of public key distribution which will be explained in future postings.

Requirements:

  1. The cipher model must be mathematical expression:
    (E: Encryption, D: Decryption, X: plaintext, Y: ciphertext, K: secret key)

    Y = E(K, X)
    X = D(K, Y)
    
  2. Assumption that the encryption algorithm is known to the attacker.
  3. A strong encryption algorithm which in case the attacker would obtain or know some examples of the ciphertext and the plaintext produced from the ciphertext, the attacker would still be not able to obtain the key. This means that if the attacker would obtain the ciphertext, the attacker would not be able to obtain the secret key or the plain text.
  4. Secret key should be known only by the sender and the receiver of the ciphertext.
  5. The distribution of the secret key must be done in a secure fashion. For example, the use of a third party that would generate and provide in a secure way the key to the sender and the receiver.

Substitution Ciphers

In classical substitution ciphers, all the letters in the plaintext will be replaced by another letter, number, and/or symbol.

Caesar Cipher

History explains that Julius Caesar <http://www.roman-empire.net/republic/caesar-index.html> came up with a substitution cipher that he used in his campaigns for military affairs.

The cipher works in the following way:

  1. We use the alphabet of 26 letters:
    
    
  2. Under this alphabet, we will rewrite the alphabet by picking a letter as a starting point.
    Lets say our key indicate the starting point such as K = 4 so we begin with the letter ‘E’ then:
  3. This means that if we wish to send a plaintext (P) that says HELLO, the ciphertext (C) would be LIPPS, and the key (K) would be 4
  4. The mathematical way to represent this cipher will be the follows:
    1. Give each letter of the alphabet a number:
      A = 1, B = 2, C = 3, D = 4, E = 5,F = 6, G = 7, H = 8, J = 9, K = 10, L = 11, M = 12, N = 13, O = 14,P = 15, Q = 16, R = 17, S = 18, T = 19, U = 20, V = 21, W = 22, X = 23, Y = 24, Z = 25.
    2. Encryption Algorithm:
      E: Encryption, Ct: Ciphertext, Pt: Plaintext, K: secret key

      Ct = E(Pt)
         = (Pt + K) mod 26
    3. Decryption Algorithm:
      D: Decryptor, Ct: Ciphertext, Pt: Plaintext, K: secret key

      Pt = D(Ct)
         = (26 + (Ct - K)) mod 26
  5. The weakness of this cipher is that it can be broken by brute force. We just need to test the 25 combinations of different keys  until we find the key that reveals the message.

Monoalphabetic Cipher

The mono-alphabetic cipher instead of shifting the alphabet a number of letters, its substitute each letter arbitrarily by mapping the plaintext letter map to a random arranged ciphertext. The only requirement for the ciphertext is that the letters must not be repeated.

Since we are using 26 letters of the alphabet the arrangement of the cipher can permute a total of 26! permutations.

If we wish to encode the word “HELLO”, we would obtain “NERRS”

Lets assume we wish to cipher a plaintext:

Plaintext = “THIS IS A SECRET MESSAGE ENCODED IN MONOALPHABETIC”

Ciphertext = “XNMW MW E WIGBIX OIWWEJI IPGSCIC MP OSPSERUEDIXMG”

The following website let you play a little with monoalphabetic cipher by randomizing for you the ciphertext:
<http://www.simonsingh.net/The_Black_Chamber/generalsubstitutionWithMenu.html>

The only problem is that this cipher can be exploited by doing regularities analysis over the frequency of the letters. Base on the language rules some letters are used more than others. For example, in English, the letter ‘E’ is the most common used in words, followed by A, I, O, N, R, S, T. Others letters such as K, J, Q, X, Z are less used than the rest.

The largest is the message, the most chances that the attacker can decrypt the message.
Just in this message “XNMW MW E WIGBIX OIWWEJI IPGSCIC MP OSPSERUEDIXMG” we have:

  • W = 6 letters
  • E = 4 letters
  • M = 4 letters
  • S = 3 letters
  • P = 2 letters
  • ….

And continue counting.

As you may notice the letter ‘W’ of the encrypted message have the most counts, so we could  assume that this is the letter E of the plaintext.

If you are interested to know the frequency of letters in English you can go to the following website:
<http://www.cryptograms.org/letter-frequencies.php>

For more information about attacking mono-alphabetic cipher, there is a good example on this website:
<http://unsecure.co.uk/attackingmonoalphabeticciphers.asp>

Playfair Cipher

Playfair is one way to improve the security of mono-alphabetic cipher by encrypting multiple letters.

Playfair Encryption

  1. Create a playfair key matrix:
    1. Create a matrix of letters based on a keyword. For this example, the matrix should be 5 by 5
    2. Fill in the letters of the keyword from left to right and from top to bottom. Make sure that there are not duplicate letters
    3. Fill the rest of the matrix with the other letters that are not in the keyboard, making sure to not duplicate letters.
    4. As a rule, the letter I and J count as one letter.
      • I am not sure the reason for this rule, except the following:
        • First, it make it harder to decrypt the message since one letter is missing.
        • Second, in some languages, the J and I would have the same pronunciation.
          For example, my last name Carlstein was originally written as Karlštejn.
      • In case you know the real reason, please let me know and give me a reference to verify (thanks).
    5. Example of playfair key matrix:
      1. Let use the keyword: “EDUCATOR”
      2. The table should looks like this:
      3. Notice that I and J are counted as one letter
  2. The next step is to encrypt the plaintext taking two letters at the time.
    1. In case a two letters are the same (repeated), we must insert a filler letter (use the letter X as the filler). For example:
      HELLO → HE LX LO
    2. In case two letters are in the same row, replace each letter with the letter to the right. In case the letter is at the last column, pick the letter of the first row (the table is considerate to be circular). For example, lets say we have the letters D and A:

      1. D → U and A → E
      2. Therefore DA became UE
    3. In case two letters are in the same column, replace each letter with the letter below. In case the letter is at the last row, pick the letter of the first row (the table is considerate to be circular). For example, lets say we have the letters T and V:

      1. T → G and V → E
      2. Therefore TV became GE
    4. In case two letter are in different row and column, the first letter will be replaced with another letter of the same row on the column of the second letter. The second letter will be replaced with another letter of the same row on the column of the first letter. For example lets say we have the letters O and Q:

      1. To replace the letter O:
        1. This means that O → B
      2. To replace the letter Q:
        1. This means that Q → N
      3. Therefore OQ became BN

Playfair Decryption:

  1. Decrypt two letters at a time:
    1. In case two letters are in the same row, replace each letter with the letter to the left. In case the letter is at the last column, pick the letter of the first row (the table is considerate to be circular). For example, lets say we have the letters U and E:

      1. U → D and E → A
      2. Therefore UE became DA
    2. In case two letters are in the same column, replace each letter with the letter above. In case the letter is at the last row, pick the letter of the first row (the table is considerate to be circular). For example, lets say we have the letters G and E:

      1. G → T and E → V
      2. Therefore GE became TV
    3. In case two letter are in different row and column, the first letter will be replaced with another letter of the same row on the column of the second letter. The second letter will be replaced with another letter of the same row on the column of the first letter. For example lets say we have the letters B and N:

      1. To replace the letter B:
        1. This means that O → B
      2. To replace the letter Q:
        1. This means that Q → N
      3. Therefore OQ became BN
  2. After you will finish with the final message. You must remove any extra X that do not make sense in the message:
    HE LX LO → HELLO
Share

Introduction to Network Security – Part 4

NOTIFICATION: These examples are provided for educational purposes. The use of this code and/or information is under your own responsibility and risk. The information and/or code is given ‘as is’. I do not take responsibilities of how they are used.

Before we begin talking about encryption, decryption, and ciphers related topic, let go over some terminologies to have in account:

  • Cipher: An algorithm used for encryption.
    Link reference: <http://www.merriam-webster.com/dictionary/cipher>
  • Ciphertext: The encrypted(coded) message.
    Link reference: <http://cryptnet.net/fdp/crypto/crypto-dict/en/crypto-dict.html>
  • Cryptanalysis: Study of the principles and methods of deciphering a ciphertext without having the required key.
    Link reference: <http://en.wikipedia.org/wiki/Cryptanalysis>
  • Cryptography: Study of the principles and methods of encryption.
    Link reference: <http://en.wikipedia.org/wiki/Cryptography>
  • Cryptology: The study of cryptanalysis and cryptography.
    Link reference: <http://www.britannica.com/EBchecked/topic/145058/cryptology>
  • Deciphering: Also known as decryption. The act of transforming a ciphertext to the original plaintext.
    Link reference: <http://www.merriam-webster.com/dictionary/deciphering>
  • Decryption: Also known as deciphering. The act of transforming a ciphertext to the original plaintext.
  • Enciphering: Also known as encryption. The act of transforming a plaintext to a ciphertext.
    Link reference: <http://www.merriam-webster.com/dictionary/enciphering>
  • Encryption: Also know as enciphering. The act of transforming a plaintext to a ciphertext.
  • Plaintext: the original message to be encrypted.
    Link reference: <http://en.wikipedia.org/wiki/Plaintext>
  • Product: stages of transposition and substitutions performed.
    Link reference: <http://www.britannica.com/EBchecked/topic/477942/product-cipher>
  • Secret key: An input required for the encryption and/or decryption algorithms.
  • Substitution: Map each element in a plain text to another element.
    Link reference: <http://substitution.webmasters.sk/>
  • Transposition: Rearrange the elements in the plaintext
    Link reference: <http://mw1.meriam-webster.com/dictionary/transposition%20cipher>

Cryptography

A cryptographic system is characterized by the use of encryption operations, number of keys used for encryption and decryption, and the way in which the plain text is processed.

Encryption Operations: In order to encrypt a plaintext to a chipertext is required to perform multiple stages of transposition and substitution, also known as product.

  • Substitution: We take each element from the plaintext and mapped them to another element
  • Transposition: We  take each element in the plaintext and rearrange its order in such a way that it differ from the original plaintext.

To perform encryption and decryption, we use a key reference. We can categorize the encryption techniques as  symmetric, single, asymmetric, double, and/or public.

The plaintext can be processed by using a method of streams or blocks:

  • Stream: The plaintext is processed as a continuous set of elements in which each element is encrypted one at a time.
  • Blocks: The plaintext is divided in a set of blocks in which each block is encrypted one at a time.

Cryptanalysis

As explained in the terminology list, Cryptanalysis is purpose of decrypt an encrypted ciphertext without the knowledge of the key used for the encryption. One way is to attack the encryption system and recover the key used for the encryption instead of recovering the plaintext from a single ciphertext.
Cryptanalysis attacks are divided in two categories:

  1. Brute-force Attack: Every combination of a possible key is tested on the chipertext until the plaintext is obtained.
  2. Cryptanalytic Attack: The use of knowing some characteristic of the original plaintext such as some used keywords, language, format, plaintext to ciphertext pairs examples, and  knowledge of the possible algorithm used to decrypt the ciphertext.

Unconditional Security

We call unconditional security when a cipher cannot be broken by using a ciphertext and the plaintext that produced the ciphertext regardless of the computational power and time available. Up to day, there are no encryption algorithm that can be unconditional secure with the exception of the one-time pad encryption algorithm <http://www.ibm.com/developerworks/library/s-pads.html> which will be explained in the following postings.

Computational Security

Base on the cost-benefit of braking a cipher, a cipher may not be broker due:

  1. The cost of braking the cipher is greater than the value of the plaintext encrypted
  2. The time required to breaking the cipher exceed the usefulness lifetime of the plaintext encrypted
  3. Depending of the complexity of the cipher, there would be a limitation of computing resources and time.

Brute Force Search

As explained before, we call brute force to try every key combination possible to decrypt the ciphertext into plaintext. Before obtaining success, the attacker must try at least 50 percent of the possible keys; therefore, the probability of success may be proportional to the size of the key.

Lets assume we wish to have to option of using:

  1. DES encoding (56-bit) <http://groups.csail.mit.edu/cag/raw/benchmark/suites/des/README.html>.
  2. Triple DES (168-bit) <http://en.wikipedia.org/wiki/Triple_DES>
  3. AES (Greater than 128 bits) <http://www.aescrypt.com/>

Depending of which encryption we use, the time required to find the right key by brute force could be:

Share