Journal CAPTCHA

Posté par  . Licence CC By‑SA.
Étiquettes : aucune
6
3
juil.
2011

Je lisais cet article totalement bidon sur les CAPTCHAS : http://www.xmco.fr/article-captcha.html

Quand j'ai eu une idée grâce à la question dans la conclusion (je présume que je ne suis pas le seul, mais je n'ai pas encore vu d'implémentation). La question c'est « Mais peut-on réellement imaginer un algorithme que seul un humain puisse résoudre ? » et la réponse est oui. Tout les problèmes informatique de la classe NPComplet sont très difficilement solvables par un ordinateur.

Pour rappel les Problème_NP-complet sont des problèmes dont on peut vérifier si une solution au problème est valide ou non en un temps polynomiale et, on va dire, qui ressemble à un problème NP-Complet déjà existant (en fait on démontre qu'on peut les formuler sous la forme d'un problème déjà NPComplet).

Grosso modo leur résolution par un ordinateur consiste à générer des solutions et à les vérifier (en "brute force"). C'est rapide (même si peu efficace) sur des petites entrées et plus le nombres de paramètres augmente, plus c'est long (en suivant une courbe exponentiellle, si je ne me trompe pas).

Un certains nombres de problèmes NPComplet sont assez ludiques (la coloration d'un graphe, le voyageur de commerce, le problème du sac à dos, …), mais je crains qu'il faille avoir des entrées un peu trop grandes (graphes trop grands, trop grand nombres d'items à mettre dans le sac, etc) pour que ça pose vraiment un problème pour une machine et pas un humain.

Qu'en pensez-vous ? Pensez-vous que ce serais réalisable ?

PS : J'ai testé ceci http://research.microsoft.com/en-us/um/redmond/projects/asirra/ qui nous vient de chez Microsoft. Ça me semble pas mal surtout si on choisit un ensemble d'image assez embêtant (qu'il ne puisse pas trop se baser sur les couleurs, les formes ou les motifs).

  • # non

    Posté par  . Évalué à 3.

    Pour rappel les Problème_NP-complet sont des problèmes dont on peut vérifier si une solution au problème est valide ou non en un temps polynomiale

    Non. Un problème NP-Complet appartient à la classe NP, donc on peut affirmer qu'on peut les résoudre en temps polynomiale de manière non-déterministe. Pour certain, on sait qu'on peut les résoudre en temps polynomiale de manière déterministe (ceux qui appartiennent à P) mais pas tous. Et plus précisément dans le cas des problèmes NP-Complet on ne sait pas faire.

    Grosso modo leur résolution par un ordinateur consiste à générer des solutions et à les vérifier (en "brute force").

    Leur résolution optimale, mais il existe des algos bien plus efficaces qui approchent l'optimale en un temps polynomiale sur machine déterministe (enfin pour la plupart des problèmes qui sont intéressants à résoudre)

    Qu'en pensez-vous ? Pensez-vous que ce serais réalisable ?

    Du coup, non.

    • [^] # Re: non

      Posté par  (site web personnel) . Évalué à 3.

      Pour rappel les Problème_NP-complet sont des problèmes dont on peut vérifier si une solution au problème est valide ou non en un temps polynomial
      Non.

      Pour préciser, il a en fait donné la définition d'un problème NP, pas NP-complet. Pour que le problème soit NP-complet, il faut qu'il soit également NP-dur, c'est-à-dire que tu puisses ramener n'importe quel autre problème NP à celui-ci en temps polynomial.

      Un problème NP-Complet appartient à la classe NP, donc on peut affirmer qu'on peut les résoudre en temps polynomial de manière non-déterministe.

      Il ne dit pas le contraire : si tu peux vérifier en temps polynomial de manière déterministe, alors tu peux résoudre en temps polynomial de manière non-déterministe. Il suffit de tirer au hasard la bonne solution et de la vérifier. Mais ça, c'est pour NP.

      Pour certain, on sait qu'on peut les résoudre en temps polynomial de manière déterministe (ceux qui appartiennent à P)

      En effet, certains problèmes de NP appartiennent aussi à P.

      mais pas tous. Et plus précisément dans le cas des problèmes NP-Complet on ne sait pas faire.

      Mais le point vraiment essentiel, c'est que si un ordinateur ne sait pas le faire, on ne sait pas le faire non plus (du moins, certainement pas plus vite que lui).

      • [^] # Re: non

        Posté par  . Évalué à 3.

        Vous avez raison, je me suis pris les pieds dans le tapis (ça m'apprendras à essayer de réfléchir à des trucs théoriques après minuit).

        Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)

  • # Robot après tout

    Posté par  . Évalué à 10.

    J'ai rien compris à ce journal (quelle idée aussi d'aller consulter linuxfr après un bbq) mais je crois que ça a à voir : http://www.labandepasdessinee.com/bpd/370-robot-apres-tout

    lbpd

    • [^] # Re: Robot après tout

      Posté par  (site web personnel) . Évalué à 10.

      Cela me fait penser à un autre type de CAPTCHA :

      Bien

      Mieux

      Ici CAPTCHA veut dire "Completely Automated Public Turing test to tell Colorblinds and Humans Apart"

      L'association LinuxFr ne saurait être tenue responsable des propos légalement repréhensibles ou faisant allusion à l'évêque de Rome, au chef de l'Église catholique romaine ou au chef temporel de l'État du Vatican et se trouvant dans ce commentaire

    • [^] # Re: Robot après tout

      Posté par  . Évalué à 7.

      C'est n'importe quoi robocop il a un cerveau humain (on voit même un bout de visage).
      ---> s/robocop/terminator/

  • # Mauvaise approche

    Posté par  (site web personnel) . Évalué à 10.

    Le hic, c'est qu'il est aussi extrêmement difficile pour un humain de trouver la solution optimale d'un problème NP-complet non-trivial (bonne chance pour résoudre un voyageur du commerce à 100 noeuds). Le problème fondamental, c'est qu'on utilise en général la notion de complexité algorithmique pour des problèmes sur lesquels les ordinateurs sont justement plus forts que les humains, parce que ce sont en général des algorithmes qui demandent "juste" des calculs. Et les ordinateurs sont très forts au calcul.

    Par contre, le lien que tu donnes chez Microsoft demande de reconnaître des photos de chat. La difficulté du problème ne réside pas dans la complexité algorithmique, mais dans le fait qu'on ne connaît juste pas d'algorithme (même NP) qui permette d'approcher la capacité humaine à interpréter une image.

    Je pense que si tu veux un CAPTCHA qui ne soit pas crackable automatiquement, il faut plutôt s'orienter sur des domaines où les ordinateurs sont mauvais (reconnaissance d'images, interprétation de texte, etc..).

    • [^] # Re: Mauvaise approche

      Posté par  (site web personnel) . Évalué à 10.

      interprétation de texte

      On pourrait par exemple proposer un système qui lit de la poésie Vogon. Si après quatre vers, l'utilisateur sait encore répondre correctement à une question basique (genre 2*3), c'est un ordinateur.

  • # Ah ?

    Posté par  (site web personnel) . Évalué à 10.

    Pourquoi il est totalement bidon l’article sur les captcha ?

    • [^] # Re: Ah ?

      Posté par  . Évalué à 6.

      Cependant, des chercheurs développent dès à présent des algorithmes afin de casser ces systèmes [de CATPCHA à la Asirra], basés sur la reconnaissance de forme et de textures.

      Pour connaître un chercheur qui travail sur ce genre de domaine, il y a 1 million d'autres application avant les captchas (notamment autour des moteurs de recherche, de l'indexation automatique d'image, …). Sa formulation laisse à penser que ce sont des pirates qui veulent rien qu'embêter les webmasters.

      Mais surtout :

      Les attaques des CAPTCHA se développent de plus en plus et leur efficacité ne cesse de progresser notamment grâce au partage et à la mise à disposition de code sources.

      « Bouh les vilains qui partagent le code source ! »

      Faire retomber les problèmes de captcha sur le dos du partage de code source moi ça ne me plaît pas.

      Oui ça n'est pas tout l'article, il m'a même appris un ou deux trucs (Asirra et l'utilisation de malware pour faire faire le travail par d'autres), mais le fait de s'attaquer au partage de code et donc au partage de connaissance fait que cet article contribue d'une certaine manière à faire à diffuser l'idée que le libres est un truc de pirate.

      Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)

      • [^] # Re: Ah ?

        Posté par  (site web personnel) . Évalué à 5.

        Je te trouve un peu dur :

        Cependant, des chercheurs développent dès à présent des algorithmes afin de casser ces systèmes [de CATPCHA à la Asirra], basés sur la reconnaissance de forme et de textures.

        On peut aussi interpréter : des chercheurs bossent sur des algorithmes et ces algorithmes permettent (entre autre) de casser des captcha. Il ne parle pas du reste car le sujet de son article c'est les captcha.

        Les attaques des CAPTCHA se développent de plus en plus et leur efficacité ne cesse de progresser notamment grâce au partage et à la mise à disposition de code sources.

        Là encore, je ne vois rien de péjoratif dans la remarque, il me semble quand même que l'un des argument avancé par les gens qui prônent les licences libres c'est justement l'amélioration du développement des logiciels grâce au partage des connaissances et à la synergie des contributeurs. Si ça marche pour le kernel, pourquoi ça ne marcherait pas pour les algos de résolution de captcha ?

        Qualifier tout l'article de "totalement bidon" pour ça... :/

        • [^] # Re: Ah ?

          Posté par  . Évalué à 3.

          Là encore, je ne vois rien de péjoratif dans la remarque, il me semble quand même que l'un des argument avancé par les gens qui prônent les licences libres c'est justement l'amélioration du développement des logiciels grâce au partage des connaissances et à la synergie des contributeurs. Si ça marche pour le kernel, pourquoi ça ne marcherait pas pour les algos de résolution de captcha ?

          Il y a une mise en exergue que je n'apprécie que moyennement, on pourrait aussi dire que l'augmentation de la puissance de calcul disponible est la cause de l'inefficacité croissante des captchas, par exemple.

          Après bien sûr que le partages de connaissances améliore la qualité des logiciels quelque soit le domaine dans nos usages classiques, dans le domaine du piratage, ainsi que dans les solutions type DRM (quand il y a partage de connaissance/code).

          Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)

  • # Commentaire supprimé

    Posté par  . Évalué à 10.

    Ce commentaire a été supprimé par l’équipe de modération.

    • [^] # Re: Marre des captcha

      Posté par  (site web personnel) . Évalué à 4.

      Je confirme. J’ai conditionné le script d’enregistrement sur les livres d’or de mes sites à l’absence de mots-clefs tels que viagra, cialis et insurance. Les attaques n’ont pas diminué si j’en crois les stats, mais depuis longtemps plus rien ne passe si ce n’est que de temps en temps je dois allonger la liste de la pharmacopée interdite. Et en plus, ce n’est pas compliqué puisque moi j’y arrive.
      Quand une seule clef ferme toutes les serrures, une seule clef suffit à les ouvrir toutes.

    • [^] # Re: Marre des captcha

      Posté par  . Évalué à 4.

      C'est parfois le défaut des développeurs qui pensent avant tout technique alors qu'il devraient d'abord réfléchir à l'ergonomie et à la simplicité d'utilisation.

      D'où mon journal, pour ça comme pour tout c'est en partageant une idée qu'on peut réellement réfléchir dessus.

      Je suis probablement geek, mais je trouve plus ludique de résoudre un problème de voyageur de commerce que d'arriver à lire un texte plus ou moins obfuscé.

      l'utilisation de champs cachés (par une règle CSS)

      Je doute que ça soit réellement efficace.

      une vérification du temps de saisie

      Par un code javascript ?

      une vérification sur une base de mots-clés

      Je ne connais pas.

      sur une liste noire d'IP de spammeurs (à utiliser avec précaution) ou sur une liste noire d'URL

      C'est toujours particulier de mettre en place des listes noires.

      Je suis d'accord avec toi que des solutions spécifiques sont plus efficaces. Par exemple une question en français choisie parmi une base spécifique au site, rend les attaque nettement plus complexes. Il faut que l'attaquant effectue un dump de la base de questions, puis qu'il répondent à chacune. Ca réduis drastiquement les possibilités d'utilisation de malware car il faut des francophones.

      Pour réduire les risques de dump, la question peut se trouver dans une image avec un texte qui change légèrement pour une question donnée.

      Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)

      • [^] # Re: Marre des captcha

        Posté par  . Évalué à 10.

        La technique du champ de texte avec un nom de type «ne pas remplir», qui est en plus caché css est très efficace.

        Les bots ont tendance à remplir tout les champs du formulaire, pour maximiser les chances de voir leur pub affichée. Ils ne gèrent pas le css, et donc si le champ caché par le css est rempli, il y a de fortes chances que ce soit un bot.

        La vérification du temps de saisie peut se faire cotés serveur, puisque les bots ne gèrent pas le javascript. Il suffit de stocker à quelle moment a été chargé la page du formulaire, et à quel autre moment le formulaire a été soumis. Si le délai entre les deux opérations est très court, ça correspond à un robot. Le problème est de désavantager une utilisation normale du formulaire par un robot, ou d'un mec sur les nerfs.

        Envoyé depuis mon lapin.

        • [^] # Commentaire supprimé

          Posté par  . Évalué à 1.

          Ce commentaire a été supprimé par l’équipe de modération.

          • [^] # Re: Marre des captcha

            Posté par  (site web personnel) . Évalué à 1.

            Pour le problème du champ caché, il suffit de mettre un petit texte (label) à côté du champ qui indique qu'il ne faut pas remplir cette case, et inclure le texte dans la partie cachée de la CSS ; quelqu'un qui a un navigateur texte verra qu'il ne doit pas remplir le champ, le bot remplira toujours le champ, et le problème d'accessibilité est réglé.

            Par ailleurs, c'est la technique utilisée par Django, le framework de développement web en Python, pour éviter le SPAM, dans les formulaires prêts à l'usage proposés par le framework.

          • [^] # Re: Marre des captcha

            Posté par  . Évalué à 1.

            Pour le temps de saisie, ça empêche aussi la saisie automatique, qui est tout de même une killer feature quand on a un ordi personnel. Un tit macro pour remplir les trucs bidons Nom Prénom Mail et une tite vérification, c'est tout de même vachement plus rapide qu'une madame michu.
            J'ai peur que les boots ne chargent pas le JS, et qu'obliger d'avoir JS activé pour un formulaire soit aussi restrictif que les captcha audios (j'suis astigmate) sur modules flash...

            "The trouble with quotes on the internet is that it’s difficult to discern whether or not they are genuine.” Abraham Lincoln

      • [^] # Re: Marre des captcha

        Posté par  . Évalué à 2.

        Pour réduire les risques de dump, la question peut se trouver dans une image avec un texte qui change légèrement pour une question donnée.

        Le problème des CAPTCHAs images est qu'ils sont non-accessibles aux mal-voyants.

        • [^] # Re: Marre des captcha

          Posté par  . Évalué à 1.

          Je n'ai pas parlé de déformation ni de changement de contraste ou autre, juste de quoi obligé les bots à faire de l'OCR pour drainer un peu leur ressources. Et avec un peu de chance, ils vont recopier la question dans le champ de texte à coté.

          Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)

          • [^] # Re: Marre des captcha

            Posté par  . Évalué à 5.

            Un humain non-voyant ne possède pas de module d'OCR car il lui manque le périphérique optique requis. Rien que l'utilisation d'une image rend la chose non-accessible. Ce n'est pas pour rien que les règles d'accessibilité demandent de donner un texte alternatif pour chaque image (attribut "alt").

            • [^] # Re: Marre des captcha

              Posté par  . Évalué à 6.

              Ah, oui, donc il faut ajouter en alt du captcha le texte à taper, pour que ce soit accessible aux non-voyants :-D

    • [^] # Re: Marre des captcha

      Posté par  . Évalué à 6.

      une liste noire d'IP de spammeurs (à utiliser avec précaution) ou sur une liste noire d'URL s'avèrent souvent suffisamment efficaces pour réduire les spam à une quantité proche de zéro.

      On pourrait aussi explorer la piste d'une liste blanche. Définir un cahier des charges imposant un minimum de respect de la nétiquette et de son esprit:

      - réponse dans un délai raisonnable aux plaintes sur abuse@,

      - sanction effective contre les utilisateurs responsables d'abus, que ce soit parce qu'ils spamment ou parce que leur machine a été vérolée,

      - définition objective de la notion d'abus, qui soit internationale (donc qui s'appuie sur le caractère hors-sujet du commentaire ou sur le fait qu'une adresse mail ait été collectée sans le consentement préalable et explicite de la personne prospectée),

      - éventuellement, afin de faciliter le repérage des abus, nécessiter de distribuer une @IP fixe à chaque utilisateur final, afin de pouvoir le bloquer très rapidement en cas de spam détecter, et de l'inscrire sur une liste noire tant que le FAI n'a pas répondu "c'est bon, j'ai contacté mon client, il cesse de spammer, et au troisième abus de ce genre je le vire de mon réseau".

      Puis créer une liste blanche de FAI répondant à ces critères. Les utilisateurs sur liste blanche se verraient accepter leur commentaire/création de compte sans captcha. Ceux sur liste noire se feraient refouler, ceux sur liste grise en resteraient au captcha. L'idée étant, en rendant très confortable le fait d'être sur liste blanche, de pousser les utilisateurs à réclamer des FAI sur liste blanche, donc d'inciter au comportement vertueux, plutôt que d'emmerder tout le monde à cause des abus de quelques un (captcha) ou de ne faire que taper sur les emmerdeurs (liste noire).

      Pour ça il faudrait une autorité de référence mondiale, dont la neutralité vis à vis des lois locales et des contenus ne puisse être remise en cause. Une sorte d'ICANN de la nétiquette (sauf que l'ICANN n'est pas super neutre non plus). Autorité qui aurait un fonctionnement démocratique, avec une adresse IPv4 (ou bloc end-user IPv6) = une voix. Vu que la plupart des gens sont contre le spam, ça pourrait fonctionner, non?

      THIS IS JUST A PLACEHOLDER. YOU SHOULD NEVER SEE THIS STRING.

      • [^] # Re: Marre des captcha

        Posté par  . Évalué à 3.

        Ces propositions sont intéressantes mais on demande aux FAI de faire des choses qu'ils ne sont pas censés faire (si j'envoie des mails depuis chez moi, même beaucoup, je ne suis pas forcément un spammeur).
        Ça m'énerverait grandement que mon FAI vienne me voir et me dise : « Hier vous avez envoyés de nombreux mails, si vous n'êtes pas à l'origine de ces mails pensez à acheter le pack de protection Ultra+ à 8.99€/mois ou bien le pack SuretéMaxPro à 19.99€/mois pour les entreprises, {FAI} toujours à votre service ».

        Les FAI pourrait aussi contacter les clients qui font du peer-to-peer : rappel que c'est illégal (même si ça l'est pas), achat du logiciel de contrôle parental de l'entreprise, etc..

        Sinon je pense que mettre un captcha aux FAI gris tandis que les blancs n'en n'ont pas ne va pas marcher (ou alors que pour les FAI peu répandus donc on revient à la case départ) certaines personnes ont un FAI nul et n'ont pas de virus car ils font attention, certaines personnes ont un bon FAI (réactif, service de qualité etc.) alors qu'ils attrapent pleins de cochonneries par Internet.

        207829⁶+118453⁶=193896⁶+38790⁶+14308⁶+99043⁶+175539⁶

        • [^] # Re: Marre des captcha

          Posté par  . Évalué à 9.

          T'as pas tout compris.

          La question n'est pas que ton FAI compte tes mails, mais qu'il prenne en compte le fait qu'on lui signale du spam envoyé par tes machines. Et qu'il le prenne en compte:

          • en te contactant,
          • en te demandant d'arrêter,
          • en prenant des mesures si tu n'arrêtes pas,
          • en faisant un résumé de la situation à celui qui se plaint: ça ne veut pas dire "balancer tes coordonnées personnelles" mais "indiquer que t'avait une machine infectée, qu'elle est désinfectée, qu'il peut te whitelister".

          Du coup un bon FAI n'est pas celui qui fait en sorte de n'avoir aucun spammeur chez lui, mais celui qui permet une lutte contre le spam efficace, en:

          • attribuant des IP fixes (blacklistage facile),
          • agissant contre ses éventuels abonnés spammeurs.

          Du coup, tu peux te permettre de whitelister les bon FAI. Si tu reçois un peu de spam venant d'eux, ce n'est pas grave, car ce spam te fera contacter le FAI, forcément. Le FAI contactera forcément son client. Et son client fera forcément quelque chose (désinfecter sa machine, veiller à ne pas la ré-infecter, ou cesser de spammer) sinon il sera bon pour changer de FAI, à force.

          L'idée ce serait d'éradiquer le spam, en élargissant le cercle des FAI propres et en blacklistant/greylistant (captcha) les clients des autres. Bref, de faire en sorte que le spammeur final (qu'il soit volontaire ou pas) soit réellement emmerdé par le spam qu'il envoie, donc trouve plus intéressant de cesser de spammer que de continuer.

          Actuellement, pour quelqu'un qui envoie du spam depuis la plupart des FAI, la question se résume à:

          • faire l'effort d'arrêter de spammer, pour n'y rien gagner,
          • ne pas faire l'effort d'arrêter, et n'y rien gagner non plus.

          C'est donc parfaitement logique que des millions de gens se traînent avec un PC zombie: on ne fait absolument rien qui les incite à faire le ménage.

          THIS IS JUST A PLACEHOLDER. YOU SHOULD NEVER SEE THIS STRING.

    • [^] # Re: Marre des captcha

      Posté par  (site web personnel) . Évalué à 3.

      J'avais vu (sur linuxfr ?) une idée de captcha sympa : proposer différentes photos de minettes, et il fallait sélectionner LA sexy dans le groupe.
      Pas parfait, mais marrant.

      ウィズコロナ

      • [^] # Re: Marre des captcha

        Posté par  (site web personnel) . Évalué à 3.

        y'a quand même plus simple, et moins sujet à polémique (pourquoi ce sexisme gratuit?). En plus les tests graphiques ne sont pas adaptés aux malvoyants, comme pour les captchas.

        sinon, poser des questions simples (genre "combien font deux plus trois" ou "quelle est la capitale de la France"), c'est déjà fait par quelques sites. Cela dit les spammeurs risquent de s'adapter si ce genre de pratique se généralise.

        • [^] # Re: Marre des captcha

          Posté par  . Évalué à 1.

          "combien font deux plus trois"

          Un simple :
          s/deux/2/ ; s/trois/3/ ; s/plus/+/
          Et on a la réponse direct.

          Pour des question géographie, une requête du genre: http://www.google.fr/search?q=capitale+de+la+france
          La réponse est dans le premier mot. Pas terrible non plus.

          Pour l'histoire du sexisme, il suffit juste de proposer aussi des photos de mecs.

          • [^] # Re: Marre des captcha

            Posté par  (site web personnel) . Évalué à 2.

            Si il y a bien une chose ou les humains sont infiniment supérieur au ordinateur, c'est bien la reconnaissance d'image, dommage pour les non-voyants.

            Mais des questions suivant une image : y'a-t-il un stylo dans l'image ? ou cette personne est-elle jolie ? etc... sont impossible à répondre pour un ordinateur sauf si la base de donnée de référence est trop petite (cela se résout par essais erreurs).

            "La première sécurité est la liberté"

            • [^] # Re: Marre des captcha

              Posté par  (site web personnel) . Évalué à 2.

              En fait, il suffit d'avoir une base d'image d'objet et de recomposer une image plus grande avec les objets et poser la question de la présence ou de l'absence d'objets.

              Cela revient au capcha avec des lettres mais ici, il serait question d'objet. Rien n’empêche de coller les images de façon complexe pour qu'un logiciel d'analyse ne puisse pas les trouver (lissage des couleurs, transparence, etc...).

              "La première sécurité est la liberté"

              • [^] # Re: Marre des captcha

                Posté par  . Évalué à 2.

                Ou plus efficacement, en générant une image à partir d'un modèle 3D.
                Inconvénient: la puissance de calcul.
                Avantage: peut-être pas tant que ça.

            • [^] # Re: Marre des captcha

              Posté par  . Évalué à 1.

              Je ne crois pas que ce soit impossible pour un ordinateur de savoir si une personne est jolie ou non.
              Par exemple, sur le lien suivant, il est question d'un programme pour "embellir" un visage: http://www.johnofthetower.com/photographe-artiste/voirautrement/beaute-algorithme/
              Pour savoir si une personne est jolie ou non, il suffirai d'appliquer ce programme sur une de ses photos. Le critère de beauté serait la différence entre l'image original, et celle "embellie".
              Plus l'image originale est proche de la nouvelle, plus la personne est belle.

              • [^] # Re: Marre des captcha

                Posté par  (site web personnel) . Évalué à 2.

                l'outil ne semble pas automatique, on dirait une trousse à outil pour photoshop.

                De plus définir une "différence" d'image, n'est pas trivial du tout.

                "La première sécurité est la liberté"

                • [^] # Re: Marre des captcha

                  Posté par  . Évalué à 3.

                  On arrive bien à reconnaitre les visage; si après retouche le logiciel ne reconnais plus c'est qu'elle est moche ;)

                  ps: je précise humour !!!

                  Il ne faut pas décorner les boeufs avant d'avoir semé le vent

            • [^] # Re: Marre des captcha

              Posté par  (site web personnel) . Évalué à 2.

              Une question « oui/non » ?
              Super dur ! T'as une chance sur deux d'avoir bon !

  • # totalement bidon ?

    Posté par  (site web personnel) . Évalué à 5.

    Je n'ai pas compris pourquoi tu disais que l'article dont tu donnes le lien sur la première ligne était "totalement bidon".

    blog.rom1v.com

  • # pwntcha

    Posté par  (Mastodon) . Évalué à 7.

    Rappelons cette belle étude de notre trublion national : http://caca.zoy.org/wiki/PWNtcha

  • # CAPTCHA qui marche bien

    Posté par  . Évalué à 9.

    Dans le temps j'avais un forum, et pour l'inscription, à force d'avoir à virer 30 bots par jours, j'avais imaginé l'astuce suivante :

    Tu fais un joli captcha, et à coté tu mets : "Veuillez écrire "toto" dans la zone de texte suivante".

    L'humain n'a aucune difficulté à comprendre, mais tous les bots essayent de résoudre le captcha et de l'écrire dans la zone de texte.
    Apparemment aucun humain mal intentionné n'est venu vérifié de lui même pourquoi ses robots n'avaient jamais réussi à s'inscrire sur le forum...

    • [^] # Re: CAPTCHA qui marche bien

      Posté par  (site web personnel) . Évalué à 3.

      J'ai fait un peu de même, j'ai une liste de questions à la con pour mon forum, genre:

      Q: Que mettre dans le Pastis?
      R: eau, glaçons, rien

      Q: Quelle était la couleur du cheval blanc de Marcel XII?
      R: Blanc.

      Sachant que celui qui sèche sur une peu actualiser et en prendre une autre.

      Je trouve que c'est une bonne solution qui est aussi adaptable à des sites "sérieux", avec des questions du type "Que met-on dans une salière?".

      Bon, si ça se généralise, les méthodes plus orientées social engineering en viendront à bout, mais il restera la barrière de la langue.

      Prochainement, je vous proposerai peut-être un commentaire constructif.

    • [^] # Re: CAPTCHA qui marche bien

      Posté par  . Évalué à 3.

      Ces méthodes sont sympathiques, mais sauf à avoir un pool gigantesque de questions/réponses, une personne malveillante aura vite fait le tour de toutes les possibilités et pourra programmer très facilement son bot.
      La force des captchas images est qu'elles peuvent générer un nombre très grand de "questions".

      • [^] # Re: CAPTCHA qui marche bien

        Posté par  (site web personnel, Mastodon) . Évalué à 3.

        On peut aussi mettre en liste noire les IP d'où proviennent trois mauvaises réponses successives dans un délai à définir.

        • [^] # Re: CAPTCHA qui marche bien

          Posté par  . Évalué à 1.

          1/ le filtrage IP, on sait ce que cela peut donner : personnes légitimes derrières un proxy, personne avec IP dynamique, botnet avec des milliers d'IP légitimes.
          2/ mon propos était de dire que si le nombre de question est trop faible, un humain peut très bien les résoudre puis programmer son bot. Il n'y aura pas alors de mauvaises réponses.

        • [^] # Re: CAPTCHA qui marche bien

          Posté par  . Évalué à 3.

          Attends de voir IPv6. "Tu m'a bloqué ? Il me reste quelques milliers d'IP"

          Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)

          • [^] # Re: CAPTCHA qui marche bien

            Posté par  . Évalué à 3.

            Bah, t'as qu'à bloquer directement le /64, et hop 18 milliards de milliards d'adresses bloquées d'un coup :-)

  • # Idées de captchas

    Posté par  . Évalué à 2.

    1 - proposer un déssin partiel d'une maison et demander à l'utilisateur de le completer
    2 - proposer une liste d'image et demander à l'utilisateur de selection celle qui représente 'Mickey'
    3 - proposer une phrase et questionner l'utilisateur sur la sémantique de la phrase (ex: qui est le sujet)
    3.1 - proposer une phrase incompléte demander à l'utilisateur de compléter la phrase avec une liste de mot
    3.2 - http://www.w3.org/2004/Talks/0319-csun-m3m/slide15-0.html

  • # Même entrée, même sortie

    Posté par  . Évalué à 3.

    PS : J'ait testé ceci http://research.microsoft.com/en-us/um/redmond/projects/asirra/ qui nous viens de chez Microsoft. Ça me semble pas mal surtout si on choisi un ensemble d'image assez embêtant (qu'il ne puisse pas trop se baser sur les couleurs, les formes ou les motifs).

    Je ne suis pas sûr que dans les faits ça fonctionne.

    1. Partons du principe que microsoft mette au point une sorte de captcha dont le test ne peut-être passé que par un humain. Cela veut dire que leur base de captcha ne peut pas être automatisée. On a donc des personnes qui vont devoir générer ces captchas. En retour, on va utiliser d'autres personnes (comme dans l'article que tu cites) qui vont être chargée d'y répondre.

    2. Les captchas sont générés automatiquement. Ça veut dire qu'il existera forcément une solution pour les passer automatiquement. La seule chose qui va jouer c'est le temps à résoudre chaque problème (trouver le mot, l'image correspondant au chat...). Si ce temps devient trop long ou le calcul trop lourd, alors on en revient à la solution #1 : on embauche un cluster de petits chinois payés 1$ les 1000 captchas ou alors on intègre les captchas à décoder dans des sites légaux qu'un utilisateur va décoder à son insu.

    • [^] # Re: Même entrée, même sortie

      Posté par  (site web personnel) . Évalué à 4.

      A l'image des fonctions de hash, je pense qu'il doit exister des problèmes insolubles par les machines qu'elles peuvent créer elle-même (un genre de fonction injective).

      "La première sécurité est la liberté"

  • # Un algorithme ayant de l'argent ?

    Posté par  . Évalué à 6.

    Soluble ou résoluble, mais pas solvable.

    • [^] # Re: Un algorithme ayant de l'argent ?

      Posté par  . Évalué à 3.

      Si si on parle d'algorithmes qui génèrent des bitcoins !

      Tu as raison, mais je ne peux pas éditer le journal.

      Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)

  • # Ouais

    Posté par  . Évalué à -5.

    C'est pas faux …

    • [^] # Re: Ouais

      Posté par  . Évalué à -2.

      Tu serais pas chevalier à kamelott ? :)

  • # The captcha and the bots

    Posté par  . Évalué à 2.

    Dites pourquoi se prendre la tête, comme dit plus haut il suffit de faire un simple texte en disant ce qu'il faut écrire, souvent j'en vois du genre 4+5 =

    Tout le reste ne sert qu'à emmerder l'utilisateur. On connait tous le captcha tellement mal écrit que déja vous même ne pouvez le décrypter, le formulaire tellement bien fait qu'une fois le code rentré il ne se valide pas car ça n'a pas été prévu pour votre navigateur et j'en passe.

    • [^] # Re: The captcha and the bots

      Posté par  . Évalué à 3.

      Dites pourquoi se prendre la tête, comme dit plus haut il suffit de faire un simple texte en disant ce qu'il faut écrire, souvent j'en vois du genre 4+5 =

      Parce que si un robot est conçu pour le site en particulier, un texte proposant une simple addition ne posera aucune difficulté au bot. Proposer une simple addition (voire demander à l'utilisateur de copier-coller un mot) ne fonctionne que contre les robots qui ne sont pas spécifiques à un site (et pas très futés).

      • [^] # Re: The captcha and the bots

        Posté par  . Évalué à 3.

        Pire encore: vu qu'il est idiot de ré-inventer la roue, la mode est quand même à l'utilisation de CMS pour créer un site Web. Le CMS embarque alors son moteur de captcha générique, et il suffira d'un seul bot pour toucher de nombreux sites.

        THIS IS JUST A PLACEHOLDER. YOU SHOULD NEVER SEE THIS STRING.

      • [^] # Re: The captcha and the bots

        Posté par  . Évalué à 3.

        et dans le cas de sites très interessants (grosses promotions sur des produits hi-tech, par exemple, avec un peu de fraude bancaire ensuite), ne t'en fais pas que si les bots ne suffisent pas, ils emploieront de la main d'oeuvre humaine à pas cher, genre des indiens

  • # mauvaise idée

    Posté par  . Évalué à 5.

    Le cerveau humain n'a rien de magique et ne trouve pas les solutions des problèmes complexes déjà formalisés en demandant la réponse aux dieux tout en sacrifiant un poulet. Si une méthode de raisonnement existe pour arriver à la solution en un temps raisonnable pour un être humain, ce raisonnement est formalisable en un algorithme et exécutable par une machine, en un temps beaucoup plus court d'ailleurs. NP ou pas NP ne change absolument rien à l'affaire.

    • [^] # Re: mauvaise idée

      Posté par  (site web personnel) . Évalué à -2.

      Bien sûr, et c'est bien connu que la faculté, par exemple, de dialoguer dans un langage aux règles extrêmement lâches (genre, n'importe quelle langue vivante (oui oui merci je connais l'esperanto et non l'astrologie ne m'intéresse pas)) est parfaitement imitée par un ordinateur.

      J'ai pas d'avis sur les captchas (ou du moins pas assez intéressant pour l'exposer publiquement), mais dire qu'il y a bijection entre les problèmes facilement solubles par un cerveau humain et par un ordi... ouvre la porte de ta cave, regarde dehors, pour voir ?

      • [^] # Re: mauvaise idée

        Posté par  . Évalué à 2.

        "déjà formalisé"

      • [^] # Re: mauvaise idée

        Posté par  . Évalué à 2.

        Et tant que j'y suis, désolé Sufflope tu va prendres pour tous les autres, l'esperanto n'est pas une lange non ambiguë, donc je vois pas ce qu'elle vient foutre là. Tu voulais ptet dire Lojban. Comme en plus ce ne sont pas des langues que j'utilise dans ma cave, je ne vois encore moins bien ce que ça vient faire ici.

      • [^] # Re: mauvaise idée

        Posté par  . Évalué à 3.

        Oh l'exemple du langage n'est pas mal choisi :)

        On pourrait imaginer un antispam qui (sur le modèle de Omegle) mette en rapport deux utilisateurs du site devant prouver leur humanité. Ils discutent alors jusqu'à ce que chacun ait convaincu l'autre qu'il est humain.

        S'il y a un ratio nombre d'humains/nombre de bots assez élevé, ça peut marcher. Et bien que ce soit un captcha lent, il est ludique.

        Un test de Turing, tout simplement \o/

        THIS IS JUST A PLACEHOLDER. YOU SHOULD NEVER SEE THIS STRING.

        • [^] # Re: mauvaise idée

          Posté par  . Évalué à 3.

          Les utilisateurs vont vouloir faire ça le plus rapidement possible et vont valider l'autre utilisateur le plus vite possible pour s'en débarrasser.

          Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)

          • [^] # Re: mauvaise idée

            Posté par  . Évalué à 4.

            Il faut mettre des bots qu'il est impossible de prendre pour un humain et de dévalider les utilisateurs les validant

            • [^] # Re: mauvaise idée

              Posté par  . Évalué à 2.

              A partir d'un certains moment, le plus simple c'est que ceux qui veulent créer un compte doivent contacter le webmaster par mail ou en messagerie instantanée en expliquant leurs motivations.

              Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)

    • [^] # Re: mauvaise idée

      Posté par  . Évalué à -3.

      d'habitude je suis pas du genre à me formaliser à être moinssé, surtout quand je trolle sur des sujets polémiques (ce qui n'est pas le cas ici, puisqu'on peut difficilement prétendre qu'un sujet mathématique, formel, de complexité algorithmique, soit polémique... c'est plutôt dans ce cas qu'il y a des gens qui y comprenne quelque chose, et d'autres moins -- ce qui n'empêche pas ces derniers de penser qu'ils y comprennent beaucoup de choses)

      mais là j'aimerai bien que messieurs les moinseurs aillent apprendre suffisamment au sujet de la complexité algorithmique avant de se déchaîner, pcq connaitre juste le mot NP parce que vous avez lu wikipedia et croire que c'est magique, c'est de la connerie, de l'idiotie, tout ce que vous voulez

      donc PUTAIN, du fond de ma cave : (oui oui je suis énervé, j'écris des gros mots et tout) je reformule mon message qui a du mal passé, et être compris comme "un cerveau c'est comme un microprocesseur" par des gens qui devraient apprendre à lire , ce que ceux qui SAVENT lire peuvent constater trivialement qu'il ne voulait pas dire ça du tout -- bref reformulation de mon message pour les abrutis : c'est pas parce qu'un problème est NP-complet qu'un être humain peut le résoudre dans le cas général tandis qu'un ordinateur ne peut pas. Croire le contraire, c'est faire preuve d'une confusion mentale que je ne peux même pas commencer à comprendre -- c'est avoir juste assez de connaissance en complexité algorithmique (pour être très clair vu le niveau auquel je m'adresse : très peu) pour être dangereux.

      sur ce, déchaînez vous

      • [^] # Re: mauvaise idée

        Posté par  . Évalué à 2.

        T'exciter tout seul ne sers à rien. Si j'ai posé la question de savoir est ce que les problèmes NP-Complet ne pourrait pas être utilisés, c'est d'une part pour ouvrir une discution à ce sujet d'autre part parce que je n'étais pas sur de moi.

        Je te conseil quand tu en viens à insulter à tout va sans vraiment savoir qui sur un coup de chaud à quitter ton ordinateur ou faire n'importe quel autre activité qui te décontracteras, ça te feras du bien à toi ainsi qu'à ceux qui te lisent. C'est vraiment dommage de s'énerver pour des broutilles.

        Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)

      • [^] # Re: mauvaise idée

        Posté par  . Évalué à 1.

        1) T'enerver et insulter les gens ne sert à rien. Tout ce que ca fait, c'est que tu vas être encore plus moinsé et que tu y perds en crédibilité.

        2) Non, tu n'as pas dit "un cerveau c'est comme un microprocesseur" mais "si un problème peut être résolu par un cerveau, il peut l'être par un ordinateur", et c'est totalement faux ! A la question "Je suis petit, teigneux, je drague à eurodisney et beaucoup de francais espèrent que je serai au chomage en 2012", un être humain francais saura répondre avant meme d'avoir finit de lire la phrase, un ordinateur non. Donc ce que tu disais est totalement faux. Pas besoin de mal comprendre ce que tu as dis pour considérer que tu as dit une connerie. Après, les gens croient que "c'est faux" signifie "c'est inutile", mais ca c'est un autre débat.

        • [^] # Re: mauvaise idée

          Posté par  . Évalué à 4.

          désolé, mais je crois être un être humain, français, et j'ai du attendre de lire beaucoup de francais espèrent que je serai au chomage en 2012 pour savoir de qui tu parlais.

          Parce que des petit teigneux y'en a un bon paquet, et la drague à eurodisney ne me dit rien.
          Par contre
          http://www.google.fr/search?q=drague+%C3%A0+eurodisney
          donne en premier résultat la réponse à la question. Globalement ça se fait assez facilement via un analyse de la structure de la phrase.

          Il ne faut pas décorner les boeufs avant d'avoir semé le vent

    • [^] # Re: mauvaise idée

      Posté par  . Évalué à 2.

      Tu vois à la relecture de ton commentaire, il n'exprimait pas ce que tu voulais dire (il existe un raisonnement qui nous permet de déterminer si une image représente un manchot ou pas, mais il n'existe pas d'algorithme qui permet de résoudre ce problème).

      Pour ce qui est des problèmes formalisés certains jeux comme le jeu de Go par exemple sont encore du domaine de la recherche si je me souviens bien (là on quitte évidement le domaine des captchas).

      Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)

      • [^] # Re: mauvaise idée

        Posté par  (site web personnel) . Évalué à 2.

        Manchot, Pingouin.... gaffe, y'a déjà des confusions connues sur ces bestioles.

        Votez les 30 juin et 7 juillet, en connaissance de cause. http://www.pointal.net/VotesDeputesRN

    • [^] # Re: mauvaise idée

      Posté par  . Évalué à 2.

      Sauf qu'il y a des problèmes qui ne sont pas solubles par un ordinateur, notamment les problèmes de l'arrêt ou les preuves de comportement d'un programme (qui découlent de l'arrêt). Et encore aujourd'hui, on n'a pas d'algorithmes pour écrire des programmes ;)

      Ça ferait des bons tests CAPTCHA pour des sites webs de programmeurs.

      • [^] # Re: mauvaise idée

        Posté par  . Évalué à 5.

        Ca nous fait une belle jambe d'avoir un problème qui n'est résoluble ni par un ordinateur ni par un humain... Autant désactiver les commentaires ou le sign up ;)

  • # Résolution de captcha

    Posté par  . Évalué à 5.

    1. Mettre en place un faux site très aguichant, les femmes a poil c'est pas mal pour ca
    2. Lorsqu'un type se connecte, aller choper le captcha a résoudre
    3. Le soumettre a votre type
    4. Enjoy
    • [^] # Re: Résolution de captcha

      Posté par  . Évalué à 2.

      C'est ce qu'indique le liens donné dans le journal.
      Si le captchas est en français par exemple tu limite de beaucoup l'efficacité de ton algorithme.

      Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)

    • [^] # Re: Résolution de captcha

      Posté par  . Évalué à 2.

      ça s'appelle "human computation"
      une très intéressante conférence a été faîte par Luis von Ahn sur le sujet
      à voir franchement.
      enjoy aussi.

  • # Impressionnant

    Posté par  (site web personnel) . Évalué à 9.

    Un certains nombres de problèmes NPComplet sont assez ludiques (la coloration d'un graphe, le voyageur de commerce, le problème du sac à dos, …), mais je crains qu'il faille avoir des entrées un peu trop grandes (graphes trop grands, trop grand nombres d'items à mettre dans le sac, etc) pour que ça pose vraiment un problème pour une machine et pas un humain.

    Tu bats un ordinateur pour résoudre le voyageur du commerce ou calculer une coloriage optimal de graphe ?

    • [^] # Re: Impressionnant

      Posté par  (site web personnel) . Évalué à 6.

      Ben, là tu peux te baser sur le temps de réponse, si ça a pris quelques heures, c'est un humain.

      Votez les 30 juin et 7 juillet, en connaissance de cause. http://www.pointal.net/VotesDeputesRN

    • [^] # Re: Impressionnant

      Posté par  (site web personnel) . Évalué à 2.

      Ca dépend de la taille, comme pour les ordinateurs. Et ça dépend si tu cherches une solution réalisable, une bonne solution ou à prouver qu'une solution est optimale.

      • [^] # Re: Impressionnant

        Posté par  . Évalué à 3.

        À mon avis, que ce soit pour une solution admissible, bonne ou optimale, c'est toujours la machine qui gagne.

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.