Skip to content

Attaque mathématique des codes Bixi (vélo libre-service)

J’étais au centre ville aujourd’hui et j’avais affaire pas très loin. Au lieu d’utiliser le métro, j’ai loué un Bixi, vélo en libre service. J’ai été surpris de constater que les codes Bixi ne comporte que 3 chiffres, sur 5 caractères, soit 3^5=243 codes possibles.

Billet bixi portant le code 21213

Billet bixi portant le code 21213

Ça semble bien peu, mais si les codes ne sont utilisables qu’au point de service où ils sont émis, et pour une durée limitée, avec peut-être une détection d’attaque en force brute, on devrais pouvoir dormir tranquille…

Je me suis rappellé une attaque mathémaitque sur des codes de ce genre. Avec une location de 24 heures à 5$, on peut prendre et remettre le vélo plusieurs fois, histoire de tester la théorie… Bonne nouvelle, Bixi n’est pas vulnérable. Mais j’écris quand même la démarche, c’est trop rare qu’on a l’occasion d’utiliser des math pour (tenter de) contourner les règles d’un système.

La vulnérabilité apparais lorsque l’implémentation utilise une fenêtre coulissante pour vérifier les codes entrés. Cette attaque a déjà été utilisée pour dévérouiller une porte de voiture à combinaison.

Pour les Bixi, les chiffres du codes de dévérouillage de vélo peuvent être 1, 2 ou 3. Le dictionnaire des valeurs possibles à une taille k=3. Il faut entrer 5 chiffres, on dit que n=5. Avec ces variables, une fenêtre coulissante fonctionne comme ceci :

  1. On entre n chiffres (par exemple 12222)
  2. Ce ne sera pas le bon code
  3. On entre un chiffre supplémentaire, disons 3
  4. Pour accomoder le chiffre supplémentaire, l’implémentation décale les chiffres déjà entrés pour faire de la place. Dans notre exemple, c’est le 1 qui disparaît à gauche à la faveur du 3 à droite.
  5. L’implémentation vérifie le nouveau code dans la fenêtre, soit 22223.

On réussi ainsi à tester 2 codes en ne saisissant que 6 chiffres, au lieu de 10. Et ainsi de suite, à chaque fois qu’on ajoute un seul chiffre, on se trouve à tester un nouveau code de 5 chiffres. La première étape ne sert qu’à initialiser le processus, sans affecter la complexité de l’attaque.

C’est une vielle idée. Un mathématicien Hollandais, Nicolaas Govert de Bruijn, a formalisé une séquence de chiffres dans laquelle n’importe quelle séquence de n chiffres n’apparait qu’une seule fois. Autrement dit, si vous générez une séquence de Bruijn avec k=3 et n=5 (les codes Bixi) et que vous y cherchez votre code Bixi, il n’y sera qu’une seule fois. C’est la façon la plus optimale d’attaquer un système de codes comme celui de Bruijn.

Voici la séquence dans l’ordre. Elle se lit de gauche à droite, de haut en bas. 1111121111311…… Le 1111 de la fin de la séquence est en fait les premiers chiffres qui se répêtent.

11111 21111 31112 21112 31113 21113 31121 21121 31122 21122
31123 21123 31131 21131 31132 21132 31133 21133 31212 21212
31213 21213 31221 31222 21222 31223 21223 31231 31232 21232
31233 21233 31313 21313 31322 21322 31323 21323 31332 21332
31333 21333 32222 23222 33223 23223 33232 33233 33311 11

La protection contre cette attaque est heureusement toute simple : à l’étape 2, effacer tous les chiffres et en redemander n autres. C’est ce qu’on fait les designers de Bixi. L’histoire ne dit pas s’ils connaissaient l’attaque, ou s’ils ont été chanceux… Au moins il pourrons dire qu’il m’ont fais marcher et pédaler !

3 Comments

  1. cyruscode wrote:

    Très intéressant comme analyse de la sécurité du système!

    Wednesday, June 24, 2009 at 16:49 | Permalink
  2. Pierre-Luc wrote:

    Ça aurait été niaiseux de ne pas prendre tous les 5 chiffres d’un coup…

    Déjà là, quelqu’un avec TROP de patience peut entrer 245 combinaisons pour essayer d’en débloquer là.

    Mais sérieux, rendu là, il l’aura presque mérité…!

    Guillaume Reply:

    Oui, assez niaiseux. Mais c’est déjà arrivé pour des voitures (voir lien dans le texte).

    En moyenne, il faudra entrer 122 codes (610 chiffres) pour trouver le bon. A 5 secondes chaque, c’est 10 minutes, 20 minutes max.

    Mais le pattern d’attaque en force brute est si facile à détecter… Je me demande ce qui a été programmé dans le truc. J’aurais fais ceci :
    * N’accepter des codes que si on en a émis qui n’ont pas été utilisés
    * Après un certain nombre d’essais infructueux, ne plus accepter les codes de ce clavier pour x minutes
    * Ainsi de suite pour chaque clavier
    * Envoyer une alerte au centre opérationnel Bixi et journaliser l’utilisateur présumé (en respectant la norme PCI, bien sur).

    Ne pas accepter veut dire : laisser l’utilisateur entrer des codes, mais toujours les refuser, même s’il finit par tomber sur le bon code a force d’essayer.

    Bon été à vélo !

    Wednesday, July 8, 2009 at 11:14 | Permalink
  3. iWoo wrote:

    Je suis pas doué pour les mathématiques, mais votre analyse et la séquence de Bruijn sont très intéressant! I believe the codes are indeed only usable for 3 or 5 minutes after it is given. However, the main reason that makes brute force attack impractical is that ten minutes is still too long. They may not need to program brute force detection, because they can just refuse all code entry until the station gives a code to someone renting.

    I believe each code is only valid for 3 minutes at the same station it is given at; and only when someone rents a BIXI by credit card. You would have to enter the correct code and take a bike in the 30 seconds before they are able to. Bonne chance!

    Someone also brought up the worry that BIXI member codes are easily guessed; they are 7 digits, allowing 0-9. They are not random at all. It seems they are just 1000000 + the number of subscribers + 1 (you).

    However, as far as I can tell, the only time this number is currently used is in gaining an extra 15 minutes free at a station with no available docks. You would identify yourself with your member number or credit card, depending on if you are subscriber or not. In this case, nothing is gained if you use someone else’s number; if they happen to be on a BIXI, they may gain 15 minutes before they get charged. You, however, still have the same 30-minute free period!

    Je suis désolé pour ecrire en anglais sur un blog français. J’ai étudié français un peu, mais pas encore assez pour m’expliquer bien…et surtout, assez rapidement!

    Guillaume Reply:

    Merci, ne t’en fais pas pour l’anglais, I usually posts in english anyway…

    You are right, brute force protection is pretty much built-in. I hear they have some physical security problems, with damaged bike racks. But the good news is that rollout of new bikes is still going strong !

    Thursday, July 9, 2009 at 10:54 | Permalink