My experience from the Cryptography course. Pictures are captured from the lecture slides. For my own review, I summarize the course at the bottom.
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.
- 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.
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?
- Symmetric Ciphers : E, D use the same key K.
- E is often randomized, D is always deterministic.
- 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 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.
- Advance Encryption Standard (AES)
- CBC with random IV
- CBC with nonce : key nonce pair used only once.
- 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
- 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.
- PMAC : PRF. Incremental, not sequential like CBC MAC.
- 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.
- H(m0) = H(m1) and m0 <> m1
- 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.