Analyse du challenge
La première étape est de regarder le code…
Une fois qu’on la zyeuté je suis passé à l’exécution à la main du programme pour une entrée de ‘1000000’.
Autrement dit pour
echo -n '\x80' > flag.txt && go run ./convolu-quoi.go
On réalise que pour chaque bit en entrée on va générer deux bits dans res. Que le premier bit détermine les deux premiers bit de res, les deux premiers déterminent les deux suivants…
Donc on peut le résoudre en reconstruisant progressivement la séquence en entrée.
Résolution
On va prendre la chaîne de bits encodée et la décoder progressivement.
On prend les bits deux par deux, on détermine si le bit en entrée était 0 ou 1, puis on passe aux deux bits d’après…
Concrètement j’ai fait ça avec une chaîne de charactères que je controllais avant de le faire pour le flag.
Le script final que j’ai lancé avec
echo -n 'FCSC{fake_flag}' > flag.txt && go run ./convolu-quoi.go
On se moque du FCSC{fake_flag}, il était juste là pour que je contrôle ce qu’il se passait, je l’ai laissé puisque je trouvais que ça montrait plus fidèlement le processus de réflexion
package main
import (
"fmt"
"os"
)
func parity(b uint8) uint8 {
b ^= (b >> 4)
b ^= (b >> 2)
b ^= (b >> 1)
return (b & 1)
}
func convolve(sequence []uint8, G0, G1 uint8) []uint8 {
res := make([]uint8, 0)
var state uint8 = 0
for _, bit := range sequence {
state = (state << 1) | bit
res = append(res, parity(state&G0))
res = append(res, parity(state&G1))
}
for range 4 {
state = (state << 1)
res = append(res, parity(state&G0))
res = append(res, parity(state&G1))
}
return res
}
func deconvolve(encoded []uint8, G0, G1 uint8) []uint8 {
res := make([]uint8, 0)
var state uint8 = 0
for i, bit := range encoded {
if i%2 == 1 {
continue
}
attempt := (state << 1)
if parity(attempt&G0) != bit {
attempt |= 1
}
if parity(attempt&G1) != encoded[i+1] {
attempt |= 1
}
res = append(res, (attempt & 1))
state = attempt
}
return res
}
func convertAsBits(sequence []uint8) []uint8 {
res := make([]uint8, 0)
for _, b := range sequence {
for i := range 8 {
bit := (b >> (7 - i)) & 1
res = append(res, uint8(bit))
}
}
return res
}
func decodeFromBits(bits []uint8) []uint8 {
res := make([]uint8, 0)
for i := 0; i < len(bits); i += 8 {
var b uint8 = 0
for j := range 8 {
b |= (bits[i+j] << (7 - j))
}
res = append(res, b)
}
return res
}
func main() {
attempt, _ := os.ReadFile("flag.txt")
bitSequence := convertAsBits(attempt)
fmt.Printf("Original attempt (as bits): ")
for _, b := range bitSequence {
fmt.Printf("%d", b)
}
fmt.Printf("\n")
var G0 uint8 = 0x19 // X**4 + X**3 + 1
var G1 uint8 = 0x1B // X**4 + X**3 + X +1
result := convolve(bitSequence, G0, G1)
fmt.Printf("Encoded attempt: ")
for _, b := range result {
fmt.Printf("%d", b)
}
fmt.Printf("\n")
decon := deconvolve(result, G0, G1)
fmt.Printf("Decoded attempt (as bits): ")
for _, b := range decon {
fmt.Printf("%d", b)
}
fmt.Printf("\n")
decodedSeq := decodeFromBits(decon[:len(decon)-4])
fmt.Printf("Decoded attempt: %s\n", string(decodedSeq))
// Encoded flag: 00110100110010011111100011111110010001001011000101000111111111100100100101011110100001001011000101000111111111100111110101000111110010101000111000001011011011111011100001010110011101001011111100001110011100110011100100101011000010100101001110111011000110100011010100100101011101110001010001001000101100010100010001010110011101111111110100000110101101001000100010001011110001110101011001110111111111100111110101110011001110010010011000111011100001101111100000011001011110100010101100001010101101001000100010001011111111100111000001000001011100110011100100100110001101011100111101110110001010110000011101010110011101111111111001000111000110010111011111000100111111100111110101111101010001001000100001010110010011010100011111001010100011100000100011000111100010000101011001110111000110100000001001110011001110101011011111000111010101100111010010001011110010010001111111001110010001111100011110001011110001110101011001110111001000111100111001000111110010101000111000001000110001001100101001100111011111111101111011111100
encodedFlagStr := "00110100110010011111100011111110010001001011000101000111111111100100100101011110100001001011000101000111111111100111110101000111110010101000111000001011011011111011100001010110011101001011111100001110011100110011100100101011000010100101001110111011000110100011010100100101011101110001010001001000101100010100010001010110011101111111110100000110101101001000100010001011110001110101011001110111111111100111110101110011001110010010011000111011100001101111100000011001011110100010101100001010101101001000100010001011111111100111000001000001011100110011100100100110001101011100111101110110001010110000011101010110011101111111111001000111000110010111011111000100111111100111110101111101010001001000100001010110010011010100011111001010100011100000100011000111100010000101011001110111000110100000001001110011001110101011011111000111010101100111010010001011110010010001111111001110010001111100011110001011110001110101011001110111001000111100111001000111110010101000111000001000110001001100101001100111011111111101111011111100"
encodedFlag := make([]uint8, 0)
for _, c := range encodedFlagStr {
if c == '0' {
encodedFlag = append(encodedFlag, 0)
} else {
encodedFlag = append(encodedFlag, 1)
}
}
fmt.Printf("Encoded flag (as bits): ")
for _, b := range encodedFlag {
fmt.Printf("%d", b)
}
fmt.Printf("\n")
deconFlag := deconvolve(encodedFlag, G0, G1)
fmt.Printf("Decoded flag (as bits): ")
for _, b := range deconFlag {
fmt.Printf("%d", b)
}
fmt.Printf("\n")
decodedFlag := decodeFromBits(deconFlag[:len(deconFlag)-4])
fmt.Printf("Decoded flag from encoded string: %s\n", string(decodedFlag))
}