Cryptography Midterm

What is confidentiality?

Prevent access by unauthorized users

What is integrity?

Data is not modified without being detected

What is authenticity?

Data is from the claimed sender

What is non-repudiation?

You can’t deny what you have done

What are the elements of the encryption process?

Plaintext + key → encryption algorithm → ciphertext

What are the elements of the decryption process?

Ciphertext + key → decryption algorithm → plaintext

Should a cipher’s algorithm be published or kept secret? Why?

Publish the algorithm and keep only the key secret. Attackers will probably learn the algorithm anyway, and publishing lets the good guys try to crack it for free, which exposes weaknesses. Most commercial algorithms are published, while most military ones are not.

What is the fundamental tenet of cryptography?

If lots of smart people have failed to solve a problem, it probably won't be solved (soon).

How does key size affect security?

Security depends on how much work an attacker needs to break the cipher. A longer key means more possible keys to try in a brute-force search. Each additional bit doubles the work.

What is the main feature of symmetric (secret key) cryptography?

The same key is used for both encryption and decryption.

• Encryption: c = E_k(m)

• Decryption: m = D_k(c)

Name well-known symmetric key algorithms.

DES, 3DES, AES

What is the main feature of asymmetric (public key) cryptography?

Different keys are used for encryption and decryption. Each user has a private key “d” and public key “e”.

• Encryption: c = E_e(m)

• Decryption: m = D_d(m)

Name well-known public key algorithms.

RSA and ECC

In a public/private key pair, which key is secret and which is public?

The private key (d) is known only by its owner, and the public key (e) is known by the world.

In public key crypto, which keys provide confidentiality?

The sender encrypts with the receiver's public key and the receiver decrypts with her own private key. Only the receiver holds the private key, so only she can read the message.

What is the tradeoff between security and performance?

Stronger security (longer keys, more complex algorithms) costs more computation and time, and it also adds complexity. Complexity is the worst enemy of security.

What are the basic properties of a block cipher?

It has a constant (fixed) key size and a constant input/output size, and the input size equals the output size (e.g., DES: 64-bit block, 56-bit key). For a given key it acts as a one-to-one mapping (a random-looking permutation) that looks completely random to anyone who doesn't know the key.

What does "random permutation" mean for a block cipher? What does it not mean?

The key selects a key-dependent permutation table over whole blocks, so each possible input block maps to a unique output block. It does not mean the bits of the plaintext are simply shuffled.

How does 3DES work (encryption and decryption)?

as EDE (encrypt-decrypt-encrypt) with keys K1, K2, K3. In the standard usage K1 is set equal to K3.

• Encryption: c = E_k3(D_k2(E_k1(m)

• Decryption: m = D_k1(E_k2(D₃(c)

Why was 3DES created?

To expand the key size from 56 bits to more than 80 bits or so.

Why use EDE instead of EEE in 3DES?

EDE is backward compatible with single DES. If K1 = K2 = K3.

Why not just use double DES with the same key twice (encrypt with K1, then K1 again)?

It gains nothing. The good guys do 2x the work of DES, and so do the bad guys, because they can still brute-force a single 56-bit key (trying each key and double-encrypting costs only 2x per guess). The security level stays at 56 bits.

Why not double DES with two different keys (encrypt with K1, then K2)?

Because of the meet-in-the-middle attack. The effective security is far less than the 112 bits you'd expect.

How does the meet-in-the-middle attack work on double DES?

The attacker needs a known <m, c> pair.

1. Encrypt m under every possible K1 and store the results in a table.

2. Decrypt c under every possible K2 and look for a match in the table.

3. A match gives candidate keys (K1, K2), which can be checked with a second <m, c> pair.

The work is about 2⁵⁷ operations

Why is padding needed?

Block ciphers encrypt fixed-size blocks, so a message that isn't an exact multiple of the block size must be extended to fill the last block.

What makes a padding method good or bad?

The padding must be reversible: the receiver must be able to tell exactly where the real message ends and remove the padding unambiguously. Appending zeros is bad because if the message itself ends in zeros, the receiver can't tell which zeros were original.

Why is at least one byte of padding added even when the message is already an exact multiple of the block size?

So the receiver can always assume padding is present and remove it. If padding were skipped for exact-length messages, the receiver couldn't tell whether the last bytes were padding or real data.

What are the two padding methods from the slides?

• Append a 1 bit followed by zeros (1000…0).

• Append n bytes, each with value n, where n is the number of padding bytes needed.