Introduction à la sécurité en intensif

Site du prof

Explication des symboles de maths du cours

Symbole	Définition
Définition	\doteq
Congru à (égalité modulo qqch)	\equiv
Calcul fauté	\widehat{s_{q}}

Cours de la semaine

Lundi 12/09

Clé Vigenère-Bellaso : clé parfaite tant que la clé est parfaitement aléatoire + aussi longue que le message à chiffré

Retrouvé la taille de la clé

On fait le PGCD (Plus Grand Diviseur Commun) des écarts entre les répétitions

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Chiffre un message avec une clef (tout en minuscule)
void chiffre(char *message, char *clef) {
  char decalage = 'a';
  for (int i = 0, taille_clef = strlen(clef); *message != '\0';
       ++message, ++i) {
    *message = ((*message - decalage + clef[i % taille_clef] - decalage) % 26) +
               decalage;
  }
}

// Déchiffre un message avec une clef (tout en minuscule)
void dechiffre(char *message, char *clef) {
  char decalage = 'a';
  for (int i = 0, taille_clef = strlen(clef); *message != '\0';
       ++message, ++i) {
    *message =
        (((*message - decalage) - (clef[i % taille_clef] - decalage) + 26) %
         26) +
        decalage;
  }
}

int main(int argc, char *argv[]) {
  if (argc < 3) {
    fprintf(stderr, "Usage: %s <clef> <message en minuscule et sans espace>\n",
            argv[0]);
    return 1;
  }

  printf("clef: %s\n", argv[1]);
  printf("message: %s\n", argv[2]);

  char message_original[strlen(argv[2])];
  strcpy(message_original, argv[2]);

  chiffre(argv[2], argv[1]);
  printf("message chiffré: %s\n", argv[2]);

  dechiffre(argv[2], argv[1]);
  printf("message déchiffré: %s\n", argv[2]);

  return 0;
}

PRNG: Pseudo RaNdom Generator

Mardi 13/09

Rappel

a	b	a & b	a \| b	a ^ b
0	0	0	0	0
0	1	0	1	1
1	0	0	1	1
1	1	1	1	0

coupage octet

Structure modulo en cercle

structure modulo

Échange de clefs de Diffie-Hellman

protocole2participants

Exemple en python :

from random import randint

p = 23
g = 3

# Alice
a = randint(1, p - 1)
A = g ** a % p

# Bob
b = randint(1, p - 1)
B = g ** b % p

# Alice de son côté
K_alice = B ** a % p

# Bob de son côté
K_bob = A ** b % p

# On vérifie l'égalité
print(K_alice == K_bob) # True

En python, au lieu de faire x ** y % z on peut faire pow(x, y, z).

Version du protocole avec 3 participants :

from random import randint

p = 23
g = 3

"""
Ce que sait Alice est préfixé par un a_
Ce que sait Bob est préfixé par un b_
Ce que sait Charlotte est préfixé par un c_
"""

a_a = randint(1, p - 1)
a_A = pow(g, a_a, p)

b_b = randint(1, p - 1)
b_B = pow(g, b_b, p)

c_c = randint(1, p - 1)
c_C = pow(g, c_c, p)

b_A = a_A # Alice transmet à Bob
b_Ab = pow(b_A, b_b, p)

c_Ab = b_Ab
c_K = pow(c_Ab, c_c, p)

b_C = c_C # Charlotte transmet à Bob
b_Cb = pow(b_C, b_b, p)

a_Cb = b_Cb
a_K = pow(a_Cb, a_a, p)

# On vérifie l'égalité entre Alice et Charlotte
print(a_K == c_K) # True

a_C = c_C # Charlotte transmet à Alice
a_Ac = pow(a_C, a_a, p)

b_Ac = a_Ac
b_K = pow(b_Ac, b_b, p)

# On vérifie que tout est bon
print(a_K == b_K == c_K)

Pour générer un nombre de 2048 bits pour RSA on peut faire :
$ openssl prime -generate -bits 2048

SSSS

Il faut 3 personnes dans ce cas là, avec ces courbes, pour avoir les infos
SSSS

Homomorphisme

Avec le RSA

Soit les paires RSA
(e, n) \text{ et } (d, n)

\begin{aligned} x\prime &= x^{e} \text{ \% } n \\\ y\prime &= y^{e} \text{ \% } n \end{aligned}
\begin{aligned} x\prime y\prime &= x^{e} y^{e} \text{ \% } n \\\ y\prime &= (xy)^{e} \text{ \% } n \end{aligned}
\begin{aligned} z'^{d} \text{ \% } n & \\\ &= ((xy)^{e})^{d} \text{ \% } n \\\ &= (xy)^{ed} \text{ \% } n \\\ &= xy \end{aligned}

