Cryptography Flashcards
When do we have secure communication?
When there is no tampering (integrity) or eavesdropping (confidentiality)
When do we have secure data storage?
No information leakage (confidentiality) or tampering (integrity)
What are the 2 steps of secure communications?
- Establish a secret key (face-to-face, trusted courier, handshake algorithms)
- Transmit data using the shared secret key
Name 6 ciphers that provides confidentiality
Polybios
shift cipher
Vigenére method
One time pad
Stream cipher
Block cipher
What ciphers provide integrity?
ECB
HMAC
Describe the Polybios cipher
Partition the alphabet in a grid.
Each plaintext letter is represented by 2 number (row, col)
What is the shift cipher?
Each letter is a number: A-0, E-4
K: Encryption key
Enc:
C = (M + K) mod 26
Dec:
M = (C - K) mod 26
Why is the shift cipher insecure?
Only 26 keys
Monoalphabetic - one plaintext alphabet to ciphertext alphabet mapping.
Plaintext is easily recognizable during brute force
Describe the Vigenére cipher
Key is a string
Shifts each plaintext character with the amount dictated by the character of the key
Compare Vigenére and shift
Vigenére: Larger key space
Key length n: Keyspace = 26^n
Brute force is expensive
When is Vigenére insecure?
Given a long ciphertext.
If key length is n, then every n character is encrypted using the same character.
This can be used to break the cipher
How can the period of the Vigenére cipher be broken?
Make a guess for n, and divide the ciphertext into sub-block containing letters encrypted using the same key.
Run a frequency analysis on the sub-blocks. When the period value is correct, the requency distribution should mirror the frequency distribution og the english language.
For each sub-block, calculate the similarities of the frequencies in the sub-blocks and in the english language
Calculate the avarage value of the similarities of all sub-blocks.
Of the guessed period, choose the period with the highest avarage similarity.
How can Vigenére be broken, when we know the period?
Extract the sub-blocks of the ciphertext, using the period n.
Run a frequency analysis on each block. Compare it to the english language to figure out what ciphertext letters represent which english letter. Use this to find the ciphertext representation of the most common letter in the english alphabet (such as E).
When this is done, we know the Key for the block.
Do this for each block to put together the whole key
What is the one time pad?
Enc:
C = P XOR Key
Dec:
P = C XOR Key
Perfect security
What is perfect secrecy?
Observing the ciphertext should not change the attacker’s knowledge about the distribution of the plaintext.
What are some limitations of the one time pad?
Key must be atleast as long as the plaintext
New key for each message
How can the OTP be misused?
Use the same key to encrypt 2 or more messages. The cipher is then no longer perfectly secure.
How can OTP be broken when two ciphertext are encrypted using the same key?
C1 = m1 XOR k
C2 = m2 XOR k
C1 XOR C2
= m1 XOR k XOR m2 XOR k
= m1 XOR m2 XOR (k XOR k)
= m1 XOR m2
m1 XOR m2 reveals information about m1 and m2
Info:
- All letters in binary begins with 01
- XOR-ing 2 letters will there for being with 00
- Space begins with 00
- XOR letter with space gives 01
Does OTP provide integrity?
No
What is quantum key distribution
utilizes the unique properties of quantum mechanical systems to generate and distribute cryptographic keying material using special purpose technology
What issue does stream ciphers address?
OTP key is as long as the message
What is the idea behind stream ciphers?
Use a short key k as a seed
Generate a pseudo ransom key k’
k’ is as long as the message
Use k’ for OTP enc and dec (XOR)
What is the flow of stream ciphers from the sender?
key -> PRG -> k’ XOR P -> C
What is the flow of stream ciphers from the receiver?
key -> PRG -> k’ XOR C -> P
What issue does block ciphers also try to be a solution for?
OTP long key issue
How does block ciphers work
Split P into similar sized blocks
Enc/Dec each block using a short key
How does DES work?
Feistel cipher
56 bit key
Key expansion: 48 bit round key for each block
One plaintext block of 64 bits passes through 16 rounds of the round functions
The result is a 64 bit ciphertext block
What is 3DES?
Block: 64 bits
K = 168 / 112 / 56 bits
48 rounds
What is the round function of DES?
Apply 48 bit key to the 32 rightmost bits to produce a 32 bit output
Then, the rightmost 32 bits are swapped with the leftmost 32 bits.
Flow:
- 32 bit input block is expanded to 48 bit (P-box)
- Block is XORed with 48 bit key
- 48 bit output is split into 8 6-bit blocks
- The 6-bit blocks is sent trough an S-box, which provides a 4 bit output
- The resulting 32 bits are sent to a Straight P-box which outputs 32 bits
What is used to split plaintext into blocks, and chain the blocks?
Mode of operation
Describe the ECB mode of operation?
P is split into blocks of size n, add padding if necessary.
All blocks uses the same encryption key sets generated from identical key and key expansion function
Round function is identical for each block
Describe the CBC mode of operation
IV
Padding
Round 1:
Enc(IV XOR P, K)
Round 2:
Enc(Ci-1 XOR P, K)
Dec:
Dec(C, K) XOR Ci-1
Dec(C, K) XOR IV
Describe AES
Block: 128
Key: 128, 192, 256
Rounds: 10, 12, 14
What are some tips when using block ciphers?
Choose right cipher (DES, 3DES, AES)
Choose right mode of operation (do not use ECB)
Compare stream vs. block ciphers
Stream: fast
Block: slow
Stream: Good for cases when we don’t know the size of data, or it is continuous (e.g. network streams)
Block: Godd when we know data-size (e.g. file, data fields, request/response protocols)
Stream: Cannot provide integrity
Block: Can provide integrity
What is MAC
Message Auth code
provides Integrity
Hash message before transmission creating a tag.
Send message and tag.
Receiver verifies tag.
A:
Tag: G(K, m)
B:
Verify Tag: V(K, m, tag) = ‘yes’?
What is enhanced CBC?
Generate tag:
G(K, K1, m, IV)
Verify:
V(K, K1, m, tag, IV) = ‘yes’
Describe hash functions
Various sized input -> fixed size output
Properties:
- Collision resistant
- Pre-image resistant
- Second preimage resistant
What is coliision resistance?
Hard to find M1 and M2 such that h(M1) = h(M2)
What is preimage resistance?
Given h, hard to find a M such that h(M) = h
What is HMAC?
Hash-MAC
Uses hash functions to generate a tag.
Generate:
G(K, m)
Verify:
V(K, m, tag)
What is the format of HMAC?
T = H((k XOR opad) || H((k XOR ipad), M))
ipad: inner pad
opad: Outer pad
What are 3 strategies to compine confidentiality and integrity?
MAC-then-Encrypt (TLS)
Encrypt-and-MAC (SSH)
Encrypt-then-MAC (IPSec)
What is encrypt-then-mac?
Encrypt message, then create a mac from the encrypted message.
What are the building blocks of Public key encryption?
KeyGen: Output PK and SK
One-way trapdoor function F(PK, x)
Inverse function F^-1(SK, y)
What is a one-way function?
Computing y = f(x, k) is easy
Computing x = f^-1(y) is difficult
What is a trapdoor function?
When we have a secret key, computing the inverse of the function becomes easy
How does digital signatures work?
B hashes M
B signs h(M) using B’s secret key and F^-1
Sends M and signature
Signature: F^-1(SK, H(m))
A has M, signature and PK
Check if F(PK, Sig) = H(m)
When an entity receives a public key, how can they know that it is the public key of a certain other entity and not a public key issued by an attacker?
Certificates issued by a CA
What must a certificate include?
A public key
The CA’s signature
Identity of issuer and subject
Describe the TLS handshake
Before handshake:
Client A has:
PKca
Server B has:
PKca, PKb, SKb, Cert
Handshake:
1. Client Hello
2. Server Hello: Cert
Now A has PKb from Cert
3. A generates a secret key C and encrypt using PKb, sends c
4. ClientKeyExcange: c
5. B decrypts c using SKb to get K
A and B now have the same key K
What is a known attack on TLS 1.2?
Raccoon attack
Compare RSA and ECDSA
RSA:
- Simple, effective
- Widely used (SSL, TLS)
- Prime factorization
ECDSA:
- Higher complexity, faster
- Shorter keys (+ elliptic curve)
- limited support
- y^2 = x^3 + ax + b
What is Kerchoff’s principle?
The only secret is the key, and must be chosen at random
It is easier to change key than change algorithm
Makes standardization and public validation possible
