Comment vérifier le numéro avec Bob sans le savoir?

49

Vous devez vérifier que votre ami, Bob, a votre numéro de téléphone correct, mais vous ne pouvez pas lui demander directement. Vous devez écrire la question sur une carte et la donner à Eve qui la remettra à Bob et vous retournera la réponse. Que devez-vous écrire sur la carte, en dehors de la question, pour vous assurer que Bob peut coder le message afin qu'Eve ne puisse pas lire votre numéro de téléphone?

Remarque: cette question figure sur une liste de "questions d'entretien Google". En conséquence, il existe des tonnes de versions de cette question sur le Web, et beaucoup d’entre elles n’ont pas de réponses claires, ni même correctes.

Note 2: La réponse sournoise à cette question est que Bob devrait écrire "appelle-moi". Oui, c'est très intelligent, "hors des sentiers battus" et tout, mais n'utilise aucune technique de ce domaine de la CS où nous appelons notre héros "Bob" et son adversaire "Eve".

Mise à jour:
points bonus pour un algorithme que vous et Bob pourriez raisonnablement compléter à la main.

Mise à jour 2:
notez que Bob n'a pas à vous envoyer de message arbitraire, mais seulement à confirmer qu'il a votre numéro de téléphone correct sans que Eve ne puisse le décoder, ce qui peut éventuellement conduire à des solutions plus simples.

Joe
la source
1
Mais "appelez-moi" n'a pas de sens du tout, il n'a pas encore votre numéro de téléphone correct ou du moins vous n'êtes pas sûr de l'avoir, alors je ne pense pas que ce soit très intelligent.
Gigili
1
@Gigili si vous recevez un appel de lui, alors il a votre numéro, si vous ne recevez pas un appel, alors il ne le fait pas.
Joe
1
Oh, c'est vrai. Je pense toujours que ce n'est pas intelligent!
Gigili
Une autre réponse ironique peut être le chiffre de César . Même si Eve essaie tous les décalages possibles, elle n’a aucune raison de choisir une séquence de chiffres plutôt qu’une autre (à moins d’essayer de les appeler tous).
Raphaël
2
@Raphael N'y a-t-il pas seulement 10 chiffres possibles sur les chiffres de César?
Joe

Réponses:

27

Nous devons d’abord supposer que Eve n’est que passive. Je veux dire par là qu’elle envoie honnêtement la carte à Bob et que ce qu’elle rapporte à Alice est bien la réponse de Bob. Si Eve peut modifier les données dans un sens ou dans les deux (et que son action reste non détectée), tout est permis.

(Pour honorer les traditions de longue date, les deux parties honnêtes impliquées dans la conversation s'appellent Alice et Bob. Dans votre texte, vous dites "vous". Mon vrai nom n'est pas "Alice", mais je vous répondrai comme si vous écriviez que Alice veut vérifier le numéro de téléphone de Bob.)

La réponse simple (mais faible) consiste à utiliser une fonction de hachage. Alice écrit sur la carte: "retournez-moi le hachage SHA-256 de votre numéro de téléphone". SHA-256 est une fonction de hachage cryptographique censée être sécurisée, pour autant que les fonctions de hachage disparaissent. Le calculer à la main serait fastidieux mais toujours faisable (environ 2500 opérations 32 bits, où chaque opération est une addition, un décalage ou une rotation de mots, ou une combinaison de bits au niveau des bits; Bob devrait pouvoir le faire en une journée ou alors).

Maintenant, quel est faible à ce sujet? SHA-256, étant une fonction de hachage cryptographique, résiste aux "pré-images": cela signifie que, avec une sortie de hachage, il est très difficile de récupérer une entrée correspondante (c'est le problème auquel Eve est confrontée). Cependant, "très difficile" signifie "la méthode la plus simple est la force brute: essayer les entrées possibles jusqu'à ce qu'une correspondance soit trouvée". Le problème, c'est que la force brute est facile ici: il n'y a pas beaucoup de numéros de téléphone possibles (en Amérique du Nord, c'est 10 chiffres, soit à peine 10 milliards). Bob veut faire les choses à la main, mais nous ne pouvons pas supposer qu'Eve est si limitée. Un PC de base peut essayer quelques millions de hachages SHA-256 par seconde . Eve se fera en moins d’une heure (moins de 5 minutes si elle utilise un processeur graphique).

