Capture the Coin — Cryptography Category Solutions
Capture the Coin — Cryptography Category Solutions
By Jake Craige, Max Mikhaylov, Jesse Posner
In the last post of the Capture the Coin competition series we will dive into the solutions for our cryptography challenges. Also, feel free to revisit our other write ups in the series for Trivia, Blockchain as well as the Competition and Prizes announcements.
AES Encryption Flaw
By Jake Craige
This challenge presents you with the output of an encryption and asks for the message that was encrypted (plaintext) as the solution. It was encrypted with Ruby as follows:
def encrypt(message)
require ‘openssl’
# Encrypt the message using random key+iv with AES-128-OFB
cipher = OpenSSL::Cipher.new(‘AES-128-OFB’).encrypt
random_key = cipher.random_key
cipher.key = random_key
random_iv = cipher.random_iv
cipher.iv = random_iv
ciphertext = cipher.update(message) + cipher.final
# Encrypt the IV with AES-128-ECB
simple_cipher = OpenSSL::Cipher.new(‘AES-128-ECB’).encrypt
simple_cipher.key = random_key
encrypted_iv = simple_cipher.update(random_iv) + simple_cipher.final
{
ciphertext: ciphertext.unpack(‘H*’).first,
encrypted_iv: encrypted_iv.unpack(‘H*’).first
}
end
If you have worked with AES before there are a few parts of this that may stand out to you.
First, it uses the Output Feedback (OFB) mode of operation as seen by usage of “AES-128-OFB” in the prompt. There isn’t anything wrong with this on its own, but the Cipher Block Chaining (CBC) and Counter (CTR) modes are more common and in practice, authenticated encryption (AE) like Galois/Counter Mode (GCM) should be used.
Next, we see that the IV is encrypted and uses the Electronic Codebook (ECB) mode. IVs are non-secret values and do not need to be encrypted. The security of the block cipher relies on them being random, but not secret. Furthermore, using ECB mode for encryption is never what you want. It is meant to serve as a building block for other modes, but should not be used as a mode on its own.
Block Ciphers & Modes
Let’s review what block ciphers and modes are, as they are key to solving this problem. A block cipher is a deterministic algorithm that accepts a fixed size secret key and plaintext as input and outputs a fixed size output, called a block. They are used for encryption which implies they also have a decryption operation that accepts the key and ciphertext and returns the plaintext.
A block cipher on its own is not secure for encrypting more than one message because encrypting the same message twice would result in the same ciphertext, put another way, a block cipher is deterministic.
Why is this a problem? Let’s say an army sends the message “Attack at dawn” one day and their adversary figures it out. On another day, if the army sends the same message and the adversary is watching, the will know that an attack is imminent and can set up defenses.
Formally, we say that a block cipher is not IND-CPA secure (indistinguishable under a chosen plaintext attack). This means that if we have a service encrypting data and we provide it two separate plaintexts to encrypt, we should not be able to identify which one was encrypted from the ciphertext.
We solve this issue by introducing different block cipher “modes of operation”. The default is ECB which is insecure, and other modes make it secure by introducing randomness and chaining blocks together in various ways.
We’ll review the ECB and OFB modes as they are the what the challenge uses.
Electronic Codebook (ECB)
ECB mode works by splitting the plaintext into blocks and independently encrypts each block. The final ciphertext is the concatenation of each block ciphertext.
A popular example of why this mode fails at providing enough security can been seen with the “ECB Penguin” image. We see that even when the image is encrypted, you can still see the penguin. This is clearly an undesirable property of an encryption scheme. An ideal encryption scheme would make the encrypted image look random as seen in the third image. Modes other than ECB provide this.
Output Feedback (OFB)
OFB introduces an initialization vector, exclusive ORs (XOR), and the ciphertext from the previous block is used as input to another. The IV is a random value chosen at the time of encryption and prefixed to the ciphertext. The combination of the random IV and chaining blocks together solves the issues we described with ECB.
The Solution
With an understanding of the block ciphers used in the prompt, we can review how they were used and find the solution. Recall that the two ciphertexts are generated are as follows:
- The message is encrypted with a random key and IV using AES-128-OFB.
- The same IV is then encrypted with AES-128-ECB using the same key.
Looking at the size of the message ciphertext, we can see that it is 16 bytes long which means the plaintext is exactly one block since AES-128 uses 128-bit blocks. Given this, we can describe the message ciphertext as Encrypt(Key, IV) XOR Message. For the IV encryption, ECB mode was used, so the encrypted IV is simply Encrypt(Key, IV). Due to the property of XOR where a XOR b XOR a = b, we can solve for the plaintext by Ciphertext XOR EncryptedIV which is equivalent to Encrypt(Key, IV) XOR Message XOR Encrypt(Key, IV) = Message.
The solution in Ruby can be found as follows:
message_ct = [“1b08dbade73ae869436549ba781aa077”].pack(“H*”)
iv_ct = [“6f60eadec7539b4930002a8a49289343a7c0024b01568d35d223ae7a9eca2b5c”].pack(“H*”)
message_ct.bytes.zip(iv_ct.bytes).map { |l, r| l ^ r }.pack(“C*”)
This correctly outputs the CTF flag “th1s is sec01234”.
ECDSA Nonce Reuse
By Jake Craige
This challenge is described as follows:
The data below provides two hex encoded ECDSA-SHA256 signatures using the secp256k1 curve for the provided public key. These signatures were generated using the same nonce value which allows recovery of the private key.
Your task is to find the private key and submit it (hex encoded with 0x prefix) as the solution to this challenge.
Pubkey (SER-compressed): 0x2341745fe027e0d9fd4e31d2078250b9c758e153ed7c79d84a833cf74aae9c0bb
Sig #1 (msg): what up defcon
Sig #1 (r, s): (0x5d66e837a35ddc34be6fb126a3ec37153ff4767ff63cbfbbb32c04a795680491, )
Sig #1 (msg): uh oh this isn’t good
Sig #2 (r, s): (0x5d66e837a35ddc34be6fb126a3ec37153ff4767ff63cbfbbb32c04a795680491, 0xd67006bc8b7375e236e11154d576eed0fc8539c3bba566f696e9a5340bb92bee)
The prompt explains what is wrong, so all we have to do is figure out how to solve for the private key. A quick search will provide various explanations of the problem and how to solve it. Wikipedia provides a good explanation of how ECDSA signatures are generated and documents the solution to nonce reuse. We’ll describe the math here using the same variable names as Wikipedia.
Given two signatures s and s’ of different messages digests z and z’ which used the same nonce, the first step is solving for the private key is solving for k.
Now that we know k, we have enough public information to restructure the signature equation and solve for the private key d_a.
We can solve this problem in Python with the following code:
import hashlib
# secp256k1 order
order = int(“fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141”, 16)
# Input from challenge
z = int(hashlib.sha256(“what up defcon”).hexdigest(), 16)
z_prime = int(hashlib.sha256(“uh oh this isn’t good”).hexdigest(), 16)
s = int(“1a53499a4aafb33d59ed9a4c5fcc92c5850dcb23d208de40a909357f6fa2c12c”, 16)
s_prime = int(“d67006bc8b7375e236e11154d576eed0fc8539c3bba566f696e9a5340bb92bee”, 16)
r = int(“5d66e837a35ddc34be6fb126a3ec37153ff4767ff63cbfbbb32c04a795680491”, 16)
# dividing within a field is not standard division so we need to define it as follows
def modinv(a, modulus): return pow(a, modulus — 2, modulus)
def divmod(a, b, modulus): return (a * modinv(b, modulus)) % modulus
# Solve for private key d
k = divmod(z — z_prime, s — s_prime, order)
d = divmod(k * s — z, r, order)
# output challenge flag
print(hex(d))
This correctly outputs the challenge flag 0x128e06938ac462d9.
Linkable Payments
By Max Mikhaylov
This is a cryptography challenge. We will use Python to solve it. I assume that you are familiar with scalar multiplication for elliptic curves over finite fields. If this topic doesn’t sound familiar, read the first 3 chapters of Jimmy Song’s Programming Bitcoin book. This is a prerequisite for understanding the challenge.
For this challenge I need only one nonstandard package — fastecdsa. We use it to do arithmetic on ECC points of brainpoolP160r1 curve. We will be using only two classes from that package: Point and brainpoolP160r1.
Examining the data
Looking at transactions that were broadcast to the node, we see that all of them contain an invalid destination key. The problem clearly establishes the format for ECC points and the destination key doesn’t follow it (‘dest_key’: ‘G0’). It’s not even a valid hex number.
But the transaction public key looks valid. Let’s try converting those public keys to ECC points on brainpoolP160r1 curve. Let’s write a function that converts a single public key to a point on the curve.
def key_to_point(key):
return Point(int(key[2:42], 16), int(key[42:], 16), curve=brainpoolP160r1)
If we try converting some public keys to points with this function, we will get an error: ValueError: coordinates are not on curve <brainpoolP160r1>
It looks like the public key provided by the sender is not on the brainpoolP160r1 curve. In fact, none of the provided public keys are on that curve. From the description of the transaction model from the Cryptonote whitepaper we know that the node needs to perform scalar multiplication using the sender’s transaction public key and its own private key. Is it dangerous for the node to perform this multiplication with a point that is not on the expected curve? Yes! We will find out why in a bit.
If the node’s implementation wasn’t flawed, it would have checked if the public key provided by the sender is on the expected curve and throw an exception if it is not on the curve (just like fastecdsa library does). However, the node accepted this public key, performed scalar multiplication using its private tracking key and tried to compare whether its version of the shared secret (P_prime) is different from the one provided by the sender (P). Only when comparing those values, the node threw an error since one of the values is not a valid ECC point (the destination key provided by the sender). To make matters worse (or better for us as an attacker), the node exposed its version of the shared secret (P_prime) in the log.
Analyzing ECC points
The first hint of the challenge tells us that we need to concentrate on these invalid ECC points provided by the sender. Since the flawed node software doesn’t check if the provided point is on the curve, we can monkey patch the Point class of fastecdsa library to remove the following check:
def point_init_monkey_patch(self, x, y, curve):
self.x = x
self.y = y
self.curve = curve
Point.__init__ = point_init_monkey_patch
We can now try converting tx_pub_key to ECC point for all transactions one more time; no error:
Input:
pub_key_points = txs_to_pub_key_points(txs) # txs is dict of txs.json contents
We can also convert shared secret values from node logs to ECC points, now that we monkey patched the ECC library:
def err_log_to_shared_secret_points(err_log):
shared_secret_points = []
for entry in err_log:
msg = entry[‘err_msg’]
shared_secret = msg.split(‘P_prime=’)[1].split()[0]
shared_secret_point = key_to_point(shared_secret)
shared_secret_points.append(shared_secret_point)
return shared_secret_points
shared_secret_points = err_log_to_shared_secret_points(err_log) # err_log is dict of err_log.json contents
Let’s go back to public key points. The first public key point looks very suspicious. I am talking about the Y-coordinate being 0. Let’s try calculating the order of this point.
Input:
def point_order(p):
for x in range(2, brainpoolP160r1.p):
if x * p == p:
return x — 1
point_order(pub_key_points[0])
Output:
2
This is very low order! Turns out other public key points have low order as well. Does this give us some way to derive the private key used by the node to calculate shared secrets?
Invalid-curve attack
It turns out that these exact conditions allow us to carry out an invalid-curve attack. You can read more about what an invalid-curve attack is in “Guide to Elliptic Curve Cryptography” by Hankerson, Menezes and Vanstone on page 182. Also read a recent CVE-2019–9836 describing this attack in a practical setting (this was the second hint for this challenge).
The gist of the attack: if we can make the node compute shared secrets from low order points of relatively prime order, and can find results of these computations, we can recover the secret using the Chinese Remainder Theorem (CRT). To be more specific, we need the product of all low order points to be greater than the private key in order for the recovered key to be unique (thus, match the private key). If we calculate the product of the order of all points in `pub_key_points`, we can in fact see that this number doesn’t fit in 160 bits, thus has to be larger than the private key used with brainpoolP160r1 curve.
Input:
product = 1
for point in pub_key_points:
product *= point_order(point)
from math import log2
log2(product)
Output:
175.1126248794482 # the product occupies 176 bits in binary representation
First, we need to be able to use the CRT. There are many resources on how CRT works, so you can read those if you are curious about math behind it. For solving this problem, I copied the CRT implementation from Rosetta Code.
We are now ready to perform the attack! The main idea behind this is the following:
- We know that multiplying a low order point by a very large scalar (the private key) will result in a point of the same low order (the shared secret).
- We can calculate the smallest possible scalar that, when multiplied by the public key, will result in the same low order shared secret.
- We can do that by simply trying all possible scalars that are smaller than the order of the public key.
- By bruteforcing the smallest possible scalar that gives us the shared secret when multiplied by the public key, we can construct a system of simultaneous congruences in the exact format that is suitable for applying the CRT. Since the product of all relatively prime orders is greater than the private key we are looking for, the result of applying the CRT is unique.
Input:
v = [] # can think of values in this list as the minimum number of EC additions of E_hat to itself to get shared_secret
moduli = [] # prime moduli of the system
print(“Constructing a system of simultaneous congruences:”)
for P_hat, shared_secret in zip(pub_key_points, shared_secret_points):
order = point_order(P_hat)
# search for shared_secret mod o_prime; i.e. the min number of additions of E_hat to itself to get shared_secret
for x in range(1, brainpoolP160r1.p):
if x * P_hat == shared_secret: # found the min number of additions
print(f’e ≡ {x} mod {order}; ’, end=’’)
v.append(x)
moduli.append(order)
break
Output:
Constructing a system of simultaneous congruences:
e ≡ 1 mod 2; e ≡ 1 mod 11; e ≡ 7 mod 23; e ≡ 1 mod 5; e ≡ 34 mod 41; e ≡ 4 mod 7; e ≡ 273 mod 293; e ≡ 161 mod 691; e ≡ 93 mod 347; e ≡ 7 mod 17; e ≡ 162 mod 229; e ≡ 19 mod 53; e ≡ 7 mod 13; e ≡ 380 mod 977; e ≡ 83 mod 89; e ≡ 82 mod 109; e ≡ 4771 mod 9767; e ≡ 381213 mod 439511; e ≡ 758 mod 10009; e ≡ 14048 mod 26459; e ≡ 11 mod 37; e ≡ 196934 mod 949213;
Input:
e = chinese_remainder(moduli, v)
hex(e)
Output:
‘0xdec1a551f1edc014ba5edefc042019’
This private key hex looks unusual… This is definitely a flag!
P.S. If you are curious about how I found low order points in the first place, see my question on Cryptography Stack Exchange that I asked when working on this challenge.
Schnorrer Signature
By Jesse Posner
This challenge describes a defective signature scheme called Schnorrer signatures. This scheme is nearly identical to Schnorr signatures, however, it contains a critical flaw that allows Schnorrer signatures, unlike Schnorr signatures, to be easily forged. The goal of the challenge is to produce a valid Schnorrer signature for a given public key and message.
A Schnorrer signature, and its defect, are best understood by contrasting them with a Schnorr signature. A Schnorr signature applies the Fiat-Shamir heuristic to the Schnorr identification protocol, an interactive proof-of-knowledge sigma protocol, and transforms it into a digital signature protocol.
In Schnorr, the Fiat-Shamir heuristic challenge is generated by hashing the message and the public nonce, but in Schnorrer the challenge is the hash of the message and the public key. By replacing the public nonce with the public key in the challenge hash, the Schnorrer signature undermines the security of the scheme.
Schnorr Identification Protocol
The Schnorr identification protocol consists of 3 elements: (1) a key generation algorithm, (2) a prover and (3) a verifier. The prover generates a secret, `x`, and wants to prove to the verifier that she knows `x` without revealing it to the verifier.
Both parties will need to agree on some parameters: a cyclic group, with a generator, `G`, and a prime modulus, `q`. For example, the Bitcoin protocol uses the secp256k1 parameters, with a generator specified by an elliptic curve point with compressed coordinates:
02 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798
An uppercase letter, such as `G`, `P`, or `R`, denotes a group element, for example, an elliptic curve point. Lowercase letters denote scalar values, such as `x`, `r`, and `s`.
Key Generation Algorithm
The prover uses the key generation algorithm to produce a public-private key pair, `x` and `P`. `x` is an integer selected at random from a finite field with modulo `q`. The public key `P` is calculated by using `x` as a scalar value and multiplying it by `G`:
```x*G```
The private key, `x`, is the discrete logarithm of `P` with the base `G`, and thus the verifier is unable to efficiently derive the private key from the public key, and so the prover can reveal a public key without revealing the private key, hence the “public” and “private” denotations.
Protocol
Let’s suppose that Alice wants to prove to Bob that she knows the value `x`. Alice begins the Schnorr identification protocol by generating a nonce, `r`, to be used as a scalar, similar to the private key. However, unlike the private key, the nonce must be used just once (“for the nonce”). Alice then computes the value `r*G` to derive the group element `R`, similarly to how the public key was generated. This value, `R`, is typically referred to as the public nonce, or the nonce commitment. Once Alice has her public key, `P`, and public nonce, `R`, she sends those values to Bob.
Bob now must generate another scalar value called the challenge value, `c`. After Bob receives `P` and `R`, he then generates `c` and sends it to Alice. Note that while `c` is independent from `R`, it is very important that Bob wait until he has received `R` from Alice before sending `c` to her. In fact, if Bob fails to do this, and sends `c` to Alice prior to receiving `R`, Alice can trick Bob into believing that she has knowledge of the secret key without actually knowing it. The integrity of the verification depends on `R` being generated prior to `c`, as we will see shortly.
Alice completes the conversation with Bob by multiplying her private key, `x`, by the challenge, `c`, and adding that product to her private nonce, `r`, to produce what is referred to as the `s` value. `s` must be modulo `q` (all scalar values must be modulo `q` so that they fall within the curve order).
We can now see the purpose of the nonce: it allows Alice to produce a value that is the product of (1) the private key, `x`, and (2) a value chosen solely by Bob, namely, the challenge, `c`. Yet Alice must accomplish this without directly disclosing `x` to Bob. If we omitted the nonce from the protocol, then `s` would be equal to `x*c`, and, while this value would indeed prove Alice’s knowledge of `x` to Bob, it does so far too aggressively and allows Bob to trivially compute `x` by dividing `s` by `c`.
```x = s/c```
However, with the addition of the nonce, x is hidden from Bob and cannot be computed solely from `s`.
```x = (s — r)/c```
Upon receiving `s` from Alice, Bob verifies the outputs of the protocol, `s` and `R` as follows: Bob computes `s*G`, and checks whether that value is equal to the sum of (1) the public nonce, `R`, and (2) the public key, `P`, multiplied by the challenge, `c`. Bob can be confident that Alice knows `x` if this equality holds, because Bob scaled `P` by `c`, and yet Alice knew the discrete logarithm of the result (offset by the public nonce), `s`. Thus, unless Alice has an efficient means of calculating discrete logarithms, she must know `x`.
However, as alluded to above, if Bob provides `c` to Alice prior to receiving `R`, then Alice can choose a malicious `R` and trick Bob into verifying the output, despite Alice not actually having knowledge of the private key, `x`, and the nonce, `r`. Alice does this by selecting a random integer modulo `q` to be used as `s`, and then computes `s*G` and `c*P`. Next, Alice subtracts `c*P` from `s*G` to compute `R`.
```R := s*G — c*P```
Now Alice has a valid public nonce, `R`, without knowing the private nonce, `r`, and a valid `s` without knowing the private key, `x`. Thus, we can see that it is critically important that Bob not disclose `c` to Alice until he has received `R` from her, otherwise Alice can choose `R` maliciously, by computing the difference between `c*P` and `s*G`.
Schnorr Signature
The Fiat-Shamir heuristic is a method that transforms Sigma protocols into digital signature schemes. It does this by replacing the challenge value, `c`, with a cryptographic hash of (1) a message, `m`, which is the data that is being signed, and (2) the public nonce, `R`. Requiring `R` as an input to a hash function that creates `c` prevents Alice from computing `R` from `c*P` and `s*G`, because `c` is now generated based on `R`, and thus `R` must preexist `c`.
The signature protocol proceeds similarly to the identity protocol: Alice multiplies her private key, `x`, by the challenge value, `c`, and then adds it to the private nonce, `r`, to produce `s`. The signature consists of the pair of values, `s`, and the nonce commitment, `R`, which are provided to Bob by Alice. Bob can compute `c` himself because `c := H(m || R)`.
The structure of the verification algorithm is the same as the identity protocol: `s*G == R + c*P`
Schnorrer Signature
A Schnorrer signature is identical to a Schnorr signature, except the challenge value, `c`, is a hash of (1) the message and (2) the public key, `P`, instead of (1) the message and (2) the nonce commitment, `R`. This seemingly small modification to the scheme renders it insecure.
The forgery attack proceeds along the same lines as the identification attack described above. In the identification attack, Bob provided the challenge value to Alice prior to receiving the public nonce, `R`. Similarly, because the Schnorrer signature challenge value does not include `R`, Alice can reverse the order of the protocol, and choose an `s` value first, and then calculate `R` as the difference between `s*G` and `c*P`, and thus forge a signature, in other words, with this defect, Alice can produce a valid Schnorrer signature without knowing the private key, `x`, (and also without knowing the nonce, `r`).
Forging A Signature
By Jake Craige
This challenge is described as follows:
Given two Pedersen commitments in and out, you must construct a proof that the difference between the commitment amounts is zero. We’ll use the secp256k1 curve and define `g` as the standard base point of the curve and `h=g^SHA256(“CoinbaesRulez”)`.
We’ll define out input and output commitments as `in=g¹³³⁷⋅h⁹⁸⁷⁶` and `out=g²⁶⁷⁴ ⋅h³⁴⁵⁶` and walk through the evaluation here.
= in⋅out^−1
= (g¹³³⁷⋅h⁹⁸⁷⁶)⋅(g^−2674⋅h³⁴⁵⁶)^−1
= g^(1337+2674)⋅h^(9876−3456)
y = g⁴⁰¹¹⋅h⁶⁴²⁰
We see that this is not a commitment to zero and actually creates more money thaen went into it. Your task is to provide us a `(t, s)` pair that convinces a verifier that `y` is a commitment to zero even though that’s not true.
Here is the input data you should use to create the signature. The elliptic curve points (commitments) are provided in the SEC compressed encoding. For the signature, we’ll use the Schnorr Identification Protocol proof described in the attached PDF. You must use the provided nonce so that we get a deterministic outcome for the CTF verification.
in=0x25b0d4d0ad70054b53c16d6b3269b03e7b8582aa091317cab4d755508062c6f43
out=0x35e3bdfa735f413f2213aa61ae4f7622596feddb96ecc0f263892cb35ca460182
y=0x20ab37bbcc43b8e96714aae06fdc1bbfc386d0165afb69500c9df1553e6c94ed1
nonce=0x19
The submission should be in the format `(t, s)` where both `t` is the hex encoded compressed point and `s` is a hex encoded unsigned integer. They should both have a `0x` prefix and the parenthesis and `,` must be present to verify. An example format would be: `(0xdead, 0xbeef)`.
The problem with the construction defined above is how `h` is selected. For a pedersen commitment to be trusted no one can know the discrete log of `h` with respect to `g`. Restated: no one should know `x` such that `h=g^x`. Knowledge of that allows one to forge commitments.
Recall that our commitment looks like `y=g^a⋅h^b` where `a` is the amount and `b` is the blinding factor. We provide a proof for `y=h^z`. With a non-malicious prover, this proves a commitment to a zero amount because `y=g⁰⋅h^b=h^b`, so we simply prove that we know the blinding factor `b` and verify against the public key `y`.
Unfortunately, by naively deriving `h` from `g`, we know the discrete log and can forge the signature. Here’s how.
We first set up the equality we wish to forge, and restructure it such that everything is done in base `g`. This is the step that can only be done if you know the discrete log of `h` which is the value `x`.
From this, we can solve for the value `z` which is what we need to create the proof. For simpler notation, we drop the base to show how this value is solved for.
With that equation in hand, we can proceed to create the proof. The values for `a, b, x` can be found in the problem statement: `a=4011`, `b=6420`, and `x=SHA256(“CoinbaesRulez”)` We treat the byte output of the SHA256 function as big-endian to represent it as a number.
Using this information we can compute `z` using our equation from before. In Python this can be done as follows:
import hashlib
# secp256k1 order
order = int(“fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141”, 16)
def modinv(a, modulus): return pow(a, modulus — 2, modulus)
a = 4011
b = 6420
x = int(hashlib.sha256(“CoinbaesRulez”).hexdigest(), 16)
z = (a * modinv(x, order) + b) % order
Now that we know `z`, the last step is to create a proof of knowledge of discrete log to submit as the solution flag. This is done using the Schnorr Identification Protocol where we use the Fiat-Shamir transform to make it non-interactive by setting the challenge value to be the big-endian representation of the SHA256 output of the compressed points H, T, and Y concatenated together as bytes. The problem description provides a fixed nonce to make the output deterministic. The solution in Python, building on the former Python code, is:
from fastecdsa.curve import secp256k1
from fastecdsa.point import Point
from fastecdsa.encoding.sec1 import SEC1Encoder
# Challenge input
H = secp256k1.G * x
r = 0x19
# Generate the proof of knowledge of discrete log
T = H * r
Y = H * z
hashInput = SEC1Encoder.encode_public_key(H)
hashInput += SEC1Encoder.encode_public_key(T)
hashInput += SEC1Encoder.encode_public_key(Y)
c = int(hashlib.sha256(hashInput).hexdigest(), 16)
s = (r + c*z) % order
# Print the formatted flag
print(“(0x” + SEC1Encoder.encode_public_key(T).encode(“hex”) + “, 0x” + format(s, ‘x’) + “)”)
To see more about how these Pedersen Commitments are used in practice in blockchains, I recommend reading up on MimbleWimble based blockchains.
Conclusion
This concludes our writeups for the Capture the Coin competition. We hope you enjoyed learning more about a variety of blockchain security topics and can join us again next year.
In the meantime, if solving blockchain security challenges is something that you see yourself doing full time, then join us at Coinbase to help build the most trusted brand in the Crypto here.
This website contains links to third-party websites or other content for information purposes only (“Third-Party Sites”). The Third-Party Sites are not under the control of Coinbase, Inc., and its affiliates (“Coinbase”), and Coinbase is not responsible for the content of any Third-Party Site, including without limitation any link contained in a Third-Party Site, or any changes or updates to a Third-Party Site. Coinbase is not responsible for webcasting or any other form of transmission received from any Third-Party Site. Coinbase is providing these links to you only as a convenience, and the inclusion of any link does not imply endorsement, approval or recommendation by Coinbase of the site or any association with its operators.
All images provided herein are by Coinbase.
Capture the Coin — Cryptography Category Solutions was originally published in The Coinbase Blog on Medium, where people are continuing the conversation by highlighting and responding to this story.
OhNoCoinbase via https://www.ohnocrypto.com/ @Coinbase, @Khareem Sudlow
