3 Basics of Cryptography Basics of Cryptography

cryptography

1. CMPS 385 Computer Security
Spring 2024
Lecture 3
Basics of Cryptography
Instructor: Dr. Khaled Mohammed Khan

2. Outline
●Overview
●Terminology
●Subfields
●Kerckhoffs’s Principle
●Cryptanalysis
2

3. Goals
●Confidentiality:= Data not disclosed to unauthorized parties
●Integrity:= Data cannot be modified in an unauthorized or undetected way
●Availability:= Data must be available whenever legitimate principals need it
●Authenticity:= Data origin or identity of an entity can be determined
●Non-repudiation:= An entity cannot deny the receipt or transmission of data
●…
3

4. Applications of Cryptography
●Data encryption (at rest, in
transit, in use)
○Disks
○Storage
○E-Mails
●Remote authentication
○Secure Shell (SSH)
○Virtual Private Network (VPN)
●Digital signatures
○E-Mails
○eIDs
○Bank cards
4
●Online Banking
●Cryptocurrencies
●Digital Rights Management
●…

5. The Field of Cryptography
5
Number
Theory
Complexity
Theory
Information
TheoryAlgorithms
Cryptography
ConfidentialityIntegrityAuthenticityNon-repudiation
MathematicsComputer SciencePhysicsElectrical Engineering
Risk ManagementSecurity

6. Terminology (1)
●Cryptology:= The subordinate study of cryptography and cryptanalysis
●Cryptanalysis:= The technique of obtaining information about the content of
a ciphertext without knowing the key
●Alphabet:= A finite set Aof characters, and n = |A| is the size of the alphabet
○Alphabet A:= {a, b, c}, n = 3
○a, b, c, aaa, bbc, cabbacbbaa, are plaintexts from the alphabet A
6

7. Terminology (2)
●Plaintext (m):= A message in its original form
●Ciphertext (c):= A message in encrypted form
●Cipher-algorithm for transforming plaintext to ciphertext
●Key-information used in cipher known only to sender/receiver
●Encryption (E) := An invertible mapping that generates a ciphertext cfrom a
plaintext mand a key k
●Decryption (D) := The inversion of Eto restore the plaintext m from
ciphertextc and keyk
7
•Cipher: An algorithm used to encrypt and decrypt text
•Key: The set of parameters that guide a cipher.
•Neither is any good without the other.

8. Terminology (3)
●Cryptosystem := 5-tuple (M, C, E, D, K)
○M := set of plaintexts
○C:= set of ciphertexts
○K:= set of keys
○E:= M x K => C enciphering function
○D:= C x K => M deciphering function
8

9. The Field of Cryptology
9
Cryptology
CryptographyCryptanalysis
Symmetric
Cryptography
Asymmetric
CryptographyProtocols
Block CiphersStream
Ciphers

10. Focus in this Course
10
Cryptology
CryptographyCryptanalysis
Symmetric
Cryptography
Asymmetric
CryptographyProtocols
Block CiphersStream
Ciphers

11. Symmetric Cryptography
11
Cryptology
CryptographyCryptanalysis
Symmetric
Cryptography
Asymmetric
CryptographyProtocols
Block CiphersStream
Ciphers

12. Symmetric Cryptography -Analogy
●Safe with a strong lock, only Alice and Bob have a copy of the (shared) key
○Alice encrypts, i.e. locks the safe with her key
○Bob decrypts, i.e. unlocks the safe with his key
12

13. Symmetric Cryptography
Alternative names: private-key, single-key or secret-key cryptography.
Alice Bob
Eve
(bad guy)
P P
Unsecure channel
(e.g. Internet)
•Problem Statement:
1) Alice and Bob would like to communicate via an unsecure channel (e.g., Internet)
2) A malicious third party Eve (the bad guy) has channel access but should not be able
to understand the exchanges messages
13

14. Symmetric Cryptography
Alice Bob
Eve
(bad guy)
Encryption
e( )
Decryption
d( )
Secure Channel
K
P C
K
P
Unsecure
channel
(e.g. Internet)
P is the. plaintext
C is the ciphertext
Kis thekey
e() istheencryptionalgorithm
d() isthedecryptionalgorithm
Set of all keys {K1, K2, ...,Kn} is the
key space
Solution:Encryption with symmetric cipher.
ÞEve obtains only ciphertext C, that looks
like random bits
C
14