Mercredi 14/09

taktoy.py

sbox = [3, 14, 1, 10, 4, 9, 5, 6, 8, 11, 15, 2, 13, 12, 0, 7]
# sbox = [12, 5, 6, 11, 9, 0, 10, 13, 3, 14, 15, 8, 4, 7, 1, 2] # from PRESENT
xobs = [14, 2, 11, 0, 4, 6, 7, 15, 8, 5, 3, 9, 13, 12, 1, 10]


def round(msg, subkey):
    return sbox[msg ^ subkey]


def enc(msg, key):
    t0 = round(msg, key[0])
    t1 = round(t0, key[1])
    return t1


def simplified_enc(msg, key):
    t0 = round(msg, key[0])
    return t0 ^ key[1]

cryptanalyse differentielle

diff.py

from random import choice, randint
import taktoy

debug = True


def compute_differential_characteristics():
    sbox_dc = [[0 for _ in range(0, 16)] for _ in range(0, 16)]
    for a in range(0, 16):
        for b in range(0, 16):
            sbox_dc[a ^ b][taktoy.sbox[a] ^ taktoy.sbox[b]] += 1
    if debug:
        print("\n> XOR differential table:")
        print("     ", end="")
        for i in range(0, 16):
            print("%2x " % i, end="")
        print("\n   +-", end="")
        for i in range(0, 16):
            print("---", end="")
        for i in range(0, 16):
            print("\n%2x | " % i, end="")
            for j in range(0, 16):
                print("%2d " % sbox_dc[i][j], end="")
    return sbox_dc


def get_most_probable_diff_sbox_io(dc):
    mpd = 0
    for i in range(1, 16):
        for j in range(1, 16):
            mpd = max(mpd, dc[i][j])
    if debug:
        print(f"\n> Most probable diff occurs {mpd} times\n")
        print("> Most probable diff I/O:")
    io = []
    for i in range(1, 16):
        for j in range(1, 16):
            if dc[i][j] == mpd:
                io.append((i, j))
                if debug:
                    print(f"{hex(i)[2:]} --> {hex(j)[2:]}")
    return io


def get_possible_intermediate_values(diff_io):
    di, do = diff_io
    if debug:
        print(f"\n> Selected diff: di={di} --> do={do}")
    piv = []  # probable intermediate values
    for a in range(0, 16):
        b = a ^ di
        if taktoy.sbox[a] ^ taktoy.sbox[b] == do:
            piv.append(a)
            if debug:
                print(
                    f"> Possible a ^ b --> S[a] ^ S[b]: {a} ^ {b} --> {taktoy.sbox[a]} ^ {taktoy.sbox[b]}.")
    return piv


def generate_pairs(count, di, key):
    pairs_rand = []
    pairs_diff = []
    for _ in range(0, count):
        m = randint(0, 15)
        c0 = taktoy.simplified_enc(m, key)
        pairs_rand.append((m, c0))
        md = m ^ di
        cd = taktoy.simplified_enc(md, key)
        pairs_diff.append((md, cd))
    return pairs_rand, pairs_diff


def find_good_pair(pairs_r, pairs_d, do):
    print(f"> Looking for a pair with output diff = {do}...")
    for i in range(0, len(pairs_r)):
        if pairs_r[i][1] ^ pairs_d[i][1] == do:
            if debug:
                print(f"> Found {pairs_r[i]}.")
            return pairs_r[i]
    print("> Cannot find good pair...")


def test_key(key, pairs):
    for p in pairs:
        if p[1] != taktoy.simplified_enc(p[0], key):
            return False
    return True


def attack(piv, m, c, pairs_r, pairs_d):
    for i in range(0, len(piv)):
        k0 = piv[i] ^ m
        k1 = taktoy.sbox[piv[i]] ^ c
        if test_key((k0, k1), pairs_r) and test_key((k0, k1), pairs_d):
            return k0, k1
    print("> Raté")


if __name__ == "__main__":
    dc = compute_differential_characteristics()
    mpd_io = get_most_probable_diff_sbox_io(dc)
    io = choice(mpd_io)
    piv = get_possible_intermediate_values(io)

    key = (randint(0, 15), randint(0, 15))
    print(f"KEY: {key}")
    pairs_r, pairs_d = generate_pairs(8, io[0], key)
    m, c = find_good_pair(pairs_r, pairs_d, io[1])

    k = attack(piv, m, c, pairs_r, pairs_d)
    print(f"ATTACK: {k}")