Security and Cryptography just by images

Pascal Lafourcade

► To cite this version:

Pascal Lafourcade. Security and Cryptography just by images. Doctoral. Grenoble, France. 2009, pp.52. hal-04449291

HAL Id: hal-04449291

https://uca.hal.science/hal-04449291v1

Submitted on 9 Feb 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Security and Cryptography just by images

Pascal Lafourcade

<figure><img src="image_2.png" /></figure>

<figure><img src="image_3.png" /></figure>

2009

pascal.lafourcade@imag.fr
Applications

<figure><img src="image_4.png" /></figure>

<figure><img src="image_5.png" /></figure>

<figure><img src="image_6.png" /></figure>

<figure><img src="image_7.png" /></figure>

<figure><img src="image_8.png" /></figure>

<figure><img src="image_9.png" /></figure>

<figure><img src="image_10.png" /></figure>

<figure><img src="image_11.png" /></figure>

<figure><img src="image_12.png" /></figure>
Secrecy or Confidentiality

Alice communicates with the White rabbit via a network.

<figure><img src="image_13.png" /></figure>

<figure><img src="image_14.png" /></figure>

<figure><img src="image_15.png" /></figure>
Secrecy or Confidentiality

Alice communicates with the White rabbit via a network.

<figure><img src="image_16.png" /></figure>

<figure><img src="image_17.png" /></figure>

Secret

<figure><img src="image_18.png" /></figure>

<figure><img src="image_19.png" /></figure>

Intruder

<figure><img src="image_20.png" /></figure>
Secrecy or Confidentiality

Alice communicates with the White rabbit via a network.

<figure><img src="image_21.png" /></figure>

<figure><img src="image_22.png" /></figure>

Secret

<figure><img src="image_23.png" /></figure>

<figure><img src="image_24.png" /></figure>

Intruder

<figure><img src="image_25.png" /></figure>
Authentication

<figure><img src="image_26.png" /></figure>

"On the Internet, nobody knows you're a dog."
Mechanisms for Authentication

1. Something that you know
   E.g. a PIN or a password

2. Something that you have
E.g. a smart-card

3. Something that you are
Biometric characteristics like voice, fingerprints, eyes, ...

4. Where you are located
E.g. in a secure building

Strong authentication combines multiple factors:
E.g., Smart-Card + PIN

<figure><img src="image_27.png" /></figure>
Other security properties

► **Integrity**: No improper modification of information

► **Availability**: No improper impairment of functionality/service

► **Non-repudiation** (also called **accountability**) is where one can establish responsibility for actions.

► **Privacy** or **Anonymity**: secrecy of principal identities or communication relationships.

► etc ...
# Symmetric key and public key encryption

## Symmetric key encryption

<figure><img src="image_28.png" /></figure>

## Public key encryption

<figure><img src="image_29.png" /></figure>
# Outline

- Motivations

- Two Examples

- History of Cryptography

- Cryptographic Security Intuitions

- Logical Attacks

- Interactive Zero Knowledge Proofs

- Secret Sharing

- Conclusion
# Outline

* Motivations

* Two Examples

* History of Cryptography

* Cryptographic Security Intuitions

* Logical Attacks

* Interactive Zero Knowledge Proofs

* Secret Sharing

* Conclusion
Symmetric Encryption for GSM communication

<figure><img src="image_30.png" /></figure>

SIM card contains a shared secret key used for authenticating
phones and operators, then creating key session for communication.

1. Message is encrypted and sent by Alice.

2. The antenna receives the message then unencrypted.

3. Message is encrypted by the antenna with the second key.

4. Second mobile unencrypted the communication.
Hash Functions

A hash function *H* takes as input a bit-string of any finite length and returns a corresponding 'digest' of fixed length.

$H : \{0,1\}^* \rightarrow \{0,1\}^n$

$H(\text{Alice}) = \text{BARCODE} \neq H(\text{Bob})$

<figure><img src="image_31.png" /></figure>