15. Block Ciphers
16
Cryptology
CryptographyCryptanalysis
Symmetric
Cryptography
Asymmetric
CryptographyProtocols
Block CiphersStream
Ciphers

16. Block Ciphers -Overview
17
Plaintext of length n-bit
Plaintext
Block 0 of x-bit
Plaintext
Block 1 of x-bit
Plaintext
Block n of x-bit…
Enc()Enc()Enc()…
Ciphertext
Block 0 of x-bit
Ciphertext
Block 1 of x-bit
Ciphertext
Block n of x-bit…
Ciphertext of length n-bit

17. Block Ciphers Can Do More Than Encryption
●In addition to encryption, Block ciphers can be used to
○Build different types of block-based encryption algorithms
○Realize Stream ciphers
○Construct Message Authentication Codes
○Construct Hash functions
○Realize Key Establishment protocols
○Build Pseudorandom Generators
○…
18

18. Building Blocks of Block Ciphers
●Confusion
○Goal:Obfuscate the relationship between
the key and ciphertext
○Achieved through substitution
○Avalanche effect:Small changes in key
results in large changes in ciphertext
19
●Diffusion
○Goal:Spread the influence of a plaintext
symbol over many ciphertext symbols
○Achieved through bit permutation
○Avalanche effect:Small changes in plaintext
results in large changes in ciphertext
•Confusion and Diffusion by themselves alone cannot provide security.
•The idea is to alternate them to build so called Product ciphers.
•Many encryption standards use Confusion and Diffusion
•Here are two examples of standards that use these:
•Data Encryption Standard (DES)
•Advanced Encryption Standard (AES)

19. •DES
•DES is a Block Cipher Symmetric encryption algorithm
•It takes 64 bit plain text block and a key size of 64 bit
•It produces 64 bits cipher text
•No of rounds: 16 rounds
•Key size: 64 bits
•DES uses Permutation(for diffusion) and Substitution (for confusion)
•AES•AES is a Block Cipher Symmetric encryption algorithm•AES Block size -minimum 128 bit plain text •No of round: 10 rounds•Key size –128 bit•AES uses Permutation(for diffusion) and Substitution (for confusion)
Basics of DES and AES

20. ExampleofSubstitution:DESUsesS-Boxes
•Eightdifferent substitutiontables•Each S-box maps 6 bits of input
to 4 bits of output•S-Box introducesconfusion
21Chapter 3 of Understanding Cryptographyby Christof Paar and Jan Pelzl
Row Index
3
Column Index
2
S-box
•Bitwisepermutation
Introducesdiffusion
in DES
An example of a S-Box
Output is 4-bit: 1000

21. Substitution Example: AES UsesS-Box
•Each value of the state is replaced with the corresponding S-Box value => bytewiseS-Box substitution•8 bitsfromtheinputmatrixaresavedin thestatematrix.•First 4 bitsof8-bits in eachcelloftheinputmatrixistherownumberin S-box: 0..15 (A..F)•Next 4 bitsisthecolumnnumberin theS-box•Find thevaluefromS-Box, andstoreitin bit-form in thestatematrix(intermediate result)•S-box isa 16 x 16 matrix. •Example: input00010100 (0001 istherownumberand 0100 isthecolum) will producehexaFA (binary1111 1010):
•1111 1001 1111 1001
22
Another example:
•First byte is 0010 0101 to the S-Box
•Row value is 0010=2
•Column value is 0101 = 5
•Find the value in the position of row 2, and
column 5, say it is 3F (Hexavalue)
•Convert 3F to bits.
•0011 1111 is the output from the S box.
1111 1010

