Clefs publiques commençant par "1"

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:

5 Likes

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:

5 Likes

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 Likes

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 :

https://git.duniter.org/nodes/typescript/duniter/-/blob/oxyde-parse-and-verify-tx/test/integration/transactions/transaction-unlock-pubkey-with-leading-1.ts

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 Likes

Fait : Dubp v13 (!1) · Merge requests · documents / RFCs · GitLab

3 Likes

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 Likes

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 Likes

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 Likes

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é…

Le changement de protocole ce fait automatiquement quand plus de 70% des nœuds du réseau son prêt. À ce moment-là, tous les nœuds sous ancienne version se désynchronise.

Même si je revert le support des clés courtes, quand le réseau sera en DUBPv13, Duniter 1.7 ne sera plus utilisable de toute façon. Tout changement de protocole est nécessairement cassant ne serait-ce par l’incrément du numéro de version du block.
De plus, DUBPv13 contient d’autres changements cassant, comme le changement de la définition de CSV pour devenir compatible avec les LN, ainsi que le retrait de la contrainte sur le blockstamp des docs transaction que tu me demandes de re prioriser.

Duniter 1.8 à passé une très longue campagne de test, les problèmes de sync ne sont pas liées au changement de version mais à l’inefficience du process de sync qui réalise beaucoup trop d’I/O, qui se ressent de plus en plus avec le nombre de blocs qui augmentent.

Le problème c’est que pour régler cela je ne vois pas d’autre moyen que de réécrire entièrement le process de synchronisation, ce qui demande au préalable de migrer toute la base de données leveldb, chantier titanesque sur lequel j’étais avant que tu ne me pousses a re prioriser GVA.

Mais ce n’est pas tout, la partie «network» de la sync pose aussi des problèmes, mais là il faut carrément créer une nouvelle couche réseau, c’est dans ma roadmap moyen/long terme.

En attendant, il est nécessaire de disposer d’un SSD pour synchroniser la blockchain, ou alors de copier le dossier data, je veux bien fournir une copie de mon dossier data si ça peut te débloquer :slight_smile:

1 Like

En fait il y a une autre solution pour les utilisateurs sur HDD: sync dans /dev/shm :

duniter --home /dev/shm/duniter sync g1.duniter.org
cp -r /dev/shm/duniter/duniter_default/data ~/.config/duniter/duniter_default/data
2 Likes

ok je comprends que, de toute façon, un changement de protocole aura lieu.

Quel est le checksum de la clef publique :

  • 11111111111111111111111pubKey49311
  • alias pubKey49311

Est-ce :

  • 14R ( issue de 11111111111111111111111pubKey49311 resultat avec 1 initaux)
  • 4Ru ( issue de 11111111111111111111111pubKey49311 resultat sans 1 initaux)
  • 12p ( issue de pubKey49311 resultat avec 1 initaux)
  • 2p7 ( issue de pubKey49311 resultat sans 1 initaux)

PS : actuellement, la fonction checkKey(‹ pubKey49311:??? ›) de g1lib.js considère les 4 comme valide.
En revanche pubKey2checksum(‹ pubKey49311 ›) comme pubKey2checksum(‹ 11111111111111111111111pubKey49311 ›) retournent 14R à moins de leur spécifier des paramètres optionnels pour obtenir les autres résultats.

3 Likes

Ça n’est pas une clé publique valide selon DUBPv12, car elle est trop courte et doit faire entre 43 et 44 caractères :

echo "11111111111111111111111pubKey49311" | wc -c
35

Donc :

#44
silkaj checksum 111111111111111111111111111111111pubKey49311
111111111111111111111111111111111pubKey49311:HnN

#43
silkaj checksum 11111111111111111111111111111111pubKey49311
11111111111111111111111111111111pubKey49311:BhW

Ah oui. Y’a pas d’hélice, hélas, c’est là qu’est l’os.

11111111111111111111111pubKey49311 fait 34 caractères. Elle ne devrait pas être valide. Pourtant, sa conversion en bytes fait bien 32 bytes.

Je ne comprends pas :upside_down_face:

J’ai écrit un petit script Python pour tester toutes les clefs pub valides entre pubKey49311 et 11111111111111111111111111111111pubKey49311 (43 caractères) :

script
import hashlib
import base58

MAX_PUBKEY_LENGTH = 44

str_pubkey = "pubKey49311"

def ck_from_pk_bytes(pk_bytes):
    hash = hashlib.sha256(hashlib.sha256(pk_bytes).digest()).digest()
    return base58.b58encode(hash)[:3].decode("utf-8")


#script

