Principe:
Construire un système de redondance par parité pour trouver un bit inversé dans un secret
Le challenge
Oui, j'ai oublié de screener le descriptif du challenge, donc, je vous spoil un morceau du flag. Mais les fichiers du challenge sont disponibles ici .
Ignorer le mensonge pour commencer
Le principe du code PHP est d'envoyer un message composé que de "0" sauf pour un seul bit: si le serveur répond "1", c'est que ce bit est à "1" (car le serveur fait un & binaire avec le secret avant de nous dire si le nombre de "1" du résultat est impair), sinon, il est à 0
Redondance
On dispose de quelques essais en plus, qui vont servir à déterminer le bit "menti" par dichotomie: le PHP affiche maintenant la valeur SECRET qu'il a déterminée, et il tente de savoir quel bit est inversé (j'ai forcé le secret à 0, et le mensonge au 1er bit pour tester)
On envoie un payload de 64 "0" suivit de 64 "1": si la parité retournée correspond à celle qu'on a (Parity Matches), alors le mensonge est sur les bits "0" (l'un des 64 premiers), sinon, sur l'un des 64 derniers
Après ce premier payload, on a donc divisé par 2 les emplacements possibles du mensonges: on va réitérer les payloads jusqu'à n'avoir qu'un seul bit
Le second payload est une succession de 32 "0", puis 32 "1", puis 32 "0" puis 32 "1",…
Flag
FCSC{e055ea6ffd540907c52a34bef47cbf79758e6732af597d98c33aceade78979c5}
Un peu de détail
Voici un exemple sur 8 bits de l'algorithme, pour aider à la compréhension du système de parité. On rappelle que le serveur répond "1" s'il y a un nombre impair de "1" dans Message reçu par python &_binaire Secret, sauf dans 1 seul cas, où le serveur va mentir
Payload Secret Payload&Secret Théorie Réponse réelle
10000000 01100100 00000000 0 0
01000000 01100100 01000000 1 1
00100000 01100100 00100000 1 0 (mensonge)
00010000 01100100 00000000 0 0
00001000 01100100 00000000 0 0
00000100 01100100 00000100 1 1
00000010 01100100 00000000 0 0
00000001 01100100 00000000 0 0
11111111 01100100 01100100 1
00001111 01100100 00000100 1
00110011 01100100 00100000 1
01010101 01100100 01000100 0
Les 8 premiers payloads servent à trouver le secret
Le PHP reçoit d'abord: 0 1 0 0 0 1 0 0
Il en déduit le secret: 01000100
Il ne sait pas quel bit est mensonger
Les 4 derniers payloads servent à trouver le mensonge
PHP reçoit 1 1 1 0 en parités
PHP évalue les parités du secret qu'il a deviné
et les compare aux réponses du serveur
11111111 & 01000100 = 01000100 = 2x"1" = 0 vs 1 FAUX
00001111 & 01000100 = 00000100 = 1x"1" = 1 vs 1 OK
00110011 & 01000100 = 00000000 = 0x"1" = 0 vs 1 FAUX
01010101 & 01000100 = 01000100 = 2x"1" = 0 vs 0 OK
La première parité est fausse:
le mensonge se trouve dans l'une des 8 premières réponses du serveur
Donc, dans l'un des 8 bits du message secret récupéré
La seconde parité est juste:
le mensonge n'est pas dans les 4 "1" de 00001111
D'où les positions possibles du mensonge: 11110000
La 3e parité est fausse:
le mensonge est à la position d'un des "1" dans 00110011
D'où les positions possibles du mensonge:
11110000 & 00110011 = 00110000
La 4e parité est juste:
donc le mensonge n'est pas sur l'un des "1" dans 01010101
D'où les positions possibles du mensonge:
00110000 & inv(01010101) = 00110000 & 10101010 = 00100000
Le mensonge est donc en position 00100000
Il a eu lieu à la 3e réponse du serveur
On inverse le 3e bit du secret que PHP avait déduit
Le secret est donc 0 1 1 0 0 1 0 0