22. Block Ciphers
●There are several ways, so called Modes of Operation
○Electronic Code Book (ECB)
○Deterministic, Can be parallelized
○Cipher Block Chaining (CBC)
○Nondeterministic, Cannot be parallelized.
○Output Feedback (OFB)
○Nondeterministic, Cannot be parallelized.
○Cipher Feedback (CFB),
■Nondeterministic, Cannot be parallelized.
○Counter (CTR)
○Can be parallelized
○Galois Counter Mode (GCM)
23
Note!
In addition to confidentiality, some of these
modes provide authenticityand integrityof
blocks.

23. Stream Ciphers
29
Cryptology
CryptographyCryptanalysis
Symmetric
Cryptography
Asymmetric
CryptographyProtocols
Block CiphersStream
Ciphers

24. Stream Ciphers
Type of symmetric key crypto
Use a fixed length key to produce a pseudo-random stream of bits
Same key gets you the same keystream
XOR those bits with plaintext to encrypt
XOR those same bits with ciphertextto decrypt
Tries to approximate a one-time-pad.
30

25. Stream Cipher vs. Block Cipher
•Stream Ciphers•Encrypt bits individually•Usually small and fast àcommon in embedded devices
•e.g., A5/1 for GSMphones.•GSM(Global System for Mobile communication) is a digital mobile
network that is widely used by mobile phone users in Europe and other
parts of the world.
•Block Ciphers:•Always encrypt a full block (several bits)•Are common for Internet applications

26. Stream Ciphers -Overview
32
Plaintext bit-0Plaintext bit-1…Plaintext bit-n
Key Generator
Seed Key
Key bit 0Key bit 1…Key bit n
…Enc()Enc()Enc()
Ciphertext bit-0Ciphertext bit-1…Ciphertext bit-n

27. One-Time Pad (OTP)
●OTP cryptosystem by Gilbert Vernamin 1918, also known as VernamCipher
●Perfectly secure, if following holds
○Key has the same length as the message
○Key used only once
○Key is chosen randomly ( 0’s and 1’s)
●However, OTP is impractical due to key size
●Solution
○Stream ciphers
○Keystream generated in pseudo-random fashion from a relatively short secret key
33

28. Stream Ciphers -An approximation of OTP
●Use a secret, fixed size key to generate pseudo-random bits (keystream)
●XOR the key-stream with the plaintext to be encrypted
●XOR the same key-stream with ciphertext to decrypt.
●xi, yi, kiÎ{0,1}
Encryption: eki(xi) = xiÅki
Decryption:dki(yi) = yiÅki
34
Chapter 2 of Understanding Cryptographyby Christof Paar and Jan Pelzl
Note!
Same secretkey outputs the same keystream.

29. Symmetric Cryptography -Challenges
●Secure key distribution
●Number of keys
●Alice or Bob can cheat, because they have identical keys
35
2
3
4
5
1
10 key-exchanges for 5 users
1
2
3
n
...
n*(n-1) keys for n users, for n=10k, ~50M key-exchanges
2
Question: How many secret-keys
needed to be exchanged in order to set
up a system of n-users?
For10 000 usersweneed50 millionkey-exchanges!

30. Asymmetric Cryptography
36
Cryptology
CryptographyCryptanalysis
Symmetric
Cryptography
Asymmetric
CryptographyProtocols
Block CiphersStream
Ciphers

31. Asymmetric Cryptography -Key pair (Pu, Pr)
37
Enc()m InternetDec()m
Alice Bob
PuBob PrBob
Eve
c
(Bob’s public key)(Bob’s private key)

32. Asymmetric Cryptography -Analogy
●Based on the “good old mailbox” principle:
Everyonecan drop a letter
38
●But only the owner has the
corresponding key to open the mailbox

33. Shortcomings of Symmetric Crypto
In practice, can be used to offer confidentiality only
Not integrity, authentication, or non-repudiation
Easy to deny an act that used the secret key (non-repudiation is not ensured)
Key distribution problem
The secret key distribution must be done securely
Share the key with all parties that you want to communicate with
Large number of keys to manage
Each pair of users requires a distinct key
For !users, we need to establish !(!−1)/2=)(!!)keys;
e.g., For 1000 users, we need ~500K key exchanges
Each user is required to store (!−1)keys
39

