Cryptographie symétrique

Ce sont les systèmes, qui, comme les exemples classiques vus au premier cours, fonctionnent avec une clé secrète partagée. Il en existe principalement deux types :

  • les chiffrements par blocs (block ciphers):
    le texte clair est divisé en blocs de \(N\) caractères (en général \(N\) bits), et chacun d'eux est chiffré en un bloc de \(M\) caractères (en général, \(M=N\));

  • les chiffrements par flux (stream ciphers) : on superpose au texte clair une suite pseudo-aléatoire, supposée imprédictible si on ne connaît pas la clé.

Par exemple, les chiffres monoalphabétiques opèrent sur des blocs de 1 caractère, et les chiffres polyalphabétiques sur des blocs de \(N\) caractères, où \(N\) est la longueur de la clé.

Parmi les chiffres en usage actuellement, DES (Data Encryption Standard), maintenant remplacé par AES (Advanced Encryption Standard, ex Rinjdael), Blowfish, IDEA, sont des chiffrements par blocs. RC4 (utilisé pour le WiFi, pdf, …) A5/1
(téléphonie mobile GSM), ou le one-time pad sont des chiffrements par flux.

Avec Python, on pourra utiliser le paquetage pycrypto.

In [1]:
import Crypto
In [2]:
help(Crypto)
Help on package Crypto:

NAME
    Crypto - Python Cryptography Toolkit

FILE
    /usr/lib/python2.7/dist-packages/Crypto/__init__.py