C'est un problème générique: si Bob est déterministe (c'est-à-dire que pour un message donné d'Alice, il retournera toujours la même réponse), Eve peut le simuler. Notamment, Eve sait tout sur Bob sauf le numéro de téléphone. Elle gère donc pratiquement 10 milliards de Bobs, qui ne diffèrent que par leur numéro de téléphone supposé; et elle attend que l'un des Bobs virtuels retourne ce que le vrai Bob a réellement rendu. La faille affecte de nombreux types de solutions "intelligentes" impliquant des nonces aléatoires et un chiffrement symétrique, entre autres choses. Il s’agit d’un défaut grave, dont la racine réside dans l’énorme différence de puissance de calcul entre Eve et Bob (maintenant, si Bob avait aussi un ordinateur aussi grand que celui d’Eve, il pourrait alors utiliser un ordinateur lent.fonction de hachage grâce à l'utilisation de nombreuses itérations; C’est plus ou moins le but du mot de passe, avec le numéro de téléphone au lieu du mot de passe; voir bcrypt et aussi cette réponse ).

Par conséquent, une solution non faible doit impliquer un certain hasard de la part de Bob: Bob doit lancer une pièce de monnaie ou lancer des dés à plusieurs reprises, et injecter les valeurs dans ses calculs. De plus, Eve ne doit pas être en mesure de comprendre ce que Bob a fait, mais Alice doit pouvoir le faire, de sorte que certaines informations sont transmises confidentiellement de Bob à Alice. C'est ce qu'on appelle le cryptage asymétrique ou, au moins, l'accord de clé asymétrique. L'algorithme le plus simple de cette classe à calculer, mais toujours raisonnablement sécurisé, est alors RSA avec le remplissage PKCS # 1 v1.5 . RSA peut utiliser comme exposant public. Le protocole va donc comme suit:e=3

  • n=pqpqnp1q1

  • n

  • nn

  • mm3 mod n

  • pqmm3 mod nm

Le calcul d'Alice nécessitera un ordinateur (ce que fait un ordinateur est toujours élémentaire et réalisable à la main, mais l'ordinateur est diablement rapide, donc le "faisable" risque de prendre trop de temps à faire en pratique; le déchiffrement RSA à la main prendrait beaucoup semaines).