marion →

<figure><img src="image_32.png" /></figure>

marine ↔

laurence ←
# Hash function, e.g. Software Installation

<figure><img src="image_33.png" /></figure>

Integrity of the downloaded file.

1. Download on server 1 the software.

2. Download on server 2 the hash of the software.

3. Check the integrity of the software.
# Outline

* Motivations

* Two Examples

* History of Cryptography

* Cryptographic Security Intuitions

* Logical Attacks

* Interactive Zero Knowledge Proofs

* Secret Sharing

* Conclusion
Information hiding

<figure><img src="image_34.png" /></figure>

► Cryptology: the study of secret writing.

► **Steganography**: the science of hiding messages in other messages.

► **Cryptography**: the science of secret writing.
Note: terms like **encrypt**, **encode**, and **encipher** are often
 loosely and wrongly) used interchangeably
Slave

<figure><img src="image_35.png" /></figure>
## Historical ciphers

* Used 4000 years ago by Egyptians to encipher hieroglyphics.

<figure><img src="image_36.png" /></figure>

* 2000 years ago Julius Caesar used a simple substitution cipher.

* Leon Alberti devised a cipher wheel, and described the principles of frequency analysis in the 1460s.
## Substitution cipher examples

* L oryh brx
## Substitution cipher examples

* L oryh brx = I LOVE YOU

**Caesar cipher**: each plaintext character is replaced by the character three to the right modulo 26.
## Substitution cipher examples

* L oryh brx = I LOVE YOU
  Caesar cipher: each plaintext character is replaced by the
  character three to the right modulo 26.

* Zngurzngvdhrf = Mathematiques
  ROT13: shift each letter by 13 places.
  Under Unix: tr a-zA-Z n-za-mN-ZA-M.

* 2-25-5 2-25-5
## Substitution cipher examples

* L oryh brx = I LOVE YOU
  **Caesar cipher**: each plaintext character is replaced by the character three to the right modulo 26.

* Zngurzngvdhrf = Mathematiques
  **ROT13**: shift each letter by 13 places.
  Under Unix: tr a-zA-Z n-za-mN-ZA-M.

* 2-25-5 2-25-5 = BYE BYE
  **Alphanumeric**: substitute numbers for letters.

How hard are these to cryptanalyze? Caesar? General?
(In)security of substitution ciphers

► Key spaces are typically huge. 26 letters ↪→ 26! possible keys.

► Trivial to crack using frequency analysis (letters, digraphs...)

► Frequencies for English based on data-mining books/articles.

<figure><img src="image_37.png" /></figure>
Improvement: Homophonic substitution ciphers

$$A = \{a, b\}$$

$H(a) = \{00, 10\}$, and $H(b) = \{01, 11\}$.

Example

The plaintext *ab* encrypts to one of 0001, 0011, 1001, 1011.
Improvement: Homophonic substitution ciphers

$$ \mathcal{A} = \{a, b\} $$

$H(a) = \{00, 10\}$, and $H(b) = \{01, 11\}$.

Example

The plaintext $ab$ encrypts to one of 0001, 0011, 1001, 1011.

* Rational: makes frequency analysis more difficult.

* Cost: data expansion and more work for decryption.
Polyalphabetic substitution (Leon Alberti, Vignere)

<figure><img src="image_38.png" /></figure>

Example: English (n = 26), with k = 3,7,10

m = THI SCI PHE RIS CER TAI NLY NOT SEC URE

then

E<sub>e</sub>(m) = WOS VJS SOO UPC FLB WHS QSI QVD VLM XYO
Example: transposition ciphers

<figure><img src="image_39.png" /></figure>
Example: transposition ciphers

► C = Aduaenttlydhatoiekounletmtoihahvsekeeeleeyqonouv

