Clefs publiques commençant par "1"

Bonjour,

Une question qui fait suite à un ancien post que je ne retrouve pas ce message.

Il y a quelques semaines, une personne avait posté une question : sa clef publique commençait par un « 1 » , par exemple :

12BjyvjoAf5qik7R8TKDJAHJugsX23YgJGi2LmBUv2nx

et dans les logs Duniter, le « 1 » de tête n’était pas affiché.

@elois avait répondu que c’était normal, car le « 1 » en base58 correspond à « 0 ».


Si je vous parle de ça, c’est que je suis en train d’implémenter l’affichage généralisé des checksum dans Silkaj, et je me demande si je dois prendre ce phénomène en compte, comment, ou si je me torture l’esprit pour rien.

Ces deux clefs publiques sont-elles équivalentes ? Avec une même clef privée, peut-on signer des documents qui correspondent à ces deux clefs publiques ? :

12BjyvjoAf5qik7R8TKDJAHJugsX23YgJGi2LmBUv2nx
2BjyvjoAf5qik7R8TKDJAHJugsX23YgJGi2LmBUv2nx

Si elles sont équivalentes, faut-il gérer le fait que leurs checksums sont différentes, et « forcer » une checksum plutôt que l’autre? Mon avis est que non, mais je préfère confirmer avant de faire une sottise.

Pourquoi non ? L’utilisateur, ayant la clef pub 12Bjyvjo..., en calcule le checksum en suivant les specs, et trouve 8pQ. Il serait tout à fait perturbé de vois que Silkaj lui donne 5vi en réponse, à savoir le checksum de la clef 2Bjyvjo...

J’observe que les checksum sont différentes :

Generate Transaction:
   - From:    AhRMHUxMPXSeG7qXZrE6qCdjwK9p2bu5Eqei7xAWVEDK:CWj
   - To:      12BjyvjoAf5qik7R8TKDJAHJugsX23YgJGi2LmBUv2nx:8pQ 
   - Amount:  1000.0
   - To:      2BjyvjoAf5qik7R8TKDJAHJugsX23YgJGi2LmBUv2nx:5vi 
   - Amount:  1000.0
   - Total:   2000.0
Transaction successfully sent.
3 J'aimes

Je vais avancer une hypothèse au pif :

  • Si tu vois que la clef fait 43 caractères au lieu de 44, tu peux sans doute ajouter 1 devant, avant de calculer le checksum.

Si on est sûr qu’une clef de 43 caractères a son premier caractère escamoté.

Je l’aurais plutôt fait dans l’autre sens : si je vois une clef qui commence par 1, alors j’enlève ce 1 avant de calculer le checksum.

Ben non, je suis loin d’en être sûr, justement.


Mais je pense que le mieux est de traiter 1Bghkj… et Bghkj… comme deux clefs différentes, et de calculer deux checksums différentes. Les specs de @Tortue ne mentionnent pas cette histoire de « 1 » au début.

Ces deux clés publiques ont exactement la même représentation binaire, elles sont issues de la même clé privée et une signature valide pour l’une sera valide pour l’autre (sauf si la clé publique se situe également dans le message signé, le « 1 » faisant varier le contenu du message).

C’est uniquement leur représentation en base 58 qui charge, certainement dû au fait que les différents logiciels n’utilisent pas la même lib base58.

Non tu ne te tortures pas pour rien, il faut prendre en compte ce phénomène, j’ai été obligé de le faire dans dup-crypto sinon certaines signatures valides étaient considérés comme invalides : j’ai carrément été obligé de créer un champ supplémentaire pour compter ses *** de « leading 1 » : https://git.duniter.org/libs/dubp-rs-libs/-/blob/master/crypto/src/keys/ed25519.rs#L170

Aujourd’hui Duniter considère (à tort) les 2 clés comme 2 comptes différents car c’est les chaînes de caractères qui sont comparées.
Quand la migration de Duniter en Rust sera plus avancée, ce sont les représentations binaires des clés qui seront comparées, il sera donc possible d’utiliser les Ğ1 du compte 2BjyvjoAf5qik7R8TKDJAHJugsX23YgJGi2LmBUv2nx quand bien même elles auront été envoyées au compte 12BjyvjoAf5qik7R8TKDJAHJugsX23YgJGi2LmBUv2nx.

En attendant, il est préférable que les checksum soit différent, Mais à terme, il faudra que le checksum soit identique : Il faudra alors supprimer les « leading 1 » avant de calculer le checksum.
On pourrait aussi calculer le checksum à partir de la représentation binaire de la clé publique, ce qui serait plus logique et plus simple, se baser sur les chaînes de caractères cause toutes sortes d’effets de bord indésirables, les traitements ne devraient pas se baser dessus, ça ne devrait être qu’une « human view ».

