Disclaimer: Je suis vraiment pas un expert en cryptographie, je fais plus du réseau et du système qu’autre chose, je fais plus cet article pour présenter ce que j’ai pu découvrir et comprendre que pour faire un cours ou un tutoriel sur les concepts abordés.

Un peu de contexte

Il y a quelques mois j’ai eu l’occasion de travailler sur l’implémentation de méthodes de reconciliation de l’information dans le cadre de l’implémentation de protocoles de dérivation de clés cryptographiques au niveau de la couche physique. Pour faire simple, l’idée c’est que nous avons nos bons vieux \(Alice\) et \(Bob\) qui détiennent tous les deux une clé de \(n\) bits. Ces deux clés sont supposées proches mais non égales, certains bits diffèrant d’une clé à l’autre. En d’autre termes, nous avons \(\lVert\ key_{Alice}\ \rVert\ =\ \lVert\ key_{Bob}\ \rVert\) tel que \(key_{Alice}\ \sim\ key_{Bob}\), et \(dis(key_{Alice},\ key_{Bob})\ \leq\ t\), avec \(dis\) la distance de Hamming et \(t\) le nombre maximum de bits différents que l’on accepte.

Je vais détailler un peu cette explication pas très très formelle, mais si elle était clair vous pouvez sauter à la suite!

Distance de Hamming

Dans un premier temps, rappelons la notion de distance de hamming. Pour faire simple, soient deux mots binaires de taille \(n\) \(mot_{A}\) et \(mot_{B}\). La distance de hamming entre \(mot_{A}\) et \(mot_{B}\) écrite ici \(dis(mot_{A},\ mot_{B})\) est égale au nombre de bits qui diffèrent à position égale entre \(mot_{A}\) et \(mot_{B}\). Et comme un exemple vaut mille mots:

Ici \(\lVert mot_{A} \rVert\ =\ \lVert mot_{B} \rVert\ =\ 8\) et \(dis(mot_{A},\ mot_{B})\ =\ 3\).

Par exemple en C on pourrait calculer la distance de hamming entre deux octets de cette manière:

uint8_t mot_A = 0b10011010;
uint8_t mot_B = 0b10111100;
  
int dis = __builtin_popcount(mot_A ^ mot_B);

En faisant \(mot_{A}\oplus mot_{B}\) on met à 1 uniquement les bits qui diffèrent entre \(mot_{A}\) et \(mot_{B}\), et on utilise __builtin_popcount pour compter le nombre de bits à 1.

Si l’on revient à \(dis(key_{Alice},\ key_{Bob})\ \leq\ t\), on comprend donc que l’on accepte au plus \(t\) bits différants entre \(mot_{A}\) et \(mot_{B}\).

Et ensuite ?

C’est bien sympas tous ces trucs de distance de Hamming, mais de 1 ni \(Alice\) ni \(Bob\) ne peut la calculer sans connaître la clé de l’autre, et de 2 même si on sait que disons 8 bits diffèrent entre \(key_{A}\) et \(key_{B}\), on ne sait pas desquels il s’agit, donc ça sert à rien en fait cette histoire… Alors oui, un peu en effet, mais au moins maintenant on est tous raccord avec la notion de distance de Hamming, c’est déjà ça non ?

