Jump to content

BOINC Project


floofloo44
 Share

Recommended Posts

  • Replies 116
  • Created
  • Last Reply

Top Posters In This Topic

La clé n'est pas "jetable" avec OpenVPN et ne sert pas que pour une session...

Sinon pour le dev, je crois avoir compris: il a le choix de créer une clé et d'en recréer une nouvelle si elle ne lui plait pas, c'est ça ?

Exactement. Si le dev se rend compte que la clef générée est en fait une clef qui tient sur 32 ou 64 bits, il peut en générer une autre jusqu'à ce qu'il en trouve une suffisamment longue. De coup, pour notre projet BOINC, je pencherais plus pour tester d'abord les clefs qui tiennent sur au moins 512 bits et ce, afin de maximiser nos chances de tomber sur la clef au début de la recherche plutôt qu'à la fin...

Edited by nimbus3d
Link to comment
Share on other sites

Ouais enfin vu le niveau des devs chez Motorola, j'ai du mal a croire qu'ils seraient si "rigoureux"... Ou alors ils ont un programme qui vérifie ces conditions automatiquement. Après tu peux toujours essayer d'en parler sur le forum du projet, on ne sait jamais ^^

Link to comment
Share on other sites

J'ai une remarque concernant la stratégie de calcul adoptée.

J'ai l'impression que les modules de calcul commencent par le "début" de l'espace des clefs, c'est à dire les clefs avec une faible mantisse.

j'ai par exemple des modules intitulés Milestone_1295724114_59614_0 que j'interprète comme étant des clefs "aux alentours" de 1295724114596140. Hors, si la clef est effectivement de 1024bits, la clef la plus grosse qu'il est possible de générer est 1,797693134862315907729305190789e+308 (1 avec 300 (!) zéros derrière).

Ne serait-il pas judiceux de commencer par les unités ayant une mantisse bien plus élevée? Certes, les probabilités indiquent qu'il est aussi probable que la clef soit 1053 que 1515154518515151415475148943116581518515187451, mais humainement, est-ce le cas?

En effet, en tant que développeur Motorola, si je devais choisir une clef pour un téléphone, je choisirais plutôt une clef avec une mantisse élevée.

Qu'en pensez-vous?

Attention, si les unités de travail (ou WU sur les forums en anglais) sont bel et bien distribuées afin de calculer les clés en suivant un ordre de progression logique, leur nom correspond avant tout à un timestamp unique utilisé par le serveur qui gère le projet. Tu ne peux donc déduire l'amplitude de la plage de clés calculés aussi simplement à partir du nom de l'unité en question.

Ensuite, il est important de bien saisir le principe de fonctionnement d'une clé RSA.

Je me lance dans une tentative d'explication (n'hésitez pas à me corriger si je me trompe, je suis loin d'être un spécialiste en cryptographie).

