Scribd
Upload
226 views27 pages

Cryptography and Information Theory: Brute Force and Cryptanalysis

This document discusses brute force attacks and cryptanalysis techniques for breaking encryption. It begins by defining a brute force attack where an attacker tries all possible keys until finding the correct one. Cryptanalysis is then discussed as studying the cryptosystem to decipher messages without the key. Different types of cryptanalysis attacks are presented like ciphertext-only, known-plaintext, and chosen-plaintext attacks. The document concludes by introducing the concept of perfect secrecy achieved by the one-time pad where the key entropy equals the message entropy.

Uploaded by

Shorya Kumar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
226 views27 pages

Cryptography and Information Theory: Brute Force and Cryptanalysis

This document discusses brute force attacks and cryptanalysis techniques for breaking encryption. It begins by defining a brute force attack where an attacker tries all possible keys until finding the correct one. Cryptanalysis is then discussed as studying the cryptosystem to decipher messages without the key. Different types of cryptanalysis attacks are presented like ciphertext-only, known-plaintext, and chosen-plaintext attacks. The document concludes by introducing the concept of perfect secrecy achieved by the one-time pad where the key entropy equals the message entropy.

Uploaded by

Shorya Kumar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 27

Cryptography

and
Information Theory

Brute Force and Cryptanalysis

Sang-Yoon Chang, Ph.D.


Module Objectives

1. Brute Force Attack

2. Cryptanalysis

3. Perfect Secrecy
Brute Force Attack

Attacker tries all possible keys until


it finds the correct key

Attacker selects the keys (to try) randomly

Assume that attacker can distinguish the


correct and the incorrect key after trials
Information Entropy Key Strength
Information Entropy Key Strength

Attacker Effort
00

01

10
Entropy = 2 bits
11
00 Incorrect

01

10
Entropy = log23 bits
11
Brute Force Attack

With keys that are “n” bits long,


there are 2n possible keys

Attacker can succeed in the attack


in the 1st try (best case) or the
last try (worst case; 2n tries)

On average, attacker will try 2n-1 tries


Cryptanalysis

Studying and analyzing the


cryptosystem in order to
effectively decipher the coded
message without the key
Cryptanalysis

Attacker can know which keys are


more likely than others

Use the information to more quickly


find the key

The non-uniform distribution of the key


selection yields entropy reduction
Cryptanalysis

Plaintext Enc Ciphertext

Key

Computing ß à Communication/
Networking
Ciphertext-Only Attack

Plaintext Enc Ciphertext

Key

Computing ß à Communication/
Networking
Known-Plaintext Attack

Plaintext Enc Ciphertext

Key

Computing ß à Communication/
Networking
Known-Plaintext Attack

Plaintext Enigma Ciphertext

Key
E.g., in WW2, Key
Weather, “Nothing
Computing ß à Communication/
to report” Networking
Chosen-Plaintext Attack

Plaintext Enc Ciphertext

Key

Computing ß à Communication/
Networking
Chosen-Plaintext Attack

Plaintext Enigma Ciphertext

E.g., in WW2,
Location Key
(staging events)
Computing ß à Communication/
Networking
Perfect Secrecy

Ciphertext provides no information


about the plaintext without the key

Holds regardless of the attacker’s


computational capabilities

Cryptanalytically unbreakable
One-Time Pad

The key entropy is as great


as the message entropy,
even as the message grows

Achieves perfect secrecy


Practicality of One-Time Pad

Two challenges that limit its practicality:


• Key and randomness generation
• Key distribution and agreement

Examples of its use:


• Low-bandwidth applications (small
messages)
• Cryptosystem design, e.g., key refresh
Practicality of One-Time Pad

Two challenges that limit its practicality:


• Key and randomness generation
• Key distribution and agreement

Examples of its use:


• Low-bandwidth applications
(e.g., mission-critical messages)
• Cryptosystem design, e.g., key refresh

You might also like