Mais sur le principe vous avez raison, nous n’avons toujours pas abordés le coeur de cet article… Si \(dis(key_{A},\ key_{B}\ \leq\ t\), alors comment je fais pour faire passer de \(key_{A}\ \sim\ key_{B}\) à \(key_{A}\ =\ key_{B}\) sans communiquer ni \(key_{A}\), ni \(key_{B}\) ?

Donne moi un dessin que je retrouve ta clé!

Vous connaissez les Secure Sketch ? C’est un objet cryptographique assez simple mais qui va nous servir. En gros, \(Alice\) va prendre sa clé et générer un \(sketch\) à partir de celle-ci. Le \(sketch\) c’est un mot binaires de taille \(n\), qui n’est pas censé donner d’information sur la clé utilisée pour le générer (dans la théorie, on reviendra sur ça un peu plus tard promis…). Cependant, donné un \(sketch\) et notre clé un peu égale mais pas vraiment en fait, on peut récupérer la clé utilisée pour générer le \(sketch\), toujours si \(dis(key_{A},\ key_{B})\ \leq\ t\) (je radote pas, je suis pédagogue nuance).

Grossièrement, cela dirait quelque chose comme, ça ferait quelque-chose comme ça, ça ferait… attends ça ferait quoi ?

C’est un schéma de haut niveau mais il donne je pense une bonne idée de ce que l’on cherche à faire. La constructions exacte que nous allons utiliser est décrite dans l’article Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data, Dodis et al., dans la partie Constructions for Hamming Distance.

Code de correction d’erreur

Le but n’est pas d’entrer en détail dans le principe des codes de correction d’erreur, puis bon moi et les maths hein… Mais si le sujet vous intéresse je vous recommande cette très bonne vidéo pour commencer. Nous nous contenterons de dire que donné un mot \(x\) de \(k\) bits, un code de correction d’erreur nous donnerait un mot \(C(x)\) de \(n\) bits, avec \(k\ \leq\ n\). Ensuite, soit \(C^{'}(x)\ \sim\ C(x)\), avec \(dis(C^{'}(x),\ C(x))\ \leq\ t\) on peut trouver les bits différants et corriger \(C^{'}(c)\) pour obtenir \(C(x)\). Hey, mais attendez ça ressemble vachement à ce que je décrivais plus tôt non ? Il doit y avoir un moyen d’utiliser cette propriété des codes de correction d’erreur à notre avantage non ?

Bon derrière cette question réthorique plus que forcée, voyons ce que l’on peut faire. Je ne vais pas rentrer dans les détails de l’article mentionné plus haut mais dans l’idée est la suivante:

1. Alice et Bob ont tous les deux une clé supposée proche, \(key_{A}\ \in\ \{0,1\}^{n}\) et \(key_{B}\ \in\ \{0,1\}^{n}\).
2. Alice tire aléatoirement un mot \(x\ \in\ \{0,1\}^{k}\), et utilise un code de correction d’erreur pour calculer \(C(x)\ \in\ \{0,1\}^{n}\).
3. Alice calcul ensuite \(sketch\ =\ key_{A}\ \oplus\ C(x)\). A ce stade, retrouver \(C(x)\) depuis \(sketch\) revient à deviner \(key_{A}\) et vice-versa.
4. Alice envoie à Bob \(sketch\).
5. Bob calcul \(C^{'}(x)\ =\ key_{B}\ \oplus\ sketch\). Du fait des propriétés de l’opération XOR, les bits qui diffèrent entre \(C^{'}(x)\) et \(C(x)\) sont les même que ceux qui diffèrent entre \(key_{A}\) et \(key_{B}\). Autrement dit, \(dis(key_{A},\ key_{B})\ \leq\ t\ \iff\ dis(C(x),\ C^{'}(x))\ \leq\ t\). Dans ce cas, il est donc possible de d’utiliser l’algorithme de correction d’erreur pour trouver les bits qui diffèrent entre \(C(x)\) et \(C^{'}(x)\), et donc les bits qui diffèrent entre \(key_{A}\) et \(key_{B}\).
6. Bob utilise donc un algorithme de décodage par syndrome qu’il a préalablement trouvé dans une librairie toute faite parce que c’est vraiment pas drôle à implémenter… Voir l’annexe BCH Syndrome Decoding in Sublinear Time du papier présentant la construction. Il se débrouille pour récupérer la liste des bits qui diffèrent et flip les bits qui différants sur \(key_{B}\), se retrouvant avec \(key_{A}\). Si la différence dépasse \(t\), alors le comportement dépend de la méthode utilisée mais l’on supposera que cela se détecte pour plus de simplicité.

Si l’on complète notre schéma de tout à l’heure, alors on obtient

Magie, \(Bob\) récupère la clé d’\(Alice\) sans l’avoir jamais communiquée directement… Mais est-elle aussi sûre qu’on le croit ? Nous en discuterons un peu plus tard, avant voyons comment implémenter cela…

PoC

Nous allons utiliser Sage, une librairie permettant de faire à peu près des maths en python. J’aime pas Matlab, et la “version libre” de Matlab, Octave est relativement incomplète, surtout au niveau des librairies de traitement de signal qui implémente des codes de correction d’erreur. Nous utiliserons un code BCH. Sans trop rentrer dans les détails, un code BCH se définit selon deux paramètres, \(N\) et \(d\). Dans notre cas binaire (code BCH sur \(GF_{2}\)), \(N\) est la taille en bits de notre mot de code \(C(x)\), et d la distance minimale entre deux mots. Sans rentrer dans les détails, sachons juste que l’on peut corriger jusqu’à \(\frac{d-1}{2}\) erreurs. Etant donné que je ne vais pas m’aventurer dans les détails de BCH, il va falloir me croire (et éventuellement me corriger) pour la suite.

Nous utiliserons un code BCH(255, 2t+1), générant des mots de code de 255 bits pouvant corriger jusqu’à t erreurs. La petite subtilité est que dans ce paramétrage, x fait 63 bits. Nous reviendrons un peu plus tard sur ce que cela implique mais c’est bien de le garder en tête.

N = 255
T = 30
code = BCHCode(GF(2), N, T * 2 + 1)

GEN

def ss(key: Vector_mod2_dense) -> Vector_mod2_dense:
    random_x = get_random_bits(code.dimension())
    C_x = code.encode(random_x)
    return C_x + key

Ici rien de sorcier, on utilise code.dimension() pour obtenir la taille des mots que l’on encode, et on tire ce nombre de bits aléatoirement. Ensuite, on génère \(C(x)\), et on calcul \(C(x)\ \oplus\ key\).

Quelques petites explications cependant… Vector_mod2_dense représente un vecteur d’un espace vectoriel sur le corps fini \(GF(2)\). Autrement dit, il s’agit d’un vecteur dont les coefficients appartiennent à \(\{0,1\}\), et dont les opérations sont définis modulo 2, eg. \(1 + 1 = 0\) Dans ce contexte, on peut définir un vecteur \(x=(0, 1, 1, 0, 1, 0, 0 1)\in GF(2)^{8}\) et on a grosso modo formalisé mathématiquement un octet (01101001), mais surtout l’addition se comporte comme un XOR… On implémente donc strictement la construction décrite plus haut dans GEN.

REP

def rep(key_p: Vector_mod2_dense, sketch: Vector_mod2_dense) -> Vector_mod2_dense:
    C_x_p = key_p + sketch
    try:
        C_x = code.decode_to_code(C_x_p)
        mask = C_x_p + C_x
        return key_p + mask
    except DecodingError:
        print("not in decoding capacity")
        return None

Rien de beaucoup plus complexe ici, on calcul d’abord \(C^{'}(x)\), puis on essaie de le corriger. On triche un peu pour obtenir un masque des bits à changer mais c’est juste une façon de récupérer un masque de nos erreurs, et on applique ensuite ce masque à la clé que l’on tente de corriger. Notons également que si nous ne sommes pas dans les capacités de correction de notre code, alors on sait que l’on ne peut pas récupérer la clé.

Et tada, sans jamais communiquer \(key\) (la clé d’\(Alice\)), on a réussi à la récupérer à partir de \(key^{'}\) (la clé de \(Bob\)).

Limitations

Avant de crier victoire trop vite, notons tout de même que deviner \(key_{A}\) à partir de notre \(sketch\) revient en réalité à deviner \(x\), car si nous avons \(x\) et les paramètres du code utilisé (qui ne sont pas supposés inconnus, et sont plutôt facile à deviner au besoin) alors trouver \(x\) nous donne \(C(x)\), et donné \(C(x)\) et \(sketch\) on a \(key\). Dans notre cas, il suffit donc d’avoir un message chiffré avec la clé réconciliée et \(sketch\) pour s’assurer de retrouver \(key\) si l’on devine \(x\), on doit donc deviner seulement 63 bits. Je fais avant tout cet article pour présenter une construction que je trouve intéressante mais il n’est certainement pas à prendre comme un “tutoriel”. Si vous souhaitez pousser un peu plus, je vous invite à lire les articles mentionnés au long du post.

Dans notre configuration (N=255, t=30), il nous reste une entropie de 63 bits pour x. C’est très bien pour notre PoC, mais une sécurité de 63 bits ça se pète avec suffisament de GPU… Pour une application réelle, il faudrait soit réduire la tolérance aux erreurs (diminuer t) pour augmenter la taille de x, soit utiliser des clés plus longues (par exemple sur 511 ou 1023 bits).

Merci pour votre lecture, si vous avez des remarques, n’hésitez pas à me contacter par mail (codeberg-contact.ventricle108@passmail.net)!

Code Source

Tout le code source utilisé pour ce petit post est disponible ici