34. Public Key Cryptography
Public Key Crypto: A cryptographic technique where both parties in the communication use
different keys
Allows you to encrypt with one key and have someone else decrypt the message with a
different keyPrivate
KeyPublic
Key
Alice Bob
40

35. Public Key Crypto Introduction
Maintain two keys per user: For !users, we only need to establish 2!keys
No need to exchange keys. Each user publishes one key and keeps the other
key secret.
Can have multiple uses:
Confidentiality
Send secret messages to someone
Integrity:
Ensure something wasn’t modified
Authentication/nonrepudiation
Prove who created a message
Deniability of symmetric encryption is addressed.
41

36. Public and Private Keys?
Every user has two keys: A public key and a private key
Public key: Not a secret. Anyone can have it
Private key: Secret. Only the owner can have it
Mathematically related pair of keys that allow you to encrypt with one
and decrypt with the other
42

37. Asymmetric Encryption
Encryption with the public key
C = EPUB-Alice(M)
M = DPRIV-Alice(C)
Encryption with the private key
C = EPRIV-Alice(M)
M = DPUB-Alice(C)
PUB_K = Public key; PRIV_K = Private key
Plaintext M
Ciphertext
C
PUB_KPRIV_KPUB_kPRIV_k
43

38. Addressed Challenges
●Key distributionwithout a pre-shared secret*, e.g., DH key exchange
●Non-repudiationvia digital signatures to provide message
integrity/authenticity, e.g., RSA, DSA, ECDSA
●Identification/Authenticationusing challenge-response protocols
●Encryption, e.g., RSA, ElGamal
○Rarely used in practice, because of performance
○~1000 times slower than symmetric algorithms
○Rather hybrid encryption, combining asymmetric and symmetric cryptography
44
*) assumption for now, public keys need to be authenticated
Chapter 6 of Understanding Cryptographyby Christof Paar and Jan Pelzl

39. How to Build Asymmetric Crypto Systems
●Asymmetric crypto systems are based on a “one-way function” f()
○Computing y = f(x)is computationally feasible (easy)
○Computing x = f-1(y)is computationally infeasible (hard)
●One-way functions arebased on mathematically hard problems
○Factoring integers(RSA, Rabin, …)
■Given a composite integer n, find its prime factors (hard)
■Note that to multiply two integers (primes) is easy
○Discrete Logarithm (Diffie-Hellman, ElGamal, DSA, ...)
■Given a, x, m, finding yin axmod m = y is easy
■Given only a, m and y, finding xin axmod m = y is hard
■2nmod 17 = 16, What is the value of n?
○Elliptic Curves(ECDH, ECDSA): Generalisationof the discrete logarithm
45

40. Public Key Crypto for Confidentiality
If Alice wants to send a message, M, to Bob…
She computes CT = EPUB-Bob(M) and sends it to Bob
Bob decrypts it by calculating M = DPRIV-Bob(C)
Who can perform the decryption?
Only Bob, with his private key
Who can perform the encryption?
Anyone, because Bob’s public key is public
BobAlice
CT
47

41. Public Key Crypto for Confidentiality
What if Bob wants to reply to Alice?
He should encrypt the message with Alice’spublic key EPUB-Alice(M’)
(Same way Alice sends a message to Bob)
48

42. Problem of Asymmetric Cryptography #1: Slow
Public key cryptography is very slow
Decryption speeds ~100 times slower than symmetric algorithms (in
software)
AES-128: 100 MB/s (symmetric cryptography)
RSA-1024: 1 MB/s (asymmetric cryptography)
Using this for big files would be horrible
49

43. Problem #1 Solution
Hybrid crypto: In practice, we combine symmetric and asymmetric
tools
1.Key exchange is done using (slow) asymmetricalgorithms (not too bad
since key is small)
2.Encryptionfor confidentiality is done by using (fast) symmetricciphers
(block or stream ciphers)
Most cryptography on the internet is based, in part, on this concept
50

44. Using Hybrid Crypto
If Alice wants to send Bob a message M, she…
Chooses a random symmetric key, k
Computes CTk= EPUB-Bob(k) and sends it to Bob
Computes CT = Ek(M)and sends it to Bob
Bob uses his private key to decrypt CTkinto kand then uses kto
decrypt CTand get the message
Alice and Bob can continue their session of communicating encrypted
messages using the shared symmetric key k.
51

