Writeup of Stellar puzzle challenge

quest9.md

Puzzle #9 'The clueless Multisig'

This is a writeup and example implementation for puzzle #9 by https://nebolsin.keybase.pub/puzzles/

Our clue was given in form of the pubkey GBW7N7EXR5MV4A34N7LEQGSKZMFEJGW4SQWHUPXGDX2JCGNJH2RXKHUL

When looking up the accounts state we find an threshold setting of 2/3/4, 2 active signers (and one to clawback). The master key has been removed.

The account also posseses an data entry containing

More puzzles: https://erayd.keybase.pub/puzzles.html. Have fun!

<=>

Puzzle9//by+nebolsin//The+Clueless+Multisig=

where the second part is base64 encoded.

All operations required to put the account in its base state are performed in a single transaction.

The submitted XDR is as follows:

AAAAAJQDnG831sTaSXvoh8GYWdlJQ69AEu1zFjaTqoGfJ3a3AAACWAGbM7AAAAAEAAAAAAAAAAAAAAAGAAAAAAAAAAEAAAAAbfb8l49ZXgN8b9ZIGkrLCkSa3JQsej7mHfSRGak+o3UAAAAAAAAAACqeCYgAAAABAAAAAG32/JePWV4DfG/WSBpKywpEmtyULHo+5h30kRmpPqN1AAAABQAAAAEAAAAA6KF3fpZCZZEshXSN3u/zC4N2RFxA7TymoYrfI6IiIzUAAAABAAAAAAAAAAEAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAJQDnG831sTaSXvoh8GYWdlJQ69AEu1zFjaTqoGfJ3a3AAAABQAAAAEAAAAAbfb8l49ZXgN8b9ZIGkrLCkSa3JQsej7mHfSRGak+o3UAAAAFAAAAAAAAAAEAAAAAAAAAAQAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAEAAAACi9BDLJjzLiYzOrD+jN9LTE67InNSUe6IYLKENF06kVkAAAABAAAAAQAAAABt9vyXj1leA3xv1kgaSssKRJrclCx6PuYd9JEZqT6jdQAAAAUAAAAAAAAAAQAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAQAAAAEH7YqDp4KUmJ6ZASBrWwllDkh8GfmXHdtnFdWJPC39FQAAAAMAAAABAAAAAG32/JePWV4DfG/WSBpKywpEmtyULHo+5h30kRmpPqN1AAAABQAAAAAAAAABAAAAAAAAAAEAAAAAAAAAAQAAAAAAAAABAAAAAgAAAAEAAAADAAAAAQAAAAQAAAAAAAAAAAAAAAEAAAAAbfb8l49ZXgN8b9ZIGkrLCkSa3JQsej7mHfSRGak+o3UAAAAKAAAAP01vcmUgcHV6emxlczogaHR0cHM6Ly9lcmF5ZC5rZXliYXNlLnB1Yi9wdXp6bGVzLmh0bWwuIEhhdmUgZnVuIQAAAAABAAAAID7s85Xvf/28vp3m6JbIp//04XvgpbnpXrLPjLpbYrIoAAAAAAAAAAKfJ3a3AAAAQG7kycI2fAlbGS7tUPkcpd7fj0qiJnQIaxI3t1OemQTxLVKaQgDr+0UgMwPIGFXWgVTFLrtWyci8aVXHO3HmWgSpPqN1AAAAQLF6GamqadZBtre3tAspGywIWPe4YakyhmtZcOunBJ3pWfWmJ1h3kwRiRv30kTiKkOcX3K7WNq44SJc78zUUcQ4=

After decoding the Transaction Envelope we find a fee of 600 stroops for 6 operations and no timebound.
We can thus conclude that the used baseFee is 100 stroops.

The two previously mentioned signers are defined as follows:

• Signer1

  • type: hashX
  • hashValue: 8bd0432c98f32e26333ab0fe8cdf4b4c4ebb22735251ee8860b284345d3a9159
  • weight: 3

• Signer2

  • type: preAuthTx
  • hashValue: 07ed8a83a78294989e9901206b5b09650e487c19f9971ddb6715d5893c2dfd15
  • weight: 1

  This being told we can see:

• With only Signer2 we are unable to perform any transactions

• With only Signer1 we are able to perform low and medium threshold transactions:

  • Basically all operations but set Options and Account merge

As our final goal is to merge away or at least payout the content of this account we may argue that we will need a combination of both signers.

To be able to do anything with this account we therefore must crack Signer1:

The HashX Signer

Signer1 is a hash signer, we thus need to find some data (byte[]) - also called "preimage" - which after calculating its sha256 hash is equal to the given hashValue derrived from the ledger. We then can use the preimage encoded in hex to sign any of our transactions with an weight of 1.

On the first glance over the account we noticed a strange data entry.
At first its purpose may seem to brand the challenge account with the challenge website, but uppon further inspection we notice something strange: Normally an data entry has the form $key <=> base64($value) but in this case the base64 encoded value field (Puzzle9//by+nebolsin//The+Clueless+Multisig=) is already in reasonable plain text ($key <=> $value).
Very curious...

After stumbeling upon this curiosity one may want to try this strange value as their preimage.

The obvious seems to use the given value as a plain string for our preimage, but the resulting hash does not match the given one.

A little more puzzeling around and getting more and more fustrated over all the base64 strangeness one will eventually come to use the base64 decoded value (some gibberish) as the preimage and (Eureka!) it fits our hashX signer.

We therefore find our hashX preimage to be base64_decode(Puzzle9//by+nebolsin//The+Clueless+Multisig=)

The pre-signed Transaction

Signer2 is a pre-authorized transaction.

As our final goal is to merge away / payout the reward to an abitrary target and the pre-authorized transaction must not include our public key (else it would be non deterministic) the pre-auth'ed transaction must include a setOptions operation giving us more control over the puzzle account.

To come to our desired outcome we must therefore have a final signing weight of 3 (payment operation) or even 4 (merge / full control).

We already have the known signer Signer1 with weight 1 and thus only need another signer (or increase an existing one) with weight 2 / 3

The required threshold to be able to use a setOptions operation is high (4 in our case).
As the pre-auth'ed transaction has only a weight of 3 it on its own will not be able to complete the required operation.

This is where our Signer1 comes into play. If we sign our potential setOptions transaction with our hashX signer, the resulting transaction will have the required weight of 4.

Now we can play the game of edcuated guessing potential setOptions parameters, where we can already set the following:

• The base fee of the setup transaction was 100 stroops, therefore we can conclude with reasonable certainty that our base fee should be the same.
  This also matches with the balance of the puzzle account (reward + 2.50002) where 2.5 XLM are required as base reserves and two transactions will be required to solve the puzzle and transfer the reward to ones account.
• In each setOptions operation used in the setup transaction the setFlags and clearFlags field was set to 0. (After speaking with the puzzle author it seems like this is a default value of many stellar sdks)
• As sequence numbers must be successive (if not using bumpSeq) the puzzle would be unsolveable if the sequence number was not the next sequence number.
• The timeBound of the creating transaction was set to None (Rhis hint was also amplified by the author, as in most SDKs the default value for this field was changed over the years to now (0,0))

As it seems that we do not have access to the secret key of the puzzle account it would be reasonable to assume that we need to change some threshold weights or increase a known signer (e.g. Signer1) to the required value.

After spending some hours trying different combinations of parameters and questioning their sanity this is were most of the competitors became stuck.

Only after @SiD mentioning something of them having the secret key another idea struck.

The hidden signer

Most of the time a keypair in steller is generated randomly using something like Keypair.random() but there is also the lesser known method of creating a secret key from a seed.

After the helpful tip from @SiD it came to mind that maybe the full keypair of the puzzle account can be derived from some clue hidden on the ledger. (Eureka!)

It appears that the ed25519 keypair derived from the same pre image used for the hashX signer (i.e. using from_raw_ed25519_seed) matches our puzzle accounts keypair.

There now is a new way to gain the required signer weight of 3 or 4:
If we are able to recover the master signing key with a weight of 2 or 3 we can combine it with the hashX signer for the required weight.

This gives us two more possibilites for the setOptions transaction of Signer2 and after a little more trial and error we find the matching hash by creating the following transaction:

• baseFee: 100
• timeBounds: None(!)
• setOptions:
  • masterWeight : 2
  • setFlags : 0
  • clearFlags : 0

This now allows us to create an abitrary transaction with medium threshold (e.g payment) by signing it using Signer1 and the master Key.

quest9.py

from stellar_sdk import Server, Keypair, TransactionBuilder, Network
from stellar_sdk.account import Account
from hashlib import sha256
import base64

server = Server('https://horizon.stellar.org')

# This account was given as the clue

# Normally we would load the account from the ledger
# but as the account was merged away we will emulate it's state before puzzle completion
quest_account = Account("GBW7N7EXR5MV4A34N7LEQGSKZMFEJGW4SQWHUPXGDX2JCGNJH2RXKHUL", 115782658918711296)

# We can derive these values by look at the ledger entries of the given account
pre_signed_tx_hash = "07ed8a83a78294989e9901206b5b09650e487c19f9971ddb6715d5893c2dfd15"
hashX_signer = bytes.fromhex("8bd0432c98f32e26333ab0fe8cdf4b4c4ebb22735251ee8860b284345d3a9159")

# We can find this clue by looking at the data entries of our puzzle account
pre_image = base64.b64decode("Puzzle9//by+nebolsin//The+Clueless+Multisig=")

# The puzzle accounts secret key can be derived from this clue
quest_keypair = Keypair.from_raw_ed25519_seed(pre_image)

if quest_account.account_id() != quest_keypair.public_key:
    print("The derived master secret key does not match!")
    exit()

print("The derived master secret key matches!")

# The same clue leeds to the hashX signer
if sha256(pre_image).hexdigest() != hashX_signer.hex():
    print("The derived hashX signer preimage does not match!")
    exit()

print("The derived hashX signer preimage matches!")



# we now have all the puzzle inputs to solve for our pre signed transaction

BASE_FEE = 100 # we make an educated guess for this value as it's the base value and also was used for every tx creating this puzzle 

presigned_tx = TransactionBuilder(quest_account, Network.PUBLIC_NETWORK_PASSPHRASE, BASE_FEE, v1=False)

# The `clear_flags` and `set_flags` are educationally guessed as they are the same in the creating txs.
# It also seems like these are the default values in many stellar SDKs but not in python
presigned_tx.append_set_options_op(
    clear_flags=0,
    set_flags=0,
    master_weight=2,
    )

presigned_tx = presigned_tx.build()

# We must sign this transaction using our hashX signer in order to archive the required `high` threshold of 4
presigned_tx.sign_hashx(pre_image)

if presigned_tx.hash_hex() != pre_signed_tx_hash:
    print("The hash of the pre-signed transaction candidate does not match!")
    exit()

print("The pre-signed transaction candidate fits the given hash!")

server.submit_transaction(presigned_tx) # This will no longer work as the sequence number of the account was already used


print("We successfully combined all the clues and are now able to submit `medium` transactions!")

# Now we are free to use any `medium` or lower operations for example to manage the data entries

own_tx = TransactionBuilder(quest_account, Network.PUBLIC_NETWORK_PASSPHRASE, BASE_FEE)

own_tx.append_manage_data_op("This puzzle was solved by", base64.b64decode("Smephite\\\\Thank\\you\\nebolsin!"))

own_tx = own_tx.build()

# We need to supply signing weight of `4` (master key + hash signer)

own_tx.sign_hashx(pre_image)
own_tx.sign(quest_keypair)

# This would normally commit the transactions to the server.
# This will not work as the account does no longer exist and if it did its sequence number would not
# match the ones assumed for this puzzle solution

#server.submit_transaction(presigned_tx)
#server.submit_transaction(own_tx)

Beautiful! Really.. just absolutely marvelous 💪 🎉

Since keybase.pub has recently been shut down and discontinued, falling first victim of Zoom cost cutting measures, the original puzzle (subject of this excellent write-up) is now available here: https://pages.nebols.in/puzzles/#puzzle-9.