Td corrigé Exercice EXR1530 : Attaque force brute - ASI @ INSA Rouen pdf

Exercice EXR1530 : Attaque force brute - ASI @ INSA Rouen

Si on considère une moyenne de un million de clés par seconde et par machine, ... indiquez quel morceau de texte vous allez pouvoir utiliser pour trouver la clé ? .... de l'algorithme DES avec une clé K donne le bloc plain text, alors cette clé K ...




part of the document



chines (ie Deep Crack, de l’ordre de 250 kEuro) permettant de casser une clé en 72 heures environ (source : http://www.eff.org/Privacy/Crypto_misc/DESCracker/HTML/19980716_eff_des_faq.html#whatsdes)

Question
1. Avant de demander au chef de service de commander une machine « Deep Crack », vérifier que l’ordre de grandeur est correct (en matière de sécurité, il faut se méfier des rumeurs). pour calculer rapidement l’ordre de grandeur, souvenez-vous que 2puissance(ln a / ln 2) = a.
2. Si votre chef de service n’est pas convaincu, indiquez-lui dans combien de temps il sera possible de casser une clé DES 56 bits sur un ordinateur personnel haut de gamme dans un délai aussi court que sur Deep Crack, en appliquant la loi de Moore.
3. Quels est(sont) le(s) élément(s) nécessaire(s) pour casser la clé (paramètre(s) en entrée d’un outil de cassage de clé) ?
4. A l’aide des articles de la section Document, indiquez quel morceau de texte vous allez pouvoir utiliser pour trouver la clé ?
5. Que pensez-vous des personnes qui annoncent péremptoirement que DES n’est pas fiable ?
Document

Extrait de : http://www.faqs.org/faqs/jpeg-faq/part1/section-15.htmlIf you have an alleged JPEG file that your software won't read, it's likely
to be some proprietary JPEG-based format. You can tell what you have by
inspecting the first few bytes of the file:

1. A JFIF-standard file will start with the four bytes (hex) FF D8 FF E0,
followed by two variable bytes (often hex 00 10), followed by 'JFIF'.

2. If you see FF D8 FF at the start, but not the 'JFIF' marker, you
probably have a not-quite-JFIF JPEG file. Most JFIF software should
read it without complaint. If you are using something that is picky
enough to complain about the lack of a JFIF marker, try another decoder.
(Both very old JPEG files and very new ones may lack JFIF markers ---
the new SPIFF standard mentioned above doesn't use a JFIF marker.
So gripe to your software vendor if you find this to be the problem.)

3. A Macintosh PICT file, if JPEG-compressed, will have several hundred
bytes of header (often 726 bytes, but not always) followed by JPEG data.
Look for the 3-byte sequence (hex) FF D8 FF. The text 'Photo - JPEG'
will usually appear shortly before this header, and 'AppleMark' or
'JFIF' will usually appear shortly after it. Strip off everything
before the FF D8 FF and you will usually be able to decode the file.
(This will fail if the PICT image is divided into multiple "bands";
fortunately banded PICTs aren't very common. A banded PICT contains
multiple JPEG datastreams whose heights add up to the total image
height. These need to be stitched back together into one image.
Bailey Brown has some simple tools for this purpose on a Web page at
http://www.isomedia.com/homes/bailey/photo-jpeg/photo-jpeg.html.)

4. If the file came from a Macintosh, it could also be a standard JFIF
file with a MacBinary header attached. In this case, the JFIF header
will appear 128 bytes into the file. Get rid of the first 128 bytes
and you're set.

5. Anything else: it's a proprietary format, or not JPEG at all. If you
are lucky, the file may consist of a header and a raw JPEG data stream.
If you can identify the start of the JPEG data stream (look for FF D8),
try stripping off everything before that.

At least one release of HiJaak Pro writes JFIF files that claim to be
revision 2.01. There is no such spec; the latest JFIF revision is 1.02.
It looks like HiJaak got the high and low bytes backwards. Unfortunately,
most JFIF readers will give up on encountering these files, because the JFIF
spec defines a major version number change to mean an incompatible format
change. If there ever *were* a version 2.01, it would be so numbered
because current software could not read it and should not try. (One wonders
if HiJaak has ever heard of cross-testing with other people's software.)
If you run into one of these misnumbered files, you can fix it with a
binary-file editor, by changing the twelfth byte of the file from 2 to 1.
Pour information, allure binaire d’un fichier JPG pris sur un PC
Correction
1. Ordre de grandeur
Le nombre de clés essayés par l’expérience ci-dessus est de (au calcul au dimension prêt) :
10 000 machines * 42 jours * 1 000 000.
Ce nombre est-il de l’ordre de 2puissance56 ?

(1) 10 000 machines * 42 jour/machine * 24 heures/jour * 3600 secondes/heure * 1 000 000 clés/secondes

Pour travailler sans risque avec les grands nombres (éviter des fautes de frappe, …), nous allons travailler sur les puissance de 2 de chacun des paramètres de la formule (1) :
Ln (10 000 ) / ln (2) = 13 à 14, donc 10 000 = 213
Ln ( 42 ) / ln (2) = 5 à 6
Ln (24) / ln (2) = 4 à 5
Ln (3600) / ln (2) = 11 à 12
Ln (1 000 000 ) / ln (2) = 19 à 20

La relation (1) ci-dessus peut donc s’écrire :

Si on prend les minima
213 * 25 * 24 * 211 * 219 = 25(13+5+4+11+19) = 252
Si on prend les maxima
214 * 26 * 25 * 212 * 220 = 257

On est donc bien dans l’ordre de grandeur, à savoir 256 clés essayées.

2. Loi de Moore

2.1 Recherchons N, le nombre d’opérations effectué en 72 heures avec la puissance actuelle :
La puissance de calcul actuelle est de 1000000 de combinaison par seconde.
Il y a 3600 secondes par heures, soit en puissances de 2:
2^6*2^11*2^19 < 1000000*3600*72 < 2^7*2^12*2^20
2^36 < N < 2^39


Tous les 18 mois, la puissance de calcule est multipliée par 2.
On a:
N*2^t=2^56, avec t le nombre de multiples de 36 mois.

Alors, si N=2^a,
2^(t+a)=2^56
Soit
(t+a) = 56

t=56-a,
Sachant que 36 < a < 39,
on a : -36 > a > -39
D’où: 56-36 > 56-a > 56-39
alors (eq 1) 20 > t > 17
(eq 2) A = t*1.5 (où A est le nb d’années)
(eq 3) 1.5*20 > 1.5*t > 1.5*17
ce qui est équivalent à (d'après (eq 2) et (eq 3))
30 ans > A > 25,5 ans

Notre résultat à l’air dêtre juste car nous sommes dans le même ordre de grandeur que l’article ci-dessous :

Source :  HYPERLINK "http://www.eff.org/Privacy/Crypto_misc/DESCracker/HTML/19980716_eff_des_faq.html#keylength" http://www.eff.org/Privacy/Crypto_misc/DESCracker/HTML/19980716_eff_des_faq.html#keylengthHow long should cipher keys be to avoid these attacks?
According to 1996 study by cryptographay experts, "Minimal Key Lengths for Symmetric Ciphers to Provide Adequate Commercial Security" ( ftp://research.att.com/dist/mab/keylength.txt ), secret-key ciphers used to protect data over the next 20 years should have an effective key length of at least 90 bits. (Public key ciphers, such as RSA and Diffie-Hellman, need longer keys). 

3. Paramètres en entrée de Deep Crack :
un bloc de texte encrypté d’une longueur 64 bits
le bloc de texte original correspondant (plain text)

Rappel du fonctionnement d’un algo de cassage de clé :
Dès que l’application de l’algorithme DES avec une clé K donne le bloc plain text, alors cette clé K correspond au texte original.

Quelques rappels sur DES :
C’est un algorithme dont le source est public.
Il est réversible :
Si j’applique 2 fois l’algo sur un message A, je retrouve le message initial (il n’y a pas un algo pour encrypter et un autre pour décrypter).
DES prend le message initial et applique l’algorithme sur des morceaux du fichier (à encrypter) de 64 bits (au début du traitement, DES retire 1 bit de chacun des 8 octets pour parvenir à un premier morceaux de 56 bits, en phase avec la longueur de la clé !).

4. Interpol

Dans la mesure où nous n’avons aucune information sur la validité de la source consultée ainsi que sur la pérennité des informations données, une vérification de la véracité des informations est effectuée par la consultation des fichiers JPG sur notre ordinateur (PC avec Windows, comme le pirate).

On retrouve bien ce qui est prévu par l’article, à savoir
FF D8 FF E0 00 10
Le 7ème octet (0x4A = 74) correspond au caractère J
Le 8ème octet (0x46 = 70) correspond au caractère F
Le 9ème octet (0x49 = 73) correspond au caractère I
Le 10ème octet (0x46 = 70) correspond au caractère F
Il y a donc de grande chance pour que le bloc des 64 premiers bits du texte encrypté (ciphertext) corresponde au texte original (plain text) suivant :
FF D8 FF E0 00 10 4A 46

Quelques informations complémentaires

Les images JPG peuvent servir à véhiculer des messages secrets.
Par exemple des messages textes dont les lettres sont « dissimulées » dans l’image par substitution de la valeur d’un pixel par la valeur d’une lettre alphabêtique ; ces substitutions de quelques pixels sur les milliers dont sont constituées les images sont invisibles à l’œil nu. Il suffit à l’émetteur et au destinataire d’utiliser les mêmes tables leur permettant de savoir quels sont les pixels impactés (ie lettre 1 au pixel 107 ; lettre 2 au pixel 458, …).
Source : http://www.eff.org/Privacy/Crypto_misc/DESCracker/HTML/19980716_eff_des_faq.html#howsitworkDoes the EFF DES Cracker really work?
The EFF DES Cracker first solved a challenge posed more than a year ago by world-renowned cryptographer and AT&T Labs research scientist, Matt Blaze. The "Blaze Challenge" was designed to only be solvable by "brute force" cryptanalysis of DES. Mr. Blaze challenged the world to find matching pairs of plaintext and ciphertext numbers, consisting of nothing but repeated digits. Blaze himself was unaware of any such pairs until the EFF DES Cracker revealed the first known pair. It found that a hexadecimal key of 0E 32 92 32 EA 6D 0D 73 turns a plaintext of 8787878787878787 into the ciphertext 0000000000000000.
5. Il existe effectivement des moyens de casser une clé DES MAIS aucune méthode n’a de chance de réussir à 100% dans un temps connu d’avance (il faut quand même faire des hypothèses sur le morceau de plain text que l’on cherche).
De plus, étant donné les moyens à mettre en œuvre, la valeur de l’information à découvrir doit être à la hauteur des investissements consenti pour que les craintes soit objectivement justifiées.
INSA-ROUEN - ASI  PAGE 4/ NUMPAGES 4 UV Réseaux




 :