collusion.md

Collusion

For this challenge we are given a go program and json payloads.

message.json

{
 "V":584221881758507213769903010020339815950057645818648920364983549601225341062365062520391665711126204114735381305339677935863870281557078300036090892608892021129276590502981260857531205402850896018739268436262147451812156349860568744247316332461855247671922521643140703633415753776548859345314133294397634741631,
 "Nonce":"2NXgQhueKbVm5Pd8",
 "Body":"0ZWAaAxvazGfyTJSRPkyeHU9ZUSWSoWFObggHmmfb835TWFAzA=="
}

bobs-key.json

{
  "N":620887747698031680282278459418853751800768044276786350910455457327697386307992399290465847519812877907840137497935973466569696906188829328481045481062835414724706348319327533678662137243078740689059557633186372578973734559506901939700830250898600687716678884072023222665290974338233795503284024757704681902513,
  "D":533470860187977428874664770749404286395369594882914913229314502136395302372814852272450839649881108562946368861816140387784087275639561655065952799932016774771032557950682169220669553278027305664591294664780571771444011952670173545687132460199094202220018835973570943657523151658594651454700759087609204840601
}

carols-key.json

{
  "N":620887747698031680282278459418853751800768044276786350910455457327697386307992399290465847519812877907840137497935973466569696906188829328481045481062835414724706348319327533678662137243078740689059557633186372578973734559506901939700830250898600687716678884072023222665290974338233795503284024757704681902513,
  "D":465067931136600975748708204542464514380024325025535227883674632338749953227521580764857657167362578029849896066287943943434104585258069157493421521598078626985841741990663128952187029252332502950750816362532527813756399290358906777668719885727291165584927703512677443961502026513815615226146319193324416029571
}

Reading the program we see that V is used to encapsualte a symmetric key in the following manner.

V = 3^((n + x)r)
D = (n + x)^-1 (mod phi)
key = sha256(V^D) = sha256(3^r)

Meaning recovering 3^r will allow us to decrypt the flag in Body.

The n values are known since they are deterministically generated from the strings Alice, Bob and Carol respectively. Let's name these values na, nb and nc. Other known values are db = (nb + x)^-1 (mod phi) and dc = (nc + x)^-1 (mod phi).

One thing we notice is that, since we know the n values, their is a fixed offset between (na + x) and (nb + x) or (nc + x). And thus we can write

V^db = (3^(((nb + x) + (na-nb))r))^db = 3^((1 + (na-nb)db)r)

and

V^dc = (3^(((nc + x) + (na-nc))r))^dc = 3^((1 + (na-nc)dc)r).

This seems non trivial since we went from 3^(unknown*r) to 3^(known*r). We name these A and B and write V^db = 3^(A*r) and V^dc = 3^(B*r).

We got stuck here for a while but then we realized that if we were able to find x and y values such that x*A + y*B = 1 we would then be able to compute (3^(A*r))^x*(3^(B*r))^y = 3^(x*A + y*B)r = 3^r.

But this is exactly what the extended Euclidean algorithm gives us when A and B are coprimes and they are!

common.go

package main

import (
        "crypto/aes"
        "crypto/cipher"
        "crypto/rand"
        "crypto/sha256"
        "io"
        "math/big"
        "fmt"
        "encoding/hex"
)

