FIT2093 INTRODUCTION TO CYBER SECURITY
Week 2 Lecture Cryptography I: Symmetric Key Encryption Part 1
Principles for CONFIDENTIALITY
www.monash.edu
Copyright By PowCoder代写 加微信 powcoder
Symmetric Cryptography
Part 1: Basic Concepts ● CONFidentialityproblem
● Cryptography:bigpicture
● Encryption:ClassicalCiphers
● Encryption:ModernCipherprinciples
Part 2: Modern Encryption Algorithms ● Blockciphers
● Designrequirements
● CasestudyI:DataEncryptionStandard(DES)
● CasestudyII:AdvancedEncryptionStandard(AES)
● BlockCipherModes:Howtouseblockciphersforencryption • ECB, CBC, CTR
CONFidentiality Problem
The CONF Problem: Insecure Channel vs Secrecy
• Aim: vs Insecure channel / storage
• Strategy
• accept fact: channel insecure
• whatever sent, could be intercepted (eavesdropping)
• no control over channel
CONFidentiality : How?
• Aim: reveal nothing: secrecy / confidentiality (CONF)
• Strategy
• accept fact: whatever sent, could be intercepted (eavesdropping)
• even if intercepted, not reveal secret info
• scramble info before send, s.t. only Rx can descramble (encrypt) (decrypt)
• use secret (key) s.t. only Rx can decrypt Encrypt
Note: free images from freeimages.com
CONFidentiality: How?
Symmetric Crypto
● Goal:secretdataremainsCONFidential
○ notallcanaccess
○ only some can access ● Q: how to enforce?
○ access control: check who, & grant access ○ encryption:
• lock, only some have key
• scramble / mix up, only some can undo
Security Principle(s)
• State what can’t be solved/avoided, aim for next best e.g. channel insecure, cannot avoid interceptions
so next best: don’t let intercepted things reveal info • change means: “prevent interception” “wrap it up”
(physically secure the channel) (secure the sent info)
• be fluid: the means could be varied , as long as same goal achieved eventually • x prevent interception, that’s ok
• so prevent revelation of info
CONFidentiality: How?
Symmetric Crypto
● Goal:secretdataremainsCONFidential ● Means:
○ notallcanaccess,onlysomecanaccess
○ encryption: cannot access anymore
○ decryption: to access again, undo the encryption
• only some can decrypt (restricted reversal) • how?
• keep algorithms secret
• use extra (secret) input (the key)
CONFidentiality: via Obscurity?
Symmetric Crypto
● … only some can decrypt … ● How?
○ keep algorithms secret
CONFidentiality: Kerckhoffs’ Principle
Symmetric Crypto
● … only some can decrypt … ● How?
○ useextra(secret)input(calledthekey)
CONFidentiality
Symmetric Crypto
● keep algorithms secret: security by obscurity
● keep key secret: security by Kerckhoffs’ principle
● Q: which one do you think is harder to do: Keeping an algorithm secret or a key secret? Why?
Activity (5 mins)
1) Click the latest link in the Zoom chat
2) Add your question response to the Ed forum
A hint from history…
Cryptography: Big Picture
Cryptography: Big Picture
Symmetric Crypto
● CONFidentiality:achievedviaEncryption(weeks2-4) ● Twotypesofencryption:
● Symmetrickey(week5) ● PublicKey(weeks6-7)
● INTegrity achieved via (week 5)
○ Message Authentication Code (MAC) – symmetric key
○ Digital Signatures – public key
● AUTHentication achieved via (week 5) ○ Digital Signatures – public key
Cryptography: Big Picture
Symmetric Crypto
Cryptography – Terminology
● plaintextp⟶Encryption⟶ciphertextc
● messagem⟶MAC⟶tagτ
● message m ⟶ DigitalSignature ⟶ signature s
● Cryptography:
○ techniques that transform the input (message) such that output allows to
achieve CONF, INT, AUTH, …
• from Greek words kryptos (hidden) & graphein (writing)
• initially: study of message secrecy (hidden writing) aka CONF, now covers many
other security goals
Cryptography vs Cryptanalysis
Symmetric Crypto
Cryptography – Terminology
● Cryptography: by cryptographer
○ how to design to achieve security
● Cryptanalysis: by cryptanalyst
○ how to break / analyse security
○ offers security assurance to others about your design
Encryption: Classical Ciphers
Cryptography: Classical
Symmetric Crypto
● Mostly about encryption
○ e.g. [during ’s time]
○ Enigma [by Germany during World War II]
● Classical Ciphers: two types of basic operations ○ Substitution
○ Transposition
Cryptography: Classical
Symmetric Crypto
● Substitution
Systematically substitute (group of) letters with
other (group of) letters … like table lookup
● Example: change each letter with another letter that
is two positions down in the English alphabet sequence: “message” => “oguucig”
● Transposition
Rearrange the position of the letters in the message according to some rules:
not depend on value of letter(s)
● Example: Move each letter in the message by 1 position:
“message” => “emessag”
Classical Example:
Symmetric Crypto
● Caesar cipher:
○ asubstitutioncipher,namedafterJuliusCaesar
● Howitworks:
each letter is substituted with the letter a fixed number of positions after it in the alphabet table
● Thenumberofpositionsisthekeybothforencryptionanddecryption: should not let others know how many number of positions
Classical Example:
Symmetric Crypto
● K=3 … Shifted by three characters
Outer: plaintext char
Inner: ciphertext char
Classical Example:
Symmetric Crypto
● can be viewed as modulo operation ● Encryption:
○ Letxbethepositionofplaintextlettertobereplaced,nbenumberof positions to be shifted to find the replacement (ciphertext) letter
i.e the key is the value of n
○ En(x)=(x+n)mod26&substitutethatcharacterinthatposition
● Decryption:
○ Dn(x)=(x−n)mod26
Classical Example:
Symmetric Crypto
● forakeyK=3,
○ plaintext letter: ABCDEF…PQRSTUVWXYZ
○ ciphertext letter: DEFGHI…STUVWXYZABC e.g. TREATY IMPOSSIBLE
is translated into
WUHDWB LPSRVVLEOH
● Play with the online Caesar cipher here: https://cryptii.com/pipes/caesar-cipher
Symmetric Crypto
● Q: How to attack the ?
● A: by brute force exhaustive search for the key
○ Q: what is the key?
● Attack time complexity is very low
○ can be easily broken
○ Q: how many possible keys?
○ Q: how to check a guess for key?
○ Q: how long would it take?
Activity (5 mins)
1) Click the latest link in the Zoom chat
2) Add your question response to the Ed forum
: Attack example
BRUTE FORCE ATTACK ON CAESAR CIPHER
LET’S SAY WE ARE USING CAESAR TO ENCRYPT THE NAME “ALICE”, THERE WILL BE ONLY 26 POSSIBILITIES:
ONLY ONE OF THE 26 POSSIBLE DECRYPTIONS WILL TYPICALLY MAKE SENSE
E.G. BRUTE FORCE ATTACK ON CIPHERTEXT = “BMJDF”
Key = Shift
0 1 2 3 4 . . . . . 25
Symmetric Crypto
● Security of the
○ insecure against brute force exhaustive key search ● Attack complexity
○ how many guesses?
• how many possible shifts = 26 (too small!)
○ effort to check each guess • see if it’s English
Example II: Monoalphabetic Substitution Cipher
Symmetric Crypto
● Build a (mapping) table that maps a character with the replacement character Q: How is this cipher different from Caesar cipher?
● Need this table (in fact column 2) to encode/decode messages
○ assuming the alphabets in column 1 is in a known sequence, else column 1 also
● Different people can use different tables
Example II: Monoalphabetic Substitution Cipher
Symmetric Crypto
● Build a (mapping) table that maps a character with the replacement character
● Q: What property(ies) does this table need to satisfy?
● Q: How many such mapping tables are possible for 26 upper-case English alphabets?
○ 26! Mapping tables. Why?
Monoalphabetic Substitution Cipher: Security
Symmetric Crypto
● Alphabetsubstitution(mapping)table ○ canbethoughtofasakey:
○ NumberofpossiblekeysN=26!~4×1026
○ Bruteforcekeysearchisinfeasible(millionsofyears)
Q: Assume each key guess takes 1 ns = 10-9 sec to check. How long would brute force key search take?
Activity (5 mins)
Add your question response to the Ed forum
Monoalphabetic Substitution Cipher: Security
Symmetric Crypto
● But, is Monoalphabetic cipher secure against other cryptanalysis attacks?
○ No,anefficientstatisticalfrequencyanalysisattack: • Observation:
• each plaintext letter always encrypts to same ciphertext letter
• letter repeat in plaintext letter
→ repeat in ciphertext !
• cipher weakness: ciphertext letter frequencies are equal to corresponding plaintext letter frequencies
• Fact: letter frequency in English gives lots of info on letter • use fact with above weakness to break the cipher!
CRACKING THE MONOALPHABETIC SUBSTITUTION CIPHER: FREQUENCY ANALYSIS ATTACK
• Byusingfrequencyanalysiswith following assumptions:
• MessagesareinEnglishform
• Themessageislongenoughtoseethe
repetitive patterns
as we’ll see, they don’t have to be too long!
Relative frequency (typical English text)
Given the ciphertext:
STUTFR LIASS LHTAQ GY LAEKOYOET AM
CGKSRL TFR MIT COFR LAOSL GXTK MIT
CAMTKL LWKYAET JWOTMSB ZWM LWKTSB
TXTF OY MIT DGKKGC OL ZAKKTF GY
HKGDOLTL FGMIOFU LIASS YGKTLMASS DB
KTMWKF MG ZTEGDT MIT RTC MIAM
JWTFEITL MIT SAFR MG LHAKT MIT
LAFRL MIT LTAL MIT LQOTL O GYYTK
MITT MIOL LOSTFM LAEKOYOET
Ciphertext letter frequencies
FREQUENCY ANALYSIS ATTACK: EXAMPLE
English Letter Frequencies
TLMKAIOGSFYERWCDBHZJQUXNP
1. See the frequency table, replace T with E, because normally the letters with highest frequencies will match
FREQUENCY ANALYSIS ATTACK: EXAMPLE
SEUEFR LIASS LHEAQ GY LAEKOYOEE AM CGKSRL EFR MIE COFR LAOSL GXEK MIE CAMEKL LWKYAEE JWOEMSB ZWM LWKESB EXEF OY MIE DGKKGC OL ZAKKEF GY HKGDOLEL FGMIOFU LIASS YGKELMASS DB KEMWKF MG ZEEGDE MIE REC MIAM JWEFEIEL MIE SAFR MG LHAKE MIE LAFRL MIE LEAL MIE LQOEL O GYYEK MIEE MIOL LOSEFM LAEKOYOEE
2. See the replaced ciphertext, any short & repeated words? One short word that ends with E is THE. Update the table.
SEUEFR LHASS LHEAQ GY LAEKOYOEE AT
CGKSRL EFR THE COFR LAOSL GXEK THE
SEUEFR LIASS LHEAQ GY LAEKOYOEE AM CGKSRL EFR MIE
CATEKL LWKYAEE JWOETSB ZWT LWKESB
COFR LAOSL GXEK MIE CAMEKL LWKYAEE JWOEMSB ZWM
EXEF OY THE DGKKGC OL ZAKKEF GY
LWKESB EXEF OY MIE DGKKGC OL ZAKKEF GY HKGDOLEL
HKGDOLEL FGTHOFU LHASS YGKELTASS DB
FGMIOFU LIASS YGKELMASS DB KEMWKF MG ZEEGDE MIE
KETWKF TG ZEEGDE THE REC THAT
REC MIAM JWEFEIEL MIE SAFR MG LHAKE MIE LAFRL MIE
JWEFEHEL THE SAFR TG LHAKE THE
LEAL MIE LQOEL O GYYEK MIEE MIOL LOSEFM LAEKOYOEE
LAFRL THE LEAL THE LQOEL O GYYEK THEE THOL LOSEFT LAEKOYOEE
FREQUENCY ANALYSIS ATTACK: EXAMPLE
3. There are still short words e.g. “I”, “but”, can be guessed from current ciphertext. Replace Z with B, W with U, O with I.
SEUEFR LHASS LHEAQ GY LAEKIYIEE AT
CGKSRL EFR THE CIFR LAISL GXEK THE CSAETUEKFLRLUHKAYSASEELHJEUAIQETGSYBLABUETKOLYUOKESEBAT CGKSRL EFR THE CEXOEFRILYAOTSHLEGDXGEKGTCHEICLABTAEKKLELFWGKYAEE JWOETSB ZWT HLWKGKDEISLBELEXFEGFTHOIYFUTHLEHDASGSKKYGCKEOLLTAZSASKKDEBF GY HKGDOLEL KFEGTUHKOFFUTGLHBAESESGDYEGKTEHELTARESCS DTBHAKTETWKF TG ZEEGDE THE REC TJUHEAFTEJHWELEFTEHEELSATFHRE STGAFLRHTAGKELHTAHKEE THE LAFRL THE LEAL THE LQAFORELL TOHGEYLYEAKLTHTHEE TLHQIOELLLOISGEYFYTELKAEKOYOEE
THEE THIL LISEFT LAEKIYIEE
4. With the replaced ciphertext, we can discover even more short words, such as “that”, “to”, “if” and “this”. Notice that the plaintext of A is A too, which is not shown in the frequency analysis because the sample text is not long enough.
SEUEFR SHASS SHEAQ OF SAERIFIEE AT CORSRS EFR THE CIFR SAISS OXER THE CATERS SURFAEE JUIETSB BUT SURESB EXEF IF THE DORROC IS BARREF OF HRODISES FOTHIFU SHASS FORESTASS DB RETURF TO BEEODE THE REC THAT JUEFEHES THE SAFR TO SHARE THE SAFRS THE SEAS THE SQIES I OFFER THEE THIS SISEFT SAERIFIEE
FREQUENCY ANALYSIS ATTACK: EXAMPLE
5. Looking back to the frequency table we have, replace E with C.
SEUEFR SHASS SHEAQ OF AT CORSRS EFR THE CIFR SAISS OXER THE CATERS SURFACE JUIETSB BUT SURESB EXEF IF THE DORROC IS BARREF OF HRODISES FOTHIFU SHASS FORESTASS DB RETURF TO BECODE THE REC THAT JUEFCHES THE SAFR TO SHARE THE SAFRS THE SEAS THE SQIES I OFFER THEE THIS SISEFT
6. Continue with the table, skipping the letters that are already being replaced, replace C with W
SEUEFR SHASS SHEAQ OF AT WORSRS EFR THE WIFR SAISS OXER THE WATERS SURFACE JUIETSB BUT SURESB EXEF IF THE DORROW IS BARREF OF HRODISES FOTHIFU SHASS FORESTASS DB RETURF TO BECODE THE REW THAT JUEFCHES THE SAFR TO SHARE THE SAFRS THE SEAS THE SQIES I OFFER THEE THIS SISEFT
7. Ciphertext letter B has two possible plaintext letters, which is G and Y. Looking at the current text, the words containing B makes more sense if replacing with Y, thus replace B with Y.
FREQUENCY ANALYSIS ATTACK: EXAMPLE
SEUEFR SHASS SHEAQ OF AT WORSRS EFR THE WIFR SAISS OXER THE WATERS SURFACE JUIETSY BUT SURESY EXEF IF THE DORROW IS BARREF OF HRODISES FOTHIFU SHASS FORESTASS DY RETURF TO BECODE THE REW THAT JUEFCHES THE SAFR TO SHARE THE SAFRS THE SEAS THE SQIES I OFFER THEE THIS SISEFT
8. Using the same method as in Step 7, replace Q with K instead of V and J.
SEUEFR SHASS SHEAK OF SACRIFICE AT WORSRS EFR THE WIFR SAISS OXER THE WATERS SURFACE JUIETSY BUT SURESY EXEF IF THE DORROW IS BARREF OF HRODISES FOTHIFU SHASS FORESTASS DY RETURF TO BECODE THE REW THAT JUEFCHES THE SAFR TO SHARE THE SAFRS THE SEAS THE SKIES I OFFER THEE THIS SISEFT
FREQUENCY ANALYSIS ATTACK: EXAMPLE
9. We can tell “shall”, “forestall”, “over”, “even”, “morrow”, replacing S with L, X with V, F with N, D with M respectively.
LEUENR SHALL SHEAK OF SACRIFICE AT WORLRS ENR THE WINR SAILS OVER THE
EVEN IF THE
H U SHALL
J THE LANR TO SHARE THE SANRS THE SEAS THE SKIES I OFFER THEE THIS
THE REW THAT
8. Using same method as in Step 9, replace R with D,
H with P, U with G…and the rest of the letters accordingly. D
M A G O F L I K
SHALL SPEAK OF AT END THE WIND SAILS OVER THE
EVEN IF THE IS SHALL
TO THE DEW THAT THE LAND TO SPARE THE
SANDS THE SEAS THE SKIES I OFFER THEE THIS
FAILED ATTEMPT TO FIX THE MONOALPHABETIC STATISTICAL WEAKNESS
How about a more complex two–step cipher:
1. Encrypt message M with monoalphabetic key K1 to get ciphertext C1
2. Encrypt C1 again with monoalphabetic cipher with a different key K2 to get ciphertext C2
M → C1 → C2
Q: Is the two-step more secure than one-step monoalphabetic cipher?
A: No. Why?
Activity (5 mins)
1) Click the latest link in the Zoom chat
2) Add your question response to the Ed forum
Example III: Transposition Cipher: Rail Fence Cipher
Symmetric Crypto
● an example transposition cipher
● letters placed in multiple number of lines,
from line 1 position 1 to line 2 position 2, then line 3 position 3, line 2 position 4,
line 1 position 5, etc
● e.g. the plaintext “WE ARE DISCOVERED FLEE AT ONCE” W…E…C…R…L…T…E
.E.R.D.S.O.E.E.F.E.A.O.C. ..A…I…V…D…E…N..
● ciphertext:wecrlteerdsoeefeaocaivden
● Q:Whatisthekeyforthisexampleofrailfencecipher?
● Railfenceofdepth3 39
Example III: Transposition Cipher: General
Symmetric Crypto
● DecideonablocksizeL(sayL=10letters)
● Fixapermutationof(0,1,2,3,…,9)i.e.thekeyK:
○ e.g.K=(5,3,1,4,6,8,2,0,9,7)
○ TransposeeveryblockofLsuccessivemessagelettersaccordingtoK,
e.g.: 0123456789 0123456789
○ Message = HELLOTHERE HOWARETHEY
○ Cipher = TLEOHRLHEE EAORTEEWHY ● Secure?
● No – Statistical patterns (letter frequencies) remain in ciphertext! 40
Encryption: Modern Cipher principles
Modern Ciphers = Product Ciphers
Symmetric Crypto
● Substitution&Transposition
○ eachcontributesownstrengthtoencryption
● Q:doescombiningamonoalphabeticsubstitution&transpositioncipher give a
○ Monoalphabeticsubstitutioncipher?
○ Atranspositioncipher?
● No!productismorecomplexthaneitheroneindividually!
● Number of possible product keys is (likely to be) the product of number of keys of individual methods
Cipher Properties (I)
Symmetric Crypto
● Confusion
○ maketherelationshipbetweenciphertextC&encryptionkeyKas complex as possible
• otherwise observing C statistics would leak info on K ○ achievedbycomplexsubstitution
○ HardtogetKbyobservingC
Q: Does Caesar cipher have confusion? Why?
Cipher Properties (II)
Symmetric Crypto
● Diffusion
shouldspreadtheinformationfromPsothat(eventually)eachPdigit affects many C digits
achievedbycomplextransposition patternsinPcannolongerbeobservedinC
Activity (5 mins)
Add your question response to the Ed forum
○ and encrypts P=“HEMPME” to C=“GQADKW”
Does this cipher achieve Diffusion? Why/why not?
Q:IfsomecipherencryptsP=“HELPME”toC=“GQWCKW”
Cipher Properties (III)
Symmetric Crypto
● Avalancheeffect(diffusionforchangesineitherPorK)
○ SmallchangeineitherplaintextPorkeyKproducesasignificantchangein the ciphertext C
○ E.g.changeinonebitofPoronebitofKshouldproduceachangeinmanybitsofC
● P=11000000, K = 01101101 à C = 10101011
● P=11000000, K = 01111101 à C = 11011101
Unconditional vs Computational Security
Symmetric Crypto
● Two kinds of encryption security requirements
● Unconditional security / information- theoretic security
○ even if attacker has infinite computational power, ○ cannot get information on plaintext from ciphertext
● Computational security
○ if attacker has limited computational power,
○ cannot get information on plaintext from ciphertext
○ time needed for attack > useful age of info
○ cost of breaking > value of info
The One-Time Pad
Symmetric Crypto
● Q: Is unconditionally secure encryption possible?
● A: Yes – One-Time Pad Encryption
○ startwiththeCaesarsubstitutioncipher
○ butuseanindependentrandomalphabetshiftforforeach plaintext letter:
e.g. K = (2,9,13,20, 4) M=HELLO C=JNYFP
● Claim:Itisnotpossibletobreakthiscipherbybruteforceexhaustive search. Q: Why?
EXAMPLE OF DECRYPTING ONE-TIME PAD BY USING RANDOM KEY
Given a ciphertext “EQNVZ”. Assume we already obtained the random key, which is also the same length “XMCKL”, how do we decrypt the message?
EQNVZ 4 16 13 21 25
XMCKL 23 12 2 10 11
-179 4 11 11 14 HELLO
1. Convert the letters into numbers, where A = 0, B = 1…Z = 25
2. Subtract the value of random key from the ciphertext
3. If the result is a negative number, calculate how much it needs to reach 26. In this case, -19-7 = -26. Thus 7.
4. Convert the number back into alphabets, which is the message in plaintext
ONE-TIME PAD USING RANDOM KEY
IMPOSSIBLE TO APPLY BRUTE FORCE ATTACK!
Why is brute force attack impossible on a one-time pad? Reason is NOT the complexity of brute force!
e.g. a short plaintext “Alice”, we will have 26*26*26*26*26 = 11,881,376 possibilities, which is easy to search through in a fraction of a second on any computer today
However if we are using random key for each of the alphabet, this is like rolling a 26-sided die for each encrypted letter
REASON FOR IMPOSSIBILITY TO BRUTE FORCE THE ONE-TIME PAD: ALL POSSIBLE DECRYPTIONS ARE EQUALLY LIKELY
It is possible to brute force the number of possibilities in previous
However, since each possible key is equally likely, it is impossible – to know which decryption is the corre
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com