Abdulrahman AlQallaf

Decluttering my mind into the web ...








Week 2 — Building Blocks: Random Numbers, Hash Functions, Encryption


Contents:

Week 2 Live Event

Section 1: Random Numbers
---- Video 01: Introduction to Random Numbers
---- Video 02: Pseudo Random Numbers
---- Video 03: Cryptographically Secure Random Numbers (CSPRN) and CSPRN Generators (CSPRNG)

Section 2: Hash Functions
---- Video 04: Hash Functions and Properties
---- Video 05: Cryptographic Hashes
---- Video 06: Standard Hash Functions (MD-5 and SHA)

Section 3: Encryption Algorithms
---- Video 07: OTP - One Time Pad – Unconditionally Secure Cipher
---- Video 08: DES – Digital Encryption Standard
---- Video 09: AES – Advanced Encryption System
---- Video 10: RC4 – Rivest Cipher Version 4
---- Video 11: RSA - Public Key Encryption

Section 4: Birthday Attacks on Hash Functions
---- Video 12: Birthday Paradox
---- Video 13: Constructing and Preventing Birthday Attacks






Week 2 Live Event













































Section 1: Random Numbers






Video 01: Introduction to Random Numbers



  • Used to get keys.
  • Also called nonces (challenge/response).
  • Best way to generate them is through nature.


Method for generating random numbers: linear congruence generator



  • Passes statistical tests.
  • Not good enough to be used in crypto.



Different types of randomness:

  • Statistical.
  • Crypto secure.







Video 02: Pseudo Random Numbers





Statistical tests for randomness:

  • Frequency – tests frequency of numbers generated.
  • Serial – do a frequency test for a pair of numbers.
  • Poker – same as serial, but choose 5 numbers.
  • Gap – choose one number, check distance.


CSPRNG (Crypto Secure Psudo Random Number Generator)

  • They work the same as a PRNG.
  • They pass the:
    • Prediction/next bit test.
    • State compromise test – by knowing the current machine state, you can generate the next, but not the previous.





Video 03: Cryptographically Secure Random Numbers (CSPRN) and CSPRN Generators (CSPRNG)



Cypto secure:

  • Very unpredictable.
  • Indistinguisable from real random numbers.
  • Pass the NBT (i.e., not possible with > 50% probability).
  • Pass the state compromise test.


How to build CSPRNG?

  • Use physical randomness (at least as a seed).
  • Math (very slow, one bit at a time, also requires a seed).




  • Crypto algorithms (encryption/hash functions)





Note: does not pass the state compromise test, requires other things as well such as hash chaining.



What is the standard CSPRNG?

  • There isn’t any.
  • But there is a document (NIST 800-90A):s
    • HASH DRBG (deterministic random bit generator) – use hash function in counter mode
    • HAMC DRBG (hash message authentication codes).


















Section 2: Hash Functions






Video 04: Hash Functions and Properties




  • Almost impossible to find a collision.
  • Impossible to reverse.


Notes:

  • Impossible to prove that a one way function exist.
  • This doesn’t mean however that one does not exist.



Names for crypto hashes:

  • Secure hash
  • Collision resistant
  • Collision free





Video 05: Cryptographic Hashes



  • We can use crypto algorithms for generating hashes.
  • However, we don’t because sometimes they might produce unforseen weaknesses.

Note: There is no single way to build hash functions.



There is the Merkle Damgard Construction/Compression:

  • A method of building collision-resistant cryptographic hash functions from collision-resistant one-way compression functions.
  • Used in MD5 and SHA (SHA is a family of algorithms).








Video 06: Standard Hash Functions (MD-5 and SHA)



Finding problems in hashes:



MD5:

  • Message digest 5.
  • 128 bit hash function.
  • Ronald Rivest, 1993.
  • Weaknesses discovered, starting 2010.












SHA1:

Good YouTube video: SHA: Secure Hashing Algorithm - Computerphile









SHA3:




















Section 3: Encryption Algorithms






Good YouTube video: Almost All Web Encryption Works Like This (SP Networks) - Computerphile

Lecture Video Guide


OTP - One Time Pad – Unconditionally Secure Cipher: The best and (provably unconditionally secure) encryption algorithm is One Time Pad. In this lecture, we discuss why it is so secure–and why it is impractical to use.

DES – Digital Encryption Standard: Digital Encryption Standard, or DES, is the first open encryption standard. It is interesting, intriguing and not breakable. This lecture provides some insight into the circumstances that led to its creation before taking a deep dive into how it works.

AES – Advanced Encryption System: Advanced Encryption System, or AES, is a modern cipher that is widely used in all encryption applications today. The inner workings of this system are presented in this lecture.

RC4 – Rivest Cipher Version 4: Unlinke DES and AES, Rivest Cipher Version 4, or RC4 is a stream cipher. This lecture presents the complete details of how it works. Despite its elegant design, several weaknesses in RC4 were found, and it is no longer in use.

RSA - Public Key Encryption: RSA (named for its inventors, Rivest-Shamir-Adleman) is a widely-used public key (asymmetric key) algorithm. The algorithm, its background, and internal properties are discussed in this lecture.





Video 07: OTP - One Time Pad – Unconditionally Secure Cipher





Issues?

  • Key transmission is an issue
  • Key needs to be brand new every time
  • If key is reused then we run into the following issue (the ‘+’ is an ‘xor’):




  • Also, if you have PT and CT, then you can figure out the key used.



Why does it work?

  • If you assume that you have the key and decrypt, how do you know that you have ended up with the PT intended?





Video 08: DES – Digital Encryption Standard



  • Never broken, but outlived its usefulness (computer became faster)


Differential cryptanalsis: A technique for finding minor weaknesses in ciphers.


How does DES work?















Note: AES is faster than DES, that is why we don’t use a multiple of DES.







Video 09: AES – Advanced Encryption System



Good YouTube video: AES Explained (Advanced Encryption Standard) - Computerphile

Hi Everyone,

In week 2 video on AES (here), around 1:22 it is said that “Unlike DES, AES does not use a permutation substitution network.”, it should be changed to: “Unlike DES, AES does not use a Feistel network.”. In summary, AES uses permutation substitution network and DES uses Feistel network.

Around 2:25, it is said that the numbers in the 4*4 matrix are “16 bit long”. This is also stated in the text inside the slide in the video (“16 bit per entry”). However, each number in matrix is a 1 byte or 8 bit long, which makes the block consisting of 16 numbers to be 128 bit long.























Video 10: RC4 – Rivest Cipher Version 4



















Video 11: RSA - Public Key Encryption
































Section 4: Birthday Attacks on Hash Functions






Lecture Video Guide


Birthday Paradox: If there are twenty-three people in a room, the chances of two people sharing the same birthday is over 50%. This fact is not a paradox, but a problem. This video explains what the birthday paradox is and what its existence implies in hash collisions.

Construction Birthday Attacks: The birthday problem can be used to innovatively attack hash functions. There are some best practices used to avoid any chance of using the birthday attack on a cryptosystem. This lecture details how the attacks can be carried out, as well as a strategy for mitigating the risk of birthday attacks.





Video 12: Birthday Paradox



Birthday Paradox: If there are twenty-three people in a room, the chances of two people sharing the same birthday is over 50%. This fact is not a paradox, but a problem.

  • using the pigeonhole principle, we will need 366 people instead.



This is not the birthday paradox:



This is the birthday paradox:











Video 13: Constructing and Preventing Birthday Attacks