45. Hybrid Encryption
52
Chapter 6 of Understanding Cryptographyby Christof Paar and Jan Pelzl
c1= enc(PuBob,K)c1
Key Exchange
(asymmetric)
c2= AESenc(K, m)
Data Encryption
(symmetric)
(PuBob,PrBob)
PuBob
Chooses a random
symmetric key K
Uses Kto encrypt
message m
K= dec(PrBob,c1)
c2
Uses Kto decrypt
ciphertext c2
m= AESdec(K,c2)
Bob
Alice

46. Problem #2: No Integrity and No Authenticity
Let’s add Eve, a malicious attacker who can
interceptand modifymessages
Alice computes CT = EPUB-Bob(M) and sends it to
Bob
Eve intercepts it, throws it away
Eve computes CTevil= EPUB-Bob(Mevil) and sends it to
Bob
Bob decrypts it, can’t tell that it isn’t from Alice
BobAlice Eve
CT CTevil
53

47. Problem Explained
Our current technique provides confidentiality, but not integrity and
authenticity
Eve couldn’t read the message from Alice
Eve replaced the message and Bob didn’t know
Solution?
54

48. Public Key Crypto for Integrity
If Alice wants to send a message, M, to Bob that proves it is from her
She computes digital signature DS = EPRIV-Alice(M) and sends it to Bob
Bob decrypts it by calculating M = DPUB-Alice(DS)
Who can perform the encryption?
Only Alice, with her private key
Who can perform the decryption?
Anyone, because Alice’s public key is public
BobAlice
DS
55

49. Public Key Crypto for Integrity
Bob knows the message is from Alice because
Only Alice could have produced it
Integrity: No one could have changed it
Authenticity: It can only come from Alice
Non-repudiation: Alice can not deny sending the message as she is
the only one knowing the secret key
Notice this doesn’t offer confidentiality
We call this a digital signature
Alice is simply signing the message to prove it is from her
56

50. Digital Signatures
57
Cryptology
CryptographyCryptanalysis
Symmetric
Cryptography
Asymmetric
CryptographyProtocols
Block CiphersStream
Ciphers
Digital
Signatures

51. Use Case
●Bob orders a pink car from the car saleswoman Alice
●After seeing the pink car, Bob states that he never order it
●How can Alice prove towards a judge that…
○…Bob indeed ordered the pink car?
○…Alice did not fabricate the order herself?
58
Answer:
❖By usingasymmetric cryptography, more specifically
digital signatures.

52. Basic Idea
59
Chapter 10 of Understanding Cryptographyby Christof Paar and Jan Pelzl
S’ := ver(PuBob,S)
PuBob
(m,S)
(PuBob,PrBob)
BobAlice
S
mS := sig(PrBob,m)
truefalse
S’ ≟S

53. Public-Key Signature Process
60

54. Cryptographic Protocols
61
Cryptology
CryptographyCryptanalysis
Symmetric
Cryptography
Asymmetric
CryptographyProtocols
Block CiphersStream
Ciphers

55. Cryptographic Protocols -Example Zero-Knowledge-Proof
62The Ali Baba cave
source: https://en.wikipedia.org/wiki/Zero-knowledge_proof
•Zero-Knowledge Proof (ZKP) is a technique to define whether the provided
data is true without revealing it.
•ZKP resolves two main parties; a prover and a verifier
•It is a way for a prover to convince a verifier that the data is accurate without
revealing any underlying information.

56. Zero Knowledge Proof: Ali Baba Cave
●In cryptography, a zero-knowledge proofor zero-knowledge protocolis a method by which one
party (the prover) can prove to another party (the verifier) that a given statement is true while the
prover avoids giving any additional information apart from the fact that the statement is indeed
true.
●A story presenting the fundamental ideas of zero-knowledge proofs, based on the Ali Baba cave.
●In this story, Alice has uncovered the secret word used to open a magic door in a cave.
●The cave is like a ring, with the entrance on one side and the magic door blocking the opposite
side.
●Bob wants to know whether Alice knows the secret word; but Alice, being a very private person,
does not want to reveal the secret word to Bob.
●They label the left and right paths from the entrance A and B.
●First, Bob waits outside the cave as Alice goes in.
●Alice takes either path A or B; Bob is not allowed to see which path she takes.
●Then, Bob enters the cave and shouts the name of the path he wants her to use to return, either A
or B, chosen at random.
●Providing she really does know the magic word, this is easy: she opens the door, if necessary,
and returns along the desired path.63

