Cryptography

Question 1

SIDH

Answer 1

Supersingular Isogeny Diffie-Hellman

Question 2

SIKE

Answer 2

Supersingular Isogeny Key Encapsulation

Got through round 3 of the NIST PostQuantum process
Broken in 2021 by researchers using difficult elliptic curve theory.

Question 3

SSL/TLS

Answer 3

Secure Socket Layer/Transport Layer Security

Question 4

Secure Communication Example

Answer 4

Starting with a message in a chest
1. Lock the chest with padlock A
2. Send to B
3. Lock the chest with padlock B
4. Send to A
5. Unlock padlock A
6. Send to B
7. Unlock padlock B

And then B ends up with the message without anyone inbetween having been able to read it

Question 5

Diffie-Hellman Algorithm

Answer 5

Represent data as intergers modulo a large prime P
1. A will rase x to a power a (x^a)
2. Send to B
3. B will raise to a power b (x^ab)
4. Send to A
5. Take ath root (x^b)
6. Send to B
7. Take bth root (x)

B now has the unencrypted message
If we could take logarithms the message could be unecrypted by a third party but for an appropriate P we can’t do that efficiently.

Question 6

Secure Key Agreement

Answer 6

Everyone knows both large prime P and x
1. A and B pick their powers
2. Raise x to them
3. Exchange results
4. Raise results to their powers

Now both A and B have x^ab which they can use as a key for an efficient cipher such as AES

Question 7

RSA Public/Private Key Communication

Answer 7

1. A selects two distinct prime numbers P and Q, which must be
   sufficiently large and sufficiently ‘random’ to ensure that no
   adversary could factor N = PQ except by luck.
2. A then chooses a number x relatively prime to
   ϕ(N) = (P − 1)(Q − 1) and publishes the values of N and x.
3. Anyone wishing to send a message to A then divides it up into
   digits to the base N (taking care to avoid extremely small
   digits) and transmits each digit a by sending ax (mod N)
4. A decodes by computing x-th roots, since she knows P and Q

Question 8

Man-in-the-middle

Answer 8

In Diffie–Hellman (and many others), our attacker E can pretend to be B to A, and A to B, so each thinks they have a secure channel to the other, whereas in fact they have a secure channel via E, who decrypts and re-encrypts the messages. This is why TLS requires signatures to prevent this.

Question 9

Meet-in-the-middle

Answer 9

If ek (m) is implemented as ek1 (ek2 (m)), you might think we had to guess all combinations of (k1, k2). But under a Known Plaintext Attack (we know m and c, and want k), we compute (and store!) ek1 (m) for all possible k1, then start computing dk2 (c) and look for a match.

Question 10

DES

Answer 10

• Data Encryption Standard
• 56-bit key
• 64-bit blocks

Question 11

2DES

Answer 11

• e_{k1, k2}(m) = e_k1(ek2(m))
• a meet in the middle attack requires 2^57 operations (144 petaops)

Question 12

3DES

Answer 12

• e{k1,k2,k3}(m) = ek1(dk2(ek3(m)))
• k1 = k2 = k3 is just DES

Question 13

AES

Answer 13

• 128-but blocks
• 128/192/256 bit keys
• it is possible to break related 192-bit keys in 2^176 operations and related 256-bit keys in 2^99.5 operations

Question 14

Hashes

Answer 14

An n-bit hash function reduces an arbitrary message to an n-bit
string: h(m) ∈ [0, 2n − 1].

Question 15

Collision Resistance

Answer 15

it is hard to find two messages m1 != m2 with h(1) == h(m2)

Question 16

Pre-image Resistance

Answer 16

given v is it hard to find m with h(m) = v

Question 17

SHA-1

Answer 17

descendant of MD5, deprecated in 2010

Question 18

SHA-2

Answer 18

comes in a variety of size, e.g. SHA224

varying strengths, still viable

Question 19

SHA-3

Answer 19

current hashing algorithm recommendation

Question 20

Password Hashing

Answer 20

want a slower hashing algorithm to make brute force and dictionary attacks harder

often slowed down by performing the hash 10000 times

Argon is a password specific hash

Question 21

Cryptographically Secure Pseudo-Random Numbers

Answer 21

requirements
* next bit - given the first k bits of a random sequence there is no polynomial-time algorithm that can predict the (k+1)th bit with probability of success non-negligibly better than 50%
* state compromise - if part or all of its state has been revealed it hsould be impossible to reconstruct the stream of random numbers prior to the revelation

CSPRNGs
* ChaCha2.0 - Linux
* AES in counter mode

Question 22

CSPRNG Warnings

Answer 22

require a random seed to start them off

see difference between /dev/random and /dev/urandom

Question 23

Cloudflare Seeds

Answer 23

cloudflare uses physical randomness to generate the seeds
* main HQ - lava lamps
* london HQ - double pendulum
* singapore HQ - uranium radioactive decay

Question 24

ECB

Answer 24

Electronic Codebook

each message block is encoded separately, c_i := e_k(m_i), this is open to frequency and pattern attacks

Question 25

CBC

Answer 25

cipher block chaining c_i = e_k (m_o ⊕ ci−1). c_0 is a supplied “initialisation vector”. Encryption is serial.

Question 26

CTR

Answer 26

Counter Mode ci = mi ⊕ ek (i), i.e. a counter is encrypted, and the result X-ored with the input. Encryption can be parallel.

Question 27

GCM

Answer 27

Galois/Counter Mode.

Question 28

Harvest Now Decrypt Later

Answer 28

collect sensitive communications, break the ECDH in 10 years time and read the secrets

Question 29

Grover Algorithm

Answer 29

uses quantum computing for attacking hashes and block cipher

Question 30

Shors Algorithm

Answer 30

uses quantum computer for attacking RSA, Diffie-Hellman, EC Diffie-Hellman and ECDSA

Question 31

ML-KEM

Answer 31

quantum proof key encapsulation chosen by NIST bob will encapsulate the key with alices public key and then pass this to alice where she can decrypt it with her private key and reveal the shared key | formerly called Crystals-Kyber