3 J'aimes

OK cool !

Bon. Du coup les gens qui ont une pubkey qui commence par 1 verront le checksum changer. Tant que c’est bien communiqué, ok.

Dans ce cas, ce sont toutes les checksum de toutes les clefs publiques qui changeraient d’un coup. Si on veut faire ça, faut peut-être pas trop tarder… Avant que tout le monde se soit habitué à sa checksum ?

Voici le type de somme de contrôle que j’ai trouvé dans le module base58.

Voir la fonction suivante :

base58.b58decode_check()

Avec comme description du dépôt :

Base58 and Base58Check implementation compatible with what is used by the bitcoin network.
1 J'aime

Si ça ne tenais qu’a moi tout les traitements seraient en binaire depuis le début… Oui bien entendu qu’il faudrait le faire correctement de suite, de mon coté je peut faire en sorte que les clés avec leading 1 soient consommable dès la prochaine version de Duniter :slight_smile:

Et l’on voit que le checksum est bien calculé à partir de la représentation binaire et non de la représentation base 58 : https://github.com/keis/base58/blob/master/base58/init.py#L150

Ça veut donc dire qu’une clé peut faire moins de 43 caractères, donc que tous les programmes utilisant {44,43} ont un problème ? Par exemple, la clé 1 serait valide ?

Comment la checksum pourrait changer si elle est calculée depuis la forme binaire ? Il faudrait enlever des octets 0x00 au début ?

Oui, je ne vois aucune justification théorique à ce que la représentation base 58 d’une clé publique Ed25519 ne puissent pas faire moins de 43 caractères.

Si l’espace des 2^256 clés publiques possible était équiprobable, ce serait le cas pour ure clé sur 3364. Mais la fonction de la courbe elliptique Ed25519 n’est pas bijective, (plusieurs seed peuvent donner le même couple de clés), et à tendance à avoir plus de points parmi les très grands nombres. La probabilité réelle d’avoir une clé publique de moins de 43 caractères est donc bien plus faible, mais ce n’est pas impossible.

Par exemple, la clé 1 serait valide ?

Tout dépend ce que l’on entend par « valide ». Si l’on entend par là : un point existant sur la forme « Edward » de la courbe Curve25519 alors non.
Mais si l’on entend : toute clé publique qui peut être parsée et utilisée dans les traitements métier sans les faire planter alors oui.
Dans la pratique, aucun traitement ne vérifie que la clé publique correspond bien à « un point de la représentation d’Edward de la courbe Curve25519 ». On vérifie simplement si un triplet (message, pubkey, signature) est valide ou non, et cette vérification peut sans problème se faire avec la clé zéro (représentée « 1 » en base58), c’est d’ailleurs ce que je fais dans mes tests unitaires :stuck_out_tongue:

Elle ne pourrait pas justement, car la représentation binaire est de taille fixe :slight_smile:

4 J'aimes

Du coup je viens de m’amuser à créer un TU qui cherche une clé publique ed25519 de moins de 43 caractères, et j’en ai trouvée une en moins d’une seconde !

Le test est sur la branche gen-pubkey-42-len du dépôt dubp-rs-libs

La clé publique en question : 6gy5DmTfGKEF79qru957rPdiDGtGXnHP49ocE7KXNX
Et la clé privée associée : 3ZS3coLVeNDi5MpvGeTR8UvXXbK42Aj5nL7Qjq1B7EobFBghLy8fyWAa7rzhnN2rp8ur4byH74GMWXwqEhnvow2w
Obtenue avec la seed : 9cfdVoFGFEswB66Hp14vfvB21sNqrFtTvbVTDPFaTXVH

Pour générer votre propre clée publique de moins de 43 caractères :

git clone https://git.duniter.org/libs/dubp-rs-libs.git -b gen-pubkey-42-len
cd dubp-rs-libs
cargo test --release -p dup-crypto --lib -- keys::ed25519::tests::tmp_find_key_42 --exact --nocapture

On peut donc confirmer définitivement par l’expérience qu’une clé publique ed25519 valide peu bel et bien faire moins de 43 caractères dans sa représentation base 58 et que tous les programmes qui utilisent une regex en {44,43} ont bien un problème :stuck_out_tongue:

EDIT : J’ai également trouvé une clé publique ed25519 à 41 caractères en laissant chauffer le cpu 15 secondes :