DESCRIPTION
    A collection of cryptographic modules implementing various algorithms
    and protocols.
    
    Subpackages:
    
    Crypto.Cipher
     Secret-key (AES, DES, ARC4) and public-key encryption (RSA PKCS#1) algorithms
    Crypto.Hash
     Hashing algorithms (MD5, SHA, HMAC)
    Crypto.Protocol
     Cryptographic protocols (Chaffing, all-or-nothing transform, key derivation
     functions). This package does not contain any network protocols.
    Crypto.PublicKey
     Public-key encryption and signature algorithms (RSA, DSA)
    Crypto.Signature
     Public-key signature algorithms (RSA PKCS#1) 
    Crypto.Util
     Various useful modules and functions (long-to-string conversion, random number
     generation, number theoretic functions)

PACKAGE CONTENTS
    Cipher (package)
    Hash (package)
    Protocol (package)
    PublicKey (package)
    Random (package)
    SelfTest (package)
    Signature (package)
    Util (package)
    pct_warnings

DATA
    __all__ = ['Cipher', 'Hash', 'Protocol', 'PublicKey', 'Util', 'Signatu...
    __revision__ = '$Id$'
    __version__ = '2.6.1'

VERSION
    2.6.1



Le DES (Data Encryption Standard)

Le prototype du chiffrement par blocs est le DES (maintenant abandonné au profit de l'AES).

Adopté comme standard aux USA en 1976. C'est une modification du chiffre Lucifer d'IBM, demandée par la NSA. On a longtemps supposé que cette modification était destinée à affaiblir l'algorithme. On a depuis découvert qu'elle lui permettait de résister à des attaques qui n'ont été rendues publiques que bien plus tard.

Le standard DES a été remplacé en 2001 par l'AES (Advanced Encryption Standard).

Il est déjà suffisamment complexe pour qu'on se contente d'une étude superficielle. Avant de l'aborder, commençons par nous familiariser avec son utilisation.

Le DES transforme un bloc de 64 bits en un autre bloc de 64 bits. Il utilise des clés de 56 bits, représentées sur 64 bits (avec un bit de contrôle de parité dans chaque octet).

Il est décrit par une structure de Feistel (du nom de Horst Feistel, auteur de Lucifer).

In [3]:
from Crypto.Cipher import DES
In [4]:
d = DES.new('azertyui') # Clef de 64 bits = 8 caractères
x = "Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua.$$$$$"
print len(x) # doit être multiple de 8, d'où les $ ...
y = d.encrypt(x)
y
128

Out[4]:
"3pZWb\xc4\xea\xd0l\x00\xb4=\x9d$\xd7\x12U\xb9\xeb41\xe0\xc9\x0eCh\xa5Z~~\x1c\xefRT%{\xea\x9b\xfdB\x96\xfa]0;F\xf9O9\xd1$L+\xadk\xa6\xa2-[\xa1\xc9\x1a\xdfS\x1e\x97#^\xaf'\xa6\xd1\xfd'ZA\x9f\xa9\xe3\xb5\xf4\xdaR\xc90\x80\x8b\xce;\xa8b\xa8\xdb4\xe6\xcd\xf7\xf0s\xd5\x1e\xa1Z\x01\xddt\xbeb*\\\xd4q2\x16i\xe4\x01\x03\xebF\xaa\x06\xdc\xb8`&\xd2\xe9"
In [5]:
d.decrypt(y)
Out[5]:
'Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua.$$$$$'
In [6]:
help(DES)
Help on module Crypto.Cipher.DES in Crypto.Cipher:

NAME
    Crypto.Cipher.DES - DES symmetric cipher

FILE
    /usr/lib/python2.7/dist-packages/Crypto/Cipher/DES.py

DESCRIPTION
    DES `(Data Encryption Standard)`__ is a symmetric block cipher standardized
    by NIST_ . It has a fixed data block size of 8 bytes.
    Its keys are 64 bits long, even though 8 bits were used for integrity (now they
    are ignored) and do not contribute to securty.
    
    DES is cryptographically secure, but its key length is too short by nowadays
    standards and it could be brute forced with some effort.
    
    DES should not be used for new designs. Use `AES`.
    
    As an example, encryption can be done as follows:
    
        >>> from Crypto.Cipher import DES3
        >>> from Crypto import Random
        >>>
        >>> key = b'Sixteen byte key'
        >>> iv = Random.new().read(DES3.block_size)
        >>> cipher = DES3.new(key, DES3.MODE_OFB, iv)
        >>> plaintext = b'sona si latine loqueris '
        >>> msg = iv + cipher.encrypt(plaintext)
    
    .. __: http://en.wikipedia.org/wiki/Data_Encryption_Standard
    .. _NIST: http://csrc.nist.gov/publications/fips/fips46-3/fips46-3.pdf
    
    :undocumented: __revision__, __package__

CLASSES
    Crypto.Cipher.blockalgo.BlockAlgo
        DESCipher
    
    class DESCipher(Crypto.Cipher.blockalgo.BlockAlgo)
     |  DES cipher object
     |  
     |  Methods defined here:
     |  
     |  __init__(self, key, *args, **kwargs)
     |      Initialize a DES cipher object
     |      
     |      See also `new()` at the module level.
     |  
     |  ----------------------------------------------------------------------
     |  Methods inherited from Crypto.Cipher.blockalgo.BlockAlgo:
     |  
     |  decrypt(self, ciphertext)
     |      Decrypt data with the key and the parameters set at initialization.
     |      
     |      The cipher object is stateful; decryption of a long block
     |      of data can be broken up in two or more calls to `decrypt()`.
     |      That is, the statement:
     |          
     |          >>> c.decrypt(a) + c.decrypt(b)
     |      
     |      is always equivalent to:
     |      
     |           >>> c.decrypt(a+b)
     |      
     |      That also means that you cannot reuse an object for encrypting
     |      or decrypting other data with the same key.
     |      
     |      This function does not perform any padding.
     |      
     |       - For `MODE_ECB`, `MODE_CBC`, and `MODE_OFB`, *ciphertext* length
     |         (in bytes) must be a multiple of *block_size*.
     |      
     |       - For `MODE_CFB`, *ciphertext* length (in bytes) must be a multiple
     |         of *segment_size*/8.
     |      
     |       - For `MODE_CTR`, *ciphertext* can be of any length.
     |      
     |       - For `MODE_OPENPGP`, *plaintext* must be a multiple of *block_size*,
     |         unless it is the last chunk of the message.
     |      
     |      :Parameters:
     |        ciphertext : byte string
     |          The piece of data to decrypt.
     |      :Return: the decrypted data (byte string, as long as *ciphertext*).
     |  
     |  encrypt(self, plaintext)
     |      Encrypt data with the key and the parameters set at initialization.
     |      
     |      The cipher object is stateful; encryption of a long block
     |      of data can be broken up in two or more calls to `encrypt()`.
     |      That is, the statement:
     |          
     |          >>> c.encrypt(a) + c.encrypt(b)
     |      
     |      is always equivalent to:
     |      
     |           >>> c.encrypt(a+b)
     |      
     |      That also means that you cannot reuse an object for encrypting
     |      or decrypting other data with the same key.
     |      
     |      This function does not perform any padding.
     |      
     |       - For `MODE_ECB`, `MODE_CBC`, and `MODE_OFB`, *plaintext* length
     |         (in bytes) must be a multiple of *block_size*.
     |      
     |       - For `MODE_CFB`, *plaintext* length (in bytes) must be a multiple
     |         of *segment_size*/8.
     |      
     |       - For `MODE_CTR`, *plaintext* can be of any length.
     |      
     |       - For `MODE_OPENPGP`, *plaintext* must be a multiple of *block_size*,
     |         unless it is the last chunk of the message.
     |      
     |      :Parameters:
     |        plaintext : byte string
     |          The piece of data to encrypt.
     |      :Return:
     |          the encrypted data, as a byte string. It is as long as
     |          *plaintext* with one exception: when encrypting the first message
     |          chunk with `MODE_OPENPGP`, the encypted IV is prepended to the
     |          returned ciphertext.

FUNCTIONS
    new(key, *args, **kwargs)
        Create a new DES cipher
        
        :Parameters:
          key : byte string
            The secret key to use in the symmetric cipher.
            It must be 8 byte long. The parity bits will be ignored.
        :Keywords:
          mode : a *MODE_** constant
            The chaining mode to use for encryption or decryption.
            Default is `MODE_ECB`.
          IV : byte string
            The initialization vector to use for encryption or decryption.
            
            It is ignored for `MODE_ECB` and `MODE_CTR`.
        
            For `MODE_OPENPGP`, IV must be `block_size` bytes long for encryption
            and `block_size` +2 bytes for decryption (in the latter case, it is
            actually the *encrypted* IV which was prefixed to the ciphertext).
            It is mandatory.
           
            For all other modes, it must be `block_size` bytes longs.
          counter : callable
            (*Only* `MODE_CTR`). A stateful function that returns the next
            *counter block*, which is a byte string of `block_size` bytes.
            For better performance, use `Crypto.Util.Counter`.
          segment_size : integer
            (*Only* `MODE_CFB`).The number of bits the plaintext and ciphertext
            are segmented in.
            It must be a multiple of 8. If 0 or not specified, it will be assumed to be 8.
        
        :Return: an `DESCipher` object

DATA
    MODE_CBC = 2
    MODE_CFB = 3
    MODE_CTR = 6
    MODE_ECB = 1
    MODE_OFB = 5
    MODE_OPENPGP = 7
    MODE_PGP = 4
    __revision__ = '$Id$'
    block_size = 8
    key_size = 8



En plus de la clef, nous avons deux paramètres optionnels : le mode, et le vecteur d'initialisation.

Pour comprendre leur utilité, chiffrons une petite image (photographie d'un document secret) :

In [7]:
import Image
In [8]:
im = Image.open("x.png")
In [9]:
im.size, im.mode
Out[9]:
((728, 90), 'RGBA')
In [12]:
s = im.tobytes()
t = d.encrypt(s)
In [13]:
Image.frombytes(im.mode,im.size,t).save('y.png')

Contemplons le résultat

Ce n'est pas brillant. Le problème vient du mode opératoire.

La manière naïve (chiffrer chaque bloc avec la même clé) est appelée mode ECB (Electronic Code Book). Évidemment, les blocs identiques sont chiffrés de manière identique, ce qui présente un risque certain.

Dans le mode CBC (Cipher Block Chaining), on applique sur chaque bloc un "OU exclusif" avec le chiffrement du bloc précédent avant qu’il ne soit lui-même chiffré.

In [18]:
d=DES.new('azertyui',mode=2,IV='\0'*8) #IV obligatoire dans cette version
t=d.encrypt(s)
Image.frombytes(im.mode,im.size,t).save('z.png')

Contemplons le résultat :

On peut utiliser un autre vecteur d'initialisation, afin que deux messages identiques, bien que chiffrés avec la même clef, soient chiffrés de manière différente.

In [22]:
d=DES.new('azertyui',mode=2, IV='blahblah')
t1=d.encrypt(s)
Image.frombytes(im.mode,im.size,t1).save('w.png')

On obtient

In [23]:
t[:40]
Out[23]:
'X\x9a%\xcf&g/:s\xc3\xd7\xf8\x7f*\xde\xa83\x15k\xd8\x16\x96\x89\x1c\xc1\xd7.C,\x99\xd5\x96\x89+\xb6{\x89e\x85\xbf'
In [24]:
t1[:40]
Out[24]:
'\xf2\xaa\xd8#\x8f\xb4\x14\xaa\x15\xcc\xb0\xea|\xa7\x0c\x06\xc1\xad\x8f$*_\xa8\x95O\x14\xe35q\r\xd5v\x01(6\x1eQ\xf8\t\xed'

Réseaux de permutations-substitutions (SPN, Substitution-Permutation Networks)

Ils se composent d'un certain nombre \(r\) d'étages (ou tours, rounds), qui opérent sur des blocs de \(N\) bits.

Chaque étage se compose de S-boîtes (S-boxes) et d'une P-boîte (P-box).

Les S-boîtes calculent des fonctions arbitraires \(\{0,1\}^k\rightarrow \{0,1\}^l\).

Les P-boîtes réalisent des permutations des bits.

Un SPN est caractérisé par

  • son nombre \(r\) d'étages
  • Un algorithme de diversification de la clef : \(K \rightarrow K_1,K_2,\ldots,K_r\) (clefs d'étage)
  • Sa fonction d'étage \(w_i = f(w_{i-1},K_{i-1})\) (\(w_0\) est le texte clair, \(w_r\) le texte chiffré).
Exemple de SPN

Exemple de SPN

Structures de Feistel

Il s'agit d'une architecture facilitant la conception et l'implantation des SPN. Chiffrement et déchiffrement utilisent le même algorithme.

La sécurité d'un tel système dépend du choix de la fonction d'étage \(f(x,y)\) (qui n'a pas besoin d'être injective), et de l'algorithme de diversification de la clé.

On travaille sur des blocs de longueur paire \(N=2N'\) (pour le DES, \(N=64\)).

Conventions

Les blocs de texte clair (plaintext) sont notés \(P\). On note \(||\) l'opérateur de concaténation, et \(\oplus\) l'opérateur de OU exclusif bit-à-bit.

Les blocs sont divisés en deux moitiés de \(N'\) bits, \(L\) et \(R\).

Au départ, \(P=L_0||R_0\).

Pour i de 1 à r :

  1. calculer \(R_i = L_i\oplus f(R_{i-1},K_i)\)

  2. \(L_i = R_{i-1}\)

Exemple

Pour chiffrer \(P\), \[{R_0\choose L_0}\rightarrow {R_1=L_0\oplus f(R_0,K_1)\choose L_1=R_0} \rightarrow {R_2=L_1\oplus f(R_1,K_2)\choose L_2=R_1} \rightarrow{R_3=L_2\oplus f(R_2,K_3)\choose L_3=R_2}\] Pour déchiffrer, \[{R_2=L_3\choose L_2=R_3\oplus f(R_2,K_3)}\rightarrow{R_1=L_2\choose L_1=R_2\oplus f(R_1,K_2)}\rightarrow{R_0=L_1\choose L_0=R_1\oplus f(R_0,K_1)}\]

Paramètres du DES

Blocs de \(N=64\) bits, clef de 64 bits dont seulement 56 sont utilisés (les bits 8,16,24,32,40,48,56 sont des contrôles de parité).

Le nombre de clefs possible est \[2^{56} = 72.057.594.037.927.936\]

C'est beaucoup. Cependant, en 1998, l'EFF (Electronic Frontier Foundation) a pu construire une machine spécialisée, DES Cracker, dite DeepCrack pour seulement $ 250 000, permettant de retrouver une clef DES en 56 heures. On estime qu'en 1976, une telle machine aurait pu être construite pour 20 millions de dollars, une somme à la portée de la NSA.

Dans la description officielle, les bits sont numérotés de 1 à 64, le bit de poids fort en premier. Par exemple, \(18=2^4+2^1={12345\choose 10010}\).

Nombre d'étages \(r=16\).

Diversification de la clef On élimine les bits \(8i\), \(i=1,\ldots,8\). On obtient deux moitiés de 28 bits \(K_0=C_0||D_0\).

Pour \(i=1,2,9,16\), on calcule \[C_i = {\rm lrot}_1(C_{i-1}),\ D_i = {\rm lrot}_1(D_{i-1})\] Pour \(i=3-8,10-15\), \[C_i = {\rm lrot}_2(C_{i-1}),\ D_i={\rm lrot}_2(C_{i-2})\] Les résultats \(C_i||D_i\) sont filtrés par une permutation sélective. On obtient 16 clés d'étage de 48 bits.

Fonction d'étage Elle prend en entrée 32 bits, filtrés par une permutation expansive qui en produit 48. Il passent par 8 S-boîtes différentes, ayant chacune 6 bits en entrée et 4 bits en sortie. Les 32 bits sortants sont passés dans une P-boîte.

DES

DES

AES (Advanced Encryption Standard)

Issu d'un appel à candidatures international lancé en janvier 1997 et adopté par le NIST (National Institute of Standards and Technology) en 2001. Il utilise peu de mémoire. Il n'est pas basé sur un schéma de Feistel, sa complexité est moindre et il est plus facile à mettre en oeuvre.

L'algorithme prend en entrée un bloc de 128 bits (16 octets), la clé fait 128, 192 ou 256 bits. Les 16 octets en entrée sont permutés selon une table définie au préalable. Ces octets sont ensuite placés dans une matrice de 4x4 éléments et ses lignes subissent une rotation vers la droite. L'incrément pour la rotation varie selon le numéro de la ligne. Une transformation linéaire est ensuite appliquée sur la matrice, elle consiste en la multiplication binaire de chaque élément de la matrice avec des polynômes issus d'une matrice auxiliaire, à coefficients dans le corps fini \({\mathbb F}_{2^8}\)

Finalement, un OU exclusif XOR entre la matrice et une autre matrice permet d'obtenir une matrice intermédiaire. Ces différentes opérations sont répétées plusieurs fois et définissent un « tour ». Pour une clé de 128, 192 ou 256, AES nécessite respectivement 10, 12 ou 14 tours.

On trouvera des détails ici.

In [25]:
from Crypto.Cipher import AES
In [26]:
help(AES)
Help on module Crypto.Cipher.AES in Crypto.Cipher:

NAME
    Crypto.Cipher.AES - AES symmetric cipher

FILE
    /usr/lib/python2.7/dist-packages/Crypto/Cipher/AES.py

DESCRIPTION
    AES `(Advanced Encryption Standard)`__ is a symmetric block cipher standardized
    by NIST_ . It has a fixed data block size of 16 bytes.
    Its keys can be 128, 192, or 256 bits long.
    
    AES is very fast and secure, and it is the de facto standard for symmetric
    encryption.
    
    As an example, encryption can be done as follows:
    
        >>> from Crypto.Cipher import AES
        >>> from Crypto import Random
        >>>
        >>> key = b'Sixteen byte key'
        >>> iv = Random.new().read(AES.block_size)
        >>> cipher = AES.new(key, AES.MODE_CFB, iv)
        >>> msg = iv + cipher.encrypt(b'Attack at dawn')
    
    .. __: http://en.wikipedia.org/wiki/Advanced_Encryption_Standard
    .. _NIST: http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf
    
    :undocumented: __revision__, __package__

CLASSES
    Crypto.Cipher.blockalgo.BlockAlgo
        AESCipher
    
    class AESCipher(Crypto.Cipher.blockalgo.BlockAlgo)
     |  AES cipher object
     |  
     |  Methods defined here:
     |  
     |  __init__(self, key, *args, **kwargs)
     |      Initialize an AES cipher object
     |      
     |      See also `new()` at the module level.
     |  
     |  ----------------------------------------------------------------------
     |  Methods inherited from Crypto.Cipher.blockalgo.BlockAlgo:
     |  
     |  decrypt(self, ciphertext)
     |      Decrypt data with the key and the parameters set at initialization.
     |      
     |      The cipher object is stateful; decryption of a long block
     |      of data can be broken up in two or more calls to `decrypt()`.
     |      That is, the statement:
     |          
     |          >>> c.decrypt(a) + c.decrypt(b)
     |      
     |      is always equivalent to:
     |      
     |           >>> c.decrypt(a+b)
     |      
     |      That also means that you cannot reuse an object for encrypting
     |      or decrypting other data with the same key.
     |      
     |      This function does not perform any padding.
     |      
     |       - For `MODE_ECB`, `MODE_CBC`, and `MODE_OFB`, *ciphertext* length
     |         (in bytes) must be a multiple of *block_size*.
     |      
     |       - For `MODE_CFB`, *ciphertext* length (in bytes) must be a multiple
     |         of *segment_size*/8.
     |      
     |       - For `MODE_CTR`, *ciphertext* can be of any length.
     |      
     |       - For `MODE_OPENPGP`, *plaintext* must be a multiple of *block_size*,
     |         unless it is the last chunk of the message.
     |      
     |      :Parameters:
     |        ciphertext : byte string
     |          The piece of data to decrypt.
     |      :Return: the decrypted data (byte string, as long as *ciphertext*).
     |  
     |  encrypt(self, plaintext)
     |      Encrypt data with the key and the parameters set at initialization.
     |      
     |      The cipher object is stateful; encryption of a long block
     |      of data can be broken up in two or more calls to `encrypt()`.
     |      That is, the statement:
     |          
     |          >>> c.encrypt(a) + c.encrypt(b)
     |      
     |      is always equivalent to:
     |      
     |           >>> c.encrypt(a+b)
     |      
     |      That also means that you cannot reuse an object for encrypting
     |      or decrypting other data with the same key.
     |      
     |      This function does not perform any padding.
     |      
     |       - For `MODE_ECB`, `MODE_CBC`, and `MODE_OFB`, *plaintext* length
     |         (in bytes) must be a multiple of *block_size*.
     |      
     |       - For `MODE_CFB`, *plaintext* length (in bytes) must be a multiple
     |         of *segment_size*/8.
     |      
     |       - For `MODE_CTR`, *plaintext* can be of any length.
     |      
     |       - For `MODE_OPENPGP`, *plaintext* must be a multiple of *block_size*,
     |         unless it is the last chunk of the message.
     |      
     |      :Parameters:
     |        plaintext : byte string
     |          The piece of data to encrypt.
     |      :Return:
     |          the encrypted data, as a byte string. It is as long as
     |          *plaintext* with one exception: when encrypting the first message
     |          chunk with `MODE_OPENPGP`, the encypted IV is prepended to the
     |          returned ciphertext.

FUNCTIONS
    new(key, *args, **kwargs)
        Create a new AES cipher
        
        :Parameters:
          key : byte string
            The secret key to use in the symmetric cipher.
            It must be 16 (*AES-128*), 24 (*AES-192*), or 32 (*AES-256*) bytes long.
        :Keywords:
          mode : a *MODE_** constant
            The chaining mode to use for encryption or decryption.
            Default is `MODE_ECB`.
          IV : byte string
            The initialization vector to use for encryption or decryption.
            
            It is ignored for `MODE_ECB` and `MODE_CTR`.
        
            For `MODE_OPENPGP`, IV must be `block_size` bytes long for encryption
            and `block_size` +2 bytes for decryption (in the latter case, it is
            actually the *encrypted* IV which was prefixed to the ciphertext).
            It is mandatory.
           
            For all other modes, it must be `block_size` bytes longs.
          counter : callable
            (*Only* `MODE_CTR`). A stateful function that returns the next
            *counter block*, which is a byte string of `block_size` bytes.
            For better performance, use `Crypto.Util.Counter`.
          segment_size : integer
            (*Only* `MODE_CFB`).The number of bits the plaintext and ciphertext
            are segmented in.
            It must be a multiple of 8. If 0 or not specified, it will be assumed to be 8.
        
        :Return: an `AESCipher` object

DATA
    MODE_CBC = 2
    MODE_CFB = 3
    MODE_CTR = 6
    MODE_ECB = 1
    MODE_OFB = 5
    MODE_OPENPGP = 7
    MODE_PGP = 4
    __revision__ = '$Id$'
    block_size = 16
    key_size = (16, 24, 32)



In [27]:
K = open('/dev/urandom').read(16)
K
Out[27]:
'\xb3\x1a\xd9#b\x8a\x1b{T\xff\xa9g@q[\xe5'
In [28]:
A = AES.new(K)
In [29]:
msg = '\x00'*128
msg
Out[29]:
'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00'
In [30]:
A.encrypt(msg)
Out[30]:
'\xaf\x1c\xd4AE\xa3BZ\xb1\xc0\xad\x8c\x1d86$\xaf\x1c\xd4AE\xa3BZ\xb1\xc0\xad\x8c\x1d86$\xaf\x1c\xd4AE\xa3BZ\xb1\xc0\xad\x8c\x1d86$\xaf\x1c\xd4AE\xa3BZ\xb1\xc0\xad\x8c\x1d86$\xaf\x1c\xd4AE\xa3BZ\xb1\xc0\xad\x8c\x1d86$\xaf\x1c\xd4AE\xa3BZ\xb1\xc0\xad\x8c\x1d86$\xaf\x1c\xd4AE\xa3BZ\xb1\xc0\xad\x8c\x1d86$\xaf\x1c\xd4AE\xa3BZ\xb1\xc0\xad\x8c\x1d86$'
In [31]:
A = AES.new(K,AES.MODE_CBC, '\xff'*16)
In [32]:
A.encrypt(msg)
Out[32]:
'fk-a\x1c\xf8\x14\x82\nU\xf9\xda\xd6\xd6\x84\x8bp\xa9\xacF\xa0\x82v\t\xaa>\x90\xb5EA\x9fR\t\xa5\x134\xf2\xe8BlK\x08\xc0\x97\xe7\x1f\x16\x17I\x06\xea\x1e\xea\x8a7\x01\xed\xb7P/\xd9j4\xf4\x82\xc5q%\x92\xba\xc6c\xfe)\xbf\x85\x05\xe8}-\xdd\xfa\x9ac\x94\x0f\x86\xfc\xbd\xf7.\xac\x9b\x1d i\xeb\x00?o\x0b\xbb\xc9\xfa?f\x8a,^g\n\xf8\xc5\xad#\xa3\xfbe\xd1\xde]\xd4\x0fo\x81i\x89B'

Modes opératoires

On note \(E(P,K)\) la fonction de chiffrement d'un bloc \(P\) avec la clef \(K\), et \(D(C,K)\) la fonction de déchiffrement.

ECB (Electronic Code Book)

Les blocs identiques sont chiffrés de la même manière \[C_i = E(P_i,K)\]$ Comme on l'a vu, c'est à éviter.

CBC (Cipher Block Chaining)

On effectue sur chaque bloc un ‘OU exclusif’ avec le chiffrement du bloc précédent avant de le chiffrer. On utilise un vecteur d'initialisation (IV), généralement aléatoire, comme premier bloc. \[C_0 = IV,\ C_i = E(C_{i-1}\oplus P_i,K)\]

CFB (Cipher Feedback)

C'est un chiffrement par flux : \[C_0=IV,\ C_i=P_i\oplus E(C_{i-1},K)\]

CTR (Counter)

On engendre un flux en chiffrant un compteur (une fonction \(g(i)\)). \[C_i = P_i\oplus E(IV+g(i))\]

OFB (Output Feedback)

Ce mode transforme un chiffrement par blocs en un chiffrement par flux synchrone, c'est à dire que le flux est indépendant du clair et du chiffré. Cette propriété facilite l'emplo de codes correcteurs d'erreurs. \[I_0=IV,\ O_i=E(I_i,K),\ I_i=O_{i-1},\ C_i=P_i\oplus O_i\]

PGP (OpenPGP CFB Mode)

C'est une variante du mode CFB imposée par openPGP. Voir RFC 4880.

In [33]:
A = AES.new(K,AES.MODE_CFB,IV='\xff'*16)
In [34]:
A.encrypt(msg)
Out[34]:
'f\x0e\x03v\xd6\x8b\x9f\x93\xc10y\x16lR|\x06\xc9l\xe4\x8d}\xb1\xa6\x903\xc0\xbb\xc7\xed\xb4/\x95\xe6\xb3t\xfd\x06}>\x80b\xb1U\x0c\xff\xbf\x7fk\xba2\xb7\x9bu\xb3T|_\xd4@\x847E\xf4\x9am\xd3\xd5\xbf,\xae\x02\xaes\xa3\x89\xf6\n\xe6C\xe5\x9c\x97\x8d`\x0f3\xb0\x88."\xd7\x89\x060\xab_\x88Z}\x06\xc4:\x83\xb9)\xaf=\xd9\n\xf5\x9a\x84T\xff\xda&W{`\xd6\xf0\xd6\xedQ9\xc1CK'
In [36]:
from Crypto.Util import Counter
ctr = Counter.new(128, initial_value=42)
A = AES.new(K,AES.MODE_CTR,counter = ctr)
In [37]:
A.encrypt(msg)
Out[37]:
'\xa3j Q\xd6\xf8W\x1f\xef\xca\xf1\xcfB\xafq+\x82\x1e~\x7f\xef\xfa%\x99\x99r\xb2\xdb\x9c\xfd(\x9e;\x9d2\xf4\x8cg\xe28\xf5\xe1\xf1\x8d\x04\x01\x9e\x10\x1b\x95[e\xc8;m\xc9P(\xef\xe1\x1ciz$\xabO\xd7\xbe\xb5\xc2\x8f\xfe8\xf0\xfdp}\xdf\xdc~i\x143Ah\xb99\xbf\xc3 \xf2\xe2\x91\x82\rv-\xd0\xca\x87\xf5\xf3yF#%A\xe6|.\xe0\xd8/!>b\x14\xdf8D\xe1\xc5\xcbs\x0f\xba?y'
In [50]:
A = AES.new(K,AES.MODE_OFB,IV='\xff'*16)
In [51]:
A.encrypt(msg)
Out[51]:
'y\xe8\xa4\xde\xff\x1e\x00A\xfe\xe3\x9f\xac$\x19*CAp\x02\x8c\xc5\xa9Y&\xb0%J\xfdK\xe1\xefK9U.\xf8\xf7\xad\xcc\xbb\x91\xf6\xa5\xcep :1\\=\xfd\xca\xd6\xbfj\xd9(\x0b5\xb6S\x9b\xfa\xf1\x10\xfa\xff\x9co\x1e\xec\x01\x06;G\x7fj\x99\xe9\xfb\xcb\x84\rl\xed\xe2\x0e[\xb5\xef\x13Z\xc9\xca\x96>\xb4\x1f\xdft\xf2\xf3\x88\xe7\xc7\x83\x1c\xf9\x86\xe7\xd1ci\xf5\x89\xe5\xbb\xa2#RA\xc8\x15\xf3\x1e\x86#a'

Sécurité des chiffrements par blocs.

On distingue plusieurs niveaux d'attaque :

  • Chiffré connu seul
  • Clair connu
  • Clair choisi

On a vu que la force brute (test de toutes les clefs possibles) était devenue possible sur les \(2^{56}\) clefs du DES. Elle reste impraticable avec des clefs plus longues, mais il existe des techniques permettant de réduire l'espace des clefs possibles.

La cryptanalyse linéaire (Matsui 1992).

Cette technique s'applique aux réseaux de permutations-substitutions (SPN). C'est une attaque à texte clair connu. L'attaquant doit disposer d'un grand nombre de couples (X,Y) de textes clairs/textes chiffrés.

L'idée est de trouver une relation linéaire

\[X_{i_1}\oplus X_{i_2}\oplus\cdots\oplus Y_{j_1}\oplus Y_{j_2}\cdots = K_{l_1}\oplus K_{l_2}\oplus\cdots\]

entre certains bits de l'entrée \(X\), de la sortie \(Y\) et de la clé \(K\) qui ne soit pas aléatoire. Si les bits d'entrée et de sortie étaient des variables aléatoires indépendantes, un telle relation serait vérifiée en moyenne une fois sur deux (probabilité \(\frac12\)).

Supposons qu'on en connaisse une qui ait une probabilité \(p\) aussi différente de \(\frac12\) que possible.

Algorithme 1 de Matsui

  • Collecter un grand nombre \(N\) de couples \((X,Y)\)
  • Pour chaque couple, calculer le membre gauche de l'expression linéaire. Soit \(T\) le nombre de résultats nuls.
  • Si \(T\) est plus grand que \(N/2\) et si \(p > \frac12\) , on conclut que le membre droit doit être 0
  • Si \(T< N/2\) et si \(p < \frac12\) , on conclut encore que le membre droit est 0
  • Dans les autres cas, on conclut que le membre droit est 1

Ce n'est pas très efficace, mais on peut faire mieux avec le même principe. On va cette fois tester toutes les valeurs possibles des bits de la clé concernés par le membre droit de la relation.

Algorithme 2 de Matsui

  • Collecter un grand nombre \(N\) de couples \((X,Y)\)
  • Pour chaque jeu de bits de clé candidats, on calcule une valeur \(T\) égale au nombre de fois que la relation est vérifiée
  • On sélectionne les candidats qui ont un \(T\) le plus éloigné possible de \(N/2\).

Pour mettre en oeuvre cette technique, il faut commencer par calculer des « approximations linéaires » des seuls éléments non linéaires du système, à savoir les S-boîtes.

Si \(X\) et \(Y\) sont l'entrée et la sortie de la S-boîte considérée, sa table d'approximation linéaire est une matrice \(2^l\times 2^m\) dont l'entrée \((i,j)\) est \(T(i,j)-2^{l-1}\), où \(T(i,j)\) est le nombre de fois que la relation linéaire \(X|i = Y|j\) codée par les bits 1 de \(i\) et \(j\) est vérifiée.

Voir ici pour plus de détails.

Le livre Modern Cryptanalysis de Christopher Swenson contient un exemple détaillé en Python.

La cryptanalyse différentielle

C'est une attaque à texte clair choisi. Voir ici. La cryptanalyse repose sur des paires de textes clairs qui ont une différence constante. L'opération de différence peut être définie de diverses manières, la Fonction OU exclusif est la plus courante. L'attaquant calcule ensuite les différences dans les textes chiffrés, afin d'en extraire des motifs pouvant indiquer un biais. Les différences en sortie du chiffrement sont nommées des différentielles.

Il est maintenant connu que le DES avait été modifié pour résister à cette attaque, alors qu'elle n'a été officiellement découverte qu'à la fin des années 80.

D'autres algorithmes, comme FEAL-4 ont pu être cassés par cette technique.

On trouvera une liste d'attaques ici.

In [ ]: