3.2 building blocks of modern crypto Flashcards
1
Q
one-way hash
A
- Discussion of building blocks of modern crypto consists of three main algorithms, one-way hash, symmetric, and asymmetric
- One way hash is called a message digest or just hash for short
- Hash functions are not actually encryption, they don’t encrypt, but they use encryption functions – their primary function is to verify integrity – bob generates a one-way hash of a document and sends it to Alice, who creates a one-way hash of the document she receives. If the hash generated by bob and Alice math, it is a 100% guarantee the documents are identifical – there was no change during transmission
- Hashing software uses a mathematical algorithm that runs against the 1s and 0s of a file – the operation results in a fixed-length string commonly referred to as a hash.
- Note that the output hash is always the same exact length from a given algorithm, regardless of the size of the input, e.g., MD5 algorithm will always generate 128 bits, no matter how large or small the data being hashed is
- You can tell at a glance that changing one letter or lower/upper case creates a “widely divergent” has meaning they are completely different
- “no matter the length of input” the output is always going to be same – means if you write hello class one time or if you write it 100 times, the hash will always be the same length
- You cannot reverse a hash, meaning you cannot take an output and replicate an input – this is due to the complex math function and the dilemma called “trapped door” once you pass the door you can’t go back
- The hash tells you no insight on the input – so that’s why many operating systems use hashes to store passwords
- The way it works is when you write your password it generates a hash, and it stores that hash, and next time you go to authenticate it generates a hash and matches it to the hash that’s stored and if it matches then you are authenticated
- Example: return to the steganography example from earlier with the embedded picture.
o A command prompt of md5 <filename> generates an MD5 hash for that file – when you create a hash for the two pictures then you can compare and see that the images are different – but it does not tell us how the images are different</filename> - Collisions: a collision in hashing means two different documents generate the exact same hash – while this is rare, it is possible to happen. Take MD5 which gives you a 128-bit dash which results in 340 undecillion possible hashes. There are more documents than that in the world, so hash collisions are inevitable. Although there were collisions previously discovered, they did not find predictable collisions (preimage attack), meaning they could not tell in advance which two documents would generate the same hash and cause the collision – if it was predictable then it would have been truly broken.
2
Q
Secure hash algorithm: SHA
A
- The U.S national institute of standards and technology (NIST) publishes the secure hash algorithm or SHA
- SHA-0 is considered flawed and no longer used
- SHA-1 is extremely common today – this algorithm always generates a 160-bit hash
- SHA-2 family, as it is called, is a collection of algorithms – the names of these tells you the length of the hash (SHA2-224, SHA2-256, SHA2-384, SHA2-512)
- SHA-3 family was approved by NIST in 2012 as is the eventual replacement for SHA-2. The hash lengths in the SHA-3 family are the same lengths available in SHA-2.
- Why did NIST approve SHA-3 when it is the same length as SHA-2 and does not solve the collision problem? Because MD5 and SHA-1, and all of SHA-2 all rely on the same fundamental math. SHA-3 algorithsma are based on different fundamental math – by having the SHA-3 family approved now, if anything happens to invalidate the fundamental math of the other algorithms, then SHA-3 is ready to go.
3
Q
two types of crypto keys - symmetric and asymmetric
A
table on page 68
4
Q
Symmetric key cryptography
- one multi-user circuit
- many 2-user circuits
- block ciphers and rounds of encryption
- general functions: stream cipher
A
- The key that encrypts must be used to decrypt
- We have shown several historical examples of this type of crypto – the vigenere cipher, the one-time pad, the code book are all examples of symmetric key crypto
- A modern crypto algorithm is a large, and very complex math formula. As an example, it might look like 123 x ____ + 456
- To complete this we have to fill in the cryptovariable with a cryptographic key –
- If we chose a number to fill the gap there, the reciepnet must use the exact same number to decrypt the information. If the recipient inputed a different number it won’t work. Protection of the key becomes paramount because everyone will know the two numbers but not the cryptovariable that they’re trying to break.
- Scenario 1: one multi-user circuit
o One key shared by many people – to encrypt all users must possess an identical key
o This means that a management authority of some kind must use their pseudo random number generator (PRNG) to generate reasonably random keys
o Secure key distribution channel must be used such as an electronic key distribution so we can get it to everyone
o The next issue is that all users on the circuit need to change their keys regularly – the more data encrypted by a skingle key, the more likely an adversary will discern patterns and break the key in a ciphertext-only attack. This key change must be coordinated across all 100 users so that everyone does it simultaneously. The coordination becomes tricky when dealing with users in multiple time zones.
o The biggest problem is the likelihood and damage of a key compromise. When one copy of a key is possessed by 1—users, it is only a matter time and one will make a mistake. Because the adversary now possesses the entire formula they can decrypt any data encrypted by that key – meaning that the compromise impacts all 100 users in our scenario - Scenario 2: Many 2-user circuits
o in this scenario, each pair of users must have a matching key pair – this can be challenging to manage across many people.
o The formula to determine the total number of keys requires is the number of users, times the number of users minus one, divided by 2:
4 users *3 = 12/2 = 6 pairs
o In addition to the large volume of keys, you also have to manage key changes across that many users. Granted, we are not trying to get 25 people to all change keys simulatnously – but you do have to coordinate each pair of users. That means that if you have 25 users, you have to coordinate 300 key changes between pairs of people
o Finally, in the first scenario, each user is only managing one key at a time, which is reasonably straight-forward, but any compromise of the key is very damaging,. In our second scenario, each user is managing many keys per day, which is much more complicated, making it more likely that someone will compromise a key. However, any such compromise only impacts two people. While any compromise is bad, in this scenario, it is not as damning. - Block ciphers and rounds of encryption:
o The majority of symmetric algorithms operate as a block cipher, meaning they encrupt a block of text at a time, the most common block size is 64 bits
o Examples of block ciphers that you have seen: the column shift cipher, the rail fence cipher, the code book
o In all cases, a block cipher must pad the end of the data to be an exact multiple of the block size. For example, if the block size is 64 bits, and the last block of text to be encrypted is only 48 bits, then the cipher must the last two bytes at the end of the plaintext before encrypting
o DES does 16 rounds of encryption – that means that in round 1 it goes through its substite, permuatation, XOR and etc then produces a 128 bit cyphertext, then it runs that cypertext and produces another cyphertext for another 15 rounds
o AES does either 10, 12, 14 rounds of encryption - General functions: stream cipher – less common
o Encrypts 1-bit of data a time
o Efficient for smaller transactions
o Requires more computational power, best when implemented in hardware
o One-time pad is an example
5
Q
Data encryption standard (DES) and triple DES
A
- In early 1970s the U.S government put out a call for the best encryption algorithms of the day evaluated – it would pick one to become the data encryption standard, in 1975 an algorithm from IBM known as lucifer was selected and published as this new standard
- The Lucifer cipher utilized a 128-bit key, but the key length was shortened to 56 bits with 16 rounds of computation. This caused some of the brute force problems
o Remember that security is all about trade-offs – although you get more randomness with 16 rounds of computation and is therefore more secure, it takes longer – speed vs security - The DES algorithm is reasonably fast, it has a 56-bit key, operates on 64-bit blocks of text, and performs 16 rounds of computation before spitting out ciphertext
- In 1998, it was reported that DES could be brute forced in three days with a purpose-built computer costing 250 thousand, today a computer can brute force DES in under one day costs less than 5 thousand
- They needed a bandaid solution as single DES could be brute forced but it required more time to get AES approved and gone through peer-review
- It was argued that if you encrypt the DES output three times than it is 2 to the power of 128 times better. This became known as triple DES and is still in use today – with triple DES you have an effective key length of 168 (56 times 3).
- In 2010 NIST said we done enough peer-review and we can start using AES but no one listened – NIST started to deprecate DES in 2017 – it means that the command will still work but something new and better is now available so you should use that instead
- This was to accelerate the move to AES
6
Q
Advanced encryption standard (AES)
- subbytes
- shiftrows
- mixcolumns
- addroundkey
A
- NIST put out a call for algorithms once they learned that DES could be brute forced too quickly – the one they chose was Rijndael in October 2000.
- It seems that a new system comes out every day using AES – it is common and becoming more so
- AES always uses a 128-bit block size. It has three key lengths to choose from: 128, 192, and 256. When you choose key size you are also choosing the number of computational rounds 10, 12, or 14.
- Steps to encryption:
o Subbytes: arbitrary substitional that generates an output similar to what you saw earlier with the scytale cipher
o Shiftrows: rotational substation similar to ROT 13 or ceaser chipher
o Mixcolumns: permutation similar the column shift example
o Addroundkey: a deceptively simple XOR operation to randomize the key for each round
o It combines these four functions and repeats them up to 14 times. This is the real strength and speed of AES – if it only had one of these techniques then any computer would break this encryption really easily
o Remember that the math and software needed is much more complex, but using previous examples to understand it conceptually.
7
Q
Asymmetric cryptography
- process
- key exchange required
- the four processess
- Diffie-hellman
- how can this be secure if the common number and both calculated numbers are shared in the clear for all to see
- pictures on page 71 and beyond
A
- Two mathematically linked keys
o One called the public key one called the private key
o Give the public key to anyone – keep the private key to yourself (passphrase protected – you input a passphrase to get the decryption key) - Possession of one key does not allow you to discern the other key
- The key that encrypts cannot decrypt:
o Just backward of symmetric – and the most fundamental difference - Anything encrypted by one key can only be crypted by the mathematically linked key
- Process:
o Each person has two mathematically linked keys – one is referred to as the public key, this key can be shared with anyone
o The second is the private key and you always keep this key to yourself – in fact, in most implementations, the private key is protected by a passphrase
o Anything encrypted with the public key can only be decrypted by the linked private key
o Anything encrypted by the private key can only be decrypted by the linked public key - Key exchange required:
o Before two parties can communicate there must be a key exchange
o Each side must provide their public key to the other
Bob must provide his public key to Alice
Alice must provide her public key to Bob
The way this happens could be through multiple ways like thumb drive, sending a digitally signed message, or a key repository server where everyone in the organization puts their public key which is help in the active directory domain controller - The four processes:
o When using asymmetric key crypto, there are four possible processes you might want to accomplish.- one of the most common mistakes people make with these systems is using the wrong key for the wrong purpose
Encrypt to send: use the receipeint public key
Decrypt to read: use the recipient private key
Generate a digital signature: use the sender private key
Verify digital signature: use the sender public key
o You can get to the process by answering questions logically and you will always get the correct answer – answer the question correcrlt you will always arrive at the correct key
Anytime the goal comes from the recipient the key is also from them – and anytime it comes from the sender then the key is also from them - Diffie-Hellman: the first publicly available asymmetric algorithm was released in 1976 – one of those things that has one purpose and does it really well. It allows two computers who never communicated with eachother before to exchange symmetric keys securely. They then use that symmetric key to exchange data. It is really common and many encryption methods like IPsec-based VPNs, SSH, and ecommerce or online banking using HTTPS.
o To begin, the web browser’s PRNG generates a number and sends it to the server. For the math that follows, both sides must know this common number. The math only works on a prime number.
o Each side of the communication then uses their PRNG to generate random numbers.
o Each side then takes the common number to the power of the random number they just generated
o Each side sends these newly calculated values to the other side
o Each side takes the calculated value to the power of their individual random values form earlier in the process. The number they both generate is identical and is a shared secret encryption key. The key is neither symmetric not asymmetric since it has properties of both. It is symmetric in that one value will be used to both encrypt and decrypt. It is asymmetric in that it is based on prime numbers and is, therefore, very slow. Technically you can use that shared secret to encrypt data but it is not done that way, so instead what does happen is to encrypt the encryption key – usually no longer than 256 binary bits, which will be quick regardless of the method used.
o The browser’s PRNG generates a symmetric session key
o On the browser’s side, the shared secret generated in step 5 is then used to encrypt the symmetric session key. The encrypted form of the symmetric session key transmits to the server. There the server decrypts the symmetric session key using its copy of the shared secret from step 5.
o The browser and server proceed to utilize symmetric session key to both encrypt and decrypt traffic to eachother. - How can this be secure if the common number and both calculated numbers are shared in the clear for all to see?
o To decrypt the symmetric session key, an attacker would have to know the common number, which of course they do know since it was shared in plaintext. The attacker would also need one of the private PRNG generated numbers. The strength of this method boils down to how hard it would be to predict or brute force one of those numbers. In our example we used simple numbers, but in the real world those three numbers are usually each 4,096 binary bits which is 1,234 digits in length. Predicting or brute forcing such a number is virtually impossible.
8
Q
Asymmetric key: RSA
A
- Diffie-Hellman can only do key exchange, but RSA can also be used for encryption and digital signature – RSA is the most common asymmetric algorithm for encryption and digitial signatures
- The algorithim is based on the difficulty of factoring large prime numbers
- Considered the de facto worldwide standard
- Created in 1978 by Ron Rivest, Adi Shamir, Leonard Adleman – name from the first letter of their last names
9
Q
Asymmetric key: elliptical curve crypto
A
- The exception to the rule regarding asymmetric algorithms using prime numbers, instead it is based on the difficulty of factoring points on an elliptical curve
- Because it is not based on prime numbers, the earlier discussion about asymmetric being slower and requiring much larger keys do not apply to the ECC. It is fast and efficient, even in less powerful hardware.
- Provides encryption, digital signature, and key exchange
- Popular and implemented in smart cards, smartphones, other devices with limited storage and processing capability
- There I also the elliptical curve Diffie-hellman key exchange
- The company certicmon of Ontario Canada holds a patent on ECC – bottom line: ECC adoption is growing but would be growing more rapidly without the patens and resulting lawsuits
- Interestingly, the NSA licensed certicom’s ECC implementation for $25 million. In a 180 degree turnaround the NSA now allows for the use of public domain algoriwthms to encrypt the US classifief information up to top secret. NSA has never even considered this in the past, this seems to be a strong endorsement of AES, ECDH, ECDSA and SHA-384.
10
Q
Digital signature
- how does the digital signature work
A
- A generic term to describe a process to:
o Verify who sent the document
o Verify the document received is the exact same document that was sent
o 68 countries recognize digital signatures from other countries - In the following scenarios, there is an assumption that Alice and Bob have at some point already exchanged their public keys – there is also an assumption that each is certain the public key in their possession real does belong to the other
- How does digital signatures work?
o Alice opens outlook and types a message – she clicks a little button in outlook that says sign and then clicks the button that says send – the process that follows happens behind the scenes:
The software generates a one-way hash of the plaintext file
The hash is encrypted with alice’s private key – this creates the actual digital signature
The digital signature is attached to the message
The message and attached signature transmit to Bob
When bob opens the message, the software detaches the signature and decrypts it. Because it was encrypted with the sender’s private key, only the sender’s public key can decrypt it
The software generates a second one-way hash of the plaintext message
The new hash and the one retrieved by decrypting the signature are compared
Facts: - Because Alice’s public key was capable of decrypting the signature, and only Alice possess the mathematically associated private key, then only Alice could have generated that signature.
- Because the hash from the signature and the new hash match, the message Bob received, and the message Alice sent are exactly identical – every binary bit is the same
11
Q
Hybrid cryptography example
A
- In this example, alice and Bob are concerened with confidentiality but not with integrity – again aAlice opens outlook and types an email message to Bob – this time she clicks the button that says encrypt followed by the button that says send
o A PRNG generates a symmetric session key
o The symmetric session key encrypts the plaintext message, generating the ciphertext version
o The symmetric session key encrypted by the recipeint’s public key. This creates the digital envelope, which is just the encrypted form of the symmetric session key
o The digital envelope is attached to the ciphertext message - The package transmits to bob, and when he opens it this is what happens:
o The digital envelope is detached form the ciphertext message
o The digital envelope was encrypted with Bob’s public key, so his private key decryps it
o The symmetric session key decrypts the ciphertext, giving Bob the paintext version of the message - This is the best of both worlds: the speed of symmetric and the ease of use of asymmetric – this hybrid approach is extremely common today
- People also want really good security for the symmetric session key and choose a 1,024 bit asymmetric key to encrypt the digital envelope – this becomes the weakest link in the chain for the same level of security you would need an asymmetric key of 15,360 bits long – we have never seen encryption implemented with an asymmetric key that long
- Why not simply encrypt with the asymmetrick key? Speed – AES encryption is dramatically faster than RSA – that is why we encrypt the bulk data with symmetric such as AES. We then encrypt the AES key with RSA – which shouldn’t take long since the longest AES key can only be 256 binary bits
12
Q
Signcryption
- example sender
- example reciever
A
- What if we’re greedy and want more:
o The nonrepudation of the digital signature
o The confidentiality of hybrid crypto
o The speed of symmetric key
o The ease of use of asymmetric key
o Protection of the symmetric key during transmission - Signcryption example sender: once Alice opens outlook and types amessage addressed to Bob, but this time she clicks both the button that says sign and the other that says encrypt
o PRNG generates a symmetric session key
o The symmetric session key encrypts the plaintext, generating the ciphertext
o The symmetric session key is encrypted with the recipient’s public key to create the digital envelope
o The digital envelope is attached to the ciphertext message (up to this point, the process is identical to the top one-half of the hybrid encryption slide)
o A one-way hash algorithm generates a hash of the plaintext message
o The hash is encrypted with the sender’s private key to create the digital signature
o The digital signature is attached to the ciphertext message
o The combines package of the ciphertext message, the digital envelope, and the digital signature are transmitted to Bob - Signcryption example receiver:
o The software detaches the digital envelope
o The digital envelope was encrypted with Bob’s publick ley, so his private key decrypts it – this returns the symmetric session key to a usable state
o The symmetric session key decrypts the ciphertext, regenerating the original plaintext
o The digital signature is detached by the software
o The digital signature was encrypted by the sender’s private key, so the sender’s public key can decrypt it – the digital signature is decrypted, returning the original hash – returning the original hash to plaintext
o Bob’s software generates a second hash using the same algorithm – the new hash and the original hash are compared – if they match, the message opens on Bob’s screen without errors
o Bob reads the message – he knows it came from Alice and that he got exactly what she sent. He knows the symmetric key was protected throughout the process. And he appreciates the ease of use of the asymmetric key as well.
13
Q
Email to multiple recipients
A
- Why is it so slow when I send an encrypted email especially to multiple people?
- When you send an email to multiple people your computer connects to the email server and the email transmits to that server – the email server distributes the email to all recipients. Note the email transmits from Alive’s computer to the mail server one time, and the mail server distributes it to all recipients. In this case, Alice has to send each email individually to the mail server and the mail server sends it to one recipient at a time –
- The process to multiple recipients changes due to a fundemantal rule about crypto: encryption and decryption can only occur on the system(s) where the keys reside
- In this case, the emaikl server does not have the encryption/decryption keys – those reside on Alice’s computer and on each recipient’s computer
o Alice’s computer must encrypt the message with recipient1’s key, send it to the server and server sends the email to recipient 1
o Alice’s computer must encrypt the message. With recipient2’s key, send it to server and the server. Sends the email to recipient2
o This continues until all recipients hav received the email encrypted via their own key
14
Q
Cryptographic man-in-the-middle
- picture on page 78
A
- Occurs when someone has created a situation in which all your data goes through the attacker
o When Bob sends his real public key to Alice, Eve intercepts it and sends a fake of Bob’s public key on to Alice
o When Alice sends her real public key to Bob, Eve intercepts it and sends a fake of Alice’s public key on to Bob
o Notice: Eve has mathematically associated private key for each of the public keys forwarded to Alice and Bob. Specifically, Eve possess a fake Alice and Bob public keys since she created those key-paids. Of course, she also has real Alice and Bob publick keys since she intercepted them - Eve can mess with Bob and Alice. For example, Alice sends an encrypted and signed message to Bob – Eve intercepts the message – it was encrypted with Bob’s fake public key (since that is the public key Alice thinks belongs to Bob), and Eve has the fake private key to decrypt and read the message. Indeed, Eve can even modify the message if she likes – then she can rencrypt the message with Bob’s real public key and re-sign it with Fake Alice private key and send the message on to him. If Eve is careful, this attack is virtually undectable.
15
Q
Digital certificates
- two parts private portion with the private key
- public portion
A
- A digital certificate is an electronic document:
o Analogies include passpower, or dirver’s license but they are not on the same level of verification and information - There’s always two parts:
o The private portion contains the private key
o The public portion contains:
Your public key
Your name
A validity period (from date x to date y)
Who issued it (the certificate authority)
Digital signature that can prove the certificate’s validity
Proves the cryptographic MitM attack did not occur – does not prevent it but it proves it never happened
