Ciphers de bloc | Mode de retour en sortie | Mode Compteur | Alison
Loading
Notes d'étude
Study Reminders
Support
Text Version

Mode de retour en sortie et mode de compteur

Set your study reminders

We will email you at these times to remind you to study.
  • Monday

    -

    7am

    +

    Tuesday

    -

    7am

    +

    Wednesday

    -

    7am

    +

    Thursday

    -

    7am

    +

    Friday

    -

    7am

    +

    Saturday

    -

    7am

    +

    Sunday

    -

    7am

    +

Fondations de CryptographyProf. Dr. Ashish Choudhury (Former) Infosys Foundation Career Development Chair ProfessorInternational Institute of Information Technology-BangaloreLecture-17Modes of Operations of Block Ciphers Part IIHello everyone, welcome to lecture 16. Au cours de cette conférence, nous poursuivrons notre discussion sur les modes de fonctionnement des algorithmes de chiffrement par bloc. (Référez-vous à la diapositive: 00 :36) Plus précisément, la feuille de route pour cette conférence est la suivante: nous discuterons de la façon de concevoir des chiffrements sécurisés de CPA à l'aide de 2 modes d'opérations, à savoir le mode de rétroaction en sortie et le mode de compteur de fonctionnement. (Voir Heure de la diapositive: 00 :50) Donc, commençons par le mode de retour en sortie ou le mode OFB en bref. Donc, l'idée ici est fondamentalement l'expéditeur et le récepteur génèrent un flux pseudo-aléatoire de pad, qui est en fait indépendant du texte en clair, que l'expéditeur veut chiffrer. Et une fois que le flux pseudo-aléatoire de l'extrusion est généré et que le message est disponible, le flux pseudo-aléatoire de l'extrusion est utilisé pour XORing ou le masquage du message. Alors, voyons comment le flux pseudo-aléatoire de l'extrusion est généré. Donc, l'expéditeur choisit au hasard un IV, ce que nous ne faisons pas comme y0.Et la taille de la IV doit être la même que la longueur de bloc de votre fonction sous-jacente F. Et alors imaginez que nous voulons générer 3 blocs de flux pseudo-aléatoires d'extrusions ici c'est comme nous allons. Nous invotons donc 3 invocations sous-jacentes de la fonction F, toutes instanciées avec la même clé k et nous alimentons l'IV en entrée de bloc pour le premier appel, obtenez la sortie y1, et ensuite nous faisons le chaînage, mais maintenant ce chaînage est différent du mode de cryptage CBC que nous avions vu lors de la dernière conférence. Ici, le chaînage est indépendant du bloc de messages car à l'heure actuelle, il n'y a pas de texte en clair qui s'implique ici. Donc, la sortie y1 est alimentée comme l'entrée de bloc pour le second appel de la fonction pour obtenir le second bloc de pseudo-flux pseudo-aléatoire de pad que nous pourrions dénoter comme y2, puis ceci est alimenté comme l'entrée de bloc pour le troisième appel, et nous pouvons continuer comme ce droit. Donc, c'est ainsi que le flux pseudo-aléatoire de l'extrusion est généré. Et maintenant, si le message est disponible pour le chiffrement, quel que soit le flux pseudo-aléatoire de remplissage qui a été généré jusqu'à présent, il peut être utilisé pour le message maître en fonction de la longueur du message. Donc, vous pouvez imaginer que le chiffrement ici est maintenant un processus en 2 étapes et un processus hors ligne et un processus en ligne où dans la phase hors ligne ou une phase indépendante du message un flux pseudo-aléatoire de pad est généré. Et pendant la phase en ligne lorsque le message réel est disponible, nous faisons le chiffrement en utilisant n'importe quelle extrusion qui a été générée dans la phase hors ligne comme le masque droit. Ainsi, si le IV est également communiqué au récepteur et que le récepteur peut également générer un flux pseudo-aléatoire de remplissage hors ligne et une fois que le message est chiffré du côté de l'expéditeur et qu'il est communiqué au récepteur, il peut être déchiffré correctement.Ainsi, dans cet exemple spécifique, le chiffrement du message sera constitué de l'IV et du chiffrement effectif, à savoir c1 c2 c3, à droite. Et pour déchiffrer, nous faisons l'opération correspondante, à savoir récupérer le bloc de texte en clair, ce que nous faisons est le récepteur a besoin de la moelle de pseudo-flux aléatoire et qui peut être calculé en faisant simplement cette opération et une fois que le bloc de moelle de pseudo-flux aléatoire est disponible, il peut être XORed du bloc de chiffrement de la ith pour récupérer le texte en clair. Cela signifie, il est suffisant dans ce mode de fonctionnement, pour que le F ne soit qu'une fonction pseudo-aléatoire, nous n'avons pas besoin de la fonction f pour être une fonction inversable. C'est là, il suffit que F (k) soit juste un PRF. Et l'avantage de ce mode de fonctionnement est que le flux peut être précalculé et une fois précalculé le calcul du texte chiffré est parallélisable. Cela signifie que nous ne pouvons pas générer le flux de blocs en parallèle car la génération de l'extrusion se produit de manière séquentielle.Mais une fois que la phase hors ligne est terminée et que l'extrusion est disponible, quel que soit le bloc de message que nous voulons que le chiffrement crypté puisse se produire en parallèle, d'ailleurs, l'autre avantage ici est qu'un texte en clair peut ne pas être un multiple de la longueur de bloc de votre fonction sous-jacente F, cela signifie ici que nous n'avons pas besoin de padding sophistiqué pour faire la longueur du message pour être un multiple de la longueur de bloc de votre fonction sous-jacente avant de crypter le message, c'est différent de votre mode de cryptage CBC. Et il peut être prouvé formellement que si votre fonction clé sous-jacente F (k) est un PRF sécurisé, alors ce mode de fonctionnement, c'est-à-dire le mode OFB est sécurisé CPA, nous pouvons aussi prouver qu'une variante avec état est aussi sécurisée par l'ACP, imaginez un scénario où l'expéditeur et le récepteur sont synchronisés et ils ont généré un flux pseudo-aléatoire y1 y2 y3 et qui est utilisé pour chiffrer un message m. Et maintenant, il y a un nouveau message m ’ pour le chiffrement qui est disponible pour l'expéditeur. Ainsi, si l'expéditeur veut maintenant chiffrer un message m ’ à l'aide du mode OFB, il n'est pas nécessaire de choisir un nouveau IV le y3 qui a été utilisé qui a été le dernier bloc du pseudo-clavier aléatoire pour le message précédent peut être utilisé comme IV pour le message m ’ et à l'aide de y3 nous pouvons démarrer l'ensemble du processus. Et générer un flux pseudo-aléatoire frais qui peut être ensuite utilisé pour masquer le nouveau message m ’ et il peut être prouvé qu'une variante avec état de ce mode OFB est également CPA secureright. Donc, plus ou moins nous obtenons tous les avantages que nous voulons ou nous attendons du meilleur mode de fonctionnement possible. À savoir que nous avons maintenant la sécurité de l'ACP, nous avons l'hypothèse minimale requise de la fonction sous-jacente, c'est-à-dire l'hypothèse du PRF. Et si nous supposons que l'extrusion a été générée dans la phase hors ligne et que le calcul du texte chiffré est parallélisable, et ainsi de suite. Mais il s'avère que nous pouvons faire mieux, à droite. (Référez-vous à la diapositive: 06 :26). Un meilleur mode de fonctionnement est le mode de fonctionnement du mode CTR. Et l'idée ici est plus ou moins la même. Nous divisons le processus de cryptage en deux phases. La première phase est la phase indépendante du message, où un flux pseudo-aléatoire de remplissage est généré et qui est ensuite utilisé pour faire le masquage réel du message. Mais maintenant, la façon dont le pseudo-flux aléatoire de remplissage sera généré, tout peut être parallélisé, c'est-à-dire que la génération de l'extrusion ainsi que le chiffrement réel peuvent être mis en parallèle. Donc voici comment le mode de compteur de fonctionnement est exécuté. Donc, comme en mode OFB, nous commençons par un aléatoire IV, que nous appelons le compteur, et le compteur est sélectionné au hasard à partir du domaine de la longueur de bloc de votre fonction sous-jacente. Il s'agit donc d'une chaîne de bits uniformément aléatoire de longueur L et qui sera également une partie du texte de chiffrement. Et puis nous générons le flux pseudo-aléatoire de l'extrusion, mais contrairement au mode OFB, nous ne faisons pas de chaînage ici, la façon dont nous générons le flux pseudo-aléatoire de l'extrusion est comme suit. Donc, le premier appel de votre fonction F sera avec le compteur d'entrée plus un, le second appel de la fonction sera avec le compteur d'entrée plus 2 et ainsi de suite. Cela signifie que tous les appels suivants d'appel de la fonction seront avec une entrée qui est une valeur supérieure à la valeur précédente du compteur utilisé dans l'appel précédent ou précédent de la fonction. Et une fois que les fonctions F sont évaluées sur cette entrée, nous obtenons le flux pseudo-aléatoire de blocs de blocs qui peut être amené à utiliser pour masquer réellement votre message pour le droit de cryptage. Donc c'est la seule différence ici, la façon dont nous générons le pseudo-flux aléatoire de pad, restant toutes les opérations restent les mêmes que dans le mode OFB ici. Donc ici encore, le chiffrement réel du message sera constitué de votre contre-valeur, qui sera le bloc c0, et en fait les blocs de chiffrement sont les blocs codés seront c1 c3 okay. (Voir Diapositive Heure: 08 :26) Donc, comme dans le mode OFB, nous pouvons en fait prouver formellement qu'il suffit que la fonction clé sous-jacente soit juste un PRF pour que le mode de fonctionnement du compteur soit sécurisé par CPA. Parce que pour le processus de décryptage, nous n'avons pas besoin de calculs d'inversion. C'est pourquoi il suffit que la fonction clé sous-jacente soit juste un PRF. Plus important encore, le chiffrement et le décryptage peuvent se produire en parallèle. C'est parce que si vous voyez de près la façon dont nous générons le pseudo-flux aléatoire de pad. Si je veux générer y2 je n'ai pas besoin de dépendre de y1 qui était le cas en mode OFB, en mode OFB et jusqu'à et sauf si vous générez, y1 vous ne pouvez pas calculer y2 et donc jusqu'à et si y2 est calculé, vous ne pouvez pas générer y3 et ainsi de suite. C'est pourquoi le pseudo-flux aléatoire de génération de l'extrusion qui n'était pas parallélisable. Mais la façon dont nous générons le flux pseudo-aléatoire de l'extrusion et le mode de compteur de fonctionnement, y2 peut être généré indépendamment de y1 et ainsi de suite. En ce sens, le chiffrement et l'opération de déchiffrement peuvent être parallèles à droite. Plus important encore dans le mode de compteur de fonctionnement, si je veux juste déchiffrer un bloc de chiffrement spécifique, et que je ne suis pas intéressé à déchiffrer les autres blocs qui est possible, et que pour appeler simplement un appel de la fonction clé sous-jacente, par exemple, si je veux juste déchiffrer c2, pour décrypter c2 ce dont j'ai besoin est y2.Et y2 me demande juste d'appeler la fonction sous-jacente sur le compteur de valeur plus 2. Donc si j'ai la contre-valeur initiale, qui est là en c0, et si je décrypte c2 ce que je dois faire, je dois créer c0 comme valeur de compteur, le compteur de calcul plus 2 appellent mon soulignement keyedfunction sur le compteur d'entrée plus 2 générer le pseudo-pad y2 et XOR it de c2qui me donnera de retour m2.Donc, en fonction de mon besoin, je peux décrypter n'importe quel bloc de texte spécifique en appelant juste un appel de la fonction de clé sous-jacente, ce qui n'était pas possible en mode OFB. Et plus important encore, nous pouvons prouver formellement que la variante avec état du mode de fonctionnement est également sécurisée par l'ACP. Cela signifie que si j'ai un message m, et que mon résultat final est c0, c1 c2 c3, où y3 a été le dernier flux de pseudo-pad aléatoire. Et maintenant j'ai un nouveau message m ’, donc, je n'ai pas besoin de choisir une valeur de compteur frais pour générer un flux pseudo-aléatoire de pad pour le message m ’, je peux utiliser y3 comme valeur de compteur pour générer la séquence suivante de pseudo-aléatoire pour le message m ’, et la même chose peut être faite à l'extrémité du récepteur, et il peut être prouvé précédemment que la variante avec état est aussi la CPA sécurisée. Nous avons donc maintenant presque exactement toutes les fonctionnalités dont nous avons besoin, le bon mode de fonctionnement du chiffrement par bloc. Et c'est pourquoi ce mode de fonctionnement est très populaire, qui est utilisé dans plusieurs instanciations des protocoles du monde réel. (Voir la diapositive: 11 :25) Nous voulons donc faire une analyse de sécurité rigoureuse de la sécurité de CPA pour ce mode de fonctionnement du compteur. Donc, je vais utiliser cet exemple. Alors imaginez un scénario où un émetteur a chiffré un message composé de 3 blocs de droite et c'est ainsi que le mode de fonctionnement du compteur aurait fonctionné. Et nous voulons prouver que ce mode de fonctionnement est sécurisé par l'ACP. Alors, avant d'entrer dans la véritable preuve de sécurité du mode de fonctionnement, considérons une variante de ce compteur de fonctionnement où tout reste tel qu'il est dans le mode de fonctionnement réel du compteur, sauf que tous les appels de la clé PRF sont remplacés par des appels d'une fonction vraiment aléatoire qui est une fonction non indexée. Donc, imaginez que l'expéditeur et le récepteur ont convenu d'une fonction vraiment aléatoire qui est une fonction non indexée, de mapper des chaînes de bits L à L bit strings.So, la variante du mode de compteur de fonctionnement que je dénote en tant que Π??? Est presque identique au mode de compteur réel de fonctionnement, sauf que tous les appels de la fonction à clé Fk sont remplacés par les véritables appels de la fonction vraiment aléatoire f. Maintenant, ce que nous allons prouver, c'est que, si nous considérons cette variante du contre mode de fonctionnement basé sur une fonction vraiment aléatoire. Et si nous considérons tout adversaire de polytime arbitraire participant à une instance de jeu d'indistinction CPA et fait un total de q (n) nombre de requêtes d'oracle de chiffrement, alors la probabilité avec laquelle l'adversaire peut gagner le jeu CPA est bornée par ½ ; + (2 q (n) 2/ 2L), non. Donc, si L est en fait si nous supposons que L est une fonction polynomiale du paramètre de sécurité, et anyhow q (n) est une fonction polynomiale du paramètre de sécurité. Dans l'ensemble, nous finissons par montrer que la probabilité de tout adversaire polytime gagnant le jeu CPA contre ce mode de fonctionnement de compteur basé sur une fonction vraiment aléatoire est à moitié plus négligeable, ce qui satisfait à la définition de la sécurité CPA. Alors, faisons d'abord ça. Une fois que nous le faisons, plus tard nous montrerons que le mode de fonctionnement réel que nous voulons prouver formellement pour être CPA sécurisé, n'est pas sécurisé CPA, alors cela signifie qu'il existe un distinguisher qui peut distinguer le comportement de la fonction pseudo-aléatoire à clé du comportement d'une fonction vraiment aléatoire et qui sera une contradiction avec l'hypothèse que la fonction à clé est une fonction pseudo-aléatoire. Donc, c'est l'idée générale de la preuve, nous allons d'abord considérer une variante du contre-mode de fonctionnement pour prouver qu'il s'agit formellement de CPA.Et puis nous revivirons et nous avanceront que puisque la seule différence entre le mode de fonctionnement réel du compteur et une variante du mode de compteur d'opération est l'invocations sous-jacentes de la fonction. Par conséquent, le mode de fonctionnement réel du compteur devrait également être protégé par l'ACP. Dans le cas contraire, il y a un distinguo qui peut distinguer l'écart de la fonction clé du résultat d'une fonction vraiment aléatoire (voir la diapositive: 14 :37). Alors, faisons d'abord la preuve de la sécurité CPA de la fonction vraiment aléatoire basée sur le compteur de fonctionnement. Alors, considérons un adversaire de calcul arbitraire qui participe à une instance de jeu CPA qui sera composée de 4 phases, nous aurons une phase de formation à l'épreuve du défi et nous aurons une phase de défi, pas vrai. Et pour répondre aux questions de la phase de formation pré-challenge, le challenger choisira une fonction vraiment aléatoire qui ne serait pas connue de ce droit de l'adversaire. Et toutes ces requêtes seront cryptées en exécutant l'algorithme de chiffrement du processus de cryptage basé sur les fonctions réellement aléatoires. Et une fois que la paire de contestation des textes en clair est soumise par l'adversaire, le challenger choisira l'un de ces messages au hasard pour le chiffrement. Et il le chiffrera en choisissant une contre-valeur aléatoire, que je dénote comme CTR* et ensuite c * sera essentiellement la valeur de CTR* sur la fonction vraiment aléatoire XORed avec le message mb. Et puis il y aura une phase de formation post-challenge, là encore, où l'adversaire soumettra des requêtes d'oracle de chiffrement et qui sera crypté conformément à ce processus de cryptage modifié. Et finalement, l'adversaire va déterminer si ce chiffrement de défi est un chiffrement du message m0 ou du message m1, de droite. Supposons donc que le nombre total de demandes que l'adversaire demande dans le cadre de cette expérience est q (n).Le q (n) est une fonction polynomiale du paramètre de sécurité l. De plus, nous supposons également que chaque requête comporte également au plus q (n) nombre de blocs. Donc, en fait, nous supposerons le pire scénario où il y a un total de q (n) nombre de requêtes et chaque requête est exactement composée de q (n) nombre de blocs droit. Donc, je dénote la requête de la moelle pour laquelle l'adversaire a demandé le service d'oracle de cryptage à être Mi.Et puisque Mi se compose de q (n) le nombre de blocs adverses pour répondre au service d'oracle de chiffrement pour répondre au chiffrement de ce message Mi, le challenger doit prendre q (n) le nombre de contre-valeurs. Donc, je dénote ces contre-valeurs comme compteur i + 1, compteur i + q (n) et ainsi de suite. Donc, la première observation est que si l'adversaire soumet le message Mi pour le chiffrement et c est le cryptage de ce message selon cette variante du mode de fonctionnement, alors en voyant l'adversaire chiffré va apprendre la valeur de la fonction vraiment aléatoire inconnue sur ces contre-valeurs, c'est-à-dire compteur i + 1, compteur i + 2 et ainsi de suite. (Voir Diapositive Heure: 17 :20) Pourquoi, alors considérons la jème requête Mi qui consiste essentiellement en q (n) nombre de blocs, à droite et pour crypter ce message, le challenger choisira une valeur de compteur aléatoire, que je dénote comme CTRi à droite. Et une fois que la valeur de compteur est sélectionnée, puisqu'il y a q (n) nombre de blocs dans mon message mi, le challenger a besoin d'évaluer la fonction vraiment aléatoire sur CTRi + 1, CTRi + 2 et CTRi + q (n), ce qui va générer la séquence des blocs de remplissage qui sera XORed avec les blocs de message réels présents dans le message mi pour générer les blocs de chiffrement. Et le texte de chiffrement sera communiqué à l'adversaire comme la réponse de la requête d'oracle de chiffrement, puisque l'adversaire saura la valeur du compteur i et du compteur i + 1 et ainsi de suite. L'adversaire peut simplement exécuter cette opération, à savoir, il peut XORed le bloc jthciphertext et le bloc de message jth présent dans le message mi et cela lui donnera la valeur de la fonction vraiment aléatoire inconnue sur cette contre-valeur, c'est-à-dire compteur i + 2. (Voir la diapositive: 18 :32) Donc, puisque je suppose que mon adversaire va faire q (n) nombre de requêtes que je représente comme message m1 m2 et mq (n) et je suppose que chacun de ces messages se compose plus de q (n) nombre de blocs. Et je suppose que notre challenger dans cette instance de l'expérience utilise ces contre-valeurs pour le chiffrement de ces blocs de messages, à savoir le premier message est chiffré à l'aide des valeurs de compteur CTR1 + 1, CTR1 + 2, CTR1 + q (n) ainsi on.Donc, ce sont les contre-valeurs qui sont utilisées par le challenger. Et comme je l'ai vu, basé sur le chiffrement de son message, l'adversaire apprend la sortie correspondante de la fonction vraiment aléatoire sur les contre-valeurs correspondantes. Donc cela signifie que l'adversaire a essentiellement accès à la valeur de la fonction vraiment aléatoire inconnue f et à toutes les valeurs de compteur qui ont été utilisées par le challenger pour répondre aux requêtes d'oracle de chiffrement. Maintenant, notre objectif est d'analyser quelle est la probabilité de succès de cet adversaire pour déterminer si ce chiffrement de défi est un chiffrement du message m0 ou s'il s'agit d'un chiffrement de m1 et nous pouvons diviser cette probabilité globale en la sommation de 2 probabilités. Alors, considérons le premier cas lorsque les contre-valeurs qui sont utilisées pour préparer le texte de chiffrement c * sont différentes de toutes les valeurs de compteur qui ont été utilisées pour répondre aux requêtes d'oracle de chiffrement soulevées par l'adversaire.C'est le premier cas. Et le deuxième événement est quand les contre-valeurs qui sont utilisées pour préparer le chiffrement de texte de défi se chevauchent ou sont répétées dans au moins une des instances des requêtes d'oracle de chiffrement, à savoir les contre-valeurs qui sont utilisées pour préparer le chiffrement de texte de chiffrement chevauche les valeurs de compteur qui ont été utilisées pour répondre aux requêtes de l'oracle de l'adversaire ’. Il s'agit donc de deux cas distincts (voir la page Diapositive: 20 :33). Et prenons le premier cas et essayez d'analyser quelle est la probabilité que dans ce cas, l'adversaire soit capable de gagner le jeu CPA. Donc nous sommes dans le cas où les contre-valeurs, à savoir CTR* + 1, CTR* + 2 et ainsi de suite, qui sont en fait utilisées pour chiffrer le challenge en clair mb sont différentes de toutes les valeurs de compteur qui ont été utilisées pour répondre aux requêtes de chiffrement de l'adversaire, donc nous sommes dans ce cas. Donc, c'est le challenge en clair mb crypté en évaluant d'abord la fonction vraiment aléatoire sur ces contre-valeurs qui n'ont pas été utilisées jusqu'à présent dans l'une quelconque des requêtes d'oracle de chiffrement pour générer les tampons. C'est ce que notre prochain objectif est. Donc, cela se fera plus ou moins à l'aide du même argument que celui que nous avions utilisé pour prouver la sécurité CPA de notre premier candidat, le plan de sécurité CPA basé sur la fonction pseudo-aléatoire, à droite. Alors souvenez-vous, dans cette preuve, nous avons d'abord considéré une hypothétique construction basée sur une fonction vraiment aléatoire, a prouvé sa sécurité CPA.Puis nous avons donné un argument basé sur la réduction où nous avons montré que la différence dans l'avantage gagnant de l'adversaire entre les 2 instances du jeu CPA est délimitée par une probabilité négligeable si ma fonction sous-jacente est une fonction pseudo-aléatoire. Nous pouvons donc utiliser le même argument ou un argument similaire et finir par montrer que la différence dans l'adversaire qui a remporté le jeu de l'ACP contre le mode de fonctionnement réel du compteur, et que l'adversaire qui a remporté le jeu de l'ACP contre un mode de fonctionnement de compteur basé sur une fonction vraiment aléatoire peut être délimité par une quantité négligeable. Et comme nous savons que l'adversaire gagnant le jeu CPA contre le mode de compteur d'opération est 1/2 + (2 q (n) 2 / 2L) en remaniant le terme nous finissons par obtenir que le mode de compteur de fonctionnement utilisant la pseudo fonction aléatoire est aussi la sécurité de CPA (voir Diapositive: 34 :05) Donc c'est ce que nous finissons par montrer, et qui conclut que le mode de compteur de fonctionnement est en fait CPA sécurisé. Donc, ça m'amène à la fin de cette conférence. En résumé, dans cette conférence, nous avons vu 2 des modes de fonctionnement, soit le mode OFB et le mode de fonctionnement du compteur. Et nous avons aussi vu la preuve de sécurité du contre mode de fonctionnement, le mode de compteur de fonctionnement a plusieurs fonctions.Namely, le chiffrement et le décryptage peuvent se produire en parallèle. Et nous n'avons pas besoin d'une supposition sophistiquée de la fonction clé sous-jacente, elle est suffisante ou suffisante pour que la fonction clé sous-jacente soit juste une fonction pseudo-aléatoire. Et la variante avec état est aussi sécurisée par l'ACP. Et ces caractéristiques séduisantes font que le mode de fonctionnement du compteur doit être utilisé avec rigueur dans le protocole du monde réel. Je vous remercie.

Notification
You have received a new notification
Click here to view them all