57. Hash Functions
64
Cryptology
CryptographyCryptanalysis
Symmetric
Cryptography
Asymmetric
CryptographyProtocols
Block CiphersStream
Ciphers
Hash
Functions
Hash
Functions

58. One-Way Functions -Fruits to Juices
65
Easy
Hard

59. Formal Definition of One-Way Functions
●Hashing maps arbitrary long message to a fixed size message.
●A function f:{0,1}*→ {0,1}*is one way function, if:
●fis publicly available, and requires no secret forits operation
●Given x, it is easy(in polynomial time algorithm) to computef(x)
●Given y, in range off, it is hard to find x, where y = f(x)
66

60. Properties of a Cryptographic Hash Function
h = H(m). Hash(Variable size message m) to produce a fixed size hash
value(sometimes called a message digest)
Efficient computation
Pseudorandom (small change of myields a big change of h)
Cryptographic hash function has 2 properties:
1.Pre-image Resistant (the one-way property): Infeasible to determine m
from H(m)
2.Collision Resistant (the collision-free property): Infeasible to find any two
messages m1and m2such that m1≠ m2 and H(m1) = H(m2)
67

61. Analogy
68
•The size of the hash is always fixed
•Does not depend on the size of the input data.
•No two distinct data sets (plain texts) are able to produce the same hash.
•If it does happen, it's called a collision

62. Java Code to Create MD5 Hash
69

63. Java Code for SHA Hashing
70

64. Simple Python Code for SHA Hashing
71
import hashlib
md = hashlib.sha256(b"Thequick brown fox jumps over the lazy dog").hexdigest()
print (md)
SHA256Data (??-bits)Hash (256 bits)
d7a8fbb307d7809469ca9abcb0082e4f8d5651e46d3cdb762d02d0bf37c9e592
# byte string b

65. Definition of Cryptographic Hash Functions (CHFs)
●Functions that compress arbitrarily long messages to fixed-size messages
H({0,1}*) → h ∈{0,1}n
●H(m)=hm is efficiently computed
●H-1(hm)= m is hard to reverse
72
“It's no use going back to yesterday,
because I was a different person then.”
“We are all mad here.”
“We are all sad here.”
0x9632D312AF
0x3AEB342A14
0x876BB2CD1F
H
H
H

66. Application of CHFs -File integrity
73

67. Application of CHFs -User authenticity
74

68. Application of CHFs -Password storage
75

69. Applications of Hash Functions
Message Authentication: Integrity + Source Authentication
Integrity to ensure that the message has not been modified in transit
Source Authentication: the receiver is assured of the origin of the message
Encrypt hash using a shared secret key
Digital Signatures: Encrypt hash with private key to ensure Integrity +
Source Authentication + Non-repudiation
Password storage: Stored hashed password with a salt.
When a user enters a password, the hash of that password is compared to the
stored hash value for verification
Hackers can not get password from storage.
More!
Detect errors in file transfers.
Pseudorandom number generation: Hash an IV, Hash the hash, …, repeat 76

70. Application: File Transmission
77https://en.wikipedia.org/wiki/MD5

71. Verifying Data using Checksum
Verify whether the stored data (or file) or during transit between two
environments has been tampered with.
Remember: the hash function always produces the same output for the same given
input,
Compare a hash of the source file with a newly created hash of the destination file
to check that it is intact and unmodified.
For this, we generate
a hash of the data called the checksum before storing or transferring.
We generate the hash again before using the data.
If the two hashes match, we determine that the integrity check is passed and
the data has not been tampered with.
78