func solve() {
        N, ok := new(big.Int).SetString("620887747698031680282278459418853751800768044276786350910455457327697386307992399290465847519812877907840137497935973466569696906188829328481045481062835414724706348319327533678662137243078740689059557633186372578973734559506901939700830250898600687716678884072023222665290974338233795503284024757704681902513", 10)
        if !ok {
                return
        }
        db, ok := new(big.Int).SetString("533470860187977428874664770749404286395369594882914913229314502136395302372814852272450839649881108562946368861816140387784087275639561655065952799932016774771032557950682169220669553278027305664591294664780571771444011952670173545687132460199094202220018835973570943657523151658594651454700759087609204840601", 10)
        if !ok {
                return
        }
        dc, ok := new(big.Int).SetString("465067931136600975748708204542464514380024325025535227883674632338749953227521580764857657167362578029849896066287943943434104585258069157493421521598078626985841741990663128952187029252332502950750816362532527813756399290358906777668719885727291165584927703512677443961502026513815615226146319193324416029571", 10)
        if !ok {
                return
        }
        v, ok := new(big.Int).SetString("584221881758507213769903010020339815950057645818648920364983549601225341062365062520391665711126204114735381305339677935863870281557078300036090892608892021129276590502981260857531205402850896018739268436262147451812156349860568744247316332461855247671922521643140703633415753776548859345314133294397634741631", 10)
        if !ok {
                return
        }
          nb, err := DecrypterId("Bob", N)
        if err != nil {
                return
        }
        nc, err := DecrypterId("Carol", N)
        if err != nil {
                return
        }
        na, err := DecrypterId("Alice", N)
        if err != nil {
                return
        }

        A := big.NewInt(1)
        A = A.Add(A, new(big.Int).Mul(na, db)).Sub(A, new(big.Int).Mul(nb, db))

        // go xgcd does not account for negative A or B, *-1 the input *-1 the output
        B := big.NewInt(1)
        B.Add(B, new(big.Int).Mul(na, dc)).Sub(B, new(big.Int).Mul(nc, dc)).Neg(B)
        x := new(big.Int)
        y := new(big.Int)
        new(big.Int).GCD(x, y, A, B)
        y.Neg(y)

        K := new(big.Int)
        K.Mul(new(big.Int).Exp(v, new(big.Int).Mul(db, x), N), new(big.Int).Exp(v, new(big.Int).Mul(dc, y), N)).Mod(K, N)

        shared := sha256.Sum256(K.Bytes())
        ct, _ := hex.DecodeString("d19580680c6f6b319fc9325244f93278753d6544964a858539b8201e699f6fcdf94d6140cc")
        pt := Decrypt(shared[:], ct)
        fmt.Printf(string(pt))
        fmt.Printf("\n")
}


func Decrypt(key, ciphertext []byte) []byte {
        nonce, _ := hex.DecodeString("d8d5e0421b9e29b566e4f77c")
        block, err := aes.NewCipher(key)
        if err != nil {
                panic(err.Error())
        }

        aesgcm, err := cipher.NewGCM(block)
        if err != nil {
                panic(err.Error())
        }

        plaintext, err := aesgcm.Open(nil, nonce, ciphertext, nil)
        if err != nil {
                panic(err.Error())
        }
        return plaintext
}


type devZero struct{}

func (dz devZero) Read(p []byte) (n int, err error) {
        for i := 0; i < len(p); i++ {
                p[i] = 0
        }
        return len(p), nil
}

// newReader returns a deterministic, cryptographically-secure source of random
// bytes seeded by `seed`.
func newReader(seed string) (io.Reader, error) {
        sum := sha256.Sum256([]byte(seed))
        block, err := aes.NewCipher(sum[:])
        if err != nil {
                return nil, err
        }

        iv := make([]byte, block.BlockSize())
        return cipher.StreamReader{
                S: cipher.NewCTR(block, iv),
                R: devZero{},
        }, nil
}

// DecrypterId deterministically maps a name to an integer modulo N.
func DecrypterId(id string, N *big.Int) (*big.Int, error) {
        r, err := newReader(id)
        if err != nil {
                return nil, err
        }
        n, err := rand.Int(r, N)
        if err != nil {
                return nil, err
        }
        n.SetBit(n, 0, 1) // odd

        return n, nil
}

// phi returns Phi(N = p * q), where Phi is Euler's totient function.
func phi(p, q *big.Int) *big.Int {
        one := big.NewInt(1)

        a := new(big.Int).Sub(p, one)
        b := new(big.Int).Sub(q, one)

        return a.Mul(a, b)
}


// generateSafe generates a safe prime p=2q+1 where q is another prime.
//
// THIS FUNCTION IS VERY SLOW!
func generateSafe(src io.Reader, bits int) (*big.Int, error) {
        const level = 20
        var (
                one = big.NewInt(1)

                p    = new(big.Int)
                temp = new(big.Int)

                err error
        )

        for {
                p, err = rand.Prime(src, bits)
                if err != nil {
                        return nil, err
                }

                // Check if 2p+1 is prime.
                temp.Lsh(p, 1)
                temp.Add(temp, one)

                if temp.Bit(0) != 0 && temp.ProbablyPrime(level) {
                        return temp, nil
                }

                // Check if (p-1)/2 is also prime.
                temp.Sub(p, one)
                temp.Rsh(temp, 1)

                if temp.Bit(0) != 0 && temp.ProbablyPrime(level) {
                        return p, nil
                }
        }
}

// Group is the group manager's private key. The group manager is capable of
// issuing decrypters' private key.
type Group struct {
        P, Q *big.Int
        X    *big.Int
}