(En fait, nous pourrions avoir un calcul manuel plus rapide en utilisant le cryptage McEliece , mais alors la clé publique - ce que Alice écrit sur la carte - serait énorme et une carte ne ferait tout simplement pas l'affaire; Eve devrait alors transporter un livre complet de chiffres.)

Thomas Pornin
la source
1
Juste un commentaire rapide, une autre faiblesse du premier protocole (Alice dit "envoyez-moi un hachage du numéro de téléphone") est qu'il est vulnérable à une attaque par rejeu. Si vous implémentiez cela dans le monde réel, Alice devrait envoyer une chaîne aléatoire (appelée "nonce") qui est hachée avec le numéro de téléphone.
Pseudonyme
1
Vous avez dit que "tout va bien" si Eve peut modifier le message, mais ce n'est pas nécessairement une cause perdue. En utilisant RSA, nous pouvons également protéger le message contre les attaques MITM. Envoyez une question: "Avez-vous mon numéro de téléphone?", Plus votre clé publique, plus une signature de (message + votre numéro de téléphone) signé avec votre clé privée. Si Eve tente de modifier le message (remplace la clé publique par elle-même), elle ne pourra pas générer de signature valide car elle ne connaît pas votre numéro de téléphone.
Stévendesu
15

Ressemble à une application classique de Cryptosystem à clé publique telle que RSA .

Vous envoyez votre clé publique, BoB chiffre votre numéro de téléphone à partir de sa liste de contacts et vous le renvoie.

Aryabhata
la source
5
Compte tenu de Bob et Eve, c'est probablement censé être l'idée clé. Est-ce pratique dans ce contexte (crayon et papier)? J'espérais aussi un peu plus qu'un lien vers un article de Wikipédia avec le drapeau "cet article doit être modifié".
Joe
@ Joe: J'ai édité d'inclure un autre lien. Je suis à peu près sûr que vous avez entendu parler de RSA. RSA est probablement assez pratique, car écrire 1000 chiffres ne devrait pas prendre beaucoup de temps.
Aryabhata
14

Une des choses les plus fondamentales que vous puissiez faire est un échange de clé Diffie-Hellman . Il n'est pas nécessaire que les clés soient configurées avant le début de la communication, car il en négocie une de sorte que les auditeurs ne puissent pas obtenir la clé eux-mêmes. Voir l'article complet de Wikipedia pour plus de détails.

pgpggamodpa

  • gbmodpb
  • gabmodp

gamodpgbmodpgabmodp

Tant qu’il est correctement implémenté et que les communicateurs et l’attaquant disposent à peu près de la même puissance de calcul, la sécurité est assurée.

Raphaël
la source
2

Bob n'a pas à envoyer de messages que vous pouvez déchiffrer. Il n'a qu'à vous prouver qu'il a votre numéro de téléphone. Par conséquent, les fonctions de hachage cryptographique (chiffrement unidirectionnel) offrent une alternative au cryptosystème à clé publique. SHA-2 est actuellement un exemple populaire d'une telle fonction.

Dans cette stratégie, vous n'avez jamais à déchiffrer le message de Bob. Vous indiquez à Bob quelle fonction de hachage vous souhaitez utiliser, par exemple: "Bob, utilise SHA-2 pour chiffrer mon numéro de téléphone et demande à Eve de me renvoyer le résultat". Ensuite, vous utilisez le même algorithme pour hacher votre numéro de téléphone et vérifiez si vous obtenez le même hachage que Bob. Il est extrêmement improbable que deux numéros de téléphone différents donnent le même hachage. Vous pouvez donc déterminer si Bob a le numéro de téléphone correct.

Si vous, Bob et Eve n’avez pas d’ordinateur disponible pour calculer la fonction de hachage (ou effectuer une attaque par force brute), il est peut-être possible d’utiliser la fonction de hachage qui sacrifie une partie de la sécurité contre les attaques par force brute mais qui est beaucoup plus facile pour vous et Bob. calculer.

Joe
la source
J'écrivais la même réponse! Malchanceux. Je le posterai quand même car j'ai passé du temps dessus.
Gigili
@Gigili J'espérais que quelqu'un écrirait cette réponse, mais j'ai décidé de le faire quand j'ai vu que personne n'offrait cette alternative pour le moment ... Je suis toujours à la recherche d'une version conviviale pour le crayon et le papier. Honnêtement, je ne voudrais pas demander à mon ami de faire du RSA ou du SHA-2 à la main.
Joe
Le problème est que chaque algorithme simple qui peut être fait à la main serait chiffré par Eve.
Gigili
@Gigili voulez-vous dire "déchiffré par Eve"? Le problème est très limité. Il semble qu'il devrait y avoir un hachage unidirectionnel plus simple à partir de nombres entiers à 7 chiffres que Eve ne peut pas annuler pour récupérer le nombre original.
Joe
Oups, je voulais dire décrypté évidemment.
Gigili
0

Une solution simple serait:

Alice et Bob sont d'accord sur la même couleur. et ce n'est pas un problème si Eve le sait, nous l'appellerons P. Disons que c'est jaune. Maintenant, Alice et Bob choisissent tous les deux au hasard une couleur privée, dites "x". Alice choisit le rouge et Bob choisit le bleu. Maintenant, ils les mélangent avec le P. Alice a maintenant orange, et Bob a vert. Alice envoie la couleur orange à Bob, qui envoie sa couleur verte à Alice. Eve connaît maintenant le jaune, l'orange et le vert, mais Alice connaît également sa couleur privée, le rouge, et Bob connaît sa couleur privée, le bleu, que personne d'autre ne sait. Alice et Bob prennent leurs couleurs privées d'origine et les ajoutent à celles qu'elles viennent d'échanger. Maintenant, s'ils mélangent leurs couleurs privées d'origine, le rouge et le bleu, à la couleur commune, ils finissent tous les deux avec la même couleur, une sorte de brun ou de rouge brique.

gx(modp)gx(modp)Ax(modp)By(modp)


Je pense que vous pouvez écrire quelque chose comme ceci sur la carte:

Le nombre est multiple de 3,5 et 7 (par exemple).

(10)nn

Gigili
la source
Ceci est une narration de l'image trouvée dans l'article de Wikipédia sur l' échange de clés Diffie-Hellmann . Vous devriez au moins mentionner votre source.
Raphaël
@Raphael: Je ne le savais pas moi-même, quelqu'un me l'a expliqué et j'ai pensé que c'était une bonne idée.
Gigili
0

Il suffit de demander à Bob de multiplier le nombre par 2 ou 3 ou quoi que ce soit d'autre et xor ce nombre avec le nombre lui-même. C'est faisable à la main et réversible si le nombre est connu. Pas de sha, rsa ou md5. Juste des maths.

Hérétique
la source
3
Cette réponse est fausse. Simple, faisable à la main et totalement peu sûr. Cela ne fonctionne tout simplement pas. Eve peut récupérer beaucoup d’informations sur le numéro de téléphone.
DW
0

Envoyez à Bob un mot de code chiffré avec votre numéro de téléphone; s'il vous renvoie le mot de code, vous savez qu'il a le bon numéro.

Le problème est qu’Eve peut simuler Bob. Essayez donc tous les numéros de téléphone jusqu’à ce qu’elle obtienne celui qui donne le mot de code au retour de Bob.

Demandez donc à Bob d’ajouter un très grand nombre au mot codé, puis de le chiffrer avant de vous le renvoyer. Cela rend l’espace de recherche Eves aussi grand que vous le souhaitez.

Ian Ringrose
la source
Cela ne semble pas juste. Si Bob a le mauvais numéro, il va d'abord déchiffrer et obtenir un mauvais mot de code. Après cela, il ajoute un nombre aléatoire au mot de code et le chiffre avec la mauvaise clé. Lorsque le message est reçu et déchiffré avec la clé correcte, le premier segment du message récupéré peut éventuellement être le mot de code correct, même si le numéro que Bob a est incorrect.
InformedA
@randomA Vous avez juste besoin de créer un mot de code suffisamment long pour que la probabilité que cela se produise soit si faible que vous ne vous en souciez pas.
Ian Ringrose
Ce que vous avez dit est vrai, mais la solution choisie est également très intéressante sur ce point. Je ne suis que contre la solution choisie de la part de "certaines informations sont donc transmises confidentiellement de Bob à Alice". Si vous utilisez un message de remplissage suffisamment volumineux et ne contenant aucun symbole représentant le numéro de téléphone, Bob peut y insérer le numéro de téléphone de manière aléatoire et Alice peut facilement récupérer le numéro de téléphone du message décrypté sans connaître les étapes aléatoires suivies par Bob ( aucune information confidentielle n'est nécessaire dans ce cas).
InformedA
-1

J'écrirai environ 10 numéros de téléphone sur la carte et parmi ceux-ci, je ferai en sorte que mon numéro soit placé à côté du numéro de Bob et que je mentionne "Hey Bob, mon numéro est à côté de ton numéro, merci de vérifier" :)

Everlasto
la source
1
En supposant que je connaisse le numéro de Bob et que la veille ne le sait pas: P
everlasto
-1

Je pense que la question est beaucoup plus simple que tout le monde le pense. Nous sommes obligés de vérifier que le nombre que Bob a est correct (ou éventuellement, incorrect). Puisque nous "vérifions" si le numéro est correct, on peut supposer que Bob a déjà votre numéro. Par conséquent, il n'est pas nécessaire d'envoyer votre numéro à Bob dans un code. Ma réponse serait: "Cher Bob, appelle-moi mon numéro. Merci, Alice"

Joshua Campbell
la source
1
La question exclut déjà explicitement cette réponse triviale.
David Richerby
-2

essayez de faire un trik comme ça

solution1: si le nombre est 37, la carte de hachage ressemblera à ceci

01 07

15 12

25 20

31 36

49 43

53 50

60 62

72 72

85 82

91 94

et faire la même chose pour 10 chiffres ou même plus pour confondre: P

solution2: ou construire un polynôme dans lequel votre nombre devient un autre nombre unique

solution3: écrivez ceci dans la lettre "mec m'appelle"

solution4: écrit une fonction de telle sorte qu'elle effectue des opérations sur chaque chiffre et renvoie 0, puis envoie une réponse vraie ou fausse solution5: si les deux extrémités partagent une fonction de hachage commune ... cela rend la vie très facile

Ajay Reddy
la source
Ce n'est pas évident de voir comment votre code code 37.
David Richerby
tout ce que nous devons faire est de cartographier ... 31 en gras signifie que 3 est en position 1 .... 72 en moyen 7 est en position 2 ... désolé si ce n'était pas très intuitif à comprendre
Ajay Reddy
Cela devrait être expliqué en détail dans la réponse. Mais sérieusement, si c'est votre système de codage, il n'est pas vraiment sécurisé, n'est-ce pas?
David Richerby
-2

Je pense que nous pouvons le faire en utilisant des opérations de base assez sages ou peut-être le personnaliser pour le travail au crayon et au papier. Si le nombre d'alice est par exemple 663, elle peut simplement convertir le nombre en utilisant cette méthodologie. Convertir chaque chiffre en représentation binaire équivalente dire ceci comme A 663-> 110 110 011 que inverser les bits correspondants pour chaque nombre individuel dire ceci comme B-> 011 011 110 Maintenant faites A et B-> 010 010 010 Maintenant envoyez ce nombre à bob et demander de faire la même chose si le résultat obtenu est identique, lui demander de dire oui ou non. Dans ce cas, il ne sera pas possible de décoder le nombre et il est très peu probable que des nombres différents aboutissent à la même représentation. La seule façon dont nous puissions le deviner est d’écrire toutes les combinaisons possibles et de les essayer toutes, sauf pour préciser que nous pouvons compliquer les choses davantage en utilisant un décalage à gauche ou à droite et en ajoutant des bits factices.

Sanjay Singh
la source
Ça ne marche pas. Tout d'abord, le bit central de chaque groupe de 3 bits est laissé intact. Deuxièmement, les premier et troisième bits de chaque groupe du message transmis seront toujours les mêmes, et généralement zéro, ce qui entraînera de nombreux faux positifs. Troisièmement, trois bits ne peuvent représenter que huit valeurs, mais un chiffre décimal peut prendre l'une des dix valeurs. Quatrièmement, votre dernière phrase est essentiellement: "Oh, et si cela ne fonctionne pas, essayez quelque chose de plus complexe." Tel que?
David Richerby
-3

S'il vous plaît appelez-moi (mon nom est 1001001). Si vous ne pouvez pas me joindre, écrivez le numéro de téléphone que vous avez et demandez à Eve de me rendre.

Explication: si Bob a mon numéro correct, il peut me joindre alors je sais que c’est un # correct; Si Bob n'a pas obtenu mon numéro de droite, Eve ne peut pas lire aussi mon (bon) numéro de téléphone. De cette façon, j'ai déjà vérifié que mon ami, Bob, avait mon numéro de téléphone correct ou non.

Pobol Wong
la source
to everlasto: Eve peut contacter Bob afin qu’elle ait probablement son #. Par conséquent, si vous demandez "Hey Bob, Mon numéro est à côté de ton numéro, vérifie s'il te plaît", Eve te connaîtra #.
Pobol Wong
1
La question dit explicitement que vous ne pouvez pas simplement envoyer à Bob une carte disant "Appelle-moi". Et si Bob écrit le mauvais numéro sur la carte s'il ne peut pas passer, cela n'ajoute rien.
David Richerby
J'ai écrit un programme d'encodage / décodage LZW auparavant. Je peux demander à Bob de l'utiliser pour m'envoyer le numéro codé de mon téléphone et également pouvoir l'utiliser pour coder la partie correcte de mon numéro de téléphone.
Pobol Wong
à David Richerby: la question ne mentionne que "vous ne pouvez pas lui demander directement", ce qui veut dire que moi, 1001001, je ne peux pas demander directement à Bob, mais devrait pouvoir lui demander de m'appeler avec le numéro de téléphone qu'il a reçu.
Pobol Wong
Lisez la question plus attentivement. "Note 2" dans la question rejette la solution consistant à envoyer une note demandant à Bob de vous appeler car elle n’utilise aucune science.
David Richerby