<table><tr><td>A</td><td>n</td><td>d</td><td>i</td><td>n</td><td>t</td><td>h</td><td>e</td><td>e</td><td>n</td></tr><tr><td>d</td><td>t</td><td>h</td><td>e</td><td>l</td><td>o</td><td>v</td><td>e</td><td>y</td><td>o</td></tr><tr><td>u</td><td>t</td><td>a</td><td>k</td><td>e</td><td>i</td><td>s</td><td>e</td><td>q</td><td>u</td></tr><tr><td>a</td><td>l</td><td>t</td><td>o</td><td>t</td><td>h</td><td>e</td><td>l</td><td>o</td><td>v</td></tr><tr><td>e</td><td>y</td><td>o</td><td>u</td><td>m</td><td>a</td><td>k</td><td>e</td><td></td><td></td></tr></table>

Table defines a permutation on 1, ..., 50.
Example: transposition ciphers

► C = Aduaentlyldhatoiekounletmtoihahvsekeeeleeyqonouv

<table><tr><td>A</td><td>n</td><td>d</td><td>i</td><td>n</td><td>t</td><td>h</td><td>e</td><td>e</td><td>n</td></tr><tr><td>d</td><td>t</td><td>h</td><td>e</td><td>l</td><td>o</td><td>v</td><td>e</td><td>y</td><td>o</td></tr><tr><td>u</td><td>t</td><td>a</td><td>k</td><td>e</td><td>i</td><td>s</td><td>e</td><td>q</td><td>u</td></tr><tr><td>a</td><td>l</td><td>t</td><td>o</td><td>t</td><td>h</td><td>e</td><td>l</td><td>o</td><td>v</td></tr><tr><td>e</td><td>y</td><td>o</td><td>u</td><td>m</td><td>a</td><td>k</td><td>e</td><td></td><td></td></tr></table>

Table defines a permutation on 1, ..., 50.

► Idea goes back to Greek **Scytale**: wrap belt spirally around baton and write plaintext lengthwise on it.

<figure><img src="image_40.png" /></figure>
Composite ciphers

► Ciphers based on just substitutions or transpositions are not
secure

► Ciphers can be combined. However ...

► two substitutions are really only one more complex substitution,

► two transpositions are really only one transposition,

► but a substitution followed by a transposition makes a new harder cipher.

► Product ciphers chain
substitution-transposition combinations.

► Difficult to do by hand
~→ invention of cipher machines.

<figure><img src="image_41.png" /></figure>
One-time pad (Vernam cipher)

<figure><img src="image_42.png" /></figure>

<figure><img src="image_43.png" /></figure>
One-time pad (Vernam cipher)

<figure><img src="image_44.png" /></figure>

<figure><img src="image_45.png" /></figure>

► Example: $\frac{m = 010111}{k = 110010}$

► Unconditional (information theoretic) security, if key isn't reused!

► Problem?
One-time pad (Vernam cipher)

<figure><img src="image_46.png" /></figure>

<figure><img src="image_47.png" /></figure>

► Example: $\frac{m = 010111}{k = 110010}$

► Unconditional (information theoretic) security, if key isn't reused!

► Problem? Securely exchanging and synchronizing long keys.
# Outline

- Motivations

- Two Examples

- History of Cryptography

- Cryptographic Security Intuitions

- Logical Attacks

- Interactive Zero Knowledge Proofs

- Secret Sharing

- Conclusion
ECB vs Others

<figure><img src="image_48.png" /></figure>
ECB vs Others

<figure><img src="image_49.png" /></figure>

<figure><img src="image_50.png" /></figure>
ECB vs Others

<figure><img src="image_51.png" /></figure>

<figure><img src="image_52.png" /></figure>

<figure><img src="image_53.png" /></figure>
One-Wayness (OW)

Put your message in a translucid bag, but you cannot read the text.

<figure><img src="image_54.png" /></figure>
One-Wayness (OW)

Put your message in a translucid bag, but you cannot read the text.

<figure><img src="image_55.png" /></figure>

Without the private key, it is computationally impossible to
recover the plain-text.
Is it secure ?

<figure><img src="image_56.png" /></figure>
Is it secure ?