Grossièrement il y a une clé publique N encodée sur 1024bits (ce qui représente comme tu l'as précisé quelque chose comme 1,79e+308 possibilité) et une clé privée p ou q également encodée sur 1024bits.

Ces deux clés sont liées par la formule mathématique suivante (attention c'est du lourd) : N = p*q

Après je ne connais pas le fonctionnement précis du bootloader ou des opérations de vérification des clés mais en gros cela repose sur la résolution de l'équation ci-dessus.

A l'heure actuelle nous connaissons la valeur de N (je pourrais la retrouver plus tard si ça vous intéresse) et le projet BOINC consiste à retrouver mathématiquement la valeur de p ou q (à partir du moment on l'on en connait un on peut déduire l'autre). Il ne s'agit donc pas de "casser" le bootloader à proprement parler mais de trouver la clé privée utilisée par Motorola pour signer ses ROMs et ainsi pouvoir signer nous-mêmes nos ROMs personnalisées.

La bonne nouvelle c'est que l'on peut donc théoriquement trouver la-dite clé tout seul avec un papier et du crayon, sans devoir trafiquer son Milestone, en testant toutes les combinaison possible jusqu'à trouver une valeur de p et q qui donne N.

La mauvaise c'est que l'on opère avec des nombres tellement grand qu'il est actuellement impossible de tester toutes les combinaisons dans un temps "raisonnable".

On connaissait l'algorithme et le fonctionnement exact utilisé par le calculateur de la première mouture du projet (MilestoneRSA) il était donc possible de débattre de la méthode employée et tenter de l'optimiser (là aussi, si ça intéresse du monde je pourrais tenter de vous en expliquer le principe de fonctionnement).

Puis les gars de la PNT (Polish National Team) ont débarqué clamant que l'algorithme en question était foireux, depuis ils ont repris le projet en main sous un nouveau nom (AndrOINC) et avec un nouvel algorithme. Le soucis c'est qu'ils se refusent à en publier le code source prétextant des histoires de propriété intellectuelle... Du coup il est très difficile de discuter "optimisation" vu qu'on a aucune idée précise de la façon dont ce dernier fonctionne...

Edited by Ming-Z
Link to comment
Share on other sites

J'ai osé m'aventurer sur Wikipédia pour voir exactement à quoi corréspond ce mot "RSA". J'ai pas compris grand chose mais du peu que j'ai compris c'est quand même un truc de fou furieux, et dire que les 3 gars qui ont pondu cet algo l'ont fait en 1977 ! :o

Bon ça reste wikipedia donc il faut toujours se méfier de ce qui est écrit sur ce site mais j'ai relevé quelques passages intéréssants et ou j'aimerais bien avoir quelques expliquations si possible :)

Il est possible que l'une des deux conjectures soit fausse, voire les deux. Jusqu'à présent, ce qui fait le succès du RSA est qu'il n'existe pas d'algorithme connu du grand public pour réaliser une attaque force brute avec des ordinateurs classiques.

Et c'est justement pas ce qu'on est en train de faire à l'aide de BOINC ?

Le 12 décembre 2009, le plus grand nombre factorisé par ce moyen, en utilisant une méthode de calculs distribués, était long de 768 bits. Les clés RSA sont habituellement de longueur comprise entre 1 024 et 2 048 bits. Quelques experts croient possible que des clés de 1 024 bits seront cassées dans un proche avenir (bien que ce soit controversé

Si j'ai bien compris la clé RSA du Milestone est de 1024 bits, on peut donc vraiment "éspérer" la trouver ?

Par sûreté, il est couramment recommandé que la taille des clés RSA soit au moins de 2 048 bits.

On pourrait presque parler de chance si Motorola en a choisi une de 1024 bits alors ... lol

Source : Wikipedia

Link to comment
Share on other sites

Voici une traduction approximative de la méthode de résolution mise au point dans le projet original MilestoneRSA :

Vous devez savoir que nous connaissons la clé publique N et que nous devons connaître P et Q pour calculer la clé privée.

P et Q sont des nombres premiers et sont reliés à N de la manière suivante : N = P * Q

Il est facile de déduire de l'équation ci-dessus que la valeur de la racine carré de N [que l'on peut écrire sqrt(N)] se situe donc entre les valeurs de P et Q

Nous savons que si P est supérieur à la racine carré de N alors Q est forcément inférieur à la racine carré de N et inversement. L'une de c'est deux valeur P ou Q est donc supérieure à la racine de N, laquelle des deux n'a aucune importance vu qu'elles sont totalement interchangeables.

Nous décidons donc de commencer à calculer à partir de la racine carré de N et on va en augmentant. Pour chaque nombre X impaire (on a pas besoin de tester les nombres paires car comme expliqué plus haut, P et Q sont des nombres premiers, or il est prouvé que tout les nombres premiers sont impaires exception faite du nombre 2) on calcule la retenue de la division N / X. Si la retenue est égale à 0, alors nous avons trouvé un de facteur premier P ou N (savoir lequel duquel des deux il s'agit n'a une fois de plus pas d'importance, mais pour plus de simplicité appelons le P).

Connaissant P on peut alors calculer Q de la façon suivante Q = N / P et possédons alors toutes les inconnues de l'équation, dès lors il nous est possible de signer nos propres ROMs de façon à ce que celle-ci puissent être validé par le bootloader.

Chaque unité de calcul se compose de 3 nombres : N, START et END. La valeur de END étant égale à celle de START + 100 000 000 000.

Le module de calcul calcule en boucle la retenue de N / X pour toute les valeurs impaires de X comprise en START et END. Si la retenue est égale à 0 il s'arrête alors et retourne au serveur la valeur de X ayant permis de valider le calcul. On connait alors P (ou Q).

Voilà pour ce qui était du fonctionnement du projet MilestoneRSA. Comme vous le voyez cela se base sur une logique relativement simple. Bien entendu celle-ci n'est pas exempte de défaut.

Le premier étant de calculer dans le mauvais sens : En effet tester X en allant de sqrt(N) vers N cela revient à vérifier un nombre de combinaisons égale à quelque chose comme (N - sqrt(N)) / 2. Ce qui correspond grosso-merdo à un groooooooooooooooooooos nombre s'encodant sur 1023bits.

En allant dans l'autre direction, de sqrt(n) vers 0 on réduit le nombre de combinaisons tester à quelque chose comme sqrt(N) / 2. Ce qui correspond cette fois à un gros nombre s'encodant sur 512bits.

L'autre défaut de cette méthode est qu'elle repose sur la division et que d'après les gars de la PNT, au niveau informatique la division est une des opérations les plus lentes. C'est d'ailleurs là-dessus qu'ils se sont appuyé pour développer leur super-module de calcul qui a fini par faire tomber le serveur original.

Malheureusement pour nous, comme ces derniers maintiennent le secret sur la façon exacte donc fonctionne leur module de calcul il est impossible de vérifier ce que fait ce dernier et ainsi de s'assurer de son bon fonctionnement et de son optimisation. On ne peut donc que leur faire confiance.

Il y a d'ailleurs quelques personnes sur XDA et (non des moindres) qui commencent à râler en réclamant à la PNT la mise à disposition de leur code source.

Avouez que c'est une situation pour le moins ironique :lol:

Enfin pour les curieux qui se demandent quelle est la valeur de N, est bien la voici :

130302296876495664949661851680712011323312218834692385409623477008770865634659674156795804984537277912018798333263614293465141543417786692641368992984327637616442187669331580699115569820799572488140940906656454027164582729057745051164346395037158084882727830713343954973996507744959096964190716798991681022591

En écriture hexadécimal ça donne :

B98E7F4EE7C2FA971E4807B619133C2859ECD24FEDE69CC6C096E7701C77F07C24FAC4C39B40C159CF8C8F9981C2FFD00C862359BC43592FA9B8591967EE0EC5C9EE401F69249610EEB7DCA96644ABB8E16AABEAC64FCF0A5140529F0B220E3C68097E28B6BCC96C3F778A8DA5582CF6AE7CFEC62612E1AFCE462CF0A1396A7F

Edited by Ming-Z
Link to comment
Share on other sites

Et c'est justement pas ce qu'on est en train de faire à l'aide de BOINC ?

En fait on ne connait pas d'algo assez efficace et rapide pour trouver la combinaison. La méthode existante

se résume à de la recherche à tatons

Si j'ai bien compris la clé RSA du Milestone est de 1024 bits, on peut donc vraiment "éspérer" la trouver ?

La dernière clef trouvé à été une clef de 768.

Oui MAIS. Ceci à été l'oeuvre de plusieurs Laboratoire de math et de sécurité info.

Ces laboratoires avaient à leur disposition une puissance de calcul ... colossale.

De plus des génies matheux se sont penchés sur le problème un sacré moment pour optimiser leur recherche.

Donc grosso merdo, Non, on ne peut pas espérer trouver la clef. Mais sur un malentendu pourquoi pas.

Par sûreté, il est couramment recommandé que la taille des clés RSA soit au moins de 2 048 bits.

Oui parce que avec la puissance de calcul mondial, et le temps que cela prendrait, ce chiffrement est plus que sûre, quelques soient les méthodes utilisé. La base actuelle de 1024b est pour le moment on ne peut plus sûre. Dans quelques années (décennie) il deviendra peut être nécessaire de passer sur un chiffrement à 2048 bit. Pour le moment ça reste du luxe et de la paranoia.

Edited by hiroko
Link to comment
Share on other sites

Une clé de ce type n'est pas choisi humainement, c'est le pc qui la génère automatiquement. Donc la clé peut se situer n'importe où.

Si tu veux tester le principe, regarde les clés générées pour des protocoles type OpenVPN, c'est certes assez différent mais le principe de clé privée/publique généré est le même, il me semble...

EDIT:

Geoxyde > le calcul GPU n'est toujours pas activé/implémenté. Donc il faudra patienter encore un peu. La seul chose dans ton cas est que ton GPU n'est pas détecté et effectivement cela va te poser problème lorsque le calcul par GPU sera activé. N'ayant pas de carte ATI (nVidia ftw :P ) je ne peux pas t'aider plus que ça. A la limite installe des pilotes plus récents via le site d'ATI...

Salut,

Tout est réparé ... il m'a suffit de réinstaller la version x64 disponible sur BOINC>toutes les versions et mon GPU a été automatiquement détecté. Maintenant, il n'y a plus qu'à attendre que le calcul par GPU soit activé. B)

Link to comment
Share on other sites

En fait on ne connait pas d'algo assez efficace et rapide pour trouver la combinaison. La méthode existante

se résume à de la recherche à tatons

La dernière clef trouvé à été une clef de 768.

Oui MAIS. Ceci à été l'oeuvre de plusieurs Laboratoire de math et de sécurité info.

Ces laboratoires avaient à leur disposition une puissance de calcul ... colossale.

De plus des génies matheux se sont penchés sur le problème un sacré moment pour optimiser leur recherche.

Donc grosso merdo, Non, on ne peut pas espérer trouver la clef. Mais sur un malentendu pourquoi pas.

Oui parce que avec la puissance de calcul mondial, et le temps que cela prendrait, ce chiffrement est plus que sûre, quelques soient les méthodes utilisé. La base actuelle de 1024b est pour le moment on ne peut plus sûre. Dans quelques années (décennie) il deviendra peut être nécessaire de passer sur un chiffrement à 2048 bit. Pour le moment ça reste du luxe et de la paranoia.

Merci pour tes précision ;)

Link to comment
Share on other sites

Ca prend une tournure inquiétante cette histoire...

Le projet monte tranquillement en puissance alors que des sites majeurs commencent à relayer l'information. Mais en parallèle à cette bonne nouvelle, plusieurs personnes (dont je fais parti) commencent à s'inquiéter du manque de transparence et de l'absence de code source librement accessible. Un développeur a décidé de prendre le taureau par les cornes en désassemblant la version Linux du module de calcul.

Et son constat est terrible. Selon lui l'algorithme utilisé par la PNT est faux ! Il l'explique sur le forum officiel du projet.

Je n'ai malheureusement pas les compétences informatiques nécessaire pour vérifier l'algo par moi même. Cependant les erreurs mathématiques qu'il a relevé sont fondées.

Edited by Ming-Z
Link to comment
Share on other sites

En gros on tente un bruteforce sur un algorithme faux. Déjà que comme ca, on a autant de chance de gagner a l'euromillion que de le trouver d'ici 100 ans...

Faudrait essayer d'amadouer un des mecs qui a fait l'algorithme ce serait bien plus simple :(

Link to comment
Share on other sites

Alors du côté de chez XDA plusieurs personnes commencent à mettre en doute la légitimité de l'équipe en charge du projet en raison de leur manque total de communication et de transparence. Face à cela la seule réaction officielle de la PNT (transmise par l'un de leur contact sur XDA) a été d'invoquer une limitation du forum XDA qui interdit aux nouveaux inscrits (moins de 10 messages) de poster dans les sections dédiées au développement... En gros ils réclament un passe-droit afin de pouvoir donner des informations sur le projet.

En parallèle à cela du côté du forum officiel dédié au projet, Girino, le développeur ayant annoncé que l'algo était défectueux à passer le week-end à appuyer ses propos en invitant les devs de la PNT à corriger leur algo. L'un deux à répondu en niant tout simplement les propos et démonstrations de Girino, affirmant sans plus d'explication que l'algo est correct.

Enfin, pour clore le sujet en beauté, la PNT a annoncé en fin d'après-midi la clôture du projet à compté du 31 janvier 2011 par faute de financement pour maintenir leur serveur...

Donc pour résumer toute cette histoire :

- Tout commence avec un étudiant plutôt talentueux mais aux ressources matérielles limitées qui lance le projet sans trop y croire.

- Victime de son succès il rencontre quelques difficulté à maintenir convenablement ce dernier.

- Débarque la PNT, une équipe polonaise dédiée aux projets BOINC, qui vampirise littéralement le projet original avec un calculateur trafiqué et fini d'achever le serveur original.

- La PNT, reprend le projet sous son nom promettant le support du GPU et autres améliorations (on peut bien évidement faire des dons pour les soutenir dans cette croisade)

- Le projet remonte en puissance et trouve du relais auprès de quelques médias spécialisés.

- Le nombre de participants augmentant, certains en viennent légitimement à demander des précisions quand au bon fonctionnement du projet.

- La PNT joue la politique de l'autruche en refusant de livrer son code source et en communiquant de manière très illisible.

- Un utilisateur démontre l'inefficacité du calculateur de la PNT.

- La PNT nie en bloc et continue sa politique de l'autruche.

- La pression monte doucement sur XDA ainsi que sur le forum officiel du projet.

- La PNT annonce la suspension du projet par manque de finances...

En tout cas mon opinion est maintenant tranchée. Cette équipe se fout de la gu***** de la communauté depuis le début. Alors pourquoi donc ? Quel est leur but non-avoué ? J'ai bien ma petite idée digne... Mais ça ressemble à un mauvais film d'espionnage...

La bonne nouvelle cependant c'est que cette expérience à démontrée une chose : même si le projet peut paraître irréaliste (casser la clé RSA 1024 bits du Milestone par force-brute) la communauté est prête à suive pour peu qu'une bonne âme soit en mesure de fournir un serveur qui tienne la route et que le projet soit géré de manière open-source.

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

 Share




×
×
  • Create New...