func NewGroup(src io.Reader, bits int) (*Group, error) {
        p, err := generateSafe(src, bits/2)
        if err != nil {
                return nil, err
        }
        q, err := generateSafe(src, bits/2)
        if err != nil {
                return nil, err
        }

        x, err := rand.Int(src, phi(p, q))
        if err != nil {
                return nil, err
        }
        x.SetBit(x, 0, 0) //even

        return &Group{p, q, x}, nil
}

unc (g *Group) Encrypter() *Encrypter {
        N := new(big.Int).Mul(g.P, g.Q)

        H := big.NewInt(3)
        H.Exp(H, g.X, N)

        return &Encrypter{N, H}
}

func (g *Group) Decrypter(id string) (*Decrypter, error) {
        N := new(big.Int).Mul(g.P, g.Q)

        n, err := DecrypterId(id, N)
        if err != nil {
                return nil, err
        }
        phiN := phi(g.P, g.Q)
        d := new(big.Int).Add(g.X, n)
        d.Mod(d, phiN).ModInverse(d, phiN)

        return &Decrypter{N, d}, nil
}


// Encrypter is a public key, used to encrypt messages to the set of decrypters.
type Encrypter struct {
        N *big.Int // N is the RSA modulus.
        H *big.Int // H is g^x (mod N), where g is a generator of (Z/NZ)* and x is the group manager's secret scalar.
}

// GenerateKey takes a random source as input and the identity of the recipient;
// it outputs the public KEM value and the shared secret.
func (e *Encrypter) GenerateKey(src io.Reader, id string) (*big.Int, []byte, error) {
        n, err := DecrypterId(id, e.N)
        if err != nil {
                return nil, nil, err
        }
        r, err := rand.Int(src, e.N)
        if err != nil {
                return nil, nil, err
        }

        V := big.NewInt(3)
        V.Exp(V, n, e.N).Mul(V, e.H).Mod(V, e.N).Exp(V, r, e.N)

        K := big.NewInt(3)
        K.Exp(K, r, e.N)
        shared := sha256.Sum256(K.Bytes())

        return V, shared[:], nil
}

// Decrypter is a decrypter's private key.
type Decrypter struct {
        N *big.Int // N is the RSA modulus.
        D *big.Int // D is the decrypter's private exponent.
}

// RecoverKey takes a public KEM value as input and outputs the shared secret.
func (d *Decrypter) RecoverKey(V *big.Int) []byte {
        K := new(big.Int).Exp(V, d.D, d.N)
        shared := sha256.Sum256(K.Bytes())
        return shared[:]
}

// Payload is a public-key encrypted message.
type Payload struct {
        V     *big.Int
        Nonce []byte
        Body  []byte
}

func Encrypt(e *Encrypter, recipient, message string) (*Payload, error) {
        V, shared, err := e.GenerateKey(rand.Reader, recipient)
        if err != nil {
                return nil, err
        }

        block, err := aes.NewCipher(shared)
        if err != nil {
                return nil, err
        }
        nonce := make([]byte, 12)
        if _, err := io.ReadFull(rand.Reader, nonce); err != nil {
                return nil, err
        }
        ciph, err := cipher.NewGCM(block)
        if err != nil {
                return nil, err
        }
        body := ciph.Seal(nil, nonce, []byte(message), nil)

        return &Payload{V, nonce, body}, nil
}

generate_challenge.go

package main

import (
        "crypto/rand"
        "encoding/json"
        "io/ioutil"
        "log"
)

func main() {
        log.SetFlags(log.LstdFlags | log.Lshortfile)

        g, err := NewGroup(rand.Reader, 1024)
        if err != nil {
                log.Fatal(err)
        }
        e := g.Encrypter()

        if err := saveToFile("encrypter.json", e); err != nil {
                log.Fatal(err)
        }

        payload, err := Encrypt(e, "Alice", "flag{someflag}")
        if err != nil {
                log.Fatal(err)
        } else if err := saveToFile("message.json", payload); err != nil {
                log.Fatal(err)
        }

        dB, err := g.Decrypter("Bob")
        if err != nil {
                log.Fatal(err)
        } else if err := saveToFile("bobs-key.json", dB); err != nil {
                log.Fatal(err)
        }

        dC, err := g.Decrypter("Carol")
        if err != nil {
                log.Fatal(err)
        } else if err := saveToFile("carols-key.json", dC); err != nil {
                log.Fatal(err)
        }
}

// saveToFile json-encodes x and writes to a file with the given name.
func saveToFile(name string, x interface{}) error {
        raw, err := json.Marshal(x)
        if err != nil {
                return err
        }
        return ioutil.WriteFile(name, raw, 0777)
}