72. Application: Password Storage
When designing an application that stores passwords, don’t store them in plaintext
If someone steals your password file, then they have all the user passwords!
Store salted hashed passwords instead
A saltisrandom data (similar to nonce) that is concatenated with the password then
hashed.
The primary function of salts is to defend againstdictionary attacks.
79=> Using a different salt produces a different hash

73. Kerckhoffs’sPrinciple
80
Auguste Kerckhoffs
1835-1903
§“The securityof a cryptographicalgorithmshall depend solelyon the
confidentiality of the key, and not on the confidentiality of the algorithm
used.”
source: https://wikisource.org/wiki/Auguste_Kerckhoffs

74. How to Achieve Kerckhoffs’sPrinciple in Practice?
●Use only widely accepted ciphers that have been cryptanalyzed for several
years by well-known cryptographers
●Use such ciphers only with recommended security parameters
●Use only widely accepted implementations of such ciphers
81
Note!
Do not rely onsecurity through obscurity.

75. What is Cryptanalysis, and why do we need it?
●There is no mathematical security proof for any practical cipher
●Whether a cipher is secure is based on try to break it or fail
○Cryptanalysts try to break ciphers, and if they can’t, we assume those to be secure
○But, time has shown that such assumption may be false, e.g. Needham–Schroeder protocol
82
§“The technique of obtaining informationabout the content of a ciphertext
without knowing the key”

76. Cryptanalysis: Attacking cryptosystems
83
Cryptanalysis
Classical
Cryptanalysis
Implementation
Attacks
Social
Engineering
Mathematical
AnalysisBrute ForceOthers

77. Brute Force
●Considers the cipher as black-box, but requires at least a pair (m0, c0)
●Check for all k ∈K, dec(k, c0) = m0
84
Key size in bitKey spaceSecurity lifetime
64264 Short-term (few days or less)
1282128Long-term (several decades, in the absence of quantum computers
-are in their baby steps)
2562256Long-term (also resistant against quantum computers)

78. Brute Force Attack vs. Dictionary Attack
85

79. Cryptanalysis: Attacking cryptosystems
86
Cryptanalysis
Classical
Cryptanalysis
Implementation
Attacks
Social
Engineering
Mathematical
AnalysisBrute ForceOthers

80. Other attacks in Cryptanalysis
●Ciphertext Only Attack (COA)
•An attack model for cryptanalysis where the attacker is assumed to get access only to a set of
ciphertexts, but no knowledge of the plain texts or encryption key.
•The attack is completely successful if the corresponding plaintexts can be deduced (extracted) or,
even better, the key.●Known Plaintext Attack (KPA)•Where the attacker has access to both the plaintext (called a crib), and its ciphertext. ●Chosen Plaintext Attack (CPA)•The attacker can obtain the ciphertexts for arbitrary plaintexts. •The attacker can choose specific ciphertexts and observe the corresponding plaintext.•The goal of the attack is to gain information that reduces the security of the encryption scheme.●Chosen Ciphertext Attack (CCA)•Where the cryptanalyst can gather information by obtaining the decryptions of chosen ciphertexts. •From these pieces of information the adversary can attempt to recover the hidden secret key used
for decryption.•Classical attacks
•Mathematical Analysis
•Brute-Force Attack
87

81. Resources
●This is a handy tool where you can get all basics of cryptography with example:
https://www.cryptool.org/en/cto/
●Quisquater, J-J. et al. How to Explain Zero-Knowledge Protocols to Your Children. Advances in
Cryptology –CRYPTO '89: Proceedings. Lecture Notes in Computer Science. Vol. 435. pp. 628–631
●Kerckhoffs, A. La cryptographie militaire. Journal des sciences militaires. IX: 5–83
●Kerckhoffs, A. La cryptographie militaire. Journal des sciences militaires. IX: 161–191
●Needham, R., and Schroeder, M. Using encryption for authentication in large networks of
computers. Communications of the ACM, 21(12)
●Denning, D., and Sacco, G. Timestamps in key distributed protocols. Communication of the
ACM, 24(8):533--535
●Lowe, G.An attack on the Needham-Schroeder public key authentication protocol. Information
Processing Letters, 56(3):131—136
88