<figure><img src="image_57.png" /></figure>

<figure><img src="image_58.png" /></figure>

<figure><img src="image_59.png" /></figure>
Is it secure ?

<figure><img src="image_60.png" /></figure>

<figure><img src="image_61.png" /></figure>

<figure><img src="image_62.png" /></figure>

► you cannot read the text but you can distinguish which one has been encrypted.
Indistinguishability (IND)

Put your message in a black bag, you can not read anything.

<figure><img src="image_63.png" /></figure>

Now a black bag is of course IND and it implies OW.
Is it secure?

<figure><img src="image_64.png" /></figure>
Is it secure?

<figure><img src="image_65.png" /></figure>

<figure><img src="image_66.png" /></figure>
Is it secure?

<figure><img src="image_67.png" /></figure>

<figure><img src="image_68.png" /></figure>

* It is possible to scramble it in order to produce a new cipher. In more you know the relation between the two plain text because you know the moves you have done.
Non Malleability (NM)

Put your message in a black box.

<figure><img src="image_69.png" /></figure>

But in a black box you cannot touch the cube (message), hence
NM implies IND.
# Summary of Security Notions

<figure><img src="image_70.png" /></figure>

Non Malleability

<figure><img src="image_71.png" /></figure>

<figure><img src="image_72.png" /></figure>

Indistinguishability

<figure><img src="image_73.png" /></figure>

<figure><img src="image_74.png" /></figure>

One-Wayness
# Outline

- Motivations

- Two Examples

- History of Cryptography

- Cryptographic Security Intuitions

## Logical Attacks

- Interactive Zero Knowledge Proofs

- Secret Sharing

- Conclusion
# Attacks

Computational Model
Cryptanalysis

<figure><img src="image_75.png" /></figure>
Attacks

<figure><img src="image_76.png" /><figcaption>Computational Model
Cryptanalysis</figcaption></figure>
## Attacks

### Computational Model

### Cryptanalysis

<figure><img src="image_77.png" /></figure>

<figure><img src="image_78.png" /></figure>

<figure><img src="image_79.png" /></figure>

<figure><img src="image_80.png" /></figure>

<figure><img src="image_81.png" /></figure>

### Symbolic Model

### Logical Attack

- Perfect Encryption hypothesis

- Needham-Schroeder Public Key Protocol (1978)

