Détails
- Catégorie : crypto
- Points : 256
- Résolutions : 30
Description
“In this challenge, you have access to a signing oracle. Good luck!”
nc tonality.2021.ctfcompetition.com 1337
Fichiers sources :
$ ls -l
total 52
-rw-r--r-- 1 enoent enoent 12310 nov. 30 1979 challenge_pb2.py
-rw-r--r-- 1 enoent enoent 18227 nov. 30 1979 challenge.pb.go
-rw-r--r-- 1 enoent enoent 1072 nov. 30 1979 challenge.proto
-rw-r--r-- 1 enoent enoent 2428 nov. 30 1979 challenger.go
-rw-r--r-- 1 enoent enoent 2169 nov. 30 1979 client_skel.py
-rw-r--r-- 1 enoent enoent 3587 nov. 30 1979 server.go
Comprendre le problème
Lorsque nous nous connectons au serveur, nous sommes accueillis par ce message :
$ nc tonality.2021.ctfcompetition.com 1337
== proof-of-work: disabled ==
l
Server says 1+1=2Server says 1+1=3�D
dN<����UOB���q���Q&�ѕq �2��X�:<�;�nށ��Ŏm�_�v��zB���
Cela semble très étrange. Nous devrons examiner le code source fourni pour comprendre ce qui se passe.
Il y a beaucoup de fichiers sources pour un challenge de crypto. Certains d’entre eux sont écrits en Go (c’est le CTF de Google après tout) et d’autres en Python.
Tous ne sont pas intéressants, nous allons donc nous concentrer sur les principaux.
Le fichier server.go
est le point d’entrée du serveur :
// Copyright 2021 Google LLC
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
package main
import (
"crypto-tonality/challenger"
"crypto-tonality/pb"
"encoding/binary"
"flag"
"fmt"
"io"
"io/ioutil"
"os"
"strings"
"github.com/golang/protobuf/proto"
)
var flagFile string
const maxMessageLengh = 10 * 1024 * 1024
func writeMessage(w io.Writer, m proto.Message) error {
if err := binary.Write(w, binary.LittleEndian, uint32(proto.Size(m))); err != nil {
return fmt.Errorf("failed to write message length, binary.Write() = %v, want nil err", err)
}
, err := proto.Marshal(m)
bufif err != nil {
return fmt.Errorf("failed to serialize message, proto.Marshal(%v) = %v, want nil err", m, err)
}
, err := w.Write(buf)
nif n != len(buf) || err != nil {
return fmt.Errorf("failed to write serialized message, w.Write(%X) = %v, %v, want n=%d and nil error", buf, n, err, len(buf))
}
return nil
}
func readMessage(r io.Reader, m proto.Message) error {
var length uint32
if err := binary.Read(r, binary.LittleEndian, &length); err != nil {
return fmt.Errorf("failed to read length, binary.Read(buf) = %v, want nil error", err)
}
if length > maxMessageLengh {
return fmt.Errorf("want legnth <= %d, got %d", maxMessageLengh, length)
}
:= make([]byte, length)
buf if n, err := r.Read(buf); n != len(buf) || err != nil {
return fmt.Errorf("failed to read serialized message, r.Read(buf) = %v, %v, want n=%d and nil error", n, err, len(buf))
}
if err := proto.Unmarshal(buf, m); err != nil {
return fmt.Errorf("failed to unmarshal message, proto.Unmarshal(%X, m) = %v, want nil error", buf, err)
}
return nil
}
func runSession(chal *challenger.Challenger, r io.Reader, w io.Writer) error {
:= chal.Hello(&pb.HelloRequest{})
hello if err := writeMessage(w, hello); err != nil {
return fmt.Errorf("writeMessage(w, hello=%X)=%v, want nil err", hello, err)
}
:= &pb.SignRequest{}
signReq if err := readMessage(r, signReq); err != nil {
return fmt.Errorf("readMessage(r, signReq)=%v, want nil err", err)
}
:= chal.SignFirstMessage(signReq)
signRes if err := writeMessage(w, signRes); err != nil {
return fmt.Errorf("writeMessage(w, signRes=%X)=%v, want nil err", signRes, err)
}
:= &pb.VerifyRequest{}
verifyReq if err := readMessage(r, verifyReq); err != nil {
return fmt.Errorf("readMessage(r, verifyReq)=%v, want nil err", err)
}
:= chal.VerifySecondMessage(verifyReq)
verifyRes if err := writeMessage(w, verifyRes); err != nil {
return fmt.Errorf("writeMessage(w, verifyRes=%X)=%v, want nil err", verifyRes, err)
}
return nil
}
func init() {
.StringVar(&flagFile, "flag", "/flag", "flag filename")
flag}
func main() {
defer func() {
if r := recover(); r != nil {
// Uncomment to catch panics during development.
// panic(r)
}
}()
.Parse()
flag
, err := ioutil.ReadFile(flagFile)
fif err != nil {
panic(err)
}
, err := challenger.NewChallenger(strings.TrimSpace(string(f)))
chalif err != nil {
panic(err)
}
= runSession(chal, os.Stdin, os.Stdout)
err if err != nil {
panic(err)
}
}
Il fait appel aux fonctions définies dans challenger.go
:
// Copyright 2021 Google LLC
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
package challenger
import (
"crypto-tonality/pb"
"crypto/ecdsa"
"crypto/elliptic"
"crypto/rand"
"crypto/sha1"
"io"
"math/big"
)
const m0 = "Server says 1+1=2"
const m1 = "Server says 1+1=3"
func hashMessage(m string) []byte {
:= sha1.New()
h .WriteString(h, m)
ioreturn h.Sum(nil)
}
type Challenger struct {
string
flag *ecdsa.PrivateKey
sk }
func NewChallenger(flag string) (*Challenger, error) {
, err := ecdsa.GenerateKey(elliptic.P256(), rand.Reader)
skif err != nil {
return nil, err
}
return &Challenger{
: flag,
flag: sk,
sk}, nil
}
func (chal *Challenger) Hello(req *pb.HelloRequest) *pb.HelloResponse {
return &pb.HelloResponse{
: m0,
Message0: m1,
Message1: &pb.Point{
Pubkey: chal.sk.PublicKey.X.Bytes(),
X: chal.sk.PublicKey.Y.Bytes(),
Y},
}
}
func (chal *Challenger) scalePrivate(t *big.Int) *ecdsa.PrivateKey {
:= new(big.Int).Mul(chal.sk.D, t)
rk .Mod(rk, chal.sk.PublicKey.Curve.Params().N)
rk
:= new(ecdsa.PrivateKey)
ret .PublicKey.Curve = chal.sk.PublicKey.Curve
ret.D = rk
ret.PublicKey.X, ret.PublicKey.Y = chal.sk.PublicKey.Curve.ScalarBaseMult(ret.D.Bytes())
retreturn ret
}
func (chal *Challenger) SignFirstMessage(req *pb.SignRequest) *pb.SignResponse {
:= new(big.Int).SetBytes(req.Scalar)
t , s, err := ecdsa.Sign(rand.Reader, chal.scalePrivate(t), hashMessage(m0))
rif err != nil {
return &pb.SignResponse{}
}
return &pb.SignResponse{
: &pb.Signature{
Message0Sig: r.Bytes(),
R: s.Bytes(),
S},
}
}
func (chal *Challenger) VerifySecondMessage(req *pb.VerifyRequest) *pb.VerifyResponse {
:= new(big.Int).SetBytes(req.Message1Sig.R)
r := new(big.Int).SetBytes(req.Message1Sig.S)
s
:= ecdsa.Verify(&chal.sk.PublicKey, hashMessage(m1), r, s)
ok if !ok {
return &pb.VerifyResponse{}
}
return &pb.VerifyResponse{Flag: chal.flag}
}
En gros, ce qu’il fait, c’est :
- Générer une clé privée sur la courbe elliptique P-256
d
. - Envoyer une requête Hello contenant
- Deux messages fixes
m0
etm1
- La clé publique du serveur
(x, y)
.
- Deux messages fixes
- Attendre une demande de signature contenant :
- Un facteur d’échelle
t
- Un facteur d’échelle
- Envoyer la signature (
r0
,s0
) dem0
par la clé privéed*t
’. - Attendre une demande de vérification de signature contenant :
- La signature à vérifier
(r1, s1)
dem1
par la clé privéed
- La signature à vérifier
- Vérifier que
(r1, s1)
est valide en utilisant sa clé publique(x, y)
. - Si la signature est valide, envoyer le flag
Le serveur utilise protobuf pour envoyer les messages, ce qui explique la sortie étrange quand on se connecte directement en utilisant netcat.
Heureusement, un client Python est fourni dans client_skel.py
:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# Copyright 2021 Google LLC
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
# https://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.
import argparse
import pwnlib
import challenge_pb2
import struct
import sys
def handle_pow(tube):
raise NotImplemented()
def read_message(tube, typ):
= struct.unpack('<L', tube.recvnb(4))[0]
n = tube.recvnb(n)
buf = typ()
msg
msg.ParseFromString(buf)return msg
def write_message(tube, msg):
= msg.SerializeToString()
buf '<L', len(buf)))
tube.send(struct.pack(
tube.send(buf)
def main():
= argparse.ArgumentParser()
parser
parser.add_argument('--port', metavar='P', type=int, default=1337, help='challenge #port')
parser.add_argument('--host', metavar='H', type=str, default='tonality.2021.ctfcompetition.com', help='challenge host')
= parser.parse_args()
args
= pwnlib.tubes.remote.remote(args.host, args.port)
tube print(tube.recvuntil('== proof-of-work: '))
if tube.recvline().startswith(b'enabled'):
handle_pow(tube)
# Step 1: Hello.
= read_message(tube, challenge_pb2.HelloResponse)
hello print(hello)
# Step 2: Sign.
= 1234
a = challenge_pb2.SignRequest()
sign_req = a.to_bytes((a.bit_length() + 7) // 8, 'big')
sign_req.scalar
write_message(tube, sign_req)
= read_message(tube, challenge_pb2.SignResponse)
sign_res print(sign_res)
# Step 3: Verify.
= challenge_pb2.VerifyRequest()
verify_req = b'\x11\x22'
verify_req.message1_sig.r = b'\x33\x44'
verify_req.message1_sig.s
write_message(tube, verify_req)
= read_message(tube, challenge_pb2.VerifyResponse)
verify_res print(verify_res)
return 0
if __name__ == '__main__':
sys.exit(main())
Ce client envoie un facteur d’échelle t=1234
et ensuite envoie une demande de vérification factice.
Son exécution donne le résultat suivant :
$ python3 client_skel.py
b'== proof-of-work: '
message0: "Server says 1+1=2"
message1: "Server says 1+1=3"
pubkey {
x: "\325^\025\253[\323c(\020\260\017\216\221\332\305\375O\313\255K\252U\324\334\311\214\345\001\373\346\004\'"
y: "k\214\363h\357\254\224f\271\026\222\204\"/\301\245\027~\205\242\213[\353\004\265#\007_\356bP\270"
}
message0_sig {
r: "\206\254\371\260\212\204@\327JN\271\357\305\362O\3509\2177\032\234\371!\277\307\277$\251\310\n\244\336"
s: "\230 B\356c%\256\335\232+}\346;\271S=\361\002#\243\326\236#\326\202J\210\262+y\210)"
}
Le but du challenge est de forger une signature valide pour m1
connaissant une signature de m0
calculée en utilisant la clé privée du serveur mise à l’échelle par un facteur t
que nous contrôlons.
Résoudre le problème
D’après la définition de ECDSA, nous avons s0 = (r0*d*t + h0)*k^-1
, avec h0
étant le hash SHA-1 de m0
et k
le nonce aléatoire.
Voici l’astuce: si on définit h0 = t*h1
, l’équation ci-dessus devient s0 = (r0*d*t + t*h1)*k^-1 = t*(r0*d + h1)*k^-1
.
Encore une fois, d’après la définition de ECDSA, cela peut être réécrit comme s0 = t*s1
, car (r0*d + h1)*k^-1
est la composante s
de la signature de m1
par la clé d
avec le même nonce k
(r0 = (k*G).x
).
Donc, pour forger une signature valide pour m1
connaissant (r0, s0)
, il suffit d’envoyer (r0, s0*t^-1)
, avec t = h0*h1^-1
.
Implémentation de la solution
Nous devons d’abord calculer t
et t^-1
. Pour cela, nous devons travailler modulo l’ordre du générateur de la courbe P-256 :
import gmpy2
from Crypto.Hash import SHA1
# order of the generator of P-256
# https://neuromancer.sk/std/secg/secp256r1
= 0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551
n
= b"Server says 1+1=2"
m0 = b"Server says 1+1=3"
m1
= int(SHA1.new(m0).hexdigest(), 16)
h0 = int(SHA1.new(m1).hexdigest(), 16)
h1
= int((h0 * gmpy2.invert(h1, n)) % n)
t = int(gmpy2.invert(t, n))
t_inv
print(f"{t = }")
print(f"{t_inv = }")
Ce qui nous donne :
= 13325888469672337108611681934270644951924450129063937690100547119146820540863
t = 79606180523211936313941056796648868354970640032974922105651641315498916037346 t_inv
Maintenant nous pouvons modifier légèrement le client fourni pour envoyer notre facteur d’échelle t
et demander de vérifier la signature forgée (r0, s0*t^-1)
:
def main():
#...
# order of the generator of P-256
# https://neuromancer.sk/std/secg/secp256r1
= 0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551
n
# Step 2: Sign.
= 13325888469672337108611681934270644951924450129063937690100547119146820540863
t = challenge_pb2.SignRequest()
sign_req = t.to_bytes((t.bit_length() + 7) // 8, 'big')
sign_req.scalar
write_message(tube, sign_req)
= read_message(tube, challenge_pb2.SignResponse)
sign_res = sign_res.message0_sig.r
r = sign_res.message0_sig.s
s print(f"{sign_res.message0_sig.r.hex()=}")
print(f"{sign_res.message0_sig.s.hex()=}")
= 79606180523211936313941056796648868354970640032974922105651641315498916037346
t_inv from Crypto.Util.number import bytes_to_long, long_to_bytes
= (bytes_to_long(s)*t_inv) % n
sn = long_to_bytes(sn)
s
# Step 3: Verify.
= challenge_pb2.VerifyRequest()
verify_req = r
verify_req.message1_sig.r = s
verify_req.message1_sig.s
write_message(tube, verify_req)
= read_message(tube, challenge_pb2.VerifyResponse)
verify_res print(verify_res)
L’exécution du script ci-dessus nous donne le flag :
$ python3 client_skel.py
b'== proof-of-work: '
hello.pubkey.x.hex()='ed7182459e761b4b9a3be2a8a403aed8afd2cd4c1caa76f49a0fe995102dfa15'
hello.pubkey.y.hex()='927afecd316004896fac6a544819a2bd283a6f3283538351a582e1c1792126c3'
sign_res.message0_sig.r.hex()='ff65a051354f432949455aab0f21fd76a1fece8a76c44e04456fc0a4d16ff278'
sign_res.message0_sig.s.hex()='028ae229b3b0ceee5ac6be2af978a16e88ff1235586a58b91af99f8d8194da5a'
flag: "CTF{TheySayTheEmptyCanRattlesTheMost}"
Flag : CTF{TheySayTheEmptyCanRattlesTheMost}
Réflexions postérieures
Après la fin du CTF, les sources du challenge ont été publiées.
L’attaque est en fait une attaque par clé privée connexe, qui est décrite au chapitre 4.2 de cet article.
On ne sait toujours pas ce que le nom du challenge ou le contenu du flag sont censés signifier.