print ("len, len_bytes_tortue, ck_tortue, len_bytes_rfc, ck_rfc_0016, pubkey")
for n in range(0, (MAX_PUBKEY_LENGTH - len(str_pubkey))):
    # add ones before pubkey
    pubkey = n * "1" + str_pubkey
 
    # convert to bytes
    pk_b_tortue = base58.b58decode(pubkey)
    
    pk_b_rfc_0016 = bytearray(pk_b_tortue)
    while len(pk_b_rfc_0016) < 32:
        pk_b_rfc_0016 = bytearray(b"\x00") + pk_b_rfc_0016
        
    # compute checksums
    ck_tortue = ck_from_pk_bytes(pk_b_tortue)
    ck_rfc_0016 = ck_from_pk_bytes(pk_b_rfc_0016)
    
    # display result
    print(str(len(pubkey)) + ":", len (pk_b_tortue), ck_tortue, len(pk_b_rfc_0016) , ck_rfc_0016, pubkey)

résultat, une clef pub de longueur 43 n’est pas valide, elle fait 41 octets. De même pour une de longueur 40, qui fait 38 octets. Le loup est-il dans mon script ? Y’a un truc que je ne comprends pas, là, sans doute sur la conversion de la réprésentation base58 vers les bytes.

len, len_bytes_tortue, ck_tortue, len_bytes_rfc, ck_rfc_0016, pubkey
11: 9 12p 32 14R pubKey49311
12: 10 Gym 32 14R 1pubKey49311
13: 11 6Rg 32 14R 11pubKey49311
14: 12 J8X 32 14R 111pubKey49311
15: 13 C7x 32 14R 1111pubKey49311
16: 14 AYi 32 14R 11111pubKey49311
17: 15 8HQ 32 14R 111111pubKey49311
18: 16 Dvz 32 14R 1111111pubKey49311
19: 17 EVs 32 14R 11111111pubKey49311
20: 18 vnd 32 14R 111111111pubKey49311
21: 19 3Bk 32 14R 1111111111pubKey49311
22: 20 Bqg 32 14R 11111111111pubKey49311
23: 21 4et 32 14R 111111111111pubKey49311
24: 22 HhR 32 14R 1111111111111pubKey49311
25: 23 JB3 32 14R 11111111111111pubKey49311
26: 24 9Zs 32 14R 111111111111111pubKey49311
27: 25 CM2 32 14R 1111111111111111pubKey49311
28: 26 FFP 32 14R 11111111111111111pubKey49311
29: 27 GB5 32 14R 111111111111111111pubKey49311
30: 28 GsF 32 14R 1111111111111111111pubKey49311
31: 29 AMh 32 14R 11111111111111111111pubKey49311
32: 30 7MZ 32 14R 111111111111111111111pubKey49311
33: 31 4Za 32 14R 1111111111111111111111pubKey49311
34: 32 14R 32 14R 11111111111111111111111pubKey49311
35: 33 865 33 865 111111111111111111111111pubKey49311
36: 34 2M4 34 2M4 1111111111111111111111111pubKey49311
37: 35 Ay9 35 Ay9 11111111111111111111111111pubKey49311
38: 36 FuA 36 FuA 111111111111111111111111111pubKey49311
39: 37 2cv 37 2cv 1111111111111111111111111111pubKey49311
40: 38 8j1 38 8j1 11111111111111111111111111111pubKey49311
41: 39 68r 39 68r 111111111111111111111111111111pubKey49311
42: 40 Eqt 40 Eqt 1111111111111111111111111111111pubKey49311
43: 41 BhW 41 BhW 11111111111111111111111111111111pubKey49311

NB : Duniter a déjà accepté la clef pub 11111111111111111111111111111111111111111111 en dépense.

$ silkaj balance 11111111111111111111111111111111111111111111
╒══════════════════════════════╤══════════════════════════════════════════════════╕
│ Balance of pubkey            │ 11111111111111111111111111111111111111111111:G3N │
├──────────────────────────────┼──────────────────────────────────────────────────┤
│ Total amount (unit|relative) │ 50.75 Ğ1 | 4.92 UD Ğ1                            │
├──────────────────────────────┼──────────────────────────────────────────────────┤
│ Total relative to M/N        │ 0.01 x M/N                                       │
╘══════════════════════════════╧══════════════════════════════════════════════════╛

1 Like

Le comportement est variable selon les implémentations de base58.
J’ai eu le problème en Rust, je suis obligé d’effacer les octets en trop qui valent zéro et qui sont au début.

Voir ici:

https://git.duniter.org/libs/dubp-rs-libs/blob/dewif-rework/crypto/src/bases/b58.rs#L74-78

Ah ben du coup, il va falloir revoir la RFC pour traiter ce cas-là également (le cas où la clef pub est > à 32 octets et commence par des octets nuls). Je me trompe ?