- "Man in the middle attack" [Lowe'96]

<figure><img src="image_82.png" /></figure>

<figure><img src="image_83.png" /></figure>
Simple Example

<figure><img src="image_84.png" /></figure>
Simple Example

<figure><img src="image_85.png" /></figure>

$$ \{12h10\}_{K_B} \rightarrow $$

<figure><img src="image_86.png" /></figure>

<figure><img src="image_87.png" /></figure>

$$ \{12h10\}_{K_B} \rightarrow $$

<figure><img src="image_88.png" /></figure>

<figure><img src="image_89.png" /></figure>
## Simple Example

<figure><img src="image_90.png" /></figure>

$\{12h10\}_{K_B}$

<figure><img src="image_91.png" /></figure>

<figure><img src="image_92.png" /></figure>

$\{12h10\}_{K_B}$

<figure><img src="image_93.png" /></figure>

<figure><img src="image_94.png" /></figure>

Day After

<figure><img src="image_95.png" /></figure>

$\{11h45\}_{K_B}$

<figure><img src="image_96.png" /></figure>

<figure><img src="image_97.png" /></figure>

$\{12h10\}_{K_B}$

<figure><img src="image_98.png" /></figure>

<figure><img src="image_99.png" /></figure>
## Simple Example

<figure><img src="image_100.png" /></figure>

$\{12h10\}_{K_B}$

<figure><img src="image_101.png" /></figure>

<figure><img src="image_102.png" /></figure>

$\{12h10\}_{K_B}$

<figure><img src="image_103.png" /></figure>

<figure><img src="image_104.png" /></figure>

Day After

<figure><img src="image_105.png" /></figure>

$\{11h45\}_{K_B}$

<figure><img src="image_106.png" /></figure>

<figure><img src="image_107.png" /></figure>

$\{12h10\}_{K_B}$

<figure><img src="image_108.png" /></figure>

<figure><img src="image_109.png" /></figure>

This kind of attack is valid for all encryptions
Authentication Problem: Wormhole Attack

<figure><img src="image_110.png" /></figure>
Example: Needham-Schroeder Protocol 1978

<figure><img src="image_111.png" /></figure>
Example: Needham-Schroeder Protocol 1978

<figure><img src="image_112.png" /></figure>
Example: Needham-Schroeder Protocol 1978

<figure><img src="image_113.png" /></figure>
Example: Needham-Schroeder Protocol 1978

<figure><img src="image_114.png" /></figure>

Question

► Is $N_B$ a shared secret between A et B?
Example: Needham-Schroeder Protocol 1978

<figure><img src="image_115.png" /></figure>

Question

► Is $N_B$ a shared secret between A et B?

Answer

► In 1995, G.Lowe find an attack 17 years after its publication!
Lowe Attack on the Needham-Schroeder
so-called "Man in the middle attack"

<figure><img src="image_116.png" /><figcaption>Agent A</figcaption></figure>

<figure><img src="image_117.png" /><figcaption>Intruder /</figcaption></figure>

<figure><img src="image_118.png" /><figcaption>Agent B</figcaption></figure>

$A \rightarrow B : \{A, N_a\}_{K_B}$

$B \rightarrow A : \{N_a, N_b\}_{K_A}$

$A \rightarrow B : \{N_b\}_{K_B}$
Lowe Attack on the Needham-Schroeder
so-called "Man in the middle attack"

<figure><img src="image_119.png" /></figure>

A $\rightarrow$ B : {$A, N_a$}$_{K_B}$

B $\rightarrow$ A : {$N_a, N_b$}$_{K_A}$

A $\rightarrow$ B : {$N_b$}$_{K_B}$
Lowe Attack on the Needham-Schroeder

so-called "Man in the middle attack"

<figure><img src="image_120.png" /></figure>

Agent A

Intruder I

Agent B

A $\rightarrow$ B : {$A, N_a$}$_{K_B}$

B $\rightarrow$ A : {$N_a, N_b$}$_{K_A}$

A $\rightarrow$ B : {$N_b$}$_{K_B}$
Lowe Attack on the Needham-Schroeder

so-called "Man in the middle attack"

<figure><img src="image_121.png" /></figure>

Agent A

Intruder /

Agent B

<figure><img src="image_122.png" /></figure>
Lowe Attack on the Needham-Schroeder

so-called "Man in the middle attack"

<figure><img src="image_123.png" /></figure>

Agent A

Intruder I

Agent B

<figure><img src="image_124.png" /></figure>
Lowe Attack on the Needham-Schroeder

so-called "Man in the middle attack"

<figure><img src="image_125.png" /></figure>

Agent A

Intruder /

Agent B

$A \rightarrow B : \{A, N_a\}_{K_B}$

$B \rightarrow A : \{N_a, N_b\}_{K_A}$

* $A \rightarrow B : \{N_b\}_{K_B}$
Lowe Attack on the Needham-Schroeder

so-called "Man in the middle attack"

<figure><img src="image_126.png" /></figure>

Agent A

Intruder I

Agent B

$A \rightarrow B : \{A, N_a\}_{K_B}$

$B \rightarrow A : \{N_a, N_b\}_{K_A}$

* $A \rightarrow B : \{N_b\}_{K_B}$
Needham-Schroeder corrected by Lowe 1995

<figure><img src="image_127.png" /></figure>
Needham-Schroeder corrected by Lowe 1995

<figure><img src="image_128.png" /></figure>
Needham-Schroeder corrected by Lowe 1995

<figure><img src="image_129.png" /></figure>
Needham-Schroeder corrected by Lowe 1995

<figure><img src="image_130.png" /></figure>

Question

► This time the protocol is secure?
# Outline

- Motivations

- Two Examples

- History of Cryptography

- Cryptographic Security Intuitions

- Logical Attacks

- Interactive Zero Knowledge Proofs

- Secret Sharing

- Conclusion
# Interactive Zero Knowledge Proofs

An Example: The Cave Story (2)

<figure><img src="image_131.png" /></figure>

First, Victor waits outside while Peggy chooses a path.
# Interactive Zero Knowledge Proofs

An Example: The Cave Story (3)

<figure><img src="image_132.png" /></figure>

Then Victor enters and shouts the name of a path.
# Interactive Zero Knowledge Proofs

An Example: The Cave Story (4)

<figure><img src="image_133.png" /></figure>

At last, Peggy returns along the desired path (using the secret if necessary).
# Outline

- Motivations

- Two Examples

- History of Cryptography

- Cryptographic Security Intuitions

- Logical Attacks

- Interactive Zero Knowledge Proofs

## Secret Sharing

- Conclusion
Secret Sharing

► How keep nuclear code secret in British Army?
Secret Sharing

► How keep nuclear code secret in British Army?

► Burn it, but do not preseve integrity
How to Share a Secret Code I

<figure><img src="image_134.png" /></figure>

1234567

<figure><img src="image_135.png" /></figure>
## How to Share a Secret Code I

<figure><img src="image_136.png" /></figure>

1234567

<figure><img src="image_137.png" /></figure>

## Problem of Integrity and Confidentiality
How to Share a Secret Code II

<figure><img src="image_138.png" /></figure>

<figure><img src="image_139.png" /></figure>

1234567

1234567

1234567

1234567

1234567

1234567

1234567

1234567
## How to Share a Secret Code II

<figure><img src="image_140.png" /></figure>

Problem of Confidentiality
No problem of Integrity

<figure><img src="image_141.png" /></figure>

<figure><img src="image_142.png" /></figure>

1234567

<figure><img src="image_143.png" /></figure>

1234567

<figure><img src="image_144.png" /></figure>

1234567

<figure><img src="image_145.png" /></figure>

1234567

<figure><img src="image_146.png" /></figure>

1234567

<figure><img src="image_147.png" /></figure>

1234567

1234567

1234567

<figure><img src="image_148.png" /></figure>
How to Share a Secret Code II

<figure><img src="image_149.png" /></figure>

<figure><img src="image_150.png" /></figure>

<figure><img src="image_151.png" /></figure>

<figure><img src="image_152.png" /></figure>

<figure><img src="image_153.png" /></figure>

<figure><img src="image_154.png" /></figure>

<figure><img src="image_155.png" /></figure>

<figure><img src="image_156.png" /></figure>
## How to Share a Secret Code II

<figure><img src="image_157.png" /></figure>

No Problem of Confidentiality
Problem of Integrity

<figure><img src="image_158.png" /></figure>

<figure><img src="image_159.png" /></figure>

23572

<figure><img src="image_160.png" /></figure>

11567

<figure><img src="image_161.png" /></figure>

734567

<figure><img src="image_162.png" /></figure>

534567

<figure><img src="image_163.png" /></figure>

934567

<figure><img src="image_164.png" /></figure>

563317

<figure><img src="image_165.png" /></figure>

114567

455967²
(2,5)

<figure><img src="image_166.png" /></figure>
(3,5)

<figure><img src="image_167.png" /></figure>
Conclusion

Outline

Motivations

Two Examples

History of Cryptography

Cryptographic Security Intuitions

Logical Attacks

Interactive Zero Knowledge Proofs

Secret Sharing

Conclusion
# Summary

## Today

* Motivation

* History of Cryptography

* Securities notions

* Logical attacks

* Zero-knowledge

* Secret Sharing
Thank you for your attention

<figure><img src="image_168.png" /></figure>

Questions ?

pascal.lafourcade@imag.fr