pubkey_b58="uCBY5yuaA83d1sqKZGz8cJLv79b53ftfND3cLupZH"
seed=DvVZM6C2VYnn88AUxjm9H4tWk9coJJPE7y65e8xxgvRd
expanded_base58_secret_key="4qeTGnRLyb2AtkjoZfZYLH9UY7dLk6kNvMHv3bmAfC46MuJJRGSw9GwurvLZ96w1QouWWpM1cRQVCYGhb8ddAe3D"

J’ai essayé avec 40 caractères, mais je n’ai rien après 60 secondes et j’ai pas envie de faire trop chauffer mon cpu donc j’ai arreté là :sweat_smile:

4 J'aimes

Si la limite basse est potentiellement inconnue, peut-on garder la règle de la limite haute à 44 caractères pour vérifier une clef base58 ?

Ça a l’air :

>>> len(base58.b58encode(b"\xff"*32))
44

Par contre, le module Python base58 a parfois un comportement bizarre :

>>> len(base58.b58decode("1"*44))
44
>>> len(base58.b58decode("1"+"a"*43))
33
>>> base58.b58decode("1"+"a"*43)
b'\x00\x08\x9a"p\xf8\xb8p\xbd_\x13#\x11\x17}\xbe\xc9\xadra\x84d\t\x06OU\xc2uyC^P\xd7'

Il ne faut donc pas oublier de virer les zéros en trop au début.

Et certaines clés base58 ne sont pas valides et font 33 octets, car 58^44 > 255^32.

2 J'aimes

Oui car toute clé publique ed25519 fait 32 octets et comme 58^44 > 2^256 on est certain que toutes les clés publiques ed25519 peuvent être représentées en base58 par 44 caractères ou moins :slight_smile:

Voilà qui est fait sur la branche oxyde-parse-and-verify-tx :smiley:

Et voici le test qui prouve qu’en DUBPv13 il sera possible de consommer les sources de la clé 1A avec la clé A :

Cela nécessite un changement de protocole, car on change les conditions d’utilisation d’une source, il faudrait d’ailleurs que je le précise dans la RFC !

A noté que ma priorité étant désormais la migration de Duniter, lorsque je dois modifier un traitement dans Duniter j’en profite pour le migrer en même temps (dans la mesure du possible).
C’est ce que j’ai fait ici : j’ai migré en Rust le traitement qui vérifie que les preuves de déblocage d’une source sont valides (ce qui m’a demandé de migrer également le parser du script de conditions).

@matograine tu peux donc de suite générer la même checksum avec ou sans leading 1, le mieux est de le faire sur la représentation binaire comme le fait le module python base58 :slight_smile:

À noter que les comptes A et 1A seront toujours présentés comme différents via l’api BMA (car stockés en DB comme 2 comptes différents). Cela sera réglé lors de la migration de la DB, mais comme c’est un chantier titanesque ce sera probablement pour une future version (afin de ne pas bloquer la sortie de Duniter 1.9).

3 J'aimes

Fait : https://git.duniter.org/documents/rfcs/-/merge_requests/1/diffs?commit_id=80ec1e5fa9df6d81351b803a4fd21678643cb27a

3 J'aimes

Zut, il va falloir revoir le DUBP :sweat_smile:

A public key is to be understood as an Ed25519 public key.
Its format is a Base58 string of 43 or 44 characters, such as the following: …

C’est @moul qui a pointé ça, Duniter renvoie une erreur quand on lui fait des requêtes qui concernent des clefs publiques « courtes ».

2 J'aimes

Je descends à 40 pour DUBPv13. Je ne le sens pas de descendre en dessous car Duniter est faiblement typé (quasiment tous les champs sont des string), et donc ça peut causer des effets de bord chelous (comme considérer un champ comme une clé publique alors que c’est tout autre chose).

Quand la migration sera suffisamment avancée, les regex pubkey n’existeront plus car tout sera géré par le typage fort, la limite basse sera alors zéro au lieu de 40, mais ce ne sera pas avant 1 an voir plus.

2 J'aimes

Un message a été scindé en un nouveau sujet : Quelle priorité dans les devs Duniter?

Attention au biais de discussion : ce n’est pas parce que l’on parle d’un sujet que c’est sur ce sujet que je consacre le plus de temps, bien au contraire.

La majeure partie du temps que je consacre à Duniter ces dernières semaines n’a rien à voir avec ce sujet « Clefs publiques commençant par “1”»

2 J'aimes

Petite question : si tu modifie le protocole, il y a bien un risque de fork, non ?
Par exemple, sur mes noeuds, je suis repassée en v1.7 car impossible de finir une synchro en 1.8.
Si tu passes en prod cette modif, il suffira de consommer une clef plus courte pour déclencher un fork, non ?
Je me retrouverai alors avec des noeuds bloqués…

Voilà ce dont il est question, en terme de priorité…