Cette simple communication cryptée XOR est-elle absolument sécurisée?

23

Imaginons qu'Alice et Peter ont chacun une clé USB à mémoire flash de 4 Go. Ils se rencontrent et enregistrent sur les deux sticks deux fichiers nommés alice_to_peter.key(2 Go) et peter_to_alice.key(2 Go) qui contiennent des bits générés aléatoirement. Ils ne se rencontrent plus jamais, mais communiquent électroniquement. Alice maintient également une variable appelée alice_pointeret Peter maintient une variable appelée peter_pointer, toutes deux initialement définies sur zéro.

Quand Alice doit envoyer un message à Peter, elle le fait (où nest le nième octet du message):

encrypted_message_to_peter[n] = message_to_peter[n] XOR alice_to_peter.key[alice_pointer + n]
encrypted_payload_to_peter = alice_pointer + encrypted_message_to_peter
alice_pointer += length(encrypted_message_to_peter)

(et pour une sécurité maximale, la partie utilisée de la clé peut être effacée)

Peter reçoit encrypted_payload_to_peter, lit les données alice_pointerstockées au début du message et fait:

message_to_peter[n] = encrypted_message_to_peter[n] XOR alice_to_peter.key[alice_pointer + n]

Et pour une sécurité maximale, après lecture du message effacez également la partie utilisée de la clé. - EDIT: En fait, cette étape avec cet algorithme simple (sans vérification d'intégrité et authentification) diminue la sécurité, voir le post de Paŭlo Ebermann ci-dessous.

Lorsque Peter a besoin d'envoyer un message à Alice, ils font l'inverse, cette fois avec peter_to_alice.keyet peter_pointer.

Avec ce schéma trivial, ils peuvent envoyer chaque jour pendant les 50 prochaines années 2 Go / (50 * 365) = ~ 115 Ko de données chiffrées dans les deux directions. S'ils ont besoin de plus de données à envoyer, ils pourraient utiliser des clés plus grandes, par exemple avec les HD 2 To actuels (clés 1 To), il serait possible d'échanger 60 Mo / jour pendant les 50 prochaines années! C'est beaucoup de données dans la pratique; par exemple, en utilisant la compression, c'est plus d'une heure de communication vocale de haute qualité.

Il me semble qu'il n'y a aucun moyen pour un attaquant de lire les messages cryptés sans les clés, car même s'ils ont un ordinateur infiniment rapide, avec la force brute, ils peuvent obtenir tous les messages possibles sous la limite, mais c'est un nombre astronomique des messages et l'attaquant ne sait pas lequel d'entre eux est le message réel.

Ai-je raison? Ce schéma de communication est-il vraiment absolument sécurisé? Et s'il est sécurisé, a-t-il son propre nom? Le cryptage XOR est bien connu, mais je recherche le nom de cette application pratique concrète utilisant de grandes clés des deux côtés? J'attends humblement que cette application ait été inventée quelqu'un avant moi. :-)

Remarque: s'il est absolument sécurisé, c'est incroyable, car avec les grands périphériques de stockage à faible coût d'aujourd'hui, il serait beaucoup moins cher de faire une communication sécurisée qu'avec la cryptographie quantique coûteuse, et cela a une sécurité équivalente!

EDIT: Je pense que ce sera plus pratique à l'avenir que les coûts de stockage diminuent.Il peut résoudre la communication sécurisée pour toujours.Aujourd'hui, vous n'avez aucune certitude si quelqu'un attaque avec succès les chiffres existants, même un an plus tard, et rend ses implémentations souvent coûteuses peu sûres. Dans de nombreux cas, avant la communication, lorsque les deux parties se rencontrent personnellement, c'est le moment de générer les clés. Je pense que c'est parfait pour la communication militaire, par exemple entre les sous-marins qui peuvent avoir des HD avec de grandes touches, et la centrale militaire peut avoir un HD pour chaque sous-marin. Cela peut également être pratique dans la vie quotidienne, par exemple pour contrôler votre compte bancaire, car lorsque vous créez votre compte, vous rencontrez la banque, etc.

user3123061
la source
4
Autre que le schéma spécifique pour coordonner la partie de la clé à utiliser, ce n'est qu'un tampon à usage unique . Mais en y regardant de plus près, il s'avère ne pas être réellement utile pour 99% des cas d'utilisation.
10
Comme cette question concerne la force d'un algorithme de cryptographie particulier, il pourrait être plus adapté à crypto.stackexchange.com . Pour y déplacer votre question, vous pouvez signaler l'attention du modérateur et demander la migration.
Bart van Ingen Schenau
12
Les OTP ont été inventés il y a plus d'un siècle et ont été utilisés comme de véritables blocs de papier physiques dans les deux guerres mondiales. ( en.wikipedia.org/wiki/One-time_pad ) Le problème de la cryptographie alors comme maintenant est l'échange de clés.
Gort the Robot
6
Notez que cela vous laisse toujours résoudre le problème de génération de suffisamment de clés uniques pour toutes les données attendues jusqu'à ce que les deux parties se rencontrent à nouveau, et que les clés doivent être générées via un processus aléatoire GENUINELY - les générateurs de nombres pseudo-aléatoires sont vulnérables à l'analyse, de plus en plus que plus d'échantillons utilisant le même PRNG deviennent disponibles.
keshlam
1
@keshlam. La génération de vrais nombres quantiques aléatoires devient très bon marché. Article intéressant sur arxiv: Génération de nombres aléatoires quantiques sur un téléphone portable: arxiv.org/abs/1405.0435
user3123061

Réponses:

50

Oui, il s'agit d'un bloc à usage unique . Si le matériau clé n'est jamais réutilisé, il est théoriquement sûr.

Les inconvénients sont que vous auriez besoin d'une clé par paire de principaux communicants et que vous auriez besoin d'un moyen sécurisé d'échanger le matériel clé avant de communiquer.

Vatine
la source
52
Je pense qu'il vaut la peine de souligner que «théoriquement sûr» signifie qu'il est mathématiquement prouvé qu'il est incassable , à condition que les clés soient vraiment aléatoires et non réutilisées. C'est à peu près la garantie la plus solide que vous puissiez obtenir n'importe où en cryptographie.
Michael Borgwardt
1
@MichaelBorgwardt énorme point là-bas. Dans ce cas, «théoriquement sûr» est en fait mieux que «pratiquement sécurisé».
Mark
2
cas d'espèce: j'ai une clé aléatoire de 2 Go qui se trouve avoir 16 octets séquentiels de 0.
Michael
@Michael Les chances que cela se produise sont d'environ 1 sur 10 ^ 27.
ce
1
@Floris Mon "calcul": un octet a 256 valeurs possibles. C'est un sur 256 que tout sera nul. 256 ^ 16 pour obtenir 16 octets. Et puis divisez le nombre d'octets en 2 Go par cette chance. Je pense que j'ai raté une division par 16, de toute façon ici (1024 * 1024 * 1024 * 1024 * 2 * (1/16)) / (256 ^ 16) Votre dernier point rend ce calcul non pertinent de toute façon.
ce
32

Comme l' indique la réponse de Vatine , votre algorithme est essentiellement un bloc ponctuel.

Cependant, pour commenter une de vos notes:

Remarque: si c'est absolument sûr, c'est incroyable, car avec les grandes mémoires d'aujourd'hui à faible coût, c'est une méthode de communication sécurisée beaucoup plus économique que la cryptographie quantique coûteuse et avec une sécurité équivalente!

Ma réponse est non, ce n'est pas étonnant. Le diable est toujours dans les détails, et le diable est ici dans l'échange de clés. Votre méthode repose sur un échange de clés en face à face parfait. Je ne peux pas me permettre d'envoyer James Bond avec un disque flash de 4 Go à chaque commerçant sur Internet chaque fois que je veux acheter quelque chose ou avoir d'autres connexions sécurisées.

Et enfin, l'aspect XOR de votre algorithme n'est pas important. Un chiffrement de substitution simple est très bien avec un OTP. La force de l'OTP est que la clé n'est jamais réutilisée, et elle suppose que James Bond échange parfaitement les clés pour les deux parties (c'est-à-dire un échange de clé sécurisé préalable)

comment s'appelle-t-il
la source
13
L'autre chose à propos d'un OTP est que la clé est (au moins) aussi longue que le message à crypter, et a besoin d'une source de nombres aléatoires de très haute qualité.
Donal Fellows
De nombreux algorithmes de chiffrement fonctionnent en convertissant d'une manière ou d'une autre une clé en un flux de données qui ne peut pas être distingué des données aléatoires, puis en utilisant ces données comme une seule fois. Du point de vue d'un attaquant, il n'y a pas de différence entre des données qui sont vraiment aléatoires et des données qui ne peuvent pas être distinguées de données aléatoires (par définition; si vous avez trouvé une différence, ce n'était pas impossible à distinguer), donc en théorie, c'est tout aussi sûr qu'OTP . Bien sûr, lorsque nous disons que les données ne peuvent pas être distinguées des vraies données aléatoires, il y a généralement un tas de mises en garde. Cette explication est bien sûr une simplification exagérée.
Brian
21

Bien que le tampon à usage unique ait une garantie de confidentialité inconditionnelle (prouvée mathématiquement) contre un attaquant qui ne peut lire que les messages, il présente certaines faiblesses.

  • Un attaquant interceptant qui devine correctement le texte brut peut manipuler le texte chiffré comme bon lui semble (avec la même longueur).

  • Si un attaquant insère ou supprime un message (ou une partie de celui-ci), les pointeurs d'Alice et de Bob se désynchronisent et toute communication future est interrompue.

    Mise à jour: cela supposait que les deux parties gardent une trace des deux pointeurs. Si vous envoyez la valeur actuelle du pointeur, vous êtes vulnérable aux attaques à deux tampons temporels (si vous autorisez la même plage de clés à être utilisées plusieurs fois) ou aux attaques DOS (si vous n'autorisez pas la même plage de clés à utiliser plusieurs fois, par exemple en les supprimant).

Ces deux problèmes sont dus au manque d'intégrité et de protection d'authentification - vous avez un chiffrement parfait, mais pas de MAC.

Ajoutez un MAC à votre protocole ponctuel pour le rendre réellement sécurisé. Chaque message doit obtenir une «somme de contrôle» qui garantit qu'il a bien été envoyé par l'expéditeur supposé et n'a pas été modifié entre les deux. En outre, vous devez envoyer un numéro de séquence pour que le destinataire sache quelle partie de la clé utiliser lors de la perte d'un message précédent (ou pour rejeter le message s'il est dupliqué) - incluez-le dans le calcul de la somme de contrôle.

Un algorithme MAC habituel ferait l'affaire ici, mais je suppose que vous voudrez peut-être utiliser un MAC polynomial à usage unique pour avoir la sécurité correspondante à votre bloc à usage unique. (Prenez la clé MAC des bits avant ou après votre clé de chiffrement, c'est-à-dire ne réutilisez pas une clé pour les deux objectifs.)

Paŭlo Ebermann
la source
Si un attaquant insère ou supprime un message (ou une partie de celui-ci), les pointeurs d'Alice et de Bob se désynchronisent et toute communication future est interrompue. Les pointeurs sont indépendants et n'ont pas besoin d'être synchronisés, donc aucune communication future n'est interrompue si le message est perdu (le décalage réel de la clé utilisée pour chiffrer le message est envoyé avec ce message). Mais vous avez en partie raison: la synchronisation est utilisée comme partie de la clé côté réception qui n'est pas effacée car le message supprimé n'est pas reçu (la partie utilisée sera effacée avec le prochain message reçu).
user3123061
Mais tu as raison. Présentation de l'intégrité et de l'authentification de l'algorithme simple. La mise en œuvre pratique devra être plus robuste.
user3123061
@ user3123061 Je n'éliminerais pas simplement l'intégrité et l'authentification si j'étais vous. La technique d' attaque adaptative de texte chiffré choisie exploite une absence de protection de l'intégrité pour briser la confidentialité . J'irais jusqu'à dire que le pad classique à usage unique (c'est ce que vous avez réinventé) est carrément peu sûr , malgré sa solidité mathématique apparente, juste à cause de cette attaque.
zwol
2
L'attaque adaptative choisie par cipertext est un choix d'attaque assez mauvais contre un OTP vérifié par l'homme. OOS va être remarqué et votre attaquant sera botté assez rapidement. Ce n'est que si le récepteur est traité par machine et donne une réponse que cette attaque est bonne du tout.
Joshua
@Zack Il existe de nombreux problèmes avec les OTP, mais aucun ne menace la confidentialité. Notez que même si vous devinez parfaitement la clé plantext + du message précédent, le message suivant est crypté avec une clé indépendante entièrement nouvelle (de taille considérable également). Il n'y a rien à s'adapter à de multiples interactions.
4

En fait, ce n'est pas entièrement sûr. Ce que fuit votre protocole, c'est la LONGUEUR du message communiqué.

Par exemple, si l'espion sait que vous répondrez par «oui» ou «non» et voit la longueur = 2, il peut déduire que c'est «non».

En fait, il est étonnant de voir combien on ne peut déduire que des longueurs connues si l'on peut deviner le contexte.

w.pasman
la source
3
C'est assez facile à corriger cependant, à un niveau de sécurité raisonnable, car vous pouvez remplir le message avec des indésirables, de sorte que la longueur du message est multiple d'une taille de bloc fixe - disons 256 caractères. Cela irait à l'encontre d'une simple analyse oui / non, au prix d'une utilisation plus rapide de l'OTP.
Peter Bagnall
En effet - puisque vous pouvez envoyer ~ 115 Ko par jour pendant les 50 prochaines années, vous pouvez vous attendre à ce que chaque bloc soit d'au moins 20 Ko, ce qui signifie que la longueur n'est pas aussi importante.
apnorton