Category Archives: Cryptography

My Understanding 1 – TLS (SSL)

After I took the Cryptography course, I started to read more things about the security on the Web. Some of the concepts are now more clear than before because of general understanding of Cryptography. Thanks to the course! I will try to summarize my understanding of several topics in the security.

Transport Layer Security (TLS) / Secure Socket Layer (SSL)

TLS/SSL provide a secure channel between two points using Asymmetric and Symmetric encryption. Just using symmetric cipher only faces the challenge of securely delivering the shared key. For this reason, both asymmetric and symmetric encryption is used.

A secure channel provides message integrity between two points. Before establishing a secure channel, SSL Handshake needs to be happened. This post is to explain how the SSL Handshake works. The Client can be translated as client’s browser and server will be Web Server.

Below scenario doesn’t require a Server to authenticate Client’s Certificate. If Server requires mandatory Client’s Certificate validation, it will happen after Step 4.  If Client doesn’t have a Certificate, the handshake will stop. I added some symbols for me to remember and understand the process better.

1. Client sends a message to the server. The message contains a list of algorithm that client can support, client’s date and time (4 bytes), and a random number (28 bytes), which will be used later to generate the server random value (PreMasterSecret).

2. Server sends a message to the client. The message contains the algorithm to be used from the list, server’s date and time (4 bytes), and a random number (28 bytes), which also will be used later to generate the client random value (PreMasterSecret).

3. Server also sends a Certificate to client.

4. Client authenticate the Server’s Certificate by going through below steps. Any failure in the steps will stop the handshake.

  • Is Certificate expired?
  • Is CA trusted CA?
  • Is public key validate issuer’s digital signature?
  • Does domain name match? This will prevent the “Man in the middle” attack.

5. Client generates a random value (PreMasterSecret) and encrypt with Server’s public key.

  • G() = Xp
  • E(PKs, Xp) = Cc

6. Server decrypts the random value (PreMasterSecret) using its private key.

  • D(SKs, Cc) = Xp

7. Client and Server use the 28 bytes random number and PreMasterSecret value to generate the Master Secret key.

  • X  is generated.

8. Client sends “Finished” message with Hash and MAC for a message integrity.

9. Server attempt to decrypt “Finished” message and verify the Hash and MAC. If decryption or verification failed, handshake will stop.

10. Server does the same thing by sending “Finished” message with Hash and MAC.

11. Client performs the same decryption and verification.

12. Handshake is done and further message exchange will be encrypted using the Master Secret key.

Diagram from IBM

Numbers don’t match above. Diagram is to show the steps visually.

sy10660a

Summary

TLS/SSL handshake requires many steps from both sides. Key thing is that SSL uses both asymmetric (PK, SK) and symmetric (X – master key) to exchange the Certificate (PK) each other and to encrypt messages after secure channel is established. Next posting, I’d like to summarize the Digital Certificate and different type of attacks on the Web.

Stanford Free Cryptography online course experience

My experience from the Cryptography course. Pictures are captured from the lecture slides. For my own review, I summarize the course at the bottom.

Certificate

MichaelJo_certificate

Experience

After week 2 post, I had a several occasions that I almost gave up on the course – dealing with a pressure from the project deadline, home repair, and family commitment. I can say the course played a significant role keeping me focused during the difficult time. The course experience was totally different from what I expected before taking it. I thought it was a general cryptography introduction course for non-technical people.  It turned out that it was not for anyone. This course required a BIG commitment. Personally, the week 5 was the hardest. It has been almost two decades that I’ve done anything with mathematics theory. Week 5 part 2 concept was hard – I had to digest lots of concept and examples in the lecture. I knew I can’t perform well in the quiz without understanding the concept. I had to repeat the lecture many times and try to really understand the concept – even that, certain topic was really hard to digest. Concept built on top of the concept, so I had to understand the concept 100% before moving on to next concept in the Week 5.  The Week 5 quiz took me the longest time and the quiz itself had the most questions.

The Forum helped me a lot. Even though I didn’t post any questions, someone had the same trouble that I had. Sometimes, I didn’t even understand what the question was in the quiz. Somebody else faced the same trouble and posted the questions and hints. I’ve seen so many smart people in the forum and I was just amazed. Because the quiz gives you 4 chances, most of the times, I can pass over 80% after 4th attempt.

Overall, my experience from this course was great. The professor, Dan Boneh, was great and you can tell how good and smart he is. I didn’t try any of the programming assignment, which are for the extra credit. Simply, I just couldn’t find the time.

Even though I was struggling throughout the course, I managed to pull it through and got over 90% on my final exam. The question lies how and what I can apply in the real world from the course experience.

Application

  • I can distinguish symmetric and asymmetric encryption.
    • Symmetric ciphers are bulk data encryption. Faster than asymmetric encryption.
    • Asymmetric encryption solves the key distribution problem by using very difficult mathematical problems.
    • I had an idea how x.509 works underneath – asymmetric encryption using the ElGamal instead of RSA trapdoor.
    • Asymmetric ciphers are used to transfer session keys for symmetric ciphers.
    • Data encrypted with a symmetric cipher, but send the key encrypted with an asymmetric cipher.
    • Asymmetric ciphers are used for digital signatures.
  • Overall, I have better understanding in the Security and Encryption.

Conclusion

I accomplished what I wanted to do. Certainly, it requires time and effort, especially commitment. At this time, I don’t have a plan to take the Cryptography 2, but I am going to take different courses in February : Algorithm 1 (Princeton from Coursera), HTML 5 Gaming Development (Udacity). I will be challenged again, but they are FREE after all. So why not?

Summary

Introduction

  • Symmetric Ciphers : E, D use the same key K.
  • E is often randomized, D is always deterministic.

Stream Cipher

  • One Time Pad : K is the same size of M. Uses XOR.
  • Perfect Secrecy : |K| >= |M|. Hard to use in practice.
  • Pseudorandom Generator (PRG) : Replace random key by “pseudorandom” key to make OTP practical. This will make Stream Ciphers.
  • Stream Cipher doesn’t have perfect secrecy because key is shorter than message.
  • PRG must not be predictable. Unpredictable PRG is secure.
  • Never use stream cipher key more than once. Two time pad is insecure.
  • Integrity attack can happen because modifications to ciphertext are undetected and have predictable impact on plaintext.
  • Secure cipher defines :
    • Attacker can’t recover secret key
    • Attacker can’t recover all of plaintext
    • Cipher Text should reveal no “info” about plaintext.
    • Stream ciphers are semantically secure.

Block Ciphers

  • Block ciphers built by iteration.
  • Pseudorandom Permutation (PRP) : Deterministic algorithm to evaluate E(k,x) and inversion exists. E : K x X -> X. PRP is also PRF where X=Y and invertible.
  • Pseudorandom Function(PRF) : Algorithm to evaluate F(k, x). F : K x X -> Y
  • Data Encryption Standard (DES) : Invertible functions.

DES

  • Advance Encryption Standard (AES)

AES1

AES2

  • CBC with random IV

CBC1

  • CBC with nonce : key nonce pair used only once.

CBC2

  • Attacks on the implementation
    • Side channel attack : measure time and power consumption
    • Fault attack
    • Quantum attack
    • AES block cipher : Byte Sub, Shift Row, Mix Column

MAC

  • Attach tag to verify the message for integrity.
  • CBC MAC : padding with 0s. PRF
  • NMAC : Nested MAC with fpad. Not used with AES or 3DES. Basis for HMAC. PRF
  • ECBC-MAC : AES based MAC. Add dummy block starting with “1” with following zeros. There are variant of CBC MAC without padding block.

ECBCMAC

  • PMAC : PRF. Incremental, not sequential like CBC MAC.

PMAC

  • HMAC : Hash MAC. MAC from SHA-256. Most widely used MAC on the internet. Similar to NMAC PRF. Main difference is k1, k2 are dependent.

HMAC

Collision Resistance

  • H(m0) = H(m1) and m0 <> m1

Authenticated Encryption

  • Semantically secure under CPA and cipertext integrity.
  • Deterministic CPA security : Security if never encrypt same message twice using same key.
  • Format Preserving Encryption (FPE) : Credit card.

Basic Key Exchange

  • Trusted Third Party : Reduce number of keys to manage.
  • Toy Protocol : E(ka, “A, B” || Kab) ; E(Kb, “A,B” || Kab)
  • Merkle Puzzles : 2^32 puzzle along with it and obtain key upon solving the puzzle.
  • Diffie-Hellman Protocol : A <- g^a (mod p), B<- g^b(mod p). kab = g^ab
  • DH still insecure against man-in-the-middle attack.
  • Public Key encryption : G, E, D. G() generate pk, sk. Establish a shared secret.

Public Key Encryption from trapdoor permutations

  • Secure symmetric cipher provides authenticated encryption. Attacker can not create new ciphertexts.
  • Public key settings : Attacker can create ciphertexts using pk, chosen ciphertext security is required.
  • Secure Trapdoor Function : one-way function. Can’t be inverted without sk.
  • RSA Trapdoor permutation.  ISO standard.
  • PKCS1 mode 2. PKCS1 v1.5. Used in HTTPS.
  • PKCS1 v.2.0 : OAEP. Use SHA-256 for H and G.

ElGamal public key system

  • Escrow Service. Data recovery with third party key.
  • Used in GPG.
  • Public key encryption made possible by one-way functions with special properties.

Stanford Free Cryptography online course – week 2 experience

Struggle

I am taking Free Stanford Online “Introduction to Cryptography par 1” course (6 weeks duration). I came across this course from other blogger’s site. Today was the end of week 2. So far my experience with the course has been very challenging. The concept is not too difficult to understand, but the theory, because cryptography is based on the mathematics and statistics, is explained in mathematics and statistics symbols, which I haven’t paid attention quite some time and those blew away in week 1.  Even though video lectures don’t take more than 4 hours/week, I still have to rewind many times because professor is going really fast and assuming students know the basics.

In week 1, I just dived into the video lecture right away and was surprised to see the lecture style was like the university classroom, not like public continuing online course style – definitely not for everyone. Without any prerequisite, I thought it wasn’t going to be hard, but I found myself still struggling in week 2. Just spent great amount of time on Saturday to figure out the week 1 quiz and didn’t get the satisfying score. I have 3 more times to try and improve my score on quiz 1, so I will try again this week.

Learning

One thing I realized today was that I wasn’t applying any of the MMOST techniques. Maybe because it is a video lecture and not a book, so I couldn’t skim through the topics and couldn’t exercise the “Hooks” to capture the main concept. Maybe I thought I was in a hurry and wanted to get the concept down quickly. Regardless, I learned that I wasn’t well prepared for this course.  Today, after second half of week 2 lectures, I found the better way of taking the lecture. I previewed the PPT slides and listened the lecture afterward. This actually reduced the overall studying time. I didn’t have to rewind video lecture as much as I did in week 1.

Resources

People from the forum made my eyes open to the “Free Learning”. So far, my learning resource has been limited to online resources, books, and classroom courses. However, I learned other good quality learning opportunities are available online. I’d like to share these resources.

Commitment

I feel keeping up with my commitment is important. Especially something that I wanted and decided to do. I will share my experience again after I complete this course.